FCM算法

全名为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=\sum _{i=1}^N\sum _{j=1}^C{u}_{ij}^m||x_i-c_j|{|}^2$$

• m是任何大于1的实数
• $u_{ij}$是$x_i$在类j上隶属度
• 其中$x_i$是第i个d维测量向量
• $c_j$是一个d维的类中心

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

迭代终点一般选取两个：

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

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

算法流程

1. 初始化矩阵U （描述每个点在不同的类中的概率）
2. 通过U算类中心
   $$C_j=\frac{{\sum }_{i=1}^N{u}_{ij}^m\ast x_i}{{\sum }_{i=1}^N{u}_{ij}^m}$$
3. 更新U，通过之前算出来的类中心
   $$u_{ij}=\frac{1}{{\sum }_{k=1}^C(\frac{||x_i-c_j||}{||x_i-c_k||}{)}^{\frac{2}{m-1}}}$$
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.98429, 0.2245, 0.48345)

• 画图

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) 

• 原图：

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

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