Участник:Gkhazeeva/Нечеткий алгоритм C средних
| Нечеткий алгоритм C средних | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(ndc^2i) }[/math], [math]\displaystyle{ i }[/math] - количество итераций |
| Объём входных данных | [math]\displaystyle{ n*d }[/math], [количество наблюдений * размерность] |
| Объём выходных данных | [math]\displaystyle{ n*c }[/math], [количество наблюдений * количество кластеров] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ }[/math] |
Авторы : Гелана Хазеева, Павел Юшин
Свойства и структура алгоритмов
Общее описание алгоритма
Кластеризация - это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между группами. Нечеткий алгоритм C Средних (Fuzzy C-means, FCM) - алгоритм кластеризации, позволяющий объектам принадлежать с различной степенью нескольким кластерам одновременно. Впервые алгоритм был предложен J.C. Dunn в 1973 [1]. Нечеткое разбиение позволяет просто решить проблему объектов, расположенных на границе двух кластеров - им назначают степени принадлежностей равные 0.5.
Входные данные алгоритма: набор векторов, которые следует кластеризовать.
Параметры алгоритма: [math]\displaystyle{ c }[/math] - количество кластеров; [math]\displaystyle{ m }[/math] - экспоненциальный вес; [math]\displaystyle{ \varepsilon }[/math] - параметр останова алгоритма.
Выходные данные: матрица вероятностей принадлежности векторов кластерам.
Краткое описание алгоритма:
- Задать параметры алгоритма.
- Сгенерировать случайную матрицу принадлежностей векторов кластерам (матрицу нечеткого разбиения).
- Повторить следующие шаги до момента, пока матрицы нечеткого разбиения на этом и предыдущем шаге алгоритма будут отличать менее чем на параметр останова.
- Рассчитать центры кластеров.
- Рассчитать расстоение между объектами и центрами кластеров.
- Пересчитать элементы матрицы нечеткого разбиения.
Математическое описание алгоритма [2]
Пусть [math]\displaystyle{ W = w_{ij} \in[0,1],\; i = 1, ..., M, \; j = 1, ..., c }[/math] - матрица разбиения, где [math]\displaystyle{ w_{i,j} }[/math] - степень принадлежности объекта [math]\displaystyle{ i }[/math] к кластеру [math]\displaystyle{ j }[/math]; [math]\displaystyle{ c }[/math] - количество кластеров, [math]\displaystyle{ M }[/math] - количество векторов.
При этом элементы матрицы должны удовлетворять условиям:
- [math]\displaystyle{ \sum_{j = 1}^c w_{ij} = 1, i = 1, ..., M }[/math] [math]\displaystyle{ (1) }[/math]
- [math]\displaystyle{ 0 \lt \sum_{i = 1}^M w_{ij} \lt M, j = 1, ..., c }[/math] [math]\displaystyle{ (2) }[/math]
Тогда алгоритм принимает следующий вид:
1) Задаем параметры алгоритма: [math]\displaystyle{ c }[/math] - количество кластеров; [math]\displaystyle{ m \gt = 1 }[/math] - экспоненциальный вес, определяющий нечеткость кластеров; [math]\displaystyle{ \varepsilon \gt 0 }[/math] - параметр останова алгоритма.
2) Генерируем случайным образом матрицу нечеткого разбиения с учетом условий [math]\displaystyle{ (1) }[/math] и [math]\displaystyle{ (2) }[/math]
3) Рассчитываем центроиды (центры кластеров): [math]\displaystyle{ V_j = {{\sum_{i=1}^M w_{ij}^m * |X_i|} \over {\sum_{i=1}^M w_{ij}^m}}, j = 1, ..., c }[/math]
4) Рассчитываем расстояния между объектами [math]\displaystyle{ X }[/math] и центроидами:
[math]\displaystyle{ D_{ij} = \sqrt{{||X_i - V_j||}^2}, i = 1,...,M; j = 1,...,c }[/math]
5) Пересчет элементов матрицы разбиения:
при [math]\displaystyle{ D_{ki} \gt 0 }[/math] : [math]\displaystyle{ w_{kj} = {{1}\over {{ ( D_{jk}^2 * \sum_{j=1}^c {{1}\over{D_{jk}^2}} ) }^{1/(m-1)}}}, j = 1,...,c }[/math]
при [math]\displaystyle{ D_{ki} =0 }[/math] : [math]\displaystyle{ w_{kj} = \delta_{ji}, j = 1,...,c }[/math], где [math]\displaystyle{ \delta_{ji} }[/math] - символ Кронекера
6) Если [math]\displaystyle{ || F - F^{*} || \lt \varepsilon }[/math], где [math]\displaystyle{ F^{*} }[/math] - матрица нечеткого разбиения предыдущей итерации, то идем далее, иначе возвращаемся на пункт 3.
7) Конец.
Вычислительное ядро алгоритма
Вычислительным ядром алгоритма являются пункты (3), (4), (5) - расчет центроидов, вычисление расстояний и пересчет элементов матрицы соответственно
Макроструктура алгоритма
Основные шаги при реализации алгоритма
- Генерация случайной матрицы размера [math]\displaystyle{ M }[/math] на где [math]\displaystyle{ c }[/math], проверка условий
- Расчет центроидов – по сути, скалярное произведение с нормировкой
- Расчет расстояний – в общепринятом случае является скалярным произведением
- Пересчет матрицы – по сути, скалярное произведение
- Проверка условий останова – вычисление нормы
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма состоит из сложности каждой итерации умноженной на их количество. Так как число итераций заранее неизвестно и зависит от входных параметров, рассмотрим сложность на каждой итерации. Наибольшую сложность представляет собой расчет центроидов, сложность которого [math]\displaystyle{ O(c^2 nd) }[/math] (по сравнению со сложностью [math]\displaystyle{ O(cnd) }[/math] расчета расстояний, пересчета матрицы и проверки условия останова). Итого общая сложность алгоритма [math]\displaystyle{ O(c^2 ndi) }[/math]