1.一种居民地多边形的多级图聚类划分方法,其特征在于:具体包括以下步骤:步骤1、选定居民地的地理区域,获取多边形的图形,并以此为依据构建Delaunay三角网,获取多边形之间的邻接信息;然后获取多边形各个顶点的数据,再次构建Delaunay三角网,并根据五个多边形的相似性度量指标对多边形之间的空间相似性进行度量,得到对应的相似性数值,五个多边形的相似性度量指标分别为形状狭长度、大小、凹凸性、距离和连通性;
步骤2、将经由各个指标计算得到的相似性数值进行归一化处理,并使用信息熵权重法确定各个指标的权重,最终得到多边形之间空间相似性数值;
步骤3、获取多边形之间的空间相似性数值,并对数据进行组织与存储,使用多级图划分算法,经过粗化阶段、初始划分阶段和细化阶段,对多边形进行聚类,并得到聚类结果。
2.如权利要求1所述的居民地多边形的多级图聚类划分方法,其特征在于:多边形之间的空间相似性的计算方法如下式所示:S(x,y)=μ1*A(x,y)+μ2*B(x,y)+μ3*C(x,y)+μ4*D(x,y)μ5*E(x,y)其中,A(x,y),B(x,y),C(x,y),D(x,y),E(x,y)分别为形状狭长度、大小、凹凸性、距离和连通性经过标准化处理后的数据,μ1、μ2、μ3、μ4、μ5则分别为五个指标的权重,S(x,y)为多边形x和多边形y之间空间相似性,且有μ1+μ2+μ3+μ4+μ5=1,0≤A(x,y),B(x,y),C(x,y),D(x,y),E(x,y)≤1。
3.由权利要求1所述的居民地多边形的多级图聚类划分方法,其特征在于:所述步骤1中使用的形状狭长度、大小、凹凸性、距离和连通性五个相似性度量指标的计算方法如下式所示,具体的描述方法如下:(a)形状狭长度:
其中,ax,bx分别表示多边形x的最小外接矩阵的长和宽,shp(x,y)是多边形x和多边形y之间的形状狭长度相似性;
(b)大小相似性:
其中,Area(x)和Area(y)分别指多边形x和多边形y的面积,size(x,y)指多边形x和多边形y之间的大小相似性;
(c)凹凸性:
其中,Area(x)是指多边形x的面积,peri(x)是指多边形x的周长,cvx(x,y)是指多边形x和多边形y的凹凸性相似性;
(d)距离:
其中, 是指连接多边形x,y的所有Delaunay三角形的边的长度之和,n为两个多边形之间边的个数,dist(x,y)为多边形x和多边形y之间的距离相似性;
(e)连通性:
con(x,y)=Len(Landscape(x,y))
其中,Landscape(x,y)是指连接多边形x和多边形y的所有Delaunay三角形的边的中点连成的线,Len(Landscape(x,y))是指多边形x和多边形y之间毗邻边界的长度,con(x,y)是指多边形x和多边形y之间连通性相似性。
4.如权利要求3所述的居民地多边形的多级图聚类划分方法,其特征在于:步骤2中计算得到的相似性数值先进行标准化处理,采用最大最小化准则进行归一化处理,同时使用信息熵权重法确定各个指标的权重,最终得到多边形之间空间相似性数值;
具体的描述方法如下:
(a)信息熵权重法确定各个指标的权重:
1)记n为多边形的数目,m为相似性指标的数目,xij为第i个多边形第j个指标的数值,其中i=1,2,…n,j=1,2,…m;
2)计算第j个指标下第i个多边形占该指标的比重:
3)计算第j项指标的熵值:
其中,k=1/ln(n)>0,且满足ej≥0;
4)计算信息熵冗余度:
dj=1-ej
5)计算各项指标的权值:
(b)多边形之间的空间相似性计算:
S(x,y)=μ1*A(x,y)+μ2*B(x,y)+μ3*C(x,y)+μ4*D(x,y)μ5*E(x,y)
0≤A(x,y),B(x,y),C(x,y),D(x,y),E(x,y)≤1其中,x为计算的相似性指标值,min(x)和max(x)分别为指标x所有值中的最小值和最大值,x’为经过标准化处理之后的值,此时所有的值落到[0,1]的区间内,A(x,y),B(x,y),C(x,y),D(x,y),E(x,y)分别为形状狭长度、大小、凹凸性、距离和连通性经过标准化处理后的数据,μ1、μ2、μ3、μ4、μ5则分别为五个指标的权,S(x,y)为多边形x和多边形y之间空间相似性。
5.如权利要求1所述的居民地多边形的多级图聚类划分方法,其特征在于:多级图划分算法主要分为数据组织阶段、粗化阶段、初始划分阶段和细化阶段四个阶段,具体的描述方法如下:(a)数据组织阶段:给定图Gt=(Vt,Et),其中 存储着第t个划分子图中的所有顶点v的信息,E则存储着邻接点之间的边的信息,即为多边形之间的邻接信息,记为Adjcy;
(b)粗化阶段:生成一系列的子图,每个子图中含有的点的个数将会较原始图形有所减少,主要由匹配和重构两个部分构成:在匹配阶段,采用最大化匹配准则,记Map[v]为被匹配并存储到粗化图Gi+1中的顶点v,Match[v]则为那些未被匹配的顶点;
在重构阶段,利用在匹配阶段生成的点来生成粗化图Gi+1,设定顶点v1,v2为两个被匹配的顶点,重构顶点u1=Map[v1],那么与u1邻接的顶点为:Adj(u1)=({Map[x]|x∈Adj(v1)}∪{Map[x]|x∈Adj(v2)})-{u1}且边(u1,u2)之间的权值为:
w(u1,u2)=∑x{w(u1,x)|Map[x]=u2}+∑x{w(u2,x)|Map[x]=u2};
Adj(v2)为多边形v2的邻接信息;
(c)初始划分阶段:使用Kernighan-Lin算法来计算最粗糙和最小图形的划分,设定P为G=(V,E)原始划分的顶点,定义gaingv为代价函数,将点v从当前聚类簇中移动到其他簇时,边界权值的减少值定义为:其中w(v,n)是指边(v,n)的权重值,且在每移动一个顶点之后,都需要重新计算并更新与之相邻接的顶点的gain值;
(d)细化阶段:通过遍历图形Gm-1,Gm-2,…,G1,粗化图形Gm的划分Pm被映射到原始图形上,根据Pi+1得到Pi可以通过将分解成为v∈Gi+1的点集 分配到划分Pi+1[v]中实现;
使用Kernighan-Lin细化算法,使用控制顶点的gain值进行计算,gain值通过计算每一个顶点的两个值ID和ED来表示:其中ID[v]是指与顶点v在同一个簇内且与v邻接的点连线的边的权值之和,是用来度量聚类簇内部紧密度的一项指标,ED[v]是指与顶点v不在同一个簇内且与v相邻接的点之间的边的权值之和,是用来度量聚类簇分离度的一项指标,那么gv=ED[v]-ID[v];P[v]为顶点集合P中的v顶点、P[u]为顶点集合P中的u顶点。
6.如权利要求1所述的居民地多边形的多级图聚类划分方法,其特征在于:采用多边形的轮廓系数的均方根作为度量聚类结果的评价指标,具体的描述方法如下:
(a)各个多边形的轮廓系数:
其中,i表示第i个空间实体对象,a(i)表示第i对象到簇中其他所有对象的平均距离,体现空间簇内部对象之间的凝聚度;b(i)表示第i个对象到给定簇中其他所有对象的平均距离,体现空间簇之间的分离度;轮廓系数sil(i)∈[-1,1],sil(i)为负时,即b(i)a(i),代表该对象与所在簇对象之间的凝聚度大于与其他簇对象之间的分离度,不需对该对象所属空间簇做出调整;
(b)轮廓系数的均方根:
其中,meana(i)为各个簇中所包含对象的轮廓系数的均值,k为第i个簇中所包含的对象的个数,n为数据集中的样本数目,RMSE越小,表示均方根误差越小,聚类结果越好;RMSE为轮廓系数均方根误差。
7.如权利要求1-6任一项所述的居民地多边形的多级图聚类划分方法,其特征在于:对所述聚类结果使用轮廓系数进行评估而判断聚类结果的精准度,并结合K-Means++算法和ArcToolbox得到的聚类结果进行对比分析。