Участник:Шишков Илья Сергеевич/Алгоритм HCM (Hard C – Means): различия между версиями
Строка 17: | Строка 17: | ||
Последовательность исполнения метода следующая: | Последовательность исполнения метода следующая: | ||
− | |||
1. Инициализация кластерных центров <math>c_i \, (i=1,2,\ldots,c)</math>. Это можно сделать выбрав случайным образом <math>c</math> – векторов из входного набора. | 1. Инициализация кластерных центров <math>c_i \, (i=1,2,\ldots,c)</math>. Это можно сделать выбрав случайным образом <math>c</math> – векторов из входного набора. | ||
Строка 34: | Строка 33: | ||
</math> --> | </math> --> | ||
− | 3. Расчёт объектной функции: | + | 3. Расчёт объектной функции: |
:<math> | :<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) | 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) |
Версия 18:59, 15 октября 2016
Алгоритм 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.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{other}. \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.