改进的快速DBSCAN算法

改进的快速DBSCAN算法 改进的快速DBSCAN算法 第29卷第9期 2009年9月 计算机应用 Jouma1ofC0mpluterApplications Vo1.29N0.9 Sep.2009 文章编号:10o1—9081(2009)09—25O5—04 改进的快速DBSCAN算法 王桂芝,王广亮 (河南商业高等专科学校计算机应用系,郑州45oo44) (w123@yaI10o.cn) 摘要:针对DBSCAN算法时间性能低效的问题, 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 快速聚类过程中丢失对象的原因,提出一种新的改进算法 IF—DBScAN.该算法在不丢失对象的基础上,通过选取核心对象邻域中的代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 对象来扩展类,从而减少邻域查询次 数,提高了算法的时间性能.实验结果表明,IF.DBscAN算法是正确和高效的. 关键词:聚类;DBscAN算法;邻域;核心对象 中图分类号:TP3O1文献标志码:A ImprOVedfastDBSCANalgOrithm WANGGui_Zhi,WANGGuang—liang (脚州眦D,c0"锄z,,Mn曰,螂sc0阮,0Mn45oo44,,m) Abstract:rhetimeperf0nnanceofDensity-BasedSpatialClustering0fApplicationswithNoi se(DBSCAN)isinefficient. ConcemingtIlispmblem,theauthorsanalyzedthereasons0flosingobjectin出epr0cessoffastclustering,andpmposedanew ImpmVedFastDBSCAN(IF— DBSCAN)algorithm.0nthebasis0fn0tl0singdataobject,thisalg0rithmexpandedacateg0r y byselectingrepre8entativeobjectsflr0mtheneighborhood0fcored砒aobject,sothatitreducedthenumber0freonal inquiriesandimpmvedthealgorithm'stimeperf0Hnance.Theexperimentalresultsshowthat IF-DBSCANalg0ritIlmiscorrect aJ1demcient. Key,v0rds:clustering;DBSCANalgorithm;ne培hborhood;coreobject O引言 聚类(clustering)是数据挖掘中的重要组成部分.所谓 聚类,就是将数据对象分组成多个类或簇(cluster),在同一个 簇中的对象之间具有较高的相似度,而不同簇中的对象差别 较大J.通过聚类,人们能够识别密集的和稀疏的区域,发 现全局的分布模式和数据属性之间有趣的相互关系.在数据 挖掘中,聚类分析能作为一个独立的工具来获得数据分布的 情况,观察每个簇的特点,集中对特定的某些簇做进一步分 析.此外,聚类分析还可以作为其他算法(如特征和分类等) 的预处理步骤,这些算法再在生成的簇上进行处理. 迄今为止,人们已经提出了许多聚类算法,如K- MEANS【2.,CLARANS【,DBSCAN【4.,CURE【,CUQUE_o和 C2P【7等算法,其中DBscAN算法是一种基于密度的聚类算 法.该算法将具有一定密度的区域划分为簇,可以在含有 "噪声"的空间数据集中发现任意形状的聚类.但其时间性 能是低效的.本文提出了一个新的DBsCAN改进算法IF— DBSCAN.该算法在时间和空间性能上都比传统的DBsCAN 算法有较大提高. 1基于密度的聚类算法DBSCAN 1.1基本概念 基于密度的聚类算法的核心思想是:对于构成簇的每个 对象,其s邻域包含的对象个数,必须不小于一个给定值 (nP拈),也就是说其邻域的密度必须不小于某个阈值.下面 给出基于密度聚类算法分析中的一些定义. 定义1s一邻域.给定对象半径s内的区域称为该对象的 ? 邻域. 定义2核心对象.给定s,ns,若对象p的8邻域船(p) 包含的对象个数I^(p)I?施nPfs,则称p为核心对象. 定义3直接密度可达.给定s,MnP,s,当: 1)p??(g)且 2);^(g)I?;nP拈 则称对象p是从对象g出发直接密度可达的. 定义4密度可达.给定对象集合D,当存在一个对象链 pl,P2,…,p,p1=q,p=p,对p.?D,p?是从pf关于和 JlfnP拈直接密度可达的,则称对象p从对象g关于8和 密度可达(非对称). 定义5密度相连.如果对象集合D中存在一个对象o, 使得对象p和q是从.关于s和nPts密度可达的,那么对象 p和g关于和nP拈密度相连(对称). 定义6簇和噪声.基于密度可达性的最大的密度相连 对象的集合称为簇,不在任何簇中的对象被认为是"噪声". 1.2DBSCAN算法 DBSCAN(Density—BasedSpatialClustering0fApplic砒ions thNoise)是一个基于密度的聚类算法.该算法采用迭代查 找的方法,通过迭代地查找所有直接密度可达的对象,找到各 个簇所包含的所有密度可达的对象.具体方法如下: 1)检查数据库中尚未检查过的对象p,如果p未被处理 (归人某个簇或标记为噪声),则检查其邻域?8(p),若 ?8(p)包含的对象数不小于MP拈,建立新簇c,将?s(p)中 所有点加入c; 2'对c中所有尚未被处理的对象g,检查其邻域 ^(g),若?(g)包含至少s个对象,则将(g)中未 收稿日期:2o09一O3—23;修回日期:2009—05一l0. 作者简介:王桂芝(1970一),女,河南郑州人,副教授,硕士,主要研究方向:数据挖掘, 聚类分析;王广亮(197O一),男,河南郑州人,副教 授,主要研究方向:聚类分析. 2506计算机应用第29卷 归入任何一个簇的对象加入C; 3)重复步骤2),继续检查C中未处理对象,直到没有新 的对象加入当前簇c; 4)重复步骤1),3),直到所有对象都归入了某个簇或 标记为噪声. DBscAN算法可以在有噪声的数据中发现任意形状的聚 类,但该算法也具有明显的局限性.DBsCAN的时问复杂度为 0(n).另外,DBscAN算法要对每个数据对象进行邻域查 询,其时间性能低效. 2IF—DBSCAN算法 基于DBscAN算法时间性能问题,周水庚等人提出了 一 种快速的聚类算法FDBscAN,本文的IF—DBscAN算法正 是在此基础上提出的. 2.1IF—DBSCAN算法基础 FDBscAN算法通过选用核心对象附近区域包含的所有 对象的代表对象作为种子对象来扩展类,减少了区域查询的 次数,从而减低了聚类时间和L/0开销.该算法提出,在n维 空间中,选择2n个代表对象.也就是说,在每一维空间上,选 择两个对象作为代表对象用于类的扩展.但是,如果某些 对象唯一地通过被忽略的核心对象p密度可达,则当p所在的 类C扩展完成后,这些对象将未被包含在类C中,此时称之 为丢失对象.FDBSCAN算法在进行选取代表对象进行快速 聚类后,还必须对丢失对象进行处理. 我们用c语言编程实现了DBscAN算法和未处理丢失 对象的FDBscN算法,在Vc++6.0环境下调试运行,采用二 维数据集进行验证.实现结果表明,在未对丢失对象进行处 理时,FDBscAN算法比DBscAN算法的速度要快数倍,甚至 十倍以上.但此时,FDBscAN算法不能进行有效聚类——本 来存在几个类的数据集却被分成几十个类.显然,FDBscAN 算法必须对丢失对象进行处理,特别是对丢失对象所引起的 许多小类的合并问题必须解决.但是,要进行类的合并必然 要对已聚类后的数据库再次进行扫描,并对某些数据对象进 行区域查询.这必将降低算法的时间性能.为此提出一种新 的快速聚类算法——IF—DBscAN,可以避免后期对丢失对象 的处理过程. 2.2IF—DBSCAN算法思想 下面通过深入分析快速聚类中丢失对象的原因而提出 IF—DBscAN算法的基本思想. 2.2.1丢失对象的原因分析 在二维空间中,对一个核心对象的邻域选择4个代表对 象作为种子对象,并通过核心的种子对象再次选择其邻域的 4个代表对象来扩展类,用这种方法聚类会有两个问题. 1)当用4个代表对象作为种子对象来进行扩展类时,如 果某一个种子对象不是核心对象将不再进行类的扩展,同时 也放弃它邻域中的所有对象.这样将会导致大量的对象丢 失,从而导致一些本应属于此类的数据对象被排除在外.这 是因为,代表对象的邻域并不仅仅是这一数据对象的邻域,它 同时代表了这一种子对象附近的许多对象的邻域,甚至于一 个类的扩展方向.如果把这一邻域放弃了,等于放弃了这一 方向(即四分之一)的类的扩展. 2)一个核心对象的邻域可以近似地被4个分散较好的代 表对象的具有相同半径的邻域所覆盖,但是,当用这4个种子 对象进行类扩展时,如果再次选择它们邻域的4个代表对象 继续扩展时,同样会丢失对象.这是因为,当第一轮选择的4 个种子对象再次选择它们各自邻域的4个代表对象时,必定 都有一个代表对象已归过类(在初始的核心点邻域内),如果 一 个种子对象邻域的另外三个代表对象中恰巧有两个代表对 象也在初始核心点的邻域内,那么这一种子对象则仅依靠离 初始核心对象最远的那个代表对象来扩展类.如图1所示, p1,p2,p3,p4是第一轮选择的4个代表对象作为种子对象, 其中p1为核心对象,其邻域的代表对象q1,q2,q3,q4,由图 示可以看出q2,q3,q4均在初始核心对象的邻域内,即已标记 了类,此时仅对q1计算邻域进行类的扩展,这样显然会造成 大量数据对象的丢失. 图1二维空间中的邻域及其代表对象 2.2.2IF—DBSAN算法的基本思想 IF—DBscAN算法针对上述两个问题而提出,算法的基本 思想是在保证不丢失对象的基础上,选择合适的代表对象进 行类的扩展,从而提高算法的时间性能. 首先讨论第二个问题.在一个核心对象的邻域内选择4 个代表对象作为种子对象是不存在丢失对象的问题.但是, 当用这4个种子对象进行类扩展时,如果再次选择它们邻域 的4个代表对象继续扩展,将会丢失对象,此时应当选择足够 多的代表对象.显然,在核心对象的邻域中,外围数据点的邻 域可以完全覆盖内部数据点的邻域,因此,可以选择距核心对 象较远的一圈数据作为代表对象进行全方位的类扩展.至于 这一圈数据的距离应当尽量的远(即接近s),这样才能发挥 这一算法的效率,同时应当保证在各个方位都能选中代表对 象.于是,IF—DBscAN选择半径在0.9之外的数据作为代表 对象. 下面讨论第一个问题.在对4个种子对象进行处理时, 如果某一个种子对象不是核心对象将不再进行类的扩展,同 时也放弃它邻域中的所有对象.这将导致本应属于该类的数 据对象而被未归为此类,从而导致许多小类的生成.其实,当 某一个种子对象A不是核心对象,但如果其邻域中对象个数 接近于肘nP,,则很大程度上意味着:在它的附近(更接近原 始核心对象的方向)存在一个核心对象B,显然这一核心对象 中的所有数据对象都应归为此类.很容易理解,这个核心对 象B的邻域与非核心对象A的邻域几乎完全重合.于是,可 以这样处理,当某一种子对象的邻域中的对象个数接近于 nPfs时,将其邻域中所有数据对象归为此类.这样做,可能 导致本应属于噪声的个别数据进行了归类.通过实验,我们采 用0.8MnP,s这一参数来作为处理条件,这个参数可以很好 地避免数据对象的丢失,又可以从很大程度上区分出噪声数 据. 综上所述,IF—DBscAN算法的具体作法为:在一个核心 对象的邻域中选与核心对象最远的4个代表对象作为种子对 象进行类的扩展,在对4个种子对象进行类扩展时,把其邻 第9期王桂芝等:改进的快速DBscAN算法2507 域内距离大于或等于0.9s的未归类的数据对象作为代表对 象进行类扩展;另外,如果种子对象不是核心对象,但其邻域 中对象个数大于或等于0.8nP,s,则将其邻域中未归类的数 据对象归为此类,不再进行类的扩展. 2.3IF-DBsCAN算法 框架 财政支出绩效评价指标框架幼儿园园本课程框架学校德育工作框架世界古代史知识框架质量保证体系框架图 IF—DBscAN算法是DBscAN算法的另一个快速版本. 与FDBscAN相比,主程序IF—DBscAN不需要调用丢失点处 理过程,Expandcluster过程也有所改变.其算法框架描述如 下. IF?DBscAN(&0印5,肘,lPzs,尺印ren,口,一^nPs) {//&fn中的所有点被初始化为uNCLASsIFIED CZ,er=t(?0E); f0r(=l;<se#P0组se;++) I P0n=&Q0n组,() if(P0n.Cf,d==UNCLASSIFIED) { if(Expandcluster(s啦,Ponts,P0毗cf,e,印5, R印一se,l,8e一肘nn)) Chterld=?extIdCh'sterI J } l ExpondCh'stertSetfPottns,Potnt,Ctu3terId,Eps,MtnP拈,Rep ren,一.】IfP { C口dd口te—see=-'.0n如.,egongue,y(P0n,,Elps); if(c口如'e一5ee.<nP,5) {//Pont为一边界点 setq,Poc^?ecf,d(P0溉?DE); Ietum0: l else {//Po毗为一核心点 Set?D,s.c^口,leCZ,出(c0凡dd口te—see,c; R印e,l,口t一see-seZect(c?nd如,ee, rePresen,n痂卵,R印en,n痂e-肼nPs,P0); whi1e(r印ren,口,一see!=Empty) ( curre,P=r印ren口te一5ee.耶(); suZf=&,PDn如.on口ne(c小nP'); if(s>=P,s) f//cur7n为核心点 fore8chntPinrcP他,口tz'P if(Pc2,d==uNCLASSIFIED) re,ne一5ee.qPPend(P); fbreachp0intpin,'es { if(p.c2==UNCLASsIFIED0r?DE) 5et?7'0拈.c口,lgeCZ^d(p,Cf); (d,0rwe(P,c"rrentP))>=0.9Es) //P距离c"rren在0.9之外 印r?en把t一&e出*Sec,(5玩r印reef口,e.re?ZtP, 脚5enm,一肘nPP); ) } else {//cMrren,P不是核心点 if(u>=0.8肘Pts) floreachpointpin轧' if(p.Cz==UNcLAssIFlED0r?0 Jset'0ns.c^n,geCZ,d(p,cz^); ) Relpr?se凡,nfz一seeds.ckfete(cu,7nzP) l I?tuml: } 3相关实验 本文所涉及的算法均用c语言编程实现,并在wind0ws xP,VC++6.0环境下调试运行,所有测试在1台PC机 (PIII8o0cPu,256MB内存,20GB硬盘)进行. 3.1IF—DBscAN算法的正确性对比实验 为了验证IF-DBscAN算法的正确性,采用5个二维数据 集进行实验,如图2所示. (a)dataset1(b)dataset2(c)dataset3 (e)dataset5 始数据集 其中,dataset1有9993个点,数据自然聚为4类;datase 有5034个点,数据自然聚为5类;dataset3有l2917个点,数 据自然聚为3类;dataset4有8487个点,数据自然聚为4类; dataset5有l1183个点,数据自然聚为5类. 本文采用相同的参数验证DBscAN算法和IF—DBScAN 算法,所得到的聚类结果完全相同,如图3所示.其中, dataset1所采用参数为:=4,MnP拈=12;d0,?e垃, d.5e3,d8fe珥所采用参数均为::3,nP拈=15; d.t伽e所采用参数为:s=4,nPzs=15. (b)dataset2 (d)dataset4(e)dataset5 图3DBscAN和IF—DBscAN算法执行结果 通过对实验结果数据分析发现:数据集dataset1, dataset3,dataset4和dataset5在DBscAN算法和IF-DBscAN 算法中所执行的结果完全相同,每一个点的聚类结果都一样, 只有在数据集dataset2中,有个别数据点的聚类结果有差异. 由此可见,IF—DBscAN算法是正确的,它可以与DBscAN算 25O8计算机应用第29卷 法具有相同的聚类功效. 3.2IF—DBSCAN算法的执行时间对比实验 在测试IF—DBSCAN算法与DBsCAN算法的执行时间时, 仍然采用上述5个数据集,其中时间均以秒为单位.其执行 时间对比如表1所示. 表l两种算法的执行时间对比s 从表1中数据可以看出,IF—DBScAN算法总是比 DBscAN算法的速度快,尤其是对于数据集dataset2,IF— DBscAN算法的执行时间只是DBscAN算法执行时间的 42%.可见,IF.DBscAN算法与DBscAN算法相比,其时间 性能是高效的. 为了验证算法执行时间与数据规模的关系,采用数据集 dataset4(参数:s=s,nP,s=15)进行实验.本次实验分别 选取dataset4中的3000个,5oo0个,70o0个,9oo0个,l1Ooo 个及全部数据点,其实验结果图4所示. 50 4O 30 20 l0 0 jANI1—?一IF—DBSCAN厂7广一 I 一 .【==r|I.. juuU,INHJllI,LJU 数据规模 图4数据规模对执行时间的影响 由图4可以看出,两个算法的执行时间近似抛物线,这表 明这两个算法的时间复杂度与数据的规模成平方的关系.从 图中直观的可以发现,IF—DBscAN算法的执行效率明显比 DBscAN算法高,而且随着数据规模的增长仍能保持良好的 状态,说明IF—DBSCAN算法具有良好的可扩展性. 4结语 DBscAN算法与DBscAN算法相比,它们具有相同的 IF— 时间复杂度和空间复杂度.但是,DBscAN算法对每一个数 据点都计算其s邻域,建立其邻域链表,而IF—DBscAN算法尽 管没有降低时间复杂度,但却大大减少了计算8邻域的数据 点,从而减少了算法的执行时间,提高了其时间性能.另一 方面,由于IF.DBscAN算法中存在大量的数据点并不进行邻 域查询,所以在该算法中数据点后的存在许多空的链表,从而 也减少了空间的使用,提高了空间性能. 参考文献: 【1】CHENMS,HANJH,YUPS.Datamining:AnoVerviewflmma databaseperspective【J】.IEEETmnsactions0nKnow1edgeandDa— taEn舀neering,1996,8(6):866—883. 【2]KAuFANL,RPUSSEEUWPJ.Findinggmupsindata:Anintr0一 duction【0clusteranalysis【M】.NewY0rk:J0hnWiley&Sons, 199O. [3]ESI'ERM,KRIEGELHP,xUXW.Knowledgediscoveryinla SPATIALdatabase:Focusi"gtechniquesf0remcientclassidentifi— cation[C】//Pr0ceedings0f出e4tllIntemationalSymp0sium0nAd— vancesinSpatia1Datab鹊es,LNCS951.kndon:Spnger-Verlag, 1995:67—82. [4】ESTERM,KRIEGELHP,SANDERJ,口Z.Adensity_basedal— g0rithmfdiscoveringclustersinldrgespatdatabasewithnoise [C】//KDD一96:Pn.ceedings0fthe2ndInternationalConrence onKnowledgeDisc0veringaIldDataMini"g.P0rtland,0reg0n:【s. n.】,l996:226—231. [5】GUHAS,RAST0GIR,SHIMK.CURE:Anemcientclustering alg0rit}Imf0rlargedatabases【C】//Pr0ceedjngs0fthe1998ACM SIGM0DInlemati0nalC0nferenceonManagement0fData.New Y0rk:ACMPress.1998:73—84. 【6】AGRAWALR,GEHRKEJ,GUNOPOLOSD,et0Z.Aut0m"c subspaceclustedng0fhighdimensionajdataf_0rdatamining印piica' ti0n【C】//Proceedings0ftIleACMSIGMODIntemationalC0nfe卜 ence0nVeryLargeDataBases.R0?MorganKaufm叽nPubl ers.20o1:331—340. [7]ALEXANDROSN,YANNIST,YANNISM.C2P:Clusteringbased 0nclosestpairs【C]//Proceedings0fthe27thIntemationalConfe卜 ence0nVeryI哪eDatabases.Roma:Morg虮KaufmallnPublish, ers.2o01:331—34O. [8】周水庚,周傲英,曹晶,等.一种基于密度的快速聚类算法[J】.计 算机研究与发展,2O0o,37(11):1287一l292. (上接第2493页) 【2】HEcKERMAND,GEIGERD,cHIcKERINGD.LearningBayes— iaI1networks:Thecombination0fknowledgeandstatisticaldata [J].MachineL?ming,1995,2O(3):197—243. 【3】GEIGERD,HEcKERMAND.LeamingGaussiannetworks[c]// Proceedings0fthe1OthC0nferenceonUncertaintyinAn浓cialIntel— lince.san五hnsc0,cA:【s.n.】,1994:235—243. 【4】王飞,刘大有,薛万欣.基于遗传算法的Bayesian网中连续变量 离散化的研究[J】.计算机科学,20o2,25(8):794—80o. [5】FAYYADU,IRANIK.Multi—intervaldiscretizati0nofcontinuous— Va1uedattributesf0rclassicati0nleaming[C】//UCAI'93:Pr0一 ceedings0f1993Intemati0na1JointC0nferenceonArt墒ciaIIntelli. gence.SanFr.衄sisc0,CA:M0唱anKa1lfmann,l993:lO22—1027. 【6]PFAHRINGERB.Compressi0n.baseddiscretization0fc0ntinuous vables[C]//Pmceedings0fthe12thIntemationalC0nference0n MachineLe哪ing.SanFmsisco,CA:MorganKaufmann,l995: 456—463. f71FRIEDMANN,G0LDSZMIDTM.Discretizati0n0fcontinu0usat. tuteswhileleamingBayesiannetworks[C]//ISML'96:Proceed— ings0ft|le13thIntemationalC0nferenceonMachineLeanling. 1996:l57—165. [8】王国胤.R0ugll集理论与知识获取【M].西安:西安交通大学出 版社,2oo1. 【9】潘巍,李晋川,王阳生,等.基于决策的剥离式连续属性离散化算 法【J1.计算机科学,2007,34(8):2O8—2l0. [10】NGUYENHS,SK0WRONA.Quantizati0n0frealvaluesattributes roughsetsandB00leanreas0ningapproaches[C】//Pr0ceedings0f the2ndJ0intAnnualConference0nInfomIationScience.w堍hts- vi11eBeach,NC:【s.n.】,1995:34—37. 【11]NGUYENHS.Discretizati0nproblemforroughsetsmeLhods[C】// RSCTC'98:Pr0ceedings0fthelstIntemati0nalCorrenceon RouSetsandCunentTrendsinC0mputing.warsaw,Po1and:【s. n.],l998:545—552. [12]赵军,王国胤,吴中福,等.基于粗集理论的数据离散化方法[J】. 小型微型计算机系统,2O04,25(1):60—64. [13】彭佳文.一种改进的启发式离散化算法及应用【J】.计算机与现 代化,20o8(9):51—53. ?,厘莒