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

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

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

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

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

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

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

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

1) Инициализировать матрицу принадлежности M случайными значениями от 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_{i,k}^q} * u_{k}} \over {\sum_{k = 1}^{K}{m_{i,k}^q}}} }[/math], где [math]\displaystyle{ m_{i,k} }[/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_{i,k}^q}d_{i,k}^2 (2) \end{align} }[/math]

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

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

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