Алгоритм k-средних

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

История

Метод k-средних был впервые предложен в 1956 году Стюартом Ллойдом в рамках работы над квантованием сигналов в лаборатории Bell Labs, однако его статья была опубликована только в 1982 году. В 1965 году польский математик Ежи Мацкун (Jerzy MacQueen) независимо разработал и формализовал алгоритм, введя термин «k-средние» и описав итеративную процедуру. В 1967 году Джеймс Маккуин (James MacQueen) опубликовал работу, закрепившую название метода. С тех пор алгоритм многократно модифицировался и оптимизировался, став базовым инструментом в задачах кластеризации.

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

Алгоритм k-средних работает итеративно, последовательно уточняя положение центров кластеров. Входными данными являются набор из n объектов (каждый описывается d признаками) и число кластеров k. Основная цель — минимизировать целевую функцию:

\[ J = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2 \]

где \(C_i\) — множество точек, принадлежащих кластеру \(i\), а \(\mu_i\) — центроид этого кластера.

Базовый алгоритм (алгоритм Ллойда)

1. Инициализация. Выбираются k начальных центров кластеров (центроидов). Это могут быть случайные точки из набора данных или случайные значения в пространстве признаков.
2. Шаг присваивания. Каждый объект относится к тому кластеру, центроид которого находится к нему ближе всего (обычно по евклидову расстоянию).
3. Шаг обновления. Для каждого кластера вычисляется новый центроид как среднее арифметическое всех точек, входящих в этот кластер.
4. Проверка сходимости. Если центроиды не изменились (или изменение меньше заданного порога), алгоритм завершает работу. Иначе повторяются шаги 2 и 3.

Инициализация центроидов

Качество работы алгоритма сильно зависит от начального выбора центроидов. Наиболее распространённые методы:

• Случайная инициализация. Выбор k случайных точек из набора данных. Прост, но может приводить к неоптимальным решениям.
• Метод k-means++ (Arthur, Vassilvitskii, 2007). Вероятностный метод, при котором первый центроид выбирается случайно, а каждый последующий — с вероятностью, пропорциональной квадрату расстояния до ближайшего уже выбранного центроида. Обеспечивает лучшее начальное разбиение и ускоряет сходимость.
• Инициализация на основе Forgy. Выбор k случайных точек из данных (без возврата). Распространён в пакетах статистического анализа.

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

Одна из ключевых проблем алгоритма — необходимость заранее задавать число кластеров k. Для его определения используются эвристические методы:

• Метод локтя (elbow method). Строится график зависимости суммы квадратов расстояний (инерции) от числа кластеров. Точка перегиба (излома) графика указывает на оптимальное k.
• Коэффициент силуэта (silhouette score). Оценивает компактность и разделимость кластеров. Значения от -1 до 1; чем ближе к 1, тем лучше разбиение.
• Индекс Калински-Харабаса. Отношение межкластерной дисперсии к внутрикластерной. Максимум индекса соответствует оптимальному k.
• Статистика Гапа (gap statistic). Сравнивает инерцию реальных данных с инерцией случайных данных (равномерное распределение). Оптимальное k — где разрыв максимален.

Свойства и ограничения

Достоинства

• Простота и скорость. Алгоритм легко реализовать, он работает за время \(O(n \cdot k \cdot d \cdot t)\), где t — число итераций (обычно небольшое).
• Масштабируемость. Хорошо подходит для больших наборов данных (миллионы точек) при использовании оптимизированных реализаций.
• Интерпретируемость. Результаты легко визуализировать и объяснить.

Недостатки

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

Модификации и варианты

• K-medoids (PAM). Вместо среднего используется медиана (фактическая точка данных), что делает метод устойчивее к выбросам.
• Fuzzy c-means. Нечёткая версия, где каждая точка принадлежит всем кластерам с разной степенью (от 0 до 1).
• Mini-batch k-means. Использует случайные подвыборки данных на каждой итерации, что ускоряет сходимость на очень больших наборах.
• X-means. Автоматически определяет число кластеров, разбивая кластеры на два, если это улучшает критерий (например, информационный критерий Акаике).
• K-means с ограничениями. Позволяет задавать обязательные связи (must-link, cannot-link) между точками.

Применение

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

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

Пример работы

Рассмотрим простой пример: набор точек на плоскости (признаки — координаты x и y). Пусть k = 2. После инициализации двух случайных центроидов алгоритм последовательно перераспределяет точки между двумя кластерами, пока центроиды не стабилизируются. В результате точки сгруппируются в два компактных облака, каждое со своим центром.

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

• Алгоритм k-средних является частным случаем метода максимизации ожидания (EM) для смеси гауссовых распределений, когда ковариации всех компонент полагаются единичными.
• В 2006 году Дэвид Артур и Сергей Васильвицкий доказали, что в худшем случае время работы стандартного алгоритма может быть экспоненциальным, но на практике он сходится за десятки итераций.
• Существует теорема о том, что задача минимизации суммы квадратов расстояний для k кластеров является NP-трудной в общем случае (при k > 1 и размерности > 1), поэтому все практические алгоритмы являются эвристиками.

Критика

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

Источники

• Lloyd, S. P. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory, 28(2), 129–137.
• MacQueen, J. (1967). "Some methods for classification and analysis of multivariate observations". Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
• Arthur, D., & Vassilvitskii, S. (2007). "k-means++: The advantages of careful seeding". Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 1027–1035.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.
• James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An Introduction to Statistical Learning: with Applications in R. Springer.