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

Нечеткий алгоритм C средних

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

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

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

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

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

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

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

1) Инициализировать матрицу принадлежности;

2) Вычислить центры кластеров;

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

4) Иначе вычислить новые значения матрицы принадлежности;

5) Перейти к шагу 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$. Таким образом эти два условия дают нам итерационный процесс.

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

1) Инициализировать матрицу принадлежности $M$ случайными значениями от 0 до 1;

2) Вычислить центры кластеров $c_{i} (i = 1,2,...c)$ используя формулу $~(2)$;

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

4) Иначе вычислить новые значения матрицы М по формуле $~(3)$;

5) Перейти к шагу 2

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

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

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

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

1) Инициализация матрицы $M$ случайными значениями от 0 до 1;

2) Вычисление центров кластеров;

3) Вычисление значения решающей функции(если оно удовлетворяет условиям останова - завершение вычислений);

4) Вычисление новых элементов матрицы принадлежности;

5) Переход к шагу 2;

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

Пример реализации алгоритма на языке С++

    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)<eps1) || (j<eps2)) 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]),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)$.

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

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

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