Участник:Gkhazeeva/Нечеткий алгоритм C средних

Нечеткий алгоритм C средних
Последовательный алгоритм
Последовательная сложность	$O(ndc^2i)$, $i\lt \math\gt - количество итераций | input_data = \lt math\gt n*d$, [количество наблюдений x размерность]
Объём выходных данных	$n*c$, [количество наблюдений x количество кластеров]
Параллельный алгоритм
Высота ярусно-параллельной формы
Ширина ярусно-параллельной формы

Авторы : Гелана Хазеева, Павел Юшин

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

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

Кластеризация - это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между группами. Нечеткий алгоритм C Средних (Fuzzy C-means, FCM) - алгоритм кластеризации, позволяющий объектам принадлежать с различной степенью нескольким кластерам одновременно. Впервые алгоритм был предложен J.C. Dunn в 1973 . Нечеткое разбиение позволяет просто решить проблему объектов, расположенных на границе двух кластеров - им назначают степени принадлежностей равные 0.5.

Входные данные алгоритма: набор векторов, которые следует кластеризовать.

Параметры алгоритма: $c$ - количество кластеров; $m$ - экспоненциальный вес; $\varepsilon$ - параметр останова алгоритма.

Выходные данные: матрица вероятностей принадлежности векторов кластерам.

Краткое описание алгоритма:

• Задать параметры алгоритма.

• Сгенерировать случайную матрицу принадлежностей векторов кластерам (матрицу нечеткого разбиения).

• Повторить следующие шаги до момента, пока матрицы нечеткого разбиения на этом и предыдущем шаге алгоритма будут отличать менее чем на параметр останова.
  • Рассчитать центры кластеров.
  • Рассчитать расстоение между объектами и центрами кластеров.
  • Пересчитать элементы матрицы нечеткого разбиения.

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

Пусть $W = w_{ij} \in[0,1],\; i = 1, ..., M, \; j = 1, ..., c$ - матрица разбиения, где $w_{i,j}$ - степень принадлежности объекта $i$ к кластеру $j$; $c$ - количество кластеров, $M$ - количество векторов.

При этом элементы матрицы должны удовлетворять условиям:

• $\sum_{j = 1}^c w_{ij} = 1, i = 1, ..., M$ $(1)$
• $0 \lt \sum_{i = 1}^M w_{ij} \lt M, j = 1, ..., c$ $(2)$

Тогда алгоритм принимает следующий вид:

1) Задаем параметры алгоритма: $c$ - количество кластеров; $m \gt = 1$ - экспоненциальный вес, определяющий нечеткость кластеров; $\varepsilon \gt 0$ - параметр останова алгоритма.

2) Генерируем случайным образом матрицу нечеткого разбиения с учетом условий $(1)$ и $(2)$

3) Рассчитываем центроиды (центры кластеров): $V_i = {{\sum_{i=1}^M w_{ij}^m * |X_i|} \over {\sum_{i=1}^M w_{ij}^m}}, j = 1, ..., c$

4) Рассчитываем расстояния между объектами $X$ и центроидами:

$D_{ij} = \sqrt{{||X_i - V_j||}^2}, i = 1,...,M; j = 1,...,c$

5) Пересчет элементов матрицы разбиения:

при $D_{ki} \gt 0$ : $w_{kj} = {{1}\over {{ ( D_{jk}^2 * \sum_{j=1}^c {{1}\over{D_{jk}^2}} ) }^{1/(m-1)}}}, j = 1,...,c$

при $D_{ki} =0$ : $w_{kj} = \delta_{ji}$, где $\delta_{ji}$ - символ Кронекера

6) Если $|| F - F^{*} || \lt \varepsilon$, где $F^{*}$ - матрица нечеткого разбиения предыдущей итерации, то идем далее, иначе возвращаемся на пункт 3.

7) Конец.