Привет! На этой неделе мы будем говорить про специальный кейс в машинном обучении, который называется "Обучение без учителя". Это такой случай, когда у нас нет правильных ответов, у нас есть только признаковые описания объектов, и мы хотим понять, как же эти объекты устроены, есть ли там какие-то кучки, есть ли там какая-то структура в этих самых данных. Обычно под обучением без учителя понимают или кластеризацию, или визуализацию, и, собственно, с этими алгоритмами мы с вами и будем знакомиться. Мы узнаем на этой неделе про два алгоритма кластеризации (это k-means и DBSCAN) и про два алгоритма визуализации (РСА и t-SNE). Начнем с k-means, наш первый алгоритм кластеризации. Как устроен k-means (в переводе "k-средних")? В этом алгоритме кластеры представляют собой центроиды. Что это означает? Это означает, что каждый кластер задается координатами центра, а точки относятся к тому кластеру, чей центр к ним ближайший. Вот на этой картинке мы можем задать гиперпараметр k, равный трем, и можем выбрать три центроиды. Выбор этих центроид (это крестики на слайде) однозначно задает, как выглядит кластеризация: каждый объект относится к ближайшей центроиде. И, по сути, мы кластеризовали наши данные на три кластера, на три таких сгустка, таких, что вроде бы они друг от друга далеко, а внутри все точки, которые внутри одного кластера, они все похожи. Это, собственно, основная задача кластеризации. Давайте поймем, как можно эти центроиды найти. На самом деле, существует простой и традиционный алгоритм. Во-первых, нам нужно задать число k, это является гиперпараметром. Пусть k равно четырем (возьмем какое-то просто случайное число — четыре). У нас есть вот эта выборка, и нам нужно найти четыре центроиды. Нам нужно с чего-то начать. Давайте возьмем случайное положение этих центроид. Вот здесь на картинке специально выбраны такие плохие случаи, когда все эти центроиды очень близко получились друг к другу, но, как мы увидим, даже в таком случае k-means может разрулить эту ситуацию. Выбираем четыре случайных центроиды. Дальше, так как они являются центроидами, то нам нужно все объекты присоединить как бы к ближайшему кластеру. Присоединяем каждый объект к ближайшей центроиде. А теперь, так как это центроида, то она должна быть где-то по центру своего кластера, правда? И кажется логичным теперь взять и пересчитать эти центроиды так, чтобы они были в центре масс точек, которые относятся именно к ней. То есть для каждой центроиды берем все точки, которые к ней принадлежат, и считаем просто среднюю, и наши центроиды сдвигаются. Теперь, когда у нас получилось новое положение центроид, наши связи с предыдущей итерацией, которые здесь выглядят как красные ребра, уже не валидные. Эти связи нужно пересчитать, потому что центроиды сдвинулись, и ближайшая точка теперь может стать другой. Поэтому для каждой точки нужно пересчитать расстояние до всех центроид и выбрать минимальное. Мы переподключили точки, и теперь можем повторить делать то же самое, что мы делаем, в цикле. Для каждой точки нужно теперь пересчитать заново эти центроиды и опять переподключить точки к ближайшей центроиде. И так можно делать довольно долго. Здесь вы видите анимацию, как это все выглядит в таком замедленном варианте. На компьютере это все работает очень быстро, но здесь мы можем проследить глазами, как это работает: начинаем со случайных точек, от случайных центроид (их у нас всего четыре), подключаем к ним точки, сдвигаем центроиды, и так в цикле. Можно посмотреть на еще другой пример, например, для k, равного трем. Здесь инициализация тоже не очень была удачная: все три точки, три центроида наших начальных были в одной области пространства, но тем не менее им удалось разбежаться по всей картинке и найти вот эти три сгустка данных. Но может показаться, что это всегда так классно работает. На самом деле это не совсем так. Вот здесь есть пример, когда найденные центроиды не совсем правильные, не те, которые мы ожидаем, когда мы видим эту картинку глазами. Здесь у нас картинка Микки Мауса, и хочется найти три центроиды, которые отвечают за голову и за ушки. Здесь начальная инициализация была неудачной, и наши центроиды просто перестают двигаться после какого-то момента, то есть они находят какой-то локальный вот этот оптимум и дальше не сдвигаются. То есть все зависит довольно сильно от инициализации, и она может быть неудачной. Собственно, в этом и заключается алгоритм k-средних — это самый простой алгоритм кластеризации, и его реализовать очень просто, и он работает даже на огромных массивах данных, потому что все, что нам нужно сделать, на каждой итерации к каждой точке найти ближайшую центроиду, которых как правило не так много, — это параметр k, который мы задаем руками, до сотен каких-то может он, например, изменяться. Но у этого алгоритма есть и минусы: из-за того, что он такой простой, он не может находить кластеры причудливой формы, то есть этот алгоритм ищет только кластеры, которые такие выпуклые. Это все следует из того, как мы определили вообще кластеры, что они задаются центроидами, и каждая точка относится к ближайшей центроиде. Это означает, что у нас получаются такие ячейки ближайших соседей, и они, конечно же, выпуклые, то есть найти какой-нибудь сложный кластер при помощи k-means не получится. Еще один минус, что нам нужно вот это число k задавать руками, и не совсем понятно, каким его действительно взять. Можно перебрать разные по сетке и выбрать то, при котором, например, сумма внутрикластерных расстояний будет минимальная, а межкластерных максимальная. Существует огромное количество метрик, и люди пытаются разными эвристиками это число k выбирать.