- K-means
-
k-means (иногда называемый k-средних) - наиболее популярный метод кластеризации. Был изобретён в 1950-х математиком Г. Штейнгаузом[1] и почти одновременно С. Ллойдом[2]. Особую популярность приобрёл после работы МакКвина[3].
Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное уклонение точек кластеров от центров этих кластеров:
где k - число кластеров, Si - полученные кластеры, и μi - центры масс векторов .
По аналогии с методом главных компонент центры кластеров называются также главными точками, а сам метод называется методом главных точек[4] и включается в общую теорию главных объектов, обеспечивающих наилучшую аппроксимацию данных[5].
Содержание
Алгоритм
Алгоритм представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбраной метрике.
Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множество конечно, а на каждом шаге суммарное квадратичное уклонение V уменьшается, поэтому зацикливание невозможно.
Как показали Д.Артур и С.Вассилвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна .[6]
Демонстрация алгоритма
Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.
Проблемы k-means
- Не гарантируется достижение глобального минимума суммарного квадратичного уклонения V, а только одного из локальных минимумов.
- Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
- Число кластеров надо знать заранее.
Расширения и вариации
Широко известна и используется нейросетевая реализация K-means - сети векторного квантования сигналов (одна из версий нейронных сетей Кохонена).
Ссылки
- ↑ Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801-804.
- ↑ Lloyd S. (1957). Least square quantization in PCM's. Bell Telephone Laboratories Paper.
- ↑ 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.
- ↑ Flury B. (1990). Principal points. Biometrika, 77, 33-41.
- ↑ 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.
- ↑ David Arthur & Sergei Vassilvitskii (2006). "How Slow is the k-means Method?". Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
Демонстрация и визуализация
- K-means and K-medoids (апплет, демонстрирующий работу алгоритма и позволяющий исследовать и сравнивать два метода), Е. Миркес и University of Leicester
Категории:- Машинное обучение
- Кластерный анализ
-
Wikimedia Foundation. 2010.