Метод k-средних

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

История

Метод k-средних был независимо предложен несколькими исследователями в разных областях. Впервые математическая формулировка задачи кластеризации методом наименьших квадратов была опубликована Гуго Штейнгаузом в 1956 году. Однако наиболее известная версия алгоритма, получившая широкое распространение, была разработана Джеймсом Маккуином в 1967 году. В 1957 году Стюарт Ллойд предложил аналогичный алгоритм для обработки сигналов (импульсно-кодовой модуляции), который позже, в 1982 году, был опубликован и стал известен как «алгоритм Ллойда». В 1965 году Е. В. Форги опубликовал независимое описание того же метода. Таким образом, метод k-средних имеет несколько «отцов-основателей», и его современная реализация обычно объединяет идеи этих авторов.

Основные понятия и формальная постановка

Кластеры и центроиды

Пусть дано множество из n объектов, каждый из которых описывается d числовыми признаками (координатами в d-мерном пространстве). Задача кластеризации заключается в разбиении этого множества на k непересекающихся подмножеств (кластеров) C₁, C₂, ..., Cₖ. Каждый кластер характеризуется своим центром — центроидом (англ. centroid), который обычно определяется как среднее арифметическое всех точек, входящих в данный кластер. Для кластера Cⱼ центроид μⱼ вычисляется по формуле:

μⱼ = (1/|Cⱼ|) * Σ(x ∈ Cⱼ) x,

где |Cⱼ| — количество точек в кластере.

Функция стоимости (целевая функция)

Алгоритм k-средних стремится минимизировать целевую функцию, называемую инерцией или суммой квадратов внутрикластерных расстояний (WCSS — Within-Cluster Sum of Squares):

J = Σⱼ Σ(x ∈ Cⱼ) ||x — μⱼ||²,

где ||·|| обозначает евклидово расстояние. Чем меньше значение J, тем более компактными и однородными являются кластеры. Минимизация этой функции является NP-трудной задачей в общем случае, поэтому алгоритм находит лишь локальный оптимум.

Алгоритм работы

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

1. Инициализация. Выбираются k начальных центроидов. Способ инициализации существенно влияет на конечный результат. Наиболее распространённые методы:

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

1. Присвоение (Assignment). Каждый объект (точка) относится к ближайшему центроиду на основе выбранной метрики расстояния (обычно евклидовой). Формально: для каждой точки x определяется кластер j, для которого расстояние ||x — μⱼ|| минимально.

1. Обновление (Update). Вычисляются новые центроиды как средние арифметические точек, отнесённых к каждому кластеру на предыдущем шаге.

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

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

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

• Метод локтя (Elbow method). Строится график зависимости инерции (WCSS) от k. Оптимальное значение k выбирается в точке, где дальнейшее увеличение числа кластеров перестаёт давать существенное уменьшение инерции (график образует «изгиб»).
• Коэффициент силуэта (Silhouette score). Оценивает, насколько хорошо объект кластеризован: учитывает как компактность внутри кластера, так и отделимость от соседних кластеров. Значения коэффициента находятся в диапазоне от -1 до 1; чем ближе к 1, тем лучше.
• Индекс Калински — Харабаса (Calinski-Harabasz index). Основан на отношении межкластерной дисперсии к внутрикластерной дисперсии.
• Статистика разрыва (Gap statistic). Сравнивает инерцию реальных данных с инерцией, полученной на случайных данных (нулевая модель).

Разновидности и модификации

• k-medoids (PAM — Partitioning Around Medoids). Вместо среднего арифметического используется реальный объект из набора данных (медоид), что делает метод более устойчивым к шумам и выбросам.
• Fuzzy c-means (нечёткая кластеризация). Каждая точка может принадлежать нескольким кластерам с разной степенью принадлежности (от 0 до 1).
• Mini-batch k-means. Использует случайные подвыборки (мини-батчи) данных на каждой итерации, что значительно ускоряет работу на больших массивах данных.
• K-means с ограничениями (Constrained k-means). Позволяет учитывать априорную информацию (например, обязательное объединение некоторых точек в один кластер или запрет на объединение).
• X-means. Автоматически определяет оптимальное число кластеров k, используя критерий Байеса (BIC) или информационный критерий Акаике (AIC).

Применение

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

• Маркетинг: сегментация клиентов по поведению, демографии или покупательским привычкам.
• Обработка изображений: сжатие изображений (замена цветов палитрой из k цветов), сегментация изображений (выделение объектов).
• Биоинформатика: кластеризация генов со схожими профилями экспрессии, анализ последовательностей ДНК.
• Социология и психология: выявление типов личности или социальных групп на основе анкетных данных.
• Геоинформационные системы: группировка географических объектов (например, населённых пунктов) по близости расположения.
• Анализ текстов: кластеризация документов по тематикам (после векторизации текстов, например, с помощью TF-IDF).

Достоинства и недостатки

Достоинства

• Простота реализации и интерпретации результатов.
• Высокая скорость работы, особенно на больших наборах данных (линейная сложность O(n·k·d·I), где I — число итераций).
• Хорошо масштабируется на многомерные данные.

Недостатки

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

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

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

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

• В 2006 году алгоритм k-средних был признан одним из десяти наиболее влиятельных алгоритмов интеллектуального анализа данных (по версии IEEE International Conference on Data Mining).
• Метод k-means++ за его улучшенную инициализацию используется по умолчанию в библиотеке scikit-learn языка Python.
• Существует теорема о том, что для любого набора точек в евклидовом пространстве алгоритм Ллойда сходится за полиномиальное число итераций, хотя на практике обычно требуется 10–20 итераций.

Источники

• MacQueen, J. B. (1967). «Some Methods for classification and Analysis of Multivariate Observations». Proceedings of 5th 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 18th Annual ACM-SIAM Symposium on Discrete Algorithms.
• Hastie, T., Tibshirani, R., Friedman, J. (2009). «The Elements of Statistical Learning: Data Mining, Inference, and Prediction».
• Воронцов, К. В. (2007). «Лекции по методам кластеризации». Машинное обучение (курс лекций).