Участник:Шишков Илья Сергеевич/Алгоритм HCM (Hard C – Means)

Алгоритм HCM (Hard C – Means)
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^3) }[/math]
Объём входных данных	[math]\displaystyle{ O(n^2) }[/math]
Объём выходных данных	[math]\displaystyle{ O(n^2) }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ }[/math]

Основные авторы описания: Илья Шишков, Гульгайша Темербекова

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

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

Последовательность исполнения метода следующая:

1. Инициализация кластерных центров [math]\displaystyle{ c_i \, (i=1,2,\ldots,c) }[/math]. Это можно сделать выбрав случайным образом c – векторов из входного набора.

2. Вычисление рядовой матрицы [math]\displaystyle{ M = \|m_{ik}\| }[/math], Матрица [math]\displaystyle{ M }[/math] состоит из элементов [math]\displaystyle{ m_{ik} }[/math]:

[math]\displaystyle{ m_{ik} = \begin{cases} 1, & \|u_k-c_i\|^2 \leqslant \|u_k-c_j\|^2 \;\; \text{for all } i \neq j; \;\; (i,j=1,2,\ldots,C; \; k = 1,2,\ldots,K) \\ 0, & \text{otherwise}. \end{cases} }[/math]

где К – количество элементов во входном наборе данных. \\ Будем говорить, что [math]\displaystyle{ u_k \in C_i }[/math], если [math]\displaystyle{ m_{ik} = 1 }[/math].

3. Расчёт объектной функции: \\

[math]\displaystyle{ J = \sum\limits_{i=1}^C J_i = \sum\limits_{i=1}^C \left( \sum\limits_{k:\, u_k \in C_i} \|u_k -c_i \|^2 \right) . }[/math]

На этом шаге происходит остановка и выход из цикла, если полученное значение ниже пороговой величины или полученное значение не сильно отличается от значений, полученных на предыдущих циклах.

4. Пересчёт кластерных центров выполняется в соответствии со следующим уравнением:

[math]\displaystyle{ c_i = \frac{1}{|C_i|} \sum\limits_{k:\, u_k \in C_i} u_k, }[/math]

где под [math]\displaystyle{ |C_i| }[/math] подразумевается количество элементов в [math]\displaystyle{ i }[/math]-ом кластере.

5. на шаг 2.