Участник:Шишков Илья Сергеевич/Алгоритм HCM (Hard C – Means): различия между версиями
Строка 13: | Строка 13: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
+ | |||
+ | === Схема реализации последовательного алгоритма === | ||
+ | |||
+ | Последовательность исполнения метода следующая: | ||
+ | |||
+ | |||
+ | 1. Инициализация кластерных центров <math>c_i \, (i=1,2,\ldots,c)</math>. Это можно сделать выбрав случайным образом c – векторов из входного набора. | ||
+ | |||
+ | 2. Вычисление рядовой матрицы <math>M = \|m_{ik}\|</math>,Матрица <math>M<math> состоит из элементов <math>m_{ik}<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> | ||
+ | <!-- Матрица <math>M</math> обладает следующими свойствами: | ||
+ | :<math> | ||
+ | \sum\limits_{i=1}^C m_{ij} = 1, \;\; \sum\limits_{i=1}^C\sum\limits_{j=1}^K m_{ij} = K. | ||
+ | </math> --> | ||
+ | Будем говорить, что <math>u_k \in C_i</math>, если <math>m_{ik} = 1</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. |
Версия 18:46, 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]. Это можно сделать выбрав случайным образом c – векторов из входного набора.
2. Вычисление рядовой матрицы [math]M = \|m_{ik}\|[/math],Матрица [math]M\lt math\gt состоит из элементов \lt math\gt m_{ik}\lt math\gt : :\lt math\gt 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]u_k \in C_i[/math], если [math]m_{ik} = 1[/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.