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

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

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

Алгоритм:

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

Ссылки

1. Dunn J.C. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters // Journal of Cybernetics. — 1973. — 17 сентября (т. 3, № 3). — С. 32–57. — ISSN 0022-0280. — doi:10.1080/01969727308546046.
2. Bezdek, James C. Pattern Recognition with Fuzzy Objective Function Algorithms. — 1981. — ISBN 0-306-40671-3.