Fuzzy c-means

Fuzzy c-means

​ 模糊C-均值聚类算法：是一种模糊聚类算法，是K均值算法聚类的推广形式，隶属度取值为[0,1]区间内的任意一个数，提出的基本依据是“类内加权误差平方和最小化”准则。

​ 这两个方法都是迭代求取最终的聚类划分，即聚类中心与隶属度值。两者都不能保证找到问题的最优解，都有可能收敛到局部极值，模糊c均值甚至可能是鞍点。

Fuzzy c-means Algorithm

样本矩阵：$X=[x_1,x_2,...,x_n]\in R^{d\times n}$，有n个$x_i$每个$x_i$是d维

簇集合：$C=[C_1,C_2,...,C_c]$，有c个簇集合

加权误差平方和：计算每个样本点和相应簇均值的加权误差平方和，即：
$$\begin{gathered} \underset{F1=1,F\ge 0,M}{\min }\sum _{j=1}^c\sum _{i=1}^n{f}_{ij}^r||x_i-m_j|{|}_2^2(1) \\ ⟺\underset{F1=1,F\ge 0,M}{\min }\sum _{j=1}^c\sum _{i=1}^n{f}_{ij}^r(x_i^T{x}_i-2x_i^T{m}_j+m_j^T{m}_j) \\ {m}_j是矩阵M\in R^{d\times c}的第j列,表示第c个集合的均值; \\ {f}_{ij}\in [0,1]是隶属矩阵F的i行j列元素，表示第i个样本对第j个簇的隶属度; \\ F1=1表示\sum _{j=1}^c{f}_{ij}=1; \\ r是模糊器参数或者加权指数，r的值是大于1的实数，当r越趋向于1聚类越清晰， \\ 但是当r达到无穷大时聚类就变得更模糊.当r=1时FCM等价于KMEAN \end{gathered}$$
​

​ 上述问题可以看作：
$$\begin{gathered} \underset{F1=1,F\ge 0,M}{\min }\sum _{j=1}^c\sum _{i=1}^n{f}_{ij}^r(x_i^T{x}_i-2x_i^T{m}_j+m_j^T{m}_j) \\ s.t.\sum _{j=1}^c{f}_{ij}=1,F\ge 0 \end{gathered}$$
​ 用拉格朗日乘子法：
$$\begin{gathered} J=\sum _{j=1}^c\sum _{i=1}^n{f}_{ij}^r(x_i^T{x}_i-2x_i^T{m}_j+m_j^T{m}_j)+{\lambda }_1(\sum _{j=1}^c{f}_{ij}-1)+{\lambda }_2(\sum _{j=1}^c{f}_{ij}-1)+...+{\lambda }_n(\sum _{j=1}^c{f}_{ij}-1) \\ =\sum _{j=1}^c\sum _{i=1}^n{f}_{ij}^r(x_i^T{x}_i-2x_i^T{m}_j+m_j^T{m}_j)+\sum _{i=1}^n{\lambda }_i(\sum _{j=1}^c{f}_{ij}-1) \\ {f}_{ij}=\frac{1}{{\sum }_{k=1}^c(\frac{d_{ij}}{d_{ik}}{)}^{\frac{2}{r-1}}}=\frac{(d_{ij}{)}^{\frac{2}{1-r}}}{{\sum }_{k=1}^c(d_{ik}{)}^{\frac{2}{1-r}}}(2) \\ {m}_j=\frac{{\sum }_{i=1}^n{f}_{ij}^r{x}_i}{{\sum }_{i=1}^n{f}_{ij}^r}=\frac{{\sum }_{i=1}^n{g}_{ij}{x}_i}{{\sum }_{i=1}^n{g}_{ij}}=\frac{X{g}_j}{g_j^{T}1}(3) \\ 其中d_{ij}=||x_i-m_j|{|}_2^2,f_{ij}^r=g_{ij} \end{gathered}$$

Algorithm 1 FCM. The standard algorithm for minimizing problem (1) 
    1: Input data matrix X ∈ Rd×n, cluster number c. 
    2: Initialize membership matrix F. 
    3: repeat 
         4: Calculate center matrix M ∈ Rd×c by Eq. (3); 
	     5: Calculate membership matrix F ∈ Rn×c by Eq. (2); 
	6: until convergence 
    7: Output membership matrix F.
1
2
3
4
5
6
7
8