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

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

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

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

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

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

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

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

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

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

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

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

[math] \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](3)[/math];

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

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

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

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

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

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

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

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

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

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