Участник:Urandon/Строгий алгоритм С средних (Hard C-Means, HCM)

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

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

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

Строгий алгоритм C средних (Hard C-Means; Jang, Sun and Mizutani, 1997) пытается определить центры кластеров в многомерном признаковом пространстве. Цель заключается в том, что бы сопоставить каждой точке признакового пространства соответствующий кластер.

Назначение алгоритма заключается в кластеризации больших наборов числовых данных представленных признаковыми описаниями объектов. Достоинства алгоритма в классе алгоритмов, решающих данную задачу, -- лёгкость реализации и вычислительная простота. Недостатки же -- явное задание количества кластеров, отсутствие гарантии нахождения оптимального решения.

На вход алгоритму задаются точки конечномерного признакового пространства и количество кластеров. Так же могут задаваться пороговые значения, использующиеся в критерии останова алгоритма: величина целевого функционала, скорость изменения функционала при выполнении основного цикла алгоритма. Целевой функционал алгоритма -- среднее внутрикластерное расстояние.

На первом шаге алгоритма производится инициализация центров кластеров. Это может быть осуществлено путём выбора случайных значений. Затем выполняется основной цикл алгоритма:

1. Расчёт рядовой матрицы, сопоставляющей каждую точку признакового пространства с ближайшим к ней кластерному центру. Иначе это можно рассматривать как оптимизацию целевого функционала по принадлежности точек к кластерам
2. Расчёт целевого функционала. Проверка условий критерия останова и выход из цикла в случае его выполнения.
3. Пересчёт кластерных центров как центров масс точек кластера. Представляет собой оптимизацию целевого функционала по координатам центров кластеров.

Алгоритм гарантирует монотонное невозрастание целевой функционала, следовательно, сходимость к локальному минимуму.

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

На вход алгоритм принимает точки [math]\{u_k\}_{k=1}^{N}[/math] признакового пространства [math]\mathbb{R}^D[/math] и количество кластеров [math]C[/math].

На выходе алгоритм возвращает рядовую матрицу[math]M[/math], содержащую информацию о принадлежности элементов кластерам: [math] m_{ij} = \begin{cases} 1, & u_j \in C_i, \\ 0, & \text{otherwise}, \end{cases} [/math] где [math]C_i[/math] -- это множество точек, принажлежащих [math]i[/math]-му кластеру, и а [math]c_i[/math] -- центр [math]i[/math]-го кластера.

Алгоритм состоит из пяти шагов, включающих инициализацию и цикл оптимизации.

Шаг 1 – инициализация центров кластеров

[math] c_i \sim Uniform \{u_1, \dots, u_N\} [/math] -- инициализация путём случайного выбора центров кластеров из точек входного набора. Начальные центры кластером так же могут быть заданы пользователем явно. [math]test[/math]

Шаг 2 – вычисление рядовой матрицы [math]M[/math]

[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]

где [math]N[/math] — количество элементов во входном наборе данных.

Представляет собой шаг [math]J \to \min_{M}[/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]J \to \min_{c_1, \dots, c_N}[/math]

Шаг 5 – зацикливание

Переход по циклу к шагу 2.

1.3 Вычислительное ядро алгоритма

Для каждой пары [math]\{u_i, c_k\}, i \in \mathbb{N}_N, k \in \mathbb{N}_C[/math] согласно алгоритму необходимо вычислить расстояние [math]\|u_i - c_k\|^2[/math] в [math]D[/math]-мерном пространстве. Такие расстояние вычисляются для [math]NC[/math] пар. Таким образом, происходит вычисление [math]O(NCD)[/math] арифметичеких операций.

1.4 Макроструктура алгоритма

Алгоритм распадается на макрооперации, примитивами которых выступают вектора линейных пространств.

Вычисление разностей векторов с последующим вычислением евклидовой нормы на втором шаге алгоритма. [math] d_{ik} = \|u_k - c_i\|^2 [/math]

Нахождение аргминимума в векторе при фиксированном объекте [math]k[/math]: [math] i^* = \arg\!\min\limits_{i = 1 \dots C} d_{ik} [/math]. После чего [math]m_{ik} := [i = i^*][/math].

Суммирование матрицы вдоль [math] J = \sum\limits_{i=1}^C J_i = \sum\limits_{i=1}^C \left( \sum\limits_{k:\, u_k \in C_i} d_{ki} \right) = \sum\limits_{i=1}^C\sum\limits_{k=1}^N m_{ik} d_{ik} = \mathbb{e} M \odot D \mathbb{e}^T .[/math]