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

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

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

Общее описание алгоритма

Алгоритм HCM (Строгий алгоритм С-средних) был предложен группой исследователей(Jang, Sun and Mizutani) в 1997 и относится к классу алгоритмов со строгой кластеризаций.

Кластеризацией называется подход к описанию данных, в котором наиболее схожие данные объединяются в группы(кластеры). Кластеризация является распространенным подходом для анализа данных и используется во многих сферах научной деятельности, таких как машинное обучение, анализ данных, распознавание шаблонов, анализ изображений и биоинформатика.

Кластеризация представляет собой комбинирование рассматриваемых объектов так, чтобы каждая группа объектов обладала схожим свойством. В общем случае кластеризация характеризуются следующими критериями: - Каждая группа или кластер однородны; объекты, принадлежащие одной группе имеют схожие свойства; - Каждая группа или кластер отличаются от других кластеров т.е. объекты, принадлежащие одному кластеру, должны отличатся от объектов других кластеров

В строгой кластеризации наборы данных разделяются на кластеры однозначно. Каждый набор данных может относится только к одному кластеру. Строгой кластеризации характеризуется следующими свойствами: - Используется для классификации данных в однозначные наборы - Каждый набор данных принадлежит только одному кластеру - Кластеры также называют разделами - Результатом работы кластерного алгоритма является матрица соответствия которая показывает, к какому кластеру принадлежит каждый набор данных

В этом кластерном алгоритме не допускается частичное отношение к кластеру (как в FCM). HCM предназначен для классификации входных наборов в строгом смысле. В строгом алгоритме С-средних данные классифицируются по кластерам однозначно, т.е. при определенном заранее критерии, каждый элемент данных может принадлежать одному и только одному кластеру.

Алгоритм HCM является итеративным и состоит из нескольких шагов: 1) Инициализация:

  Случайным образом определяются C векторов - центров кластеров

2) Расчет рядовой матрицы:

   В процессе расчета рядовой матрицы каждый вектор сравнивается с ближайшим кластерным центром

3) Расчет оценочной функции:

  Проверка условия, при котором алгоритм завершает работу и вывод результата в этом случае

4) Переопределение кластерных центров

Пункты 2-4 выполняются до тех пор, пока в пункте 3 проверка не станет успешной.

Математическое описание алгоритма

Обозначения

[math]\displaystyle{ X }[/math] - наборы данных

[math]\displaystyle{ X_{i} }[/math] - i-ый набор из [math]\displaystyle{ X }[/math]

[math]\displaystyle{ x }[/math] - любой набор из [math]\displaystyle{ X }[/math]

[math]\displaystyle{ n }[/math] - количество наборов в [math]\displaystyle{ X }[/math]

[math]\displaystyle{ N }[/math] - кластерный центр после обновления

[math]\displaystyle{ V_{j} }[/math] - j-ый кластер

[math]\displaystyle{ C }[/math] - количество кластеров

[math]\displaystyle{ v_{j} }[/math] - j-ый кластерный центр

[math]\displaystyle{ v^*_{j} }[/math] - j-ый кластерный центр после обновления

Выходные данные: [math]\displaystyle{ V_{1}, V_{2}, ... V_{C} }[/math]

Объектная функция:

[math]\displaystyle{ J=\sum_{j = 1}^{C} \sum_{x_{i} \in v_{j}}^{} \|x_{i}-v_{j}\|^2, j \in 1,2, ... C, i={1,2, ...n} }[/math]

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

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

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

2. Вычисление рядовой матрицы [math]\displaystyle{ M }[/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{other}. \end{cases} }[/math]

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

Матрица [math]\displaystyle{ M }[/math] обладает следующими свойствами:

[math]\displaystyle{ \sum\limits_{i=1}^c m_{ij} = 1, \;\; \sum\limits_{j=1}^K m_{ij} = K. }[/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.

Последовательная сложность алгоритма

Каждая операция вычисления квадрата нормы разности векторов выполненяет [math]\displaystyle{ n }[/math] вычитаний, [math]\displaystyle{ n-1 }[/math] сложений и [math]\displaystyle{ n }[/math] операций возведения в квадрат (умножений).

Для каждой итерации алгоритма требуется:

• [math]\displaystyle{ ncK }[/math] умножений,
• [math]\displaystyle{ ncK }[/math] вычитаний,
• [math]\displaystyle{ K(c+cn+1) }[/math] сложений,
• [math]\displaystyle{ \frac{c(c+1)K}{2} }[/math] сравнений.

Умножения, сложения (вычитания), сравнения составляют основную часть алгоритма.

Итоговая сложность последовательной реализации алгоритма [math]\displaystyle{ O(ncK) }[/math]. Обычно [math]\displaystyle{ n }[/math], [math]\displaystyle{ c }[/math] значительно меньше, чем [math]\displaystyle{ K }[/math].