Участник:ADovganich/Нечеткий алгоритм С средних: различия между версиями
| Строка 40: | Строка 40: | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
| − | Рассмотрим матрицу <math> M = m_{ik} \in[0,1],\; i = 1, ..., c, \; k = 1, ..., K </math> | + | Рассмотрим матрицу <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>1</math>; | ||
| Строка 46: | Строка 46: | ||
- сумма всех элементов матрицы равно <math>K</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> | + | Назовем <math> M </math> матрицей принадлежности. |
| + | |||
| + | Пусть <math>c_{i} (i = 1,2,...c)</math> - центры кластеров. Тогда рассмотрим функцию <math>(2)</math>, где <math> d_{i,k} = \left\Vert{u_{k}-c_{i}}\right\| </math> - Евклидово расстояние между центром кластера и объектом, <math> 1 \le q \le \infty </math> - экспоненциальный весовой коэффициент, характеризующий нечеткость. Будем минимизировать значение функции <math> J </math>. <math> (1) </math> и <math> (3) </math> являются необходимым условие достижения минимума этой функцией. Таким образом эти два условия дают нам итерационный процесс, описанный выше. | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия 01:19, 15 октября 2016
| Нечеткий алгоритм C средних |
Авторы : Мария Проценко, Андрей Довганич
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 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 Свойства и структура алгоритмов
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] M [/math] матрицей принадлежности.
Пусть [math]c_{i} (i = 1,2,...c)[/math] - центры кластеров. Тогда рассмотрим функцию [math](2)[/math], где [math] d_{i,k} = \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 Вычислительное ядро алгоритма
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 Литература
- ↑ Нейский И.М. Классификация и сравнение методов кластеризации
- ↑ 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.
