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

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

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

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

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

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

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

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

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

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

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

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

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

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

   $\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$

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

   $\forall i=\overline{1,k}: \widetilde{\mu_i} = \cfrac{1}{||S_i||}\sum_{x\in S_i}x$

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

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

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

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

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

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

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

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

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

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

• Целое положительное число $k$– количество кластеров.
• Матрица из $n*d$ элементов – координат векторов (наблюдений).

Объем входных данных
1 целое число + $n*d$ вещественных чисел (при условии, что координаты – вещественные числа).

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

Объем выходных данных
$n$ целых положительных чисел.