Участник:Gkhazeeva/Нечеткий алгоритм C средних: различия между версиями
Yushin (обсуждение | вклад) |
Yushin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
| name = Нечеткий алгоритм C средних | | name = Нечеткий алгоритм C средних | ||
| serial_complexity = <math>O(ndc^2i)</math>, <math>i</math> - количество итераций | | serial_complexity = <math>O(ndc^2i)</math>, <math>i</math> - количество итераций | ||
| − | | input_data = <math>n*d</math>, [количество наблюдений | + | | input_data = <math>n*d</math>, [количество наблюдений * размерность] |
| − | | output_data = <math>n*c</math>, [количество наблюдений | + | | output_data = <math>n*c</math>, [количество наблюдений * количество кластеров] |
| pf_height = <math></math> | | pf_height = <math></math> | ||
| pf_width = <math></math> | | pf_width = <math></math> | ||
| Строка 48: | Строка 48: | ||
2) Генерируем случайным образом матрицу нечеткого разбиения с учетом условий <math>(1)</math> и <math>(2)</math> | 2) Генерируем случайным образом матрицу нечеткого разбиения с учетом условий <math>(1)</math> и <math>(2)</math> | ||
| − | 3) Рассчитываем центроиды (центры кластеров): <math> | + | 3) Рассчитываем центроиды (центры кластеров): <math>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>X</math> и центроидами: | 4) Рассчитываем расстояния между объектами <math>X</math> и центроидами: | ||
| Строка 58: | Строка 58: | ||
при <math>D_{ki} >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} = {{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> - символ Кронекера | + | при <math>D_{ki} =0</math> : <math>w_{kj} = \delta_{ji}, j = 1,...,c</math>, где <math>\delta_{ji}</math> - символ Кронекера |
6) Если <math>|| F - F^{*} || < \varepsilon </math>, где <math>F^{*}</math> - матрица нечеткого разбиения предыдущей итерации, то идем далее, иначе возвращаемся на пункт 3. | 6) Если <math>|| F - F^{*} || < \varepsilon </math>, где <math>F^{*}</math> - матрица нечеткого разбиения предыдущей итерации, то идем далее, иначе возвращаемся на пункт 3. | ||
| Строка 67: | Строка 67: | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
| + | Вычислительным ядром алгоритма являются пункты (3), (4), (5) - расчет центроидов, вычисление расстояний и пересчет элементов матрицы соответственно | ||
== Макроструктура алгоритма == | == Макроструктура алгоритма == | ||
| − | + | Основные шаги при реализации алгоритма | |
| + | * Генерация случайной матрицы размера <math>M</math> на где <math>c</math>, проверка условий | ||
| + | * Расчет центроидов – по сути, скалярное произведение с нормировкой | ||
| + | * Расчет расстояний – в общепринятом случае является скалярным произведением | ||
| + | * Пересчет матрицы – по сути, скалярное произведение | ||
| + | * Проверка условий останова – вычисление нормы | ||
== Схема реализации последовательного алгоритма == | == Схема реализации последовательного алгоритма == | ||
| Строка 75: | Строка 81: | ||
== Последовательная сложность алгоритма == | == Последовательная сложность алгоритма == | ||
| − | + | Последовательная сложность алгоритма состоит из сложности каждой итерации умноженной на их количество. Так как число итераций заранее неизвестно и зависит от входных параметров, рассмотрим сложность на каждой итерации. Наибольшую сложность представляет собой расчет центроидов, сложность которого <math>O(c^2 nd)</math> (по сравнению со сложностью <math>O(cnd)</math> расчета расстояний, пересчета матрицы и проверки условия останова). Итого общая сложность алгоритма <math>O(c^2 ndi)</math> | |
== Информационный граф == | == Информационный граф == | ||
Версия 20:42, 11 октября 2016
| Нечеткий алгоритм C средних | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(ndc^2i)[/math], [math]i[/math] - количество итераций |
| Объём входных данных | [math]n*d[/math], [количество наблюдений * размерность] |
| Объём выходных данных | [math]n*c[/math], [количество наблюдений * количество кластеров] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math][/math] |
| Ширина ярусно-параллельной формы | [math][/math] |
Авторы : Гелана Хазеева, Павел Юшин
Содержание
- 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.
Входные данные алгоритма: набор векторов, которые следует кластеризовать.
Параметры алгоритма: [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_j = {{\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}, j = 1,...,c[/math], где [math]\delta_{ji}[/math] - символ Кронекера
6) Если [math]|| F - F^{*} || \lt \varepsilon [/math], где [math]F^{*}[/math] - матрица нечеткого разбиения предыдущей итерации, то идем далее, иначе возвращаемся на пункт 3.
7) Конец.
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма являются пункты (3), (4), (5) - расчет центроидов, вычисление расстояний и пересчет элементов матрицы соответственно
1.4 Макроструктура алгоритма
Основные шаги при реализации алгоритма
- Генерация случайной матрицы размера [math]M[/math] на где [math]c[/math], проверка условий
- Расчет центроидов – по сути, скалярное произведение с нормировкой
- Расчет расстояний – в общепринятом случае является скалярным произведением
- Пересчет матрицы – по сути, скалярное произведение
- Проверка условий останова – вычисление нормы
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма состоит из сложности каждой итерации умноженной на их количество. Так как число итераций заранее неизвестно и зависит от входных параметров, рассмотрим сложность на каждой итерации. Наибольшую сложность представляет собой расчет центроидов, сложность которого [math]O(c^2 nd)[/math] (по сравнению со сложностью [math]O(cnd)[/math] расчета расстояний, пересчета матрицы и проверки условия останова). Итого общая сложность алгоритма [math]O(c^2 ndi)[/math]
