-
摘要: 针对线要素综合质量评价中的形状相似性评价问题，提出一种基于双侧弯曲森林形状表示模型的线要素形状相似性评价方法。引入约束Delaunay三角网及其凸包，生成线要素的双侧根弯曲序列，并在每个根弯曲上生成弯曲树，使用三角形表达每个层次上的弯曲，从而建立基于双侧弯曲森林的线要素形状表示模型。在该模型基础上，顾及线要素的地理位置特征，对综合前后线要素的形状相似性进行评价。实验结果表明，该方法能够区别不同层次上的形状特征，与形状认知的层次一致，能够有效辨识综合质量是否存在问题。Abstract: Focusing on the shape similarity aspect in linear feature generalization's quality assessment problem, this paper presents a novel shape similarity assessment method for linear feature generalization. By introducing the constrained Delaunay triangulation and convex hull, the two-side root-bend series are generated. After that, the bend trees are constructed on every root-bend to form the two-side bend forest shape representation model, in which every bend on every level is represented by a triangle. Based on this model, together with the geo-location of the linear feature, the shape similarity between the linear feature before and after generalization is assessed. Experimental results show that, this method can distinguish shape features of different levels effectively, thus achieving the same result as subject shape cognition, and can identify quality problems caused by linear feature generalization.
-
Keywords:
- linear feature /
- generalization /
- quality /
- bend /
- shape similarity
-
聚类是数据挖掘的基础技术，有广泛的应用前景[1-2]。聚类算法主要分为层次聚类法、网格聚类法、分割聚类法和密度聚类法[3]。其中，分割聚类法简单、快速，广泛应用于各个领域，典型的分割聚类法是K-means算法和K-medoids算法。在实际应用中，这两种算法由于需要用户输入聚类个数，聚类结果与初始点选择有关等缺点，不能很好地满足用户的需要[4]。《Science》中提出的峰值密度聚类算法虽然解决了上述问题，但存在阈值需要人为输入的问题[5]。
本文根据数据场，提出了数据质量聚类中心的概念。数据场将物质粒子间的相互作用及场描述方法引入到抽象的数域空间，实现数据对象或者样本点间相互作用的形式化描述[6]和计算。数据场将数据所具有的固有属性定义为数据的质量，并根据实际挖掘视角的不同，表示数据不同的属性。本文中，数据质量将代表数据的密集程度，并以此确定聚类中心，该方法无需用户输入聚类个数，也无需选择初始点，更无需人为设定阈值。
1 数据质量聚类
在物理场中，物体的质量是不能改变的，是物体固有的属性。同理，在数据场中，数据的质量也代表了每个数据自身的固有属性。所不同的是，在数据场中，数据并不是实际存在的物体，可以这样认为，n维数据集构成了一个n维的数据空间，数据集中每一个数据就是存在于这个n维空间中的“物体”，其各种属性都遵从于这个n维空间自身的特点。
定义：设数据集α含有N个数据点，α ={x1, x2…xn}，其中xi={xi1, xi2…xip}，组成一个P维空间Ω，在空间Ω中的数据点xi所固有的属性τ，称之为点xi在数据集α中的数据质量。
需要注意的是，定义中数据质量代表的是数据在数据集中的固有属性，这个固有属性会随着数据挖掘视角的不同而改变。一个数据点在数据集中可能会具有多种不同的固有属性，应当根据当前的挖掘任务赋予数据相应的属性。因此，数据场中数据质量具有集群性，即只在数据集中具有质量；空间唯一性，即相关的属性只在对应的数据集中存在；可变性，即根据需求不同代表的数据属性也不同。
聚类算法的目的是让类内相似度最高，类间相似度最低。反映在数据集的空间分布上，就是相似度高的数据分布在同一个类簇中，不同的类簇代表了不同的类别。因此，在聚类分析中，一般取数据密集程度这一属性作为数据的质量。此时，数据场中的数据质量本质上是反映数据集中数据的密集程度，处于密集区域的数据具有较大的数据质量，处于稀疏区域的数据具有较小的数据质量。
图 1所示的红色点标出的是数据集中质量较大的点，与所描述的数据质量概念一致，这些点都处于数据集中的密集区域。在聚类分析中，处于密集区域的点都有可能成为聚类中心。图 1中所示的数据集含有5 000个点，而质量较大的点约有1 000个，显然，只根据数据的质量不能确定数据集的聚类中心。
类比于物理场中的引力，聚类中心应当具有较大的质量，能够吸引其他质量较小的点在其周围形成一个类簇。同时，各个聚类中心应当相距较远，从而使聚类中心之间的作用力很小，直至可以忽略，这样，类簇与类簇间的相互关系就很弱，而类簇内的相互关系就很强，满足了最基本的聚类思想。
因此，数据质量聚类算法使用数据质量和数据之间的距离两个属性共同确定一个聚类中心。其中，数据之间的距离属性定义为：在数据集{x1, x2…xn}中，所有比xi质量大的点到xi距离的最小值；如果点xi是数据集中质量最大的点，那么其距离属性就为数据集中其他点xj(j≠i)到xi距离的最大值。
数据距离属性的计算式为：
$$ {{\delta }_{i}}=\left\{ \begin{align} &\underset{j:{{m}_{j}}>{{m}_{i}}}{\mathop{\min }}\, ({{d}_{ij}}), \ \ \exists \ {{m}_{i}}<{{m}_{j}} \\ &\underset{j=1, 2, \cdots , n}{\mathop{\max }}\, ({{d}_{ij}}), \ \ \nexists \ {{m}_{i}}<{{m}_{j}} \\ \end{align} \right. $$ (1) 式中，m表示数据的质量，dij表示两点间的距离。当数据集x1, x2…xn中存在比xi数据质量大的点xj，即mi＜mj时，数据之间的距离为所有比xi质量大的点到xi距离的最小值；如果不存在比xi数据质量大的点xj，即xi是数据集中质量最大的点，那么其距离属性就为数据集中其他点xj(j≠i)到xi距离的最大值。所以点xi的mi和δi都较大时，可以确定是聚类中心。在实际操作中，为了便于准确找到数据集中同时具有较大数据质量和较大距离属性的点，用数据集中每个数据点的质量属性作为横坐标、距离属性作为纵坐标绘制的决策图来确定聚类中心。在决策图中，同时具有较大横坐标和纵坐标数值的点会脱离其他只具有1个较大属性的点或者不具有较大属性的点，从而可以将这些脱离出来的点作为聚类中心。
图 2所示为数据集的决策图，可以发现，只有少数几个点的两个属性都较大，这些点用红色标出，作为备选聚类中心。
2 数据质量聚类算法实验验证
2.1 实验数据
数据质量聚类算法的核心是确定聚类中心，涉及数据的质量和距离两个属性。其中，距离属性计算使用欧氏距离，质量的计算采用参考文献[7]中的方法。在确定聚类中心后，先进行数据类别的划分，即将剩余点划入与其最近的聚类中心，形成一个个类簇，然后根据用户需要输出聚类结果。算法流程如图 3所示。
通过一系列的对比实验验证数据质量聚类算法的聚类效果，并与传统的K-means算法、K-medoids算法和文献[1]中的峰值密度聚类算法进行了对比。
在对比实验中，采用7个数据集进行实验。数据集A1、A2、A3分别含有3 000个点和20个类簇、5 250个点和35个类簇、7 500个点和50个类簇，并且3个数据集中类簇内点的个数均为150个。数据集S1、S2、S3、S4都含有5 000个点和15个类簇，但是每个数据集中类簇的扩展程度不一样，而且4个数据集中每个类簇的中心是已知的[8]。这7个数据集的二维可视图如图 4和图 5所示，图 4和图 5中的横、纵坐标分别为数据集二维可视图的X轴和Y轴。
2.2 对比实验
首先对数据集A1, A2, A3分别使用数据质量聚类算法和K-means算法、K-medoids算法和峰值密度聚类算法进行聚类。将得到的聚类结果进行二维可视化展示，同时，对每个数据集中聚类结果进行统计，记录每种算法在每个类簇中聚集的点个数，与数据集实际每个类簇中应有点的个数进行对比，计算出准确率。
因K-means算法和K-medoids算法需要输入聚类个数，故按照数据集实际情况输入。数据质量聚类算法使用决策图确定聚类中心，如图 6所示为数据集A1、A2和A3通过决策图选出的聚类中心。图 6中彩色点为聚类中心，即横坐标和纵坐标都较大的点。所选出的聚类中心个数在数据集A1中为20，在A2中为35，在A3中为50，这与数据集原有的类簇个数相同。
图 7是4种聚类算法的结果图，从图 7中可以发现，数据质量聚类算法和峰值密度聚类算法都有较好的聚类效果。对于聚类算法的准确率统计每一个数据集中4种算法对每一个类簇聚类的准确率，即类簇内点的个数和实际每个类内点的个数比值。统计结果如表 1所示。
![]()
图 7 数据集A1、A2、A3聚类结果比较Figure 7. Comparison of Clustering Results on Datasets A1, A2, A3表 1 数据集A1、A2、A3实验平均准确率统计表/%Table 1. Clustering Accuracies of Datasets A1, A2, A3/%数据集 K-means
算法K-medoids
算法峰值密度
聚类数据质量
聚类A1 86.87 70.33 95.33 96.00 A2 76.84 79.73 96.65 96.91 A3 79.81 61.17 96.17 97.49 从表 1的统计结果中可以发现，数据质量的聚类算法具有最高的平均准确率，相比于传统的K-mean算法和K-medoids算法分割聚类算法，在准确率上提高了很多，同时，与最新的峰值密度聚类算法相比，准确率也有所提高。
在数据集S1、S2、S3、S4中，每个类簇的中心是已知的，通过比较4种算法得到的聚类中心与实际中心的偏差量，对比每种算法确定聚类中心的效果。使用决策图确定数据质量聚类算法的聚类中心。K-means算法与K-medoids算法依然输入真实的类簇个数，4种算法聚类结果二维可视图如图 8所示。
![]()
图 8 数据集S1、S2、S3、S4聚类结果比较Figure 8. Comparison of Clustering Results on Datasets S1, S2, S3, S4在图 8中，数据质量聚类算法和峰值密度聚类算法的聚类效果直观上要优于K-means算法和K-medoids算法。在对比聚类效果后，统计4种聚类算法所确定的聚类中心与实际中心位置的误差率。具体计算式为：
$$ {{\gamma }_{i}}=\frac{1}{2}(\frac{{{x}_{i}}-{{a}_{i}}}{{{a}_{i}}}+\frac{{{y}_{i}}-{{b}_{i}}}{{{b}_{i}}}) $$ (2) 式中，xi和yi为实验中得到的聚类中心的坐标；ai和bi为数据集类簇实际的坐标。γi值越小，说明越接近实际的类簇中心。每个数据集中的平均误差率统计结果如表 2所示。
表 2 数据集S1、S2、S3、S4聚类中心平均误差率统计/%Table 2. Error Rate of Clustering Centers for Datasets S1, S2, S3, S4/%数据集 K-means
算法K-medoids
算法峰值密度
聚类数据质量
聚类S1 0.37 0.49 2.81 0.14 S2 0.53 0.74 0.31 0.11 S3 0.98 1.55 0.66 0.15 S4 1.39 1.71 0.46 0.14 从表 2中可以看出，数据质量聚类算法所确定的聚类中心与实际聚类中心的误差率最小，几乎与实际中心重合，明显优于K-means算法、K-medoids算法和峰值密度聚类算法。
综合数据集A1、A2、A3和数据集S1、S2、S3、S4的实验结果，可以认为数据质量聚类算法比传统的分割聚类算法和峰值密度聚类算法有更好的聚类效果。
2.3 实验结果分析
上述实验结果说明，数据质量聚类算法不仅可以准确提取出聚类中心的个数，而且在剩余点的划分上也有很高的准确率，对于数据集A1、A2、A3平均准确率分别达到了96.00%、96.91%和97.49%。在确定聚类中心上，本文方法也有很高的准确率，对于数据集S1、S2、S3、S4，聚类中心的平均误差率分别为0.14%、0.11%、0.15%和0.14%。数据质量聚类算法不仅在各项指标上明显优于传统的K-means算法和K-medoids算法，而且优于峰值密度聚类算法。
对于数据集A1、A2、A3，数据质量聚类算法比峰值密度聚类算法在平均准确率上分别提高了0.67、0.26和1.32个百分点，而对于数据集S1、S2、S3、S4，聚类中心的平均误差率分别降低了20.07、2.82、4.40和3.29倍。综合以上实验结果，可以证明数据质量聚类算法能够准确确定聚类中心，并能够得到准确的聚类结果。
3 结语
传统的中心聚类算法虽然简单快速，但是需要用户输入较多参数，并且具有球形偏差，在实际应用中有较多限制。本文提出了数据质量的概念，即代表了数据场中数据的固有属性，并且根据挖掘视角的不同，数据质量所代表的属性也不同。在本文中，赋予数据质量数据密集程度的属性，结合物理场中引力的概念，提出一种确定聚类中心的新方法，即具有较大质量和较大距离属性的点可以视为聚类中心。本文方法解决了需要用户输入参数、聚类结果受初始点影响等问题，减少了中心聚类算法在实际应用中的限制。实验结果证明，数据质量聚类算法能够准确找到数据集的聚类中心，并具有较为准确的聚类结果。
数据质量聚类算法虽然较为准确，但在实际应用中需要提高算法的效率，可以采取分布式计算的方式，这将是下一步研究的方向。
-
表 1 不同方法下实验结果Ⅰ（均值）
Table 1 Experimental Results Ⅰ of Different Methods (Mean Value)
要素类 容差/10-4° Length Ratio/% Hausdorff距离/10-5° TBF-SS/% 转角函数/((°)·m-1) 河流 3 97.73 26.574 5 91.48 24.765 1 8 94.38 65.791 2 70.95 29.523 7 边界 3 99.72 29.259 4 93.03 1.671 3 8 99.17 75.377 7 82.77 17.845 6 
下载: 导出CSV
表 2 不同方法下实验结果Ⅱ
Table 2 Experimental Results Ⅱ of Different Methods
要素类别 节点保留率/% Length Ratio/% Hausdorff距离/(10-5°) TBF-SS/% 转角函数/((°)·m-1) 河流 80 99.74 5.874 3 96.15 3.999 7 10 92.12 91.892 5 74.30 43.712 8 边界 80 100.00 2.597 2 95.87 0.286 1 10 98.21 179.638 5 85.46 22.936 6
下载: 导出CSV
表 3 不同方法下实验结果Ⅲ
Table 3 Experimental Results Ⅲ of Different Methods
线要素 删除节点 Length Ratio/% Hausdorff距离/m TBF-SS /% 转角函数/((°)·m-1) 线2 B、C 98.57(1) 1.128 4(4) 83.52(3) 28.686 7(5) 线3 D、 F 98.17(5) 0.742 2(1) 90.23(2) 10.669 4(2) 线4 E、G 98.37(3) 0.885 4(2) 91.03(1) 10.146 4(1) 线5 H、I 98.44(2) 1.021 5(3) 85.39(4) 12.277 6(3) 线6 I、J 98.25(4) 2.431 4(5) 41.52(5) 17.258 7(4) 注：3~6列中括号内数值表示线号
下载: 导出CSV
-
[1] 朱鲲鹏, 武芳, 王辉连, 等. Li-Openshaw算法的改进与评价[J].测绘学报, 2007, 36(4):450-456 doi: 10.3321/j.issn:1001-1595.2007.04.015 Zhu Kunpeng, Wu Fang, Wang Huilian, et al. Improvement and Assessment of Li-Openshaw Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4):450-456 doi: 10.3321/j.issn:1001-1595.2007.04.015
[2] 杜佳威, 武芳, 巩现勇, 等.采用双向斜拉式弯曲划分的曲线渐进化简方法[J].中国图象图形学报, 2017, 22(10):1 455-1 466 doi: 10.11834/jig.170238 Du Jiawei, Wu Fang, Gong Xianyong, et al. Progressive Line Simplification Approach Based on the Double-Oblique-Dividing-Curve Method[J]. Journal of Image and Graphics, 2017, 22(10):1 455-1 466 doi: 10.11834/jig.170238
[3] Burghardt D, Steiniger S. Usage of Principal Component Analysis in the Process of Automated Generalization[J]. Aq Australian Quarterly, 2005, 71(1):18-21 https://www.academia.edu/14968179/Usage_of_Principal_Component_Analysis_in_the_process_of_automated_generalisation
[4] 刘鹏程, 罗静, 艾廷华, 等.基于线要素综合的形状相似性评价模型[J].武汉大学学报·信息科学版, 2012, 37(1):114-117 http://ch.whu.edu.cn/CN/abstract/abstract102.shtml Liu Pengcheng, Luo Jing, Ai Tinghua, et al. Evaluation Model for Similarity Based on Curve Genera-lization[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1):114-117 http://ch.whu.edu.cn/CN/abstract/abstract102.shtml
[5] 帅赟, 艾廷华, 帅海燕, 等.基于形状模板匹配的多边形查询[J].武汉大学学报·信息科学版, 2008, 33(12):1 267-1 270 http://ch.whu.edu.cn/CN/abstract/abstract1775.shtml Shuai Yun, Ai Tinghua, Shuai Haiyan, et al. Polygonal Inquiry Based on Shape Template Matching[J]. Geomatics and Information Science of Wuhan University, 2008, 33(12):1 267-1 270 http://ch.whu.edu.cn/CN/abstract/abstract1775.shtml
[6] Belongie S, Malik J, Puzicha J. Matching Shapes[C]. ICCV2001, Vancouver, Canada, 2001
[7] Steiniger S, Weibel R. Relations Among Map Objects in Cartographic Generalization[J]. American Cartographer, 2007, 34(3):175-197 doi: 10.1559/152304007781697866
[8] 操震洲.网络多分辨率传输中曲线集的相似性度量模型研究[J].武汉大学学报·信息科学版, 2014, 39(10):1 257-1 260 http://ch.whu.edu.cn/CN/abstract/abstract3106.shtml Cao Zhenzhou. A Similarity Measurement Model for Multi-resolution Transmission of Curve Dataset over the Internet[J]. Geomatics and Information Science of Wuhan University, 2014, 39(10):1 257-1 260 http://ch.whu.edu.cn/CN/abstract/abstract3106.shtml
[9] 安晓亚, 刘平芝, 杨云, 等.一种线状要素几何相似性度量方法及其应用[J].武汉大学学报·信息科学版, 2015, 40(9):1 225-1 229 http://ch.whu.edu.cn/CN/abstract/abstract3325.shtml An Xiaoya, Liu Pingzhi, Yang Yun, et al. A Geometric Similarity Measurement Method and Applications to Linear Feature[J]. Geomatics and Information Science of Wuhan University, 2015, 40(9):1 225-1 229 http://ch.whu.edu.cn/CN/abstract/abstract3325.shtml
[10] Yan H, Li J. Spatial Similarity Relations in Multi-scale Map Spaces[M]. Switzerland: Springer International Publishing, 2014
[11] Seki M, Shimizu T, Matsumoto K. Part-Based Representations of Visual Shape and Implications for Visual Cognition[J]. Advances in Psychology, 2001, 130(2):401-459 http://cn.bing.com/academic/profile?id=1f1e61bf961ef0c57d1acca9f67423da&encoded=0&v=paper_preview&mkt=zh-cn
[12] 刘慧敏, 邓敏, 徐震, 等.线要素几何信息量度量方法[J].武汉大学学报·信息科学版, 2014, 39(4):500-504 http://ch.whu.edu.cn/CN/abstract/abstract2970.shtml Liu Huimin, Deng Min, Xu Zhen, et al. Geometric Information Content Measurement of Individual Line Feature[J]. Geomatics and Information Science of Wuhan University, 2014, 39(4):500-504 http://ch.whu.edu.cn/CN/abstract/abstract2970.shtml
[13] 朱强, 武芳, 钱海忠, 等.采用剖分思想的谷地弯曲识别及结构化方法[J].测绘科学技术学报, 2014(4):424-430 doi: 10.3969/j.issn.1673-6338.2014.04.020 Zhu Qiang, Wu Fang, Qian Haizhong, et al. Cognizing and Structuring Valley Curves of Contour Lines Based on the Idea of Subdivision[J]. Journal of Geomatics Science and Technology, 2014(4):424-430 doi: 10.3969/j.issn.1673-6338.2014.04.020
[14] 翟仁健, 武芳, 朱丽, 等.曲线形态的结构化表达[J].测绘学报, 2009, 38(2):175-182 doi: 10.3321/j.issn:1001-1595.2009.02.014 Zhai Renjian, Wu Fang, Zhu Li, et al. Structured Representation of Curve Shape[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2):175-182 doi: 10.3321/j.issn:1001-1595.2009.02.014
[15] 钱海忠, 武芳, 陈波, 等.采用斜拉式弯曲划分的曲线化简方法[J].测绘学报, 2007, 36(4):93-106 http://d.old.wanfangdata.com.cn/Periodical/chxb200704014 Qian Haizhong, Wu Fang, Chen Bo, et al. Simplifying Line with Oblique Dividing Curve Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4):93-106 http://d.old.wanfangdata.com.cn/Periodical/chxb200704014
[16] 操震洲, 李满春, 程亮.曲线弯曲的多叉树表达[J].测绘学报, 2013, 42(4): 602-607 http://d.old.wanfangdata.com.cn/Periodical/chxb201304019 Cao Zhenzhou, Li Manchun, Cheng Liang. Multi-way Trees Representation for Curve Bends[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 602-607 http://d.old.wanfangdata.com.cn/Periodical/chxb201304019
[17] 艾廷华, 郭仁忠, 刘耀林.曲线弯曲深度层次结构的二叉树表达[J].测绘学报, 2001, 30(4):343-348 doi: 10.3321/j.issn:1001-1595.2001.04.013 Ai Tinghua, Guo Renzhong, Liu Yaolin. A Binary Tree Representation of Curve Hierarchical Structure in Depth[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(4):343-348 doi: 10.3321/j.issn:1001-1595.2001.04.013
[18] 田泽宇, 门朝光, 刘咏梅, 等.一种应用三角形划分的空间对象形状匹配方法[J].武汉大学学报·信息科学版, 2017, 42(6):749-755 http://ch.whu.edu.cn/CN/abstract/abstract5748.shtml Tian Zeyu, Men Chaoguang, Liu Yongmei, et al. A Spatial Object Shape Matching Method Based on Triangular Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6):749-755 http://ch.whu.edu.cn/CN/abstract/abstract5748.shtml
[19] Hangouet J F. Computation of the Hausdorff Distance Between Plane Vector Polylines[C]. The 12th International Symposium on Computer-Assisted Cartography, Charlotte, USA, 1995
[20] 于晓艳.等高线简化算法评价体系研究[D].南京: 南京大学, 2011 http://cdmd.cnki.com.cn/Article/CDMD-10284-1011126159.htm Yu Xiaoyan. Research on Evaluating Indexes System of Contour Simplification Algorithms[D]. Nanjing: Nanjing University, 2011 http://cdmd.cnki.com.cn/Article/CDMD-10284-1011126159.htm
[21] Arkin E M, Chew L P, Huttenlocher D P, et al. An Efficiently Computable Metric for Comparing Polygonal Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3):209-216 doi: 10.1109/34.75509
[22] Douglas D H, Peucker T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]. Canadian Cartographer, 1973, 10(2):112-122 doi: 10.3138/FM57-6770-U75U-7727
计量
- 文章访问数: 1409
- HTML全文浏览量: 243
- PDF下载量: 196
