K-средние

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

История

Алгоритм k-средних был независимо предложен несколькими исследователями в середине XX века. Впервые идея, близкая к современной версии, была описана Хуго Штейнгаузом в 1956 году в контексте задачи оптимального квантования сигнала. В 1957 году Стюарт Ллойд (Bell Labs) разработал алгоритм для импульсно-кодовой модуляции, который фактически является стандартной реализацией k-средних, но его работа долгое время оставалась внутренним отчётом и была опубликована лишь в 1982 году. В 1965 году Э. В. Форги опубликовал метод, который также известен как алгоритм k-средних. Термин «k-средние» (k-means) впервые был использован Джеймсом МакКуином в 1967 году. С тех пор алгоритм стал одним из базовых инструментов в статистике, интеллектуальном анализе данных и машинном обучении.

Описание алгоритма

Исходные данные и цель

На вход алгоритма подаётся набор из \( n \) объектов (точек) в многомерном пространстве признаков и целое число \( k \) — количество кластеров, которое необходимо выделить. Цель — найти такое разбиение множества объектов на \( k \) непересекающихся подмножеств (кластеров) \( S = \{S_1, S_2, \dots, S_k\} \), чтобы минимизировать целевую функцию — сумму квадратов расстояний от каждого объекта до центроида его кластера:

\[ \arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} \| x - \mu_i \|^2 \]

где \( \mu_i \) — центроид (среднее арифметическое) всех точек, принадлежащих кластеру \( S_i \), а \( \| x - \mu_i \| \) — евклидово расстояние (хотя могут использоваться и другие метрики).

Этапы работы (алгоритм Ллойда)

Стандартная реализация алгоритма (алгоритм Ллойда) является итеративной и состоит из следующих шагов:

1. Инициализация центроидов. Выбираются \( k \) начальных центроидов. Это может делаться случайно (выбор \( k \) точек из исходного набора данных) или с помощью более сложных методов, например, k-means++ (см. раздел «Модификации»).
2. Назначение точек к кластерам. Для каждого объекта вычисляется расстояние до каждого из \( k \) центроидов. Объект относится к тому кластеру, центроид которого оказался ближайшим.
3. Пересчёт центроидов. Для каждого из \( k \) кластеров вычисляется новый центроид как среднее арифметическое всех точек, входящих в этот кластер.
4. Проверка сходимости. Если центроиды изменились (или изменилось разбиение на кластеры) относительно предыдущей итерации, алгоритм возвращается к шагу 2. В противном случае алгоритм завершается.

Сходимость и ограничения

Алгоритм гарантированно сходится за конечное число итераций, так как на каждом шаге целевая функция уменьшается. Однако он находит локальный минимум, а не глобальный. Результат сильно зависит от начальной инициализации центроидов. Разные запуски алгоритма на одних и тех же данных могут приводить к разным результатам. Кроме того, алгоритм чувствителен к выбросам и предполагает, что кластеры имеют сферическую форму и примерно одинаковый размер, что на практике бывает не всегда.

Выбор числа кластеров

Одной из ключевых проблем при использовании k-средних является выбор подходящего числа кластеров \( k \). Существует несколько эвристических методов, помогающих определить оптимальное значение:

• Метод локтя (Elbow method). Строится график зависимости суммы квадратов расстояний (инерции) от числа кластеров \( k \). Точка, после которой уменьшение инерции замедляется (образуется «изгиб» графика), считается оптимальным значением \( k \).
• Коэффициент силуэта (Silhouette coefficient). Измеряет, насколько хорошо объекты сгруппированы внутри своих кластеров по сравнению с соседними кластерами. Значение коэффициента варьируется от -1 до 1. Выбирается \( k \), при котором средний коэффициент силуэта максимален.
• Индекс Калински — Харабаса (Calinski-Harabasz index). Оценивает компактность и разделимость кластеров. Чем выше значение индекса, тем лучше разбиение.
• Индекс Дэвиса — Боулдина (Davies-Bouldin index). Вычисляет среднее «сходство» между каждым кластером и его наиболее похожим кластером. Чем меньше значение, тем лучше разбиение.

Модификации и улучшения

k-means++

Метод инициализации центроидов, предложенный Дэвидом Артуром и Сергеем Васильвицким в 2007 году. Первый центроид выбирается случайно из точек данных. Каждый последующий центроид выбирается из оставшихся точек с вероятностью, пропорциональной квадрату расстояния до ближайшего уже выбранного центроида. Это значительно улучшает качество и скорость сходимости алгоритма по сравнению со случайной инициализацией.

Mini-batch k-means

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

K-medoids (PAM)

Альтернатива k-средних, где центроидом кластера является не среднее арифметическое, а один из реальных объектов (медоид), наиболее центральный в кластере. Это делает алгоритм более устойчивым к выбросам, но и более вычислительно затратным.

Kernel k-means

Модификация, позволяющая выделять кластеры нелинейной формы. Данные с помощью ядровой функции (kernel trick) отображаются в пространство более высокой размерности, где кластеры становятся линейно разделимыми, после чего применяется стандартный алгоритм k-средних.

Применение

Благодаря своей простоте, скорости и масштабируемости, k-средние широко применяется в различных областях:

• Сегментация клиентов. Разделение покупателей на группы по поведению, демографическим признакам или покупательской способности для таргетированного маркетинга.
• Сжатие изображений. Каждый пиксель изображения представляется как точка в цветовом пространстве (например, RGB). Кластеризация пикселей в \( k \) цветов и замена каждого пикселя на цвет его центроида позволяет уменьшить количество используемых цветов и степень сжатия.
• Обработка естественного языка. Группировка документов по темам (тематическое моделирование) или кластеризация слов для построения векторных представлений.
• Биоинформатика. Кластеризация генов или белков по уровню экспрессии, выявление групп организмов со схожими генетическими характеристиками.
• Анализ социальных сетей. Выявление сообществ пользователей со схожими интересами или поведением.
• Обнаружение аномалий. Точки, которые находятся далеко от центроидов своих кластеров или образуют очень маленькие кластеры, могут считаться аномалиями.

Критика и ограничения

• Необходимость задания \( k \). В реальных задачах число кластеров часто неизвестно заранее, а эвристические методы не всегда дают однозначный ответ.
• Чувствительность к начальной инициализации. Результат может быть невоспроизводим и неоптимален.
• Предположение о сферической форме кластеров. Алгоритм плохо работает с кластерами сложной формы (вытянутыми, вложенными, соединёнными перешейками).
• Чувствительность к выбросам. Выбросы могут существенно смещать центроиды и искажать результаты кластеризации.
• Чувствительность к масштабу признаков. Если признаки имеют разные единицы измерения, необходимо проводить нормализацию или стандартизацию данных, иначе признаки с большими значениями будут доминировать при расчёте расстояний.
• Работа только с числовыми данными. Алгоритм не предназначен для работы с категориальными признаками напрямую (требуется предварительное кодирование).

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

• Алгоритм k-средних является частным случаем алгоритма максимизации ожидания (EM-алгоритма) для смеси гауссовых распределений с фиксированной и одинаковой ковариационной матрицей.
• В 2006 году алгоритм k-средних был признан одним из десяти наиболее влиятельных алгоритмов в области интеллектуального анализа данных (по версии IEEE International Conference on Data Mining).
• Несмотря на свою простоту, k-средних остаётся одним из самых используемых алгоритмов кластеризации в промышленности, особенно в задачах, где важна скорость обработки больших объёмов данных.

Источники

• MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability.
• Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory.
• Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction.
• Bishop, C. M. (2006). Pattern Recognition and Machine Learning.