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

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

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

Впервые строгий алгоритм C средних (Hard C-Means) был сформулирован Jang, Sun and Mizutani в 1997. Он позволяет распределить большие наборы числовых данных по кластерам в многомерном пространстве. Алгоритм является управляемым, так как для работы с ним требуется задание одного параметра — числа кластеров, на которое необходимо разделить данные.

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

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

1) Расчёт рядовой матрицы, которая показывает для каждого вектора ближайший кластерный центр.

2) Расчёт объектной функции. Проверка условий остановки и завершение расчета в случае их выполнения.

3) Пересчёт кластерных центров.

Так как алгоритм является итеративным и зависит от начальных значений кластерных центров, то он может сходиться локальному минимуму.

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

1.2.1 Входные и выходные данные

Входные данные:

• [math]\{u_k\}_{k=1}^{n} \subset \mathbb{R}^n[/math] — исходный набор векторов;
• [math]c[/math] — желаемое количество кластеров ([math]2 \leqslant c \leqslant n[/math]);
• (опционально) [math]\varepsilon_{tr}[/math] — пороговая точность работы алгоритма.

Выходные данные:

• [math]M[/math] — рядовая матрица.

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

Алгоритм состоит из 5 последовательных шагов.

Шаг 1

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

Шаг 2

Вычисление рядовой матрицы [math]M = \|m_{ik}\|[/math], элементы которой задаются следующими выражениями ([math]n[/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=1,2,\ldots,c, \; k = 1,2,\ldots,n)\\ 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]

На этом шаге происходит остановка и выход из цикла, если полученное значение ниже пороговой величины [math]\varepsilon_{tr}[/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]\|u_k-c_i\|^2[/math]. На каждой итерации алгоритма происходит расчёт [math]nc[/math] таких расстояний.

1.9 Входные и выходные данные алгоритма

На вход подаётся набор векторов [math]\{u_k\}_{k=1}^{n}[/math] пространства [math]\mathbb{R}^m[/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]-ый построенный кластер.