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

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

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

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

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

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

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

2. Вычисление рядовой матрицы [math]M[/math]:

[math] 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]

где К – количество элементов во входном наборе данных.

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

[math] 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] c_i = \frac{1}{|C_i|} \sum\limits_{k:\, u_k \in C_i} u_k, [/math]

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

5. на шаг 2.