K-Means кластеризация

У Spotify 600 миллионов пользователей. Ни один человек не группировал их вручную - алгоритм кластеризации сам нашёл сегменты: фанаты рока, любители подкастов, меломаны-эклектики. Uber не знает заранее, где в городе «горячие зоны» - K-Means каждый час пересчитывает кластеры заказов, чтобы перераспределить водителей. Но как алгоритм, не понимающий музыку и не видящий карту, находит эти группы? И почему иногда он ошибается так, что объединяет фанатов классики с рэперами?

• **Uber/Lyft** кластеризуют заказы такси в реальном времени: K-Means определяет «горячие зоны» города каждые 5 минут, перенаправляя водителей туда, где спрос максимален - это сокращает время ожидания на 20-30%
• **Ритейл и маркетинг:** Amazon сегментирует 300+ млн клиентов по покупательскому поведению - частота, средний чек, категории товаров. Каждый сегмент получает персонализированные предложения, увеличивая конверсию на 15-25%
• **Медицинская визуализация:** K-Means применяется для сегментации МРТ-снимков мозга - выделение серого вещества, белого вещества и спинномозговой жидкости в автоматическом режиме, ускоряя диагностику в 10 раз

Алгоритм, родившийся внутри телефонной компании

У K-Means необычное происхождение: он вырос из телефонной инженерии, а не из статистики. В 1957 году Стюарт Ллойд в Bell Labs придумал итеративную процедуру, изучая импульсно-кодовую модуляцию и подбирая лучший способ квантовать сигнал на фиксированное число уровней. Его отчёт ходил внутри компании, но формально был опубликован лишь в 1982 году. Тем временем ту же идею переоткрывали не раз: Эдвард Форги описал эквивалентный метод в 1965 году, а в 1967 году Джеймс Маккуин дал алгоритму его закрепившееся название, введя термин «k-means» в работе о классификации многомерных наблюдений. Три независимые линии сошлись на одном и том же простом цикле «назначить и пересчитать» - поэтому метод иногда называют алгоритмом Ллойда-Форги. Спустя десятилетия этот трюк квантования из телефонной лаборатории кластеризует всё подряд, от клиентов до МРТ-снимков.

Предварительные знания

• ML Types: supervised, unsupervised, reinforcement

Алгоритм K-Means: центроиды и итерации

Представьте, что вы - владелец сети пиццерий и хотите открыть 3 новых точки доставки. У вас есть адреса всех заказов за год. Задача: расположить пиццерии так, чтобы **среднее расстояние доставки было минимальным**. Именно это и делает K-Means - находит K центров (центроидов), минимизируя расстояние от каждой точки данных до ближайшего центра.

K-Means работает итеративно, чередуя два шага. **Шаг 1 (Assign):** каждую точку данных относим к ближайшему центроиду. **Шаг 2 (Update):** пересчитываем каждый центроид как среднее арифметическое всех точек, назначенных в его кластер. Эти два шага повторяются, пока центроиды не перестанут двигаться - алгоритм **сошёлся**.

Как измерить «близость»? По умолчанию K-Means использует **евклидово расстояние** - обычное расстояние между точками в пространстве. Для двух точек (x1, y1) и (x2, y2) это sqrt((x1-x2)^2 + (y1-y2)^2). В многомерном пространстве формула та же, только слагаемых больше.

**Inertia (WCSS - Within-Cluster Sum of Squares)** - главная метрика K-Means. Inertia = сумма квадратов расстояний от каждой точки до центроида её кластера. - **Inertia = 0** - все точки совпадают с центроидами (идеал, но нереалистично) - **Inertia велика** - точки далеко от центроидов, кластеризация плохая - **K-Means минимизирует inertia** на каждой итерации Важно: inertia всегда уменьшается при увеличении K. При K = N (каждая точка - свой кластер) inertia = 0, но такая кластеризация бессмысленна.

**K-Means гарантированно сходится**, но к **локальному** оптимуму, не к глобальному. Разные начальные центроиды могут привести к разным результатам. Поэтому sklearn запускает алгоритм **n_init=10 раз** с разными начальными точками и выбирает результат с наименьшей inertia.

Метод локтя: выбор K

K-Means требует, чтобы вы **заранее указали K** - количество кластеров. Но как узнать правильное K, если вы ещё не видели кластеры? Это фундаментальная проблема: алгоритм не скажет вам, на сколько групп делить данные. **Метод локтя (Elbow Method)** - самый популярный эвристический подход к выбору K.

Идея проста: запустите K-Means для K = 1, 2, 3, ..., 10 и запишите inertia для каждого K. Постройте график inertia(K). При маленьком K inertia огромна (все точки в одном кластере). При увеличении K inertia падает. В какой-то момент падение **резко замедляется** - это и есть «локоть». Оптимальное K - это точка перегиба, после которой добавление новых кластеров почти не улучшает результат.

**Проблема метода локтя:** «локоть» не всегда виден. Если кластеры нечёткие, размытые или перекрываются, график может быть плавной кривой без выраженного излома. В таких случаях метод локтя - не надёжный инструмент, и нужны другие подходы.

**Альтернативы методу локтя:** - **Silhouette Score** - оценка качества кластеризации (разберём в следующем концепте) - **Gap Statistic** (Tibshirani, 2001) - сравнивает inertia с равномерным распределением: если данные не кластеризуются, Gap ~ 0 - **Calinski-Harabasz Index** - отношение between-cluster variance к within-cluster variance; чем больше, тем лучше - **BIC/AIC** - информационные критерии для Gaussian Mixture Models На практике чаще всего комбинируют метод локтя с Silhouette Score.

Важно понимать: выбор K - это не только математика. Если вы сегментируете клиентов для маркетинга, бизнесу может быть нужно ровно 3 сегмента (VIP, обычные, редкие покупатели), даже если данные говорят о 5 кластерах. **Доменное знание** часто важнее формальных метрик.

Silhouette Score: оценка качества

Метод локтя смотрит только на inertia - насколько плотны кластеры внутри себя. Но хорошая кластеризация - это не только плотность: кластеры должны быть ещё и **хорошо разделены**. **Silhouette Score** учитывает оба фактора: насколько точка близка к своему кластеру и насколько далека от соседнего.

Для каждой точки i вычисляются два числа. **a(i)** - среднее расстояние от точки i до всех остальных точек **в её кластере** (чем меньше - тем плотнее кластер). **b(i)** - среднее расстояние от точки i до всех точек **ближайшего чужого кластера** (чем больше - тем лучше разделение). Silhouette score для точки: **s(i) = (b(i) - a(i)) / max(a(i), b(i))**.

**Silhouette Plot** - удобный инструмент диагностики. Он показывает silhouette score для **каждой точки**, сгруппированной по кластерам: - Широкие «полосы» одинаковой ширины - кластеры сбалансированы - Узкая полоса - мало точек в кластере (возможно, лишний кластер) - Точки с отрицательным s(i) - ошибочно назначенные, стоит проверить В sklearn: `silhouette_samples(X, labels)` возвращает s(i) для каждой точки, а `silhouette_score(X, labels)` - среднее по всем точкам.

На практике Silhouette Score и метод локтя используют **вместе**. Метод локтя дает «кандидатов» (например, K=3 или K=4), а Silhouette Score помогает выбрать из них. Если оба метода указывают на одно K - это сильный сигнал. Если расходятся - стоит визуализировать данные и использовать доменное знание.

**Ограничение Silhouette Score:** он использует евклидово расстояние и хорошо работает для **выпуклых, сферических** кластеров. Для кластеров сложной формы (полумесяцы, кольца, вытянутые эллипсы) Silhouette Score может давать некорректную оценку - высокий балл при неправильной кластеризации.

K-Means++ и ограничения

Помните предупреждение о том, что K-Means сходится к **локальному** оптимуму? Главная причина - случайная инициализация центроидов. Если начальные центроиды выбраны неудачно (например, все три оказались в одном углу данных), алгоритм может «застрять» в плохом решении. **K-Means++** (Arthur & Vassilvitskii, 2007) решает эту проблему умной инициализацией.

Алгоритм K-Means++: **(1)** Выбрать первый центроид случайно из точек данных. **(2)** Для каждой точки x вычислить D(x) - расстояние до ближайшего уже выбранного центроида. **(3)** Выбрать следующий центроид с вероятностью, пропорциональной D(x)^2 - чем дальше точка от существующих центроидов, тем выше шанс стать новым центроидом. **(4)** Повторять шаги 2-3, пока не выбраны все K центроидов.

**Когда K-Means НЕ работает - ограничения алгоритма:** 1. **Только сферические кластеры** - K-Means предполагает, что кластеры имеют примерно одинаковую дисперсию во всех направлениях. Вытянутые, кольцевые или произвольные формы он не распознает 2. **Чувствителен к выбросам** - один выброс может сдвинуть центроид целого кластера, искажая всю кластеризацию 3. **Одинаковый размер кластеров** - алгоритм стремится создать кластеры примерно равного размера, даже если реальные группы различаются в 10 раз 4. **Нужно знать K заранее** - в отличие от DBSCAN, K-Means не определяет число кластеров автоматически 5. **Масштаб признаков** - евклидово расстояние зависит от масштаба; обязательно нормализуйте данные (StandardScaler) перед K-Means

**Mini-Batch K-Means** - вариант для больших данных (миллионы точек). Вместо использования всего датасета на каждой итерации, он берёт случайный mini-batch (например, 1000 точек) и обновляет центроиды по нему. Результат чуть менее точен, но скорость на порядки выше. В sklearn: `MiniBatchKMeans(n_clusters=5, batch_size=1000)`.

Ключевые идеи

• **K-Means** итеративно чередует два шага: Assign (каждую точку - к ближайшему центроиду) и Update (центроид = среднее точек кластера), пока не сойдётся
• **Метод локтя** запускает K-Means для K=1..10 и ищет точку на графике inertia(K), где падение резко замедляется - это оптимальное K
• **Silhouette Score** s(i) = (b-a)/max(a,b) оценивает качество кластеризации, учитывая и плотность кластера (a), и отделённость от соседей (b)
• **K-Means++** решает проблему инициализации, выбирая начальные центроиды максимально разнесёнными по пространству данных (по умолчанию в sklearn)
• K-Means не универсален: только сферические кластеры, чувствителен к выбросам и масштабу - поэтому Uber каждый час пересчитывает зоны, а для несферических данных используют DBSCAN и другие алгоритмы

Связанные темы

K-Means - отправная точка в мире кластеризации. Его ограничения породили целое семейство более гибких алгоритмов:

• Типы машинного обучения — K-Means - классический алгоритм unsupervised learning, одной из трёх парадигм ML, где модель работает с неразмеченными данными
• Иерархическая кластеризация — В отличие от K-Means, не требует указания K заранее - строит дендрограмму, позволяя выбрать число кластеров на любом уровне
• DBSCAN — Находит кластеры произвольной формы и автоматически определяет выбросы - решает главные ограничения K-Means
• Предобработка данных — StandardScaler критически важен перед K-Means - без нормализации признаки с большим масштабом доминируют в евклидовом расстоянии

Вопросы для размышления

• Если бы вы кластеризовали посетителей интернет-магазина по поведению (время на сайте, число кликов, сумма покупок), какие проблемы могут возникнуть с K-Means без предобработки данных?
• K-Means всегда назначает каждую точку в какой-то кластер. В каких реальных задачах это свойство может быть вредным, и какой алгоритм решает эту проблему?
• Компания хочет сегментировать клиентов для маркетинга. Метод локтя показывает K=5, но маркетологи говорят, что им нужно ровно 3 сегмента. Как поступить и кто прав?

Связанные уроки

• ml-02-types — K-Means - классика unsupervised learning
• ml-17-hierarchical-clustering — Иерархическая кластеризация - альтернатива K-Means
• ml-18-dbscan — DBSCAN решает слабости K-Means для произвольных форм
• ml-09-gradient-descent — EM-алгоритм для GMM аналогичен gradient descent
• prob-06-random-vars — Понимание распределений нужно для Gaussian Mixture Models
• ir-07 — Vector clustering в поиске - K-Means для embedding space
• alg-12-bfs