留言板

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

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

矢量居民地多边形多级图划分聚类方法

金澄 安晓亚 陈占龙 马啸川

金澄, 安晓亚, 陈占龙, 马啸川. 矢量居民地多边形多级图划分聚类方法[J]. 武汉大学学报 ( 信息科学版), 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
引用本文: 金澄, 安晓亚, 陈占龙, 马啸川. 矢量居民地多边形多级图划分聚类方法[J]. 武汉大学学报 ( 信息科学版), 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
JIN Cheng, AN Xiaoya, CHEN Zhanlong, MA Xiaochuan. A Multi-level Graph Partition Clustering Method of Vector Residential Area Polygon[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
Citation: JIN Cheng, AN Xiaoya, CHEN Zhanlong, MA Xiaochuan. A Multi-level Graph Partition Clustering Method of Vector Residential Area Polygon[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358

矢量居民地多边形多级图划分聚类方法

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

国家自然科学基金 41871305

国家重点研发计划 2017YFC0602204

中央高校基本科研业务费 CUGQY1945

地质探测与评估教育部重点实验室主任基金和中央高校基本科研业务费 GLAB2019ZR02

详细信息
    作者简介:

    金澄,博士,高级工程师,主要从事地理信息服务研究。jinchengno1@163.com

    通讯作者: 安晓亚,博士,副研究员。xya2001@tom.com
  • 中图分类号: P208

A Multi-level Graph Partition Clustering Method of Vector Residential Area Polygon

Funds: 

The National Natural Science Foundation of China 41871305

the National Key Research and Development Program of China 2017YFC0602204

the Fundamental Research Funds for the Central Universities CUGQY1945

the Opening Fund of Key Laboratory of Geological Survey and Evaluation of Ministry of Education and the Fundamental Research Funds for the Central Universities GLAB2019ZR02

More Information
    Author Bio:

    JIN Cheng, PhD, senior engineer, specializes in the server of geo-information. E-mail: jinchengno1@163.com

    Corresponding author: AN Xiaoya, PhD, associate researcher. E-mail: xya2001@tom.com
  • 摘要: 针对复杂居民地多边形的信息挖掘问题,提出了一种多级图划分聚类分析方法,构造居民地多边形的图模型,并通过对图模型进行粗化匹配与重构、初始化分和细化得到聚类结果。首先构建研究区域内居民地建筑物的Delaunay三角网, 生成包含研究对象之间的邻接信息图;然后结合空间认知准则和人类认知的特点,采用形状狭长度、面积比、凹凸性、距离和连通性5个指标度量邻接图的相似性;最后应用多级图划分方法,得到聚类结果。采用中国上海地区的居民地建筑物矢量数据进行聚类分析实验,并对比了改进的k均值算法(k-Means++)、具有噪声鲁棒性的基于密度的空间聚类算法(density-based spatial clustering of applications with noise,DBSCAN)和最小生成树(minimum spanning tree, MST)聚类算法得到的轮廓系数以及视觉效果。实验结果表明,基于多级图划分的居民地多边形聚类分析的结果更加符合人类认知。
  • 图  1  多级图划分算法的主要阶段

    Figure  1.  Main Stages of Multi-level Graph-Partition Algorithm

    图  2  数据组织形式

    Figure  2.  Data Organization Form

    图  3  多边形之间的距离与连通性

    Figure  3.  Distance and Connectivity Between Polygons

    图  4  研究区域

    Figure  4.  Study Area

    图  5  Delaunay三角网邻接图

    Figure  5.  Adjacency Graph of Delaunay Trianglar Mesh

    图  6  本文聚类结果的平均轮廓系数和RMSE值

    Figure  6.  Average Silhouette Coefficients and Root Mean Square Errors of Our Proposed Clustering Method

    图  7  4种聚类方法的平均轮廓系数和RMSE值

    Figure  7.  Average Silhouette Coefficients and Root Mean Square Errors of Four Clustering Methods

    图  8  4种聚类算法完成聚类实验所消耗的时间

    Figure  8.  Consumed Time of Completing the Clustering Experiments Using Four Clustering Algorithms

    图  9  实验区1的聚类结果

    Figure  9.  Clustering Results of Experiment Area 1

    图  10  实验区2的聚类结果

    Figure  10.  Clustering Results of Experiment Area 2

    表  1  空间相似性度量指标

    Table  1.   Measurement Indicies of Spatial Similarity

    度量指标 定义 说明
    形状狭长度 $ \text{shp}\left( x, y \right)=\frac{\text{min}\left( \text{asp}\left( x \right), \text{asp}\left( y \right) \right)}{\text{max}\left( \text{asp}\left( x \right), \text{asp}\left( y \right) \right)} $ $ \text{asp}\left( x \right)=\frac{\text{max}\left( {{a}_{x}}, {{b}_{x}} \right)}{\text{min}\left( {{a}_{x}}, {{b}_{x}} \right)} $,其中axbx表示多边形x的最小外接矩形的长和宽;同理可得sap(y)。
    面积比 $ \text{size}\left( x, y \right)=\frac{\text{Area}\left( x \right)}{\text{Area}\left( y \right)} $ Area(x) < Area(y),Area ( )为多边形的面积。
    凹凸性 $ \text{cvx}\left( x, y \right)=\frac{\min \left( \text{cp}\left( x \right), \text{cp}\left( y \right) \right)}{\max \left( \text{cp}\left( x \right), \text{cp}\left( y \right) \right)} $ $ \text{cp}\left( x, y \right)=\frac{\text{Area}\left( x \right)}{\text{Peri}\left( x \right)} $,其中Area(x)、Peri(x)分别为多边形x的面积和周长;同理可得cp(y)。
    距离 $ \text{dist}\left( x, y \right)=\frac{n}{\sum\limits_{i=0}^{n}{l_{i}^{x, y}}} $ 图 3(a)所示,dist(x, y)表示多边形xy之间的距离。
    连通性 con(x, y)=L(Landscape(x, y)) 图 3(b)所示,con(x, y)表示多边形xy之间的连通性。
    下载: 导出CSV

    表  2  空间相似性数值(部分)

    Table  2.   Spatial Similarity Values (Part)

    邻接多边形组 相似性度量指标 空间相似值
    连接对象ID 连接对象ID 形状狭长度 面积比 凹凸性 距离 连通性
    15 17 0.808 8 0.275 3 0.588 4 0.105 2 0.128 4 0.368 0
    45 50 0.862 3 0.772 8 0.921 3 0.116 4 0.521 3 0.618 8
    274 276 0.919 5 0.748 6 0.860 6 0.156 6 0.272 8 0.570 2
    540 560 0.936 5 0.846 3 0.894 6 0.179 9 0.424 1 0.638 8
    815 823 0.760 4 0.842 5 0.890 9 0.189 2 0.189 7 0.544 1
    1325 1394 0.292 2 0.841 9 0.918 1 0.204 8 0.245 9 0.454 7
    1367 1368 0.814 1 0.771 2 0.991 0 0.106 7 0.375 7 0.579 9
    下载: 导出CSV

    表  3  各多边形的轮廓系数(部分)

    Table  3.   Silhouette Coefficient of Each Polygon (Part)

    对象ID 轮廓系数
    1 -0.120 8
    2 -0.102 2
    3 -0.078 3
    696 -0.113 2
    697 0.070 9
    698 0.086 2
    699 0.066 7
    1392 -0.395 9
    1393 -0.168 6
    1394 -0.196 0
    下载: 导出CSV

    表  4  多级图划分过程中的各阶段耗时/s

    Table  4.   Consumed Time During the Progress of Multi-level Graph Partition Algorithm /s

    划分阶段 体积不同的矢量建筑物多边形群组 平均耗时占比/%
    200 250 300 350 400 450 500 550 600
    构图 1.33 1.41 1.48 1.57 1.64 1.71 1.77 1.83 1.88 11
    粗化 7.86 8.33 8.74 9.28 9.69 10.11 10.46 10.82 11.11 65
    初始化分 0.97 1.02 1.08 1.14 1.19 1.24 1.29 1.33 1.37 8
    细化 1.93 2.05 2.15 2.28 2.38 2.49 2.57 2.65 2.75 16
    下载: 导出CSV

    表  5  实验区1局部聚类结果对比

    Table  5.   Comparison of Local Clustering Results in Experiment Area 1

    聚类算法 局部研究区域
    A B C D
    本文算法
    k-Means++算法
    MST算法
    DBSCAN算法
    下载: 导出CSV

    表  6  实验区2的局部聚类结果对比

    Table  6.   Comparison of Local Clustering Results in Experiment Area 2

    聚类算法 局部研究区域
    A B C D E
    本文算法
    k-Means++算法
    MST算法
    DBSCAN算法
    下载: 导出CSV
  • 朱杰, 孙毅中, 陈律余, 等.顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例[J].武汉大学学报·信息科学版, 2017, 42(12): 1 696-1 702 doi:  10.13203/j.whugis20150590

    [1] Zhu Jie, Sun Yizhong, Chen Lvyu, et al. A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes—Identifying City Commercial Center[J].Geomatics and Information Science of Wuhan University, 2017, 42(12):1 696-1 702 doi:  10.13203/j.whugis20150590
    [2] Estivillcastro V, Lee I. Multi-level Clustering and Its Visualization for Exploratory Spatial Analysis[M]. Norwell:Kluwer Academic Publishers, 2002
    [3] 焦利民, 刘耀林, 刘艳芳.区域城镇基准地价水平的空间自相关格局分析[J].武汉大学学报·信息科学版, 2009, 34(7):873-877 http://ch.whu.edu.cn/article/id/1299

    Jiao Limin, Liu Yaolin, Liu Yanfang. Spatial Autocorrelation Pattern of Datum Land Prices of Cities in a Region [J].Geomatics and Information Science of Wuhan University, 2009, 34(7):873-877 http://ch.whu.edu.cn/article/id/1299
    [4] Pei T, Jasra A, Hand D J, et al. DECODE: A New Method for Discovering Clusters of Different Densities in Spatial Data[J].Data Mining and Knowledge Discovery, 2009, 18(3):337-369 doi:  10.1007/s10618-008-0120-3
    [5] 贾奋励, 游雄, 刘芳.多尺度表达的地图设计模型[J].测绘科学技术学报, 2011, 28(2):153-156 doi:  10.3969/j.issn.1673-6338.2011.02.019

    Jia Fenli, You Xiong, Liu Fang.Map Design Model for Multi-scale Representation[J].Journal of Geomatics Science and Technology, 2011, 28(2):153-156 doi:  10.3969/j.issn.1673-6338.2011.02.019
    [6] Wang W, Du S, Guo Z, et al. Polygonal Clustering Analysis Using Multilevel Graph‐Partition[J].Transactions in GIS, 2015, 19(5):716-736 doi:  10.1111/tgis.12124
    [7] Guo D, Wang H. Automatic Region Building for Spatial Analysis[J].Transactions in GIS, 2011, 15(s1):29-45
    [8] Wang S, Eick C F. A Polygon-Based Clustering and Analysis Framework for Mining Spatial Datasets[M]. Norwell:Kluwer Academic Publishers, 2014
    [9] 余莉.克服双重约束的面目标位置聚类方法[J].测绘学报, 2016, 45(10):1 250-1 259 doi:  10.11947/j.AGCS.2016.20150491

    Yu Li. Position Clustering for Polygon Object Under Dual-constrains[J].Acta Geodaetica et Cartographica Sinica , 2016, 45(10): 1 250-1 259 doi:  10.11947/j.AGCS.2016.20150491
    [10] Chu S C, Roddick J F, Pan J S. Novel Multi-centroid, Multi-run Sampling Schemes for K-Mediods-Based Algorithms[M].Berlin, Heidelberg:Springer Berlin, 2004
    [11] 程绵绵, 孙群, 李少梅, 等.顾及密度对比的多层次聚类点群选取方法[J].武汉大学学报·信息科学版, 2019, 44(8): 1 131-1 137 doi:  10.13203/j.whugis20180043

    Cheng Mianmian, Sun Qun, Li Shaomei, et al.A Point Group Selecting Method Using Multi-level Clustering Considering Density Comparison[J].Geomatics and Information Science of Wuhan University , 2019, 44(8): 1 131-1137 doi:  10.13203/j.whugis20180043
    [12] 林恒, 龚威, 史硕, 等.利用等边长正交格网进行层次聚合聚类[J].武汉大学学报·信息科学版, 2018, 43(5): 786-791 doi:  10.13203/j.whugis20150668

    Lin Heng, Gong Wei, Shi Shuo, et al.Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid[J].Geomatics and Information Science of Wuhan University, 2018, 43(5): 786-791 doi:  10.13203/j.whugis20150668
    [13] Ester M, Kriegel H P, Xu X. Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications[J].Data Mining and Knowledge Discovery, 1998, 2(2):169-194 doi:  10.1023/A:1009745219419
    [14] 职露, 余旭初, 李光强, 等.滚圆法用于空间点聚类的研究[J].武汉大学学报·信息科学版, 2018, 43(8): 1 193-1 198 doi:  10.13203/j.whugis20160287

    Zhi Lu, Yu Xuchu, Li Guangqiang, et al. Spatial Point Clustering Analysis Based on the Rolling Circle[J].Geomatics and Information Science of Wuhan University, 2018, 43(8): 1 193-1 198 doi:  10.13203/j.whugis20160287
    [15] Gholamhosein S, Surojit C, Zhang A D. WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases[C]. The 24th International Conference on Very Large Data Bases (VLDB'98), San Francisco, CA, USA, 1998
    [16] 邓敏, 刘启亮, 李光强, 等.一种基于似最小生成树的空间聚类算法[J].武汉大学学报·信息科学版, 2010, 35(11): 1 360-1 364 http://ch.whu.edu.cn/article/id/1115

    Deng Min, Liu Qiliang, Li Guangqiang, et al. A Spatial Clustering Algorithm Based on Minimum Spanning Tree-like[J].Geomatics and Information Science of Wuhan University, 2010, 35(11): 1 360-1 364 http://ch.whu.edu.cn/article/id/1115
    [17] Caruso G, Hilal M, Thomas I. Measuring Urban Forms from Inter-building Distances: Combining MST Graphs with a Local Index of Spatial Association[J].Landscape and Urban Planning, 2017, 16(3):80-89 https://www.sciencedirect.com/science/article/abs/pii/S0169204617300518
    [18] Yan X. A Graph Convolutional Neural Network for Classification of Building Patterns Using Spatial Vector Data[J].ISPRS Journal of Photogrammetry and Remote Sensing, 2019, 150:259-273 doi:  10.1016/j.isprsjprs.2019.02.010
    [19] Karypis G, Kumar V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs[J].SIAM Journal on Scientific Computing, 1998, 20(1):359-370 doi:  10.1137/S1064827595287997
    [20] Kernighan B W, Lin S. An Efficient Heuristic Procedure for Partitioning Graphs[J].Bell System Technical Journal, 1970, 49(2):291-307 doi:  10.1002/j.1538-7305.1970.tb01770.x
    [21] Robnik-Šikonja M, Kononenko I. Theoretical and Empirical Analysis of ReliefF and RReliefF[J].Machine Learning, 2003, 53(1): 23-69
    [22] Chen Z, Ma X, Wu L, et al. An Intuitionistic Fuzzy Similarity Approach for Clustering Analysis of Polygons[J].ISPRS International Journal of Geo-Information, 2019, 8(2): 98-106 doi:  10.3390/ijgi8020098
    [23] 于剑, 程乾生.模糊聚类方法中的最佳聚类数的搜索范围[J].中国科学, 2002, 32(2):274-280 https://www.cnki.com.cn/Article/CJFDTOTAL-JEXK200202014.htm

    Yu Jian, Cheng Qiansheng. The Upper Bound of the Optimal Number of Clusters in Fuzzy Clustering[J].Science in China, 2002, 32(2):274-280 https://www.cnki.com.cn/Article/CJFDTOTAL-JEXK200202014.htm
    [24] Fisher J. Visualizing the Connection Among Convex Hull, Voronoi Diagram and Delaunay Triangulation[C]. Midwest Instruction and Computing Symposium, Lawrence, Canada, 2004
  • [1] 卢威, 艾廷华.  利用三角剖分骨架图提取简单多边形目标中心点 . 武汉大学学报 ( 信息科学版), 2020, 45(3): 337-343. doi: 10.13203/j.whugis20180236
    [2] 信睿, 艾廷华, 晏雄锋, 杨敏.  相似性度量支持下的隐喻地图轮廓设计 . 武汉大学学报 ( 信息科学版), 2019, 44(4): 625-632. doi: 10.13203/j.whugis20170153
    [3] 王伟玺, 杜靖, 李晓明, 胡翰, 许文波, 郭晗, 丁雨淋.  基于栅格填充的直角多边形建筑物轮廓规则化方法 . 武汉大学学报 ( 信息科学版), 2018, 43(2): 318-324. doi: 10.13203/j.whugis20160071
    [4] 陈占龙, 吴亮, 谢忠, 张丁文.  利用约束满足问题进行多洞面实体相似性度量 . 武汉大学学报 ( 信息科学版), 2018, 43(5): 745-751, 785. doi: 10.13203/j.whugis20160191
    [5] 陈占龙, 吕梦楼, 吴亮, 徐永洋.  基于特征矩阵和关联图的空间场景相似性度量方法 . 武汉大学学报 ( 信息科学版), 2017, 42(7): 956-962. doi: 10.13203/j.whugis20140450
    [6] 范仲鸣, 李精忠, 张小波.  矢量多边形模式识别的小波方法 . 武汉大学学报 ( 信息科学版), 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
    [7] 卞玉霞, 刘学军, 甄艳.  三维空间多边形的位置不确定性度量模型 . 武汉大学学报 ( 信息科学版), 2015, 40(1): 26-31.
    [8] 王新生, 谢凯, 姜友华, 郭光毅.  复杂多边形中轴构建方法! . 武汉大学学报 ( 信息科学版), 2014, 39(2): 181-185. doi: 10.13203/j.whugis20120715
    [9] 王晓妍, 郭庆胜, 翁杰, 龙毅.  零散多边形综合质量评价研究 . 武汉大学学报 ( 信息科学版), 2012, 37(9): 1112-1115.
    [10] 唐永鹤, 陶华敏, 卢焕章, 胡谋法.  一种基于Harris算子的快速图像匹配算法 . 武汉大学学报 ( 信息科学版), 2012, 37(4): 406-409.
    [11] 安晓亚, 孙群, 尉伯虎.  利用相似性度量的不同比例尺地图数据网状要素匹配算法 . 武汉大学学报 ( 信息科学版), 2012, 37(2): 224-228.
    [12] 谢明霞, 王家耀, 郭建忠, 陈科.  不等距划分的高维相似性度量方法研究 . 武汉大学学报 ( 信息科学版), 2012, 37(7): 780-783.
    [13] 帅赟, 艾廷华, 帅海燕, 倪琳.  基于形状模板匹配的多边形查询 . 武汉大学学报 ( 信息科学版), 2008, 33(12): 1267-1270.
    [14] 韩元利, 胡鹏, 夏文芳, 张立华.  点状实体k阶Voronoi多边形的存在性判定 . 武汉大学学报 ( 信息科学版), 2007, 32(9): 833-837.
    [15] 韩元利, 胡鹏, 黄雪莲, 张立华.  基于k阶Voronoi多边形划分的k阶数据场拟合 . 武汉大学学报 ( 信息科学版), 2007, 32(4): 353-357.
    [16] 杜培军, 唐宏, 方涛.  高光谱遥感光谱相似性度量算法与若干新方法研究 . 武汉大学学报 ( 信息科学版), 2006, 31(2): 112-115.
    [17] 胡鹏, 王海军, 邵春丽, 胡海.  论多边形中轴问题和算法 . 武汉大学学报 ( 信息科学版), 2005, 30(10): 853-857.
    [18] 杜维, 艾廷华, 徐峥.  一种组合优化的多边形化简方法 . 武汉大学学报 ( 信息科学版), 2004, 29(6): 548-550.
    [19] 毛建华, 王涛, 郭庆胜.  邻接凸多边形方向关系计算及其推理 . 武汉大学学报 ( 信息科学版), 2001, 26(4): 364-368.
    [20] 徐庆荣.  用栅格填充法建立多边形文件 . 武汉大学学报 ( 信息科学版), 1989, 14(4): 42-46.
  • 加载中
图(10) / 表(6)
计量
  • 文章访问数:  984
  • HTML全文浏览量:  311
  • PDF下载量:  115
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-12-18
  • 刊出日期:  2021-01-05

矢量居民地多边形多级图划分聚类方法

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

    国家自然科学基金 41871305

    国家重点研发计划 2017YFC0602204

    中央高校基本科研业务费 CUGQY1945

    地质探测与评估教育部重点实验室主任基金和中央高校基本科研业务费 GLAB2019ZR02

    作者简介:

    金澄,博士,高级工程师,主要从事地理信息服务研究。jinchengno1@163.com

    通讯作者: 安晓亚,博士,副研究员。xya2001@tom.com
  • 中图分类号: P208

摘要: 针对复杂居民地多边形的信息挖掘问题,提出了一种多级图划分聚类分析方法,构造居民地多边形的图模型,并通过对图模型进行粗化匹配与重构、初始化分和细化得到聚类结果。首先构建研究区域内居民地建筑物的Delaunay三角网, 生成包含研究对象之间的邻接信息图;然后结合空间认知准则和人类认知的特点,采用形状狭长度、面积比、凹凸性、距离和连通性5个指标度量邻接图的相似性;最后应用多级图划分方法,得到聚类结果。采用中国上海地区的居民地建筑物矢量数据进行聚类分析实验,并对比了改进的k均值算法(k-Means++)、具有噪声鲁棒性的基于密度的空间聚类算法(density-based spatial clustering of applications with noise,DBSCAN)和最小生成树(minimum spanning tree, MST)聚类算法得到的轮廓系数以及视觉效果。实验结果表明,基于多级图划分的居民地多边形聚类分析的结果更加符合人类认知。

English Abstract

金澄, 安晓亚, 陈占龙, 马啸川. 矢量居民地多边形多级图划分聚类方法[J]. 武汉大学学报 ( 信息科学版), 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
引用本文: 金澄, 安晓亚, 陈占龙, 马啸川. 矢量居民地多边形多级图划分聚类方法[J]. 武汉大学学报 ( 信息科学版), 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
JIN Cheng, AN Xiaoya, CHEN Zhanlong, MA Xiaochuan. A Multi-level Graph Partition Clustering Method of Vector Residential Area Polygon[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
Citation: JIN Cheng, AN Xiaoya, CHEN Zhanlong, MA Xiaochuan. A Multi-level Graph Partition Clustering Method of Vector Residential Area Polygon[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 19-29. doi: 10.13203/j.whugis20190358
  • 空间聚类分析是空间数据挖掘的一个主要研究方向,是无监督分类的过程,旨在将具有相关性的空间实体依据相似性度量准则划分成一系列由若干空间实体构成的、具有空间意义的簇,最终实现同一簇中实体尽可能相似、不同簇间的实体尽可能相异。空间聚类分析既能够发现隐含在海量数据中的聚类规则,又可与其他的空间数据挖掘方法结合,挖掘更深层次的知识,提高空间数据挖掘的效率和质量。目前空间聚类分析已经被广泛运用到城市规划[1]、犯罪等热点区域分析[2]、地价评估[3]、地震分析[4]网络地图的多尺度可视化[5]等领域,并发挥着越来越重要的作用。空间对象之间的空间相似性是聚类分析的基础[6],居民地多边形具有鲜明的几何特征、空间关系和语义属性,而现有的研究大多只考虑了多边形的一些直观可见的属性,早期更是直接将其简化成多维空间点。例如,文献[7]仅仅考虑了几何距离属性和非空间属性;文献[8]先将重合多边形简化为点数据,然后将多边形的相似性定义为目标k邻近区域所包含的共享点的数目;文献[9]提出了克服双重约束的面目标位置聚类方法,该方法虽然能够识别密度不均、任意形状分布以及“桥”链接的面目标集群,但仅使用欧氏距离来度量面目标间的距离/相似性,并不符合人类聚类矢量多边形的认知特点。在地图学中,空间认知是对周围地理事物的位置、形状、空间分布、相互关系及其动态变化认识过程的感知,人类认知则是对地理事物的本质的映像所形成的地理空间整体的、动态的、连续的认识。上述研究没有充分利用多边形的几何特征和空间关系,不能有效地表达多边形之间的相似性,也不符合空间认知准则和人类认知方式。

    按照划分方式,空间聚类算法可分为以下6类:基于划分的算法[10]、基于层次的算法[11-12]、基于密度的算法[13]、基于模型的算法[14]、基于格网的算法[15]以及基于图论的算法[16]。每种聚类方法的适用范围不尽相同,且对于同样的数据,不同的聚类方法得到的聚类结果也有所差异。如k均值算法(k-Means)、k质心聚法等基于划分的算法运行效率高,对大型数据具有较高的伸缩性,但不能发现任意形状的簇,需要先验知识,受初始点影响大。BIRCH(balanced iterative reducing and clustering using hierarchies)、CURE(clustering using representatives)以及Chameleon等基于层次的算法能够处理多尺度的空间聚类问题,但不能发现密度不均匀的簇,同样需要先验知识,且并未顾及专题属性。DBSCAN、GDBSCAN等基于密度的算法可以发现任意形状的空间簇,能够有效识别孤立点,但难以识别空间簇相互邻接情况下的聚类操作,也需要先验知识。在基于模型的算法里,最大期望(expectation-maximization,EM)算法运行速度快,复杂度近似直线;自组织映射(self-organizing maps,SOM)的结果有利于解释和可视化,但它们均不能发现任意形状的空间簇,同时仍需先验知识,对专题属性考虑不足。统计信息网格(statistical information grid,STING)、小波聚类等基于格网的算法可以发现任意形状的空间簇,运行速度较快,但无法识别邻近空间簇,难以适应分布不均匀的情况。最小生成树(minimum spanning tree,MST)等基于图论的算法可以发现任意形状的簇并识别邻近簇,但对格式塔理论依赖较大,没有比较明确的定量的树分割方案。在上述算法中,尽管基于图的算法存在一定缺陷,但可以同时保留聚类实体的结构特征和邻接信息[17-18]。本文基于居民地多边形的空间属性特征,结合空间认知准则和人类认知的特点,采用形状狭长度、面积比、凹凸性、距离和连通性为相似性指标,构造包含居民地多边形之间的相似性的图模型,并应用图的多级划分[19]改进算法来实现居民地多边形的聚类分析。

    • 根据图的多级划分思想[19],可将居民地多边形聚类划分为粗化、初始化分和细化3个阶段,整体方法描述如图 1所示。其中,G0→G3表示先将原始图(G0)进行粗化(G1,G2),然后再进行初始划分(G3);G3→G0则是整个细化阶段。

      图  1  多级图划分算法的主要阶段

      Figure 1.  Main Stages of Multi-level Graph-Partition Algorithm

    • 本文利用图模型对居民地多边形进行表达,给定图Gt=(Vt, Et),其中$ {V^t} = \left\{ {v_i^t} \right\}_{i = 1}^n $,存储第t划分子图中的所有顶点v的信息,E则存储着邻接点之间的边的信息,即多边形之间的邻接信息。

      图 2所示的图模型的组织形式中共有7个实体目标,它们之间的连线代表相互间的邻接关系,线段上的数字为二者的相似度。组织与存储形式(图 2(c))如下:第一行表示与目标1有邻接关系的目标,奇数位为与之邻接的目标的标号,偶数位为二者之间的相似性值;第二行表示与目标2有邻接关系的目标,数据意义与第一行类似,依次类推。

      图  2  数据组织形式

      Figure 2.  Data Organization Form

    • §1.1中原图的子图生成过程主要包括图的粗化匹配和重构两部分。在图的随机粗化匹配过程中,权重节点匹配方案为重边匹配方案。为达到粗化图的目的,采用最大化匹配准则,即当图形中的任意一条边都没有被匹配时,至少有一个终点被匹配。在这一过程中,记Map[v]为被匹配并存储到粗化图Gi+1中的顶点v,一般称其为多节点;Match[v]为未被匹配的顶点。由于采用的匹配方案为重边匹配,并且在匹配过程中设立阈值,从而导致部分节点无匹配节点,因此每步粗化对图面积比降低的比率小于1/2。在重构阶段,图Gi按照一定的准则通过匹配过程得到Map[v]和Match[v],生成粗化图Gi+1。进行重构的准则是多节点v的边的权值为Viv的权值的总和,这是为了使边与边之间的权值达到最大,得到的粗化图能够保持原图的特性。

      设顶点v1v2为两个被匹配的顶点,则重构顶点u1=Map[v1],那么与u1邻接的顶点可表示如下:

      $$ A\left( {{u_1}} \right) = \left( {\left\{ {{\rm{Map}}\left[ x \right]|x \in A\left( {{v_1}} \right)} \right\}\mathop \cup \nolimits \left\{ {{\rm{Map}}\left[ x \right]|x \in A\left( {{v_2}} \right)} \right\}} \right) - \left\{ {{u_1}} \right\} $$ (1)

      边(u1, u2)之间的权值为:

      $$ \begin{array}{*{20}{l}} {w\left( {{u_1}, {u_2}} \right) = \sum\nolimits_x {\left\{ {w\left( {{u_1}, x} \right)\left| {{\rm{Map}}\left[ x \right] = {u_2}} \right.} \right\}} + }\\ {\;\;\;\;\;\;\;\;\;\;\;\sum\nolimits_x {\left\{ {w\left( {{u_2}, x} \right)\left| {{\rm{Map}}\left[ x \right] = {u_2}} \right.} \right\}} } \end{array} $$ (2)

      当节点间的权重大于匹配阈值时,则停止粗化。

    • 本文根据Kernighan-Lin[20]算法思想实现最粗糙和最小图形的划分。假设PG=(V, E)原始划分的顶点,定义gv为代价函数,表示将点v从当前聚类簇中移动到其他簇时边界权值的减少值,计算如下:

      $$ \begin{array}{*{20}{c}} {{g_v} = \mathop \sum \limits_{\left( {v, u} \right) \in E且 P\left[ v \right] \ne P\left[ u \right]} w\left( {v, u} \right) - }\\ {\mathop \sum \limits_{\left( {v, u} \right) \in E且 P\left[ v \right] = P\left[ u \right]} w\left( {v, u} \right)} \end{array} $$ (3)

      式中,w(v, u)是指边(v, u)的权重值,若一个顶点v从一个划分中被移动到另一个划分,那么与顶点v相邻接的顶点的g值也会相应地发生变化,因此,在每移动一个顶点之后,都需要重新计算并更新与之相邻接的顶点的g值。

    • 通过遍历图形$ {G_{m - 1}}、{G_{m - 2}} \cdots {G_1} $,粗化图形Gm的划分Pm被映射到原始图。Gi+1中的每个顶点都包含有Gi中的顶点的不同的子集,因此将vGi+1的点集Viv分配到划分Pi+1[v]中,可实现由Pi+1得到Pi,例如,$ {P_i}\left[ u \right] = {P_{i + 1}}\left[ u \right], \forall u \in V_i^v $。

      虽然Pi+1是划分Gi+1的局部最小划分,但映射的划分Pi却不一定Gi的局部最小划分。由于Gi信息更加全面,所以其有更多的自由度可以用来改善Pi,降低边界权值,进而通过局部细化来提高Gi-1的划分。因此,在初始划分阶段之后,仍然需细化算法对结果进行完善。

      在细化阶段,通过控制顶点的g值进行计算g值则是通过每一个顶点的两个指标PD来表示,具体计算如下:

      $$ \left\{ {\begin{array}{*{20}{l}} {{g_v} = D\left[ v \right] - P\left[ v \right]}\\ {P\left[ v \right] = \mathop \sum \limits_{\left( {v, u} \right) \in E且 P\left[ v \right] = P\left[ u \right]} w\left( {v, u} \right)}\\ {D\left[ v \right] = \mathop \sum \limits_{\left( {v, u} \right) \in E且 P\left[ v \right] \ne P\left[ u \right]} w\left( {v, u} \right)} \end{array}} \right. $$ (4)

      式中,P[v]是指与顶点v在同一簇内且与v邻接的点连线的边的权值之和,是用来度量聚类簇内部紧密度的一项指标;D[v]是指与顶点v不在同一簇内且与v相邻接的点之间的边的权值之和,是用来度量聚类簇分离度的一项指标。

    • 本文采用形状狭长度、面积比、凹凸性、距离以及连通性5个空间相似性指标,结合多边形之间的邻接信息,对居民地多边形之间的相似性进行度量,相关指标的定义如表 1所示。图 3(a)3(b)分别表示居民地多边形之间的距离和连通性,其中$ l_i^{x, y} $指连接多边形xy的所有Delaunay三角形的边的长度之和;Landscape(x, y)是指连接多边形xy所有Delaunay三角形的边的中点连成的线,L(Landscape(x, y))为该线的长度。

      表 1  空间相似性度量指标

      Table 1.  Measurement Indicies of Spatial Similarity

      度量指标 定义 说明
      形状狭长度 $ \text{shp}\left( x, y \right)=\frac{\text{min}\left( \text{asp}\left( x \right), \text{asp}\left( y \right) \right)}{\text{max}\left( \text{asp}\left( x \right), \text{asp}\left( y \right) \right)} $ $ \text{asp}\left( x \right)=\frac{\text{max}\left( {{a}_{x}}, {{b}_{x}} \right)}{\text{min}\left( {{a}_{x}}, {{b}_{x}} \right)} $,其中axbx表示多边形x的最小外接矩形的长和宽;同理可得sap(y)。
      面积比 $ \text{size}\left( x, y \right)=\frac{\text{Area}\left( x \right)}{\text{Area}\left( y \right)} $ Area(x) < Area(y),Area ( )为多边形的面积。
      凹凸性 $ \text{cvx}\left( x, y \right)=\frac{\min \left( \text{cp}\left( x \right), \text{cp}\left( y \right) \right)}{\max \left( \text{cp}\left( x \right), \text{cp}\left( y \right) \right)} $ $ \text{cp}\left( x, y \right)=\frac{\text{Area}\left( x \right)}{\text{Peri}\left( x \right)} $,其中Area(x)、Peri(x)分别为多边形x的面积和周长;同理可得cp(y)。
      距离 $ \text{dist}\left( x, y \right)=\frac{n}{\sum\limits_{i=0}^{n}{l_{i}^{x, y}}} $ 图 3(a)所示,dist(x, y)表示多边形xy之间的距离。
      连通性 con(x, y)=L(Landscape(x, y)) 图 3(b)所示,con(x, y)表示多边形xy之间的连通性。

      图  3  多边形之间的距离与连通性

      Figure 3.  Distance and Connectivity Between Polygons

      居民地多边形的空间相似性是通过表 1中的5个指标来进行度量的,但它们的尺度不同,不能直接使用,故需先将数据进行标准化处理。本文采用最大最小化归一化准则,即:

      $$ x' = \frac{{x - {\rm{min}}\left( x \right)}}{{{\rm{max}}\left( x \right) - {\rm{min}}\left( x \right)}} $$ (5)

      式中,x为计算的相似性指标值;min(x)和max(x)分别为指标x所有值中的最小值和最大值;x′为经过标准化处理之后的值,此时所有的值落到[0, 1]的区间内,然后结合各个指标的权重,可以得到两多边形之间的空间相似性,计算如下:

      $$ \begin{matrix} S\left( x, y \right)={{\mu }_{1}}A\left( x, y \right)+{{\mu }_{2}}B\left( x, y \right)+{{\mu }_{3}}C\left( x, y \right)+ \\ {{\mu }_{4}}D\left( x, y \right)+{{\mu }_{5}}E\left( x, y \right) \\ \end{matrix} $$ (6)
      $$ {{\mu }_{1}}+{{\mu }_{2}}+{{\mu }_{3}}+{{\mu }_{4}}+{{\mu }_{5}}=1 $$ (7)

      式中,$ A\left( x, y \right)、B\left( x, y \right)、C\left( x, y \right)、D\left( x, y \right)、E\left( x, y \right) $分别为形状狭长度、面积比、凹凸性、距离和连通性经过标准化处理后的数据,且$ A\left( x, y \right)\ge 0, B\left( x, y \right)、C\left( x, y \right)、D\left( x, y \right)、E\left( x, y \right)\le 1 $; $ {{\mu }_{1}}、{{\mu }_{2}}、{{\mu }_{3}}、{{\mu }_{4}}、{{\mu }_{5}} $则分别为5个指标的权;S(x, y)为多边形xy之间的空间相似性。

    • 本文使用特征选择经典算法(ReliefF算法[21])确定权重。ReliefF算法的基本思想是通过选取多组训练样本迭代更新特征权值,特征权重越大,表示该特征分类能力越强;反之,则分类能力越弱。在迭代更新权值结束后,选择最优特征子集。

      记单标签训练数据集有K个类别,训练集记为$ D=\left\{ \left( {{x}_{1}}, {{y}_{1}} \right), \left( {{x}_{2}}, {{y}_{2}} \right)\cdots \left( {{x}_{n}}, {{y}_{n}} \right) \right\} $,其中xiRp为数据的特征空间,yiRk为数据的类空间。若第i个样本xi属于第k类,记为yi(k)=1,否则记为yi(k)=0。每一个样本只属于一种类别,则对于某样本Ri,有$ \sum\limits_{j=1}^{q}{y\left( {{x}_{i}} \right)}=1 $。

    • 对于空间聚类来说,理想的聚类结果应当满足以下两个方面的要求:(1)凝聚度,即空间簇内部的实体应尽可能相似;(2)分离度,即不同的空间簇中的实体差异性尽可能大,这也是选取空间聚类结果评估指标所遵循的两个基本原则。轮廓系数[22]是一种度量聚类结果好坏的相对评价指标,它同时结合了凝聚度和分离度两种因素,定义如下:

      $$ {{S}_{i}}=\frac{{{b}_{i}}-{{a}_{i}}}{\text{max }\!\!~\!\!\text{ }\left\{ {{a}_{i}}, {{b}_{i}} \right\}} $$ (8)

      式中,ai表示第i个对象到簇中其他所有对象的平均距离,体现空间簇内部对象之间的凝聚度;bi表示第i个对象到给定簇中其他所有对象的平均距离,体现空间簇之间的分离度。由定义可知,轮廓系数Si∈[-1, 1],Si为负时,即bi < ai,表示该对象与所在簇对象之间的凝聚度小于与其他簇对象之间的分离度,此时应当对该对象所属空间簇做出调整;Si为正时,即bi>ai,表示该对象与所在簇对象之间的凝聚度大于与其他簇对象之间的分离度,结果较为良好。

    • 目前普遍使用的规则是$ 2\le {{c}_{\max }}\le \sqrt{n} $,其中,cmax为最大聚类数目;n为数据集的样本数,该方法已经得到一定的验证和分析[23]。本文基于这一规则,对比不同簇数目时所提出的方法与传统方法的聚类表现来进一步评估聚类结果。

    • 本文采用轮廓系数的均方根误差(root mean square error,RMSE)作为度量聚类结果的评价指标,定义如下:

      $$ \left\{ \begin{array}{*{35}{l}} \text{RMS}{{\text{E}}_{k}}=\sqrt{\text{MS}{{\text{E}}_{k}}} \\ \text{MS}{{\text{E}}_{k}}=\frac{1}{n}{{\left( {{S}_{i}}-\text{mea}{{\text{n}}_{{{a}_{k}}}} \right)}^{2}}\text{ }\!\!~\!\!\text{ } \\ \text{mea}{{\text{n}}_{{{a}_{k}}}}=\frac{1}{n}\underset{i=1}{\overset{n}{\mathop \sum }}\, \left( 1-{{S}_{i}} \right) \\ \end{array} \right. $$ (9)

      式中,meanak为分类k簇中所有样本的轮廓系数的均值;i为分类k簇中第i个样本;n为数据集中的样本数;MSEk为分类k簇中的均方误差(mean square error,MSE)。RMSE越小,则聚类结果越好。另外,本文使用平均轮廓系数对聚类结果进行进一步验证,其定义如下:

      $$ C=\text{mea}{{\text{n}}_{{{a}_{k}}}} $$ (10)

      同样地,C值越小,聚类效果越好。

    • 本文以上海市1:1.5万城区居民地地图为例,选取两个局部区域进行实验。实验区1、2分别包括1 387、6 901个建筑物,如图 4所示。实验区域以小区居民楼为主,辅以学校、银行及购物广场等生活基础设施,建筑物样式较为丰富。本文主要通过实验区1进行数据分析,通过实验区2计算运行速度,并最终展示两个实验区域使用4种方法的聚类结果及特定区域的细节信息。

      图  4  研究区域

      Figure 4.  Study Area

    • 首先利用本文方法构建实验区域内邻接居民地多边形的图模型,这一过程通过构造Delaunay[24]三角网实现,选取居民地多边形的质心来代表居民地多边形,进而生成图模型,结果见图 5

      图  5  Delaunay三角网邻接图

      Figure 5.  Adjacency Graph of Delaunay Trianglar Mesh

      然后根据表 1中的5个空间相似性度量指标计算各邻接多边形之间的相似性数值,得到邻接居民地建筑物的空间相似性数值,部分计算结果如表 2所示。

      表 2  空间相似性数值(部分)

      Table 2.  Spatial Similarity Values (Part)

      邻接多边形组 相似性度量指标 空间相似值
      连接对象ID 连接对象ID 形状狭长度 面积比 凹凸性 距离 连通性
      15 17 0.808 8 0.275 3 0.588 4 0.105 2 0.128 4 0.368 0
      45 50 0.862 3 0.772 8 0.921 3 0.116 4 0.521 3 0.618 8
      274 276 0.919 5 0.748 6 0.860 6 0.156 6 0.272 8 0.570 2
      540 560 0.936 5 0.846 3 0.894 6 0.179 9 0.424 1 0.638 8
      815 823 0.760 4 0.842 5 0.890 9 0.189 2 0.189 7 0.544 1
      1325 1394 0.292 2 0.841 9 0.918 1 0.204 8 0.245 9 0.454 7
      1367 1368 0.814 1 0.771 2 0.991 0 0.106 7 0.375 7 0.579 9

      最后将得到的空间相似性数值按照§1.1所述方式进行组织和存储,同时根据ReliefF算法确定各指标权重,形状狭长度、面积比、凹凸性、距离以及连通性的权重分别为:μ1=0.176 0,μ2=0.298 2,μ3=0.143 9,μ4=0.268 3,μ5=0.083 5,利用多级图划分算法得到空间聚类结果,计算各个多边形的轮廓系数,部分结果如表 3所示。

      表 3  各多边形的轮廓系数(部分)

      Table 3.  Silhouette Coefficient of Each Polygon (Part)

      对象ID 轮廓系数
      1 -0.120 8
      2 -0.102 2
      3 -0.078 3
      696 -0.113 2
      697 0.070 9
      698 0.086 2
      699 0.066 7
      1392 -0.395 9
      1393 -0.168 6
      1394 -0.196 0

      实验区1共含有1 387个实验对象,依据§3中的方法,聚类数目应当落入[2, 37]区间内,计算得到不同簇数目下各聚类结果的平均轮廓系数和RMSE值,结果分别如图 6(a)6(b)所示。另外,本文还分别计算了使用DBSCAN、k-Means++和MST算法得到的平均轮廓系数和RMSE值作为对比,结果如图 7所示。

      图  6  本文聚类结果的平均轮廓系数和RMSE值

      Figure 6.  Average Silhouette Coefficients and Root Mean Square Errors of Our Proposed Clustering Method

      图  7  4种聚类方法的平均轮廓系数和RMSE值

      Figure 7.  Average Silhouette Coefficients and Root Mean Square Errors of Four Clustering Methods

      图 6可以发现,多级图划分方法整体上聚类效果的平均轮廓系数和RMSE值比较平滑,在划分的聚类簇数目增加时表现略有提升,能适应更大范围的划分。

      图 7可以发现,k-Means++算法的RMSE和RMSE整体上起伏变化较大,稳定性差,受聚类簇数目影响较大,这表明k-Means++算法不能对居民地多边形做出稳定、高质量的聚类划分;DBSCAN聚类算法随着聚类粗数目的改变变化较大,表明DBSCAN算法聚类结果不稳定,容易受划分簇数目的影响。虽然DBSCAN算法在评价指标上略优于k-Means++算法,但其依然不适合做居民地多边形聚类划分。MST聚类算法随着聚类簇数目的增加,其平均轮廓系数和RMSE值则成梯度增加,反映了MST聚类算法比较依赖格式塔理论,修剪难度大,容易受到异常数据影响,其划分结果更多的是实现局部最优,而不是整体最优;而本文采用的多级图聚类方法在一定程度上克服了其他3种方法的缺陷,聚类结果的质量和稳定性均优于对比实验方法。

      表 4统计了200~600之间9个体积不同的矢量建筑物多边形群组应用多级图划分算法进行聚类的各个阶段所消耗的时间。实验环境为Win10系统下MATLAB 2018b,CPU型号为酷睿i5,频率为2.2 GHz。由表 4可以看出,本文所提出的多级图聚类方法的主要时间消耗是在粗化阶段,其耗时约是构造图模型的6倍,属于可接受范围。且粗化匹配后的图体积较小,使得后续的划分阶段所占用时间比重比构图阶段还要小。细化阶段需要进行局部调整,因此耗时相对多一些。

      表 4  多级图划分过程中的各阶段耗时/s

      Table 4.  Consumed Time During the Progress of Multi-level Graph Partition Algorithm /s

      划分阶段 体积不同的矢量建筑物多边形群组 平均耗时占比/%
      200 250 300 350 400 450 500 550 600
      构图 1.33 1.41 1.48 1.57 1.64 1.71 1.77 1.83 1.88 11
      粗化 7.86 8.33 8.74 9.28 9.69 10.11 10.46 10.82 11.11 65
      初始化分 0.97 1.02 1.08 1.14 1.19 1.24 1.29 1.33 1.37 8
      细化 1.93 2.05 2.15 2.28 2.38 2.49 2.57 2.65 2.75 16

      图 8是使用4种聚类算法对实验区2进行聚CPU型号为酷睿i5,频率为2.2 GHz,运行时间由计算相似性环节和聚类两个部分组成。由图 8可以看出,4种聚类算法运行20次聚类实验的运行时间均在40 s以上,原因在于建筑物多边形相似性计算开销占比大。另外,本文的多级图聚类方法的中粗化、初始划分和细化3个阶段相辅相成,因此最终完成聚类的时间小于另外3种聚类算法的。

      图  8  4种聚类算法完成聚类实验所消耗的时间

      Figure 8.  Consumed Time of Completing the Clustering Experiments Using Four Clustering Algorithms

      为了进一步比较不同聚类算法的实验结果,选取9个区域对各聚类算法得到的结果进行对比分析。图 9为实验区1使用4种聚类算法得到的聚类结果,其中图 9(a)所示的红色方框区域ABCD的局部对比细节如表 5所示。由图 9表 5可知,k-Means++算法得到的结果识别出了居民地建筑物的形状和空间关联关系的差异,聚类划分结果比较符合人类认知;DBSCAN聚类算法中的划分结果不合理,与视觉认知存在明显差异,其原因是DBSCAN算法不能很好地反映高维数据特征,即使改进距离函数也不能发挥出多个指标的优势;MST算法的聚类结果图未识别出区域差异,这是由于MST缺乏合理的“剪枝理论”导致的;而本文方法则可以充分顾及居民地多边形的空间邻接关系、距离及居民地建筑几何特征信息量,避免出现DBSCAN和MST算法中存在的问题,从而划分出比较符合认知的结果。

      图  9  实验区1的聚类结果

      Figure 9.  Clustering Results of Experiment Area 1

      表 5  实验区1局部聚类结果对比

      Table 5.  Comparison of Local Clustering Results in Experiment Area 1

      聚类算法 局部研究区域
      A B C D
      本文算法
      k-Means++算法
      MST算法
      DBSCAN算法

      此外,图 10为实验区2使用4种聚类算法得到的聚类结果,其中图 10(a)所示的红色方框区域ABCDE的局部对比细节如表 6所示。由表 6中的E区域聚类结果可知,k-Means++算法的聚类结果体现了划分聚类算法对聚类中心的过度依赖;DBSCAN算法的聚类结果体现了密度聚类算法无法克服在聚类目标间密度不均匀、距离/相似性相差很大时聚类效果差的问题;MST聚类算法难以解决“剪枝”时对格式塔理论过度依赖的问题。而本文提出的多级图聚类方法在划分时的粗化阶段能提前将聚类目标划分成不同的簇,在细化阶段对聚类划分结果进一步优化,因而最终聚类结果能够反映聚类目标物之间的空间关联关系和形态学属性,从而得到更加符合人类认知的聚类结果。

      图  10  实验区2的聚类结果

      Figure 10.  Clustering Results of Experiment Area 2

      表 6  实验区2的局部聚类结果对比

      Table 6.  Comparison of Local Clustering Results in Experiment Area 2

      聚类算法 局部研究区域
      A B C D E
      本文算法
      k-Means++算法
      MST算法
      DBSCAN算法
    • 本文以居民地多边形为研究对象,顾及到居民地多边形的空间邻接信息,多方面考虑了居民地多边形的属性特征,采用了形状狭长度、面积比、凹凸性、距离和连通性5个相似性度量指标,对研究对象之间的空间相似性进行度量,使用多级图划分方法经过组织、粗化匹配与重构、初始划分和细化4个阶段,对研究对象进行处理,得到聚类结果,并使用轮廓系数聚类结果评价模型对聚类结果进行分析评价。本文提出的多级图方法中的粗化、初始化分以及细化3个阶段相辅相成,既保证了聚类算法的运行效率,又可以实现更好的划分结果,即相对符合人类视觉认知的簇,有利于对居民地多边形进行进一步的模式识别分析。对比实验结果表明,本文方法能够较好地实现对居民地多边形的空间聚类分析,符合人类认知。

参考文献 (24)

目录

    /

    返回文章
    返回