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

Данный документ содержит описание схемы, по которой предлагается описывать свойства и структуру каждого алгоритма. Описание состоит из двух частей. В первой части описываются собственно алгоритмы и их свойства, а вторая посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.

Общая схема описания алгоритмов имеет следующий вид:

1 ЧАСТЬ. Свойства и структура алгоритмов

Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты части II AlgoWiki, здесь также вполне уместны.

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] при включении в сумму, записанную в числителе.

На шаге пересчёта матрицы принадлежности нормировочная сумма [math]\sum^c_{j=1}\frac{1}{D_{kj}}[/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}{{\left ( \sum^{c}_{j=1} {\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.

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

2 ЧАСТЬ. Программная реализация алгоритма

Вторая часть описания алгоритмов в рамках AlgoWiki рассматривает все составные части процесса их реализации. Рассматривается как последовательная реализация алгоритма, так и параллельная. Описывается взаимосвязь свойств программ, реализующих алгоритм, и особенностей архитектуры компьютера, на которой они выполняются. Исследуется работа с памятью, локальность данных и вычислений, описывается масштабируемость и эффективность параллельных программ, производительность компьютеров, достигаемая на данной программе. Обсуждаются особенности реализации для разных классов архитектур компьютеров, приводятся ссылки на реализации в существующих библиотеках.

2.1 Особенности реализации последовательного алгоритма

Здесь описываются особенности и варианты реализации алгоритма в виде последовательной программы, которые влияют на эффективность ее выполнения. В частности, в данном разделе имеет смысл сказать о существовании блочных вариантов реализации алгоритма, дополнительно описав потенциальные преимущества или недостатки, сопровождающие такую реализацию. Важный вопрос - это возможные варианты организации работы с данными, варианты структур данных, наборов временных массивов и другие подобные вопросы. Для различных вариантов реализации следует оценить доступный ресурс параллелизма и объем требуемой памяти.

Важным нюансом является описание необходимой разрядности выполнения операций алгоритма (точности). На практике часто нет никакой необходимости выполнять все арифметические операции над вещественными числами с двойной точностью, т.к. это не влияет ни на устойчивость алгоритма, ни на точность получаемого результата. В таком случае, если значительную часть операций можно выполнять над типом float, и лишь в некоторых фрагментах необходим переход к типу double, это обязательно нужно отметить. Это прямое указание не только на правильную реализацию с точки зрения устойчивости по отношению к ошибкам округления, но и на более эффективную.

Опираясь на информацию из п.1.8 (описание ресурса параллелизма алгоритма), при описании последовательной версии стоит сказать про возможности эквивалентного преобразования программ, реализующих данных алгоритм. В дальнейшем, это даст возможность простого использования доступного параллелизма или же просто покажет, как использовать присущий алгоритму параллелизм на практике. Например, параллелизм на уровне итераций самого внутреннего цикла обычно используется для векторизации. Однако, в некоторых случаях этот параллелизм можно поднять "вверх" по структуре вложенности объемлющих циклов, что делает возможной и эффективную реализацию данного алгоритма на многоядерных SMP-компьютерах.

С этой же точки зрения, в данном разделе весьма полезны соображения по реализации алгоритма на различных параллельных вычислительных платформах. Высокопроизводительные кластеры, многоядерные узлы, возможности для векторизации или использования ускорителей - особенности этих архитектур не только опираются на разные свойства алгоритмов, но и по-разному должны быть выражены в программах, что также желательно описать в данном разделе.

2.2 Локальность данных и вычислений

Вопросы локальности данных и вычислений не часто изучаются на практике, но именно локальность определяет эффективность выполнения программ на современных вычислительных платформах [2, 3]. В данном разделе приводятся оценки степени локальности данных и вычислений в программе, причем рассматривается как временна́я, так и пространственная локальность. Отмечаются позитивные и негативные факты, связанные с локальностью, какие ситуации и при каких условиях могут возникать. Исследуется, как меняется локальность при переходе от последовательной реализации к параллельной. Выделяются ключевые шаблоны взаимодействия программы, реализующей описываемый алгоритм, с памятью. Отмечается возможная взаимосвязь между используемыми конструкциями языков программирования и степенью локальности, которыми обладают результирующие программы.

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

На рис.3 и рис.4 показаны профили обращения в память для программ, реализующих разложение Холецкого и быстрое преобразование Фурье, по которым хорошо видна разница свойств локальности у данных алгоритмов.

Рис.3 Реализация метода Холецкого. Общий профиль обращений в память

Рис.4 Нерекурсивная реализация БПФ для степеней двойки. Общий профиль обращений в память

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

• представленный иерархически ресурс параллелизма, опирающийся на структуру циклических конструкций и на граф вызовов программы;
• комбинацию (иерархию) массового параллелизма и параллелизма конечного;
• возможные способы распределения операций между процессами/нитями;
• возможные способы распределения данных;
• оценку количества операций, объёма и числа пересылок данных (как общего числа, так и в пересчёте на каждый параллельный процесс);

и другие.

В этом же разделе должны быть даны рекомендации или сделаны комментарии относительно реализации алгоритма с помощью различных технологий параллельного программирования: MPI, OpenMP, CUDA или использования директив векторизации.

2.4 Масштабируемость алгоритма и его реализации

Задача данного раздела - показать пределы масштабируемости алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование сильной и слабой масштабируемости алгоритма и его реализаций.

Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).

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

На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.

Рис.5 Масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи

2.5 Динамические характеристики и эффективность реализации алгоритма

Это объемный раздел AlgoWiki, поскольку оценка эффективности реализации алгоритма требует комплексного подхода [5], предполагающего аккуратный анализ всех этапов от архитектуры компьютера до самого алгоритма. Основная задача данного раздела заключается в том, чтобы оценить степень эффективности параллельных программ, реализующих данный алгоритм на различных платформах, в зависимости от числа процессоров и размера задачи. Эффективность в данном разделе понимается широко: это и эффективность распараллеливания программы, это и эффективность реализации программ по отношению к пиковым показателям работы вычислительных систем.

Помимо собственно показателей эффективности, нужно описать и все основные причины, из-за которых эффективность работы параллельной программы на конкретной вычислительной платформе не удается сделать выше. Это не самая простая задача, поскольку на данный момент нет общепринятой методики и соответствующего инструментария, с помощью которых подобный анализ можно было бы провести. Требуется оценить и описать эффективность работы с памятью (особенности профиля взаимодействия программы с памятью), эффективность использования заложенного в алгоритм ресурса параллелизма, эффективность использования коммуникационной сети (особенности коммуникационного профиля), эффективность операций ввода/вывода и т.п. Иногда достаточно интегральных характеристик по работе программы, в некоторых случаях полезно показать данные мониторинга нижнего уровня, например, по загрузке процессора, кэш-промахам, интенсивности использования сети Infiniband и т.п. Хорошее представление о работе параллельной MPI-программы дают данные трассировки, полученные, например, с помощью системы Scalasca.

2.6 Выводы для классов архитектур

В данный раздел должны быть включены рекомендации по реализации алгоритма для разных классов архитектур. Если архитектура какого-либо компьютера или платформы обладает специфическими особенностями, влияющими на эффективность реализации, то это здесь нужно отметить.

На практике это сделать можно по-разному: либо все свести в один текущий раздел, либо же соответствующие факты сразу включать в предшествующие разделы, где они обсуждаются и необходимы по смыслу. В некоторых случаях, имеет смысл делать отдельные варианты всей части II AlgoWiki применительно к отдельным классам архитектур, оставляя общей машинно-независимую часть I. В любом случае, важно указать и позитивные, и негативные факты по отношению к конкретным классам. Можно говорить о возможных вариантах оптимизации или даже о "трюках" в написании программ, ориентированных на целевые классы архитектур.

2.7 Существующие реализации алгоритма

Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.