Участник:Nikmedoed/Нечеткий алгоритм С-средних (Fuzzy C-means)

Нечеткий алгоритм С-средних (Fuzzy C-means)
Последовательный алгоритм
Последовательная сложность	[math]O(c^2 MI + cMnI), (I[/math] - число итераций[math])[/math]
Объём входных данных	[math] O(c^2 I + cnI)[/math]
Объём выходных данных	[math]O( M )[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]Mn[/math]
Ширина ярусно-параллельной формы	[math]cM[/math]

Выполняют: Н.А. Муромцев, М.С. Дворецкий

Нечеткий алгоритм С-средних (Fuzzy C-means) - позволяет получить нечёткую кластеризация больших наборов числовых данных, что позволяет определять объекты на границе кластеров в отдельные кластеры. Однако, выполнение данного алгоритма требует серьёзных вычислительных ресурсов, а также изначального задания количества кластеров. Кроме того, может возникнуть неоднозначность с объектами удалёнными от центров всех кластеров.

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм кластеризации Fuzzy C-Means (FCM) был предложен Дж. Данном в 1973 году и доработан Дж. Бездеком в 1981 году . В отличие от большинства существующих алгоритмов кластеризации, данный алгоритм является нечётким – каждый из объектов не входит однозначно в какой-либо кластер, а принадлежит всем кластерам с различными степенями принадлежности. Это даёт преимущества в качестве разбиения в случаях, когда кластеры находятся близко друг к другу, и большое число точек находится на их границах. Однако ценой такой нечёткости служат большие вычислительные затраты, чем у таких чётких алгоритмов, как 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] между объектами и центрами кластеров.

Формулы метода:

[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}\\ &D_{ki}=\sqrt{{\lVert X_k - V_i \rVert}^2},k=\overline{1,M},i=\overline{1,c}\\ &\mu_{ki}=\frac{1}{{\left ( \sum^{c}_{j=1} {\frac{D_{ki}}{D_{kj}}} \right ) }^{{2}/{m-1}} },k=\overline{1,M},i=\overline{1,c}\\ \end{align} [/math]

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма Fuzzy C-Means составляют шаги вычисления центров кластеров и расстояний между ними и точками данных, которые требуют порядка [math]cMn[/math] операций умножения за итерацию. Также, шаги вычисления центров кластеров и пересчёта матрицы принадлежности требуют по [math]cM[/math] операций возведения в степень, что может быть более затратно при малых [math]n[/math].

Такое число операций возведения в степень достигается за счёт устранения некоторых повторных вычислений. Так, для шага вычисления центров кластеров величины [math]\mu_{ki}^m[/math] могут вычисляться однократно и умножаться на [math]X_k[/math] при включении в сумму, записанную в числителе.

1.4 Макроструктура алгоритма

Алгоритм включает в себя три основных этапа – вычисление центров кластеров, вычисление расстояний между центрами кластеров и точками данных (включающее в себя макрооперации вычитания векторов и вычисления их норм, как правило в Евклидовом пространстве) и пересчёт матрицы принадлежности.

1.5 Схема реализации последовательного алгоритма

Последовательность исполнения алгоритма следующая:

Инициализация происходит случайным заполнением матрицы принадлежности [math]F[/math] с соблюдением условия нормировки [math]\sum_{i=1}^c {\mu_{ki} =1}[/math] и переходом к шагу 1, либо случайным определением центров кластеров [math]V_i[/math] и переходом к шагу 2.

Далее осуществляются итерации следующего вида:

1. [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]
2. [math]D_{ki}=\sqrt{{\lVert X_k - V_i \rVert}^2},k=\overline{1,M},i=\overline{1,c}[/math]
3. [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]cM(n+1)-2c-M[/math] сложений,
• [math]cMn[/math] вычитаний,
• [math]cM(2n+1)[/math] умножений,
• [math]c(M+1)[/math] делений,
• [math]2cM[/math] возведений в степень,
• [math]cM[/math] вычислений квадратного корня.

Если считать [math]n[/math] малым, то в основную часть алгоритма входят все вышеперечисленные операции, в противном случае – операции сложения, вычитания и умножения. Вычислительная сложность одной итерации алгоритма Fuzzy C-Means – [math]O(cMn)[/math].

1.7 Информационный граф

Приведём граф единичной итерации алгоритма в параллельном оптимизированном варианте:

Каждая вершина данного графа соответствует операциям из алгоритма, указанным при помощи указанных формул. Каждый из p столбцов соответствует работе одного из процессов. Пометки справа указывают число повторений каждого узла в ходе одной итерации.

Раздел 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 может быть разделено на следующие ярусы:

• c ярусов нахождения частичных сумм знаменателя (по [math]\frac{M}{p}-1[/math] сложений, [math]\frac{M}{p}[/math] операций возведения в степень на процесс),
• c ярусов нахождения частичных сумм числителя (по [math]\frac{M}{p} -1[/math] сложений, [math]\frac{M}{p}[/math] умножений на процесс),
• c редукций сумм и передач значений [math]V_i[/math] процессам,
• c ярусов вычисления расстояний до центров (по [math]n-1[/math] сложений, [math]n[/math] вычитаний, [math]n[/math] умножений, 1 взятие квадратного корня), каждый процесс получает[math]\frac{M}{p}[/math] точек на обработку,
• 1 ярус вычислений нормировочных сумм (по [math]c-1[/math] сложений, c делений), каждый процесс получает [math]\frac{M}{p}[/math] точек на обработку,
• c ярусов вычисления степеней принадлежности точек (по 1 умножению, 1 делению, 1 возведению в степень), каждый процесс получает [math]\frac{M}{p}[/math] точек на обработку.

Таким образом, в параллельном варианте при условии наличия в каждом узле достаточного объёма памяти для хранения всего массива координат центров кластеров высота и ширина ЯПФ алгоритма FCM равны соответственно [math]O(c)[/math] и [math]O(Mn)[/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]Mn[/math] (на практике величина [math]n[/math] считается малой и не учитывается).

Параметр [math]m[/math] задаёт степень «размытости» кластеров. В отсутствие априорных данных его обычно берут равным 2. В предельном случае сведения параметра [math]m[/math] к значению 1, кластеры становятся чёткими и алгоритм вырождается в алгоритм кластеризации K-Means.

Алгоритм недетерминирован, начальное положение кластеров задаётся случайно либо явно, либо опосредованно (через матрицу принадлежности). Алгоритм сходится к локальному экстремуму и, таким образом, не гарантирует оптимальный результат при случайном выборе начальных значений.