留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

滚圆法用于空间点聚类的研究

职露 余旭初 李光强

职露, 余旭初, 李光强. 滚圆法用于空间点聚类的研究[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
引用本文: 职露, 余旭初, 李光强. 滚圆法用于空间点聚类的研究[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
ZHI Lu, YU Xuchu, LI Guangqiang. Spatial Point Clustering Analysis Based on the Rolling Circle[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
Citation: ZHI Lu, YU Xuchu, LI Guangqiang. Spatial Point Clustering Analysis Based on the Rolling Circle[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287

滚圆法用于空间点聚类的研究

doi: 10.13203/j.whugis20160287
基金项目: 

卫星测绘技术与应用国家测绘地理信息局重点实验室开放基金 KLSMTA-201603

地理信息工程国家重点实验室开放研究基金 SKLGIE-2015-M-3-2

详细信息
    作者简介:

    职露, 博士, 主要从事时空数据挖掘理论与方法研究。zhilu_361@163.com

    通讯作者: 李光强, 博士。ligq168@163.com
  • 中图分类号: P208

Spatial Point Clustering Analysis Based on the Rolling Circle

Funds: 

The Open Research Fund Program of NASG Key Laboratory of Satellite Mapping Technology and Application KLSMTA-201603

the Open Research Fund of National Key Laboratory of Geographic Information Engineering SKLGIE-2015-M-3-2

More Information
图(5)
计量
  • 文章访问数:  1005
  • HTML全文浏览量:  128
  • PDF下载量:  374
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-11-11
  • 刊出日期:  2018-08-05

滚圆法用于空间点聚类的研究

doi: 10.13203/j.whugis20160287
    基金项目:

    卫星测绘技术与应用国家测绘地理信息局重点实验室开放基金 KLSMTA-201603

    地理信息工程国家重点实验室开放研究基金 SKLGIE-2015-M-3-2

    作者简介:

    职露, 博士, 主要从事时空数据挖掘理论与方法研究。zhilu_361@163.com

    通讯作者: 李光强, 博士。ligq168@163.com
  • 中图分类号: P208

摘要: 空间点聚类依据空间点实体属性对其进行分类划分,挖掘对研究应用有价值的信息。目前,空间点聚类大多数方法能够发现多边形簇,但不能发现线状簇。针对空间点聚类现有方法在发现线状簇方面的不足,借鉴滚球法的思想,提出滚圆法用于空间点聚类的研究算法(spatial point clustering using the rolling circle,SPCURC)。针对研究区域的点实体,该算法用给定半径的圆从初始点开始按照原则进行滚动,直至满足条件为止;连接滚圆接触的点,从而形成多边形簇或者线状簇。通过模拟算例和实际算例验证了该算法的可行性。

English Abstract

职露, 余旭初, 李光强. 滚圆法用于空间点聚类的研究[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
引用本文: 职露, 余旭初, 李光强. 滚圆法用于空间点聚类的研究[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
ZHI Lu, YU Xuchu, LI Guangqiang. Spatial Point Clustering Analysis Based on the Rolling Circle[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
Citation: ZHI Lu, YU Xuchu, LI Guangqiang. Spatial Point Clustering Analysis Based on the Rolling Circle[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
  • 大数据时代的大部分数据都具有空间属性,因此,空间数据挖掘与知识发现(data mining and knowledge discovery, DMKD)成为近年来关注的热点[1]。其中,空间点聚类是DMKD的一个重要研究方向,它可以发现点实体的空间集聚模式与空间分布特点,预测事件的发展变化趋势,成为众多研究领域的热点[2]。空间点聚类的思想是尽可能使同一类中点实体的相似性更大,不同类中点实体的差异性更大[3-4]。空间点的研究具有重要意义,点聚类研究的主要算法包括基于划分的点聚类算法、基于层次的点聚类算法和基于密度的点聚类算法[5-7]

    基于划分的点聚类算法的基础是迭代优化思想,按照划分准则不断迭代计算[8],经典算法是k-means算法,该算法运行时间较少,但局限于发现近似球形的聚类簇,不能发现任意形状的聚类簇[9];基于层次的点聚类算法的基础是递归思想,将研究目标看成一个聚类树,循环进行聚合或者分裂,该算法简单,但在操作恢复以及条件确定方面有局限性,且适用于空间分布均匀的数据[10];基于密度的点聚类算法的基础是要素之间的距离判断,经典算法是DBSCAN(density-based spatial clustering of applications with noise)算法,该算法较简单,可以发现任意形状的聚类簇, 但算法参数较多,且倾向于发现高密度分布的数据[11-12]

    随着空间数据的快速增长以及复杂度的提高,在获取空间聚类簇过程中对数据分布的全面性有了更高要求。目前为止,空间点聚类算法在发现线状簇方面仍存在不足。因此,本文提出滚圆法用于点聚类的研究算法(spatial point clustering using the rolling circle, SPCURC),该算法能够有效发现线状聚类簇,并且可以给出聚类簇的边界。通过模拟算例与实际算例证明了该算法的可行性及实用性。

    • 滚圆法(rolling circle method,RCM)是滚球法(rolling sphere method,RSM)思想的衍生概念。滚球法是国际电工委员会推荐的用来计算接闪器保护范围的方法,半径为r的球体沿着物体滚动,与物体表面接触的点生成曲面[13-14]。该方法已广泛应用于医学、计算机学、建筑学等多个领域[15-17]

      滚球法适用于三维实体,但不适合二维平面数据的分析。借鉴滚球法的概念,用半径R/2的圆按照一定规则沿着目标点实体滚动,并获取滚圆接触的点集,即滚圆法。以平面点数据为例,假设有半径为R/2的圆与点集G={ABCD},其中两点之间的距离dAB= R, dBC < R, dCD> R, 则圆从点A开始顺时针滚动的过程中可以依次接触点B与点C,但不能接触到点D,如图 1所示。

      图  1  滚圆原理示例

      Figure 1.  Example of RCM

    • 本文将滚圆法引入到地理学中,应用于空间点聚类。为方便叙述算法的原理,下面给出几个相关概念及规则。

      定义1  空间边界点集:是指圆在滚动过程中所接触到的点(空间边界点)组合成的集合。如图 1所示,点ABC为空间边界点,空间边界点集为{ABC}。

      定义2  空间滚边:是指圆在滚动过程中相邻的空间边界点连接而成的线,如图 1所示,ABBC为空间滚边。

      规则1  初始滚边从初始点(纵坐标最小,纵坐标相同时其横坐标最大)出发,以(1, 0)为基准向量,对初始点的空间近邻点做极坐标排序,选择角度最小的点作为下个空间边界点,当角度相同时,选取距离最近的点。

      规则2  下一条滚边与初始滚边的选择相似,基准向量为上一条滚边。

      规则3   3个及以上空间边界点形成聚类簇,若空间边界点集为一个或者两个,则此点为孤立点。

      SPCURC算法进行点聚类时会出现两种聚类簇:多边形簇和线状簇。如图 2(a)所示,p1为初始点,圆开始顺时针滚动,依次接触到p1~p10,发现p10的下一个滚点p11与初始点p1重合,停止滚动,将此轮滚动中的空间边界点按顺序存入到集合{p1p2p3p4p5p6p7p8p9p10},依次连接可以形成空间多边形簇。

      图  2  多边形簇和线状簇过程-示意图

      Figure 2.  Process of Formation of Polygon Cluster and Linear Cluster

      图 2(b)所示,p1为初始点,圆开始顺时针滚动,直至滚动到p3,此次滚动并未形成封闭多边形,此时,圆再次从p1开始逆时针滚动,直至滚动到p6。此轮滚动中,首先将圆顺时针滚动的点逆顺序存到集合{p3p2p1},再将逆时针滚动的点追加到此集合中,最后得到此轮的空间边界点集{p3p2p1p4p5p6},依次连接,最终形成线状簇。

    • 若已知研究区域以及滚圆的半径R/2,SPCURC算法可以描述如下。

      1) 遍历点数据,寻找初始点及初始滚边。

      2) 顺时针滚动。寻找所有滚边,直到出现以下两种情况停止寻找滚边:一是点J与先前的边界点重合时, 停止寻找滚边,将所有边界点存入到多边形集合GPolygon,连接形成多边形,执行步骤4);二是点JR邻域内没有点要素时,此时将点J作为顺时针滚动终点,并执行步骤3),同时,将此顺时针过程中的边界点存入到线型点集合GLine中。

      3) 完成线状簇的逆时针滚动。反向集合GLine中点的顺序,逆时针进行滚动,同时,将此过程中的空间边界点追加到集合GLine中,连接形成线。

      4) 从原始数据集中剔除GPolygonGLine中的点,以及不能成簇的单个孤立点,并将剔除后剩下的点作为新的研究范围的点要素,循环执行所有步骤,直至原始数据集中所有点要素被执行操作完成。

      SPCURC算法的时间复杂度分析如下。首先对点要素进行遍历,寻找目标点,其复杂度约为O(nlgn); 然后,搜索滚边的复杂度约为O(nlgn),若有m个滚边,则总的复杂度不会大于O(mnlgn),m的取值是有限的,所以搜索滚边的复杂度约为O(nlgn);计算过程中要剔除集合点和孤立点,其复杂度约为O(1)。因此,SPCURC的时间复杂度约为O(nlgn)+O(nlgn)+O(1)≈O(nlgn)。纵观空间点聚类的3类主要算法,基于划分的经典聚类算法k-means不能发现任意形状的聚类簇,基于密度的经典聚类算法DBSCAN以及层次聚类算法能够发现任意形状的聚类簇[18]。因此,为了方便验证SPCURC算法的可行性,将DBSCAN算法和层次聚类算法作为本文实验的对比算法。DBSCAN算法在每次查询判断后需要返回研究区的所有空间点,层次聚类算法涉及嵌套聚类的层次,算法时间复杂度分别为O(n2)、O(n3)[19]

    • 为了验证算法的可行性,本节进行了相关的算例分析,实验运行环境为CPU 3.10 GHz、内存4.0 GB和Windows 10操作系统,使用C# 2010和ArcEngine 10.1共同开发了实验程序。共设计了两组实验,实验一为模拟算例分析,采用两组模拟数据来验证SPCURC算法的可行性,对实验参数的不同取值分别计算聚类结果。实验二为实际算例分析,分别采用南方某地区居民地与全球部分区域2006-2015年6级及以上强震数据来验证SPCURC算法的实用性。本节同时给出了DBSCAN算法以及层次聚类算法的聚类结果,以便与SPCURC算法进行对比。

    • 模拟数据共设计两组,均由ArcGIS 10.1软件模拟生成。模拟数据1有221个点,数据呈低密度分布且空间分布相对均匀,如图 3(a)所示。模拟数据2有304个点,包含了形状不同、密度不等的空间簇,空间分布相对不均匀,如图 3(b)所示。SPCURC算法的参数R/2设置了不同的取值,分别计算聚类结果。DBSCAN算法的一个参数搜索半径Eps分别设置为滚圆R/2相同的值,另一个参数MinPts取值参考Ester等[20]提出的最优设置lnn,其中n为数据库中点个数,则模拟数据库1的MinPts=ln221≈5,模拟数据库2的MinPts=ln304≈6。层次聚类的层高分别给不同的取值进行实验。由于篇幅受限,图 3(c)~3(e)给出了模拟数据1的SPCURC、DBSCAN、层次聚类算法的最佳实验结果,图 3(f)~3(h)给出了模拟数据2的SPCURC、DBSCAN、层次聚类算法的最佳实验结果。

      图  3  模拟数据及聚类结果示意图

      Figure 3.  Results of Clusters with Sample Data

      对比图 3(a)3(c)3(b)3(f)可以发现聚类结果与原数据分布形状吻合,线状簇以及其他形状的聚类簇能够适应高密度和低密度区域数据,同时圈定聚类簇的边界。LaLb…为线状簇,PaPb…为多边形簇,其中多边形簇可以根据簇边界内是否有点数据而判读聚类簇是否为环状簇,如图 3(c)中多边形簇PbPc。从图 3(d)3(g)可以看出,当点数据呈低密度分布时,DBSCAN算法几乎不能发现聚类簇;当点数据分布不均匀时,DBSCAN算法能够发现高密度分布的聚类簇,却仍未能发现线状簇。从图 3(e)3(h)可以发现,层次聚类算法的循环剖分将原本可以归为一个聚类簇的数据点分割开。分别比较模拟数据1和模拟数据2的3种聚类算法的聚类结果可知,SPCURC算法可以发现线状簇、环状簇、多边形簇等,能够适应不同密度分布的点数据。

    • 本节使用实际数据进行SPCURC算法实用性分析。首先,采用南方某地区部分居民点数据进行实际应用分析,1 419个居民点空间分布如图 4(a)所示。类似模拟数据的参数选择方法,选取多个参数进行实验,图 4(b)~4(d)分别为SPCURC算法、DBSCAN算法、层次聚类算法的聚类结果。分析图 4可以发现,SPCURC算法能够提取出线状簇以及多边形簇,划定多边形簇的边界,进而得知多边形簇的范围、面积等信息,为救灾、政府规划等其他领域提供有价值信息。DBSCAN算法和层次聚类算法未能清楚给出线状簇,本来可以聚到一条线上的点呈分散状。另外,从图 4中发现聚类结果具有以下特点:①对比图 4(b)图 4(c)发现,SPCURC算法聚类结果中多边形簇相对较少,其范围较大;②从图 4(b)中发现,SPCURC算法聚类结果线状簇少,多边形簇相对线状簇居多。第一个特点虽然不能精细得到聚类簇,但具有实际应用价值,比如可以在地灾应急响应中为快速确定重点监测区域范围提供可行方法,因为救灾中对监测区域(聚类簇)的要求更多在于全面而非精细。第二个特点不能很好地体现出SPCURC算法在发现线状簇方面的优势,居民地的分布特点决定了多边形簇的大比例成分,线状分布少见。为了能够更好验证SPCURC算法的实用性,本节选用全球部分区域2006-2015年不低于6级的强震数据作为实验数据进行验证。

      图  4  居民地算例的聚类结果示意图

      Figure 4.  Results of Clusters with Residential Data

      强震数据空间分布如图 5(a)所示。图 5(b)为SPCURC算法的聚类结果。为了便于比较,图 5(c)5(d)给出了DBSCAN算法与层次聚类算法的运行结果。分析图 5可以发现,SPCURC的聚类结果与原数据分布基本吻合,可以体现地震带的分布,能够发现不同密度的空间簇,尤其是位于低密度区域的点数据提取的线状簇反映了地震的带状分布特点。而DBSCAN算法更多地将低密度区域点数据归为孤立点,层次聚类算法割裂了聚类簇。因此,SPCURC算法在发现线状簇以及勾勒聚类簇边界方面更具有实用性,可以有效地发现空间分布上的特点,能够进一步为地震研究、交通规划等提供有价值的信息。

      图  5  地震算例的聚类结果示意图

      Figure 5.  Results of Clusters with Earthquake Data

    • 空间点聚类在分析空间分布以及空间数据挖掘方面起到重要的作用,广泛应用于地理信息系统、计算机科学等领域。本文提出了一种将滚圆法用于空间点聚类的研究算法——SPCURC算法,并且详细描述了该算法的原理及计算步骤,通过模拟算例与实际算例的对比实验及分析,发现SPCURC算法可以有效地发现线状簇,适应低密度和高密度分布的数据,输入参数较少,在聚类过程中可以给出聚类簇的边界,进一步提供聚类簇位置、形状等信息。在实际应用中,SPCURC算法也具有局限性,如算法参数需要人为地进行多次试验来获取最优值,且算法对数据分布特点具有依赖性。因此,本文的后续工作主要集中在参数的自适应方法以及算法的普遍实际适用性研究方面。

参考文献 (20)

目录

    /

    返回文章
    返回