Уровень алгоритма

Участник:Шишков Илья Сергеевич/Алгоритм 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.

Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Шишков_Илья_Сергеевич/Алгоритм_HCM_(Hard_C_–_Means)&oldid=10298