Участник:Бротиковская Данута/Алгоритм 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
          [math]\displaystyle{ FINISH }[/math]
   

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

Вычислительным ядром являются шаги 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]

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

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

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

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

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

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