Участник:Бротиковская Данута/Алгоритм k-means

Алгоритм k средних (k means)
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^3) }[/math]
Объём входных данных	[math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]
Объём выходных данных	[math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(n) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(n^2) }[/math]

Авторы страницы Данута Бротиковская и Денис Зобнин

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

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

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

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

Дан набор из [math]\displaystyle{ n }[/math] d-мерных векторов [math]\displaystyle{ X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\} }[/math]. Алгоритм k средних разбивает набор [math]\displaystyle{ X }[/math] на [math]\displaystyle{ k, k\lt =n }[/math] наборов [math]\displaystyle{ S=\{S_1, S_2, ..., S_k\}, S_i \cap S_j= \varnothing, i \ne j, }[/math] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами:

[math]\displaystyle{ \arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu}_i \rVert^2 }[/math],

где [math]\displaystyle{ \mathbf{\mu}_i }[/math]- центры кластеров, [math]\displaystyle{ i=\overline{1,k} }[/math]

Шаги алгоритма:

1. Начальный шаг: инициализация кластеров

   Выбирается произвольное множество точек [math]\displaystyle{ \mu_i, i=\overline{1,k} }[/math], рассматриваемых как начальные центры кластеров.

2. Распределение векторов по кластерам

   [math]\displaystyle{ \forall \mathbf{x}_i \in X, i=\overline{1,n}: \mathbf{x}_i \in S_j \iff j=\arg\min_{k}||\mathbf{x}_i-\mathbf{\mu}_k||^2 }[/math]

3. Пересчет центров кластеров

   [math]\displaystyle{ \forall i=\overline{1,k}: \widetilde{\mu_i} = \cfrac{1}{||S_i||}\sum_{x\in S_i}x }[/math]

4. Проверка условия останова:

      if [math]\displaystyle{ \exist i\in \overline{1,k}: \mu_i \ne \widetilde{\mu_i} }[/math] then
          goto 2;
      else
          stop
   

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

Вычислительным ядром являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.

Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором [math]\displaystyle{ \mathbf{x}_i \in X, i= \overline{1,n} }[/math] и центрами кластера [math]\displaystyle{ \mathbf{\mu}_j, j= \overline{1,k} }[/math]. Таким образом, данный шаг предполагает [math]\displaystyle{ k*n }[/math] вычислений расстояний между d-мерными векторами.

Пересчет центров кластеров предполагает [math]\displaystyle{ k }[/math] вычислений центров масс [math]\displaystyle{ \mathbf{\mu}_i }[/math] множеств [math]\displaystyle{ S_i, i=\overline{1,k} }[/math] представленных выражением в шаге 3 представленного выше алгоритма.

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

algorithm k-means is
    1. Инициализировать центры кластеров [math]\displaystyle{ \mathbf{\mu}_i^{(1)}, i=\overline{1,k} }[/math]
    2. [math]\displaystyle{ t \leftarrow 1 }[/math]
    3. Распределение по кластерам

       [math]\displaystyle{ S_i^{(t)}=\{\mathbf{x}_p: \lVert\mathbf{x}_p-\mathbf{\mu}_i^{(t)}\rVert^2 \leq \lVert\mathbf{x}_p-\mathbf{\mu}_j^{(t)}\rVert^2 \quad \forall j=\overline{1,k}\}, }[/math]

       где каждый вектор [math]\displaystyle{ \mathbf{x}_p }[/math] соотносится единственному кластеру [math]\displaystyle{ S^{(t)} }[/math]
    4. Обновление центров кластеров

       [math]\displaystyle{ \mathbf{\mu}_i^{(t+1)} = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf{x}_j \in S^{(t)}_i} \mathbf{x}_j  }[/math]

    5. if [math]\displaystyle{ \exist i \in \overline{1,k}: \mathbf{\mu}_i^{(t)} \ne \mathbf{\mu}_i^{(t+1)} }[/math] then
           goto 3;
       else
           stop

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

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

• Целое положительное число [math]\displaystyle{ k }[/math]– количество кластеров.
• Матрица из [math]\displaystyle{ n*d }[/math] элементов – координат векторов (наблюдений).

Объем входных данных
1 целое число + [math]\displaystyle{ n*d }[/math] вещественных чисел (при условии, что координаты – вещественные числа).

Выходные данные
Целые положительные числа – номера кластеров, соотвествующие каждому вектору (при условии, что нумерация кластеров начинается с 1).

Объем выходных данных
[math]\displaystyle{ n }[/math] целых положительных чисел.

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

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

1. OpenCV
2. MLPACK
3. SciPy
4. scikit-learn
5. MATLAB
6. R
7. SAS

Литература

1. MacQueen, James. "Some methods for classification and analysis of multivariate observations." Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.
2. Steinhaus, Hugo. "Sur la division des corp materiels en parties." Bull. Acad. Polon. Sci 1.804 (1956): 801.
3. Lloyd, S. P. "Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM." IEEE Trans. Inform. Theor.(1957/1982).