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

Файл:Symbol wait.svg

Эта работа прошла предварительную проверку Дата последней правки страницы: 18.12.2016 Данная работа соответствует формальным критериям. Проверено Coctic.

Нечеткий алгоритм C средних (Fuzzy C-means)
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(C^2*|X|*D*IterNumber) }[/math]
Объём входных данных	[math]\displaystyle{ |X|*p }[/math], где [math]\displaystyle{ p }[/math] - размерность входных векторов
Объём выходных данных	[math]\displaystyle{ |X|*C }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(\log_{2}C^4*|X|^3) * IterNumber }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(C^2*|X|) }[/math]

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \begin{align} \sum_{i = 1}^{|X|}\sum_{j = 1}^{C}u_{i,j}^m\left\Vert{x_{i}-c_{j}}\right\|^2 & , & & 1 \le m \le \infty , \\ \end{align} }[/math]

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

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

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

• Коэффициент принадлежности рассчитывается по формуле: [math]\displaystyle{ 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}} }[/math]

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

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

Ядром алгоритма является:

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

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

В каждой итерации алгоритма происходит 3 основных действия описанных в п. 1.2.1:

• вычисление центров кластеров
• вычисление коэффициентов принадлежности
• вычисление решающей функции

Подробное описание макроструктур в виде кода приведено в пункте 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.size(); 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.size(); 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.size(); 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.size(); i++)    //для каждого вектора
                for (int j=0; j<C; j++){   //для каждого кластера
                    uPrev[i][j]=u[i][j];
        else
            break;
             
    }
    return u;
}

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

Последовательная сложность всего алгоритма складывается из сложности операций на каждой итерации умноженную на количество итераций. Под операцией будем понимать выражение в языке с++ из пункта 1.5, находящееся в теле цикла (например, выражения "sum+= pow( dist(x[i], c[j]) / dist(x[i], c[k]), 2/(m-1));" или "uPrev[i][j]=u[i][j];" считаются за одну операцию). Так как при больших входных объёмах данных сложность алгоритма в большей степени зависит от количества входных данных, и незначительно зависит от сложности операций,то при оценке сложности алгоритма сложность выражений можно считать равной единице. Так как в данном алгоритме количество итераций не является фиксированным и зависит от:

• параметра [math]\displaystyle{ \varepsilon }[/math]
• набора входных векторов [math]\displaystyle{ x }[/math]
• выбора начальных коэффициентов [math]\displaystyle{ u }[/math]

то в данном пункте будет приведена сложность одной итерации относительно количества входных векторов. Для вычисления коэффициентов u[][] на каждой итерации алгоритма требуется определить расстояние от векторов до центра кластера. Сложность данной операции зависит от размерности входных данных и определении нормы. В виду того, что для разных задач могут быть введены разные нормы, и сложность вычисления расстояний может варьироваться, то в данной статье будем считать, что сложность вычисления расстояния зависит линейно от размерности водных данных. В таком случае, для вычисления центров кластеров требуется [math]\displaystyle{ O(2*C*|X|) }[/math] операций, для определения коэффициентов [math]\displaystyle{ u }[/math] - [math]\displaystyle{ O(C^2*|X|*D) }[/math] операций, а для вычисления решающей функции - [math]\displaystyle{ O(2*C*|X|) }[/math] операций, где [math]\displaystyle{ |X| }[/math] - число входных векторов, а [math]\displaystyle{ C }[/math] - количество кластеров.

Таким образом итоговая сложность одной итерации составляет [math]\displaystyle{ O(C^2*|X|*D) }[/math].

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

Как видно из пункта 1.5, на каждом действии каждой итерации алгоритма все операции, выполняющиеся в цикле, не зависят друг от друга и могут быть распараллелены. Это показано на Рисунке 1.

Рисунок 1. Информационный граф алгоритма. (1)-(7) - это наборы последовательных действий (например, (2) - последовательные операции деления, чтения элемента из памяти и присваивания).

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

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

Сложность алгоритма будем рассчитывать в предположении, что число вычислительных ядер стремится к бесконечности. Как видно из информационного графа, параллельная сложность вычисления центров кластеров составляет [math]\displaystyle{ O(\log_{2}(C*|X|)) }[/math], вычисления коэффициентов принадлежности - [math]\displaystyle{ O(\log_{2}(C^2*|X|)) }[/math], а вычисления решающей функции - не больше чем [math]\displaystyle{ O(\log_{2} (C*|X|)) }[/math].

Таким образом параллельная сложность итерации алгоритма составляет [math]\displaystyle{ O(\log_{2} (C^4*|X|^3)) }[/math].

Так как задачи, решаемые в макроструктуре алгоритма могут быть сведены к задачам вычисления суммы элементов массива и максимального элемента массива, то на [math]\displaystyle{ i }[/math]-ом ярусе графа будет находиться [math]\displaystyle{ {N}\over{2^i} }[/math] операции, где N - количество элементов массива.

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

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

• [math]\displaystyle{ X }[/math] - набор из [math]\displaystyle{ |X| }[/math] входных векторов длины [math]\displaystyle{ p }[/math]
• [math]\displaystyle{ C }[/math] - количество кластеров
• [math]\displaystyle{ m }[/math] - коэффициент неопределённости
• [math]\displaystyle{ \varepsilon \gt 0 }[/math] - коэффициент, определяющий точность алгоритма.

Объем входных данных: [math]\displaystyle{ |X|*p+3 }[/math]

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

• [math]\displaystyle{ u }[/math] - матрица принадлежности векторов кластерам

Объем выходных данных: [math]\displaystyle{ |X|*C }[/math]

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

Увеличение скорости работы алгоритма при распараллеливании на бесконечном количестве процессоров составляет [math]\displaystyle{ O({{C^2*|X|}\over{\log_{2} (C^4*|X|^3)}}) }[/math]. Например, для разбиения 1000 элементов на 10 кластеров производительность параллельного алгоритма будет в 2315 раз больше, а на 20 кластеров - уже в 8477 раз.

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

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

Как видно из предыдущих пунктов, масштабируется данный алгоритм хорошо. С увеличением количества процессоров время работы падает, а с увеличением количества входных данных и количества кластеров - растёт. На рисунках показаны результаты запусков алгоритма на разном количестве входных данных и процессоров на массивно-параллельной вычислительной системе Blue Gene/P. Использовался компилятор mpixlcxx без указания специфических опций. Запуски производились в режиме SMP (на каждом ядре 1 MPI процесс из 4 SMP нитей, 2 Гб памяти). Характеристики вычислительного узла: 4 ядерный 32-битный процессор PowerPC 850 Мгц.

Исходных код программы можно найти здесь: https://github.com/demonsmd/superPrak

Рисунок 2. Масштабируемость алгоритма. Зависимость времени работы алгоритма от количества процессоров и входных данных при фиксированном количестве кластеров.

Рисунок 3. Масштабируемость алгоритма. Зависимость времени работы алгоритма от количества процессоров и кластеров при фиксированном количестве входных данных.

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

Существует множество реализаций данного алгоритма. Рассмотрим некоторые из них:

- Например, тут: https://habrahabr.ru/post/208496/ приведено краткое описание алгоритма и приведена его реализация на php. В данной статье довольно подробно расписан каждый шаг алгоритма и приведён соответствующий ему фрагмент кода.

- Тут: http://num-meth.srcc.msu.ru/zhurnal/tom_2012/v13r207.html приводится реализация алгоритма для PostgreSQL, а также прилагается скрипт внедрения алгоритма.

Литература

<references \>