k-means
k-means (метод k-средних) — наиболее популярный метод кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом[1] и почти одновременно Стюартом Ллойдом[2]. Особую популярность приобрёл после работы Маккуина[3].
Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:
- <math>V = \sum_{i=1}^{k} \sum_{x_j \in S_i} (x_j - \mu_i)^2 </math>
где <math>k</math> — число кластеров, <math>S_i</math> — полученные кластеры, <math>i = 1, 2, \dots, k</math> и <math>\mu_i</math> — центры масс векторов <math>x_j \in S_i</math>.
По аналогии с методом главных компонент центры кластеров называются также главными точками, а сам метод называется методом главных точек[4] и включается в общую теорию главных объектов, обеспечивающих наилучшую аппроксимацию данных[5].
Содержание
Алгоритм
Алгоритм представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.
Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение V не увеличивается, поэтому зацикливание невозможно.
Как показали Дэвид Артур и Сергей Васильвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна <math>2^{\Omega(\sqrt{n})}</math>.[6]
Демонстрация алгоритма
Действие алгоритма в двумерном случае. Начальные точки выбраны случайно.
|
|
|
|
|---|
Проблемы k-means
- Не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов.
- Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
- Число кластеров надо знать заранее.
Расширения и вариации
Широко известна и используется нейросетевая реализация K-means — сети векторного квантования сигналов (одна из версий нейронных сетей Кохонена).
Существует расширение k-means++, которое направлено на оптимальный выбор начальных значений центров кластеров.
Применение для задач глубокого обучения и машинного зрения
В алгоритмах глубокого обучения метод k-средних иногда применяют не по прямому назначению (классификация разбивкой на кластеры), а для создания так называемых фильтров (ядер свёртки, словарей). Например, для распознавания изображений в алгоритм k-средних подают небольшие случайные кусочки изображений обучающей выборки, допустим, размером 16х16 в виде линейного вектора, каждый элемент которого кодирует яркость своей точки. Количество кластеров k задается большим, например 256. Обученный метод k-средних при определенных условиях вырабатывает при этом центры кластеров (центроиды), которые представляют собой удобные базисы, на которые можно разложить любое входное изображение. Такие "обученные" центроиды в дальнейшем используют в качестве фильтров, например для свёрточной нейронной сети в качестве ядер свёртки или других аналогичных систем машинного зрения[8]. Таким образом осуществляется обучение без учителя при помощи метода k-средних.
Ссылки
- ↑ 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). [arxiv.org/pdf/0809.0490v2 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). "[www.cs.duke.edu/courses/spring07/cps296.2/papers/kMeans-socg.pdf How Slow is the k-means Method?]". Proceedings of the 2006 Symposium on Computational Geometry (SoCG).
- ↑ E.M. Mirkes, [www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids applet]. University of Leicester, 2011.
- ↑ Adam Coates and Andrew Y. Ng. [www.cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf Learning Feature Representations with K-means], Stanford University, 2012
Демонстрация и визуализация
- Дж. Ту, Р. Гонсалес "Принципы распознавания образов", Издательство "Мир", Москва 1978, стр. 109-112 (описание алгоритма с численным примером).
- [www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids] (апплет, демонстрирующий работу алгоритма и позволяющий исследовать и сравнивать два метода), Е. Миркес и [www2.le.ac.uk/ University of Leicester]
- [home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html Интерактивный апплет, демонстрирующий работу алгоритма]
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
