模糊C均值聚类（Fuzzy C-means）算法（FCM）_模糊c均值聚类算法

本文的代码与数据地址已上传至github：https://github.com/helloWorldchn/MachineLearning

一、FCM算法简介

1、模糊集理论

L.A.Zadeh在1965年最早提出模糊集理论，在该理论中，针对传统的硬聚类算法其隶属度值非0即1的严格隶属关系，使用模糊集合理论，将原隶属度扩展为 0 到 1 之间的任意值，一个样本可以以不同的隶属度属于不同的簇集，从而极大提高了聚类算法对现实数据集的处理能力，由此模糊聚类出现在人们的视野。FCM算法广泛应用在数据挖掘、机器学习和计算机视觉与图像处理等方向。

2、FCM算法

模糊C均值聚类（Fuzzy C-means）算法简称FCM算法，是软聚类方法的一种。FCM算法最早由Dunn在1974年提出然后经 Bezdek推广。

硬聚类算法在分类时有一个硬性标准，根据该标准进行划分，分类结果非此即彼。
软聚类算法更看重隶属度，隶属度在[0,1]之间，每个对象都有属于每个类的隶属度，并且所有隶属度之和为 1，即更接近于哪一方，隶属度越高，其相似度越高。

3、算法思想

模糊 C-均值聚类（FCM）算法一种软聚类的聚类方法，该方法的思想使用
隶属度来表示每个数据之间的关系，从而确定每个数据点属于的聚类簇的聚类方法。同时 FCM 算法也是一种基于目标函数的算法，给定含有n个数据的数据集： X = { x 1 , x 2 , … x i , … , x n } X=\left\{\right.x_1,x_2,…x_i,…,x_n\left\}\right. X={x1​,x2​,…xi​,…,xn​}，$X_i$是第$i$个特征向量;$X_{ij}$是$Xi$的第$j$个属性。每个样本包含$d$个属性。FCM算法可以将该数据集划分为$K$类，$K$为大于1的正整数，其中$K$个类的聚类中心分别为$[v_1,v_2,\dots ,v_n]$。
FCM的目标函数和约束条件如下：

$$J(U,V)=\sum _{i=1}^n\sum _{j=1}^k{u}_{ij}^m{d}_{ij}^2$$

$$\sum _{j=1}^k{u}_{ij}=1,u_{ij}\in [0,1]$$

其中，$u_{ij}$是样本点$x_i$与聚类中心$v_j$的隶属度，m是模糊指数（m>1），$d_{ij}$是样本点$x_i$与聚类中心$v_j$的距离，一般采用欧氏距离。聚类即是求目标函数在约束条件的最小值。FCM 算法通过对目标函数的迭代优化来取得对样本集的模糊分类。

为使目标函数 J 取得最小值，在满足约束条件的情况下对目标函数使用拉格朗日（Lagrange）乘数法，得到隶属度矩阵U和聚类中心$v_j$。

$$u_{ij}=\frac{1}{\sum _{c=1}^k(\frac{d_{ij}}{d_{ik}}{)}^{\frac{2}{m-1}}}$$

$$v_j=\frac{\sum _{i=1}^n{u}_{ij}^m{x}_i}{\sum _{i=1}^n{u}_{ij}^m}$$

4、算法步骤

算法的具体描述如下：

输入：聚类数c，初始聚类中心 X = { x 1 , x 2 , … x i , … , x n } X=\left\{\right.x_1,x_2,…x_i,…,x_n\left\}\right. X={x1​,x2​,…xi​,…,xn​}，模糊指标m，终止误差
输出：聚类中心$V=[v_1,v_2,\dots ,v_c]$，隶属度矩阵$u_{ij}$
Step1：设置聚类数目c；
Step2：初始化模糊因子m、迭代允许的误差ε、迭代次数t=0和隶属度矩阵U(0)，从样本中随机选取c个样本作为初始聚类中心；
Step3：根据公计算或更新隶属度矩阵U，并更新聚类中心；
Step4：比较$J(t)$和 $J(t-1)$ ；若$||Jt-J(t-1)||\le \epsilon$，则满足迭代停止条件，迭代停止。否则置$t=t+1$，返回Step3，继续迭代。

伪代码如下：

输入：聚类数目c，数据集$X=\left\{\right.x_1,x_2,…x_i,…,x_n\left\}\right.$，停止阈值*ε*，模糊因子*m*，最大迭代次数*T*；
输出：聚类中心$V=[v_1,v _2,…,v_c]$, 隶属度矩阵*U*；
begin
1. V ← Ø, U ← Ø, t ← 0 // 初始化聚类中心V、隶属度矩阵U和迭代次数t
2. while t < T do 
3.    for i ← 1 to n do
4.       for j ← 1 to c do
5.          calculate uij  //根据公式(2-3)计算隶属度
6.          U[i][j]= uij  //更新隶属度矩阵
7.       end for
8.    end for
9.    for j ← 1 to c do 
10.       calculate vj  //根据隶属度和公式(2-4)计算聚类中心点
11.   end for
12.   calculate J  //根据公式(2-1)重新计算目标函数J
13.   t += 1
14.   if ||J(t) - J(t-1)|| ≤ ε then
15.      return V,U
16.   end if
17.end while
18.return V,U
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

FCM流程图如下：

5、时间复杂度分析

在有n个样本的d维数据集X中，数据集被划分成c个簇，如果本次聚类经过了t次迭代，每次迭代需要计算一次目标函数，计算过程中需要分别求出d维数据中c个簇的聚类中心与n个数据的距离，算法在此过程的时间复杂度为O(n∙c∙d)。隶属度矩阵需要计算c次距离，所以每轮迭代需要的时间复杂度为O(n∙c²d)。综上所述模糊C均值算法的时间复杂度为O(n∙c²∙t∙d)。但是由于在一般情况下类簇数目c、数据维度d以及算法的迭代次数t均可认为是常量，所以模糊C均值算法的时间复杂度可以简化为O(n)。由此可见，模糊C均值算法的时间复杂度随着数据点的数量增加呈线性增长，同时也受迭代次数、聚类簇数目以及数据维度的影响。

二、代码实现（Python3）

本文使用的数据集为UCI数据集，分别使用鸢尾花数据集Iris、葡萄酒数据集Wine、小麦种子数据集seeds进行测试，本文从UCI官网上将这三个数据集下载下来，并放入和python文件同一个文件夹内即可。同时由于程序需要，将数据集的列的位置做出了略微改动。数据集具体信息如下表：

数据集在我主页资源里有，免积分下载，如果无法下载，可以私信我。

1、Python3代码实现

from pylab import *
import pandas as pd
import numpy as np
import operator
import math
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors
import random
from sklearn.decomposition import PCA
from sklearn.preprocessing import LabelEncoder
from sklearn.metrics import normalized_mutual_info_score  # NMI
from sklearn.metrics import rand_score  # RI
from sklearn.metrics import accuracy_score  # ACC
from sklearn.metrics import f1_score  # F-measure
from sklearn.metrics import adjusted_rand_score  # ARI

# 数据保存在.csv文件中
iris = pd.read_csv("dataset/iris.csv", header=0)  # 鸢尾花数据集 Iris  class=3
wine = pd.read_csv("dataset/wine.csv")  # 葡萄酒数据集 Wine  class=3
seeds = pd.read_csv("dataset/seeds.csv")  # 小麦种子数据集 seeds  class=3
wdbc = pd.read_csv("dataset/wdbc.csv")  # 威斯康星州乳腺癌数据集 Breast Cancer Wisconsin (Diagnostic)  class=2
glass = pd.read_csv("dataset/glass.csv")  # 玻璃辨识数据集 Glass Identification  class=6

df = iris  # 设置要读取的数据集
# print(df)
columns = list(df.columns)  # 获取数据集的第一行，第一行通常为特征名，所以先取出
features = columns[:len(columns) - 1]  # 数据集的特征名（去除了最后一列，因为最后一列存放的是标签，不是数据）
dataset = df[features]  # 预处理之后的数据，去除掉了第一行的数据（因为其为特征名，如果数据第一行不是特征名，可跳过这一步）
original_labels = list(df[columns[-1]])  # 原始标签（最后一列）
attributes = len(df.columns) - 1  # 属性数量（数据集维度）


# 初始化模糊矩阵U
def initializeMembershipMatrix():
    num_samples = df.shape[0]
    membership_mat = np.random.rand(num_samples, c)
    membership_mat = membership_mat / np.sum(membership_mat, axis=1, keepdims=True)
    return membership_mat


# 计算类中心点
def calculateClusterCenter(membership_mat, c, m):
    cluster_mem_val = zip(*membership_mat)
    cluster_centers = list()
    cluster_mem_val_list = list(cluster_mem_val)
    for j in range(c):
        x = cluster_mem_val_list[j]
        x_raised = [e ** m for e in x]
        denominator = sum(x_raised)
        temp_num = list()
        for i in range(n):
            data_point = list(dataset.iloc[i])
            prod = [x_raised[i] * val for val in data_point]
            temp_num.append(prod)
        numerator = map(sum, zip(*temp_num))
        center = [z / denominator for z in numerator]  # 每一维都要计算。
        cluster_centers.append(center)
    return cluster_centers


# 更新隶属度
def updateMembershipValue(membership_mat, cluster_centers, c):
    #    p = float(2/(m-1))
    data = []
    for i in range(n):
        x = list(dataset.iloc[i])  # 取出文件中的每一行数据
        data.append(x)
        distances = [np.linalg.norm(list(map(operator.sub, x, cluster_centers[j]))) for j in range(c)]
        for j in range(c):
            den = sum([math.pow(float(distances[j] / distances[k]), 2) for k in range(c)])
            membership_mat[i][j] = float(1 / den)
    return membership_mat, data


# 得到聚类结果
def getClusters(membership_mat):
    cluster_labels = list()
    for i in range(n):
        max_val, idx = max((val, idx) for (idx, val) in enumerate(membership_mat[i]))
        cluster_labels.append(idx)
    return cluster_labels


# FCM算法
def fuzzyCMeansClustering(c, epsilon, m, T):
    start = time.time()  # 开始时间，计时
    membership_mat = initializeMembershipMatrix()  # 初始化隶属度矩阵
    t = 0
    while t <= T:  # 最大迭代次数
        cluster_centers = calculateClusterCenter(membership_mat, c, m)  # 根据隶属度矩阵计算聚类中心
        old_membership_mat = membership_mat.copy()  # 保留之前的隶属度矩阵，同于判断迭代条件
        membership_mat, data = updateMembershipValue(membership_mat, cluster_centers, c)  # 新一轮迭代的隶属度矩阵
        cluster_labels = getClusters(membership_mat)  # 获取标签
        if np.linalg.norm(membership_mat - old_membership_mat) < epsilon:
            break
        print("第", t, "次迭代")
        t += 1

    print("用时：{0}".format(time.time() - start))
    # print(membership_mat)
    return cluster_labels, cluster_centers, data, membership_mat


# 计算聚类指标
def clustering_indicators(labels_true, labels_pred):
    if type(labels_true[0]) != int:
        labels_true = LabelEncoder().fit_transform(df[columns[len(columns) - 1]])  # 如果标签为文本类型，把文本标签转换为数字标签
    f_measure = f1_score(labels_true, labels_pred, average='macro')  # F值
    accuracy = accuracy_score(labels_true, labels_pred)  # ACC
    normalized_mutual_information = normalized_mutual_info_score(labels_true, labels_pred)  # NMI
    rand_index = rand_score(labels_true, labels_pred)  # RI
    ARI = adjusted_rand_score(labels_true, labels_pred)
    return f_measure, accuracy, normalized_mutual_information, rand_index, ARI


# 绘制聚类结果散点图
def draw_cluster(dataset, centers, labels):
    center_array = array(centers)
    if attributes > 2:
        dataset = PCA(n_components=2).fit_transform(dataset)  # 如果属性数量大于2，降维
        center_array = PCA(n_components=2).fit_transform(center_array)  # 如果属性数量大于2，降维
    else:
        dataset = array(dataset)
    # 做散点图
    label = array(labels)
    plt.scatter(dataset[:, 0], dataset[:, 1], marker='o', c='black', s=7)  # 原图
    # plt.show()
    colors = np.array(
        ["#FF0000", "#0000FF", "#00FF00", "#FFFF00", "#00FFFF", "#FF00FF", "#800000", "#008000", "#000080", "#808000",
         "#800080", "#008080", "#444444", "#FFD700", "#008080"])
    # 循换打印k个簇，每个簇使用不同的颜色
    for i in range(c):
        plt.scatter(dataset[nonzero(label == i), 0], dataset[nonzero(label == i), 1], c=colors[i], s=7, marker='o')
    # plt.scatter(center_array[:, 0], center_array[:, 1], marker='x', color='m', s=30)  # 聚类中心
    plt.show()


if __name__ == "__main__":
    c = 3  # 聚类簇数
    T = 100  # 最大迭代数
    n = len(dataset)  # 样本数
    m = 2.00  # 模糊参数
    epsilon = 1e-5
    labels, centers, data, membership = fuzzyCMeansClustering(c, epsilon, m, T)  # 运行FCM算法
    F_measure, ACC, NMI, RI, ARI = clustering_indicators(original_labels, labels)  # 计算聚类指标
    print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI, "ARI", ARI)
    # print(membership)
    # print(centers)
    # print(dataset)
    draw_cluster(dataset, centers, labels)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

2、聚类结果分析

本文选择了F值（F-measure，FM）、准确率（Accuracy，ACC）、标准互信息（Normalized Mutual Information，NMI）和兰德指数（Rand Index，RI）作为评估指标，其值域为[0,1]，取值越大说明聚类结果越符合预期。

F值结合了精度（Precision）与召回率（Recall）两种指标，它的值为精度与召回率的调和平均，其计算公式见公式：

$$Precision=\frac{TP}{TP+FP}$$

$$Recall=\frac{TP}{TP+FN}$$

$$F-measure=\frac{2Recall\times Precision}{Recall+Precision}$$

ACC是被正确分类的样本数与数据集总样本数的比值，计算公式如下：

$$ACC=\frac{TP+TN}{TP+TN+FP+FN}$$

其中，TP（True Positive）表示将正类预测为正类数的样本个数，TN （True Negative）表示将负类预测为负类数的样本个数，FP（False Positive）表示将负类预测为正类数误报的样本个数，FN（False Negative）表示将正类预测为负类数的样本个数。

NMI用于量化聚类结果和已知类别标签的匹配程度，相比于ACC，NMI的值不会受到族类标签排列的影响。计算公式如下：

$$NMI=\frac{I\left(U,V\right)}{\sqrt{H\left(U\right)H\left(V\right)}}$$

其中H(U)代表正确分类的熵，H(V)分别代表通过算法得到的结果的熵。

其具体实现代吗如下：
由于数据集中给定的正确标签可能为文本类型而不是数字标签，所以在计算前先判断数据集的标签是否为数字类型，如果不是，则转化为数字类型

def clustering_indicators(labels_true, labels_pred):
    if type(labels_true[0]) != int:
        labels_true = LabelEncoder().fit_transform(df[columns[len(columns) - 1]])  # 如果标签为文本类型，把文本标签转换为数字标签
    f_measure = f1_score(labels_true, labels_pred, average='macro')  # F值
    accuracy = accuracy_score(labels_true, labels_pred)  # ACC
    normalized_mutual_information = normalized_mutual_info_score(labels_true, labels_pred)  # NMI
    rand_index = rand_score(labels_true, labels_pred)  # RI
    return f_measure, accuracy, normalized_mutual_information, rand_index


F_measure, ACC, NMI, RI = clustering_indicators(labels_number, labels)
print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI)
1
2
3
4
5
6
7
8
9
10
11
12

如果需要计算出聚类分析指标，只要将以上代码插入实现代码中即可。

3、聚类结果

1. 鸢尾花数据集Iris
   

Iris鸢尾花数据集原图

Iris鸢尾花数据集FCM聚类效果图

2. 葡萄酒数据集Wine

Wine葡萄酒数据集原图

Wine葡萄酒数据集FCM聚类效果图

3. 小麦种子数据集Seeds

Seeds小麦种子数据集原图

Seeds小麦种子数据集FCM聚类效果图

4、FCM算法的不足

FCM算法的核心步骤就是通过不断地迭代，更新聚类簇中心，达到簇内距离最小。算法的时间复杂度很低，因此该算法得到了广泛应用，但是该算法存在着许多不足，主要不足如下：

1. FCM聚类的簇数目需要用户指定。FCM算法首先需要用户指定簇的数目C值，C值的确定直接影响聚类的结果，通常情况下，C值需要用户依据自己的经验和对数据集的理解指定，因此指定的数值未必理想，聚类的结果也就无从保证。
2. FCM算法的初始中心点选取上采用的是随机的方法。FCM算法极为依赖初始中心点的选取：一旦错误地选取了初始中心点，对于后续的聚类过程影响极大，很可能得不到最理想的聚类结果，同时聚类迭代的次数也可能会增加。而随机选取的初始中心点具有很大的不确定性，也直接影响着聚类的效果。
3. FCM采用欧氏距离进行相似性度量，在非凸形数据集中难以达到良好的聚类效果。