基于Fisher判别的分布式K-Means聚类算法

彭长生

(江苏大学计算机科学与通信工程学院，江苏镇江212013)

所谓聚类(clustering)，是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程.聚类完成后所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异.目前传统的聚类算法主要是基于层次聚类和迭代的平方误差分区聚类两种方法［1］.在诸多的聚类算法中，K-Means是应用最广泛的算法之一.与其他算法相比，K-Means具有算法简单易实现且聚类效果稳定的特点.其算法思想大致如下:首先从n个数据对象X={x1，x2，…，xn}中任意选择k(k＜n)个对象作为初始聚类中心c1，c2，…，ck，而对于所剩下其他对象，则根据它们与这些聚类中心的欧式距离d(xi，cj)= ‖xi-cj‖(i=1，2，…，n;j=1，2，…，k)，分别将它们划分到与其最近的聚类.然后重新计算每个所获得的新聚类的聚类中心c*i=，(n表示属于类c的对象个数i=1，2，…，iik)，不断重复这一过程直到标准测度函数J=)收敛为止.

而当前随着网络和通讯技术的迅速发展和普及，各类企业、个人应用产生了大量自治的、分布式的数据.如何从大量分布数据源中进行有效的知识挖掘抽取，已经成为一个重要的研究课题.比如在建的大学数字图书馆国际合作计划［2］(China academic digital associative library，CADAL)整合了各种图书资源，在数字图书馆中，有大量的插图以及文本信息，同时包括来自互联网的相关图像、视频信息，要对这些数据进行有效的管理并提供好的检索服务，就需要分布式聚类技术对这些数据进行有效的分类、生成良好特征表达并创建索引.由于把如此巨大的海量数据全部集中到某一个中心服务器进行全局聚类在计算上是不可能的，因此很多学者在分布式聚类算法上做了大量研究.如文献［3-8］研究聚类的并行算法，通过将数据平摊到各个计算节点实现聚类的并行化.然而以上算法仅仅是实现了聚类的并行化，现实中存在数据隐私安全、传输代价等因素，以上算法并未考虑.

近年来，随着P2P(peer-to-peer)技术的广泛应用，文件共享、视频点播等诸多P2P网络应用［9］在互联网上日益兴盛.P2P网络上出现了越来越多的海量数据，同时由于P2P网络的高度自治特点，数据资源散落地分布在网络的各个节点上，研究适用于P2P分布式环境的分布式聚类算法可以有效解决P2P网络上大规模海量数据的挖掘和隐私保护，这引起学术界和工业界的广泛兴趣［10-15］.文献［10］提出 Probe/Echo算法，通过多次迭代发送Probe/Echo消息，完成整个网络的聚类.M.Dumitrescu等［11］提出了一种高维度数据上的集体式主成分分析法CPCA(collective principal component analysis)，该算法可与某种现成的聚类模块结合在一起，发展成一种分布式聚类.S.Nakahara等［12］构建了一种分层分布式对等聚类模型HP2PC(hierarchically peer-to-peer clustering)，该模型建立在一种多层覆盖网络之上，以模块化的方式分割聚类问题.Jin Ruoming 等［13］提出了 DFEKM(distributed fast and exact K-means clustering)算法，通过计算一个节点的聚类置信半径来消除边缘数据对聚类速度的影响，提高了分布式聚类效率.此外，国内的学者也对P2P网络上的分布式聚类进行了广泛研究.如张国印等［14］提出一种基于集成学习的分布式聚类思想.唐九阳等［15］提出一种 K-DmeansWM(K-Dmeans without master)算法，其特点在于每次计算时，都会自动去选择当前资源相对较好的节点进行聚类.王菁等［16］利用集合差异度实现基于内容聚类的P2P搜索模型提高查询效率和减少冗余消息，利用节点之间的集合差异度实现基于内容的聚类，既降低了查询时间，又减少了冗余消息.

为了减少网络中分布式聚类迭代的次数，降低网络中分布式聚类对带宽的消耗.DFEKM算法发现聚类中同一类数据分布上存在稀疏或稠密的现象，在聚类过程中通过保持稠密数据的类别属性不发生改变，而不考虑稀疏数据对聚类的影响，如此可提高分布式聚类过程中网络带宽资源的利用效率，并达到聚类精度很高的近似聚类效果.应用此原理，文中提出一种基于Fisher判别来确定置信半径的分布式K-Means聚类算法，通过应用Fisher线性判别确定节点在聚类过程中的置信半径，将此半径用以指导下一步的聚类，并将此算法与DFEKM聚类算法进行比较.

1 基于Fisher判别置信半径的分布式K-Means聚类算法

由于P2P网络上的分布式聚类算法大都需要在网络中多次迭代聚类，以使聚类达到稳定状态，存在着P2P网络带宽使用率高等问题.为此，文中根据数据在P2P网络节点中的分布的稀疏或稠密情况，提出一种基于 Fisher判别置信半径的分布式K-Means聚类算法，该算法应用Fisher线性判别比率找到同一类数据节点的稠密和稀疏分布，确定聚类的置信半径并指导下一步的聚类，从而可以用较少的迭代数使P2P网络上的聚类能快速达到稳定状态，减少了P2P网络在聚类过程中所需传递的网络流量.

1.1 Fisher线性判别率介绍

Fisher线性判别的基本思想［17］就是把空间中的数据点投影到一条直线上去，使得不同类的样本点在空间中能够形成互相分离的、且各自内部紧凑的集合.为了达到这样的分类效果，必须选择合适的投影直线，以最大限度地区分各类数据点的投影方向.

假设有n个d维数据样本X={x1，x2，…，xn}，它们分属于2个不同的类别，其中大小为n1的样本子集D1属于类别ω1，大小为n2的样本子集D2属于类别ω2.如果对X中的各个成分做线性组合，就得到一个标量点积y=WTX.Fisher线性可分性准则要求在投影y=WTX下，以下准则函数达到最大化.

式中:SB=(m1-m2)(m1-m2)T是总类间散布矩阵是该类样本均值;S=S+S是W12类内散布矩阵之和.使准则函数最大化的W必须满足SW=BλSWW.因为SBW总是位于m1-m2的方向上.由于W的模对问题无关紧要，因此易得使准则函数最大化时的W*即为

1.2 基于Fisher线性判别率的置信半径

根据以上Fisher判别准则，将之应用到本文研究:假设某一类数据共有N个数据对象，考虑将其分为两类问题，假设N个数据对象的中心为μ，对N个数据对象，分别计算其到中心的距离，并按照升序排列，得到一个按照距离排序的集合{di，i=1，2，…，N}，及其对应的数据对象集合为{Xi，i=1，2，…，N}.其中，Xi是第i个到中心距离最近的数据对象，其到中心的距离为di.Fisher线性判别率表示为

式中和分别为所有数据对象以Xr为分隔点的两个聚类均值距离以及距离方差和，即为

式中:μi是集合{di，i=1，2，…，r}的均值;类似地，μj是集合{di，i=r+1，r+2，…，N}的均值则是{di，i=1，2，…，r}的方差;是{di，i=r+1，r+2，…，N}的方差;JFisher(r)则是以{Xi，i=1，2，…，r}和{Xi，i=r+1，r+2，…，N}为两类的 Fisher线性判别率.所有数据对象集上的Fisher线性判别率越大，说明通过该方法得到的两类数据越明显，从而找到以聚类中心的数据稠密与稀疏的分界点，即当Fisher判别率最大时，假设为JFisher(R)，此时数据对象XR为聚类的最佳分隔数据点，所得置信半径为

1.3 基于置信半径的分布式K-Means聚类算法

文中采用Probe/Echo消息传递机制［10］来实现基于置信半径的分布式K-Means聚类.在网络中随机选择一个节点作为起始节点，然后随机选择k个数据作为初始聚类中心;初始节点将当前的聚类中心数据作为Probe消息转发给邻居节点，节点接收到Probe消息后向其邻居节点转发该Probe消息并更新其聚类中心;节点在发出Probe消息后就等待其邻居节点回发Echo消息，当一个节点接收到的消息总数等于其邻居数时，将接收到Echo消息中包含的聚类信息与自身节点的聚类信息进行合并同时更新Further变量的值，若该节点不是初始节点就回发Echo消息给前一个其发Probe消息的节点，若是初始节点就判断聚类是否结束，如果初始节点前后两次聚类中心的距离小于置信半径并且接收到Echo消息中所包含的Further变量均为false，则聚类迭代过程结束;否则重复上述过程.

以上是分布式聚类的整体迭代过程，网络中某个节点P更新聚类数据的具体算法过程如图1所示.

由图1可见，节点P等待从邻居节点接收消息，第1次接收到Probe消息时(假设发送此Probe消息的节点是Pa)，将接收到的消息数置1，并记Pa为节点P的父节点，然后将接收到的Probe消息转发给除节点Pa外的所有邻居节点并更新聚类中心并根据公式(2)-(5)计算新的置信半径，继续等待接收其他消息，每收到一条消息则消息数自增1，若节点P接收到的消息数等于其邻居节点数则首先判断是否需要进一步聚类，若节点P前后两次聚类中心的距离超过置信半径或者接收到Echo消息中所包含的Further变量不全为false，说明该节点或者其邻居节点需要进一步聚类将Further变量置true，否则将Further变量置false;然后合并节点聚类信息并向节点Pa发Echo消息，结束本节点的消息处理过程.合并节点聚类信息公式为

式中:cPj为节点P的第j类的聚类中心为节点P的第j类的类内数据对象数;cij为P的第i个邻居节点内第j个聚类的中心;wij为P的第i个邻居节点内第j个聚类的类内点数;Nb为P的邻居节点个数.

图1 节点消息处理流程图

2 试验结果

2.1 试验数据和度量标准

本试验在装有Intel Core Duo E7500处理器，内存为2 GB，安装了Windows 7系统的PC机上运行.采用java编程语言用栈来模拟Probe/Echo机制来进行分布式聚类，其中节点与节点之间的连接采用Gnutella协议［18］的随机连接拓扑结构.网络中设置了500个节点.本试验首先在3类2维高斯混合分布中取60 000个模拟数据作为试验数据，其参数设置如下:均值分别为(0，0)，(6，2)，(8，8);协方差矩阵均为二维单位矩阵;将60 000个模拟数据平均分配给500个网络节点;聚类的k值设为3.数据分布如图2所示.

图2 数据分布图

其次还采用了从LIBSVM［19］上下载的真实数据a8a和ijcnn进行试验，其中a8a含有22 696个123维数据，聚类的k值设为5，ijcnn中包含141 691个22维数据，聚类的k值设为12.

为评价数据聚类的效果，引入PMM(percentage membership mismatch)［18］作为衡量聚类精度的标准.PMM定义为

式中:Lcent(x)为数据点x通过集中式K-Means聚类后所属类别;LP2P(x)为x通过本算法聚类后所属类别;PMM则代表原始数据通过集中式K-Means聚类后得到的结果和通过本文算法聚类后所得到结果之间的误差率.PMM的值越小，说明聚类结果越接近集中式K-Means聚类效果.

同时，为了衡量分布式聚类的速度，同时也是评价网络中的带宽消耗量，将聚类所需的迭代数作为衡量分布式聚类带宽消耗的评价指标，显然，迭代数越多，聚类的速度越慢，带宽消耗也越大.

2.2 仿真结果

为了更好地进行比较，本试验首先对正态模拟数据，应用文中算法与DFEKM算法重复进行了50次分布式聚类试验，并计算出每次的PMM值和迭代数，结果如图3，4所示.

图3 文中算法聚类结果、DFEKM聚类结果和原始数据之间的PMM

从图3可见试验数据通过文中算法聚类后的结果的PMM值大都小于1.5，并且非常接近DFEKM聚类算法的结果，精度十分可观.

图4 文中算法和DFEKM聚类算法50次试验的迭代数

图4中蓝色线代表文中算法运行50次，每次的所需迭代数，每次试验大致需要1～3次迭代能够完成聚类，50次试验所需迭代数的均值为1.82;红色线代表DFEKM聚类算法运行50次每次试验所需的迭代数，50次试验迭代数的均值为2.52.在速度上较DFEKM聚类算法有将近30%的提升.

对从LibSVM网站上下载的两组真实数据集合a8a和ijcnn进行了聚类试验和对比分析，结果如表1所示.

表1 不同数据集合下文中方法和DFEKM算法聚类性能的比较

从表1可见，文中方法相对于DFEKM虽然带宽的消耗稍有增加但是在聚类精度上有了很大的提高，另外DFEKM算法对计算置信半径的参数的设置非常敏感，而文中方法可以根据数据的分布自动计算置信半径不受参数的限制，因此比DFEKM方法有更强的健壮性.

3 结论

文中提出一种基于置信半径的分布式K-Means算法，该算法根据各节点中数据分布紧密程度，应用Fisher线性判别比率找到同一类数据在节点的稠密和稀疏分布，从而确定聚类的置信半径.试验表明，相比DFEKM聚类算法，在聚类结果和聚类速度上，文中算法能根据数据的分布不同，能够兼顾速度与精度，达到很好的平衡效果.这表明算法具有更强的健壮性.今后将进一步研究分布式聚类算法，并且将算法应用于图像分割、模式识别等领域.

References)

［1］Jain A K，Murty M N，Flynn P J.Data clustering:a review［J］.ACM Computing Surveys，1999，31(3):264-323.

［2］杜晨阳.分布式聚类算法研究与应用［D］.杭州:浙江大学计算机学院与技术学院，2011.

［3］Chamam A，Pierre S.A distributed energy-efficient clustering protocol for wireless sensor networks［J］.Computers＆Electrical Engineering，2010，36(2):303-312.

［4］Hammouda K M，Kamel M S.Models of distributed data clustering in peer-to-peer environments［J］.Knowledge and Information Systems，2014，38(2):303-329.

［5］徐 楠，孙亚民，黄 波，等.无线传感器网络跨层自适应周期分簇路由模型［J］.计算机科学，2011，38(5):56-59，78.Xu Nan，Sun Yamin，Huang Bo，et al.Cross-layer adaptive round distributed clustering routing model for wireless sensor networks［J］.Computer Science，2011，38(5):56-59，78.(in Chinese)

［6］Ma Yajie，Guo Yike，Tian Xiangchuan，et al.Distributed clustering-based aggregation algorithm for spatial correlated sensor networks［J］.IEEE Sensors Journal，2011，11(3):641-648.

［7］鲁伟明，杜晨阳，魏宝刚，等.基于MapReduce的分布式近邻传播聚类算法［J］.计算机研究与发展，2012，49(8):1762-1772.Lu Weiming，Du Chenyang，Wei Baogang，et al.Distributed affinity propagation clustering based on MapReduce［J］.Journal of Computer Research and Development，2012，49(8):1762-1772.(in Chinese)

［8］宋余庆，王春红，陈健美，等.基于高斯混合密度模型的医学图像聚类方法［J］.江苏大学学报:自然科学版，2009，30(3):293-296.Song Yuqing，Wang Chunhong，Chen Jianmei，et al.Clustering of medical image based on Gaussian mixture density model［J］.Journal of Jiangsu University:Natural Science Edition，2009，30(3):293-296.(in Chinese)

［9］Ramzan N，Park H，Izquierdo E.Video streaming over P2P networks:challenges and opportunities［J］.Signal Processing:Image Communication，2012，27(5):401-411.

［10］Eisenhardt M，Müller W，Henrich A.Classifying documents by distributed P2P clustering［J］.GI Jahrestagung，2003，35(2):286-291.

［11］Dumitrescu M，Andonie R.Clustering superpeers in P2P networks by growing neural gas［C］∥Proceedings of2012 20th Euromicro Conference on Parallel，Distributed and Network-based Processing. Garching， Germany:IEEE Computer Society，2012:311-318.

［12］Nakahara S，Ohta T，Kakuda Y.Experimental evaluation of MANET based on autonomous clustering and P2P overlay network［C］∥Proceedings of2013First International Symposium on Computing and Networking.Matsuyama，Ehime，Japan:IEEE Computer Society，2013:480-483.

［13］Jin Ruoming，Goswami Anjan，Agrawal Gagan.Fast and exact out-of-core and distributed K-means clustering［J］.Knowledge and Information Systems，2006，10(1):17-40.

［14］张国印，李 军.移动对等网络覆盖网［J］.软件学报，2013，24(1):139-152.Zhang Guoyin，Li Jun.Overlays in mobile P2P networks［J］.Journal of Software，2013，24(1):139-152.(in Chinese)

［15］李 榴，唐九阳，葛 斌，等.k-DmeansWM:一种基于P2P网络的分布式聚类算法［J］.计算机科学，2010，37(1):39-41.Li Liu，Tang Jiuyang，Ge Bin，et al.k-DmeansWM:an effective distributed clustering algorithm based on P2P［J］.Computer Science，2010，37(1):39-41.(in Chinese)

［16］王 菁，张焕杰，杨寿保，等.利用集合差异度实现基于内容聚类的P2P搜索模型［J］.中国科学院研究生院学报，2007，24(2):241-247.Wang Jing，Zhang Huanjie，Yang Shoubao，et al.Content-based clustered P2P search model depending on set distance［J］.Journal of the Graduate School of Chinese Academy of Sciences，2007，24(2):241-247.(in Chinese)

［17］Richard O Duda，Peter E Hart，David Stork.模式分类［M］.李宏东，姚天翔，译.2版.北京:机械工业出版社，2003:96-100.

［18］Datta S，Giannella C R，Kargupta H.Approximate distributed K-means clustering over a Peer-to-Peer network［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21(10):1372-1388.

［19］Chang C C，Lin C J.LIBSVM:a library for support vector machines［J］.ACM Transactions on Intelligent SystemsandTechnology， 2011， doi:10.1145/1961189.1961199.