计算机研究与发展JouralofC冶nnlputerR巴犯archandl戈vel叩mentISSN1000一1239/CNll一1777lTP44(Suppl.):187一191,2007一种基于KNN的融合聚类算法翁芳菲,陈黎飞,姜青山’‘(厦门大学软件学院厦门361005)2(厦门大学计算机科学系厦门361005)(fangfeiweng@hotmail.com)ClusteringEnsembleBasedontheKNNAlgorithmwengFangfeil,chenLifeiZ,andjiangQingshanl1(&入,lof与jZ二re,xiamen协1,1勺,xiamen36loos)2(2无户Zrtmentof肠mPUtr&iencee,x艺以m执uni~ix,义‘t口men361005)AbstractClusteringisanimPortantresearchtopicintheclusteringanalysis.Itisdifficultforthesingl乓clusteringalgorithmtogetthehighaccuracyorevendecidewhichalgorithmwouldbethebestoneforaParticulardataset.Inthispaper,anewclusteringensemblealgorithmbasedonknearestneighbor(KNNCE)15pro卯sedtogeneratesimilarityofdataandsingle一linkal卯rithmusedtogeneratethesingsomerelatedtopics,clusteringresult,withoutspecifiednumberofclustersinadvance.AfterdiscusnaturedataandapplicationontheIntrU8londetectionareadoptedtoevaluatetheperformanceoftheproposedalgorithmanditiscomParedwithotheralgorithms.Keywordsclusteringensemble;knearestneighbor;hierarchicaltree摘要聚类是数据挖掘领域一个被广泛研究的问题.单一的算法较难获得高的聚类准确率,甚至对于特定的数据集也很难找出最佳的方法进行聚类分析.提出了一种基于KNN的融合聚类算法(KNNCE),该算法基于累积k最近邻产生数据点间相似度,并通过single一link算法构建层次聚类树得到最终的聚类划分,且能够自动确定最佳聚类数,从而很好地解决以上的问题.最后,通过常用数据浏试和入侵检浏方面的应用表明该算法是有效的.还把它和同类算法进行比较和分析,以证明算法的优越性.关键词融合聚类;k最近邻;层次树中图法分类号TP31聚类算法是一种非监督机器学习算法,其目的是将集中的数据人为地划分成若干类,以揭示这些数据的真实分布情况.目前,人们已经研究出很多的聚类算法〔’一],3然而单一的算法较难获得高的聚类准确率,甚至对于特定的数据集也很难找出最佳而得到比单一算法更为优越的结果.在分类算法和回归模型中,融合方法的使用已经比较成熟.但在聚类分析领域,融合聚类方法的研究在近几年才开始出现.目前,在融合聚类方面,有t珑Shl等人提出[]的3个基于超图的方法:CSPA5(clutes-ba横妇51r而laitypartitiorni眼algonthm),HGPA(hyperGraphpartitioningalgorithm)和MCLA(meta-的方法进行聚类分析闭.因此我们不妨设想对于给定的数据采用多种不同的聚类算法,然后选取其中最佳者.融合方法基于这种思想,将不同算法或是同一算法下使用不同参数得到的结果进行合并,从收稿日期:2007一0305苍金项目:国家“九八五”工程二期基金项目(0000一X07204)clusteringalgorithm);Fern等人[“]使用双元图进行聚类融合,提出THBGF(hybridbipartitegraph188计算机研究与发展2007,44(增刊)允mlulation)方法;以及F获月等人提出]的E7[A(eidenveCaccumulation)等方法.2基于兀NN的融合聚类算法(KNNCE)给定一个d维数据集DB=!xl,xZ,一,X,},但是,现有的融合聚类算法比如EA算法[J,7存在产生聚类成员的稳定性和聚类准确性等方面的不足之处(详见第1.1节).因此,藉着分类器组合方面的思想,本文提出了一种新的融合聚类算法KNNCE(K一nearestneighbor。lusteringensemble),X二!xl,xZ,…,x己}为一个数据点,,为数据点的数目,假设n>2.本文提出的融合聚类算法先对DB多次运行KNN,形成划分集合尸=1尸,,pZ,…,巧}进行信息累积,再通过single一hnk算法对尸它采用多次运行KNN的方法进行聚类融合,起到了信息累积的作用,具有较好的稳定性和准确性.本文组织如下:第1节简要地介绍相关概念和理论;第2节详细介绍我们的算法(KNNCE),并从理论上说明KNNCE算法的可行性声第3节进行实验验证和分析,并把它与EA算法、single一hnk算法进行比较和分析,证明该算法的优越性;在第4节对本文加以总结,并指出进一步的工作方向.1相关工作1.IEA(evidenceaccumulation)算法基于K一means的EA算法[]7遵循着分裂和合并的策略.首先,采用聚类中心随机初始化的K-means算法,数据被分裂成很多小且呈球形的簇.多次运行K一means算法,得到聚类成员的Co,association矩阵,然后用基于最小生成树的层次聚类算法合并第1阶段所产生的大量的簇,得到最终的聚类结果.从EA算法的整个过程考虑,算法运行绝大多数的时间都花费在每次重复地运行K一means算法,以获得CO-association矩阵.而同时,传统的K-means算法存在3个固有的缺点:1)对于随机的初始值选取可能会导致不同的聚类结果,甚至存在着无解的情况;2)该算法是基于梯度下降的算法,因此不可避免地常常陷人局部极优;3)聚类数k必须作为参数由用户提供,而k的取值要适中,过小不能获得数据的复杂性,过大可能导致划分类过多.这3大缺陷大大降低了它产生聚类成员的稳定性和聚类准确性等效果.1Zsingle一link层次聚类isngle一ilnk算法[‘〕是考虑数据点间的相似度.数据点间的相似度越大合并的可能性越大.同时,我们采用设置阑值占的方法来构建层次聚类树.如果数据点间的相似度大于阂值占则合并数据点,直到没有相似度大于阑值占的数据点,算法停止,生成数据集所对应的层次聚类树.此时,我们得到最终的聚类划分结果.所对应的simialrtiy矩阵建立层次聚类树来确定DB的一个划分尸’,使该划分具有最优的聚类质量,再根据P.计算得到最优的聚类数目k.KNNCE算法的原理图如图1所示:图IKNNCE算法原理图2.1相关定义聚类分析基于数据点间的相似度.常用的相似度度量基于数据点间的距离,距离小于一定阂值的、两个点被认为是相似的.而在本文中,我们的相似度是基于数据点间的邻居关系.下面给出KNNCE相关的定义.定义1.k最近邻居(KNN).设P是数据集中的一个数据点,并且P与第k个最近邻居的距离为k一成ats二(P),则P的KNN包含所有与P的距离不超过k一d钻atnec(P)的数据点,即N二NN(P)={9任n\\IP}}J(P,9)镇k一distance(P)},其中,k的取值在范围〔kmi。,klan二〕区间内随机选择,比固定的k值更具有良好的鲁棒性.kmin是最小邻居数;kmax是最大邻居数.定义2.相似度.为了获得更佳的数据划分,我们提出了一个融合聚类结果的决策机制,用于衡量数据点间的相似度.这个假设的基本思想是与数据点属于同一类的数据点,往往是与其距离最近的数据点.因此,通过KNN所找到的数据点的最近邻有极大的可能性是属于相同的类.将n个数据点的N次搜索k个最近邻,映射为一个nxn的similarity矩阵:。品:_:1__,,‘:,.,“‘:甲.‘人\\尸,,夕一_、_卫史呈ZN(1)翁芳菲等:一种基于KNN的融合聚类算法n闪是在N次搜索k个最近邻中p和q为邻居的次N数.具体来说,,、一云1二1(NN.(P)uNN{(。”.其中,NN*(P)代表每次运行KNNP所得到的与q的邻居关系,若q为P的k最近邻居,则NN‘(P)为1,反之为0;同理NN‘(q).因此,每次对数据集运行KNN,n、最多可以增加2.2.2算法过程完整的算法(KNNCE)如下:1)输人数据DB;参数N,占和区间[km;n,无二x];,imilarity矩阵初始化为空;设置循环次数变量t=0;)2在【kmin,klan二」区间内随机选择k;3)根据选择的k值,对数据集运行KNN,更新simialrity矩阵:对于每个数据对(P,q),如果q在P的k个最近邻中,或者P在q的k个最近邻中,则similar£yt(P,9)=:imilarity(P,9)+12N4)循环变量t=t+1;如果t
a,且similarity(p,q)为ismialrtiy矩阵中最大值,则将数据点p和q合并在同一类中;如果不再有满足similarity(P,妇>占数据对,则继续步骤6);6)算法停止,并输出划分C‘.基于KNN的融合聚类算法(KNNCE)的流程图如图2所示.算法主要由2个阶段组成,第1个阶段是多次运行KNN,融合不同尺度下KNN得到的相似性.由算法的步骤2)一4)构成.第2个阶段是使用single一hnk算法合并相似度大的簇,如此反复迭代直至满足停止条件.算法的第1阶段:形成相似度矩阵形成相似度矩阵的方法是基于KNN的融合聚类算法的核心.该方法一方面把高维的数据转换到低维(二维),简化了运行聚类算法的复杂度;另一方面融合了多种聚类划分的特征,增加了算法的稳定性和准确性.循环N次形成相似度矩阵.在每次循环中,根据随机选择的k,对数据集运行KNN,这样对于每k个最近邻数据点,产生了一;然后更新similarity矩阵,把新产生的聚类成员尸作为一个聚类划分的信息融合到similraity矩阵中.经过N次循环以上的过程,多重聚类划分的信息便融合到similarity矩阵中,接下来再对simialrtiy矩阵做处理,最终得到聚类结果.阶段‘,1:形成相似度矩阵..-.一厂…谕段2:构建层次聚类树一\\图ZKNNCE算法流程图2.4算法的第2阶段:构建层次聚类树根据形成的similarity矩阵,使用single一link算法构建层次聚类树.在。miilarity矩阵中值越大的数据点对越有可能被合并在同一类中.因此,每次我们合并相似度最大的数据点,且该相似度要大于一个阂值,逐层建立层次树,直到没有相似度大于阑值的数据点,算法停止.下面分析KNNCE算法的时间复杂度.运行KNN构建聚类成员的时间复杂度为0(nZN);形成similarity矩阵的时间复杂度为0(k);采用single一nilk层次算法处理相似度矩阵的时间复杂度为0(犷),其中,n是数据点的数目,N是融合聚类成员的个数.因此,总的时间复杂度为0(nZ).3实验与分析实验验证包括KNNCE方法的有效性和聚类正确率两方面.并把它和EA算法〔7〕及single一link算法川进行比较和分析,证明该算法的优越性.前两种算法都是融合聚类算法,它们都可以自动确定最佳聚类数.3.1常用测试数据在本实验中,EA算法的参数设置参考文献〔7,11〕:t=0.5,k的随机选择区间为【2,了万〕,N二05;本文设置single一nilk算法的参数为t=0.5;我们的算法参设置如下:t=0.4,【kmon,kma二」二【2,5〕,N=30.2.3一个数据点都形成了个聚类成员尸计算机研究与发展2007,44(增刊)IRIS数据集是聚类分析领域一个比较常用的测试数据[].它共包含1580个数据点,由3种类型植物所构成:Setosa,Versicolo:和virginica,且其中一类(Setosa)线性地与其他两类分开,同时剩余这两类在特征空间中有部分重叠.每个类包含50个数据点,每个数据点包含4个数值类型的属性.对每个算法分别运行10次,在各算法停止时,要是通过检测用户的异常行为来发现入侵事件.异常检测的优点就是能够发现未知的攻击类型,但同时也存在误报率高、建立正常行为模型不易等问题.我们将KNNCE算法应用于经典的KDI芜tl四9测试数据集〔9〕.KDDcup99的数据集包含41个属性,本文参考文献【0」,1选取了对人侵检测影响较大的主要属性:dst一ost一hounct,st一dhost一sry一ounct,出现概率最大的聚类数作为算法最终的聚类数:表1各算法停止时的聚类数算法聚类数isngle一linkKNNCE由表1可知,EA和single一link算法聚类不正确,KNNCE算法可以得到正确的聚类结果.其中,由于k一means方法具有聚类中心初始化随机的特点,因此,基于k一means的EA算法在多次运行过程中存在聚类数不稳定的缺点.同时,对于参数k,在KNNCE算法中,k值的增减代表着数据点邻居的增减,而在EA算法中,k值的增减代表着类的增减,而往往一个类中所包含的数据点是相当多的,因此,KNNCE算法相比EA算法,参数k的影响大大降低了.设每类数据点集合为5‘,算法停止后每类实际的数据点为F*,类的总数为。,为了评估算法的聚类效果,我们形式化定义聚类正确率如下:正确率=上艺2一—5‘门F‘x100%,(2)习5‘其中,习5‘门Fi表示所有正确划分的数据点.结果如表2所示,KNNCE算法的聚类正确率高于EA和single一hnk算法,KNNCE算法可以更准确地划分数据,表2各算法对IRIs的聚类正确率算法聚类正确率(%)single一link66.67EA86.00KNNCE97.333.2入侵检测异常检测是当前入侵检测研究领域的热点,主asme一rsy一arte,Protocol一忿夕户£,sdt一host一asme一rsy-rate,sdt一ohst一asme一src一oPrt一arte,ocunt和sry-unt作为相似度的度量,其中除了ProtoocljyPe以外都是数值属性,把ProtocolwelyPe转化为三个二元属性:“15一tcP”,“15一udP”和“1,一icmP”,即如果ProtoocljyPe=tcP,转化后1:一ctP二1,51一“dP二0,51一cimp=0.KDDcuP9数据集合较大,我们以0.02%的概率随机抽样选取了9980条数据,其中正常数据和异常数据比例分别约为19.25%和80.75%,可以看出KDDCup99数据集的异常行为大大多于正常行为.抽样结果数据集除正常数据NORMAL外,包含12种异常数据:SMURF,POD,TEARDROP,BACK,IPSWEEP,NMAP,FTP_WRITE,NEPTUNE,PORTSWEEP,SATAN,WAREZCLIE,LAND.EA算法的参数设置参考文献〔7,11〕:t=0.5,k的随机选择区间[2,80],N=50;文献[11]提出对于大的数据集,k的随机选择区间为【2,80〕时聚类结果趋于最佳.我们的算法参数设置如下:t=0.4,[无‘n,无ahtx]=[2,8],N=30;相对于上个实验,由于数据集增加,我们把k的随机选择区间适当地加大.根据文献【11〕对singlolink算法和EA算法比较分析的结论,isnglohnk在大数据集的算法性能远低于EA算法,故本实验中略去与single-hnk算法的比较.对抽样数据运行10次,然后取平均,得到聚类正确率如表3所示:表3各算法对KDIX二up99抽样数据的聚类正确率算法聚类正确率(%)EA79.30KNNCE84.22结果如表3所示,KNNCE算法的聚类正确率略高于EA,KNNCE算法可以更准确地划分数据,不过KNNCE算法把正常数据“N0RMAL’,划分正确的比率为91.93%;而EA算法把正常“NORMAL’,划分正确的比率仅为0.31%,也就是oc翁芳菲等:一种基于KNN的融合聚类算法说EA算法没有能够把正常数据形成一个独立的大类3.3参数评估相对于其他两个参数,参数t对层次聚类的过程影响最大.参数t的值越大,在算法每一次迭代的合并过程中,越少数据点被合并,相应地,最终获得的聚类数就越多.用IRIS标准数据测试参数t对算法的影响.如图3所示,变化的参数t对应于聚类的正确率,其中,钻石形状表示聚类正确率.随着参数t的增加,KNNCE的聚类正确率经历了增大,到达峰值平缓,急剧下降的过程.,几0--劝08哥镶//少,、、0~日D拟l犷一一、\\溉0d盆ll\\\\00自//、”0}U/…,,一\\_~叫卜一,0.00.20。40.60.81.0阂值1图3变化的阑值对应于算法KNNCE的聚类正确率我们设定另外两个参数分别为t二0.5,【kmin,kmax〕“[2,5],同时给定N的取值范围为[2,200]进行测试.N值是与算法的收敛相关的.通过实验,我们发现N值在达到某个收敛值后(对于IRIS这种简单的数据集,05为其收敛值),其变化对聚类正确率几乎没有影响,因为此时算法已经收敛了.同时,我们发现k值的选取与数据集有着直接的关系.数据集越大获得最优聚类正确率所对应的k值就越大.这是因为KNN所基于的思想是与数据点越近的邻居属于一类的可能性越大,因此大数据集需要足够大小的k值才能保证簇数量的合适,过小的k值会导致产生过多的簇.4结论本文提出了一个基于KNN的融合聚类算法,该算法基于KNN,采用信息累积的方法获得聚类划分结果,且不需要预先指定聚类数.通过常用测试数据和人侵检测数据的测试,表明KNNCE算法是有效和稳定的.并把它和EA算法、single一ilnk算法进行比较和分析,算法具有更好的性能.如何优化该算法的参数及其应用于实际的领域将是我们下一步的工作.参考文献[1]AKJain,MNMutry,pJFlynn.Dataclutsering:AReviewACMComputifgisurveys,1999,31(3):264一323[幻RODuda,PEHart,DGStork.pattemClasification,eScnodEd.Newyork:Wiley,2001[3]BEveritt.ClusterA刀alysis.Newyork:Johnwileyand黝ns,1993[4]CFraley,AERafte即.Howtannyclusters?whichclusteri叱method?Answersviamodel一baesdclusteranal邓15.The肠mputerjournal,1998,41(8):578一588[5]Astrehl,JGhosh.Clusterensmebles:Aknowledgereuse台ameworkforcombiningmultiple那rtitions.JoumalofMachineLe自rnl眼Resaerch,2003,3(3):583一617[6]xzFern,cEBrdoley.solvi呢clusterensembleproblemsbybipatritegraphpartitioning.TheZlstlnt’IConfonMachineLearning,aBnff,Canada,2004[7]AFrea,AKJain.oataclusteri雌usi吃evidenceaccumulationThel6thlnt’IC冶IlfonPatternRec呢nition(ICPR2002),Quebec,Canada,2002〔]8修宇.王士同,等.方向相似性聚类方法DSCM计算机研究与发展,2006,43(8):1425一1431[9〕KDDcu四gdataest,http://kdd.ics.uci.ed可database习kddcup99/kddcup99.html,1999[10]WingWYNG,RockyKCChang,DanielS.Young:DimensionalityreductionfordenialofservicedetectionProblesmusingRBFNNoutputsensitivity.TheZndlnt’IC冶nfonMachineL忍arni飞andCybernetics,Xi’na,2003[1llAFred,^KJain.E沉denceaccumulationclusterilglb,dontheK一meansalgodthnl.Thelnt’lworkshopsonstructurlaandSyntacticPattemRec呢nition(SSPR2002),Windsor,Ontarlo,aCnada,2002翁芳菲女,9183年生,硕士研究生,主要研究方向为图像处理等.陈黎飞男,9172年生,博士研究生,主要研究方向为.姜青山男,9162年生,教授,博士生导师,主要研究方向为数据挖掘、图像处理、聚类分析、地球信息系统、数字通(屯iang@xmu.edu.cn).KNNCE数据挖掘、聚类分析、数据挖掘、聚类分析等信等