Участник:IanaV/Алгоритм k means
Авторы страницы: Валуйская Я.А., Глотов Е.С.
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации.
Алгоритм был разработан в 1956 году математиком Гуго Штейнгаузом [1], и почти одновременно его изобрел Стюарт Ллойд [2]. Особую популярность алгоритм снискал после работы Джеймса Маккуина [3]
Алгоритм кластеризации k-means решает задачу распределения [math]\displaystyle{ N }[/math] наблюдений (элементов векторного пространства) на заранее известное число кластеров [math]\displaystyle{ K }[/math]. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера.
Основная идея алгоритма заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.
Математическое описание алгоритма
Исходные данные:
- множество наблюдений [math]\displaystyle{ X = \{x_1, x_2, ..., x_n\} }[/math], где каждое наблюдение [math]\displaystyle{ x_i \in R^d, i = 1, ..., n }[/math];
- количество кластеров [math]\displaystyle{ k \in N, k \leq n }[/math]
Обозначения:
- [math]\displaystyle{ S = \{S_1, S_2, ..., S_k \} }[/math] - множество кластеров, которые удовлетворяют следующим условиям:
- [math]\displaystyle{ S_i \bigcap S_j = \emptyset, i \neq j }[/math];
- [math]\displaystyle{ X = {\bigcup \limits _{i = 1}^k S_i} }[/math].
- [math]\displaystyle{ \mu_i \in R^d, i = 1, ..., k }[/math] - центр масс кластера [math]\displaystyle{ S_i }[/math]
- [math]\displaystyle{ d(u, v) }[/math] - расстояние между векторами [math]\displaystyle{ u \in R^m, v \in R^m }[/math]
Выходные данные:
- [math]\displaystyle{ L = (l_1, l_2, ..., l_n) }[/math] - набор меток, где метка [math]\displaystyle{ l_i \in N_{[1, k]} }[/math] - является порядковым номером кластера, к которому принадлежит вектор [math]\displaystyle{ x_i }[/math]: [math]\displaystyle{ x_i \in S_{l_i} }[/math]
Цель алгоритма k-means - распределить наблюдения из входного множества [math]\displaystyle{ X }[/math] по [math]\displaystyle{ k }[/math] кластерам [math]\displaystyle{ S = \{S_1, S_2, ..., S_k \} }[/math] таким образом, чтобы сумма квадратов расстояний от каждой точки кластера до его центра масс по всем кластерам была минимальной:
[math]\displaystyle{ \arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} (d(x, \mu_i))^2 }[/math],
Алгоритм состоит из следующих шагов:
- Инициализация центров масс
На данном шаге задаются начальные значения центров масс [math]\displaystyle{ \mu_1^1, ..., \mu_k^1 }[/math]. Существует несколько способов их выбора. Они будут рассмотрены ниже. - t-ый шаг итерации:
- Распределение векторов по кластерам
На данном шаге каждый вектор [math]\displaystyle{ x \in X }[/math] распределяется в свой кластер [math]\displaystyle{ S_i^t }[/math] так, что:
[math]\displaystyle{ l_i^t = \arg \min_{j} (d(x, \mu_j^t))^2 , j = 1, ..., k }[/math] - Пересчет центров масс кластеров
На данном шаге происходит пересчет центров масс кластеров, полученных на предыдущем этапе:
[math]\displaystyle{ \mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x }[/math]
- Распределение векторов по кластерам
- Критерий останова
[math]\displaystyle{ \mu_i^t = \mu_i^{t+1}, }[/math] для всех [math]\displaystyle{ i = 1, ..., k }[/math]
Способы инициализации начальных данных:
- Метод Forgy
Случайным образом выбираются [math]\displaystyle{ k }[/math] векторов из множества наблюдений [math]\displaystyle{ X }[/math]. Эти вектора используются в качестве центров масс кластеров [math]\displaystyle{ \mu_1, ..., \mu_k }[/math] - Метод случайного разбиения (Random Partition) [4]
Каждый вектор [math]\displaystyle{ x_i, i = 1, .., n }[/math] случайным образом распределяется в кластер [math]\displaystyle{ S_j, j = 1, .., k }[/math], затем для каждого кластера вычисляется его центр масс [math]\displaystyle{ \mu_j }[/math].
Вычислительное ядро алгоритма
Вычислительном ядром алгоритма является шаг 2, состоящий из следующих этапов:
- распределение векторов по кластерам;
- пересчет центров масс кластеров.
Распределение векторов по кластерам заключается в следующем: для каждого вектора [math]\displaystyle{ x_i \in X, i = 1, ..., n }[/math] необходимо посчитать расстояние между этим вектором и центром масс кластера [math]\displaystyle{ \mu_j^t, j = 1, ..., k }[/math]. Следовательно, на каждой итерации необходимо выполнить [math]\displaystyle{ n * k }[/math] операций вычисления расстояния между векторами.
Пересчет центров масс кластеров заключается в следующем: для каждого кластера [math]\displaystyle{ S_i^t \in S, i = 1, ..., k }[/math] необходимо пересчитать кластер по формуле, приведенной в пункте выше. Следовательно, на каждой итерации необходимо выполнить [math]\displaystyle{ k }[/math] операций пересчета центров масс кластеров.
Макроструктура алгоритма
- Макрооперация "Расстояние между векторами"
В данном алгоритме используется Евклидова метрика:
[math]\displaystyle{ v \in R^m }[/math] и [math]\displaystyle{ u \in R^m: d(v, u) = \sqrt{\sum_{j=1}^{m} (v_j - u_j)^2} }[/math]; - Макрооперация "Пересчет центра масс кластера"
[math]\displaystyle{ \mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x }[/math]
Схема реализации последовательного алгоритма
Псевдокод алгоритма:
Входные данные : Множество векторов [math]\displaystyle{ X }[/math], количество кластеров [math]\displaystyle{ k }[/math] Выходные данные : Набор меток [math]\displaystyle{ L }[/math] принадлежности к кластеру 1 Инициализация центров масс [math]\displaystyle{ \mu_i^1, i = 1, ..., k }[/math]; 2 t := 1; 3 Для каждого вектора [math]\displaystyle{ x_i \in X, i = 1, ..., n: }[/math] [math]\displaystyle{ l_i^t = \arg \min_{j} (d(x_i,\mu_j^t))^2 , j = 1, ..., k }[/math]; 4 Для каждого кластера [math]\displaystyle{ S_i^t, i = 1, ..., k }[/math] выполняется макрооперация "Пересчет центра масс"; 5 if ([math]\displaystyle{ \exists i = 1, ..., k: \mu_i^t \neq \mu_i^{t+1} }[/math]) { 6 t := t + 1; 7 goto 3; 8 } else { 9 stop; 10 };
Последовательная сложность алгоритма
Подсчитаем количество операций для каждого шага алгоритма.
- Инициализация:
- Метод Forgy: [math]\displaystyle{ N_{init} = 0 }[/math]
- Метод случайного разбиения:
- Количество операций деления: [math]\displaystyle{ N^{/}_{init} = k * d }[/math];
- Количество операций сложения: [math]\displaystyle{ N^{+}_{init} = d * (n - k) }[/math].
- Распределение [math]\displaystyle{ n }[/math] векторов [math]\displaystyle{ x_i \in R^d }[/math] по [math]\displaystyle{ k }[/math] кластерам на одной итерации:
- Количество операций умножения: [math]\displaystyle{ N^{*}_{distr} = k * n * d }[/math];
- Количество операций сложения: [math]\displaystyle{ N^{+}_{distr} = k * n * (d - 1) }[/math];
- Количество операция вычитания: [math]\displaystyle{ N^{-}_{distr} = k * n * d }[/math].
- Пересчет центра масс [math]\displaystyle{ \mu_i \in R^d }[/math] для [math]\displaystyle{ k }[/math] кластеров на одной итерации:
- Количество операций деления: [math]\displaystyle{ N^{/}_{centr} = k * d }[/math];
- Количество операций сложения: [math]\displaystyle{ N^{+}_{centr} = d * (n - k) }[/math].
Следовательно, в случае если алгоритм сошелся за [math]\displaystyle{ i }[/math] итераций, получаем:
- Операций сложения/вычитания: [math]\displaystyle{ N^{+,-}_{k-means} = N^{+}_{init} + i*(N^{+}_{distr} + N^{-}_{distr} + N^{+}_{centr}) = d * (n - k) + i*(k*n*(d-1)+k*n*d+d*(n-k)) \thicksim O(i*k*n*d) }[/math]
- Операций умножения/деления: [math]\displaystyle{ N^{*,/}_{k-means} = N^{/}_{init} + i*(N^{*}_{distr} + N^{/}_{centr}) = k * d + i*(k*n*d+k*d) \thicksim O(i*k*n*d) }[/math]
Таким образом, последовательная сложность алгоритма k-means для [math]\displaystyle{ n }[/math] [math]\displaystyle{ d }[/math]-мерных векторов и [math]\displaystyle{ k }[/math] кластеров за [math]\displaystyle{ i }[/math] итераций, требуемых для сходимости алгоритма:
[math]\displaystyle{ O(i * n * k * d) }[/math]
Существуют способы ускорения алгоритма [5] [6] [7]
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Входные данные:
- [math]\displaystyle{ n }[/math] векторов [math]\displaystyle{ x_i \in R^d, i = 1, ..., n }[/math];
- число кластеров [math]\displaystyle{ k \in N_{[1,n]} }[/math].
Объем входных данных: [math]\displaystyle{ n * d }[/math] действительных чисел, 1 целое число
Выходные данные:
- вектор меток [math]\displaystyle{ L \in N^n }[/math].
Объем выходных данных: [math]\displaystyle{ n }[/math] целых чисел. [math]\displaystyle{ n \in [1,k] }[/math]
Свойства алгоритма
- Достоинства
- Алгоритм прозрачный и понятный, за счет чего очень прост в реализации;
- Алгоритм имеет высокую скорость работы в случае выбора оптимальных начальных значений центров масс кластеров.
- Недостатки
- Число кластеров является входным аргументом алгоритма. Таким образом, некорректный выбор данного параметра может привести к плохим результатам работы алгоритма, поэтому очень важно проводить диагностические прогоны для подбора оптимального количества кластеров;
- Алгоритм может сойтись к локальному минимуму (достижение глобального минимума не гарантируется);
- Результат сильно зависит от выбора начальных значений центров масс кластеров. Существует улучшенная версия алгоритма - k-means++ [8], которая предлагает свой способ нахождения начальных оптимальных значений центров масс кластеров.
- Устойчивость
- Алгоритм является устойчивым к погрешностям во входных данных, так как при вычислении центров кластеров расстояния между объектами усредняются, что приводит к уменьшению ошибки
- Сбалансированность
- todo
- Соотношение последовательной и параллельной сложности
- todo
- Вычислительная мощность
- [math]\displaystyle{ {O(n*d*k*i) \over n*d+n+1} \thicksim {O(d*k*i) \over d+1} \thicksim O(k*i) }[/math], где [math]\displaystyle{ n }[/math] - число входных векторов, [math]\displaystyle{ d }[/math] - размерность векторов, [math]\displaystyle{ k }[/math] - число кластеров, [math]\displaystyle{ i }[/math] - число итераций, требуемое для сходимости
- Детерминированность
- Алгоритм является недетерминированным, так как результат зависит от выбора исходных центров кластеров, а их оптимальный выбор неизвестен.
Программная реализация алгоритма
Масштабируемость алгоритма и его реализации
Существующие реализации алгоритма
Существуют следующие Open Source реализации алгоритма:
- ELKI - содержит реализацию алгоритма k-means на языке Java (в том числе реализацию улучшенного алгоритма k-means++)
- Weka - содержит реализацию k-means на языке Java
- Apache Mahout - содержит реализацию k-means в парадигме MapReduce
- Spark Mllib - содержит распределенную реализацию k-means
- Accord.NET - содержит реализацию k-means на C# (в том числе реализацию улучшенного алгоритма k-means++)
- MLPACK - содержит реализацию k-means на языке C++
- OpenCV - содержит реализацию k-means на C++. А также есть обертки для языков Python и Java
- SciPy - содержит реализацию k-means на языке Python
- Scikit-learn - содержит реализацию k-means на языке Python
- Julia - содержит реализацию алгоритма k-means на языке Julia
- Octave - содержит реализацию k-means на языке Octave
- R - содержит реализацию k-means на языке R
- Torch - содержит реализацию k-means на языке Lua
Литература
- ↑ 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.
- ↑ Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings". Proceedings of the eleventh international conference on Information and knowledge management (CIKM).
- ↑ Phillips, Steven J. (2002-01-04). Mount, David M.; Stein, Clifford, eds. Acceleration of K-Means and Related Clustering Algorithms. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 166–177.
- ↑ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.187.3017&rep=rep1&type=pdf Hamerly G. Making k-means Even Faster //SDM. – 2010. – С. 130-140.]
- ↑ Elkan C. Using the triangle inequality to accelerate k-means //ICML. – 2003. – Т. 3. – С. 147-153.
- ↑ Arthur, D.; Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding". Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035.