论文研究-模糊C-均值聚类算法的优化.pdf

所需积分/C币:20 2019-09-07 05:14:28 559KB .PDF

针对传统模糊C-均值聚类算法(FCM算法)初始聚类中心选择的随机性和距离向量公式应用的局限性,提出一种基于密度和马氏距离优化的模糊C-均值聚类算法(Fuzzy C-Means Based on Mahalanobis and Density,FCMBMD算法)。该算法通过计算样本点的密度来确定初始聚类中心,避免了初始聚类中心随机选取而产生的聚类结果的不稳定;采用马氏距离计算样本集的相似度,以满足不同度量单位数据的要求。实验结果表明,FCMBMD算法在聚类中心、收敛速度、迭代次数以及准确率等方面具有良好的效果。
126 015,51(11) Computer Engineering and Applications计算机工程与应用 类中心选取的流程如下 33 FCMBMD算法描述 (1)假设有n个用户,对s个项目进行评分,用n个 将基于密度和距离的两种优化方法相结合得到 s维的间量X,X2…,Xn来表示。通过公式(4)来计算 FCMBMD(FuzC- Means based on mahalanobis and 每个样本点的密度值得出高密度样本点集合D。 entity)算法。 FCMBMD聚类算法步骤如下: (2)在D中选择密度最大的样本点作为第1个聚类 (1)使用公式(4)计算每个数据点的密度值,比较所 中心 有数据点的密度值,挑选出密度函数值最大的样本点 (3)由公式(6)对每个用户的密度值进行修正。接找到适当数量的初始中心点。 着从D中选出距离x,最远的样本点作为第2个聚类中 (2)设置模糊指数m,m>1 心x2。然后分别计算D中剩余样本点与x,x2的距离, (3)选择停止参数h。 从中选出最大值作为第3个聚类中心x1:依次如此进 (4)设定d的值,通过公式6)得到根据设定的参 行,选取C个初始聚类中心。 数所找到的初始中心点。 通过以上三个步骤将密度函数引入到初始聚类中 (5)假设聚类的迭代次数用k来表示,k=0,1, 心的选取中得到∫基于密度计算方法的模糊C-均值算2,…。对于第k次迭代,通过公式(10)计算各用户与 法( Fuzzy C- Means Based on Density, FCMBD算法)。 各聚类中心的距离值d 32距离度量的优化 (6)基于聚类中心距离和距离函数,计算隶属度矩 传统的模糊C均值算法采用的是欧氏距离即欧几 里德距离( Euclidean distance)。该距离公式衡量的是 (7)计算聚类中心矩阵C。 多维空间中各个点之间的绝对距离。在聚类算法中距 (8)根据求属度矩阵U对用户来进行聚类,对Vx 离函数用来计算各个用户到聚类簇中心的距离,表示用C表示第k个用户簇,当CAk=max(un)1≤j≤c}, 广隶属于该聚类簇的程度。欧式距离函数公式如下:x∈C成立的时候,就将第;个用户分到第k个用户簇中 dist(X, Y)=o-y) (9) FCMBMD算法采用密度两数找到密度高的样本点 作为初始聚类中心,并且使用了马氏距离作为计算样本 欧氏距离需要保证各维度指标在相同的刻度级别,点之间的相似度的方法,不仅避免了结果因为初始值选 比如对身高(cm)和体重(kg)两个单位不同的指标使用取的随机性而导致的不稳定,同吋也避免了使用欧拉公 欧式距离可能使结果失效。它将样本的不同属性(即各式计算样本之间相似度无法考虑到各种特性之间的联 种指标或变量)之间的差别等同对待,这一点不能够满系的问题,使得样本相似性计算的距离空间是凸的,避 足实际需求。所以在些数据集中,采用欧式距离来度免了可能存在的一些孤立点 量,不能得到好的效果 这里引用由印度统计学家马哈拉诺比斯(PC.4实验结果分析 Mahalanobis9提出的马氏距离它是种有效的计算41实验环境 两个未知样本集的相似度的方法。与欧氏距离不同的 实验选取的数据集是来自加州大学欧文分校UCI 是它考虑到各种特性之间的联系。它使用总体协方差( University of California,ine)提出的用于机器学习 矩阵的逆来计算样本之间的距离,使得样个相似性计算的数据库。从UCI数据库屮挑选了4组数据集01,用 的距离空间是凸的,避免了可能存在的一些孤立点。 它们来进行算法测试,实验数据集如表1所示,分别是 马氏距离满条件:有n个样本,如果用d表示第 Balance scale数据集、RlS数据集、 Nursery数据集和 i个样本和第j个样本之间的距离,那么对一切Adut数据集。为方便实验结果比较,所选数据集 Balance 1≤i≤n,满足如下四个条件:(1)当且仅当氵=j吋, Scale和IRlS为小数据集,它们属性数量较少; Nursery d=0;(2)d>0;(3)d=d;(4)d1≤d+d。其中,和Adut为大数据集,它们属性数量较多。 X和X分别为第i个和第j个样本的m个指标所组成 表1实验数据集 的向量,S为样本总体的协方差矩阵 数据集名称 属性个数样本个数 说明 Balance scale数据集 大平标尺数据 X-X)S"(X-X) (10) IRIS数据集 鸢尾花数据 将模糊C均值聚类算法中的欧式距离使用上面介 Nursery数据集 12960托儿所幼儿数据 绍的马氏距离来代替,使得算法更符合实际数据的需Ad数据集144842成人收入数据 求,可聚类中可检测超球体,并称优化的算法为 FCMBM 实验使用weka软件进行算法性能的比较。它是基 ( Fuzzy C- Means Based on Mahalanobis算法 于Jaⅵa环境下开源的机器学习以及数据挖掘软件。通过 熊拥军,刘卫国,欧鹏杰:模糊C-均值聚类算法的优化 2015,51(11)127 参考weka接口文档,来编写的聚类算法(FCM、 FCMBD、中心值v=(3.42、4.18、4.21、3.37)。将 Balance scale FCMBM和 FCMBMD算法)进行聚类测试 数据集分别使用FCM、 FCMBD、 FCMBM以及 FCMBMD 4.2聚类正确性比较 算法来得到初始聚类中心,结果如表6所示。 对以上 Balance Scale、IRIS、 Nursery和 Adult数据 表6采川不同聚类算法得到的聚类中心 集,分别使用FCM算法、 FCMBD算法、 FCMBV算法以 算法名称聚类中心 及 FCMBMD算法进行30次测试,取其均值得到4种聚 H1=(405、3.64、2.75、3.77) 类算法的正确率,如表2、表3、表4和表5所示。 FCM 12=(2.45、3.654.85432) 13-(2.75、3.653.572.44) 表2 Balance scale数据集聚类正确性比较 H1=(3.794.35、2.75、3.22) 算法名称样本点 聚类 聚类 正确率/% FCMBD F2=(1.77、3.36、3.71、4.65) 总数日正确数日错误数日 3-(3.664.32、4.l7、3.23) FCM 671 598 1=(3.554.39、2.08、3.30) FCMBD 671 8956 FCMBM 12-(2.122.74、369、477) MBM 626 93.29 3=(3.394.094.18,3.32) FCMBMD 671 642 29 95.68 1=(348、429、2.18、328) 表3IRIS数据集聚类正确性比较 FCMBMD 2=(1.92.88、3.71、4.80) 样本点聚类聚类 3(3.39、409、4.16、3.35) 算法名称 总数日正确数日错误数日 从表6可知,四种模糊聚类算法的聚类中心都在 FCM 81.33 Balance scale数据集的实际屮心附近,但 FCMBMD算 FCMBD 83.33 FCMBM 91.33 法的值更接近实际中心 FCMBMD 133 17 8867 4.4迭代次数和收敛性比较 表4 Nursery数据集聚类正确性比较 对于聚类算法而言,聚类结果的正确率是一个重要 样本点聚类聚类 的指标,但是仅将聚类结果的正确率作为评价算法优劣 算法名称 下确率/% 总数目正确数目错误数目 的指标会显得单一。对目标函数进行迭代运算的算法, FCM 8654 4306 66.77 其迭代的次数以及其收敛速度也是算法评价的重要指 FCMBD 2 960 9032 3928 6969 标。特别是在大量数捃的情况下,如果迭代次数过多、 FCMBM12960101152845 78.05 收敛速度差就不能够很好地满足要求 FCMBMD 12 960 9456 3504 对 FCMBD聚类算法与FCM聚类算法在收敛速度 表5 adult数据集聚类正确性比较 上进行实验比较,实验分别采川 Balance scalc、IRIS、 算法名称样本点聚类 聚类 总数日正确数日错误数日下确率 Nursery和 Adult数据集进行30次迭代测试取均值得 到的。各算法与相应的数据集在迭代次数递增的情况 FCM4884235765 卜,其目标兩数值变化的曲线如图1、图2、图3和图4 FCMBL4884238451 10391 78.73 所示。 FCMBM488424203 6808 86.06 FCMBML4884240785 8U57 83.51 0000 800 对表2表3表4和表的数据进行分析,可以得到600 以下结论:对于样本点总数目和属性较多的数据集(如400 ,,+ FCMBD算 Nursery和Adul数据集), CMBMD算法的聚类正确性 正2001 比FCM算法更好,但比 FCMBM算法略低。对于样本点 0三c丈只≌8另 迭代次数 数日较少且属性不多的数据集, FCMBMD算法比传统的 图1 FCMBD和FCM算法在 Balance scale数据集收敛性比较 FCM算法聚类正确率要高,甚至比 FCMBM算法正确率 还要高,如 Balance sc数据集。总体来说 FCMBMD=3 算法在四组测试数据集中表现了良好的聚类效果 家250 图200 CMBD算法 4.3聚类中心结果比较 长150 FCM算法 100 以 Balance scale数据集为例,该数据集的实际聚类 50 0 中心值为:L类聚类中心值V1=(352425236、312); 寸∞99C过≌8:只 达代次数 R类聚类中心值v2=(2.18、2.98、3.75、485);B类聚类图2CMBD和FCM算法在取Rs数据集的收敛性比较 128 015,51(11) Computer Engineering and Applications计算机工程与应用 12000 类结果更为稳定。采用马氏距离度量取代原有的欧氏 想10000 氣8000 距离度量计算样本的相似度,马氏距离使用总体协方差 怪6000 FCMBD算法 4000 FCM算法 矩阵的逆来计算样本之间的距离,使得样本相似性计算 2000 的距离空间是凸的,避免了可能存在的一些孤立点和局 0 部极值。实验结果表明 FCMBMD算法相对于传统的 26101418222630 迭代次数 FCM算法有更好的聚类效果 图3 FCMBD和FCM算法在 Nursery数据集的收敛性比较 18000 参考文献: 140 [1]高新波模糊聚类分析及应用[M]西安:西安电子科技大学 出版社,2004 度000 FCMBD算法 000 2] Han jiawei, Kamber m数据挖掘概念与技术[M].北京:机 6000 FCM算法 械工业出版社,2003 4000 2000 [3 Gustafson DE, Kessel w C Fuzzy clustering with fuzzy covariance matrix[C]Proceedings of the IEEE CDC, 1979 代次数 761-766 图4 FCMBD和FCM算法在 Adult数据集的收敛性比较 [4]蔡威,程俊杰基于减法聚类的GK模糊聚类研究[兰州 以上在类别数、属性数和样本数不同数据集上进行 交通大学学报,2011,30(6):50-54 测试的实验结果表明,不论是在数据集数目较少的IRs5孙静基于模糊聚类的电子商务协同过滤推荐研究[D]天 和 Balance scale数据集,或是数较多的 Nursery和 沣:河北工业大学,2010. Adult数据集, FCMBD算法与FCM算法虽然在算法结[61李杰基于模糊技术的制造单元构建方法及其在变压器企 业中的应用[D]天津:河北工业大学,2002 束时的目标函数值非常接近,但 FCMBD算法的收敛速 []孙吉贵,刘杰,赵连宇聚类算法研究[软作学报,208,19 度明显要快于FCM算法,而且迭代次数要少。由此可 (1):48-61 得, FCMBD算法比FCM在稳定性以及收敛性要更好。 [8]杨艺芳,丁正生混合模聚类法在故障诊断中的应用[J. 将 FCMBD算法与 FCMBM算法结合起来得到 计算机工程与设计,2008,29(14):3785-3787 FCMBMD算法,并选取 Balance Scale数据集、 Nursery[9诸克军,苏顺华,黎金玲模糊C均值中的最优聚类与最佳 数据集、IRIS数据集和Ad吐t数据集对该算法进行测 聚类数[J系统工程理论和实践,2005,25(3):52-61 试。其测试结果如表7所示。 [10 Liu Wenyuan, Xiao Chunjing. Study on combining subtrac 表7 FCMBMD算法在数据集上测试结果 tive clustcring with fuzzy c-mcans clustcring[]. Machinc 数据集 IRIs Balance Scale Nursery Adult Learning and Cybernetics, 2003, 5(5): 2659-2662 名称 数据集数据集数据集数据集 [l]l李鑫,张继福,祭江辉.一种基于大密度区域的模糊聚类 迭代次数 9 18 算法[J小型微型计算机系统,2012,33(6:50-58. 聚类止确性‰88.67 95.68 729683.51 [12 Xu R, Wunsch D Survey of clustering algorithmsJIEEE 由表7可知 FCMBMD算法结合了 FCMBD算法以 Transactions on Neural Networks, 2005, 16(3): 645-678 及 FCMBM算法的优点在聚类的正确性以及迭代次数 [13]Berget I, Mevik B H New modifications and applica- 两方面都优于FCM算法,达到了算法优化的目的。 ons of fuzzy C-means methodology[J]. Computational Statistics and Data Analysis, 2008, 52(5): 2403-2418 [14]Cai W L, Chen S C, Zhang D Q Fast and robust fuzzy 5结束语 c-mcans clustcring algorithms incorporating local infor FCMBMD算法针对FCM算法中初始聚类中心选 mation for image segmentation[J]. Pattern Recognition 择的随机性以及距离度量函数对于孤立点的敏感性的 2007,40(3):120-128 问题,提出基于密度函数和马氏距离度量函数的优化方[15]刘兵,夏士雄,周勇,等基于样本加权的可能性模糊聚类 法。根据样本点的密度预先确定初始聚类中心,使得聚 算法门电了学报,2012,40(2):70-78

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐