Разбираемся в ML без воды: от базы до Attention. Часть 13: Кластеризация и k-means / Хабр

В предыдущей главе мы рассматривали ситуацию, когда данных слишком много: большое количество признаков затрудняет их анализ, увеличивает вычислительные затраты и приводит к различным негативным эффектам, связанным с высокой размерностью. Для решения этой проблемы мы изучили понятие понижения размерности.

Теперь перейдем к совершенно другой ситуации. Предположим, что с данными все в порядке: признаков достаточно, они хорошо описывают объекты, однако отсутствует целевая переменная (target). Мы не знаем, к каким классам принадлежат объекты, а значит, привычные алгоритмы обучения с учителем применять уже нельзя.

Возникает вопрос: можно ли, имея только сами объекты и их признаки, автоматически обнаружить в данных закономерности и выделить группы похожих объектов? Именно эту задачу решают алгоритмы кластеризации.

Кластеризация

Кластеризация — это задача обучения без учителя, целью которой является разбиение множества объектов на группы (кластеры) таким образом, чтобы объекты внутри одного кластера были максимально похожи друг на друга, а объекты из разных кластеров — максимально различались.

Пусть задан набор объектов $X={x_1,x_2,\ldots,x_n}$ , где каждый объект $x_i\in\mathbb{R}^d$ имеет признаков.

В отличие от задач классификации, для каждого объекта неизвестна его принадлежность к какому-либо классу. То есть обучающая выборка состоит только из матрицы признаков $X\in\mathbb{R}^{n\times d}$ , а вектор целевых значений $y=(y_1,\ldots,y_n)$ отсутствует.

Задача состоит в разбиении множества на такие непересекающиеся подмножества $C_1, \dots, C_k$ , что каждый объект принадлежит ровно одному кластеру, а объекты внутри одного кластера являются максимально похожими друг на друга. Здесь — количество таких подмножеств (кластеров).

Раз речь идет о схожести объектов, естественно (в очередной раз) обратиться к понятию расстояния. Идея состоит в следующем: чем меньше расстояние между объектами и , тем более вероятно, что они должны принадлежать одному и тому же кластеру.

Но что насчет самих кластеров? Чтобы понять, насколько "хороша" отдельная группа $C_{k}$ , логично посчитать суммарное расстояние между всеми парами точек внутри нее. Если группа "хорошая" эта сумма должна быть минимальной. Запишем это:

$\Phi (C_{k})=\frac{1}{2|C_{k}|}\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}$

Коэффициент $\frac{1}{2}$ нужен, ибо мы считаем как расстояние так и .

А деление на количество элементов в кластере ( $\vert C_k \vert$ ) — просто нормализация.

Суммируя данное выражение по всем кластерам мы получим нашу лосс функцию, которую нужно минимизировать:

$\mathcal{L}(C)=\sum_{k=1}^{K}\Phi(C_{k})=\sum_{k=1}^{K}\frac{1}{2|C_{k}|}\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}\rightarrow \min _{C}$

Но считать попарные расстояния между всеми точками внутри кластеров вычислительно тяжело. Поэтому попробуем упростить внутреннюю сумму. Распишем квадрат нормы разности векторов через скалярное произведение:

$\|x_{i}-x_{j}\|{}^{2}=\|x_{i}\|{}^{2}-2\langle x_{i},x_{j}\rangle +\|x_{j}\|{}^{2}$

Далее подставим это разложение обратно в двойную сумму для кластера $C_{k}$ :

$\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}=\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\left(\|x_{i}\|{}^{2}-2\langle x_{i},x_{j}\rangle +\|x_{j}\|{}^{2}\right)$

Разложим это выражение на три отдельные суммы:

Так как $\Vert{}x_i\Vert{}^2$ не зависит от индекса , то внутреннее суммирование по $x_{j}$ превращается в умножение на количество элементов в кластере $\vert{}C_k\vert{}$ :

$\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}\|{}^{2}=|C_{k}|\sum_{x{i}\in C_{k}}\|x_{i}\|{}^{2}$
Аналогично для третьей слагаемого:

$\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{j}\|{}^{2}=|C_{k}|\sum_{x_{j}\in C_{k}}\|x_{j}\|{}^{2}$

Поскольку и — это просто индексы суммирования по одному и тому же множеству, первая и третья суммы равны. Вместе они дают:
$2\vert{}C_k\vert{} \sum_{x_i \in C_k} \Vert{}x_i\Vert{}^2$
Для средней части выражения, используя линейность скалярного произведения, мы можем вынести знаки суммирования внутрь аргументов:

$-2\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\langle x_{i},x_{j}\rangle =-2\left\langle\sum_{x_{i}\in C_{k}}x_{i},\sum_{x_{j}\in C_{k}}x_{j}\right\rangle$

Собираем все три части вместе:

$\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}=2|C_{k}|\sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-2\left\langle\sum_{x_{i}\in C_{k}}x_{i},\sum_{x_{j}\in C_{k}}x_{j}\right\rangle$

Теперь введем вектор $\mu _{k}$ , который является средним арифметическим всех точек кластера (центром масс):

$\mu_{k}=\frac{1}{|C{k}|}\sum_{x_{i}\in C_{k}}x_{i}\implies \sum_{x_{i}\in C_{k}}x_{i}=|C_{k}|\mu_{k}$

Подставим это в наше уравнение:

$\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}=2|C_{k}|\sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-2\langle |C_{k}|\mu_{k},|C_{k}|\mu_{k}\rangle$ $\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}=2|C_{k}|\sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-2|C_{k}|{}^{2}\|\mu_{k}\|{}^{2}$

Разделим обе части на $2\vert{}C_k\vert{}$ , как это было в нашей исходной функции $\Phi(C_k)$ :

$\frac{1}{2|C_{k}|}\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2}=\sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-|C_{k}|\|\mu _{k}\|{}^{2}$

И так как

$\sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-|C_{k}|\|\mu_{k}\|{}^{2}=\sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-2|C_{k}|\|\mu_{k}\|{}^{2}+|C{k}|\|\mu_{k}\|{}^{2}=$ $= \sum_{x_{i}\in C_{k}}\|x_{i}\|{}^{2}-2\langle \sum_{x_{i}\in C_{k}}x_{i},\mu_{k}\rangle +\sum {x_{i}\in C_{k}}\|\mu_{k}\|{}^{2}=\sum_{x_{i}\in C_{k}}\left(\|x_{i}\|{}^{2}-2\langle x_{i},\mu_{k}\rangle +\|\mu_{k}\|{}^{2}\right)$

Получаем:

$\frac{1}{2|C_{k}|}\sum_{x_{i}\in C_{k}}\sum_{x_{j}\in C_{k}}\|x_{i}-x_{j}\|{}^{2} = \sum_{x_{i}\in C_{k}}\|x_{i}-\mu_{k}\|{}^{2}$

Благодаря этому выводу наш лосс $\mathcal{L}(C)$ принимает гораздо более простой и красивый вид:

$\mathcal{L}(C,\mu )=\sum_{k=1}^{K}\sum_{x_{i}\in C_{k}}\|x_{i}-\mu_{k}\|{}^{2}\rightarrow \min_{C,\mu }$

Что это значит?

Оказывается, что вместо того, чтобы попарно сравнивать все объекты друг с другом внутри группы, мы пришли к понятию центроида $\mu_{k}$ . Теперь нам достаточно сравнивать каждый объект только с "центром тяжести" его кластера.

Тогда в чем подвох?

Печальная сторона данной задачи в том, что они (в общем случае) является задачей класса NP. Говоря простым языком, она нерешаема в чистом виде.

Печальная сторона заключается в том, что в общем виде минимизация этого функционала является NP-трудной задачей. Говоря простым языком, её невозможно решить абсолютно точно за разумное время.

Раз мы не можем найти глобальный оптимум в лоб, на помощь приходят приближенные, но очень быстрые итеративные методы. И самый известный среди них — алгоритм K-Means.

K-means

Раз лосс функция $\mathcal{L}(C, \mu)$ зависит одновременно от двух неизвестных: от разбиения на кластеры и от координат центроидов $\mu$ , мы можем применить стратегию поочередного шага: фиксируем одну переменную, оптимизируем по другой, а потом меняем их местами. Это частный случай так называемого EM-алгоритма (Expectation-Maximization).

Работает это таким образом:

Инициализация
Случайным образом выбираем точек из нашего пространства и объявляем их первыми, стартовыми центроидами $\mu_1, \mu_2, \dots, \mu_K$ .
Привязка к кластерам
Временно считаем, что центроиды $\mu_{k}$ заморожены и никуда не двигаются. Наша задача — распределить объекты по кластерам $C_{k}$ так, чтобы минимизировать лосс.
Поскольку центры зафиксированы, лосс распадается на сумму независимых слагаемых для каждого объекта. Чтобы минимизировать расстояние, нам достаточно приписать каждый объект $x_{i}$ к ближайшему к нему центроиду. Математически это выглядит так:
$C_{k}=\{x_{i}:\arg \min_{j}\|x{i}-\mu _{j}\|{}^{2}=k\}$
Пересчет центроидов
Теперь наоборот: мы зафиксировали, какой объект в каком кластере находится. Нам нужно обновить координаты центроидов $\mu _{k}$ , чтобы они встали в оптимальные позиции.
И вот тут выстреливает наш предыдущий математический вывод. Мы уже доказали, что минимум внутрикластерного расстояния достигается ровно тогда, когда $\mu_{k}$ равен среднему арифметическому (центру масс) всех точек, попавших в этот кластер:

$\mu_{k}=\frac{1}{|C_{k}|}\sum_{x_{i}\in C_{k}}x_{i}$

Повторяем шаг 2 и шаг 3 по кругу до тех пор, пока алгоритм не сойдется. Критерий остановки прост: либо объекты перестали переходить из кластера в кластер, либо изменение лосса упало ниже заданного порога.

Так как количество вариантов разбить N точек на K групп огромно, но всё же конечно, а лосс на каждом шаге монотонно не возрастает, алгоритм гарантированно остановится за конечное число шагов.

Но здесь нас поджидает главная проблема. То, что алгоритм сошелся, вообще не означает, что он нашел глобальный минимум нашей лосс функции. K-Means — жадный алгоритм. Он с легкостью застревает в локальных минимумах. Финальный результат сильно зависит от того, где именно стояли центроиды на самом первом шаге.

K-Means++

Как говорится, куда без плюсов?

Как мы уже поняли, классический алгоритм Ллойда (случайный выбор стартовых центроидов) превращает задачу кластеризации в казино. Потому умные люди придумали способ для начальной инициализации центроидов.

Её ключевая идея крайне простая: первые центроиды нужно расталкивать как можно дальше друг от друга.

Но перед тем, как обсудим алгоритм, взглянем на теорему, на которую он опирается:

Пусть первый центроид выбирается случайно, а каждый следующий центроид выбирается из выборки как случайную величину с плотностью вероятности, пропорциональной квадрату расстояния до уже ближайшего выбранного центра:

$P(x_{i})\propto D(x_{i})^{2}$ , где $D(x_{i})^{2}=\min_{j}|x_{i}-\mu_{j}|{}^{2}$ .

Тогда математическое ожидание итогового значения лосс функции $\mathbb{E}[\mathcal{L}]$ будет жестко ограничено сверху относительно глобального минимума $\mathcal{L}_{opt}$ :

$\mathbb{E}[\mathcal{L}]\le 8\cdot (\ln K+2)\cdot \mathcal{L}_{opt}$

Чтобы реализовать это на практике, перед запуском основного цикла K-Means мы делаем 4 простых шага:

Шаг 1. Первый центр

Выбираем абсолютно первый центроид $\mu_1$ случайно из нашей выборки объектов с равномерным распределением;

Шаг 2. Расчет расстояний

Для каждого объекта $x_{i}$ в нашей выборке считаем квадрат расстояния до ближайшего из уже выбранных центроидов, который обозначим как ;

Шаг 3. Вероятностный выбор следующего центра

Превращаем наши расстояния в честное распределение вероятностей (чтобы сумма была равна 1). Вероятность выбрать объект $x_{i}$ в качестве нового центра становится равна:

$P(x_{i})=\frac{D(x_{i})^{2}}{\sum_{m=1}^{n}D(x_m)^{2}}$

Если объект близок к уже выбранным центрам, его $D(x_i)^2 \approx 0$ и шанс стать центром нулевой;

Шаг 4. Цикл

Повторяем Шаги 2 и 3 до тех пор, пока не наберем ровно K центроидов. Как только они набраны — запускаем стандартный базовый цикл K-Means.

Как выбрать количество кластеров?

Очевидно, если взять , то задача кластеризации потеряет свой смысл. Ежели мы возьмем , равный числу объектов в датасете, то с одной стороны, все наши точки станут центроидами отдельных кластеров, и лосс будет нулевой, но мы получим ровным счетом 0 пользы.

Оказывается, что изначально при увеличении, лосс падает довольно быстро. Представьте, что мы делим планету на страны, затем на города, на районы и т.д. Но в один прекрасный момент когда мы уже разделяем дом по квартирам, можно заметить, что лосс падает уже с маленькой скоростью. Соответственно, логичный вариант — выбрать такое количество кластеров, после которго темп убывания лосса замедляется.

Этот нехитрый способ выбора гиперпараметра k имеет свое название — метод локтя (Elbow Method)

Но, несмотря на свою простоту, данный метод имеет две ключевые проблемы. Во-первых, для такого метода нам нужно построить очень много одинаковых моделей с разными , т.е. это вычислительно сложно.

Во-вторых, на практике такие графики не так красивы и ясны как на рисунке. То есть возникает уже субъективщина:

наглядная демонстрация, которую я скоммуниздил с этих ваших интернетов

Рассмотрим другой подход, который называется коэффициент силуета (Silhouette Score):

Возьмем некий объект $x_{i}$ , который наш алгоритм отнес к кластеру . Посчитаем для него два показателя:

Внутрикластерное расстояние :
Это среднее расстояние от нашей точки до всех остальных точек в её же кластере:
$a(x_{i})=\frac{1}{|A|-1}\sum_{j\in A,j\ne i}\|x_{i}-x_{j}\|$
Чем меньше тем плотнее и кучнее сидит кластер.
Межкластерное расстояние :
Теперь найдем самый близкий к нам чужой кластер (назовем его кластер). Посчитаем среднее расстояние от $x_{i}$ до всех точек этого соседа. Если соседних кластеров несколько, мы берем тот, у которого это среднее расстояние оказалось минимальным:
$b(x_{i})=\min_{C\ne A}\left(\frac{1}{|C|}\sum_{j\in C}\|x_{i}-x_{j}\|\right)$
Кластер, на котором достигается этот минимум, называют следующим наилучшим кандидатом для точки $x_{i}$ .

Теперь собираем их вместе в одну формулу и получаем силуэт для точки $x_{i}$ :

$s(x_{i})=\frac{b(x_{i})-a(x_{i})}{\max \big(a(x_{i}),b(x_{i})\big)}$

Деление на максимум нормирует метрику в строгие границы: $s(x_i) \in [-1, 1]$ .

Посмотрим, что говорят нам разные значения :

$s(x_i) \approx 1$ : Это значит, что внутрикластерное расстояние ничтожно, а до соседей — далеко. Точка идеально лежит в своем кластере.
$s(x_i) \approx 0$ : Точка лежит на границе двух кластеров, и алгоритм с трудом мог отнести её как в один, так и в другой.
$s(x_i) \approx -1$ : Это уже тревожный звоночек: точка живет в кластере , хотя среднее расстояние до чужого кластера гораздо меньше. Алгоритм ошибся с этой точкой.

Теперь, чтобы оценить общее качество кластеризации для выбранного гиперпараметра , мы просто берем среднее арифметическое силуэтов всех точек датасета:

$\text{Silhouette\ Score}=\frac{1}{N}\sum_{i=1}^{N}s(x_{i})$

Перебирая разные значения , считаем Silhouette Score, и берем такой , при котором этот коэффициент максимален. Никаких угадываний по графикам — чистая математика.

Но за математическую строгость приходится платить.

Метод локтя считается очень быстро, потому что расстояние до центроидов — это побочка работы самого K-Means $\mathcal{O}(N)$ . А вот для расчета Силуэта нам приходится вычислять попарные расстояния между всеми объектами выборки, а значит работать за $\mathcal{O}(N^2)$ .

Поэтому на больших данных Силуэт считают не по всей выборке, а по случайной репрезентативной подвыборке (subsample).

Заключение

На этом тринадцатая часть нашего погружения в ML подходит к концу, а вместе с ней и весь цикл, посвященный классическому машинному обучению.

Конечно, мир кластеризации не ограничивается одними лишь "средними". K-Means идеален для поиска сферических, круглых сгустков данных, но почти бессилен перед сложными геометрическими формами. Для вытянутых лент, вложенных колец и данных с кучей шума существуют принципиально другие подходы — например, плотностной алгоритм DBSCAN. Вместо центроидов он ищет области высокой плотности точек и умеет самостоятельно определять количество кластеров, попутно вычищая выбросы. Но это уже совсем другая история...

Что дальше?

За 13 частей мы разобрались с линейными моделями, деревьями, бустингами, регуляризацией, понижением размерности, кластеризацией и много чем ещё на уровне "как работают базовые алгоритмы под капотом". Как говорится ни одним ~~хлебом~~ .fit() и .predict()-ом едины.

В следующих частях мы перейдем уже в глубокое обучение (Deep Learning). Посмотрим на первые полносвязные нейросети, разберем обратное распространение ошибки и поймем, как матрицы и производные заставляют машине думать.