基于场论的空间聚类有效性评价方法研究

基于场论的空间聚类有效性评价方法研究摘要：空间聚类是空间数据挖掘与空间分析的重要手段之一，常用于揭示空间数据中隐藏的地理分布规律以及探测发现空间异常。空间聚类的有效性评价是对空间聚类结果进行定量、客观地评判，从而在实际应用中有利于针对不同数据集选取最优的空间聚类算法以及确定最佳的聚类参数。现有的聚类有效性评价方法一方面难以对空间簇为任意形状的空间聚类结果进行有效性评价，且很少顾及空间离群点对聚类有效性的影响；另一方面算法效率较低，难以应用于大型数据库。为此，本文从物理学中场论的角度，提出了一种基于场论的空间聚类有效性评价指标（简称FTSCV）。通过模拟实验、实际应用以及与经典的Dunn指数进行比较，发现本文提出的评价指标能够更准确、高效地对空间聚类结果的有效性进行评价，并可辅助选择空间聚类算法及聚类参数。关键词：空间聚类；有效性评价；场论；空间数据挖掘引言空间聚类是一种对空间数据进行深层次分析和挖掘的有效工具[1-4]，已成为地理信息科学与计算机科学共同关注的研究热点之一，广泛应用于地理学、制图学、地质学、遥感学、生物学、经济学等众多领域。空间聚类是一个无监督学习的过程，对其结果的有效性进行定量评价一方面有助于针对不同的应用选择最佳的空间聚类算法；另一方面可以指导选择最佳的聚类参数组合。紧密度和分离度是空间聚类有效性评价的两个基本准则，即空间簇内实体应尽可能紧密，而空间簇间应尽可能分离[5]。现有的聚类有效性评价方法主要分为：（1）外部评价法，如F-measure指数[6]、Rand指数和Jaccard系数[7]、Fowlkes-Mallows[8]指数等；（2）内部评价法，如Cophenetic相关系数[9]、Hubert’s统计量[10]等；（3）相对评价法，如Dunn指数[11]、Davies–Bouldin指数[12]、RMSSDT和RS指数[13]、SD指数[14]及S_Dbw指数[15]等。其中外部评价法对于聚类结果的评价是基于一种预先指定的结构，即已知簇的个数及正确的聚类结果，只注重数据分配的有效性，评价方法比较直接。内部评价法是针对数据集结构未知的情况，采用数据集固有的特征和量值对聚类结果进行评价，主要依据紧密度和分离度的原则，簇内方差及相关系数是比较常用的度量指标。这两种方法均是基于统计学的，计算过于复杂[10]，并且需要过多的先验信息，不适用于空间聚类的有效性评价。然而，相对评价方法不需要借助数据集的先验知识，也不需统计测试，其主要思想在于根据预先定义的评价准则，对某种算法不同参数设置的聚类结果进行评价，最终获得最佳的参数组合和聚类模式。或者，针对同一数据集，采用不同的算法及参数设置，选择最佳的聚类算法并获得最优的聚类结果。相对评价法大多采用簇内方差、直径、密度等描述簇的紧密程度；采用最短距离、最远距离、重心距离等描述簇间的分离程度。在空间聚类时，由于数据集的先验知识一般比较缺乏，同时聚类结果对参数较为敏感，故相对评价法更适用于对空间聚类结果有效性的评价。考虑到空间聚类的特点，空间聚类的有效性评价指标必须满足以下两点要求[9-10]：（1）能够评价任意形状空间簇的聚类有效性，同时能够顾及空间离群点的影响。（2）具有较高的运行效率。然而，现有的聚类有效性评价指标一般只适合评价球形空间簇的聚类结果，无法对任意形状空间簇的聚类结果进行准确评价，并且空间离群点对聚类结果的影响往往被忽视了。此外，现有指标的效率偏低，无法适用于大型空间数据库。为此，本文基于物理学中场论的思想，发展一种基于场论的空间聚类有效性评价方法。该方法可以对包含任意形状空间簇及空间离群点的空间聚类结果进行有效性评价，同时具有较高的运行效率。基于场论的空间聚类有效性评价方法现有的空间聚类及聚类有效性评价方法多数仅是从几何的角度出发，采用各种距离指标度量其紧密度和分离度，缺乏实际的物理意义。本文受物理学中场论思想的启发，根据实体间场力的相互作用关系来度量空间聚类的有效性。下面，首先借助Delaunay三角网和Voronoi图发展了一种适用于空间聚类的场理论，即凝聚场。2.1凝聚场在物理学中，场用来描述物质粒子间的非接触相互作用，常见的场有重力场、电场、磁场等。本文将场的思想引入空间聚类分析。其中，每个空间实体视为一个单位质量的质点，在其周围一定范围内产生一个稳定有源场，本文称之为凝聚场，并且每个质点都可以视为一个场源，对位于其产生的凝聚场中的所有实体均产生一个内向引力的作用，凝聚场的空间分布由场强函数确定。为了便于理解和说明，下面首先给出几个定义。定义1二维Voronoi图[18-19]：给定空间实体集合P，P={p1,p2,p3,…,pn}，对于P中任一点pi，其对应的Voronoi多边形piV可以定义为：piV={x∣d(x,pi)≤d(x,pj),pi,pj∈P,i≠j,x∈R2}（1）式中：d表示欧氏距离函数。P中所有点的Voronoi多边形构成点集P的Voronoi图（如图1实线所示），表达为：PV={p1V,p2V,p3V,…,pnV}（2）PV的对偶图为Delaunay三角网，记为D(P)，如图1虚线所示。定义2直接Voronoi邻近实体[20]：给定空间实体集合P，pi,pj∈P，若piV和pjV具有公共Voronoi边，则pi和pj互为直接Voronoi邻近实体。实体pi的所有直接邻近实体即为pi的Delaunay邻近实体，表示为ND(pi)。如图1，p1点的直接邻近实体为p2，p3，p4，p5和p6。定义3直接Voronoi区域：对于空间实体pi，piV与pi的直接Voronoi邻近实体对应的Voronoi多边形所构成的区域称为pi的直接Voronoi区域，记为DNV(pi)。如图1，p1的直接Voronoi区域包括p1V,p2V,p3V,p4V,p5V,p6V。图1图1凝聚场Fig.1AggregationfieldP2P1P3P4P5P6P7P8P9P10P12P13P14P15P11由于短程场作用更有利于揭示数据分布的聚簇特性，因此凝聚场的作用范围必须在有限的范围内迅速衰减[21]。仿万有引力定义场强函数，其衰减速度较慢，容易出现“球形偏见”现象。采用高斯函数定义场强函数时，虽可以保证场强迅速衰减，但由于空间数据分布通常是不均匀的，导致影响因子的设定比较困难。二维Voronoi图可以视为以平面内每个点作为生长核，以相同速率向外扩张，直到彼此相遇后停止生长，反映了实体天然的“势力范围”，因此本文借助Voronoi图和Delaunay三角网对空间的自然划分来约束场强函数的影响范围，进而可以表达凝聚场的场强函数为：（3）式中：Ep为场源p在空间上产生的凝聚场的场强；k为凝聚场辐射因子，本文设置为1；xi为任意一个空间位置；d(p,xi)为实体p与xi的欧氏距离；σ为衰减因子；epxi为p指向xi的单位矢量。从式（3）可以看出，一个场源产生的凝聚场，在其直接Voronoi区域内，场强函数的衰减满足距离平方反比关系；而在空间其他的区域场强函数迅速衰减，迅速达到可以忽略的程度。进而，可以表达两个实体间的凝聚力为：（4）式中：mq为实体q的质量，考虑到可以将空间点实体均视为单位质点，故令mq为1；d(p,q)为实体p与q的欧氏距离；σ表示衰减因子；epq表示p指向q的单位矢量。分析式（4）可以发现，一个场源只对其Delaunay邻近实体有明显的凝聚力作用，对其它空间实体的作用可以忽略。在凝聚场的基础上，下面进一步发展空间聚类有效性评价方法。2.2基于凝聚场的空间聚类有效性评价方法空间聚类是将空间数据库中的空间实体划分成具有一定意义的若干空间簇，使得每个空间簇内实体具有最大相似度，而簇间实体差别最大[16]。从凝聚场的角度，空间聚类的最佳效果是使得空间簇内实体间的凝聚力作用最大化，而不同簇之间的凝聚力作用最小化。于是，如果某个空间簇内的实体间凝聚力的作用越强，其“抱团”的趋势也就越明显，作为一个空间簇存在也就越合理。而不同簇之间加以区分，是因为簇之间实体的相互凝聚力过小。空间离群点可以视为一个特殊的空间簇，故离群点受到的凝聚力也应该较小。因此，一个高质量的空间聚类结果必须满足以下两个条件：（1）空间簇（包括空间离群点）之间凝聚力的作用尽可能小；（2）空间簇内实体间的凝聚力作用尽可能大。基于以上假设，下面给出空间聚类有效性评价指标的具体定义：定义4凝聚树：对于空间簇C，其形成过程可以描述为从任一空间实体开始，不断“吸附”与当前实体凝聚力作用最大的实体，最终簇中所有实体形成一个通过凝聚力联系起来的树形图结构，称为凝聚树，记为AT(C)。凝聚树与最小生成树具有相同的几何结构，凝聚树中所有实体间凝聚力的作用最强，可以更好地反映空间簇实体的紧密程度，进而给出簇内凝聚力的定义：定义5簇内凝聚力：对于一个包含n个实体的空间簇C，其生成的凝聚树为AT(C)，凝聚树中实体间所有凝聚力构成凝聚力集合AF(C)，凝聚力平均值记为μAF，方差记为σAF。进而，簇内凝聚力FI(C)可以表达为：（5）式中：m表示所有小于μAF-σAF的凝聚力数量。可以看出，簇内凝聚力的定义顾及了实体分布的均匀程度，避免了个别极限异常值的干扰。定义6簇间凝聚力：对于任一空间簇（或空间离群点）C，其簇间凝聚力定义为其他簇内实体对C内实体凝聚力的平均值，记为FE(C)，表达为：piC,pjC且pjND(pi)（6）式中：w表示其他空间簇（包括空间离群点）与空间簇C中实体有凝聚力作用的实体数量。进而，对于一个给定的空间数据库SDB，不妨设它的全部实体划分为M个空间簇，分别记为C1,C2,…,CM；同时获得N个空间离群点，分别记为O1,O2,…,ON。于是，空间聚类有效性度量指标可以定义为所有簇内凝聚力的最小值与簇间凝聚力平均值的比值，记为FTSCV，表达为：（7）从式（7）可以看出，针对一个空间聚类的结果，若空间簇内实体的凝聚力越强，簇间实体的凝聚力作用越弱，则FTSCV值越大，表示聚类的效果越好。同时亦可以发现，本文在评价过程中顾及了空间离群点的影响，而且在计算簇间的凝聚力作用时，将空间簇视为一个整体，充分体现了不同簇之间的凝聚力作用关系，避免了传统评价簇间分离度指标（如最短距离、质心距离）不能适用于任意形状空间簇的缺点。2.3方法实现与复杂度分析对于一个包含n个空间实体的空间数据库SDB，采用FTSCV指标对其空间聚类有效性进行评价时，主要分为以下几个步骤：针对空间数据库中所有实体构建Delaunay三角网，复杂度为O(nlogn)[22]。针对每个空间簇生成凝聚树。本文采用Kruskal算法在Delaunay三角网的基础上构建凝聚树，其复杂度为O(nlogn)。计算簇内凝聚力。在最差的情况下其复杂度为O(nlogn)。计算簇间凝聚力。由于Delaunay三角网的边数最大为3n-6，每个结点直接连接的结点数平均为6，于是此步骤的复杂度为n*O(6log6)=O(n)计算有效性评价指标FTSCV。综合以上几个步骤，采用FTSCV指标对空间聚类的有效性进行评价时的时间复杂度为O(nlogn)+O(nlogn)+O(nlogn)+O(n)nlog(n)。而当前聚类有效性指标[11-15]的复杂度多为O(n2)，可见本文方法的效率明显提高。3．实验分析下面设计两个实验来验证本文空间聚类有效性评价方法的正确性和可行性。实验一模拟了文献[17]中采用的三组经典模拟数据库作为研究对象，如图2（a）～（c）所示，并分别对DBSCAN算法和K-means算法的空间聚类结果进行有效性评价，指导选择最佳聚类算法和聚类参数组合。实验二采用我国华南某市土壤监测空间数据（如图2（d）所示）作为研究实例，对DBSCAN算法的聚类结果进行评价，指导选择最佳的聚类参数。图3和图4分别给出DBSCAN和K-means算法对三组模拟数据库的聚类结果。（（a）数据库1（n=190）（b）数据库2（n=295）（c）数据库3（n=213）（d）实际数据（n=104）图2实验数据库Fig.2Experimentaldatabases（a）（a）Eps=28MimPts=5（b）Eps=29MimPts=5（c）Eps=35-109MimPts=5（d）Eps=110-119MimPts=5（e）Eps=20MimPts=6（f）Eps=25MimPts=6（g）Eps=28-64MimPts=6（h）Eps=65MimPts=6（i）Eps=30MimPts=5（j）Eps=35MimPts=6（k）Eps=45MimPts=5（l）Eps=190MimPts=5图3DBSCAN算法聚类结果Fig.3ResultsviaDBSCANspatialclustering（（a）k=4FTSCV=0.09（b）k=4FTSCV=0.14（c）k=4FTSCV=37.03（d）k=4FTSCV=0.07（e）k=4FTSCV=0.10（f）k=4FTSCV=0.18（g）k=4FTSCV=0.16（h）k=4FTSCV=0.11（i）k=4FTSCV=0.03（j）k=4FTSCV=0.07（k）k=4FTSCV=0.01（l）k=4FTSCV=1.32图4K-means算法聚类结果Fig.4ResultsviaK-meansspatialclustering进而，分别采用本文提出的FTSCV指标和Dunn指标对上述聚类结果进行评价，结果如表2所示。Dunn指标采用簇的直径表示空间簇的紧密程度，采用簇间距离表示空间簇间的分离程度。对于一个具有k个空间簇的聚类结果，Dunn指标具体表达如下：（8）式中：d(Ci,Cj)为簇间实体最短距离；diam(Cm)为簇的直径，即簇内实体间最大距离。Dunn指标数值越大，则表示聚类结果越好。表2表2DBSCAN和K-means聚类的有效性评价结果Tab.2ValidityassessmentofspatialclusteringresultsofDBSCANandK-means数据库DBSCANK-means参数FTSCVDunnFTSCV数据库1Eps=28，MinPts=51.350.100.09Eps=29，MinPts=51.660.350.14Eps=35-109，MinPts=537.030.3537.03Eps=110-119，MinPts=52.320.260.07数据库2Eps=20，MinPts=62.210.050.10Eps=25，MinPts=615.730.050.18Eps=28-64，MinPts=628.680.120.16Eps=65，MinPts=62.530.130.11数据库3Eps=30，MinPts=52.280.110.03Eps=35，MinPts=59.630.110.07Eps=45，MinPts=515.210.690.01Eps=190，MinPts=52.690.391.32对DBSCAN算法聚类评价结果进行分析可以发现：（1）针对数据库1和2，FTSCV指标可以准确识别最佳聚类结果，当出现过多离群点或过度聚类时FTSCV指标较低，而在正确聚类时FTSCV指标显著增大，因此可以有效指导聚类参数的选择。而Dunn指数对数据库1，2的评价结果差异不大，同时无法准确反映聚类的有效性。例如，对于数据库1，无法区分图3（b）和（c）的聚类结果；对于数据库2，则给出了错误的评价结果。（2）针对数据库3，Dunn指数对图3（i）、（j）的聚类结果无法区分，过度聚类时有效性反而较高，显然不合理。FTSCV指标认为图3（j）、（k）的情况有效性较高，其中图3（k）的情况有效性最高，似乎与文献[17]中的正确聚类结果存在差异，而实际上这是由于空间聚类中存在的尺度效应造成的，在较大尺度上（图3（k）），中虚线内实体的内部差异性不显著，而随着尺度缩小（图3（j））则应进行区分。对图3（j）、（k）中虚线框部分聚类结果进行局部评价发现，图3（j）中聚类结果的有效性（FTSCV=14.25）明显大于图3（k）的情况（FTSCV=6.69）。进一步分析DBSCAN和K-means算法对同一数据库的聚类结果可以发现，K-means算法的聚类有效性远低于DBSCAN算法，只是在数据库1中可以得到较好的聚类效果，而对于任意形状的空间簇以及包含较多空间离群点的情况效果很不理想，这亦表明上述数据库选用DBSCAN算法聚类更为合理。下面采用实际地理空间数据对FTSCV指标的实用性进行验证。不同参数下DBSCAN算法的聚类结果如图5所示，对应的FTSCV指标与Dunn指数的有效性评价结果列于表3。（a）（a）Eps=8kmMimPts=3（b）Eps=9kmMimPts=3（c）Eps=10kmMimPts=3（d）Eps=12kmMimPts=3（e）Eps=15kmMimPts=3（f）Eps=8kmMimPts=4（g）Eps=9kmMimPts=4（h）Eps=10kmMimPts=4（i）Eps=12kmMimPts=4（j）Eps=15kmMimPts=4图5不同参数下DBSCAN聚类结果Fig.5SpatialclusteringresultsviaDBSCANwithdifferentsettingofparameters表3表3利用FTSCV指标和Dunn指数评价空间聚类有效性Tab.3ValidityassessmentofspatialclusteringresultsbyFTSCVandDunnindicators参数FTSCVDunn参数FTSC