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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 22: Строка 22:
 
2) Вычислить центры кластеров <math>c_{i} (i = 1,2,...c)</math> используя формулу <math>(1)</math>;
 
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>.
+
<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>. Если значение ниже некоторого порогового или его улучшение по сравнению с предыдущей итерацией меньше определенной величины, то остановить вычисления;
 
3) Вычислить значение решающей функции по формуле <math>(2)</math>. Если значение ниже некоторого порогового или его улучшение по сравнению с предыдущей итерацией меньше определенной величины, то остановить вычисления;
Строка 28: Строка 28:
 
<math>
 
<math>
 
\begin{align}
 
\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)
+
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}
 
\end{align}
 
</math>
 
</math>
Строка 34: Строка 34:
 
4) Иначе вычислить новые значения матрицы М по формуле <math>(3)</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>
+
<math>m_{ik} = {1 \over \sum_{j = 1}^{c}{({{d_{ik}} \over {d_{jk}}})}^{2 \over q-1}}</math>
  
  

Версия 01:02, 15 октября 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_{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]c_{i} (i = 1,2,...c)[/math] - центры кластеров. Тогда рассмотрим функцию (2), где [math] d_{i,k} = \left\Vert{u_{k}-c_{i}}\right\| [/math]

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=8363