Участник:Ян-Мартин Тамм/Строгий алгоритм С средних

Строгий алгоритм С средних (K-means, Hard C-Means)
Последовательный алгоритм
Последовательная сложность	$O(n)$
Объём входных данных	$mn+1$
Объём выходных данных	$cn$
Параллельный алгоритм
Высота ярусно-параллельной формы	$-$
Ширина ярусно-параллельной формы	$-$

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

Строгий алгоритм C средних, более известный как K-средних, решает задачу разделения векторов в многомерном пространстве на заданное количество кластеров. При этом каждый вектор принадлежит только одному кластеру, поэтому алгоритм называется строгим, в то время как нечеткий алгоритм C средних (Fuzzy C-means, Soft K-means) определяет степень принадлежности вектора каждому из кластеров.
Данная задача является NP-трудной, тем не менее описываемый алгоритм сходится к локальному оптимуму. Глобальный оптимум не гарантируется и зависит от первоначального распределения центров кластеров и их количества.
Общая идея алгоритма такова: произвольным образом выбираем центры кластеров, после чего повторяем следующие два действия, пока не будет выполнено условие остановки:

1. Распределяем каждый вектор в ближайший кластер
2. Пересчитываем значения центров как среднее значение координат векторов в каждом кластере

Минимизируется сумма расстояний векторов от центров их кластеров. Остановка производится если либо значение данной функции становится ниже некоторого порога, либо мало изменяется по сравнению с предыдущей итерацией.

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

Дано множество d-мерных векторов  $U=\{u_1, u_2, ..., u_n\}$ и число кластеров $k \in \mathbb{N}$. Требуется разбить множество $U$ на $k$ непересекающихся непустых кластеров $C_1, C_2, ..., C_k$ таких, что ${\bigcup \limits _{i = 1}^k C_i} = U$.
Для этого минимизируется функция $J = \sum\limits_{i=1}^k J_i = \sum\limits_{i=1}^k \sum\limits_{ u \in C_i} \|u-c_i \|^2$, где $c_i$— центр масс векторов кластера $C_i$.
Произвольным образом инициализируем центры кластеров $c_1, c_2, ..., c_k$, после чего начинается основная часть алгоритма.

• Каждый вектор $u_l$ определяем в ближайший к нему кластер $C_i$, то есть такой, что $\|u_l-c_i\|^2 \leqslant \|u_l-c_j\|^2 \;\; \forall i \neq j; \;\; (i,j=1,2,\ldots,k, \; l = 1,2,\ldots,n)$.
Хранить информацию о принадлежности векторов кластерам будем в матрице $M$ следующего вида:

$m_{ij} = \begin{cases} 1, & u_j \in C_i \\ 0, & \text{otherwise} \end{cases}$

• Считаем значение функции $J$ и прекращаем работу алгоритма, если это значение меньше заданного порога $\epsilon$, либо значение мало изменилось после текущей итерации.
• Обновляем значения центров кластеров

  $c_i = \frac{1}{|C_i|} \sum\limits_{u \in C_i} u \;\; (i=1,2,\ldots,k)$

• Возвращаемся к распределению векторов по кластерам.