K-средних¶

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

¶История

Идея алгоритма, известного как k-средних, впервые была предложена Хьюго Штейнгаузом в 1950-х годах. В 1957 году Стюарт Ллойд опубликовал стандартную версию алгоритма для обработки сигналов, однако его работа долгое время оставалась малоизвестной. В 1965 году Э. Форги предложил независимую, но по сути идентичную реализацию. Современное название «k-средних» закрепилось после публикации Джеймса Маккуина в 1967 году. С тех пор алгоритм стал одним из базовых инструментов анализа данных, особенно в контексте роста вычислительных мощностей и объёмов данных.

¶Принцип работы

Алгоритм k-средних итеративно стремится минимизировать сумму квадратов расстояний от каждой точки до центра её кластера (центроида). Формально это задача минимизации внутрикластерной дисперсии.

¶Основные шаги

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

¶Метрика расстояния

По умолчанию в алгоритме используется евклидово расстояние. Однако могут применяться и другие метрики, например, манхэттенское расстояние (в этом случае центроид вычисляется как медиана, а не среднее).

¶Классификация и модификации

Алгоритм k-средних имеет множество модификаций, направленных на улучшение его работы и устранение недостатков.

¶По способу инициализации

• Стандартный (случайный) k-средних. Центроиды выбираются случайно. Может приводить к неоптимальному результату.
• K-means++ (предложен Дэвидом Артуром и Сергеем Васильвицким в 2007 году). Вероятностный метод выбора начальных центроидов, при котором новые центроиды выбираются с вероятностью, пропорциональной квадрату расстояния до ближайшего уже выбранного центроида. Это значительно повышает качество и скорость сходимости. Является стандартом де-факто.

¶По типу данных

• K-medoids (PAM). Вместо среднего значения (центроида) используется один из реальных объектов набора данных (медоид). Более устойчив к выбросам, но медленнее.
• K-modes. Для категориальных данных. Вместо среднего используется мода (наиболее часто встречающееся значение).
• Fuzzy C-means (нечёткая кластеризация). Каждая точка может принадлежать нескольким кластерам с разной степенью принадлежности (от 0 до 1).

¶По масштабируемости

• Mini-batch k-means. Использует не весь набор данных, а небольшие случайные подвыборки (мини-батчи) на каждой итерации. Значительно быстрее для больших массивов данных, но может давать несколько менее точный результат.

¶Характеристики и особенности

¶Преимущества

• Простота и скорость. Один из самых быстрых алгоритмов кластеризации, особенно при большом количестве данных.
• Масштабируемость. Хорошо работает с большими наборами данных (миллионы точек).
• Интерпретируемость. Результаты легко визуализировать и понять.
• Универсальность. Применим к данным любой природы, если они могут быть представлены в виде числовых векторов.

¶Недостатки

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

¶Применение

K-средних широко используется в различных областях науки и бизнеса.

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

¶Пример

Рассмотрим задачу сегментации клиентов интернет-магазина. Пусть есть данные о 1000 клиентах: их средний чек (в рублях) и частота покупок (в месяц). Применив алгоритм k-средних с \( k=3 \), можно получить следующие кластеры:

• Кластер 1 (Экономные): низкий средний чек, низкая частота.
• Кластер 2 (Активные): средний чек, высокая частота.
• Кластер 3 (VIP): высокий средний чек, низкая частота.

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

• Алгоритм k-средних является частным случаем алгоритма максимизации ожидания (EM-алгоритма) для смеси гауссовых распределений с равными ковариационными матрицами.
• В 2006 году за разработку алгоритма k-means++ Дэвид Артур и Сергей Васильвицкий получили премию за лучшую работу на конференции ACM-SIAM Symposium on Discrete Algorithms.
• Существует теорема, утверждающая, что в худшем случае время работы стандартного k-средних может быть экспоненциальным, хотя на практике оно почти всегда линейно.

¶Источники

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