Участник:ADovganich/Нечеткий алгоритм С средних: различия между версиями
Protsenko (обсуждение | вклад) Нет описания правки |
|||
| Строка 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 | |||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия от 17:33, 13 октября 2016
| Нечеткий алгоритм C средних |
Авторы : Мария Проценко, Андрей Довганич
Свойства и структура алгоритмов
Общее описание алгоритма
Нечеткий алгоритм C-средних (fuzzy C-means) позволяет разбить имеющееся множество векторов (точек) мощностью p на заданное число нечетких множеств. Предназначен для кластеризации больших наборов данных. Основным достоинством алгоритма является нечеткость при определении объекта в кластер. Благодаря этому становится возможным определить объекты, которые находятся на границе, в кластеры. Из основного достоинства следует и главный недостаток - неопределенность с объектами, удаленными от центров всех кластеров. В остальном ему присущи стандартные проблемы подобного класса алгоритмов: вычислительная сложность, необходимость задания количества кластеров[1].
Алгоритм был разработан J.C. Dunn в 1973 г.[2], усовершенствован J.C. Bezdek в 1981 г.[3].
В общем виде алгоритм можно записать следующим образом:
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
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ Нейский И.М. Классификация и сравнение методов кластеризации
- ↑ 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.
- ↑ Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. ISBN 0-306-40671-3.