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

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

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

V=\sum _{i=1}^{k}\sum _{x\in S_{i}}(x-\mu _{i})^{2}

где $k$ — число кластеров, $S_{i}$ — полученные кластеры, $i=1,2,\dots ,k$ , а $\mu _{i}$ — центры масс всех векторов $x$ из кластера $S_{i}$ .

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

Алгоритм

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

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

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

Как показали Дэвид Артур и Сергей Васильвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна $2^{\Omega ({\sqrt {n}})}$ ^[6].

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

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

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

Проблемы k-means

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

Результат кластеризации методом k-средних для ирисов Фишера и реальные виды ирисов, визуализированные с помощью ELKI^[англ.]. Центры кластеров отмечены с помощью крупных, полупрозрачных маркеров.

Не гарантируется достижение глобального минимума суммарного квадратичного отклонения 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). 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?" (PDF). Proceedings of the 2006 Symposium on Computational Geometry (SoCG). Архивировано (PDF) 24 января 2009. Дата обращения: 20 апреля 2008.
↑ E.M. Mirkes, K-means and K-medoids applet Архивная копия от 29 мая 2013 на Wayback Machine. University of Leicester, 2011.
↑ Adam Coates and Andrew Y. Ng. Learning Feature Representations with K-means Архивная копия от 21 июня 2015 на Wayback Machine, Stanford University, 2012

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

Дж. Ту, Р. Гонсалес «Принципы распознавания образов», Издательство «Мир», Москва 1978, стр. 109—112 (описание алгоритма с численным примером).
K-means and K-medoids (апплет, демонстрирующий работу алгоритма и позволяющий исследовать и сравнивать два метода), Е. Миркес и University of Leicester
Интерактивный апплет, демонстрирующий работу алгоритма

[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.

[Mirkes2011-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG

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

Содержание

Алгоритм

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

Проблемы k-means

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

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

Ссылки

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

Навигация

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

Алгоритм

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

Проблемы k-means

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

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

Ссылки

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

Навигация

Поиск