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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 37: Строка 37:
 
Пусть <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> 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>\sum_{j = 1}^c w_{ij} = 1, i = 1, ..., M</math> <math>(1)</math>
 
* <math>0 < \sum_{i = 1}^M w_{ij} < M, j = 1, ..., c</math> <math>(2)</math>
 
* <math>0 < \sum_{i = 1}^M w_{ij} < M, j = 1, ..., c</math> <math>(2)</math>
 +
 +
Тогда алгоритм принимает следующий вид:
 +
 +
1) Задаем параметры алгоритма: <math>c</math> - количество кластеров; <math>m >= 1</math> - экспоненциальный вес, определяющий нечеткость кластеров; <math>\varepsilon > 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>
  
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==

Версия 00:15, 11 октября 2016


Нечеткий алгоритм C средних
Последовательный алгоритм
Последовательная сложность [math][/math]
Объём входных данных [math][/math]
Объём выходных данных [math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [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]

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

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

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

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

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

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

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

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

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

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

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

3 Литература