fcmeans

模糊C均值聚类(Fuzzy c-mean clustering)

模糊是指没有明确边界划分无法精确刻画的现象称为模糊。

对离散且有限的论域

$$U = \{u_1, u_2, ..., u_n\}$$

其模糊集可表示为

$$F = \{\mu_F(u_1),\mu_F(u_1),...\mu_F(u_n)\}$$

其中 $F$ 称为隶属度函数

介绍及引入

我们所谓的kmeans聚类，也就是c均值聚类，可以称之为硬C均值聚类。

给定样本集 $D = {x{1},x{2},…,x{m}}$ ，k均值聚类算法针对聚类所得簇划分 $C = {C{1},C{2},…,C{k}}$ 最小化平方误差

$$min\ E = \sum_{i=1}^{k}\sum_{x \in C_{i}}\|x-\mu_{i}\|_{2}^{2}$$

其中

$$\mu_{i}=\frac{1}{|C_{i}|}\sum_{x \in C_{i}}x$$

模糊概念的引入使得该聚类叫做软C均值聚类，允许每个样本属于一个或以上更多的聚类。可以设想，对于某个样本点，可构建到每个聚类的隶属度函数，设样本数为 $n$ ，聚类数为 $C$ ，则存在 $n*C$ 的隶属度矩阵，每个样本与聚类的硬距离乘对该聚类的隶属度总体求和保证最小，便是模糊C均值聚类所解决的问题。

原理

Fuzzy C-Means聚类所优化的目标函数如下：

$$J_m = \sum_{i=1}^{N}\sum_{j=1}^{C}\mu_{ij}^{m}||x_i-c_j||^{2}, 0 \le m< \infty$$

$m$ 为大于1的任意实数。（至于 $m$ 具体作用也没有深入考虑 $TODO…$

针对上述目标函数优化，采用启发式迭代。

$$u_{ij}=\frac{1}{\sum_{k=1}^{C}(\frac{||x_i-c_j||}{||x_i-c_k||})^{\frac{2}{m-1}}}$$ $$C_j=\frac{\sum_{i=1}^{N}u_{ij}^{m}x_i}{\sum_{i=1}^{N}u_{ij}^{m}}$$

迭代停止条件可取隶属度矩阵变化值小于某 $\xi$ 时停止。

代码实现

见github主页