Участник:Шишков Илья Сергеевич/Алгоритм 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.1 Общее описание алгоритма
Алгоритм HCM (Строгий алгоритм С-средних) был предложен группой исследователей(Jang, Sun and Mizutani) в 1997 и относится к классу алгоритмов со строгой кластеризаций.
Кластеризацией называется подход к описанию данных, в котором наиболее схожие данные объединяются в группы(кластеры). Кластеризация является распространенным подходом для анализа данных и используется во многих сферах научной деятельности, таких как машинное обучение, анализ данных, распознавание шаблонов, анализ изображений и биоинформатика.
Кластеризация представляет собой комбинирование рассматриваемых объектов так, чтобы каждая группа объектов обладала схожим свойством. В общем случае кластеризация характеризуются следующими критериями: - Каждая группа или кластер однородны; объекты, принадлежащие одной группе имеют схожие свойства; - Каждая группа или кластер отличаются от других кластеров т.е. объекты, принадлежащие одному кластеру, должны отличатся от объектов других кластеров
В строгой кластеризации наборы данных разделяются на кластеры однозначно. Каждый набор данных может относится только к одному кластеру. Строгой кластеризации характеризуется следующими свойствами: - Используется для классификации данных в однозначные наборы - Каждый набор данных принадлежит только одному кластеру - Кластеры также называют разделами - Результатом работы кластерного алгоритма является матрица соответствия которая показывает, к какому кластеру принадлежит каждый набор данных
В этом кластерном алгоритме не допускается частичное отношение к кластеру (как в FCM). HCM предназначен для классификации входных наборов в строгом смысле. В строгом алгоритме С-средних данные классифицируются по кластерам однозначно, т.е. при определенном заранее критерии, каждый элемент данных может принадлежать одному и только одному кластеру.
Алгоритм HCM является итеративным и состоит из нескольких шагов: 1) Инициализация:
Случайным образом определяются C векторов - центров кластеров
2) Расчет рядовой матрицы:
В процессе расчета рядовой матрицы каждый вектор сравнивается с ближайшим кластерным центром
3) Расчет оценочной функции:
Проверка условия, при котором алгоритм завершает работу и вывод результата в этом случае
4) Переопределение кластерных центров
Пункты 2-4 выполняются до тех пор, пока в пункте 3 проверка не станет успешной.
1.2 Математическое описание алгоритма
Обозначения
[math]X[/math] - наборы данных
[math]X_{i}[/math] - i-ый набор из [math]X[/math]
[math]x[/math] - любой набор из [math]X[/math]
[math]n[/math] - количество наборов в [math]X[/math]
[math]N[/math] - кластерный центр после обновления
[math]V_{j}[/math] - j-ый кластер
[math]C[/math] - количество кластеров
[math]v_{j}[/math] - j-ый кластерный центр
[math]v^*_{j}[/math] - j-ый кластерный центр после обновления
Выходные данные: [math]V_{1}, V_{2}, ... V_{C}[/math]
Объектная функция:
[math]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]X_{1},X_{2}, ... X_{n}[/math] выбираются [math]C[/math] начальных кластерных центра [math] v_{1},v_{2},...,v_{C}[/math]либо случайным образом, либо с использованием заранее определенного алгоритма
Шаг 2
Рассчитывается рядовая матрица [math] M=\|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,N)\\ 0, & \text{otherwise}. \end{cases} [/math]
Шаг 3
Рассчитывается объектная функция J. На этом этапе может быть инициировано завершение алгоритма в случае если значение объектной функции незначительно изменилось относительно предыдущей итерации или достигло ожидаемого значения.
Шаг 4
Рассчитываются новые кластерные центры по следующей формуле:
[math] v^*_{j} = \frac{1}{|v_{j}} === Схема реализации последовательного алгоритма === Последовательность исполнения метода следующая: 1. Инициализация кластерных центров \lt math\gt 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]
где К – количество элементов во входном наборе данных.
Матрица [math]M[/math] обладает следующими свойствами:
- [math] \sum\limits_{i=1}^c m_{ij} = 1, \;\; \sum\limits_{j=1}^K m_{ij} = K. [/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.
1.3 Последовательная сложность алгоритма
Каждая операция вычисления квадрата нормы разности векторов выполненяет [math]n[/math] вычитаний, [math]n-1[/math] сложений и [math]n[/math] операций возведения в квадрат (умножений).
Для каждой итерации алгоритма требуется:
- [math]ncK[/math] умножений,
- [math]ncK[/math] вычитаний,
- [math]K(c+cn+1)[/math] сложений,
- [math]\frac{c(c+1)K}{2}[/math] сравнений.
Умножения, сложения (вычитания), сравнения составляют основную часть алгоритма.
Итоговая сложность последовательной реализации алгоритма [math]O(ncK)[/math]. Обычно [math]n[/math], [math]c[/math] значительно меньше, чем [math]K[/math].
1.4 Информационный граф
опишем граф как аналитически, так и в виде рисунка.
Граф алгоритма состоит из шести групп вершин.
Первая группа вершин d_{1},...,d_{c} - прямое вычисление расстояния до кластерных центров, то есть вычисление расстояний от заданного элемента [math]u_i[/math] до каждого из кластерных центров. Вторая группа вершин min - ей соответствует вычисление минимального расстояния до кластерных центров,передача найденного минимального расстояния и соответствующего ему индекса кластера. Третья группа вершин M - ей соответствует операция записи единички в столбец матрицы. Четвертая группа вершин J - вычисление объектной функции, происходит проверка условия достижения необходимой точности, если достигли заданной точности то переход Out, в противном случае Conversion. Пятая группа вершин Conversion - пересчёт кластерных центров и переход на следующую итерацию.
На рисунке изображена одна итерация алгоритма.
