IncSNN - 一种基于密度的增量聚类算法


计算机研究与发展JournalofComputerResearchandDevelopmentISSN1000—1239|CN11.1777|TP43(Suppl.):309~313,2006IncSNN——一种基于密度的增量聚类算法孙焕良1邱菲1刘俊岭2朱叶丽11(沈阳建筑大学信息与控制工程学院沈阳110168)2(沈阳建筑大学计算中心沈阳110168)(sunhl@sjzu.edu.cn)IncSNN:AnIncrementalClusteringAlgorithmBasedonDensitySunHuanlian91,QiuFeil,LiuJunlin92,andZhuYelil1(SchoolofInformation&ControlEngineering,ShenyangJianzhuUniversity,Shenyang110168)2(ComputerCenter,ShenyangJianzhuUniversity。Shenyang110168)AbstractThedensity—basedclusteringalgorithmisoneofgreatimportanceclusteringanalysis,whichcanfindthearbitraryshapeclusters.Becauseofitshighcomplexity,todesignefficientincrementalalgorithmbecomesanimportantissue.Inthispaper,anincrementalalgorithmnamedIncSNNisproposed,whichisbasedondensity—basedclusteringalgorithmSNN.Thealgorithmpartitionstheupdateobjectspace,anddefinesthenearestneighborsineachpartition.Thus,theinfluenceobjectdatasetcanbefound.Whenupdating,thealgorithmonlydealswiththeinfluenceobjectspaceinsteadofthewholedataset.Becausethesizeoftheinfluenceobjectdatasetisfarlessthanthatofthewholedataset,theefficiencyofthealgorithmisimproved.TheexperimentalresultsshowthattheIncSNNalgorithmiseffective.Keywordsclusteranalysis;SNN;incrementalclusteringalgorithm;density-basedalgorithm摘要基于密度的聚类算法是一类重要的聚类算法,能发现任意形状的簇,但由于它的时间复杂度较高,因此设计有效的增量更新算法是一个重要研究方向.在SNN算法的基础上,提出一种基于密度的增量聚类算法一IncSNN.该算法将所更新对象的空间进行划分,定义了基于该划分的最近邻居的概念,进而确定了受影响对象的集合,当算法更新时,只需要对受影响的数据进行处理.由于受影响对象的集合远小于原数据集合,因此显著提高了算法的效率.实验结果验证了IncSNN的有效性.关键词聚类分析;SNN;增量聚类算法;基于密度的算法中图法分类号TP311.13作为数据挖掘中一种重要的方法,聚类分析能够作为一个独立的工具来获得数据分布的情况.作为数据挖掘的一个功能,聚类分析能观察每个簇的特点,集中对特定的某些簇做进一步的分析.迄今为止,人们已经提出了许多聚类算法,如基于划分的算法(K—means⋯)、基于层次的算法(BIRCHL21)、基于密度的算法(DBSCAN【31,SNN【41)、基于网格的算法(STING∞1)等.由于数据的更新是非常频繁的,随着数据库的不断增大,如果采用传统算法,少量的数据更新也需要处理数据库中所有数据,虽然基于密度的聚类分析算法可以发现任意形状的类且能够较好地处理含有噪声的数据,但是其时间复杂度较高.Ester等人提出基于密度的增量聚类算法incremental—DBSCAN【6J,它是在DBSCAN基础上解决增量更新问题的聚类分析算法.但是对于一组固收稿日期:2006—07—29基金项目:国家自然科学基金项目(60473073,60573090);辽宁省自然科学基金项目(20052006);辽宁省教育厅攻关计划基金项目(05L354) 万方数据 310计算机研究与发展2006,43(增刊)定的参数,高密度的聚类结果被完全包含在根据较低密度所获得的密度相连的集合中,因此incremental-I)BSCAN对密度不同数据处理并不理想.本文在基于密度的聚类算法(sharednearestneighbor,SNN)L4J的基础上,提出一种基于密度的增量挖掘算法(incrementalSNN,IncSNN).该算法将每个更新对象的空间区域进行划分,在这种空间划分的基础上找到每个对象的受影响集合.在数据更新时只需要处理那些受影响的对象.相比SNN算法,IncSNN具有更高的效率、更少的磁盘访问次数,与incremental.DBSCAN相比具有优势的方面是该算法可以找到密度不同的聚类结果.1SNN算法及相关定义SNN提出了最近邻居相似度的概念,并且在此基础上来建立聚类.这些聚类不包含所有的对象,具有代表性的对象是来自数据密度均匀区域.下面给出SNN相关的定义.1.1SNN相关定义定义1.k最近邻居(kNN).设P是数据库中的一个对象,并且P与第k个最近邻居的距离为k-distance(P),则P的kNN包含所有与P的距离不超过k-distance(P)的对象,即NkNN(P)={q∈D\{P}Id(p,q)≤k-distance(p)}.定义2.相似度.如果P和q是两个对象,则那么它们之间的相似度用如下等式表示:similarity(P,q)=size(NN(P)nNN(q)),其中,NN(P)和NN(q)分别代表P和g的最近邻居列表.定义3.SNN密度.对象P中的SNN指数据集D中,对象P在给定相似度阈值SIM内对象的个数,即N(P)={q∈D\{p}fsimilarity(P,q)≤SIM}.定义4.噪音.数据库中不属于任何类的对象为噪声.1.2SNN聚类步骤SNN算法是Jarvis—Patrick和DBSCAN算法思想的一个结合,具体步骤如下:1)建立相似度矩阵.这一步可以由数据对象之间的相似图建立,两个数据对象之间的权重设为相似度的大小;2)通过保留k个最相似的邻居简化相似度矩阵.这一步通过保留相似图中权重最大的k个连接来实现;3)利用简化相似度矩阵构建共享最近邻居图.在这一步,我们可以用一个相似度阈值找到相连接的部分得到聚类(Jarvis—Patrick算法);4)找到每个对象的SNN密度.用一个用户指定的阈值Eps,找到大于或等于Eps的SNN相似度的数据对象;5)找到核心对象.用一个用户指定的阈值MinPts,找到所有大于MinPts的SNN密度的对象,标记为核心对象;6)从核心对象形成聚类.如果两个核心对象在Eps半径内,那么它们形成一个聚类;7)抛弃所有噪音对象.所有没有在核心对象半径Eps范围内的对象标记为噪音对象;8)分配所有非噪音、非核心对象从而形成聚类.分配这样的对象到最近的核心对象.其中步骤4)~8)利用了DBSCAN算法原理.2一种基于密度的增量挖掘算法上述SNN算法中,每个数据对象的k最近邻居都与该对象所处的环境有关,如果在数据库中,新的对象加入、原有的对象删除或修改都会对某些相关对象的k最近邻居造成影响.因此,一旦出现数据的增加、删除或修改的情况,必须对所有对象的kNN都进行重新计算.但是注意到,一个对象的更新只会影响到部分对象的kNN值,而不会影响到所有对象的kNN值.本算法目标是通过采用增量的聚类算法,使之能够在数据集更新的情况下,用较小的计算和空间代价,达到与重新处理所有数据对象同样的效果.IncSNN以更新的对象为中心,将空间平均分成6个象限,如图1所示:\S1./岛.\.。/。So\。/····\/.·’..八P·.。;3·声八’.ss,/’s。。\图1空间划分示意图 万方数据 孙焕良等:IncSNN——一种基于密度的增量聚类算法311图1中更新对象P所影响到的对象区域是在一定的范围之内,没有必要对当前所有的数据对象进行全面的更新,针对这个特征下面给出IncSNN算法的相关定义及步骤.2.1IncSNN相关定义定义5.焱最近邻居(姬NN).设D是一个对象集,P一个是更新对象,在第i个象限内,P与第忌个最近邻居的距离为k-distancef(户),则定义skNN为6个象限内P的kNN的和,即5N业N_N(P)={qED\{P}l2二d(P,q)≤i=0k-distancei(P)}.如图2所示,当k=3时,在象限S。内,对象q1,q2,q3为So内心州(P)的一部分.当一个象限内对象数目少于忌个时,直接把这些对象加入到skNN中.图2正NN刁≮意图(k=3)定义6.受影响对象集合(AffectD(P)).设D是一个对象集,P为某个对象,定义AffectD(P)为D中由于向D中插入P或从D中删除P而使D中对象的kNN产生变化的对象的集合,表示为AffectD(P)={q∈D\{P}IP∈NkNN(q)}.定理1.设D是一个对象集,P为一个对象,那么,VoED:oAffectD(p)≥黜}(o)=.N,D^NNUIp}(o).证明.反证法.定理1即已知在象限Si中,0∈Si,且O每AffectD(P),证明P告NkNN(0)成立.假设P∈NkNN(0)成立,若以0为圆心,distance(P,o)为半径画圆,则{Pl,P2,⋯,P^}为圆里面的对象集合.集合中个数count≥k.则若Pi∈Si(i=1,2,⋯,k),也就是所有的圆内对象落在P的象限Si和AffectD(P)交集内,则可以得到0∈NkNN(P),与已知矛盾;同理,当Pf不全落在S内,S和AffectD(户)交集中对象个数小于k,也可以得到0∈MNN(P),与已知矛盾.则原命题成立.定理2.设D是一个对象集,P是一个更新对象,那么,AffectD(P)cN娃ⅣⅣ(P).证明.在象限Si内,取NkNN(P)中距离P最远的对象q,这个距离就是k-distancei(户).在以q为中心的k-distance£(户)范围内,一定能找到M删(q),因为qEN▲州(P),且k-distancei(q)≤k—distancei(P),那么AffectD(P)CN,女NN(P).证毕.定义7:更新的核心对象.设D是一个对象集,P为一个插入或删除的对象,那么有如下定义:1)UpdCoreI。={qq在DU{P}中是核心对象,了.q7:g7在DU{P}中是核心对象而在D中不是核心对象,并且口∈NkⅣⅣ(q,)};2)UpdCorel)el={qq在D\{P}中是核心对象,了.口7:q7在D中是核心对象而在DU{P}中不是核心对象,并且q∈NkNN(q,)}.下面我们分别论述对象插入和删除时IncSNN算法.2.2对象插入插入一个对象P时,存在以下5种情况,如图3所示:乇之;×.)乏...≥:(a)噪音(b)生成(c)吸收●●’-●●·乙。x.-.留兄:(d)合并(e)分裂图3插入一个对象时对数据集的影响1)噪音(noise)如果UpdCoreI。为空,因为P对象的插入在D没有生成新的核心对象,则P是一个噪音对象,并且没有其他的对象受到影响(见图3(a));2)聚类(creation)如果UpdCoreI。仅包含一个核心对象,且在P插入之前这个核心对象是一个噪音,那么P对象插入之后就生成一个新的聚类(见图3(b));3)吸收(absorption)在P插人之前UpdCoreI。包含一个或多个核心对象,且这些核心对象属于一个类,那么P对象被这个类吸收(见图3(c));4)合并(merge)在P插入之前UpdCoreI。包含一个或多个核心 万方数据 312计算机研究与发展2006,43(增刊)对象,且这些核心对象分别属于不同的类,那么P就把这些类连接起来形成一个类(见图3(d));5)分裂(split)这种情况发生在一个类中,且类的密度不均匀.在户插入之前UpdCoreI。包含一个或多个核心对象,P对象插入后,UpdCoreI。分属于不同的类,那么将p加入在MNN(P)中存在核心对象的那个类中(见图3(e)).由于DBSCAN本身制约,这种情况是incremental—DBSCAN算法所不具备的.2.3对象删除当从数据中删除一个对象P时,存在4种情况,如图4所示:×●●(a)移出●●●●··×!·●●●(c)分裂●●:×·(b)减少·:C遗●●(d)合并图4删除一个对象时对数据集的影响I)移出(removal)UpdCoreo。I为空,即不存在核心对象,或者因为P的删除而没有了核心对象的性质.如果UpdCore蹦大小为1,那么AffectD(P)中的对象从先前的聚类改变成噪音对象;如果为零,AffectD(P)中对象性质不变(见图4(a)).2)减少(reduction)对象P删除前后UpdCorel)el都不为空,有可能P删除前后核心对象数目不相等,但都同属于一个类,那么在AffectD(P)中一些对象可能会成为噪音对象(见图4(b)).3)分裂(split)对象P删除前后UlxlCoreDd都不为空.删除P前,UpdCoreDel中核心对象属于同一个类,删除P后,UpdCoreDd中核心对象属于不同的类.那么在AffectD(夕)中一些对象可能会成为噪音对象(见图4(c)).4)合并(merge)对象P删除前后UpdCoret)el都不为空.删除P前,UlMCoretkl中核心对象属于不同的类;删除P后,UpdCoret)el中核心对象属于相同的类.这种情况发生在多个密度不同的聚类的边缘,且P倾向于密度较大的边缘部分(见图4(d)).3算法性能测试对算法IncSNN的性能进行测试,并将测试结果与SNN做比较.所有测试在一台PC上进行,其配置为CPUP1V2.4GHz,内存512MB,硬盘80GB,操作系统为WindowsXP专业版.算法用VisualC++实现.测试数据集为SNN算法所用的数据集.因为IncSNN的时间消耗主要在求每个对象的kNN上,所以我们使用了CD-Tree[7J作为数据索引结构,这种索引结构是基于网格的,对于找到每个对象的kNN,该索引结构非常高效.测试是在参数k=50,Eps=20,MinPts=34的条件下进行.测试首先使用一个大小为100,000的数据集,在上述参数下,孤立点所占百分比为3.5%,每次测试都包含更新后用SNN算法分析后的结果.我们分别用IncSNN(插入),IncSNN(删除)分别代表向数据集中插入和从数据集中删除对象的测试结果.其中插入随机生成,删除的对象从原始数据集中随机选择.测试结果分别如图5和图6所示.岔一庭留口一厘岔图5IncSNN(插入)与SNN效率比较图6IneSNN(删除)与SNN效率比较由图5和图6可以看出,对于相同的更新对象百分比,减少对象的更新比增加对象的更新效率要低.当更新的对象数目较少时,IncSNN的优势非常明显,随着更新的数目增加,IncSNN效率逐渐逼近SNN,这也是所有增量聚类算法所共有的特点.接下来测试IncSNN空间访问次数.测试采用 万方数据 孙焕良等:IncSNN——一种基于密度的增量聚类算法313的是一个1000000的数据集,数据分布是随机的.对一个数据对象P,AffectD(P)的大小即为对P的更新所访问的次数,而SNN的访同次数是整个数据集的大小.对多个数据对象,它们之间的受影响对象可能重叠.测试过程中我们不插入或删除任何对象,因为不论插入还是删除,一个对象的受影响对象是相同的.我们分别取出数据集的一部分作为更新对象来测试空间访问次数,结果如图7所示:籁撕靛廑蕊X丫2图7IncSNN与SNN空间访I司次数比较由图7可以看出,当更新对象数较少时,IncSNN访问到的对象数要远远小于SNN,随着更新对象数的逐渐增加;IncSNN访问对象数以较快的速度逼近SNN;当达到数据集的大小时,因为所有的对象都已经访问过,因此访问对象数不再增加.4结论本文在分析聚类算法SNN的基础上,提出了一种动态环境下增量聚类算法IncSNN.该算法在数据更新时只需要处理那些受影响的对象,相比SNN算法,IncSNN具有更好的处理更新的能力、更少的磁盘访问次数.与增量的DBSCAN不同的是,该算法可以找到密度不同的聚类结果.参考文献[1】LKaufman,PJRousseeuw.FindingGroupsinData:AnIntroductiontoClusterAnalysis.NewYork:JohnWiley&Sons,1990[2]TZhang,RRamakerishnan,Livany.BIRCH:Anefficientdataclusteringmethodforverylargedatabases.In:ProeoftheACMSlGMoDInt’lConfonManagementotData.NewYork:ACMPress.1996.103—114[3]MEster。Hans-PeterKrIegel,JSander。eta1.Adensity—ba.Ⅲxlalgorithmfordiscoveringclustersinlargespatialdatabaseswithnoise.In:Procofthe2ndInt’IConfonKnowledgeDiscoveryandDataMining(KDD).MenloPark,CA,1996.226--2,31[4]LeventErtoz,MeachealSteinbaneh,VipinKumar。Findingclusterswithdifferentsize。shapes,anddensitiesinnoisehighdimensionaldata.In:Pro=oftheSDM.SanFrancisco:SIAM.2003[5]WWang.JYang,RMuntz.STING:Astatisticalinformationgridapproachtospatialdatamining.In:Procofthe23rdIEEEInt’lConfonVeryLargeDataBas酋.SanFrancisco:MorganKaufmarm,1997.186—195[6]MEster。H.PKriegel,JSander,ata1.Incrementalclusteringformininginadatawarehousingenvironment.In:AGupta,OShmueli,JWidom,eds.Procofthe24thInt’lConfonVeryLargeDataBases.SanFransiseoMorganKaufmarm,1998.323-333[7]HuanliangSun。YubinBao,FaxinZhao,甜a1.CD—Trees:Anefficientindexstructureforoutlierdetection。TheWAIM’04.Dalian.2004孙焕良男,1969年生,博士,副教授,主要研究方向为数据仓库与数据挖掘.邱菲男,1978年生,硕士研究生,主要研究方向为数据挖掘.刘俊岭女,1972年生,讲师,主要研究方向为数据挖朱叶丽女,1983年生,硕士研究生,主要研究方向为移动对象. 万方数据 IncSNN——一种基于密度的增量聚类算法 作者: 孙焕良, 邱菲, 刘俊岭, 朱叶丽, Sun Huanliang, Qiu Fei, Liu Junling, Zhu Yeli 作者单位: 孙焕良,邱菲,朱叶丽,Sun Huanliang,Qiu Fei,Zhu Yeli(沈阳建筑大学信息与控制工程学院 ,沈阳,110168), 刘俊岭,Liu Junling(沈阳建筑大学计算中心,沈阳,110168) 刊名: 计算机研究与发展 英文刊名: JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT 年,卷(期): 2006,43(z3) 被引用次数: 2次 参考文献(7条) 1.L Kaufman;P J Rousseeuw Finding Groups in Data:An Introduction to Cluster Analysis 1990 2.T Zhang;R Ramakerishnan;Livany BIRCH:An efficient data clustering method for very large databases 1996 3.M Ester;Hans-Peter Kr Iegel;J Sander A density-based algorithm for discovering clusters in large spatial databases with noise 1996 4.Levent Ertoz;Meacheal Steinbanch;Vipin Kumar Finding clusters with different size,shapes,and densities in noise high dimensional data 2003 5.W Wang;J Yang;R Muntz STING:A statistical information grid approach to spatial data mining 1997 6.M Ester;H-P Kriegel;J Sander Incremental clustering for mining in a data warehousing environment 1998 7.Huanliang Sun;Yubin Bao;Faxin Zhao CD-Trees:An efficient index structure for outlier detection 2004 本文读者也读过(9条) 1. 谢静.苏一丹 基于人工免疫的增量聚类算法[会议论文]-2009 2. 孙焕良.邱菲.朱叶丽.王永会.SUN Huangliang.QIU Fei.ZHU Yeli.WANG Yonghui ISNN:一种基于密度的高效增 量聚类算法[期刊论文]-沈阳建筑大学学报(自然科学版)2006,22(6) 3. 孙焕良.邱菲.刘俊岭.朱叶丽 IncSNN——一种基于密度的增量聚类算法[会议论文]-2006 4. 李霞.蒋盛益.LI Xia.JIANG Shengyi 改进的共享最近邻聚类算法[期刊论文]-计算机工程与应用2011,47(8) 5. 尹清波.张汝波.申丽然.王慧强.李雪耀.Yin Qingbo.Zhang Rubo.Shen Liran.Wang Huiqiang.Li Xueyao 基于 矢量量化分析的有监督聚类异常检测方法研究[期刊论文]-计算机研究与发展2006,43(z2) 6. 刘建晔.李芳.LIU Jianye.LI Fang 一种基于密度的高性能增量聚类算法[期刊论文]-计算机工程2006,32(21) 7. 倪国元 基于模糊聚类的增量式挖掘算法研究[学位论文]2004 8. 苏晓珂.兰洋.程耀东.万仁霞.SU Xiao-ke.LAN Yang.CHENG Yao-dong.WAN Ren-xia 基于约束的混合属性增量聚 类算法[期刊论文]-计算机工程与设计2010,31(8) 9. 陈卓.贺明霞.刘相双.CHEN Zhuo.He Ming-xia.LIU Xiang-shuang 基于扩展凝聚点和网格的增量聚类算法[期刊 论文]-哈尔滨工业大学学报2006,38(8) 引证文献(2条) 1.吴佳.罗可 改进的模糊C均值的增量聚类算法[期刊论文]-计算机工程与应用 2011(23) 2.洪亮亮.罗可 动态的粗糙增量聚类方法[期刊论文]-计算机工程与应用 2011(24) 本文链接:http://d.g.wanfangdata.com.cn/Periodical_jsjyjyfz2006z3055.aspx
还剩6页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

yylong_619

贡献于2014-01-16

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf