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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 
{{algorithm
 
{{algorithm
 
| name              = Нечеткий алгоритм C средних
 
| name              = Нечеткий алгоритм C средних
| serial_complexity = <math>O(ncl)</math>
+
| serial_complexity = <math>O(ndc^2i)</math>, <math>i<\math> - количество итераций
 
| input_data        = <math>n*d</math>, [количество наблюдений x размерность]
 
| input_data        = <math>n*d</math>, [количество наблюдений x размерность]
 
| output_data          = <math>n*c</math>, [количество наблюдений x количество кластеров]
 
| output_data          = <math>n*c</math>, [количество наблюдений x количество кластеров]

Версия 01:43, 11 октября 2016


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


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

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 Литература