K-means clustering 🎯

В уроке 303 ты подробно разбирал главный водораздел машинного обучения: есть ли у тебя размеченные данные с известными правильными ответами или нет. Все модели, которые курс разбирал после этого — логистическая регрессия, метод ближайших соседей, наивный байесовский классификатор, деревья решений, случайный лес, градиентный бустинг, метод опорных векторов (уроки 313–319) — принадлежат к миру обучения с учителем: каждая из них училась на данных, где для каждого объекта заранее было известно правильное значение целевой переменной, будь то класс «спам/не спам» или конкретное число. Сегодняшний урок — первый в курсе, где эта опора исчезает полностью. У тебя есть только объекты и их признаки, и никакой разметки, никакого «правильного ответа», на который можно было бы равняться.

Представь интернет-магазин с миллионом покупателей. Для каждого известны сумма покупок, частота визитов, средний чек, категории интересов — десятки признаков. Но никто заранее не пометил покупателей ярлыками «премиальный клиент», «случайный заходчик» или «охотник за скидками» — таких меток попросту не существует в данных. Задача при этом всё равно осмысленная и практически важная: разбить покупателей на группы похожих друг на друга людей, чтобы потом с каждой группой работать по-своему — предлагать разные акции, разные рассылки на электронную почту, разный сервис. Это и есть задача кластеризации (clustering) — разбиения множества объектов на группы (кластеры) так, чтобы объекты внутри одной группы были похожи друг на друга, а объекты из разных групп — непохожи, причём сами группы заранее не заданы и не известны, их нужно обнаружить.

K-means clustering, он же метод k-средних (дальше в тексте — именно этот перевод), — самый популярный и самый простой для понимания алгоритм кластеризации, и не случайно именно он открывает блок обучения без учителя в этом курсе. Идея метода интуитивно понятна почти сразу: выбери k точек-«центров», отнеси каждый объект к ближайшему центру, пересчитай центры как среднее своих объектов, повтори. Простота этой идеи, впрочем, скрывает за собой содержательную математику — метод k-средних можно строго сформулировать как оптимизационную задачу, у него есть гарантия сходимости (но не гарантия найти лучшее возможное решение), а выбор числа кластеров k — отдельная нетривиальная задача, для которой существуют конкретные количественные методы.

В этом уроке ты разберёшь: сам алгоритм пошагово с полной трассировкой на маленьком датасете, оптимизационную интерпретацию через минимизацию WCSS (within-cluster sum of squares, сумма квадратов расстояний внутри кластеров) и почему задача невыпуклая, из-за чего обычный k-means может застрять в неудачном локальном решении, умную инициализацию k-means++, которая эту проблему смягчает, метод локтя и коэффициент силуэта — два способа количественно выбрать число кластеров k, а также ограничения метода, которые в уроке 322 приведут нас к принципиально другому алгоритму кластеризации, DBSCAN.

История

Идея разбивать многомерные точки на группы вокруг центров возникла независимо в нескольких областях сразу, что для фундаментальных алгоритмов машинного обучения случается на удивление часто. Наиболее известна работа Стюарта Ллойда (Stuart Lloyd), инженера из Bell Labs, который в 1957 году, работая над задачей квантования сигналов импульсно-кодовой модуляции для цифровой передачи речи, предложил итеративный алгоритм разбиения точек на группы вокруг представительных «центров тяжести» — по сути, ровно ту процедуру, которую сегодня называют алгоритмом Ллойда и которая лежит в основе классического k-means. Задача Ллойда была сугубо инженерной: сжать непрерывный сигнал в конечный набор уровней так, чтобы ошибка квантования была минимальной, — но математическая структура этой задачи оказалась идентична задаче кластеризации точек в пространстве произвольной природы.

Здесь кроется любопытная особенность истории этого алгоритма: сама работа Ллойда оставалась внутренним техническим отчётом Bell Labs и была официально опубликована в открытой печати только в 1982 году, спустя четверть века, под названием «Least squares quantization in PCM». За эти двадцать пять лет тот же самый алгоритм несколько раз переоткрывался независимо разными исследователями под разными именами — в частности, название «k-means» в контексте статистической кластеризации ввёл в 1967 году Джеймс Маккуин (James MacQueen), предложивший похожую, но не идентичную итеративную процедуру. Именно поэтому в литературе можно встретить оба названия — «алгоритм Ллойда» и «k-means» — которые на практике сегодня чаще всего обозначают один и тот же базовый итеративный процесс: назначить точки ближайшим центрам, пересчитать центры, повторить.

Простота идеи и вычислительная дешёвость алгоритма сделали его невероятно живучим: несмотря на возраст, серьёзно превышающий полвека, и на давно известные ограничения (о них — в конце урока), k-means остаётся одним из самых используемых алгоритмов кластеризации в промышленном машинном обучении. Ключевое усовершенствование пришло значительно позже: в 2007 году Дэвид Артур (David Arthur) и Сергей Васильвицкий (Sergei Vassilvitskii) из Стэнфорда опубликовали k-means++ — метод умной инициализации начальных центров, который не меняет сам итеративный процесс Ллойда, но радикально повышает шансы алгоритма сойтись к хорошему, а не к случайно неудачному решению, и сегодня является настройкой по умолчанию практически во всех промышленных реализациях, включая sklearn.cluster.KMeans.

Алгоритм k-means: центроиды, назначение, пересчёт

Интуиция

Представь, что тебе нужно расставить k пунктов раздачи гуманитарной помощи по городу так, чтобы каждому жителю было удобно дойти до ближайшего пункта, но сами адреса жителей заранее неизвестны — известны только точки на карте, где они живут. Разумная стратегия: поставить пункты примерно наугад, посмотреть, кто к какому пункту оказался ближе всего, затем передвинуть каждый пункт в «центр тяжести» своей группы жителей — туда, где суммарный путь до всех «своих» жителей минимален, — и повторить эту процедуру снова и снова, пока пункты не перестанут заметно сдвигаться. Именно так работает k-means: «пункты» — это центроиды (centroid, буквально «центр тяжести» кластера), а «жители» — точки данных.

Алгоритм состоит из четырёх регулярно повторяющихся шагов, и всё, что он делает, — это попеременно решает две связанные подзадачи: если центроиды зафиксированы, к какому из них ближе каждая точка, и если разбиение на группы зафиксировано, где должен находиться центр каждой группы. По отдельности обе подзадачи решаются тривиально (посчитать расстояния и сравнить их; посчитать среднее координат), но вместе, друг за другом, они превращаются в мощный итеративный процесс, который постепенно «расставляет» и центроиды, и границы кластеров на свои места.

Алгоритм

Алгоритм k-means (алгоритм Ллойда). Дан набор точек $x_1, \dots, x_N \in \mathbb{R}^d$ и число кластеров $k$.

1. Инициализация. Случайно выбрать $k$ точек в качестве начальных центроидов $\mu_1, \dots, \mu_k$ (или использовать k-means++, см. ниже).
2. Назначение (assignment step). Для каждой точки $x_i$ найти ближайший центроид по евклидову расстоянию и отнести точку к соответствующему кластеру: $$c_i = \arg\min_{j \in \{1,\dots,k\}} \|x_i - \mu_j\|^2$$
3. Обновление (update step). Пересчитать каждый центроид как среднее всех точек, отнесённых к его кластеру: $$\mu_j = \frac{1}{|C_j|}\sum_{x_i \in C_j} x_i$$
4. Повтор. Вернуться к шагу 2. Остановиться, когда назначения точек кластерам (или сами центроиды) перестают меняться между итерациями — это и есть сходимость алгоритма.

Разбор примеров

Пример 1 (полная трассировка k-means на шести точках, $k=2$). Возьмём датасет из шести точек на плоскости: $A(1,1)$, $B(1,2)$, $C(2,1)$, $D(8,8)$, $E(8,9)$, $F(9,8)$ — визуально это явно две плотные группы: одна около $(1,1)$, другая около $(8,8)$. Зададим $k=2$ и в качестве начальных центроидов возьмём саму точку $A(1,1)$ и точку $D(8,8)$ (для наглядности инициализация здесь намеренно уже «удачная» — к неудачной инициализации мы вернёмся в примере 2).

Итерация 1, шаг назначения. Считаем квадрат евклидова расстояния от каждой точки до $\mu_1=(1,1)$ и $\mu_2=(8,8)$: для $A$ — $0$ и $98$, ближе $\mu_1$; для $B(1,2)$ — $1$ и $85$, ближе $\mu_1$; для $C(2,1)$ — $1$ и $85$, ближе $\mu_1$; для $D(8,8)$ — $98$ и $0$, ближе $\mu_2$; для $E(8,9)$ — $113$ и $1$, ближе $\mu_2$; для $F(9,8)$ — $113$ и $1$, ближе $\mu_2$. Получаем разбиение: кластер 1 $=\{A,B,C\}$, кластер 2 $=\{D,E,F\}$.

Итерация 1, шаг обновления. Новый центроид кластера 1: $\mu_1 = \left(\frac{1+1+2}{3}, \frac{1+2+1}{3}\right) = (1{,}3333;\ 1{,}3333)$. Новый центроид кластера 2: $\mu_2 = \left(\frac{8+8+9}{3}, \frac{8+9+8}{3}\right) = (8{,}3333;\ 8{,}3333)$.

Итерация 2, шаг назначения. Пересчитаем расстояния до новых центроидов. Очевидно (в силу того, насколько плотно и далеко друг от друга расположены две исходные группы), что каждая точка снова окажется ближе к центроиду своей же группы: $A, B, C$ по-прежнему ближе к $\mu_1$, $D, E, F$ — к $\mu_2$. Разбиение на кластеры не изменилось.

Проверка сходимости. Поскольку назначения точек кластерам не изменились между итерацией 1 и итерацией 2, центроиды при следующем шаге обновления тоже не изменятся — алгоритм сошёлся. Итоговый результат: кластер 1 $=\{A,B,C\}$ с центроидом $(1{,}3333;\ 1{,}3333)$, кластер 2 $=\{D,E,F\}$ с центроидом $(8{,}3333;\ 8{,}3333)$ — ровно то разбиение, которое интуитивно ожидалось по расположению точек.

Пример 2 (та же задача, но неудачная инициализация — иллюстрация чувствительности к старту). Возьмём тот же датасет $A(1,1), B(1,2), C(2,1), D(8,8), E(8,9), F(9,8)$, но теперь инициализируем центроиды неудачно: $\mu_1 = A(1,1)$ и $\mu_2 = B(1,2)$ — обе начальные точки взяты из одной и той же «настоящей» группы.

Итерация 1, шаг назначения. Расстояния до $\mu_1=(1,1)$ и $\mu_2=(1,2)$: для $A$ — $0$ и $1$, ближе $\mu_1$; для $B$ — $1$ и $0$, ближе $\mu_2$; для $C(2,1)$ — $1$ и $2$, ближе $\mu_1$; для $D(8,8)$ — $98$ и $85$, ближе $\mu_2$; для $E(8,9)$ — $113$ и $98$, ближе $\mu_2$; для $F(9,8)$ — $113$ и $98$, ближе $\mu_2$. Получаем разбиение: кластер 1 $=\{A,C\}$, кластер 2 $=\{B,D,E,F\}$ — уже на первом шаге вторая «настоящая» группа целиком поглощена одним кластером вместе с точкой $B$ из первой группы.

Итерация 1, шаг обновления. Новый $\mu_1 = \left(\frac{1+2}{2}, \frac{1+1}{2}\right) = (1{,}5;\ 1{,}0)$. Новый $\mu_2 = \left(\frac{1+8+8+9}{4}, \frac{2+8+9+8}{4}\right) = (6{,}5;\ 6{,}75)$.

Итерация 2, шаг назначения. Расстояние от $B(1,2)$ до нового $\mu_1(1{,}5;\,1{,}0)$: $(1-1{,}5)^2+(2-1)^2=0{,}25+1=1{,}25$. Расстояние от $B$ до $\mu_2(6{,}5;\,6{,}75)$: $(1-6{,}5)^2+(2-6{,}75)^2=30{,}25+22{,}5625=52{,}8125$. Точка $B$ по-прежнему заметно ближе к $\mu_1$, чем к $\mu_2$ — казалось бы, на следующей итерации она должна «вернуться» в кластер 1. Проверим: $\mu_1$ после этого пересчёта окажется $(1{,}3333;\,1{,}3333)$ — то же самое значение, что и в примере 1! Дальнейшие итерации в этом конкретном случае действительно сходятся к тому же самому правильному разбиению $\{A,B,C\}$ и $\{D,E,F\}$, потому что даже неудачно стартовавший $\mu_1$ остался достаточно близко к первой группе, чтобы «перетянуть» точку $B$ обратно.

Обрати внимание на важный нюанс: в этом конкретном примере неудачная инициализация всё же не помешала алгоритму найти правильный результат, но это скорее везение, связанное с тем, что датасет очень маленький и группы предельно чётко разделены. На больших и менее чётко разделённых датасетах (пример 3 ниже и раздел про k-means++) неудачная инициализация вполне может привести к тому, что алгоритм сойдётся и останется в заведомо худшем разбиении навсегда — именно поэтому чувствительность к инициализации является реальной, а не теоретической проблемой.

Пример 3 (k=3 на восьми точках — три плотные группы плюс более сложная динамика). Датасет: группа 1 — $(0,0), (0,1), (1,0)$; группа 2 — $(10,0), (10,1), (11,0)$; группа 3 — $(5,10), (5,11)$. Зададим $k=3$ с начальными центроидами $\mu_1=(0,0)$, $\mu_2=(10,0)$, $\mu_3=(5,10)$ — по одной точке из каждой «настоящей» группы.

Итерация 1, назначение. Для каждой из восьми точек ближайший центроид совпадает с центроидом «своей» группы почти без исключений: точки группы 1 ближе всего к $\mu_1$ (расстояния $0, 1, 1$ против гораздо больших расстояний до $\mu_2$ и $\mu_3$), точки группы 2 — к $\mu_2$, точки группы 3 — к $\mu_3$. Получаем разбиение ровно по трём «настоящим» группам.

Итерация 1, обновление. $\mu_1 = \left(\frac{0+0+1}{3},\frac{0+1+0}{3}\right)=(0{,}3333;\ 0{,}3333)$. $\mu_2 = \left(\frac{10+10+11}{3},\frac{0+1+0}{3}\right)=(10{,}3333;\ 0{,}3333)$. $\mu_3 = \left(\frac{5+5}{2},\frac{10+11}{2}\right)=(5;\ 10{,}5)$.

Итерация 2, назначение и проверка сходимости. Пересчёт расстояний от всех восьми точек до новых центроидов снова даёт то же самое разбиение на три группы — ни одна точка не «перетекает» в соседний кластер, поскольку группы расположены далеко друг от друга относительно своего внутреннего разброса. Алгоритм сходится за две итерации к разбиению, полностью совпадающему с визуально очевидными тремя группами, а центроиды стабилизируются на $(0{,}3333;\,0{,}3333)$, $(10{,}3333;\,0{,}3333)$ и $(5;\,10{,}5)$.

Почему это важно

Понимание того, что происходит внутри k-means на уровне отдельных шагов, — не просто академическое упражнение, а прямая подготовка к диагностике проблем на практике: когда KMeans(n_clusters=k).fit(X) из sklearn.cluster в реальном проекте выдаёт странное или нестабильное разбиение, первым делом стоит подумать именно о том, что происходит на шаге назначения (не перекрываются ли кластеры из-за немасштабированных признаков — расстояние в евклидовом пространстве чувствительно к масштабу каждой оси, поэтому перед k-means данные почти всегда стандартизируют) и на шаге обновления (не оказался ли какой-то кластер пустым или crайне маленьким). Именно этот пошаговый, механический характер алгоритма и объясняет две его следующие важнейшие особенности — то, что это в точности решение оптимизационной задачи, и то, что решение это не гарантированно наилучшее.

Оптимизационная интерпретация: минимизация WCSS и проблема невыпуклости

Интуиция

До сих пор алгоритм описывался как последовательность механических шагов: назначить, пересчитать, повторить. Но у этой последовательности шагов есть строгий математический смысл — можно доказать, что каждый шаг назначения и каждый шаг обновления либо уменьшает, либо оставляет без изменений одну конкретную величину, которая измеряет, насколько «плотно» и компактно расположены точки внутри своих кластеров. Иначе говоря, k-means — это не набор эвристик, а конкретный алгоритм решения конкретной оптимизационной задачи: минимизировать суммарную «размазанность» точек вокруг центров своих кластеров.

Формула

WCSS (within-cluster sum of squares, сумма квадратов расстояний внутри кластеров). Целевая функция, которую минимизирует k-means:

$$\text{WCSS} = \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

где $C_j$ — множество точек, отнесённых к кластеру $j$, а $\mu_j$ — центроид этого кластера. Шаг назначения (отнесение каждой точки к ближайшему центроиду) минимизирует WCSS при фиксированных центроидах; шаг обновления (пересчёт центроида как среднего точек кластера) минимизирует WCSS при фиксированном разбиении на кластеры, поскольку среднее арифметическое — это в точности точка, минимизирующая сумму квадратов расстояний до заданного набора точек. Поскольку оба шага никогда не увеличивают WCSS, а WCSS ограничена снизу нулём, алгоритм гарантированно сходится за конечное число итераций — но задача в целом невыпуклая: WCSS как функция от положения центроидов и разбиения имеет много локальных минимумов, и алгоритм гарантированно находит лишь один из них, не обязательно глобальный.

Разбор примеров

Пример 1 (расчёт WCSS для результата примера 1 предыдущего раздела). Для разбиения кластер 1 $=\{A(1,1),B(1,2),C(2,1)\}$ с центроидом $\mu_1=(1{,}3333;\,1{,}3333)$ и кластер 2 $=\{D(8,8),E(8,9),F(9,8)\}$ с центроидом $\mu_2=(8{,}3333;\,8{,}3333)$ посчитаем вклад каждой точки. Для кластера 1: $\|A-\mu_1\|^2 = (1-1{,}3333)^2+(1-1{,}3333)^2=0{,}1111+0{,}1111=0{,}2222$; $\|B-\mu_1\|^2=(1-1{,}3333)^2+(2-1{,}3333)^2=0{,}1111+0{,}4444=0{,}5556$; $\|C-\mu_1\|^2=(2-1{,}3333)^2+(1-1{,}3333)^2=0{,}4444+0{,}1111=0{,}5556$. Сумма по кластеру 1: $0{,}2222+0{,}5556+0{,}5556=1{,}3333$. По симметрии расположения точек кластер 2 даёт точно такую же сумму $1{,}3333$. Итого $\text{WCSS}=1{,}3333+1{,}3333=2{,}6667$.

Пример 2 (WCSS для заведомо худшего разбиения — сравнение значений). Возьмём тот же датасет из шести точек, но искусственно рассмотрим «неправильное» разбиение, которое k-means никогда бы не выдал при разумной инициализации: кластер 1 $=\{A,B,D\}$, кластер 2 $=\{C,E,F\}$ — то есть точки перемешаны между «настоящими» группами. Центроид кластера 1: $\mu_1=\left(\frac{1+1+8}{3},\frac{1+2+8}{3}\right)=(3{,}3333;\,3{,}6667)$. Вклады: $\|A-\mu_1\|^2=(1-3{,}3333)^2+(1-3{,}6667)^2=5{,}4444+7{,}1111=12{,}5556$; $\|B-\mu_1\|^2=(1-3{,}3333)^2+(2-3{,}6667)^2=5{,}4444+2{,}7778=8{,}2222$; $\|D-\mu_1\|^2=(8-3{,}3333)^2+(8-3{,}6667)^2=21{,}7778+18{,}7778=40{,}5556$. Сумма по кластеру 1 уже составляет $61{,}3333$ — почти в 23 раза больше, чем весь WCSS правильного разбиения из примера 1 ($2{,}6667$). Дальше считать вклад второго кластера уже не нужно: даже одного этого числа достаточно, чтобы показать, насколько сильно WCSS «штрафует» перемешанные, некомпактные кластеры и насколько предпочтительнее оказывается компактное, плотное разбиение.

Пример 3 (невыпуклость на конкретном числовом примере — два одинаково стабильных, но разных по WCSS решения). Возьмём одномерный датасет $x = (0, 1, 4, 5)$ и $k=2$. Разбиение A: $\{0,1\}$ и $\{4,5\}$ (естественная группировка по близости) с центроидами $0{,}5$ и $4{,}5$; WCSS $= (0-0{,}5)^2+(1-0{,}5)^2+(4-4{,}5)^2+(5-4{,}5)^2 = 0{,}25+0{,}25+0{,}25+0{,}25=1{,}0$. Разбиение B: $\{0,4\}$ и $\{1,5\}$ с центроидами $2{,}0$ и $3{,}0$; WCSS $=(0-2)^2+(4-2)^2+(1-3)^2+(5-3)^2=4+4+4+4=16{,}0$. Оба разбиения формально являются «устойчивыми точками» в том смысле, что можно подобрать инициализацию, при которой k-means сойдётся именно к одному из них (например, старт с центроидами ровно в $0$ и $4$ немедленно даёт разбиение B и больше не меняется, потому что при таких центроидах точка $1$ ближе к $0$, чем к $4$, а точка $5$ — ближе к $4$), но WCSS этих решений отличается в 16 раз. Это наглядно показывает невыпуклость задачи: алгоритм, стартовавший неудачно, может «застрять» в разбиении B и больше никогда его не покинуть, хотя разбиение A строго лучше по значению целевой функции.

Почему это важно

Оптимизационная интерпретация через WCSS — это не отвлечённая теория, а конкретный практический инструмент: именно значение WCSS (в sklearn оно доступно как атрибут .inertia_ после обучения KMeans) используется и для сравнения качества разных запусков алгоритма с разной инициализацией (запустить несколько раз, выбрать запуск с наименьшей WCSS — параметр n_init в sklearn.cluster.KMeans как раз это и делает автоматически), и для выбора самого числа кластеров k методом локтя, который будет разобран ниже. Одновременно понимание невыпуклости задачи объясняет, почему k-means — это не детерминированный алгоритм с одним «правильным» ответом, а алгоритм, чувствительный к случайности инициализации, и именно эта чувствительность привела к появлению более умной стратегии старта — k-means++.

Инициализация k-means++: умный старт вместо случайного

Интуиция

Проблему невыпуклости, разобранную выше, нельзя полностью устранить — задача остаётся невыпуклой при любой инициализации. Но можно резко снизить вероятность неудачного старта, если инициализировать центроиды не полностью случайно (как в классическом алгоритме Ллойда), а с оглядкой на уже выбранные центроиды: выбирать следующий центроид с повышенной вероятностью там, где точки находятся далеко от уже выбранных центров. Логика простая: если два начальных центроида случайно попадут рядом друг с другом внутри одной и той же «настоящей» группы точек (как это едва не произошло в примере 2 раздела про алгоритм), они с большей вероятностью «поделят» одну группу пополам вместо того, чтобы покрыть две разные группы, — а если изначально рассадить центроиды подальше друг от друга, шанс такого неудачного разбиения сразу падает.

Алгоритм

k-means++ (Артур и Васильвицкий, 2007).

1. Выбрать первый центроид $\mu_1$ случайно, равновероятно среди всех точек датасета.
2. Для каждой оставшейся точки $x_i$ вычислить расстояние $D(x_i)$ до ближайшего из уже выбранных центроидов.
3. Выбрать следующий центроид случайно среди всех точек, но с вероятностью, пропорциональной квадрату этого расстояния: $P(x_i) = \dfrac{D(x_i)^2}{\sum_j D(x_j)^2}$ — точки, далёкие от уже выбранных центров, получают больший шанс стать новым центром.
4. Повторять шаги 2–3, пока не будет выбрано $k$ центроидов.
5. Запустить обычный алгоритм Ллойда (назначение / обновление) с этими центроидами в качестве стартовых.

Разбор примеров

Пример 1 (пошаговый расчёт вероятностей k-means++ на пяти точках). Датасет: $P_1(0,0)$, $P_2(1,0)$, $P_3(10,0)$, $P_4(10,1)$, $P_5(20,0)$, нужно выбрать $k=2$. Пусть первый центроид случайно выпал на $P_1(0,0)$. Считаем квадраты расстояний от каждой оставшейся точки до $P_1$: $D(P_2)^2=(1-0)^2=1$; $D(P_3)^2=(10-0)^2=100$; $D(P_4)^2=10^2+1^2=101$; $D(P_5)^2=20^2=400$. Сумма квадратов расстояний (не считая уже выбранного $P_1$, у которого расстояние 0): $1+100+101+400=602$. Вероятности выбора: $P(P_2)=1/602\approx0{,}17\%$, $P(P_3)=100/602\approx16{,}6\%$, $P(P_4)=101/602\approx16{,}8\%$, $P(P_5)=400/602\approx66{,}4\%$. Точка $P_2$, находящаяся почти вплотную к уже выбранному $P_1$, получает ничтожный шанс стать вторым центроидом, а далёкая $P_5$ — наибольший шанс, что и требовалось: k-means++ явно поощряет разнесение центроидов по пространству.

Пример 2 (сравнение с равномерно случайным выбором на том же датасете). При классическом случайном выборе (равновероятно среди всех точек, без учёта расстояний) вероятность того, что вторым центроидом окажется именно точка $P_2$ — сосед первого центроида, из-за которого две разные группы точек рискуют оказаться в одном кластере, — составила бы просто $1/4=25\%$ (равномерно среди четырёх оставшихся точек). У k-means++ эта же вероятность падает до $0{,}17\%$ — почти в 150 раз меньше. Это количественно показывает, насколько сильно k-means++ снижает вероятность именно того сценария неудачной инициализации, который разбирался в примере 2 раздела про алгоритм k-means (два стартовых центроида внутри одной группы).

Пример 3 (k-means++ не устраняет невыпуклость полностью — вероятностная, а не абсолютная гарантия). Вернёмся к примеру 3 предыдущего раздела: одномерный датасет $x=(0,1,4,5)$, $k=2$. При k-means++ первый центроид выбирается равновероятно среди всех четырёх точек — скажем, случайно выпало $x=1$. Квадраты расстояний до оставшихся точек: $D(0)^2=1$, $D(4)^2=9$, $D(5)^2=16$, сумма $=26$. Вероятность того, что вторым центроидом станет $x=4$ (что в конечном счёте приводит к хорошему разбиению $\{0,1\}$ и $\{4,5\}$, WCSS$=1{,}0$ из предыдущего раздела): $9/26\approx34{,}6\%$. Вероятность того, что вторым центроидом окажется $x=5$, что тоже приводит к разбиению $\{0,1\}$ и $\{4,5\}$ (поскольку $1$ ближе к $0$, чем к $5$): $16/26\approx61{,}5\%$. Суммарно свыше $96\%$ вероятность хорошего разбиения при этом конкретном первом центроиде — заметно лучше, чем при равномерно случайном выборе, но не стопроцентная гарантия: k-means++ смягчает проблему невыпуклости статистически, снижая ожидаемое значение WCSS в среднем по множеству запусков, но не отменяет её математически. Именно поэтому даже с k-means++ в sklearn.cluster.KMeans параметр n_init по умолчанию запускает алгоритм несколько раз с разной инициализацией и выбирает лучший результат по WCSS.

Почему это важно

k-means++ — ровно та деталь, которая превращает k-means из «алгоритма, качество которого зависит от везения» в практически надёжный промышленный инструмент, и именно поэтому это настройка по умолчанию (init='k-means++') в sklearn.cluster.KMeans, а не опциональное улучшение, которое нужно включать вручную. Понимание того, что k-means++ снижает вероятность плохого старта, но не устраняет её полностью, объясняет и практику множественных перезапусков (n_init), и общее правило: на реальных данных k-means стоит запускать не один раз, а несколько, сравнивая финальную WCSS между запусками, а не доверять единственному прогону.

Выбор числа кластеров: метод локтя и коэффициент силуэта

Интуиция

Во всех примерах выше число кластеров $k$ было дано заранее, потому что структура игрушечных данных была визуально очевидна. На реальных данных с десятками признаков и тысячами точек число «естественных» групп заранее неизвестно совершенно, а алгоритм k-means сам по себе не умеет подсказать правильное $k$ — он с одинаковой готовностью разобьёт данные и на 2, и на 20 кластеров, если его об этом попросить. Нужен отдельный количественный критерий, который бы отвечал на вопрос «а какое k вообще имеет смысл использовать здесь?» — и таких критериев два основных: метод локтя, опирающийся на ту же самую WCSS, которую k-means и так минимизирует, и коэффициент силуэта, оценивающий качество разбиения более тонко, с учётом не только компактности кластеров, но и их отделённости друг от друга.

Метод

Метод локтя (elbow method). Запустить k-means для нескольких значений $k = 1, 2, 3, \dots$ и построить график зависимости WCSS от $k$. Поскольку увеличение числа кластеров почти всегда снижает WCSS (при $k=N$, числу точек, WCSS вообще равна нулю — каждая точка сама себе кластер), график монотонно убывает. Но убывание неравномерно: до «истинного» числа кластеров добавление каждого следующего $k$ резко снижает WCSS (алгоритм находит настоящую структуру данных), а после него — снижает WCSS лишь незначительно (алгоритм просто дробит уже цельные группы на более мелкие произвольные части). Точка на графике, где скорость убывания резко замедляется — «изгиб локтя», — считается разумной оценкой числа кластеров.

Коэффициент силуэта (silhouette score). Для каждой точки $x_i$: $a(x_i)$ — среднее расстояние до всех остальных точек её собственного кластера (мера компактности), $b(x_i)$ — среднее расстояние до точек ближайшего соседнего кластера (мера отделённости). Коэффициент силуэта для точки:

$$s(x_i) = \frac{b(x_i) - a(x_i)}{\max(a(x_i), b(x_i))}$$

Значение лежит в диапазоне $[-1, 1]$: близко к $1$ означает, что точка хорошо подходит своему кластеру и далека от соседних, около $0$ — точка находится на границе между кластерами, отрицательное значение — точка, вероятно, отнесена не в тот кластер. Средний коэффициент силуэта по всем точкам считается для каждого значения $k$, и выбирается $k$, максимизирующее это среднее значение.

Разбор примеров

Пример 1 (метод локтя — численный расчёт WCSS для нескольких k на восьми точках из примера 3 раздела про алгоритм). Датасет: группа 1 — $(0,0),(0,1),(1,0)$; группа 2 — $(10,0),(10,1),(11,0)$; группа 3 — $(5,10),(5,11)$. Для $k=1$ единственный центроид — среднее всех восьми точек: $\left(\frac{0+0+1+10+10+11+5+5}{8},\frac{0+1+0+0+1+0+10+11}{8}\right)=(5{,}25;\ 2{,}875)$; посчитав сумму квадратов расстояний до этого единственного центра, получаем $\text{WCSS}(k{=}1)\approx185{,}3$ (крупное значение — все три отдалённые друг от друга группы «слипаются» вокруг одного среднего центра). Для $k=3$, используя результат примера 3 раздела про алгоритм (три правильно найденных группы), WCSS складывается из внутригрупповых сумм: группа 1 с центроидом $(0{,}3333;0{,}3333)$ даёт WCSS-вклад $2{,}0$; группа 2 с центроидом $(10{,}3333;0{,}3333)$ — тоже $2{,}0$; группа 3 с центроидом $(5;10{,}5)$ — $\text{вклад}=(5-5)^2+(10-10{,}5)^2+(5-5)^2+(11-10{,}5)^2=0{,}25+0{,}25=0{,}5$. Итого $\text{WCSS}(k{=}3)=2{,}0+2{,}0+0{,}5=4{,}5$. Разница между $k{=}1$ и $k{=}3$ ($185{,}3$ против $4{,}5$) огромна, а для $k{=}4$ WCSS снизится ещё немного (одна из трёх групп разобьётся на две части), но уже несопоставимо слабее — именно такой резкий перегиб между $k{=}1$ (или $k{=}2$) и $k{=}3$, а затем почти плоская линия дальше, и называется «изгибом локтя», указывающим на разумное значение $k{=}3$.

Пример 2 (коэффициент силуэта для одной точки — конкретный расчёт). Возьмём разбиение из примера 1 предыдущего раздела (шесть точек, $k=2$): кластер 1 $=\{A(1,1),B(1,2),C(2,1)\}$, кластер 2 $=\{D(8,8),E(8,9),F(9,8)\}$. Посчитаем $s(A)$. Внутрикластерное расстояние $a(A)$ — среднее расстояние от $A$ до остальных точек своего кластера: $\|A-B\|=\sqrt{(1-1)^2+(1-2)^2}=1$, $\|A-C\|=\sqrt{(1-2)^2+(1-1)^2}=1$, значит $a(A)=(1+1)/2=1$. Межкластерное расстояние $b(A)$ — среднее расстояние от $A$ до всех точек соседнего кластера 2: $\|A-D\|=\sqrt{7^2+7^2}=\sqrt{98}\approx9{,}90$, $\|A-E\|=\sqrt{7^2+8^2}=\sqrt{113}\approx10{,}63$, $\|A-F\|=\sqrt{8^2+7^2}=\sqrt{113}\approx10{,}63$, среднее $b(A)\approx(9{,}90+10{,}63+10{,}63)/3\approx10{,}39$. Коэффициент силуэта: $s(A)=\dfrac{10{,}39-1}{\max(1,\,10{,}39)}=\dfrac{9{,}39}{10{,}39}\approx0{,}904$ — значение, очень близкое к $1$, что означает: точка $A$ прекрасно вписывается в свой кластер и находится далеко от чужого, ровно как и должно быть для чётко разделённых групп.

Пример 3 (силуэт демонстративно показывает плохое разбиение, где WCSS сама по себе может ввести в заблуждение). Продолжим пример из предыдущего пункта, но теперь возьмём заведомо плохое разбиение той же шестёрки точек с $k=2$: кластер 1 $=\{A,B,D\}$, кластер 2 $=\{C,E,F\}$ (перемешанные точки, уже встречавшиеся в примере 2 раздела про WCSS, где эта конфигурация давала WCSS $=61{,}33$ только для первого кластера — заведомо огромное значение). Посчитаем $s(A)$ для этого разбиения. Внутрикластерное $a(A)$: $\|A-B\|=1$, $\|A-D\|=\sqrt{98}\approx9{,}90$, среднее $a(A)\approx5{,}45$ — уже заметно выше, чем $a(A)=1$ в правильном разбиении, потому что $D$ из другой «настоящей» группы сильно «портит» компактность. Межкластерное $b(A)$ (расстояние до кластера $\{C,E,F\}$): $\|A-C\|=1$, $\|A-E\|\approx10{,}63$, $\|A-F\|\approx10{,}63$, среднее $b(A)\approx7{,}42$. Коэффициент силуэта: $s(A)=\dfrac{7{,}42-5{,}45}{\max(5{,}45,7{,}42)}=\dfrac{1{,}97}{7{,}42}\approx0{,}265$ — резко ниже, чем $0{,}904$ в правильном разбиении. Даже без единого взгляда на график, только по этому числу, коэффициент силуэта явно сигнализирует: точка $A$ в этом разбиении подходит своему кластеру гораздо хуже, чем могла бы, — и средний силуэт по всем точкам этого плохого разбиения окажется заметно ниже среднего силуэта правильного разбиения при том же $k=2$, что и позволяет использовать эту метрику для сравнения не только разных значений k, но и качества конкретных запусков.

Почему это важно

Метод локтя прост и вычислительно дёшев, но требует визуальной, отчасти субъективной оценки «где именно изгибается» график — на реальных зашумлённых данных изгиб часто выражен нечётко, и разные люди могут указать разное $k$, глядя на один и тот же график. Коэффициент силуэта даёт единственное число для каждого $k$, которое можно сравнивать формально, без визуальной интерпретации, и вдобавок учитывает не только компактность кластеров (что уже учитывает WCSS), но и то, насколько кластеры отделены друг от друга, — поэтому на практике силуэт часто считают более надёжным, хотя и более вычислительно затратным критерием (нужно посчитать попарные расстояния между всеми точками, а не только расстояния до центроидов). На практике оба метода нередко используют вместе, а sklearn.metrics.silhouette_score — стандартная функция для расчёта второго из них по готовому разбиению KMeans.

Ограничения k-means: выпуклые кластеры и что дальше

k-means предполагает, что кластеры имеют примерно выпуклую, компактную, «шарообразную» форму и примерно одинаковый размер и плотность — это прямое следствие того, что алгоритм минимизирует сумму квадратов расстояний до единственного центроида на кластер: центроид как «средняя точка» хорошо описывает компактное облако точек, но плохо описывает вытянутую, изогнутую или неправильную по форме группу. Если настоящие кластеры в данных представляют собой, например, два вложенных кольца или два вытянутых полумесяца, k-means с высокой вероятностью разрежет их пополам произвольным образом, совершенно не уловив реальную структуру, — притом что WCSS такого разбиения формально может быть даже ниже, чем у «правильного» с точки зрения человека разбиения, потому что задача k-means в принципе не умеет описывать невыпуклые формы. Метод также плохо работает, когда истинные кластеры сильно различаются по размеру или плотности: крупный разреженный кластер и маленький плотный кластер k-means нередко склонен либо неверно разделить, либо объединить, потому что каждая точка в алгоритме учитывается с одинаковым весом, а не с учётом локальной плотности вокруг неё. Эти ограничения — не недоработка конкретной реализации, а прямое математическое следствие самой формы оптимизируемой функции WCSS, и именно они подводят к следующему алгоритму курса: в уроке 322 будет разобран DBSCAN — метод кластеризации, основанный на плотности точек, а не на расстоянии до центроидов, который умеет находить кластеры произвольной формы и автоматически определяет число кластеров без необходимости задавать $k$ заранее.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Даны точки $A(2,2)$, $B(2,4)$, $C(8,8)$ и центроиды $\mu_1=(2,2)$, $\mu_2=(8,8)$. К какому центроиду будет отнесена точка $B$ на шаге назначения?

Задание 2: Кластер состоит из точек $(1,1)$, $(3,1)$, $(2,4)$. Найти новый центроид этого кластера на шаге обновления.

Задание 3: Верно ли, что алгоритм k-means гарантированно находит глобально оптимальное разбиение по WCSS? Обоснуй.

Задание 4: Кластер $\{(0,0),(2,0)\}$ с центроидом $(1,0)$. Найти вклад этого кластера в WCSS.

Задание 5 (машинное обучение): В sklearn.cluster.KMeans какой параметр отвечает за число запусков алгоритма с разной инициализацией, из которых выбирается лучший по WCSS?

Задание 6: При $k$-means++ первый центроид уже выбран. Точка $P$ находится на расстоянии $3$ от него, точка $Q$ — на расстоянии $6$. Во сколько раз вероятность выбрать $Q$ следующим центроидом выше вероятности выбрать $P$ (при прочих равных, среди только этих двух точек)?

Задание 7: Почему при $k=N$ (число кластеров равно числу точек) WCSS всегда равна нулю?

Задание 8 (машинное обучение): Клиенты интернет-магазина описаны признаками «сумма покупок в рублях» (от 0 до 500000) и «число визитов» (от 0 до 50). Перед применением k-means эти признаки не масштабировали. Что произойдёт и что нужно сделать?

Задание 9: График WCSS от $k$ показывает: $k{=}1{\to}400$, $k{=}2{\to}150$, $k{=}3{\to}90$, $k{=}4{\to}80$, $k{=}5{\to}72$. Где методом локтя разумнее всего выбрать $k$?

Задание 10: Коэффициент силуэта одной точки $s=-0{,}3$. Что это означает?

Средние задания (11–20)

Задание 11: Точки $(0,0), (0,2), (6,0), (6,2)$, начальные центроиды $\mu_1=(0,0)$, $\mu_2=(6,2)$. Выполнить шаг назначения.

Задание 12: Используя результат задания 11, выполнить шаг обновления центроидов.

Задание 13: Продолжая задания 11–12, выполнить ещё один шаг назначения с новыми центроидами $\mu_1=(0,1)$, $\mu_2=(6,1)$ и проверить, сошёлся ли алгоритм.

Задание 14: Посчитать WCSS для итогового разбиения из задания 13.

Задание 15 (машинное обучение): Объясни своими словами, почему шаг обновления центроида (среднее точек кластера) минимизирует WCSS при фиксированном разбиении.

Задание 16: Одномерные данные $x=(1,2,10,11)$, $k=2$. Инициализация k-means++: первый центроид выбран как $x=2$. Найти вероятность того, что следующим центроидом станет $x=11$.

Задание 17: По данным задания 16 найти вероятность того, что следующим центроидом станет $x=1$ (сосед уже выбранного $x=2$).

Задание 18 (машинное обучение): Датасет из 300 точек образует два вытянутых, изогнутых полумесяца (как две переплетённые дуги). Подойдёт ли k-means для их разделения? Почему?

Задание 19: Для трёх значений $k$ посчитан средний коэффициент силуэта: $k{=}2 \to 0{,}42$, $k{=}3 \to 0{,}61$, $k{=}4 \to 0{,}39$. Какое $k$ предпочтительнее по этому критерию?

Задание 20: Точка $x$ имеет $a(x)=2$ (среднее расстояние внутри своего кластера) и $b(x)=8$ (среднее расстояние до ближайшего соседнего кластера). Найти коэффициент силуэта $s(x)$.

Продвинутые задания (21–30)

Задание 21: Точки $(0,0),(1,0),(0,1),(9,9),(10,9),(9,10)$, начальные центроиды $\mu_1=(0,0)$, $\mu_2=(9,9)$. Выполнить полную первую итерацию (назначение и обновление) и проверить сходимость на второй итерации.

Задание 22 (машинное обучение): Посчитать WCSS для итогового разбиения из задания 21 (использовать вычисленные центроиды).

Задание 23: Два разных запуска k-means на одних и тех же данных с $k=3$ дали WCSS $=120$ и WCSS $=95$. Какой из запусков стоит выбрать в качестве итоговой модели и почему?

Задание 24: Одномерные данные $x=(0,1,2,10,11,12,20,21,22)$, WCSS посчитана для $k=1,2,3,4$: $\text{WCSS}(1)=234$, $\text{WCSS}(2)=68$, $\text{WCSS}(3)=6$, $\text{WCSS}(4)=4$. Определить методом локтя разумное число кластеров и объяснить выбор через относительное падение WCSS.

Задание 25 (машинное обучение): Интернет-магазин применяет k-means для сегментации клиентов, а затем использует номер полученного кластера как новый категориальный признак во входных данных для отдельной модели градиентного бустинга, предсказывающей отток клиентов. Как называется такое использование кластеризации и зачем оно нужно?

Задание 26: Кластер из пяти точек: $(1,1),(1,3),(3,1),(3,3),(20,20)$. Как последняя точка повлияет на положение центроида кластера и на WCSS по сравнению с кластером без неё?

Задание 27: Средний коэффициент силуэта для $k=2$ равен $0{,}55$, а для того же датасета WCSS при $k=2$ значительно выше, чем при $k=5$. Может ли метод локтя и коэффициент силуэта указывать на разные значения $k$ одновременно? Как это объяснить?

Задание 28: Датасет состоит из двух концентрических окружностей точек — внутреннего маленького круга и внешнего большого кольца точек вокруг него, с общим центром. Что вероятнее всего сделает k-means с $k=2$ на таких данных и почему это плохой результат?

Задание 29 (машинное обучение): В sklearn.cluster.KMeans после обучения модели атрибут .inertia_ показывает WCSS итогового разбиения, а атрибут .cluster_centers_ — координаты центроидов. Как эти два атрибута использовать вместе для реализации метода локтя на практике (опиши шаги)?

Задание 30: Объясни, почему коэффициент силуэта нельзя посчитать для $k=1$ (один-единственный кластер, включающий все точки).

Частые ошибки

• Забывают масштабировать признаки перед k-means. Евклидово расстояние, на котором строится весь алгоритм, чувствительно к масштабу каждой оси — признак с диапазоном в тысячи единиц полностью подавит признак с диапазоном в единицы. Перед KMeans почти всегда нужно применять StandardScaler или аналогичное масштабирование.

• Считают, что k-means сам «знает» правильное число кластеров. Алгоритм безропотно разобьёт данные на любое заданное $k$, даже совершенно неподходящее для реальной структуры данных, — число кластеров нужно выбирать отдельно, методом локтя, коэффициентом силуэта или с опорой на содержательное понимание задачи.

• Запускают k-means один раз и доверяют результату без проверки. Из-за невыпуклости задачи единственный запуск может застрять в неудачном локальном минимуме WCSS — стандартная практика (и настройка по умолчанию в sklearn через n_init) — несколько запусков с разной инициализацией и выбор лучшего по WCSS.

• Применяют k-means к данным с явно невыпуклыми или сильно различающимися по размеру кластерами. Метод математически предполагает компактные, примерно шарообразные и сопоставимые по размеру группы — на кольцевых, вытянутых или сильно разнородных по плотности структурах результат будет некорректным независимо от того, насколько аккуратно подобрано число кластеров.

• Путают WCSS и коэффициент силуэта как взаимозаменяемые метрики. WCSS почти монотонно убывает с ростом $k$ и годится только для метода локтя (поиска замедления убывания, а не минимума), тогда как силуэт — метрика с чётким оптимумом (максимумом), которую можно сравнивать напрямую между разными значениями $k$.

• Не проверяют устойчивость результата к выбросам. Поскольку центроид — это простое среднее точек кластера, один сильно удалённый выброс способен резко сместить центроид и исказить всё разбиение; выбросы стоит либо удалить заранее, либо использовать более устойчивые к ним методы кластеризации.

Главное запомнить

• K-means clustering (метод k-средних) — первая конкретная модель обучения без учителя в курсе: в отличие от всех моделей уроков 313–319, здесь нет разметки, и задача — найти структуру в данных, а не предсказать известный ответ.

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

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

• Задача минимизации WCSS невыпуклая: у неё много локальных минимумов, и k-means гарантированно сходится к одному из них, но не обязательно к глобально лучшему — результат зависит от случайной инициализации.

• k-means++ (Артур и Васильвицкий, 2007) — умная инициализация, выбирающая начальные центроиды с вероятностью, пропорциональной квадрату расстояния до уже выбранных центров, что резко снижает (но не устраняет полностью) риск неудачного старта.

• Число кластеров $k$ не определяется алгоритмом автоматически — его выбирают отдельно методом локтя (график WCSS от $k$, ищем точку замедления убывания) или коэффициентом силуэта (более формальная метрика с явным максимумом, учитывающая ещё и отделённость кластеров друг от друга).

• Коэффициент силуэта $s(x)=\dfrac{b(x)-a(x)}{\max(a(x),b(x))}$ лежит в диапазоне $[-1,1]$: значения около $1$ означают хорошее разбиение, около $0$ — границу между кластерами, отрицательные — вероятно неверное отнесение точки.

• k-means предполагает выпуклые, компактные кластеры примерно одинакового размера и плотности — на кольцевых, вытянутых или сильно разнородных по размеру структурах данных метод даёт некорректные результаты.

• sklearn.cluster.KMeans — стандартный промышленный инструмент: по умолчанию использует k-means++ и несколько запусков (n_init), а результат кластеризации часто используют не только как финальный ответ, но и как признак для последующих моделей обучения с учителем.

Связь с темами курса

Этот урок напрямую продолжает урок 303, где ты разбирал разделение машинного обучения на обучение с учителем и без учителя: k-means — первая конкретная реализация той самой ветки без учителя, о которой урок 303 говорил только в общих чертах. Всё, что было наработано в блоке уроков 313–319 (метрики расстояния, идея оптимизации через минимизацию функции, понятие переобучения из урока 304), переносится сюда в новом контексте: вместо минимизации ошибки предсказания относительно известного ответа k-means минимизирует WCSS — внутреннюю меру качества самого разбиения, без какого-либо внешнего критерия правильности.

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

Дальше курс продолжает блок кластеризации: в уроке 321 будет разобрана иерархическая кластеризация — альтернативный подход, не требующий заранее задавать число кластеров $k$ и строящий целое дерево вложенных разбиений сразу. А в уроке 322 — DBSCAN, метод кластеризации по плотности, который прямо отвечает на главное ограничение k-means, разобранное в конце этого урока: умение находить кластеры произвольной, невыпуклой формы без необходимости задавать число кластеров заранее.

Интересные факты

• Алгоритм, который сегодня почти всегда называют k-means, был впервые описан Стюартом Ллойдом ещё в 1957 году для совершенно другой задачи — квантования аналогового сигнала при цифровой передаче речи в Bell Labs, — а официально опубликован в открытой печати лишь в 1982 году, через двадцать пять лет.

• Название «k-means» независимо ввёл в 1967 году статистик Джеймс Маккуин, из-за чего в литературе исторически существует путаница между «алгоритмом Ллойда» и «k-means» — сегодня оба термина на практике обозначают практически один и тот же итеративный процесс.

• k-means++ не является отдельным алгоритмом кластеризации — это исключительно способ инициализации центроидов перед запуском обычного алгоритма Ллойда, но именно эта на первый взгляд небольшая деталь считается одним из самых влиятельных практических улучшений алгоритма за всю его историю и сегодня используется по умолчанию почти везде.

• Несмотря на возраст, превышающий шесть десятилетий, и известные ограничения на невыпуклых данных, k-means остаётся одним из самых часто применяемых алгоритмов кластеризации на практике — во многом благодаря вычислительной простоте: сложность одной итерации линейна по числу точек, признаков и кластеров, что позволяет применять его даже к очень большим датасетам.

Лайфхаки

• Перед запуском k-means всегда масштабируй признаки (StandardScaler или аналог) — без этого шага результат кластеризации почти всегда будет определяться одним-двумя признаками с наибольшим числовым диапазоном, а не реальной структурой данных.

• Не полагайся на единственный запуск метода локтя визуально — построй график WCSS для достаточно широкого диапазона $k$ (например, от 1 до 15) и, если изгиб выражен нечётко, дополни решение расчётом коэффициента силуэта для тех же значений $k$.

• Используй n_init со значением заметно больше единицы (в современных версиях sklearn это уже разумное значение по умолчанию) — единственный запуск k-means на реальных данных может случайно застрять в плохом локальном минимуме, и разница в WCSS между удачным и неудачным запуском бывает весьма существенной.

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

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

• Рассматривай k-means не только как финальный инструмент, но и как шаг предобработки: номер кластера, полученный от KMeans, часто оказывается полезным дополнительным признаком для последующей модели обучения с учителем — например, для градиентного бустинга (урок 318) при прогнозировании оттока клиентов.

Ты только что сделал первый шаг в мире, где у данных нет подсказок в виде готовых ответов, и это не менее ценный навык, чем всё, что ты изучал в предыдущих уроках блока обучения с учителем. Метод k-средних — простой по устройству, но глубокий по содержанию алгоритм: за четырьмя механическими шагами скрывается строгая оптимизационная задача, честная невыпуклость, которую нельзя обойти хитростью, а можно лишь смягчить умной инициализацией, и практические критерии выбора числа кластеров, которые превращают расплывчатый вопрос «сколько тут вообще групп» в конкретное, проверяемое число. Впереди — иерархическая кластеризация и DBSCAN, которые покажут, что даже у такой, казалось бы, простой задачи — «сгруппировать похожие объекты» — может быть несколько принципиально разных и по-своему правильных решений.