当前位置:首页 » 《休闲阅读》 » 正文

模糊C均值聚类(Fuzzy C-means,FCM)算法(Python3实现)

10 人参与  2024年12月04日 14:01  分类 : 《休闲阅读》  评论

点击全文阅读


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

一、FCM算法简介

1、模糊集理论

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

2、FCM算法

模糊C均值聚类(Fuzzy C-means)算法简称FCM算法,是软聚类方法的一种。FCM算法最早由Dunn在1974年的期刊“Journal of Cybernetics”文献中提出,文献为“A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters”,然后在1984年经 Bezdek于“Computers & Geosciences”推广,原始文献为“FCM: The fuzzy c-means clustering algorithm”。

硬聚类算法在分类时有一个硬性标准,根据该标准进行划分,分类结果非此即彼。
软聚类算法更看重隶属度,隶属度在[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 X_i Xi​是第 i i i个特征向量; X i j X_{ij} Xij​是 X i Xi Xi的第 j j j个属性。每个样本包含 d d d个属性。FCM算法可以将该数据集划分为 K K K类, K K K为大于1的正整数,其中 K K K个类的聚类中心分别为 [ v 1 , v 2 , … , v n ] [v_1,v _2,…,v_n] [v1​,v2​,…,vn​]。
FCM的目标函数和约束条件如下:

J ( U , V ) = ∑ i = 1 n ∑ j = 1 k u i j m d i j 2 J(U,V)=\displaystyle\sum_{i=1}^{n} \displaystyle\sum_{j=1}^{k} u_{ij}^md_{ij}^2 J(U,V)=i=1∑n​j=1∑k​uijm​dij2​

∑ j = 1 k u i j = 1 , u i j ∈ [ 0 , 1 ] \displaystyle\sum_{j=1}^{k} u_{ij}=1, u_{ij}∈[0,1] j=1∑k​uij​=1,uij​∈[0,1]

其中, u i j u_{ij} uij​是样本点 x i x_i xi​与聚类中心 v j v_j vj​的隶属度,m是模糊指数(m>1), d i j d_{ij} dij​是样本点 x i x_i xi​与聚类中心 v j v_j vj​的距离,一般采用欧氏距离。聚类即是求目标函数在约束条件的最小值。FCM 算法通过对目标函数的迭代优化来取得对样本集的模糊分类。

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

u i j = 1 ∑ c = 1 k ( d i j d i k ) 2 m − 1 u_{ij}=\frac{1}{\displaystyle\sum_{c=1}^{k} (\frac{d_{ij}}{d_{ik}}) ^\frac{2}{m-1}} uij​=c=1∑k​(dik​dij​​)m−12​1​

v j = ∑ i = 1 n u i j m x i ∑ i = 1 n u i j m v_j=\frac{\displaystyle\sum_{i=1}^{n} u_{ij}^m x_i }{\displaystyle\sum_{i=1}^{n} u_{ij}^m } vj​=i=1∑n​uijm​i=1∑n​uijm​xi​​

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,最大迭代次数T
输出:聚类中心 V = [ v 1 , v 2 , … , v c ] V=[v_1,v _2,…,v_c] V=[v1​,v2​,…,vc​], 隶属度矩阵U
Step1:设置聚类数目c
Step2:初始化模糊因子m、迭代允许的误差ε、迭代次数t=0和隶属度矩阵U(0),从样本中随机选取c个样本作为初始聚类中心;
Step3:根据公计算或更新隶属度矩阵U,并更新聚类中心;
Step4:比较 J ( t ) J(t) J(t)和 J ( t − 1 ) J{(t-1)} J(t−1) ;若 ∣ ∣ J t − J ( t − 1 ) ∣ ∣ ≤ ε || J{t} - J{(t-1)} || ≤ ε ∣∣Jt−J(t−1)∣∣≤ε,则满足迭代停止条件,迭代停止。否则置 t = t + 1 t=t+1 t=t+1,返回Step3,继续迭代。

FCM流程图如下:
在这里插入图片描述

5、FCM算法步骤伪代码

输入:聚类数目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,最大迭代次数T
输出:聚类中心 V = [ v 1 , v 2 , … , v c ] V=[v_1,v _2,…,v_c] V=[v1​,v2​,…,vc​], 隶属度矩阵U

begin01.V ← Ø, U ← Ø, t ← 0 // 初始化聚类中心V、隶属度矩阵U和迭代次数t02.while t < T do 03.   for i ← 1 to n do04.      for j ← 1 to c do05.         calculate uij  //根据公式计算隶属度06.         U[i][j]= uij  //更新隶属度矩阵07.      end for08.   end for09.   for j ← 1 to c do 10.       calculate vj  //根据隶属度和公式计算聚类中心点11.   end for12.   calculate J  //根据公式重新计算目标函数J13.   t += 114.   if ||J(t) - J(t-1)|| ≤ ε then15.      return V,U16.   end if17.end while18.return V,Uend

6、时间复杂度分析

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

7、FCM算法的优缺点

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

FCM算法优点:

FCM算法引入隶属度后,由于每个值对各类中心点都有贡献,因此中心点的迭代更易达到全局最优;FCM算法可以发现属于多个簇的数据点,这对于图像处理等应用来说非常有用;

FCM算法缺点:

FCM算法需要提前设定簇的数量C,并且C值的选取不好把握,同时需要选择合适的模糊参数m,通常情况下,C值和m值需要依据经验和对数据集的理解指定,因此指定的数值未必理想,聚类的结果也就无从保证;FCM算法对噪声和异常值敏感,聚类结果容易受到噪声点的影响;FCM算法采用欧氏距离进行相似性度量,适用于簇是凸的或球形的数据集,在非凸形数据集中难以达到良好的聚类效果;FCM算法的初始中心点选取上采用的是随机的方法。FCM算法极为依赖初始中心点的选取,一旦错误地选取了初始中心点,对于后续的聚类过程影响极大,很可能得不到最理想的聚类结果,同时聚类迭代的次数也可能会增加。而随机选取的初始中心点具有很大的不确定性,也直接影响着聚类的效果。FCM算法计算隶属度矩阵的复杂度较高,不适合处理大数据集。

二、代码实现(Python3)

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

数据集样本数属性维度类别个数
Iris15043
Wine17833
Seeds21073

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

1、Python3代码实现

from pylab import *import pandas as pdimport numpy as npimport operatorimport mathimport matplotlib.pyplot as pltimport matplotlib.colors as mcolorsimport randomfrom sklearn.decomposition import PCAfrom sklearn.preprocessing import LabelEncoderfrom sklearn.metrics import normalized_mutual_info_score  # NMIfrom sklearn.metrics import rand_score  # RIfrom sklearn.metrics import accuracy_score  # ACCfrom sklearn.metrics import f1_score  # F-measurefrom sklearn.metrics import adjusted_rand_score  # ARI# 数据保存在.csv文件中iris = pd.read_csv("dataset/iris.csv", header=0)  # 鸢尾花数据集 Iris  class=3wine = pd.read_csv("dataset/wine.csv")  # 葡萄酒数据集 Wine  class=3seeds = pd.read_csv("dataset/seeds.csv")  # 小麦种子数据集 seeds  class=3wdbc = pd.read_csv("dataset/wdbc.csv")  # 威斯康星州乳腺癌数据集 Breast Cancer Wisconsin (Diagnostic)  class=2glass = pd.read_csv("dataset/glass.csv")  # 玻璃辨识数据集 Glass Identification  class=6df = 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  # 属性数量(数据集维度)# 初始化模糊矩阵Udef 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)

2、聚类结果分析

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

F值结合了精度(Precision)与召回率(Recall)两种指标,它的值为精度与召回率的调和平均,其计算公式见公式:

P r e c i s i o n = T P T P + F P Precision=\frac{TP}{TP+FP} Precision=TP+FPTP​

R e c a l l = T P T P + F N Recall=\frac{TP}{TP+FN} Recall=TP+FNTP​

F − m e a s u r e = 2 R e c a l l × P r e c i s i o n R e c a l l + P r e c i s i o n F-measure=\frac{2Recall \times Precision}{Recall+Precision} F−measure=Recall+Precision2Recall×Precision​

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

A C C = T P + T N T P + T N + F P + F N ACC=\frac{TP+TN}{TP+TN+FP+FN} ACC=TP+TN+FP+FNTP+TN​

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

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

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

其中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_indexF_measure, ACC, NMI, RI = clustering_indicators(labels_number, labels)print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI)

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

3、聚类结果

鸢尾花数据集Iris
Iris鸢尾花数据集原图 Iris鸢尾花数据集原图

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

Iris鸢尾花数据集FCM聚类效果图 葡萄酒数据集Wine

Wine葡萄酒数据集原图

Wine葡萄酒数据集原图

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

Wine葡萄酒数据集FCM聚类效果图 小麦种子数据集Seeds

在这里插入图片描述

Seeds小麦种子数据集原图

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

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

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/196492.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1