Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску


Нечеткий алгоритм C средних
Последовательный алгоритм
Последовательная сложность [math]O(ncl)[/math]
Объём входных данных [math][/math]
Объём выходных данных [math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]n*d[/math], [количество наблюдений x размерность]
Ширина ярусно-параллельной формы [math]n*c[/math], [количество наблюдений x количество кластеров]


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

7) Конец.


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

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

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

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

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Локальность данных и вычислений

2.2 Масштабируемость алгоритма и его реализации

3 Литература