Участник:Бротиковская Данута/Алгоритм 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$ = $\{x_1, x_2, ..., x_n\}$. Алгоритм k средних разбивает набор $X$ на $k, k\lt =n$ наборов $S=\{S_1, S_2, ..., S_k\}$ таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра. Другими словами:

$\arg\min_{S} \sum\limits_{i=1}^k \sum\limits_{x \in S_i} \lVert \mathbf{x}- \mathbf{\mu_i} \rVert^2$, где $\mu_i$- центры кластеров, $\overline{i=1,k}$

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

1. Начальный шаг: Инициализация кластеров. Выбирается произвольное множество k точек, рассматриваемых как начальные центры кластеров.

2. Распределение векторов по кластерам: $\forall \mathbf{x_i} \in \mathbf{X}, \overline{i=1,N}: \mathbf{x_i} \in S_j \iff j=\arg\min_{k}|x_i-\mu_k|$,