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

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

Авторы : Мария Проценко, Андрей Довганич

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

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

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

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

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

1) Инициализировать матрицу принадлежности [math]\displaystyle{ M }[/math] случайными значениями от 0 до 1;

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

[math]\displaystyle{ c_{i} = {{\sum_{k = 1}^{K}{m_{ik}^q} * u_{k}} \over {\sum_{k = 1}^{K}{m_{ik}^q}}} }[/math], где [math]\displaystyle{ m_{ik} }[/math] — коэффициент принадлежности [math]\displaystyle{ u_{k} }[/math] вектора к кластеру [math]\displaystyle{ c_{i} (1) }[/math].

3) Вычислить значение решающей функции по формуле [math]\displaystyle{ (2) }[/math]. Если значение ниже некоторого порогового или его улучшение по сравнению с предыдущей итерацией меньше определенной величины, то остановить вычисления;

[math]\displaystyle{ \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 (2) \end{align} }[/math]

4) Иначе вычислить новые значения матрицы М по формуле [math]\displaystyle{ (3) }[/math];

[math]\displaystyle{ m_{ik} = {1 \over \sum_{j = 1}^{c}{({{d_{ik}} \over {d_{jk}}})}^{2 \over q-1}} }[/math]

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

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

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

- сумма элементов в каждом столбце равна [math]\displaystyle{ 1 }[/math];

- сумма всех элементов матрицы равно [math]\displaystyle{ K }[/math];

Назовем [math]\displaystyle{ M }[/math] матрицей принадлежности.

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

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

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