Участник:Demon smd/Нечеткий алгоритм С средних

Нечткий алгоритм C средних (Fuzzy C-means)
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ - }[/math]
Объём входных данных	[math]\displaystyle{ - }[/math]
Объём выходных данных	[math]\displaystyle{ - }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ - }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ - }[/math]

Авторы описания алгоритма: Д.А.Гуськов

Свойства и структура алгоритма

Общее описание алгоритма

Нечёткий алгоритм кластеризации С-средних был разработан (для случая m=2) J.C. Dunn в 1973 г. и усовершенствован (для случая m>1) J.C. Bezdek в 1981 г. . В отличие от алгоритма c-means Данный метод кластеризации предполагает, что входные данные могут принадлежать более, чем одному кластеру одновременно. Алгоритм получает на вход набор кластеризируемых векторов, количество кластеров, коэффициент неопределённости m и коэффициент [math]\displaystyle{ \varepsilon \gt 0 }[/math], являющийся критерием останова алгоритма. На выходе алгоритма получаем матрицу вероятностей принадлежности каждого входного вектора каждому кластеру.

Нечеткий алгоритм С средних для каждого вектора определяет случайным образом значения принадлежности вектора к каждому кластеру и запускает итерационный процесс, на каждой итерации которого происходит: \begin{align} 1) Расчёт центров кластеров.

2) Расчёт Евклидова расстояния от каждого вектора до центра каждого кластера

3) Расчёт и нормализация коэффициентов принадлежности векторов кластерам

4) Расчёт значения решающей функции и сравнение этого значения со значением решающей функции на предшествующей итерации.Если их разница меньше установленного значения, то алгоритм прекращает работу. \end{align}

Математическое описание алгоритма

[math]\displaystyle{ \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]\displaystyle{ u_{i,j} }[/math] - коэффициент принадлежности [math]\displaystyle{ x_{i} }[/math] к кластеру [math]\displaystyle{ j }[/math], [math]\displaystyle{ x_{i} }[/math] - [math]\displaystyle{ i }[/math]-ый компонент [math]\displaystyle{ N }[/math]-мерного вектора [math]\displaystyle{ x }[/math], [math]\displaystyle{ c_{j} }[/math] - центр [math]\displaystyle{ j }[/math]-ого кластера, а [math]\displaystyle{ \left\Vert{*}\right\| }[/math] - это любая норма, определяющая расстояние от вектора до центра кластера. Нечёткое разбиение входных данных на кластеры производится итеративной оптимизацией вышеуказанной функции с обновлением коэффициента принадлежности [math]\displaystyle{ u_{i,j} }[/math] и переопределением центра кластера [math]\displaystyle{ c_{j} }[/math] на каждой итерации алгоритма по формулам:

[math]\displaystyle{ \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]

Литература

<references \>