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

Нечеткий алгоритм C средних (Fuzzy C-means)
Последовательный алгоритм
Последовательная сложность	$-$
Объём входных данных	$-$
Объём выходных данных	$-$
Параллельный алгоритм
Высота ярусно-параллельной формы	$-$
Ширина ярусно-параллельной формы	$-$

Авторы описания алгоритма: Д.А.Гуськов М.А.Абраменкова

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

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

Нечёткий алгоритм кластеризации С-средних был разработан (для случая m=2) J.C. Dunn в 1973 г. и усовершенствован (для случая m>1) J.C. Bezdek в 1981 г. . В отличие от алгоритма c-means Данный метод кластеризации предполагает, что входные данные могут принадлежать более, чем одному кластеру одновременно. Алгоритм получает на вход набор кластеризируемых векторов, количество кластеров, коэффициент неопределённости m и коэффициент $\varepsilon \gt 0$, определяющий точность алгоритма. На выходе алгоритма получаем матрицу вероятностей принадлежности каждого входного вектора каждому кластеру.

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

1) Расчёт центров кластеров.

2) Расчёт Евклидова расстояния от каждого вектора до центра каждого кластера

3) Расчёт и нормализация коэффициентов принадлежности векторов кластерам

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

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

Нечеткий алгоритм С средних минимизирует величину:

$\begin{align} J_{m} = \sum_{i = 1}^{N}\sum_{j = 1}^{C}u_{i,j}^m\left\Vert{x_{i}-c_{j}}\right\|^2 & & , & & 1 \le m \le \infty & ; \\ \end{align}$

где m - это действительное число не меньше единицы, $u_{i,j}$ - коэффициент принадлежности вектора $x_{i}$ к кластеру $c_{j}$, $x_{i}$ - $i$-ый компонент $N$-мерного вектора $x$, $c_{j}$ - центр $j$-ого кластера, а $\left\Vert{*}\right\|$ - это любая норма, определяющая расстояние от вектора до центра кластера. Нечёткое разбиение входных данных на кластеры производится итеративной оптимизацией вышеуказанной функции с обновлением коэффициента принадлежности $u_{i,j}$ и переопределением центра кластера $c_{j}$ на каждой итерации алгоритма.

1.2.1 Вычисляемые данные на каждой итерации

• Центры кластеров рассчитываются по следующей формуле: $c_{j} = {{\sum_{i = 1}^{n}{u_{i,j}^m} * x_{i}} \over {\sum_{i = 1}^{n}{u_{i,j}^m}}}$, где $u_{i,j}$ — коэффициент принадлежности $x_{i}$ вектора к кластеру $c_{j}$.

• Евклидово расстояние от вектора $x_{i}$ до центра кластера $c_{j}$ рассчитывается по формуле: $\left\Vert{x_{i}-c_{j}}\right\|^2$

• Коэффициент принадлежности рассчитывается по формуле: $u_{i,j} = {1 \over \sum_{k = 1}^{C}{({\left\Vert{x_{i}-c_{j}}\right\| \over \left\Vert{x_{i}-c_{k}}\right\|})}^{2 \over m-1}}$

• Нормализация всех коэффициентов принадлежности объекта производится по формуле: $u_{i,j} = {u_{i,j} \over \sum_{j = 1}^{C}{u_{i,j}}}$

• Решающая функция рассчитывается по формуле: $\max_{i,j}(|u_{i,j}^{(k)} - u_{i,j}^{(k-1)}|)$, где $k$ - номер итерации алгоритма

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

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

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

Схему реализации последовательного алгоритма можно описать на C++ следующим образом:

FCM (X[], C[], m, eps){
    float deside = 0;
    float newDeside = 0;
    generateMembershipDegree();            //заполняет uPrev[][] случайными нормрованными коэффициентами
    while (true){
        newDeside = deside;

        //вычисление центров кластеров
        for (int j=0; j<C; j++){           //для каждого кластера
            float numerator = 0;
            float denumerator = 0;
            for (int i=0; i<X; i++){        //для каждого вектора
                numerator+=pow(u[i][j], m) * x[i];
                denumerator+=pow(u[i][j], m);
            }
            c[j] = numerator / denumerator;
        }

        //вычисление коэффициентов u[][]
        for (int i=0; i<X; i++)    //для каждого вектора
            for (int j=0; j<C; j++){   //для каждого кластера
                sum = 0;
                for (int k=0; k<C; k++)
                    sum+= pow( dist(x[i], c[j]) / dist(x[i], c[k]), 2/(m-1));
                u[i][j] = 1/sum
            }

        //определения максимального различия между u[][] и uPrev[][]
        float max = 0;
        for (int i=0; i<X; i++)    //для каждого вектора
            for (int j=0; j<C; j++){   //для каждого кластера
                if (abs(uPrev[i][j]-u[i][j])>max)
                    max = abs(uPrev[i][j]-u[i][j]);

        if (eps <= max)
            for (int i=0; i<X; i++)    //для каждого вектора
                for (int j=0; j<C; j++){   //для каждого кластера
                    uPrev[i][j]=u[i][j];
        else
            break;
             
    }
    return u;
}

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

Последовательная сложность всего алгоритма складывается из сложности операций на каждой итерации умноженную на количество итераций. Так как в данном алгоритме количество итераций не является фиксированным и зависит от:

• параметра $\varepsilon$
• набора входных векторов $x$
• выбора начальных коэффициентов $u$

то в данном пункте будет приведена сложность одной итерации относительно количества входных векторов. Как видно из предыдущего пункта, для вычисления центров кластеров требуется $O(2*C*N)$ операций, для определения коэффициентов $u$ - $O(С^{2} * N * D)$ операций, а для вычисления решающей функции - $O(2*C*N)$ операций, где $N$ - число входных векторов, $C$ - количество кластеров, а $D$ - количество операций, требуемых для вычисления Евклидова расстояния между вектором и центром кластера. Таким образом итоговая сложность одной итерации составляет $O(С*N*D)$.

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

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

• $x_{i}$ - набор входных векторов
• $C$ - количество кластеров
• $m$ - коэффициент неопределённости
• $\varepsilon \gt 0$ - коэффициент, определяющий точность алгоритма.

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

• $u$ - матрица принадлежности векторов кластерам

2 Литература

<references \>