Участник:Gkhazeeva/Нечеткий алгоритм C средних: различия между версиями
Yushin (обсуждение | вклад) |
Yushin (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
Входные данные алгоритма: набор векторов, которые следует кластеризовать. | Входные данные алгоритма: набор векторов, которые следует кластеризовать. | ||
| + | |||
Параметры алгоритма: <math>c</math> - количество кластеров; <math>m</math> - экспоненциальный вес; <math>\varepsilon</math> - параметр останова алгоритма. | Параметры алгоритма: <math>c</math> - количество кластеров; <math>m</math> - экспоненциальный вес; <math>\varepsilon</math> - параметр останова алгоритма. | ||
| + | Выходные данные: матрица вероятностей принадлежности векторов кластерам. | ||
| + | |||
| + | Краткое описание алгоритма: | ||
| + | |||
| + | * Задать параметры алгоритма. | ||
| + | |||
| + | * Сгенерировать случайную матрицу принадлежностей векторов кластерам (матрицу нечеткого разбиения). | ||
| + | |||
| + | * Повторить следующие шаги до момента, пока матрицы нечеткого разбиения на этом и предыдущем шаге алгоритма будут отличать менее чем на параметр останова. | ||
| + | ** Рассчитать центры кластеров. | ||
| + | ** Рассчитать расстоение между объектами и центрами кластеров. | ||
| + | ** Пересчитать элементы матрицы нечеткого разбиения. | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
Версия 23:16, 10 октября 2016
| Нечеткий алгоритм C средних | |
| Последовательный алгоритм | |
| Последовательная сложность | [math][/math] |
| Объём входных данных | [math][/math] |
| Объём выходных данных | [math][/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math][/math] |
| Ширина ярусно-параллельной формы | [math][/math] |
Авторы : Гелана Хазеева, Павел Юшин
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.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.
Входные данные алгоритма: набор векторов, которые следует кластеризовать.
Параметры алгоритма: [math]c[/math] - количество кластеров; [math]m[/math] - экспоненциальный вес; [math]\varepsilon[/math] - параметр останова алгоритма.
Выходные данные: матрица вероятностей принадлежности векторов кластерам.
Краткое описание алгоритма:
- Задать параметры алгоритма.
- Сгенерировать случайную матрицу принадлежностей векторов кластерам (матрицу нечеткого разбиения).
- Повторить следующие шаги до момента, пока матрицы нечеткого разбиения на этом и предыдущем шаге алгоритма будут отличать менее чем на параметр останова.
- Рассчитать центры кластеров.
- Рассчитать расстоение между объектами и центрами кластеров.
- Пересчитать элементы матрицы нечеткого разбиения.
