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.