Участник:IanaV/Алгоритм k means

Авторы страницы: Валуйская Я.А. и Глотов Е.С.

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

1.1 Общее описание алгоритма

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

Алгоритм кластеризации k-means решает задачу распределения N наблюдений по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения.

1.2 Математическое описание алгоритма

Исходные данные:

• множество наблюдений [math]X = \{x_1, x_2, ..., x_n\}[/math], где каждое наблюдение [math]x_i \in R^d, i = 1, ..., n[/math];
• количество кластеров [math]k \in N, k \leq n[/math]

Обозначения:

• [math]S = \{S_1, S_2, ..., S_k \} [/math] - множество кластеров, которые удовлетворяют следующим условиям:
  • [math]S_i \bigcap S_j = \emptyset, i \neq j[/math];
  • [math]X = {\bigcup \limits _{i = 1}^k S_i} [/math].

• [math]\mu_i, i = 1, ..., k[/math] - центр масс кластера [math]S_i[/math]

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

• [math]L = (l_1, l_2, ..., l_n)[/math] - набор меток, где метка [math]l_i \in [1, k][/math] - является порядковым номером кластера, к которому принадлежит вектор [math]x_i[/math]: [math] x_i \in S_{l_i}[/math]

Цель алгоритма k-means - распределить наблюдения из входного множества [math]X[/math] по [math]k[/math] кластерам [math]S = \{S_1, S_2, ..., S_k \} [/math] таким образом, чтобы сумма квадратов расстояний от каждой точки кластера до его центра по всем кластерам была минимальной:

[math]\arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 [/math],

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

1. Инициализация центров масс
   На данном шаге задаются начальные значения центров масс [math] \mu_1^1, ..., \mu_k^1[/math]. Существует несколько способов их выбора. Они будут рассмотрены ниже.
2. t-ый шаг итерации:
   • Распределение векторов по кластерам
     На данном шаге каждый вектор [math]x \in X[/math] распределяется в свой кластер [math]S_i^t[/math] так, что:
     [math]l_i^t = \arg \min_{j} \left\| \mathbf x - \mu_j^t \right\|^2 , j = 1, ..., k[/math]
   • Пересчет центров масс кластеров
     На данном шаге происходит пересчет центров масс кластеров, полученных на предыдущем этапе:
     [math]\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x[/math]
3. Критерий останова
   [math]\mu_i^t = \mu_i^{t+1},[/math] для всех [math]i = 1, ..., k[/math]

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

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

1. распределение векторов по кластерам;
2. пересчет центров масс кластеров.

Распределение векторов по кластерам заключается в следующем: для каждого вектора [math]x_i \in X, i = 1, ..., n[/math] необходимо посчитать расстояние между этим вектором и центром масс кластера [math]\mu_j^t, j = 1, ..., k[/math]. Следовательно, на каждой итерации необходимо выполнить [math]n * k[/math] операций вычисления расстояния между векторами.

Пересчет центров масс кластеров заключается в следующем: для каждого кластера [math]S_i^t \in S, i = 1, ..., k[/math] необходимо пересчитать кластер по формуле, приведенной в пункте выше. Следовательно, на каждой итерации необходимо выполнить [math]k[/math] операций пересчета центров масс кластеров.

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

Макрооперацией алгоритма является расстояние между векторами, в данном алгоритме используется Евклидова метрика:
[math]v \in R^m[/math] и [math]u \in R^m: d(v, u) = \sqrt{\sum_{j=1}^{m} (v_j - u_j)^2} [/math].

1.5 Схема реализации последовательного алгоритма

Псевдокод алгоритма:

Входные данные  : Множество векторов [math]X[/math], количество кластеров [math]k[/math]
Выходные данные : Набор меток [math]L[/math] принадлежности к кластеру
1  Инициализация центров масс [math]\mu_i^1, i = 1, ..., k[/math];
2  t := 1;
3  Для каждого вектора [math]x_i, i = 1, ..., n: l_i^t = \arg \min_{j} \left\| \mathbf x - \mu_j^t \right\|^2 , j = 1, ..., k[/math]
4  Для каждого кластера: [math]\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x[/math], [math]i = 1, .., k[/math]
5  if (\exists i = 1, ..., k: [math]\mu_i^t \neq \mu_i^{t+1}[/math]) {
6      t := t + 1;
7  } else {
8      break;
9  };

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

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

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