基于聚类生成图的空间网络对象聚类.pdf

《基于聚类生成图的空间网络对象聚类.pdf》由会员分享，可在线阅读，更多相关《基于聚类生成图的空间网络对象聚类.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2019 年 6 月第 45 卷 第 6 期JOURNAL OF BEIJING UNIVERSITY OF TECHNOLOGY北京工业大学学报Vol. 45No. 6Jun. 2019基于聚类生成图的空间网络对象聚类(1. 北京工业大学信息学部 , 北京摇 100124; 2. 郑州大学智慧城市研究院 , 郑州摇 450001)摘摇 要: 为了解决现有聚类技术难以适应大规模空间网络对象的聚类问题 ,提出了一种基于聚类生成图的空间网络对象聚类算法,以便降低空间网络对象聚类的时间复杂度和空间复杂度 . 首先,对网络中的非空边进行概略化聚类;然后,在此基础上,构建聚类生成图;最后,查找聚类生成图

2、的连通子图 ,每个连通子图即为一个聚类 . 实验结果表明该方法在保证准确性的同时具有良好的效率和可扩展性 .关键词: 空间网络; 聚类块; 聚类生成图; 概略化聚类中图分类号: TP 391doi: 10. 11936/ bjutxb2017120011文献标志码: A文章编号: 0254 -0037(2019)06 -0524 -10郭黎敏1, 蔺春华1, 高摇 需2, 苏摇 醒1Efficient Clustering Objects for Spatial Network Using CB鄄graph(1. Faculty of Information Technology, Beiji

3、ng University of Technology, Beijing 100124, China;2. Smart City Institute, Zhengzhou University, Zhengzhou 450001, China)GUO Limin1, LIN Chunhua1, GAO Xu2, SU Xing1Abstract: To solve the problem that the existing clustering technology cannot adapt to the clusteringwas proposed in this paper, which

4、can effectively reduce the time complexity and space complexity.problem of large鄄scale spatial network objects, an efficient method of clustering objects for spatial networkFirst, blocks were clustered based on buckets for non鄄empty edges in the network. Then, the CB鄄graphwas constructed, and finall

5、y the connected sub鄄graphs of the CB鄄graph was found, where each connectedefficiency and scalability while guaranteeing accuracy.Key words: spatial network; cluster block; CB鄄graph; bucket鄄based clustering摇 摇 聚类技术是数据挖掘的核心技术 ,其目标是使同组对象之间的相似性最大 ,而不同组对象之间的差异性最大. 聚类技术在诸多领域具有广泛应用,例如图像处理、数据压缩和模式分类等 . 其中,空

6、间对象聚类一直是备受关注的热点 .然而,现有的大多数方法主要关注欧式空间对收稿日期: 2017鄄12鄄08基金项目: 国家重点研发计划资助项目(2017YFC0803300); 北京市教育委员会科技计划资助项目(KM201810005023,作者简介: 郭黎敏(1984), 女, 讲师, 主要从事移动数据库 ,移动数据挖掘 ,大数据的存储 、查询与分析方面的研究 , E鄄通信作者: 高摇 需(1980), 男, 讲师, 主要从事移动数据库 ,移动数据挖掘 ,大数据的存储 、查询与分析方面的研究 , E鄄mail: gao. d. xu gmail. commail:guolimin bjut.

7、 edu. cnKZ201610005009);国家自然科学基金资助项目 (61402449, 61703013, 91546111, 91646201)sub鄄graph was a cluster.The experimental results demonstrate that the proposed method has good象聚类1鄄4,鲜有针对空间网络对象聚类的研究 . 在现实世界中,空间对象往往受限于网络环境,例如道路网络等 ,因此空间网络中的对象聚类更具有现实意义及应用前景 ,可应用于交通拥塞检测 、城市规划等领域 ,如在智能交通领域中 ,通过车辆聚类可以得到道路网络中的

8、密集区域,进而用于标摇 第 6 期郭黎敏, 等: 基于聚类生成图的空间网络对象聚类525识拥塞区域 ,并提供路径规划及导航服务等 . 可以说,空间网络对象聚类技术已经得到了人们日益广泛的重视 .总体上来说,空间网络对象聚类可以分为 3 类:基于划分的方法、基于层次化的方法和基于密度的方法. 基于划分的聚类算法中的典型代表是 K鄄Means5,它将目标对象划分为 k 个分组,并在迭代过程中不断交换对象直至满足聚类标准 ;基于层次化的聚类算法包括自顶向下 (分裂的层次聚类 )和自底向 上(凝聚的层次聚类) 2 种,代表算法有者开发了云平台19鄄20上的一系列聚类算法21鄄22,代 表 性 的 有

9、PDBSCAN23、 MR鄄DBSCAN24和DBSCAN鄄MR25等. 然而,这些聚类算法仅适用于欧式空间,无法应用于空间网络对象聚类问题 .本文研究了在聚类生成图的基础上 ,如何实现空间 对象的聚类,与本文最相关的工作是文献cls 和 nb鄄cls,其基本思路是在网络连通性的基础上避免盲目的对象搜索,并以广度优先方式遍历原始网络寻找可能合并的聚类. 然而这些算法依13, 它提出了基于边和基于结点的聚类算法eb鄄BIRCH6和 CURE7类算法无须事先确定聚类数量. 相较而言;基于密度的聚类算,基于层次化的聚法能发现任意形状的聚类 ,并且能发现噪声对象,代表DCPGS算 法 有OPTICS1

10、9、GEC10、EBSCAN、11DBSCAN2.、 ACSD8、然而,上述算法主要针对欧式空间对象聚类 ,不能有效解决网络中的空间对象聚类问题. 为此,文献12 提出了一种层次化聚类算法single鄄link,它的基本思路是将每个对象初始化为一个聚类 ,并分配了大容量的堆来存储将要合并的聚类对 . 但是当空间对象太多、太密集时,该算法的时间消耗和存储代价都很高. 同时,文献12 还提出了一种基于密度的聚类算法 着鄄link,即在遍历网络的过程中将空间对象插入聚类中. 由于改变了聚类与网络结点的结构,需要重复访问结点的邻接边及其上的空间对象. 当聚类包含多条边时 ,遍历过程需要更新每个结点与当

11、前聚类的距离,而当网络中的对象密集时 ,重复访问相邻边中的对象会产生不必要的代价 . 为了解决 single鄄link 及 着鄄link 带来的对象重复访问及内存空间消耗过大的问题 ,文献13 提出了基于边和基于结点的聚类算法single鄄link离边结点的远近顺序访问每个对象及 着鄄link 类似,eb鄄cls它们都需依据空间对象距和 nb鄄cls. 但是,与,然而对数据有序的假设往往很难成立,例如车辆 GPS 数据可能是无序的.随着超图14在数据挖掘领域的广泛应用 ,研究者在超图聚类方面也进行了大量的研究 . 超图是一般图的泛化,一条超边可以与多个顶点相连接 ,可用于表达复杂的结构和关系

12、. 超图聚类15的原理是将超图中的结点根据某种准则进行划分 ,使得划分之后的各个结点子集内部相似度较高 ,而结点子集ENHG之间的相似度较小 代表算法有 HGC1618.,、PHSC17、与此同时,为了解决大规模数据聚类问题 ,研究赖于空间对象在网络中的边上的局部有序性,当网络复杂、空间对象较多 、密度较大时 ,需要遍历大部分网络 ,代价很高 ,难以适应大规模空间对象的聚类问题 .为了解决上述问题 ,本文提出了一种基于聚类生objects成图法. COCGfor的spatial空间网的基本思路是network络对象:using聚类首先对网络中的非空边CB鄄graph,COCG)( effici

13、ent clustering方进行概略化聚类 ;然后在此基础上 ,构建聚类生成图;最后查找聚类生成图的连通子图 ,每个连通子图即为一个聚类1) 提出了基于聚类生成图的聚类框架. 归纳总结本文的主要贡献如下COCG;:2)3)提出了基于边的概略化聚类方法4)提出了聚类生成图的构建方法验证了 COCG 算法在空间网络对象聚类方;面良好的效率和可扩展性 .1摇问题定义本节给出了问题定义 ,并描述了空间网络对象聚类问题. 表 1 列出了本文使用的符号.表 1摇符号描述表Table 1摇Symbols and meanings符号描述符号描述G空间网络bkt概略化桶v、ni结点V结点集合e边E边集合W(

14、e)边的权值 / 长度loc. pp 的距离o、p、q空间对象S空间对象集合Dd(p, q)p 与 q 的直接距离 Dn(p, q)p 与 q 的网络距离1郾 1摇基本概念问题定义之前,本小节先引入文献 5 中的网络、网络距离及聚类块等基本概念 .526北摇 京摇 工摇 业摇 大摇 学摇 学摇 报2019 年表 2摇聚类块实例表网络是一个无向有权图 G = (V, E, W),其中 V是顶点集合;E 是边的集合 ,W:E寅R+表示对应边式中:e = (ni, nj)是 o 所在网络的边的 2 个结点,且满足偏序关系 ni nj;loc沂0, W(e) 是 o 与 ni之间的距离.集合 S =

15、p1, p2, , p13,其中 n1 n6为 G 中的结点. 空间对象以 p1为例,其所在边为(n1, n2),与 n1距离 4 m. 因此,p1可表示为 p1= (n1, n2, 4).图 1 举例说明道路网络G 及其上的空间对象的权值. 空间对象用三元组 o = (ni, nj, loc)表示,标号CB1CB2CB3CB4Table 2摇Instance of clustering blocks聚类块p1、p2p3、p4p5p6标号CB5CB6CB7CB8聚类块p7、p8、p9p11、p12p13p101郾 2摇问题定义图 1摇道路网络及空间对象摇Fig. 1摇Road network

16、with object points给定网络中 2 个空间对象 p = (nq = (na, nb, locp)和c接距离和网络距离, nd, locq),p.、若q 之间的距离可分为p、q 在同一条边上2,则类:p直、q之间的 直接距离 DDd(p, q) = | locp- locq|,否则的网络距离d(p, q) = 肄D;若 p、q 不在同一条边上,则 p、q 之间Dn(p, q) =x沂(a,minb),y沂(c,d)Dd(p,nx) +n(nx, ny须遍历网络即可在常量时间内求得) + Dd(ny, q) . 其中第 1;类直接距离无而第 2 类网络距离需要遍历网络求得最短网络距

17、离2;p,代价较高 .以图 1 中的空间对象为例 ,Dd(p1,2) = |6 - 4 | =DDd(p1, p3)聚类块是在网络某条边上的一个微小聚类D=d(n肄;Dn(p2,p6) = Dd(p2,n2) +n(n2, n5) +5, p6) =8.,表示为 CB = (O, na是空间对象的集合,nb且满足相邻空间对象之间的直),其中 O = o1, o2, , on(接距离小于等于距离阈值na,为了nb)是表CB述准所在的边确, 定.着,即 Dd(oi, oi +1)臆着,block,CB)义了最大聚类块 ( cluster再扩CB大,即,CB 是最大聚类块当且仅当 CB 不能表忆.2

18、 所示以图.1不为例存在,假设其他着聚=类2,块所有最大聚类块如CB忆,使得 CB 奂本小节定义了边界对象、聚类生成图等概念,并描述了空间网络对象聚类问题 .为了更好地描述聚类生成图 ,引入了边界对象的概念.定义 1(边界对象)摇给定聚类块 CB = (O, nna,b),CB 的边界对象BBCB表示为式中:BlCB= BlCB胰BrCBCB是 CB 的左边界对象 ,即 O 中距离结点 na最近的空间对象;Br距离结点 nCB是 CB 的右边界对象 ,即 O 中b最近的空间对象.依据边界对象的定义 ,聚类块之间的网络距离可描述为聚类块边界对象之间最小的网络距离(CB=,即Dni, CBj)p沂

19、Bn(p, q)(clusterO,定义n2(连接性聚类块)摇CBmini,q给定一个聚类块沂BCBjDCB =a, nb), 则 CB 称为连接性(1)CBblock,CCB)是边(n当且仅当满足如下条件聚类块:(connecta类块;, nb)上的第一个或最后一个聚(2)埚第 2 个条件限定了oi沂O,Dd(oi,CBna)臆所在边的结点着 或 Dd(oi,nnb)臆着.CBa或 nb与效结的距离必须小于等于VN点, 记作 VNCB.即着若,则该结点称为DnCB 的有CB= n( na, CB) 臆 着, 则a;若 Dn(nb, CB)臆着,则 VNCB= nb.当 CB 不是边(na聚类

20、块时,CB 称为确定性聚类块, nb)上的第一个和最后一个DCB.(块块)连接性聚类块描述了可能再继续合并的聚类). 相应地,确定性聚类块是不可再合并的聚类以图.1 为例,假设 着 = 2,网络 G 中对应的连接性聚类块、边界对象及有效结点如表 3 所示.定义 3(聚类生成图 )摇给定一个网络 G,聚类生成图CB ,是CB一个无向图 G忆 = (V忆, E忆), 其中 V忆 =12, ,边CBn集合;E忆是聚类的集是合,G且中所有最大聚类块的E忆 = ( CBi, CBj) |摇 第 6 期郭黎敏, 等: 基于聚类生成图的空间网络对象聚类527摇 摇表 3摇连接性聚类块、边界对象及有效结点实例

21、表Table 3摇Instance of CCB, boundary objectsand valid nodes连接性聚类块CB1CB2CB3CB4CB5CB6所在边(n1, n2)(n2, n5)(n3, n5)(n5, n6)(n4, n6)(n1, n4)边界对象p1、p2p3、p4p5p6有效结点n2、n5n3n5n4n2输出:对象的聚类结果.阶段 1:找出 G 中所有非空边上的最大聚类块 ,构造聚类生成图的顶点 ,并生成连接性聚类块相应的汇聚-连接锚点;阶段 2:根据汇聚-连接锚点合并聚类 (块),并构造聚类生成图的边;阶段 3:查找聚类生成图的连通子图 ,每个连通子图中的空间对象

22、为同一个聚类 .COCG 算法第 1 阶段的主要问题在于如何有效p7、p9p10n4、n6地组织空间对象,尽量减少空间对象的访问和比较CB8(n2, n3)p13n3D(VNn(CBi, CBj) 着 时,bkti和 bktj中的空间对象属于不同聚类块.属性 4摇 若|j - i|逸3,且坌k沂(i,j),bktk则 bkt 和 bkt= 芰,ij中的空间对象属于不同聚类块 .在概略化桶的基础上 ,设计了基于边的概略化聚类算法,如算法 2 所示,其利用桶间对象分组有序而桶内对象无序的思路有效地降低了聚类的时间和空间复杂度.cluster算法 2摇基于边的概略化聚类 Bucket鄄based鄄输

23、入:空间网络 G,空间对象集合S,距离阈值 着.1输出:聚类生成图 G忆2.边集.V忆的顶点集合 V忆.E饮饮FindNonEmptyEdge(芰;G, S);椅 找出 G 中非空34. 摇foreachSe =(na, nb)沂E do摇摇 椅处理每条非空边e象集合饮ExtractObjOnEdge( e, S);椅 获取 e 上的对略化桶5. 摇 BKT饮SplitEdge(e,着); 椅均分 e 为长 着/2 的概67.8.摇空桶.摇foreach摇摇bktbkto沂Seo.着/loc2饮appenddoo to bkto.着/loc2;pre饮FirstNonEmptyBkt(BKT)

24、; 椅第 1 个非910. 摇 id饮1; CBl11.id饮bktpre; 椅初始化第 1 个聚类块.摇摇if摇DHCAd(B饮CBHCA胰掖id,na)臆着nthen12. 摇 椅循环处理 BKT 中第a,1CB个非空桶后的每个非id, BlCBid业;13空桶bkt. 摇foreach bktnext饮 NextNonEmptyBkt ( BKT,14pre) do15. 摇 摇 if (next -pre)臆1 then摇摇 摇 摇 摇椅属性116.摇摇摇摇摇elseCBifid饮(nextCBid-胰bktpre)臆2next;and2425.摇return摇 HCA饮HCA胰掖 n

25、b, CBid,BrCBid业;在算法V忆2;中,首先初始化顶点集合V忆,并调用函数 FindNonEmptyEdge( )找出空间网络 G 中所有的非空边(行 1、2). 然后依次处理每条非空边 e,调用函数 ExtractObjOnEdge() 获取 e 上的空间对象集合 SeBKT,=将bkte 均分为若干长度为 着/2 的概略化桶ii沂0,W着(/e2)-1,并将 e 上的每个对象存入对应的概略化桶中 ,此时桶间对象分组有序(行 3 7). 然后调用函数 FirstNonEmptyBkt()从 BKT 中找到第一个非空桶如果 CB,将其初始化为第 1 个聚类块 CB1,1中的左边界对象

26、与结点na的直接距离小于等于 着,则 CBCB1是连接性聚类块 ,可能再继续合并,生成入集合HCA(行8 11)1的汇聚-连接锚点 ,并将其加. 接下来依次处理每个非空桶 ,调用函数NextNonEmptyBkt()获取下一个非空桶 ,依据属性 1 5 判断前后 2 个非空桶之间的空间对象是否属于同一聚类:若属于同一聚类 ,合并聚类块 ;否bkt则, 将当前聚类块放入顶点集合 V忆 中, 并为22)next桶中的对象构造一个新的聚类块(行 12 点 n. 同样,判断最后一个聚类块的右边界对象与结b的直接距离是否小于等于 着,若是,则为其生成汇聚-连接锚点 ,并加入集合 HCA 中(行 23、2

27、4) .最后返回生成的顶点集合 (行 25).为了提高聚类生成图的遍历效率 ,算法 2 将连接性聚类块的汇聚 -连接锚点存储在 HCA 中,因此仅需为连接性聚类块及生成的边构造CCAM26索引,缩小了索引树.以图 1 中的道路网络为例 ,图 3 举例说明基于边的概略化聚类过程 . 假设 着 =2 m,每个虚线框对应一个聚类块,构成聚类生成图中的结点 . 此外,还需判断每条边上第 1 个和最后一个聚类块距离边上结点的距离是否小于等于 着,若是,则生成汇聚 -连接锚点,图中用不同颜色的结点和聚类块表示了相关联的汇聚-连接锚点,可以看出,除边(n1, n3)之摇 第 6 期郭黎敏, 等: 基于聚类生

28、成图的空间网络对象聚类529间的聚类块 CB7距两端点都较远外 (属确定性聚类块),其余聚类块都为连接性聚类块 .间的边上没有空间对象,且 CBnext与 v 的网络距离不大于 着,则生成 CBnext与 v 的汇聚-连接锚点,继续迭代,直至处理完所有的有效结点 (行 7 9), 返回聚类生成图的边集合 E忆.然而,直接访问原始网络的索引树查找邻接结点和邻接边的效率较低 ,可以使用算法 2 中记录的长度不大于 着 且其上没有对象的边集合来实现 ,从而避免对原始网络的遍历 ,降低 I/ O 请求.从算法 3 可以看出,仅需遍历有效结点,而非整个网络 G 中的结点,因此在很大程度上提高了算法图 3

29、摇概略化聚类过程摇Fig. 3摇Bucket鄄based clustering process3摇聚类生成图的构建本节介绍了在连接性聚类块的基础上构建聚类生成图的边的方法.对边上空间对象概略化聚类后 ,可以找出所有的聚类块,即形成聚类生成图的结点 . 此外,还能找出所有连接性聚类块及其汇聚 -连接锚点. 在此基3础之上所示.,提出了聚类生成图的边的构造算法 ,如算法算法 3摇聚类生成图边的构建 Gengerate鄄edge输入:网络 G,汇聚-连接锚点集合 HCA.1输出. foreach:聚类生成图valid nodeG忆vn沂HCA的边集合doE忆.23.摇摇CBforeachmin饮Fi

30、ndNearestCB(HCA,CBnext饮FindNextCB(HCA,vn);4. 摇 摇 if Dn(CBmin, CBnext)臆着 thenvn) donext) in6G忆5.7. 摇;摇摇摇Construct a edge e忆 = (CBmin, CB摇 摇 E忆饮E忆胰e忆;8.9.摇.摇摇摇摇foreach摇摇摇if摇DHCAn(CBv adjacent饮nextHCA胰掖CB, v)臆to vn着夷inS(vn,G dov)10. return E忆3;next, v,=B芰CBthennext(v)业;在算法中,对于 HCA 中的每个有效结点 vn,调用函数 Find

31、NearestCB( )找出在 HCA 中距离 vn最近的聚类块 CB块的非递减顺序,min调用(行FindNextCB(1、2), 然后依据)获得下一个次vn 与聚类近的聚类块 CBnext,依次判断 CBmin与 CBnext之间的网络距离是否小于等于CB着,如果满足 ,则构造 CB之间的边(行 3 6). 如果 vn 与邻接结点min与nextv 之效率. 同时,在构造聚类生成图的边时 ,在最小边生成的启发式方法下,仅需构造距离有效结点最近的连接性聚类块与其余连接性聚类块之间的边 ,进一步降低了计算代价 ,也减少了聚类生成图中边的数量.以图 3 为例,假设 着 = 2,依据原始网络的有效

32、结点和连接性聚类块 (分别用不同颜色的结点和聚类块表示 ), 图 4 举例说明了构建的聚类生成图的边.图 4摇聚类生成图边的构建摇Fig. 4摇Construction of CB鄄graph算法 3 所构建聚类生成图的边可以保证属于同一聚类的聚类块是连通的 ,并且不会遗漏聚类块 .接下来通过反证法来证明算法 3 的正确性.证明:假设聚类生成图 G忆中的 2 个聚类块 CBi和CBCBj属于同一聚类 ,然而它们之间不连通 . 如果假设距离(CBi和 CBj只 通 过 一 个vn有 效 结 点 vn1相 连, 则Dni, CBj) = Dd(CBi,1) + Dd(CBj, vn1)臆着.CBv

33、n1最近的聚类块是 CBmin,那么 Dn(CBmin,vni) =+DDdd(CBCBmin, vn1) + Dd(CBi, vn1)臆Dd(CBi1,j, vn1)臆着,因此 CBmin与 CBi之间会构造一条边(行 4 6); 同理,CBmin与 CBj之间也会构造一条边,由此 CBi与 CBj之间是连通的 ,这与假设条件相矛 盾. 如果 CBi和 CBj依次通过有效结点530北摇 京摇 工摇 业摇 大摇 学摇 学摇 报2019 年vn1, vn2, , vnm相连,则 Dn(CBi, CBj) = Dd(CBi,vn1)臆着,且每条边(vnk, vnk +1)( 其中 1臆k臆m -1

34、)vn1) + W(vn1, vn2) + + W(vnm -1, vnm) + Dd(CBj,上都没有空间对象 . 算法 3 会逐渐生成 CBi与 vnk(1臆k臆m)的汇聚-连接锚点,直至生成掖CBi, vnm,BCBi(vnm)业( 行 7 9), 此时发现与 vnm相连的 CBj,且 Dn(CBi, CBj)臆着,因此 CBi与 CBj之间会构造一条边(行 4 6),由此 CBi与 CBj之间是连通的 ,这与假设条件相矛盾.2郾 0 GHz CPU、10 GB 内存和 500 GB 本地磁盘,软件环境为 Ubuntu 14郾 04 Server,结点之间通过千兆以太网 互联,MapRe

35、duce 框架基于 Hadoop 0郾 20郾 1b版本.实验采用了来自 OpenStreetMap 的真实数据集,其中道路网络为德国道路交通网络 ,空间对象数据为用户提交的位置数据 . 并在此基础上 ,使用随机采样构造了 10、20、40、80 MB 的空间对象.台计算结点,每台结点的硬件环境配置为 Quad鄄Core4摇性能分析与实验4郾 1摇算法分析本小节对 COCG 算法性能进行了分析.在 COCG 算法框架中,聚类过程分为 3 个阶段:阶段 1 要扫描所有空间对象并将其存放在对应的概略化桶中,计算代价为 O( | S|),其中 S 为空间对象的集合. 在聚类过程中要扫描每条边的非空概

36、略化桶,计算代价的上限为O(2( ) / 着),其中2移移W( )为原始网络中所有边长之和移W. 由于|S|垲W( ) / 着,而在极端情况下每个空间对象占据一个概略化桶1 的总代价为,O检索非空桶的次数为( |S|).| S|,因此阶段阶段 2 要遍历原始网络 G 中的有效结点 ,最坏的情况下需要遍历 G 中所有结点. 假设 G 中每个有效结点平均对应 r 个连接性聚类块,则汇聚-连接锚点数量也为 r,对其排序代价为 O(rlb r),因此阶段 2的总代价为 O( |V|rlb r).阶段 3 使用广度优先遍历找出聚类生成图中的所有连通子图,总代价为 O( |V忆| + |E忆|).根据上述

37、分析,在 COCG 聚类算法的总代价为O( |S| ) + O( | V | rlb r) + O( | V忆 | + | E忆 | ). 由汇聚-连接锚点定义可知,| V忆| r| V|,因此 COCG 计算代价 的上限为 O ( | S | +lb r +)r)=.O( |S| + c|V|),其中|cV为常量| rlb r,+cr=|rV(1| +r2|V|+4郾 2摇实验结果与分析为了验证复杂网络中大规模空间对象聚类的性能,本小节实现了基于MapReduce 框架下的并行化聚类算法 ,对 COCG 的性能进行了一系列实4郾验验证2郾 1摇.实验中的实验配置和数据集Hadoop 集群包括

38、 1 台主控结点和 32实验实现了基于 MapReduce 框架下的聚类算法single鄄linkCOCG鄄MR, 并与改进的 MapReduce 框架下的模、距离阈值和结点数和 eb鄄cls 进行了性能比较3 个方面测试算法的性能. 将从数据规.参数设置如表 4 所示.表 4摇试验参数设置Table 4摇Experimental settings参数数据规模 |S|结点数 N距离阈值默认值摇803280变化范围10 804 3220 1004郾 2郾 2摇本小节在模拟数据集的基础上验证了准确性验证COCG 算法的准确性.使 用 了 Oldenburg 的 交 通 网 络 数 据27Olden

39、burg径由折线段表示的数据集由结点和边组成的,. 交通网络中的空间对象是采用通,并且每条路用的移动对象生成器产生的27鄄28据预定义的交通网络产生运动的移动对象轨迹,该生成器可以根. 为了使数据更适合实验,对生成器的源码进行了修改 ,采用了 COCG 算法对其空间对象进行聚类 ,不同聚类的空间对象使用不同的颜色表示 ,并且限制所有空间对象在一定的区域(称为“实验区冶) 内,以便于观察,如图 5 所示.图 5摇准确性评估Fig. 5摇Accuracy evaluation摇 第 6 期郭黎敏, 等: 基于聚类生成图的空间网络对象聚类531从图 5 可以看出 ,COCG 算法能准确地找出属于同一

40、聚类的空间对象,而不会发生遗漏 . 以绿色、棕色、紫色和黑色的聚类为例,每个聚类的空间对象之间最多通过 1 个有效结点相连 ,它们都能被准确聚类;而红色、黄色和蓝色的聚类中的空间对象之间则最多由 2、3、4 个有效结点相连 ,也可以准确地找出同一聚类. 这些实验结果与第 4 节中的算法正确4郾 2郾 3摇数据规模的影响效果性分析是一致的.本小节测试了数据规模对 COCG鄄MR 的性能影响. 实验从两方面验证:1) 固定结点数 N =32,测试距离阈值 着 变化时,数据规模 | S | 对算法性能的影响;2) 固定距离阈值 着 =80,测试不同结点数 N 下,数据规模|S|对算法性能的影响.从图

41、 6(a) 可以看出,计算结点数固定时 ,随着数据规模的增长 ,COCG鄄MR 的执行时间呈近线性增长ms;数据量增加至而. 以着 =着80、=80、|S| =20 MB 为例,执行时间为 6802S倍| =,40而执行时间仅增加了MB 时,执行时间为1郾89031ms.倍,具有良好的可扩展性 . 图 6( b) 表示距离阈值 着 固定时,随着数据量的增长 ,COCG鄄MR 的执行时间也呈近似线性增长,且随着 N 值的增大,COCG鄄MR 的执行时间增长变平缓 ,主要原因在于数据量小的情况下,结点中能容纳更多计算任务,随着数据量增加,COCG鄄MR 的执行时间的增长反而不明显. 例如,|S|从

42、 10 MB 增至 40 MB,当 N =8 时,执行时间分别增长了 1郾 12、1郾 26 和 1郾 35 倍;而 N = 32 时,执行时间分别增长了 1郾 28、1郾 30 和 1郾 46 倍,计算资源4郾得到了充分利用2郾 4摇距离阈值的影响效果.本小节测试了距离阈值对 COCG鄄MR 性能的影响. 实验从两方面验证:1) 固定结点数 N =32,测试不同数据规模 | S | 下,距离阈值 着 对算法性能的影响;2) 固定数据规模 |S| =80 MB,测试不同结点数N 下,距离阈值 着 对算法性能的影响.从图 7(a) 可知,结点数固定时 ,随着距离阈值着 的增长,COCG鄄MR 执

43、行时间的波动较小. 图7(b)说明数据规模固定时,在不同计算结点数情况下 ,距4郾离阈值2郾 5摇着计算结点数的影响效果的改变对执行时间影响较小 .本小节测试了计算结点数对 COCG鄄MR 的性能80影响MB,.测试距离阈值实验从两方面验证着 变化时:1),结点数固定数据规模N| S | =的影响;2) 固定距离阈值 着 =80,测试不同数据规模对算法性能图 6摇数据规模 |S|的性能影响摇Fig. 6摇Effect of |S|图 7摇距离阈值 着 的性能影响摇Fig. 7摇Effect of 着|S|下从图,结点数8(a)N中可以看出对算法性能的影响,数据规模固定时.,在不同距离阈值 着

44、的条件下 ,随着计算结点数的增多 ,532北摇 京摇 工摇 业摇 大摇 学摇 学摇 报2019 年COCG鄄MR 的执行时间呈近似线性降低 . 在图 8(b)中,距离阈值 着 固定时,数据规模越大 ,随着计算结点数的增多,COCG鄄MR 的执行时间下降更快 ,说明算法能充分利用计算资源 ,体现算法具有良好的可扩展性.图 8摇计算结点 N 的性能影响摇Fig. 8摇Effect of N4郾 2郾 6摇本小节实现了在不同算法的性能比较COCG鄄MR 框架下局部聚类采用修改的 single鄄link、eb鄄cls 和 nb鄄cls 算法,分别称为COCG鄄MR鄄single、COCG鄄MR鄄eb将

45、其与本文提出的概略化聚类和COCG鄄MR鄄lscCOCG鄄MR鄄nb,进行并性能比较. 实验从两方面验证 :1) 计算结点数 N =32能;2)及数据规模计算结点数| S | =N80=32MB及距离阈值时,比较不同算法的性着 =80 时,比较不同算法的性能.从图 9( a) 中可以看出 ,在不同距离阈值着 的条件下,各算法计算时间平稳 ,但不同算法间差异较大,主要原因在于非概略化本地聚类时,需要对数据 进行排序,耗费时间较大,其中 COCG鄄MR鄄single文所提的需要对数据多次扫描COCG鄄MR鄄lsc 的性,算法性能最差能最优. 图 9(;b)而本表明,计算结点数量 N 及距离阈值 着

46、 固定时,随着数据规模的增长 ,计算时间都呈线性增长趋势,而本文所提的 COCG鄄MR鄄lsc 的计算时间增长最缓慢,扩展性最佳 .图 9摇性能对比摇Fig. 9摇Performance comparison5摇结论出了该问题的形式化定义1) 本文提出一种空间网络对象的聚类方法,提出了基于聚类生成图,给的空间网络对象聚类算法边的概略化聚类2) COCG 聚类框架分为COCG.、聚类生成图的构建和聚类生成图3 个部分,分别是基于的连通子图查找 . 实验结果表明 ,COCG 具有良好的效率和可扩展性.参考文献1 ANKERST:Optics:M, BREUNIG M M,International

47、C 椅orderingProceedingspoints toofidentifyKRIEGELthe1999the clusteringH P, et al.ACMstructure2York:ESTERACM,Conferencedensity鄄basedM, KRIGEGEL1999: 49鄄60.on Management of Data.SIGMODNewH P, SANDER J, et al.AspatialSeconddatabasesalgorithmInternationalwithConferencenoisefor discovering Cclusters in la

48、rgeon椅 Proceedings of the3andLIProceedingsY,DataHANMining.J, YANGNewJ.York:ClusteringACM,Knowledgemoving1996: 226鄄231.DiscoveryobjectsC椅Conference onofManagementthe 2004ACMofSIGMOD International42004:Data.New York: ACM,JENSEN617鄄622.C S, LIN5movingKARYPISobjectsJ.D,G, KUMARTKDE,OOI BV.2007,C. Contin

49、uous clustering ofA fast19(9):and1161鄄1174.high quality摇 第 6 期郭黎敏, 等: 基于聚类生成图的空间网络对象聚类533multilevelschemefor partitioningirregular graphsJ. SIAMJournal on ScientificComputing,1999,20 (1): 359.6 ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: anefficient data clustering method for very large databases C 椅 P

50、roceedingsofthe1996ACMSIGMODInternational Conference on Management of Data.NewYork: ACM, 1996: 103鄄114.7 GUHA S, RASTOGI R, SHIM K.CURE: an efficientclustering algorithm for large databases C 椅Proceedingsof the 2018 ACM SIGMOD International Conference onManagement of Data. New York: ACM, 1998: 73鄄84