EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 6: 638 - 643

DOI: https://doi.org/10.3724/SP.J.1047.2015.00638

Orginal Article

Self-organizing Dual Spatial Clustering Algorithm and Its Application in the Analysis of Urban Sprawl Structure

  • JIAO Limin , * ,
  • ZHANG Xin ,
  • MAO Lifan
Expand
  • 1. School of Resource and Environment Science, Wuhan University, Wuhan 430079, China
  • 2. Key Laboratory of Geographic Information System, Ministry of Education, Wuhan University, Wuhan 430079, China
*Corresponding author: JIAO Limin, E-mail:

Received date: 2014-11-18

  Request revised date: 2015-01-31

  Online published: 2015-06-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Dual spatial clustering is an exploratory data analysis that deals with spatial contiguity and attributive similarity. Conventional spatial clustering methods cannot perform effective clustering in spatial and attribute domains simultaneously. This study employs SOFM (Self-Organizing Feature Mapping) to solve dual spatial clustering problems, and then verify the proposed method in the analysis of urban expansion structure. By modifying the algorithm of best matching neuron searching in SOFM, we manage to perform clustering in both spatial and attribute domains. The algorithm includes two independent self-organizing clustering processes. The first one includes a spatial constraint, and the other one includes an attribute constraint. The final result is generated by merging the corresponding two results that derived separately from the two processes. The analysis of the structure of urban expansion of Wuhan city is used as a case study. We feed the proposed model with the location information and the expansion degree information of newly grown urban patches, and the generated dual clustering results could clearly illustrate the spatial structure of urban expansion. As a conclusion, the self-organizing dual spatial clustering method can generate spatial continuous and attributive similar clusters with little artificial interference.

Key words： self-organizing feature mapping; dual spatial clustering; urban expansion; landscape expansion index; spatial cluster

Cite this article

JIAO Limin , ZHANG Xin , MAO Lifan . Self-organizing Dual Spatial Clustering Algorithm and Its Application in the Analysis of Urban Sprawl Structure[J]. Journal of Geo-information Science, 2015 , 17(6) : 638 -643 . DOI: 10.3724/SP.J.1047.2015.00638

1 引言

双重空间聚类是指同时顾及空间域和非空间属性域的空间聚类挖掘,它针对高维空间数据进行探测性分析。Lin等提出了“双重聚类”问题（Dual Clustering）,即最优化域（Optimization domain）和约束域（Constraint domain）上的聚类,要求聚类目标方程中包含最优化域上的属性而聚类结果满足几何上连续、非覆盖的约束条件[1]。应用双重聚类的思路对带有非空间属性的空间数据进行聚类分析,与传统空间聚类在聚类目标和聚类算法方面均有明显区别,称为“双重空间聚类”。双重空间聚类既不同于一般的属性聚类问题,也不同于常规空间聚类问题。一般的属性聚类针对非空间属性数据进行聚类研究;常规的空间聚类则以空间对象的地理位置数据发现其几何学上的聚集分布特征;而双重空间聚类的本质是研究地理空间对象的属性或属性组合在空间上聚集、延伸、变化的分布规律。
在聚类算法上,双重空间聚类必须把空间对象的位置特征和属性特征区别对待,由前者派生的空间关系是约束条件,而后者才是聚类目标函数的主要关注域;在聚类结果上,则可能会产生非凸、环、岛等各种复杂区域[2]。显然,传统的空间聚类及其改进得到的高维空间聚类算法,并没有区分空间位置特征和属性特征,不可能实现双重空间聚类目标。传统空间聚类算法的简单改进,也无法满足双重空间聚类的聚类准则。现有的双重聚类算法主要采用修改聚类统计量（如增加惩罚因子）、局部密度分析、随机取样等方法,但其存在效率低、初值依赖等问题。
常规空间聚类算法根据聚类算法设计思路分为4类：划分法、层次法、密度法和网格法[3-5]。常规空间聚类算法主要通过空间距离、分布密度等统计量,采用迭代、分割或合并算法来完成对聚类对象的分类,从而刻画其空间聚集特征。显然,这与双重空间聚类要求同时在空间域和属性域上聚类,并得到空间连续约束条件下的属性聚集特征不同。由于聚类的目标和准则不同,对常规空间聚类的简单改进并不能实现双重空间聚类。Lin等提出的双重聚类的ICC算法,通过循环交错执行支持向量机（SVM）的空间划分和基于层次聚类法的属性聚类来实现双重聚类目标[1],该算法效率较低,SVM的参数对聚类结果影响较大,适用于各向同性数据空间。Tai等提出了BINGO算法来解决同时顾及地理空间和最优化空间的聚类问题[6]。该方法采用先细分再合并的2步法,可适用于形状更为复杂的双重聚类挖掘。但其采用规则网格划分得到T-region的方法具有一定的机械性,同时生成邻接图耗时较大。Zhang等提出的一种惩罚空间距离度量,与一般聚类算法结合使用可实现聚类结果的非覆盖[7]。该方法的聚类结果不一定能满足属性域上“类内距离最小类间距离最大”的准则。有学者提出了在密度方法上的改进算法[8-9],这些方法也难以满足双重空间聚类的准则。Henriques等通过在SOFM学习算法中,加入地理空间约束构造了GeoSOM模型,并给出了一个可视化的自组织聚类工具,使用人机交互的方式提取聚类结果[10]。但是,该模型需要预定义非常大的聚类类别数,并使用人机交互发现聚类结果,带来了不确定性。文献[11]提出了双重距离的空间聚类方法,使用染色递归检索策略求解空间位置毗邻和非空间属性相近的空间聚类问题。有学者进一步研究了双重距离聚类的改进和应用[12],以及多约束的点群空间聚类问题[13]。此外,还有学者研究了连续数据离散化的最优化方法[14],并用于地理探测器模型[15],该方法对于聚类算法设计和聚类结果评价具有重要参考价值。
本研究在自组织特征映射的训练算法中加入空间约束和属性约束,分别得到空间约束优先的聚类结果和属性约束优先的聚类结果,并将2类结果融合得到较为稳定的双重空间聚类结果,进一步研究了该算法在武汉市城市扩张结构的自组织识别中的应用。

2 自组织双重空间聚类模型

2.1 自组织特征映射

自组织特征映射是一种自组织神经网络,采用竞争学习机制实现对输入样本的自组织聚类,特征相似的点在聚类空间中也相邻。自组织特征映射的基本结构由输入和输出2层组成,2层之间相互连接。自组织特征映射用于聚类分析时,输入层表示聚类样本的特征空间,输出层表示目标聚类空间（图1）。
Fig. 1 The structure of SOFM neutral network

图1 自组织特征映射神经网络的结构

自组织特征映射的空间数据聚类分析主要包括4个步骤：（1）对网络连接权重进行随机初始化;（2）选择一个样本输入,在输出层寻找最佳匹配神经元,使其与输入样本距离最小,也即其对应的权重矢量和样本距离最小;（3）根据该距离调整获胜神经元及其邻域神经元对应的连接权重;（4）重复步骤（2）和（3）,直至网络收敛,即每个样本都与一个输出神经元稳定对应。网络训练完成后,根据样本与输出层神经元的对应情况进行数据聚类,每个输出神经元代表一个类中心。

2.2 自组织双重空间聚类算法

将自组织特征映射用于空间数据聚类的最直接方法,是将空间数据的坐标维和属性维作为自组织特征映射的输入维,以常规竞争学习算法进行训练。改进的方法是设计空间和属性加权的复合距离统计量,建立权重和最终聚类结果的类内属性距离方差关系,根据预期的类内属性聚类方差选择合适的权重[16],该方法需较复杂的聚类后处理。文献[10]给出了另一种改进方法,通过加入空间约束使得聚类结果空间连续,即在寻找最佳匹配单元时,限于一定的空间距离范围内。但是,该方法需设定较大的输出层,并通过人工交互识别聚类结果,具有一定的不确定性和人为干扰。因此,本研究给出一种新的自组织聚类改进方法,以克服上述问题：（1）根据空间距离搜索一个最佳匹配单元集合,然后在此集合中根据空间和属性寻找最佳匹配单元,该过程执行“空间约束优先”聚类;（2）根据属性距离搜索一个最佳匹配单元集合,然后在此集合中根据空间和属性寻找最佳匹配单元,该过程执行“属性约束优先”聚类。将2个过程的聚类结果合并,即在每种聚类算法中都被归为同一类的样本,最终才会被归为一个类别。2个过程的聚类结果都是一种双重聚类结果,但是,“空间约束优先”聚类结果和“属性约束优先”聚类结果,分别满足了空间距离约束和属性聚类约束,将2个聚类结果融合可使得聚类结果同时满足2类约束条件。该方法不需要人工交互提取聚类,适用于大规模的双重聚类划分。该算法流程如图2所示。
Fig. 2 The flowchart of dual spatial clustering algorithm

图2 自组织双重空间聚类算法流程图

设：x为一组n维的训练样本 x 1 , x 2 , ⋯ , x n ,每一个样本都包含空间属性geoi和非空间属性ngfi;W是一个 p × q 的矩阵,元素 w ij 中的i和j分别表示其在矩阵中的行数和列数;每个 w ij 都包含一个空间要素wgeoij和一个非空间要素wngfij,即 w ij = [ wge o ij , wng f ij ] ; α 是学习率,初始化为（0,1）内的实数; r 是邻域函数 h ( w ij , w mn , r ) 的参数,表示邻域半径; g 和 a 分别为空间域和属性域上的最佳匹配单元的限值;若样本和输出神经元的空间距离 ≤ g ,则认为空间相邻,若样本和输出神经元的属性距离 ≤ a ,则认为属性相似。
（1）“空间约束优先”聚类,伪代码如下：
For m=1 to n：
对于所有 w ij ∈ W ：
计算空间距离： d ij = wge o m - wge o ij
选择 d ij 的最小值,即为空间域获胜神经元 w BMUgeo ;确定一个集合 W BMU ,使 W BMU 中的元素与 w BMUgeo 的空间距离不大于限值 g ;
对于所有 w ij ∈ W BMU ：
计算距离值： d ij = x m - w ij
根据 d ij 选择获胜神经元 w BMU ,使得其对应的 d ij 取得最小值 min ( d ij ) ;
更新获胜神经元及其邻域内神经元对应的连接权重： w ij ∈ W : w ij = w ij + αh w BMU , w ij , r x m - x ij ;
减小 α 和r的值;
循环执行上述步骤,直至收敛。
（2）“属性约束优先”聚类,伪代码如下：
For m=1 to n：
对于所有 w ij ∈ W ：
计算距离值： d ij = x m - x ij ;
选择 d ij 的最小值,即为属性域获胜神经元 w BMUngeo ;确定一个集合 W BMU ,使 W BMU 中的元素与 w BMUngeo 的属性距离不大于限值 a ;
对于所有 w ij ∈ W BMU ：
计算距离值： d ij = x m - w ij ;
根据 d ij 选择获胜神经元 w BMU ,使得其对应的 d ij 取得最小值 min ( d ij ) ;
更新获胜神经元及其邻域内神经元对应的连接权重： w ij ∈ W : w ij = w ij + αh w BMU , w ij , r x m - x ij ;
减小 α 和r的值;
循环执行上述步骤,直至收敛。
（3）合并上述2个过程产生的聚类结果,作为最终结果。
一般地,“空间约束优先”聚类与“属性约束优先”聚类得到的结果会有差异。前者在满足空间连续性限值条件下寻找最佳匹配神经元,优先考虑了空间连续约束;后者是在满足属性相似性限值条件下寻找最佳匹配神经元,优先考虑了属性相似约束。但是,由于所采用的竞争学习训练算法的自组织特征,使得聚类结果具有相对稳定性。将上述2种算法产生的聚类结果进行叠置,从而产生同时满足2类约束的聚类结果。

3 算法实验分析

3.1 实验区及数据

本实证分析以2000-2010年的武汉市城市扩张斑块数据为聚类对象,以图斑位置信息和图斑扩张程度指数为输入数据,通过双重空间聚类分析发现了城市扩张组团结构。其中,图斑位置信息为空间信息,图斑扩张程度指数为图斑的属性信息。
武汉市简称“汉”,是湖北省省会,也是中国中部最大的城市,位于江汉平原东北部,地处东经113°41'~115°05',北纬29°58'~31°22'。本文采用了3景TM/ETM+影像作为原始数据,成像日期分别为2000年11月7日、2005年9月11日、2010年9月17日;使用ENVI5.0进行影像融合、影像配准校正、监督分类和建设用地提取,影像总体分类精度均在85%以上。2000、2005和2010年武汉市建设用地分布如图3所示。
Fig. 3 The study area and the distribution of urban patches

图3 研究区域及建设用地斑块分布图

本研究采用多阶景观扩张指数（Multi-order Landscape Expansion Index,MLEI）作为图斑扩张程度的度量指数。MLEI由景观扩张指数（Landscape Expansion Index,LEI）[17]改进而来。斑块MLEI指数的计算公式如式（1）所示。
MLE I i t = ∑ j = 1 m ( MLE I j t - n × a ij ) A i （1）
式中, MLE I i t 代表第t期数据中第i个斑块的MLEI值; MLE I j 代表与第i个斑块缓冲区有重叠的第j个斑块MLEI值; a ij 代表与第i个斑块的缓冲区有重叠的第j个斑块重叠部分的面积; A i 代表第i个斑块缓冲区面积;求和式中的m为所有与缓冲区相重叠的斑块数量,n的取值范围是 1 t ] ; MLE I i 0 代表第0期数据（即基期数据）第i个斑块MLEI预设值, MLE I i 0 取值为100。根据定义,MLEI的值域范围是[0,100]。

3.2 自组织双重空间聚类算法的城市扩张组团识别

以2010年武汉市新增建设用地斑块为样本,共计87 153个图斑。自组织双重空间聚类算法的输入层包括3个神经元：斑块几何中心点的x、y坐标,斑块MLEI指数。本文分别采用“空间约束优先”型和“属性约束优先”型2种聚类算法,将2类结果融合,得到最终聚类结果;提取MLEI均值较小（扩张程度较大）的类别,并生成类别边界,如图4所示。
Fig. 4 Extracting urban expansion structure with self-organizing dual spatial clustering algorithm

图4 自组织双重空间聚类提取城市扩张组团结构

对比图4的组团边界和MLEI取值可看出,采用双重空间聚类算法较好地提取了扩张程度较大的区域。图4中用矩形和数字标出的6个区域是武汉市总体规划（2005-2020年）中确定的未来城市发展的组团中心。从聚类分析提取的组团结构可看出,规划的2、4、5、6组团中心扩张显著并且形成了较大的连片建成区。这些区域在2000-2010年间经历了高度扩张,尤其是包含了武汉东湖高新开发区的区域2。区域4是汽车产业中心,区域5是食品和轻工业中心,区域6附近坐落着天河机场,该区域物流业发展迅速。在区域1和3可看出,中小扩张组团分布。城市扩张组团结构识别,可为城市扩张特征分析和未来城市规划提供必要的信息支持。自组织双重空间聚类的城市扩张组团结构识别结果与区域实际情况具有较高的吻合性,聚类结果在多次实验中具有稳定性。

4 结论与展望

本文研究了自组织双重空间聚类算法,设计了“空间约束优先”聚类和“属性约束优先”2个子过程,将2类结果融合获取更加客观和稳定的聚类结果。结果表明,自组织双重空间聚类算法,在城市扩张组团结构识别中是有效的,聚类结果较为合理,且在较大规模样本聚类中具有稳定性。许多高维空间数据分析问题可使用双重空间聚类算法进行求解,如综合应用光谱、纹理和形状信息的遥感影像非监督分类等。今后,需深入探讨此方法在该类问题中应用的效果。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Lin C R, Liu K H, Chen M S.Dual clustering: Integrating data clustering over optimization and constraint domains[J]. IEEE Trans. Knowledge and Data Engineering, 2005,17(5):628-637.

[2]
Jiao L M, Liu Y L.Research on self-organizing clustering of spatial points[C]. Proceedings of SPIE Vol.6751, the 15th International Conference on Geoinformatics, Nanjing, 2007:5.

[3]
Chawla S, Shekhar S.Modeling spatial dependencies for mining geospatial data: An introduction[A]. In: Miller H J, Han J W (eds.). Geographic Data Mining and Knowledge discovery (GKD)[M]. Boca Raton, FL: Taylor and Francis, 2001.

[4]
Han J, Kamber M, Tung A K H. Spatial clustering methods in data mining: A survey[A]. In: H. Miller H J, Han J W (eds.). Geographic Data Mining and Knowledge Discovery[M]. Boca Raton, FL: Taylor and Francis, 2001.

[5]
Halkidi M, Batistakis Y, Vazirgiannis M.On Clustering Validation Techniques[J]. Journal of Intelligent Information Systems, 2001,17(2-3):107-145.

[6]
Tai C H, Dai B R, Chen M S.Incremental clustering in geography and optimization spaces[C]. Proceedings of PAKDD’07, 2007:272-283.

[7]
Zhang B, Yin W J, Xie M, et al.Geo-spatial clustering with non-spatial attributes and geographic non-overlapping constraint: A penalized spatial distance measure[C]. Proceedings of PAKDD'07, 2007:1072-1079.

[8]
Wang X, Hamilton H J.DBRS: A density-based spatial clustering method with random sampling[C]. Proceedings of the 7th PAKDD, Seoul, Korea, 2003:563-575.

[9]
Zhou J G, Guan J H, Li P X.DCAD: A dual clustering algorithm for distributed spatial databases[J]. Geo-spatial Information Science, 2007,10(2):137-144.

[10]
Henriques R, Bacao F, Lobo V.Exploratory geospatial data analysis using the GeoSOM suite[J]. Computers, Environment and Urban Systems, 2012,36:218-232.

[11]
李光强,邓敏,程涛.一种基于双重距离的空间聚类方法[J].测绘学报,2008,37(4):484-488.

[12]
周翠竹,朱建军,石岩.一种基于双重距离约束的多层次空间聚类方法[J].测绘科学,2014,39(10):98-101.

[13]
刘启亮,邓敏,石岩,等.一种基于多约束的空间聚类方法[J].测绘学报,2011,40(4):509-516.

[14]
Cao F, Ge Y, Wang J F.Optimal discretization for geographical detectors-based risk assessment[J]. GIScience & Remote Sensing, 2013,50(1):78-92.

[15]
Wang J F, Li X H, Christakos G, et al.Geographical detectors-based health risk assessment and its application in the neural tube defects study of the Heshun Region, China[J]. International Journal of Geographical Information Science, 2010,24(1):107-127.

[16]
Jiao L M, Liu Y L, Zou B.Self-organizing dual clustering considering spatial analysis and hybrid distance measures[J]. Science in China-Earth Science, 2011,54(8):1268-1278.

[17]
Liu X P, Li X, Chen Y M, et al.A new landscape index for quantifying urban expansion using multi-temporal remotely sensed data[J]. Landscape Ecology, 2010,25:671-682.

Options
Outlines

/

〈 〉