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

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

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

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

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

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

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

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

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

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

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

Алгоритм описывается при помощи 5 шагов.

Шаг 1

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

Шаг 2

Вычисление рядовой матрицы [math]M = \|m_{ik}\|[/math], элементы которой задаются следующими выражениями (подразумевается, что [math]K[/math] — количество элементов во входном наборе данных):

[math] m_{ik} = \left\{ \begin{align} 1, & \; \|u_k-c_i\|^2 \leqslant \|u_k-c_j\|^2 \;\; \forall i \neq j; \;\; (i=1,2,\ldots,c, \; k = 1,2,\ldots,K)\\ 0, & \; \text{otherwise}. \end{align} \right. [/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|} \cdot \sum\limits_{k:\, u_k \in C_i} u_k, [/math]

где под [math]|C_i|[/math] подразумевается количество элементов в [math]i-[/math]ом кластере.

Шаг 5

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