Участник:Бротиковская Данута/Алгоритм 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 }[/math] = [math]\displaystyle{ \{x_1, x_2, ..., 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{ \mu_i }[/math]- центры кластеров, [math]\displaystyle{ \overline{i=1,k} }[/math]

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

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

2. Распределение векторов по кластерам: [math]\displaystyle{ \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| }[/math]

3. Пересчет центров кластеров: [math]\displaystyle{ \forall i=\overline{i=1,k}: \widetilde{\mu_i} = \cfrac{1}{||S_i||}\sum_{x\in S_i}x }[/math]

4. Проверка условия останова: [math]\displaystyle{ if \exist i\in \overline{i=1,k}: \mu_i != \widetilde{\mu_i} =\gt goto 2; else FINISH }[/math]