Участник: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],

Алгоритм состоит из следующих шагов:

1. Инициализация центров масс
   На данном шаге задаются начальные значения центров масс [math]\displaystyle{ \mu_1^1, ..., \mu_k^1 }[/math]. Существует несколько способов их выбора. Они будут рассмотрены ниже.
2. 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]
3. Критерий останова
   [math]\displaystyle{ \mu_i^t = \mu_i^{t+1}, }[/math] для всех [math]\displaystyle{ i = 1, ..., k }[/math]

Вычислительное ядро алгоритма

Вычислительном ядром алгоритма является шаг 2, состоящий из следующих этапов:

1. распределение векторов по кластерам;
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] операций пересчета центров масс кластеров.

Макроструктура алгоритма

1. Макрооперация "Расстояние между векторами"
   В данном алгоритме используется Евклидова метрика:
   [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];
2. Макрооперация "Пересчет центра масс кластера"
   [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 };

Входные и выходные данные алгоритма

Входные данные:

• [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]

Свойства алгоритма

Достоинства:

1. Алгоритм прозрачный и понятный, за счет чего очень прост в реализации;
2. Алгоритм имеет высокую скорость работы в случае выбора оптимальных начальных значений центров масс кластеров.

Недостатки:

1. Число кластеров является входным аргументом алгоритма. Таким образом, некорректный выбор данного параметра может привести к плохим результатам работы алгоритма, поэтому очень важно проводить диагностические прогоны для подбора оптимального количества кластеров;
2. Алгоритм может сойтись к локальному минимуму (достижение глобального минимума не гарантируется);
3. Результат сильно зависит от выбора начальных значений центров масс кластеров. Существует улучшенная версия алгоритма - k-means++, которая предлагает свой способ нахождения начальных оптимальных значений центров масс кластеров.

Устойчивость: todo

Сбалансированность: todo

Соотношение последовательной и параллельной сложности: todo

Вычислительная мощность: todo

Детерминированность: todo

Программная реализация алгоритма

Существующие реализации алгоритма

Существуют следующие 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