Участник:Gkhazeeva/Нечеткий алгоритм C средних: различия между версиями
Gkhazeeva (обсуждение | вклад) |
Gkhazeeva (обсуждение | вклад) |
||
| Строка 191: | Строка 191: | ||
На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации | На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации в зависимости от изменяемых параметров запуска. | ||
Версия от 19:45, 13 ноября 2016
| Файл:Symbol wait.svg | Эта работа прошла предварительную проверку Дата последней правки страницы: 13.11.2016 Данная работа соответствует формальным критериям. Проверено Coctic. |
| Нечеткий алгоритм C средних | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(Mdc^2i) }[/math], [math]\displaystyle{ i }[/math] - количество итераций |
| Объём входных данных | [math]\displaystyle{ M*d }[/math], [количество наблюдений * размерность] |
| Объём выходных данных | [math]\displaystyle{ M*c }[/math], [количество наблюдений * количество кластеров] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ 2i }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ n }[/math] |
Авторы : Гелана Хазеева (1.3; 1.5; 1.6; 1.7; 2.4; 2.7), Павел Юшин (1.1; 1.2; 1.4; 1.8; 1.9; 1.10)
Свойства и структура алгоритмов
Общее описание алгоритма
Кластеризация - это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между группами. Нечеткий алгоритм 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} = {||X_i - V_j||}, i = 1,...,M; j = 1,...,c }[/math]
5) Пересчет элементов матрицы разбиения:
при [math]\displaystyle{ D_{ij} \gt 0 }[/math] : [math]\displaystyle{ w_{ij} = {{1}\over {{ (\sum_{k=1}^c {{D_{ij}}\over{D_{ik}}} ) }^{2/(m-1)}}}, j = 1,...,c }[/math]
при [math]\displaystyle{ D_{ij} =0 }[/math] : [math]\displaystyle{ w_{ij} = \delta_{ij}, j = 1,...,c }[/math], где [math]\displaystyle{ \delta_{ij} }[/math] - символ Кронекера
6) Если [math]\displaystyle{ || F - F^{*} || \lt \varepsilon }[/math], где [math]\displaystyle{ F^{*} }[/math] - матрица нечеткого разбиения предыдущей итерации, то идем далее, иначе возвращаемся на пункт 3.
7) Конец.
Вычислительное ядро алгоритма
Вычислительным ядром алгоритма являются следующие пункты:
- Поиск [math]\displaystyle{ V_j }[/math] - расчет центроидов (пункт 3 алгоритма)
- Нахождение [math]\displaystyle{ D_{ij} }[/math] - расстояний между объектами (пункт 4 алгоритма)
- Пересчет [math]\displaystyle{ w_{ij} }[/math] - элементов матрицы разбиения (пункт 5 алгоритма)
Макроструктура алгоритма
Основные шаги при реализации алгоритма
- Генерация случайной матрицы размера [math]\displaystyle{ M }[/math] на где [math]\displaystyle{ c }[/math], проверка условий
- Расчет центроидов – по сути, скалярное произведение с нормировкой
- Расчет расстояний – в общепринятом случае является скалярным произведением
- Пересчет матрицы – по сути, скалярное произведение
- Проверка условий останова – вычисление нормы
Схема реализации последовательного алгоритма
float ** FuzzyCMeans (float** X, c, m, eps){
n = X.size();
r = X[0].size();
centers = generateZeroFill(c, r)
Wprev = genetateRandFill(n, c);
W = Wprev;
while (true){
// обновляем центры кластеров
for (int i=0; i<c; i++){
float * num = new float []();
float den = 0;
for (int j=0; j<n; j++){
num += pow(W[j][i], m) * X[j];
den+=pow(W[j][i], m);
}
centers[i] = num / den;
}
//обновляем вероятности W и считаем расстояние между матрицами W и Wprev
float max_diff = 0;
for (int i=0; i<n; i++)
for (int j=0; j<c; j++){
total = 0;
for (int m=0; m<с; m++)
total += pow(distance(X[i], centers[j]) / distance(X[i], centers[m]), 2/(m-1));
W[i][j] = 1/total;
max_diff = max(abs(Wprev[i][j]-W[i][j]), max_diff);
Wprev[i][j] = W[i][j];
}
if (max_diff < eps):
break;
}
return W;
}
Последовательная сложность алгоритма
Последовательная сложность алгоритма состоит из сложности каждой итерации умноженной на их количество. Так как число итераций заранее неизвестно и зависит от входных параметров, рассмотрим сложность на каждой итерации. Наибольшую сложность представляет собой пересчет матрицы, сложность которого [math]\displaystyle{ O(c^2 nd) }[/math] (по сравнению со сложностью [math]\displaystyle{ O(cnd) }[/math] расчета расстояний, вычисления центроидов и проверки условия останова). Итого общая сложность алгоритма [math]\displaystyle{ O(c^2 ndi) }[/math]
Информационный граф
Информационный граф представлен на рисунке ниже.
Первый ярус состоит из [math]\displaystyle{ M }[/math] параллельных операций 1, 2, совершаемых в цикле [math]\displaystyle{ c }[/math] раз для каждого кластера.
Операция 1: [math]\displaystyle{ w_{ij}^m }[/math], где [math]\displaystyle{ j }[/math] - номер итерации в цикле, [math]\displaystyle{ i }[/math] - номер параллельной ветви.
Операция 2: [math]\displaystyle{ w_{ij}^m*X_i }[/math]
Здесь [math]\displaystyle{ j }[/math] - номер итерации в цикле, [math]\displaystyle{ i }[/math] - номер параллельной ветви.
На выходе из каждой ветки получаем вектор размера [math]\displaystyle{ 1 }[/math] x [math]\displaystyle{ c }[/math] и матрицу размера [math]\displaystyle{ d }[/math] x [math]\displaystyle{ c }[/math]. Далее совершаем поэлементное сложение векторов и матриц соответственно, а затем делим каждый столбец в матрице на соответствующий элемент в векторе.
Второй ярус состоит их [math]\displaystyle{ M }[/math] параллельных операций 3, 4, 5 также совершаемых в цикле [math]\displaystyle{ c }[/math] раз.
Операция 3: обновление значения [math]\displaystyle{ w_{ij} }[/math] по указанной в разделе 1.2 в пункте 5 формуле.
Операция 4: [math]\displaystyle{ maximum = max(|w_{ij} - w_{ij}^{prev}|, maximum) }[/math].
Операция 5: [math]\displaystyle{ w_{ij}^{prev} = w_{ij} }[/math].
Здесь [math]\displaystyle{ j }[/math] - номер итерации в цикле, [math]\displaystyle{ i }[/math] - номер параллельной ветви.
На выходе из каждой ветки получаем число [math]\displaystyle{ maximum }[/math]. Далее находим максимальное значение из полученных величин для каждой ветки. Затем проверяем условие останова алгоритма.
Ресурс параллелизма алгоритма
Параллельная сложность алгоритма: [math]\displaystyle{ M*c^2*i }[/math]. Такая сложность получается за счет распараллеливания на каждом ярусе [math]\displaystyle{ M }[/math] операций. Иерархическая структура параллелизма подробно описана в п.1.7.
В алгоритме не возникает скошенного параллелизма.
Входные и выходные данные алгоритма
- Входные данные алгоритма: набор векторов [math]\displaystyle{ x_i }[/math] размерности [math]\displaystyle{ d }[/math], где [math]\displaystyle{ i = 1,...,M }[/math]; [math]\displaystyle{ M }[/math] - количество векторов.
- Объем входных данных: [math]\displaystyle{ M*d }[/math] , [количество наблюдений * размерность].
- Выходные данные алгоритма: матрица вероятностей принадлежности векторов кластерам [math]\displaystyle{ M }[/math] на [math]\displaystyle{ c }[/math].
- Объем выходных данных: [math]\displaystyle{ M*c }[/math] , [количество наблюдений * количество кластеров].
Свойства алгоритма
- Соотношение последовательной и параллельной формы алгоритма: [math]\displaystyle{ M }[/math]
- Вычислительная мощность: [math]\displaystyle{ {dc^2i} \over {c+d} }[/math].
- Устойчивость: алгоритм не является устойчивым, поэтому существует много исследований о том, как первоначально выбрать параметры кластеризации.
- Сбалансированность: в данном алгоритме операция умножения доминирует над операцией сложения. Операции между параллельными ветвями сбалансированны.
- Детерминированность: алгоритм не является детерминированным, так как матрица нечеткого разбиение генерируется произвольно.
- Степень исхода вершины информационного графа ( для одной интерации): 2 (3 - с учетом, если выходные данные пошли на следующую итерацию).
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Проведём исследование масштабируемости параллельной реализации нечеткого алгоритма С-средних. Исследование проводилось на суперкомпьютере "Ломоносов"[3] Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [1 : 128];
- размер матрицы [10000 : 80000].
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 0,33%;
- максимальная эффективность реализации 9,4%.
На следующих рисунках приведены графики производительности и эффективности выбранной реализации в зависимости от изменяемых параметров запуска.
Построим оценки масштабируемости выбранной реализации нечеткого алгоритма С-средних: Построим оценки масштабируемости выбранной реализации разложения Холецкого:
- По числу процессов: 0.007. При увеличении числа процессов эффективность на рассмотренной области изменений параметров запуска увеличивается
- По размеру задачи: -0.0016. При увеличении размера задачи эффективность уменьшается.
- По двум направлениям: 0,000077. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая.
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Реализация алгоритма на POSTGRESQL: http://num-meth.srcc.msu.ru/zhurnal/tom_2012/pdf/v13r207.pdf
- Библиотека для MATLAB: http://www.mathworks.com/help/fuzzy/fcm.html (распространяется на коммерческой основе)
Литература
- ↑ | J. C. Dunn. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters. Journal of Cybernetics, volume 3,1973 - Issue 3, pp 32-57
- ↑ | Нейский И.М. Классификация и сравнение методов кластеризации.// Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. – М.: НОК «CLAIM», 2006. – Выпуск 8. – С. 130-142.
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.