Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 12: Строка 12:
 
= Свойства и структура алгоритмов =
 
= Свойства и структура алгоритмов =
 
== Общее описание алгоритма ==
 
== Общее описание алгоритма ==
 +
Нечеткий алгоритм C-средних (fuzzy C-means) позволяет разбить имеющееся множество векторов (точек) мощностью p на заданное число нечетких множеств. Предназначен для кластеризации больших наборов данных. Основным достоинством алгоритма является нечеткость при определении объекта в кластер. Благодаря этому становится возможным определить объекты, которые находятся на границе, в кластеры. Из основного достоинства следует и главный недостаток - неопределенность с объектами, удаленными от центров всех кластеров. В остальном ему присущи стандартные проблемы подобного класса алгоритмов: вычислительная сложность, необходимость задания количества кластеров<ref>Нейский И.М. Классификация и сравнение методов кластеризации</ref>.
 +
 +
Алгоритм был разработан J.C. Dunn в 1973 г.<ref> Dunn, J. C. (1973-01-01). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics. 3 (3): 32–57. doi:10.1080/01969727308546046. ISSN 0022-0280.</ref>, усовершенствован J.C. Bezdek в 1981 г.<ref> Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. ISBN 0-306-40671-3.</ref>.
 +
 +
В общем виде алгоритм можно записать следующим образом:
 +
 +
1) Инициализировать матрицу принадлежности M случайными значениями от 0 до 1;
 +
 +
2) Вычислить центры кластеров <math>c_{i} (i = 1,2,...c)</math> используя формулу <math>(1)</math>;
 +
 +
<math>c_{i} = {{\sum_{k = 1}^{K}{m_{i,k}^q} * u_{k}} \over {\sum_{k = 1}^{K}{m_{i,k}^q}}}</math>, где <math>m_{i,k}</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_{i,k}^q}d_{i,k}^2 (2)
 +
\end{align}
 +
</math>
 +
 +
4) Иначе вычислить новые значения матрицы М по формуле <math>(3)</math>;
 +
 +
<math>m_{i,k} = {1 \over \sum_{j = 1}^{c}{({{d_{i,k}} \over {d_{j,k}}})}^{2 \over q-1}}</math>
 +
 +
 +
5) Перейти к шагу 2
 +
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==

Версия 20:33, 13 октября 2016


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


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

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

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

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

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

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

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

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

[math]c_{i} = {{\sum_{k = 1}^{K}{m_{i,k}^q} * u_{k}} \over {\sum_{k = 1}^{K}{m_{i,k}^q}}}[/math], где [math]m_{i,k}[/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_{i,k}^q}d_{i,k}^2 (2) \end{align} [/math]

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

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


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

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

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

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

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

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

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

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

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

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

  1. ↑ Нейский И.М. Классификация и сравнение методов кластеризации
  2. ↑ Dunn, J. C. (1973-01-01). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics. 3 (3): 32–57. doi:10.1080/01969727308546046. ISSN 0022-0280.
  3. ↑ Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. ISBN 0-306-40671-3.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:ADovganich/Нечеткий_алгоритм_С_средних&oldid=6672