Участник:Demon smd/Нечеткий алгоритм С средних: различия между версиями
Demon smd (обсуждение | вклад) |
Demon smd (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
где m - это действительное число не меньше единицы, <math>u_{i,j}</math> - коэффициент принадлежности <math>x_{i}</math> к кластеру <math>j</math>, <math>x_{i}</math> - <math>i</math>-ый компонент <math>N</math>-мерного вектора <math>x</math>, <math>c_{j}</math> | где m - это действительное число не меньше единицы, <math>u_{i,j}</math> - коэффициент принадлежности <math>x_{i}</math> к кластеру <math>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>j</math>-ого кластера, а <math>\left\Vert{*}\right\|</math> - это любая норма, определяющая расстояние от вектора до центра кластера. | ||
| + | Нечёткое разбиение входных данных на кластеры производится итеративной оптимизацией вышеуказанной функции с обновлением коэффициента принадлежности <math>u_{i,j}</math> и переопределением центра кластера <math>c_{j}</math> на каждой итерации алгоритма по формулам: | ||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
Версия 17:11, 25 сентября 2016
| Нечткий алгоритм C средних (Fuzzy C-means) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]-[/math] |
| Объём входных данных | [math]-[/math] |
| Объём выходных данных | [math]-[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]-[/math] |
| Ширина ярусно-параллельной формы | [math]-[/math] |
Авторы описания алгоритма: Д.А.Гуськов
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Нечёткий алгоритм кластеризации С-средних был разработан (для случая m=2) J.C. Dunn в 1973 г. [1] и усовершенствован (для случая m>1) J.C. Bezdek в 1981 г. [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]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] на каждой итерации алгоритма по формулам:
- [math] \begin{align} 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}} & ; \\ c_{j} = {{\sum_{i = 1}^{n}{u_{i,j}^m}*x_{i}} \over {\sum_{i = 1}^{n}{u_{i,j}^m}}} \end{align} [/math]
1.2 Математическое описание алгоритма
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.
