Нечеткий алгоритм C средних
Последовательный алгоритм
Последовательная сложность	$O(CCK*I)$ ., где $I$ - количество итераций
Объём входных данных	$KN$ , [количество векторов размерность]
Объём выходных данных	$C*K$ , [элементы матрицы принадлежности]
Параллельный алгоритм
Высота ярусно-параллельной формы	$3I$
Ширина ярусно-параллельной формы	$CCK$

Авторы : Мария Проценко (1.5-1.8, 2.7), Андрей Довганич (1.1-1.4, 1.9, 1.10)

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

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

Нечеткий алгоритм C-средних (fuzzy C-means) позволяет разбить имеющееся множество векторов (точек) мощностью $K$ на заданное число нечетких множеств. Предназначен для кластеризации больших наборов данных. Основным достоинством алгоритма является нечеткость при определении объекта в кластер. Благодаря этому становится возможным определить объекты, которые находятся на границе, в кластеры. Из основного достоинства следует и главный недостаток - неопределенность с объектами, удаленными от центров всех кластеров. В остальном ему присущи стандартные проблемы подобного класса алгоритмов: вычислительная сложность, необходимость задания количества кластеров^[1].

Алгоритм был разработан J.C. Dunn в 1973 г.^[2], усовершенствован J.C. Bezdek в 1981 г.^[3].

На вход алгоритм получает некоторое множество входных векторов и случайную матрицу их принадлежности к каждому из кластеров. На выходе с заданной точностью получаем матрицу принадлежности.

В общем виде алгоритм можно записать следующим образом:

Инициализировать матрицу принадлежности;
Вычислить центры кластеров;
Вычислить значение решающей функции. Если значение ниже некоторого порогового или его улучшение по сравнению с предыдущей итерацией меньше определенной величины, то остановить вычисления;
Иначе вычислить новые значения матрицы принадлежности;
Перейти к шагу 2

1.2 Математическое описание алгоритма

Рассмотрим матрицу $M = m_{ik} \in[0,1],\; i = 1, ..., c, \; k = 1, ..., K$ . $m_{i,k}$ - вероятность принадлежности объекта $k$ к кластеру $i$ ; $c$ - количество кластеров, $K$ - количество векторов. При этом элементы матрицы удовлетворяют следующим условиям:

сумма элементов в каждом столбце равна $1$ ;

сумма всех элементов матрицы равно $K$ ;

Назовем $M$ матрицей принадлежности.

Пусть $c_{i} (i = 1,2,...c)$ - центры кластеров. Тогда рассмотрим функцию

$\begin{align} J(M, c_{1}, c_{2},...c_{c}) = \sum_{i = 1}^{c}{J_{i}} = \sum_{i = 1}^{c}\sum_{k = 1}^{K}{m_{ik}^q}d_{ik}^2 ~(1) \end{align}$

где $d_{ik} = \left\Vert{u_{k}-c_{i}}\right\|$ - Евклидово расстояние между центром кластера и объектом, $1 \le q \le \infty$ - экспоненциальный весовой коэффициент, характеризующий нечеткость. Будем минимизировать значение функции $J$ . Для этого вычислим центры кластеров по формуле $~(2)$ .

$c_{i} = {{\sum_{k = 1}^{K}{m_{ik}^q} * u_{k}} \over {\sum_{k = 1}^{K}{m_{ik}^q}}}~(2)$

где $m_{ik}$ — коэффициент принадлежности $u_{k}$ вектора к кластеру $c_{i}$

и новые значения матрицы $M$ по формуле $~(3)$

$m_{ik} = {1 \over \sum_{j = 1}^{c}{({{d_{ik}} \over {d_{jk}}})}^{2 \over q-1}} ~(3)$

$~(2)$ и $~(3)$ являются необходимым условиями достижения минимума функцией $J$ . Таким образом эти два условия дают нам итерационный процесс.

Полностью алгоритм можно записать следующим образом:

Инициализировать матрицу принадлежности $M$ случайными значениями от 0 до 1;
Вычислить центры кластеров $c_{i} (i = 1,2,...c)$ используя формулу $~(2)$ ;
Вычислить значение решающей функции по формуле $~(1)$ . Если значение $J \lt \varepsilon,~\varepsilon \gt 0$ или $|J_{i} - J_{i-1}| \lt \delta,~\delta \gt 0$ , то остановить вычисления;
Иначе вычислить новые значения матрицы М по формуле $~(3)$ ;
Перейти к шагу 2

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

Вычислительным ядром алгоритма являются формулы: $(1)$ , $(2)$ , $(3)$ . В них производится вычисление новых центров кластеров, значения решающей функции и пересчет элементов матрицы принадлежности.

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

Макроструктура алгоритма состоит из следующих шагов:

Инициализация матрицы $M$ случайными значениями от 0 до 1;
Вычисление центров кластеров;
Вычисление значения решающей функции(если оно удовлетворяет условиям останова - завершение вычислений);
Вычисление новых элементов матрицы принадлежности;
Переход к шагу 2;

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

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

    float ** m;
    int *c;
    int number_clusters, number_items;
    m = gen_random_clusters();//заполним матрицу m случайными значениями от 0 до 1
    
    while (true)
    {
      //вычисление центров кластеров
        for (int i=0; i<number_clusters; i++)
        {
            numerator==denumerator=0;
            for (int k=0; k<number_items; k++)
            {
                numerator+=pow(m[i, k], q)*u[k];//u[k]-вектор
                denumerator+=pow(m[i, k], q);
            }
        c[i]= numerator / denumerator;//центры кластеров
        }
    
        j=0;//вычисление решающей функции
        for (int i=0; i<number_clusters; i++)
            for (int k=0; k<number_items; k++)
                j+=pow(m[i, k], q)*pow(dist(c[i], x[k],2);//dist-вычисляет расстояние между заданными векторами
    
       if ((abs(j-last_j)<delta) || (j<eps)) break;//проверка на необходимость завернешения алгоритма
       last_j=j;
     //обновление матрицы m
       for (int i=0; i<number_clusters; i++)
          for (int k=0; k<number_items; k++)
             {
               m[i,k]=0
              for(int j=0; j<number_clusters; j++)
                  m[i,k]+=pow(dist(c[i], x[k])/dist(c[j], x[k]),2/(q-1));
              m[i,k]=1/m[i,k];
              }
                                       
    }

1.6 Последовательная сложность алгоритма

Каждая итерация включает в себя

Вычисление центров кластеров $O(C*K)$
Вычисление решающей функции $O(C*K)$
Обновлене матрицы $M$ $O(C*C*K)$

Общая сложность каждой итерации $O(C*C*K)$ .

Сложность всего алгоритма будет зависеть от числа итераций, которое зависит от

Выбора начального приближения
Выбора условий останова

Окончательно, сложность алгоритма будет равна произведению количества итераций на их сложность

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

Первый ярус состоит из $C$ параллельных операций, каждая их которых в свою очередь состоит из $K$ параллельных операций, и одной, которая выполняется с использованием результата предыдущих. Результатом работы этого яруса являются значения центров кластеров , которые будут использоваться на следующем ярусе.

Второй ярус содержит в себе $C*K$ параллельных операций. Результатом его работы является значение решающей функции $J$ . Её значение определяет необходимость завершения алгоритма.

Третий ярус включает $C*K$ параллельных операций, каждая из которых состоит из $C$ параллельных операций, и одной, которая выполняется с использованием результата предыдущих.

Информационный граф алгоритма. Салатовым цветом обозначены вершины графа-операции. Дугами обозначена передача информации, передаваемые данные надписаны сверху.

1.8 Ресурс параллелизма алгоритма

На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет $O(\log_{2} C)$ . Для каждого элемента из набора входных данных( $K$ ), но здесь возможен независимый расчет(координатный параллелизм). На втором шаге(вычисление решающей функции) сложность будет $O(\log_{2} {C*K})$ , потому что здесь необходимо сложение всех элементов. На третьем шаге имеем сложность $O(\log_{2} C^2)$ . Итого суммарная сложность итерации: $O(\log_{2} {C*K} + \log_{2} C^3)$ . Воспользовавшись свойствами логарифма произведения получаем: $O(\log_{2} {K} + \log_{2} C^4)$ .

Скошенного параллелизма в алгоритме нет.

1.9 Входные и выходные данные алгоритма

Входные данные:

$u_{k} ~k = 1, ..., K$ - набор входных векторов размерности $N$ ;
$C$ - количество кластеров;
$q$ - экспоненциальный весовой коэффициент, характеризующий нечеткость;
$\varepsilon \gt 0, ~\delta \gt 0$ - коэффициенты, описывающие точность алгоритма.

Объем входных данных: $K*N$

Выходные данные:

$M$ - матрица принадлежности.

Объем выходных данных: $C*K$

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности алгоритма: $C*C*K \over {\log_{2} {K} + \log_{2} C^4}$ . Соответственно при распараллеливании наибольший прирост в производительности мы получим при разбиении большого набора данных на большее число кластеров;
Вычислительная мощность: ${{C^2*K} \over {C*K}} = C$ . Получается, что на чем большее количество кластеров мы разбиваем набор данных, тем менее затратным становится перемещение данных;
Алгоритм не является устойчивым, как и другие подобные алгоритмы этого класса(например k-means). Очень многое зависит как от входных данных, так и от изначальных параметров приближения(заполнения матрицы принадлежности => исходных центров кластеров);
Не является детерминированным. Так же очень многое зависит как от входных данных, так и от изначальных параметров приближения(заполнения матрицы принадлежности => исходных центров кластеров);
Алгоритм не сбалансирован - доминирует операция умножения. Параллельные ветви алгоритма сбалансированы;
Степень исхода вершины информационного графа - 2.

2 Программная реализация алгоритма

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

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

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

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

Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов"^[4] Суперкомпьютерного комплекса Московского университета.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

число процессоров [1 : 120];
размер входных данных [1 : 15 000] векторов размерности 4.

При количестве кластеров 100.

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

минимальная эффективность реализации 0,63%;
максимальная эффективность реализации 2,56%.

В параллельной реализации использовалась технология OpenMP. Компилятор GNU(gcc) с флагом -fopenmp. Версия компилятора: gcc version 4.4.7 20120313 (Red Hat 4.4.7-4) (GCC).

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

Изменение производительности.

Изменение эффективности.

Оценки масштабируемости:

По числу процессов: 0.1245.
По размеру задачи: -0.0278.
По двум направлениям: 0,00009.

Параллельная реализация на языке С с использованием Open MP

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

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

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

Можно найти следующие реализации алгоритма

Для MATLAB http://www.mathworks.com/help/fuzzy/fcm.html
В PostgreSQL http://num-meth.srcc.msu.ru/zhurnal/tom_2012/v13r207.html

Так же готовые реализации алгоритма и его описание можно найти на сайтах

3 Литература

↑ Нейский И.М. Классификация и сравнение методов кластеризации
↑ Dunn, J. C. (1973-01-01). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics. 3 (3): 32–57. doi:10.1080/01969727308546046. ISSN 0022-0280.
↑ Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. ISBN 0-306-40671-3.
↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.

[1] Нейский И.М. Классификация и сравнение методов кластеризации

[2] Dunn, J. C. (1973-01-01). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics. 3 (3): 32–57. doi:10.1080/01969727308546046. ISSN 0022-0280.

[3] Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. ISBN 0-306-40671-3.

[Lom-4] Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.

[1]

[2]

[3]

[4]

Участник:ADovganich/Нечеткий алгоритм С средних