Участник:Nikmedoed/Нечеткий алгоритм С-средних (Fuzzy C-means)
![]() | Эта работа прошла предварительную проверку Дата последней правки страницы: 06.11.2016 Данная работа соответствует формальным критериям. Проверено Coctic. |
Нечеткий алгоритм С-средних (Fuzzy C-means) | |
Последовательный алгоритм | |
Последовательная сложность | [math]O(c^2 MI + cMnI), (I[/math] - число итераций, [math]c[/math] - количество кластеров, [math]M[/math] - число точек, [math]n[/math] - размерность точек (свойств на объект)[math])[/math] |
Объём входных данных | [math]Mn[/math] |
Объём выходных данных | [math]cM[/math] |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | [math] O(c^2 I + cnI)[/math] |
Ширина ярусно-параллельной формы | [math]O( M )[/math] |
Авторы: Н.А. Муромцев - перенос в вики, раздел 2, картинки, М.С. Дворецкий - раздел 1
Нечеткий алгоритм С-средних (Fuzzy C-means) - позволяет получить нечёткую кластеризацию больших наборов числовых данных, что позволяет корректно определять объекты на границах кластеров. Однако, выполнение данного алгоритма требует серьёзных вычислительных ресурсов, а также изначального задания количества кластеров. Кроме того, может возникнуть неоднозначность с объектами, удалёнными от центров всех кластеров.
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Алгоритм кластеризации Fuzzy C-Means (FCM) был предложен Дж. Данном в 1973 году [1] и доработан Дж. Бездеком в 1981 году [2]. В отличие от большинства существующих алгоритмов кластеризации, данный алгоритм является нечётким – каждый из объектов не входит однозначно в какой-либо кластер, а принадлежит всем кластерам с различными степенями принадлежности. Это даёт преимущества в качестве разбиения в случаях, когда кластеры находятся близко друг к другу, и большое число точек находится на их границах. Однако ценой такой нечёткости служат большие вычислительные затраты, чем у таких чётких алгоритмов, как Hard C-Means и K-Means, при сохранении таких их недостатков, как априорное определение числа кластеров и отсутствие гарантии глобальной оптимальности результата.
1.2 Математическое описание алгоритма
Исходные данные: массив объектов [math]{X_k}\in{\R^n}, k=\overline{1,M}[/math], число кластеров c, экспоненциальный вес [math]m\in{[1,\infty)}[/math], параметр останова [math]\varepsilon\gt 0[/math].
Вычисляемые данные: матрица разбиения [math]F[/math] размера [math]M\times c[/math] (элементы [math]\mu_{ki}\in[0,1][/math], [math]\sum^{c}_{i=1} {\mu_{ki}} = 1[/math]), центры кластеров [math]V_i[/math], расстояния [math]D_{ki}[/math] между объектами и центрами кластеров.
Формулы метода (вычисляются последовательно на каждой итерации):
1. Уточнение центров кластеров по степеням принадлежности
- [math] \begin{align} &V_i=\frac{\sum^{M}_{k=1} {\mu^m_{ki} * X_k}}{\sum^{M}_{k=1} {\mu^m_{ki}}},i=\overline{1,c} \end{align} [/math]
2. Расчёт расстояний между новыми центрами кластеров и точками данных
- [math] \begin{align} &D_{ki}=\sqrt{{\lVert X_k - V_i \rVert}^2},k=\overline{1,M},i=\overline{1,c} \end{align} [/math]
3. Пересчёт степеней принадлежности объектов кластерам
- [math] \begin{align} &\mu_{ki}=\frac{1}{{ \sum^{c}_{j=1} \left ( {\frac{D_{ki}}{D_{kj}}} \right ) }^{{2}/{m-1}} },k=\overline{1,M},i=\overline{1,c}\\ \end{align} [/math]
На каждой итерации алгоритма происходит уточнение элементов матрицы [math]F[/math]. Выходом алгоритма служит матрица [math]F[/math], к которой алгоритм сходится. Факт того, что алгоритм сошёлся, устанавливается проверкой вида [math]\max_{k = \overline{1,M},i = \overline{1,c}} {( \left | \mu_{ki} - \mu_{ki}^* \right |)} \lt \varepsilon[/math] либо [math]\max_{i = \overline{1,c}} {( \left | V_i - V_i^* \right |)} \lt \varepsilon[/math], где [math]\mu_{ki}^* (V_i^*)[/math] – значение [math]\mu_{ki}(V_i)[/math], вычисленное на предыдущей итерации.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро алгоритма Fuzzy C-Means составляют шаги вычисления центров кластеров, расстояний между ними и точками данных и в особенности пересчёта матрицы степеней принадлежности точек данных.
При реальном вычислении некоторые повторяющиеся вычисления могут быть устранены. Так, для шага вычисления центров кластеров величины [math]\mu_{ki}^m[/math] могут вычисляться однократно и умножаться на [math]X_k[/math] при включении в сумму, записанную в числителе. Для шага вычисления расстояний между центрами кластеров и точками, операция взятия квадратного корня не является обязательной, так как в дальнейшем на шаге вычисления степеней принадлежности можно непосредственно использовать квадраты этих расстояний, и сумма в знаменателе будет приобретать вид:
[math]\sum^{c}_{j=1} {\left ( \frac{D_{ki} ^ {2}}{D_{kj} ^ {2}} \right )}^{{1}/{m-1}}[/math]
1.4 Макроструктура алгоритма
Алгоритм включает в себя три основных этапа – вычисление центров кластеров, вычисление расстояний между центрами кластеров и точками данных (включающее в себя макрооперации вычитания векторов и вычисления их норм, как правило в Евклидовом пространстве) и пересчёт матрицы принадлежности.
1.5 Схема реализации последовательного алгоритма
Последовательность исполнения алгоритма следующая:
Инициализация происходит случайным заполнением матрицы принадлежности [math]F[/math] с соблюдением условия нормировки [math]\sum_{i=1}^c {\mu_{ki} =1}[/math] и переходом к шагу 1, либо случайным определением центров кластеров [math]V_i[/math] и переходом к шагу 2.
Далее осуществляются итерации следующего вида:
- [math]V_i=\frac{\sum_{k=1}^{M} {\mu_{ki}^m * X_k}}{\sum_{k=1}^{M} {\mu_{ki}^m} },i=\overline{1,c}[/math]
- [math]D_{ki}=\sqrt{{\lVert X_k - V_i \rVert}^2},k=\overline{1,M},i=\overline{1,c}[/math]
- [math]\mu_{ki}=\frac{1}{{ \sum^{c}_{j=1} {\left ( \frac{D_{ki}}{D_{kj}} \right )} }^{{2}/{m-1}} },k=\overline{1,M},i=\overline{1,c}[/math]
В конце каждой итерации проверяется условие останова вида [math]\max_{k = \overline{1,M},i = \overline{1,c}} {( \left | \mu_{ki} - \mu_{ki}^* \right |)} \lt \varepsilon[/math], либо [math]\max_{i = \overline{1,c}} {( \left | V_i - V_i^* \right |)} \lt \varepsilon[/math], где [math]\mu_{ki}^* (V_i^*)[/math] – значение [math]\mu_{ki}(V_i)[/math], вычисленное на предыдущей итерации. Если условие не выполнено, осуществляется переход к шагу 1.
1.6 Последовательная сложность алгоритма
При кластеризации [math]M[/math] объектов данных, представленных точками в [math]\R^n[/math], на [math]c[/math] кластеров, алгоритм Fuzzy C-Means в последовательном варианте имеет вычислительную сложность – [math]O(c^2 MI+cMnI)[/math], где [math]I[/math] – число итераций. Если считать размерность данных [math]n[/math] малой, то эта сложность сводится к [math]O(c^2 MI)[/math]. Основной частью алгоритма в этом случае является пересчёт матрицы принадлежностей, требующий вычисления [math]cM[/math] сумм из [math]c[/math] слагаемых на каждой итерации.
1.7 Информационный граф
Приведём граф единичной итерации алгоритма в параллельном оптимизированном варианте (метод распараллеливания взят в [3]):
Раздел 1.8 уточняет, соответствуют ли эти повторения однотипным ярусам или точкам данных, вычисления для которых можно распараллелить и далее.
Каждый процесс обладает следующими данными:
- координатами точек данных [math]X_k[/math], [math]k=\overline{1+rnk* \frac{M}{p},rnk*(\frac{M}{p}+1)}[/math], где [math]rnk[/math] – номер процесса,
- значениями [math]\mu_{ki}[/math] степени принадлежности для своих точек ([math]k=\overline{1+rnk* \frac{M}{p},rnk*(\frac{M}{p} +1)}, i=\overline{1,c}[/math]),
- координатами центров кластеров [math]V_i[/math], [math]i=\overline{1,c}[/math].
Суммы [math]\sum_{k=1+rnk*\frac{M}{p}}^{rnk * ( \frac{M}{p} +1 )} {\mu_{ki}^m}[/math] и [math]\sum_{k=1+rnk*\frac{M}{p}}^{rnk * ( \frac{M}{p} +1 )} {\mu_{ki}^m X_k}[/math] вычисляются одновременно, поэтому значения [math]\mu_{ki}^m[/math] вычисляются по одному разу за итерацию. Таким образом, второй ярус операций на рисунке на деле не содержит операций возведения в степень. За счёт линейности большинства выражений относительно данных по точкам, процессы взаимодействуют только при редукции сумм, составляющих [math]V_i[/math]. Всё остальное время каждый процессор работает только со своими [math]\frac{M}{p}[/math] точками. Это обеспечивает применимость алгоритма для больших [math]M[/math].
1.8 Ресурс параллелизма алгоритма
При распараллеливании по точкам исходных данных и условии останову по малому изменению степеней принадлежности выполнение одной итерации алгоритма FCM может быть разделено на следующие ярусы:
- [math]c[/math] ярусов нахождения частичных сумм знаменателя (по [math]\frac{M}{p}-1[/math] сложений, [math]\frac{M}{p}[/math] операций возведения в степень на процесс),
- [math]c[/math] ярусов нахождения частичных сумм числителя (по [math]\frac{M}{p} -1[/math] сложений, [math]\frac{M}{p}[/math] умножений на процесс),
- [math]2[/math] редукции сумм и передач значений [math]V_i[/math] процессам (получение [math]c(n+1)[/math] значений, [math]cn[/math] делений),
- [math]c[/math] ярусов вычисления расстояний до центров (по [math]n-1[/math] сложений, [math]n[/math] вычитаний, [math]n[/math] умножений), каждый процесс получает [math]\frac{M}{p}[/math] точек на обработку,
- [math]c[/math] ярусов вычисления степеней принадлежности точек (по [math]c+1[/math] делений, c возведений в степень, [math]c-1[/math] сложений), каждый процесс получает [math]\frac{M}{p}[/math] точек на обработку,
- до [math]c[/math] ярусов проверки условий останова (по [math]1[/math] вычитанию, [math]1[/math] сравнению), каждый процесс получает [math]\frac{M}{p}[/math] точек на обработку,
- [math]1[/math] редукция для обмена статусом завершения.
Таким образом, при распараллеливании по точкам исходных данных при условии наличия в каждом узле достаточного объёма памяти для хранения всего массива координат центров кластеров высота и ширина ЯПФ алгоритма FCM равны соответственно [math]O(c^2 I+cnI)[/math] и [math]O(M)[/math].
1.9 Входные и выходные данные алгоритма
Входные данные: массив векторов [math]X_i[/math], число кластеров [math]c[/math], экспоненциальный вес [math]m\in{[1,\infty)}[/math], параметр останова [math]\varepsilon\gt 0[/math].
Объём входных данных: [math]Mn[/math] для входных векторов, 3 вспомогательных параметра.
Выходные данные: матрица принадлежности [math]F[/math] (элементы [math]\mu_{ki}\in[0,1][/math]). Условие нормировки: [math]\sum^{c}_{i=1} {\mu_{ki}} = 1[/math].
Объём выходных данных: [math]cM[/math].
1.10 Свойства алгоритма
В случае неограниченного распараллеливания по точкам данных (1 процесс на точку), отношение последовательной сложности алгоритма к параллельной пропорционально [math]M[/math].
Параметр [math]m[/math] задаёт степень «размытости» кластеров. В отсутствие априорных данных его обычно берут равным 2. В предельном случае сведения параметра [math]m[/math] к значению 1, кластеры становятся чёткими и алгоритм вырождается в алгоритм кластеризации K-Means.
Алгоритм недетерминирован, начальное положение кластеров задаётся случайно либо явно, либо опосредованно (через матрицу принадлежности). Алгоритм сходится к локальному экстремуму [4] и, таким образом, не гарантирует оптимальный результат при случайном выборе начальных значений.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Исследование проведено на суперкомпьютере IBM Blue Gene/P[5]. Для исследования была использована последовательная реализация алгоритма и реализован её параллельный вариант[6].
Для упрощения экспериментов было решено использовать количество вершин для кластеризации и количество процессов равное степени двойки, поэтому для каждого эксперимента были выбраны значения:
- [math]2^n, n=\overline{0,9}[/math], для количества процессоров;
- [math]2^w, w=\overline{10,20}[/math], для количества кластеризуемых вершин.
Для одного набора значений проводилось 4 эксперимента и результаты усреднялись. При повторных запусках экспериментов значения выходили те же самые.
В результате был получен вывод, что алгоритм очень хорошо масштабируется, показывая ожидаемое поведение при малом количестве вершин и большом количестве процессоров (много времени тратится на передачу), а также не теряя эффективности и почти линейно снижая время выполнения при росте числа процессоров. Начиная с 32768 вершин и до 16 процессоров реализация алгоритма показала эффективность почти в 100±2%. При количестве вершин меньше 32768 и количестве процессоров больше 16 эффективность начинает значительно падать.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
3 Литература
- ↑ Dunn, J.C.: A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters. Journal of Cybernetics. 3 (1973): 32–57
- ↑ Bezdek, J.C.: Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York (1981). ISBN 0-306-40671-3
- ↑ Kwok, T., Smith, K., Lozano, S., Taniar, D.: Parallel Fuzzy c-Means Clustering for Large Data Sets, последнее обращение 25.10.2016
- ↑ Höppner, F., Klawonn, F.: wolfenbuettel.de/~klawonn/Papers/hoeppnerklawonntfs03.pdf A Contribution to Convergence Theory of Fuzzy c-Means and Derivatives, Дата последнего обращения: 13.10.2016
- ↑ Описание вычислительного комплекса IBM Blue Gene/P
- ↑ Параллельная реализация алгоритма Fuzzy C-Means
- ↑ Документация пакета MATLAB, функция fcm, последнее обращение 15.10.2016
- ↑ Реализация алгоритма Fuzzy C-means на POSTGRESQL, последнее обращение 15.10.2016