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

Метод k-средних (англ. k-means) — наиболее популярный метод кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом[1] и почти одновременно Стюартом Ллойдом[2]. Особую популярность приобрёл после работы Маккуина[3].

Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:

где  — число кластеров,  — полученные кластеры, , а  — центры масс всех векторов из кластера .

По аналогии с методом главных компонент центры кластеров называются также главными точками, а сам метод называется методом главных точек[4] и включается в общую теорию главных объектов, обеспечивающих наилучшую аппроксимацию данных[5].

Алгоритм представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.

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

Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение V уменьшается, поэтому зацикливание невозможно.

Как показали Дэвид Артур и Сергей Васильвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна [6].

Демонстрация алгоритма

[править | править код]

Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.

Исходные точки и случайно выбранные начальные центры.
Точки, отнесённые к начальным центрам. Разбиение на плоскости — диаграмма Вороного относительно начальных центров.
Вычисление новых центров кластеров (Ищется центр масс).
Предыдущие шаги, за исключением первого, повторяются, пока алгоритм не сойдётся.

Проблемы k-means

[править | править код]
Типичный пример сходимости метода k средних к локальному минимуму. В этом примере результат «кластеризации» методом k средних противоречит очевидной кластерной структуре множества данных. Маленькими кружками обозначены точки данных, четырёхлучевые звезды — центроиды. Принадлежащие им точки данных окрашены в тот же цвет. Иллюстрация подготовлена с помощью апплета Миркеса[7].
Результат кластеризации методом k-средних для ирисов Фишера и реальные виды ирисов, визуализированные с помощью ELKI[англ.]. Центры кластеров отмечены с помощью крупных, полупрозрачных маркеров.
  • Не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов.
  • Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
  • Число кластеров надо знать заранее.

Расширения и вариации

[править | править код]

Широко известна и используется нейросетевая реализация K-means — сети векторного квантования сигналов (одна из версий нейронных сетей Кохонена).

Существует расширение k-means++, которое направлено на оптимальный выбор начальных значений центров кластеров.


Применение для задач глубокого обучения и машинного зрения

[править | править код]

В алгоритмах глубокого обучения метод k-средних иногда применяют не по прямому назначению (классификация разбивкой на кластеры), а для создания так называемых фильтров (ядер свёртки, словарей). Например, для распознавания изображений в алгоритм k-средних подают небольшие случайные кусочки изображений обучающей выборки, допустим, размером 16х16 в виде линейного вектора, каждый элемент которого кодирует яркость своей точки. Количество кластеров k задается большим, например 256. Обученный метод k-средних при определенных условиях вырабатывает при этом центры кластеров (центроиды), которые представляют собой удобные базисы, на которые можно разложить любое входное изображение. Такие "обученные" центроиды в дальнейшем используют в качестве фильтров, например для свёрточной нейронной сети в качестве ядер свёртки или других аналогичных систем машинного зрения[8]. Таким образом осуществляется обучение без учителя при помощи метода k-средних.

  1. Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.
  2. Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.
  3. MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.
  4. Flury B. (1990). Principal points. Biometrika, 77, 33-41.
  5. Gorban A.N., Zinovyev A.Y. (2009). Principal Graphs and Manifolds, Ch. 2 in: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques, Emilio Soria Olivas et al. (eds), IGI Global, Hershey, PA, USA, pp. 28-59.
  6. David Arthur & Sergei Vassilvitskii (2006). "How Slow is the k-means Method?" (PDF). Proceedings of the 2006 Symposium on Computational Geometry (SoCG). Архивировано (PDF) 24 января 2009. Дата обращения: 20 апреля 2008.
  7. E.M. Mirkes, K-means and K-medoids applet Архивная копия от 29 мая 2013 на Wayback Machine. University of Leicester, 2011.
  8. Adam Coates and Andrew Y. Ng. Learning Feature Representations with K-means Архивная копия от 21 июня 2015 на Wayback Machine, Stanford University, 2012

Демонстрация и визуализация

[править | править код]