Участник:Demon smd/Нечеткий алгоритм С средних: различия между версиями
| Строка 42: | Строка 42: | ||
Нечёткое разбиение входных данных на кластеры производится итеративной оптимизацией вышеуказанной функции с обновлением коэффициента принадлежности <math>u_{i,j}</math> и переопределением центра кластера <math>c_{j}</math> на каждой итерации алгоритма. | Нечёткое разбиение входных данных на кластеры производится итеративной оптимизацией вышеуказанной функции с обновлением коэффициента принадлежности <math>u_{i,j}</math> и переопределением центра кластера <math>c_{j}</math> на каждой итерации алгоритма. | ||
| − | + | ==== Вычисляемые данные на каждой итерации ==== | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | ==== Вычисляемые данные ==== | ||
* Центры кластеров рассчитываются по следующей формуле: <math>c_{j} = {{\sum_{i = 1}^{n}{u_{i,j}^m} * x_{i}} \over {\sum_{i = 1}^{n}{u_{i,j}^m}}}</math>, где <math>u_{i,j}</math> — коэффициент принадлежности <math>x_{i}</math> вектора к кластеру <math>c_{j}</math>. | * Центры кластеров рассчитываются по следующей формуле: <math>c_{j} = {{\sum_{i = 1}^{n}{u_{i,j}^m} * x_{i}} \over {\sum_{i = 1}^{n}{u_{i,j}^m}}}</math>, где <math>u_{i,j}</math> — коэффициент принадлежности <math>x_{i}</math> вектора к кластеру <math>c_{j}</math>. | ||
| Строка 63: | Строка 54: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Из вышесказанного следует, что ядром алгоритма является вычисление нового центра кластеров, для каждого входного вектора вычисление Евклидова расстояния до центров кластеров, а также коэффициент принадлежности и вычисления решающей функции. | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| Строка 75: | Строка 68: | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
| + | |||
| + | ==== Входные данные алгоритма ==== | ||
| + | * <math>x_{i}</math> - набор входных векторов | ||
| + | * <math>C</math> - количество кластеров | ||
| + | * <math>m</math> - коэффициент неопределённости | ||
| + | * <math>\varepsilon > 0</math> - коэффициент, определяющий точность алгоритма. | ||
| + | |||
| + | ==== Выходные данные алгоритма ==== | ||
| + | * <math>u</math> - матрица принадлежности векторов кластерам | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 17:14, 30 сентября 2016
| Нечеткий алгоритм C средних (Fuzzy C-means) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]-[/math] |
| Объём входных данных | [math]-[/math] |
| Объём выходных данных | [math]-[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]-[/math] |
| Ширина ярусно-параллельной формы | [math]-[/math] |
Авторы описания алгоритма: Д.А.Гуськов М.А.Абраменкова
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Нечёткий алгоритм кластеризации С-средних был разработан (для случая m=2) J.C. Dunn в 1973 г. [1] и усовершенствован (для случая m>1) J.C. Bezdek в 1981 г. [2] . В отличие от алгоритма c-means Данный метод кластеризации предполагает, что входные данные могут принадлежать более, чем одному кластеру одновременно. Алгоритм получает на вход набор кластеризируемых векторов, количество кластеров, коэффициент неопределённости m и коэффициент [math]\varepsilon \gt 0[/math], определяющий точность алгоритма. На выходе алгоритма получаем матрицу вероятностей принадлежности каждого входного вектора каждому кластеру.
Нечеткий алгоритм С средних для каждого вектора определяет случайным образом значения принадлежности вектора к каждому кластеру и запускает итерационный процесс, на каждой итерации которого происходит:
1) Расчёт центров кластеров.
2) Расчёт Евклидова расстояния от каждого вектора до центра каждого кластера
3) Расчёт и нормализация коэффициентов принадлежности векторов кластерам
4) Расчёт значения решающей функции и сравнение этого значения со значением решающей функции на предшествующей итерации.Если их разница меньше установленного значения, то алгоритм прекращает работу. Решающая функция возвращает сумму всех Евклидовых расстояний каждого объекта к каждому центру кластера умноженному на коэффициент принадлежности
1.2 Математическое описание алгоритма
Нечеткий алгоритм С средних минимизирует величину:
- [math] \begin{align} J_{m} = \sum_{i = 1}^{N}\sum_{j = 1}^{C}u_{i,j}^m\left\Vert{x_{i}-c_{j}}\right\|^2 & & , & & 1 \le m \le \infty & ; \\ \end{align} [/math]
где m - это действительное число не меньше единицы, [math]u_{i,j}[/math] - коэффициент принадлежности вектора [math]x_{i}[/math] к кластеру [math]c_{j}[/math], [math]x_{i}[/math] - [math]i[/math]-ый компонент [math]N[/math]-мерного вектора [math]x[/math], [math]c_{j}[/math] - центр [math]j[/math]-ого кластера, а [math]\left\Vert{*}\right\|[/math] - это любая норма, определяющая расстояние от вектора до центра кластера. Нечёткое разбиение входных данных на кластеры производится итеративной оптимизацией вышеуказанной функции с обновлением коэффициента принадлежности [math]u_{i,j}[/math] и переопределением центра кластера [math]c_{j}[/math] на каждой итерации алгоритма.
1.2.1 Вычисляемые данные на каждой итерации
- Центры кластеров рассчитываются по следующей формуле: [math]c_{j} = {{\sum_{i = 1}^{n}{u_{i,j}^m} * x_{i}} \over {\sum_{i = 1}^{n}{u_{i,j}^m}}}[/math], где [math]u_{i,j}[/math] — коэффициент принадлежности [math]x_{i}[/math] вектора к кластеру [math]c_{j}[/math].
- Евклидово расстояние от вектора [math]x_{i}[/math] до центра кластера [math]c_{j}[/math] рассчитывается по формуле: [math]\left\Vert{x_{i}-c_{j}}\right\|^2[/math]
- Коэффициент принадлежности рассчитывается по формуле: [math]u_{i,j} = {1 \over \sum_{k = 1}^{C}{({\left\Vert{x_{i}-c_{j}}\right\| \over \left\Vert{x_{i}-c_{k}}\right\|})}^{2 \over m-1}}[/math]
- Нормализация всех коэффициентов принадлежности объекта производится по формуле: [math]u_{i,j} = {u_{i,j} \over \sum_{j = 1}^{C}{u_{i,j}}} [/math]
- Решающая функция рассчитывается по формуле: [math]\max_{i,j}(|u_{i,j}^{(k)} - u_{i,j}^{(k-1)}|)[/math], где [math]k[/math] - номер итерации алгоритма
1.3 Вычислительное ядро алгоритма
Из вышесказанного следует, что ядром алгоритма является вычисление нового центра кластеров, для каждого входного вектора вычисление Евклидова расстояния до центров кластеров, а также коэффициент принадлежности и вычисления решающей функции.
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.9.1 Входные данные алгоритма
- [math]x_{i}[/math] - набор входных векторов
- [math]C[/math] - количество кластеров
- [math]m[/math] - коэффициент неопределённости
- [math]\varepsilon \gt 0[/math] - коэффициент, определяющий точность алгоритма.
1.9.2 Выходные данные алгоритма
- [math]u[/math] - матрица принадлежности векторов кластерам
1.10 Свойства алгоритма
2 Литература
<references \>
- ↑ 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.
