Метод нечёткой кластеризации C-средних

Метод нечёткой кластеризации C-средних (англ. fuzzy clustering, soft k-means, c-means) позволяет разбить имеющееся множество элементов мощностью $N$ на заданное число нечётких множеств $k$. Метод нечеткой кластеризации C-средних можно рассматривать как усовершенствованный метод k-средних, при котором для каждого элемента из рассматриваемого множества рассчитывается степень его принадлежности (англ. responsibility) каждому из кластеров.

Алгоритм был разработан J.C. Dunn в 1973 и улучшен J.C. Bezdek в 1981.

Алгоритм:

1. Задать случайным образом $k$ центров кластеров $c_{j}\ ,\ j=1..k$;
2. Рассчитать матрицу принадлежности элементов к кластерам $r$. В случае нормального распределения: $r_{ij}={\frac {{\mathcal {N}}(d(x_{i},c_{j})|\mu =0,\sigma )}{\displaystyle \sum _{j}^{k}{\mathcal {N}}(d(x_{i},c_{j})|\mu =0,\sigma )}}$, где $x_{i}$— $i$-й элемент множества, $c_{j}$— центр кластера $j$, $d(x_{i},c_{j})$ — расстояние между точками $x_{i}$ и $c_{j}$, ${\mathcal {N}}$— плотность вероятности нормального распределения в точке $d(x_{i},c_{j})$.
3. Переместить центры кластеров $c_{j}\leftarrow {\frac {\displaystyle \sum _{i}r_{ij}x_{i}}{\displaystyle \sum _{i}r_{ij}}}$;
4. Рассчитать функцию потерь (например, исходя из принципа максимального правдоподобия). В случае нормального распределения функция потерь будет равна: $J=\displaystyle \sum _{j}^{k}\sum _{i}^{N}d(x_{i},c_{j})^{2}r_{ij}$;
5. Если значение функции потерь уменьшается, то повторить цикл с п.2.

Метод нечеткой кластеризации C-средних имеет ограниченное применение из-за существенного недостатка — невозможность корректного разбиения на кластеры, в случае когда кластеры имеют различную дисперсию по различным размерностям (осям) элементов (например, кластер имеет форму эллипса). Данный недостаток устранен в алгоритмах Mixture models и GMM (Gaussian mixture models).