Участник:Gkhazeeva/Нечеткий алгоритм C средних: различия между версиями
Yushin (обсуждение | вклад) |
Yushin (обсуждение | вклад) |
||
| Строка 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 средних | |
| Последовательный алгоритм | |
| Последовательная сложность | |
| Объём входных данных | |
| Объём выходных данных | |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | |
| Ширина ярусно-параллельной формы | |
Авторы : Гелана Хазеева, Павел Юшин
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма [2]
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Кластеризация - это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между группами. Нечеткий алгоритм C Средних (Fuzzy C-means, FCM) - алгоритм кластеризации, позволяющий объектам принадлежать с различной степенью нескольким кластерам одновременно. Впервые алгоритм был предложен J.C. Dunn в 1973 [1]. Нечеткое разбиение позволяет просто решить проблему объектов, расположенных на границе двух кластеров - им назначают степени принадлежностей равные 0.5.
Входные данные алгоритма: набор векторов, которые следует кластеризовать.
Параметры алгоритма: c - количество кластеров; m - экспоненциальный вес; \varepsilon - параметр останова алгоритма.
Выходные данные: матрица вероятностей принадлежности векторов кластерам.
Краткое описание алгоритма:
- Задать параметры алгоритма.
- Сгенерировать случайную матрицу принадлежностей векторов кластерам (матрицу нечеткого разбиения).
- Повторить следующие шаги до момента, пока матрицы нечеткого разбиения на этом и предыдущем шаге алгоритма будут отличать менее чем на параметр останова.
- Рассчитать центры кластеров.
- Рассчитать расстоение между объектами и центрами кластеров.
- Пересчитать элементы матрицы нечеткого разбиения.
1.2 Математическое описание алгоритма [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
