FCM算法实现Python（简洁版）

青旅半醒 2022-02-18 15:09 474阅读 0赞

## FCM算法 ##

关于聚类的所有项目都放到了这个上面

*  https://github.com/Sean16SYSU/MachineLearningImplement/tree/master/Clustering

全名为Fuzzy C-Means，是一种聚类算法。

> Fuzzy c-means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by Dunn in 1973 and improved by Bezdek in 1981) is frequently used in pattern recognition. It is based on minimization of the following objective function:  
> FCM是一种聚类的方法，可以允许一个数据属于两个或以上的类。这种方法（由Dunn在1973年提出，由Bezdek在1981年改进。）被频繁地用于模式识别。
> 
>  *  J. C. Dunn (1973): “A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters”, Journal of Cybernetics 3: 32-57
>  *  J. C. Bezdek (1981): “Pattern Recognition with Fuzzy Objective Function Algoritms”, Plenum Press, New York

基于最小化下面的目标函数:

J m = ∑ i = 1 N ∑ j = 1 C u i j m ∣ ∣ x i − c j ∣ ∣ 2 J\_m = \\sum^\{N\}\_\{i=1\}\{\\sum^\{C\}\_\{j=1\}\{u\_\{ij\}^m||x\_i-c\_j||^2\}\} Jm=i=1∑Nj=1∑Cuijm∣∣xi−cj∣∣2

*  m是任何大于1的实数
 *   u i j u\_\{ij\} uij是 x i x\_i xi在类j上隶属度
 *  其中 x i x\_i xi是第i个d维测量向量
 *   c j c\_j cj是一个d维的类中心

FCM主要通过迭代更新u和c来得到最终的解。

迭代终点一般选取两个：

*  当u变化的无穷范数小于某个值时
 *  当迭代次数达到某个极限时候

这个过程可能会收敛到局部最小值或者是鞍点上

## 算法流程 ##

1.  初始化矩阵U （描述每个点在不同的类中的概率）
2.  通过U算类中心  
     C j = ∑ i = 1 N u i j m ∗ x i ∑ i = 1 N u i j m C\_j=\\frac\{\\sum^\{N\}\_\{i=1\}\{u\_\{ij\}^m \* x\_i\}\}\{\\sum^\{N\}\_\{i=1\}\{u\_\{ij\}^m\}\} Cj=∑i=1Nuijm∑i=1Nuijm∗xi
3.  更新U，通过之前算出来的类中心  
     u i j = 1 ∑ k = 1 C ( ∣ ∣ x i − c j ∣ ∣ ∣ ∣ x i − c k ∣ ∣ ) 2 m − 1 u\_\{ij\} = \\frac\{1\}\{\\sum^\{C\}\_\{k=1\}\{(\\frac\{||x\_i-c\_j||\}\{||x\_i-c\_k||\})^\{\\frac\{2\}\{m-1\}\}\}\} uij=∑k=1C(∣∣xi−ck∣∣∣∣xi−cj∣∣)m−121
4.  如果u变化的无穷范小于某个值的时候，就停下来，否者就转到第2步

> 之前也写过这个算法，当时是用其他用途有点赶，就没有仔细研究。  
> 现在自己仔细研究了一轮之后，实现了这个算法，大概只用20行左右就可以完成这个算法**FCM**，相比之前的在github上看到的100行左右的代码，这个简直可以说是改进大了很多。

## Python 实现 ##

import numpy as np
    
    def FCM(X, c_clusters=3, m=2, eps=10):
        membership_mat = np.random.random((len(X), c_clusters))
        membership_mat = np.divide(membership_mat, np.sum(membership_mat, axis=1)[:, np.newaxis])
    
        while True:
            working_membership_mat = membership_mat ** m
            Centroids = np.divide(np.dot(working_membership_mat.T, X), np.sum(working_membership_mat.T, axis=1)[:, np.newaxis])
            
            n_c_distance_mat = np.zeros((len(X), c_clusters))
            for i, x in enumerate(X):
                for j, c in enumerate(Centroids):
                    n_c_distance_mat[i][j] = np.linalg.norm(x-c, 2)
            
            new_membership_mat = np.zeros((len(X), c_clusters))
            
            for i, x in enumerate(X):
                for j, c in enumerate(Centroids):
                    new_membership_mat[i][j] = 1. / np.sum((n_c_distance_mat[i][j] / n_c_distance_mat[i]) ** (2 / (m - 1)))
            if np.sum(abs(new_membership_mat - membership_mat)) < eps:
                break
            membership_mat =  new_membership_mat
        return np.argmax(new_membership_mat, axis=1)

*  终止条件那个可以再优化下，但基本框架就是这样。

**使用：**

*  导入数据：

from sklearn import datasets
    
    iris = datasets.load_iris()

*  评估

def evaluate(y, t):
        a, b, c, d = [0 for i in range(4)]
        for i in range(len(y)):
            for j in range(i+1, len(y)):
                if y[i] == y[j] and t[i] == t[j]:
                    a += 1
                elif y[i] == y[j] and t[i] != t[j]:
                    b += 1
                elif y[i] != y[j] and t[i] == t[j]:
                    c += 1
                elif y[i] != y[j] and t[i] != t[j]:
                    d += 1
        return a, b, c, d
    
    def external_index(a, b, c, d, m):
        JC = a / (a + b + c)
        FMI = np.sqrt(a**2 / ((a + b) * (a + c)))
        RI = 2 * ( a + d ) / ( m * (m + 1) )
        return JC, FMI, RI
    
    def evaluate_it(y, t):
        a, b, c, d = evaluate(y, t)
        return external_index(a, b, c, d, len(y))

*  测试

test_y = FCM(iris.data)

*  得到评估

evaluate_it(iris.target, test_y)

对于这三个指数来说，效果高了很多。

(0.7487508922198429, 0.856326530612245, 0.8935099337748345)

*  画图

from sklearn.decomposition import PCA
    import numpy as np
    import matplotlib.pyplot as plt
    
    X_reduced = PCA(n_components=2).fit_transform(iris.data)
    plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=test_y, cmap=plt.cm.Set1)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]

*  原图：

plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=iris.target, cmap=plt.cm.Set1)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 1]

图片上也能看到效果比其他的都要好，而且，经过测试发现，FCM算法会比KMeans更加稳定（很多，很多倍）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]: /images/20220218/ccf1009e7f0b4a09b4788ad01d26883f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 1]: /images/20220218/cc4b0482e11e421d8432dc61194247d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 2]: /images/20220218/1da7741c0532406ebd84aa29fdbca0c6.png