A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes——Identifying City Commercial Center
-
摘要: 针对Delaunay三角网空间聚类存在的不足，提出一种顾及属性空间分布不均的空间聚类方法。首先将Delaunay三角网空间位置聚类作为约束条件，采用广度优先搜索方法，以局部参数"属性变化率"作为阈值识别非空间属性相似簇的聚类过程。以城市商业中心为例，验证了该方法能够更客观地识别非空间属性相似的簇，且自适应属性阈值可以满足不同聚类需求，为城市商业中心等空间实体的提取提供了一种有效方法。
-
关键词:
- 空间聚类 /
- Delaunay三角网 /
- 属性空间分布不均 /
- 属性阈值 /
- 城市商业中心
Abstract: Spatial clustering is an important tool for spatial data mining and spatial analysis. It is important for the clustering results in many applications to meet the requirement that spatial objects in the same cluster are similar in both the spatial and the attribute domains. To solve the problems of existing methods based on Delaunay triangulation, this paper proposes a spatial clustering method considering uneven distribution of non-spatial attributes. The proposed algorithm involves two main steps:the first is to construct spatial proximity relationships, and the second is to cluster spatial objects with similar attributes. Delaunay triangulation with edge length constraints is first employed to construct spatial proximity relationships among objects. To obtain satisfied results in spatial clustering with attribute similarity, the breadth first traverse (BFT) clustering algorithm is used in accordance with variation rate of attribute to adapt to the local change information of attribute distribution. The performance of the proposed algorithm was evaluated experimentally through comparison with one of the leading state-of-the-art alternatives:multi-constraints algorithm. The results show that our method outperforms the comparative algorithm as attributes are unevenly distributed in space, and provides a quantitative research method in city commercial center extraction. The effectiveness and practicability of the proposed algorithm illustrates three advantages of our algorithm:i) it can reflect the tendency of the entity attribute in the spatial distribution; ii) it can meet the requirement that attributes are unevenly distributed in space; iii) it can discovery clusters with arbitrary shape and is robust to outliers. -
空间聚类分析是空间数据挖掘与知识发现的重要内容, 能够发现空间实体的空间集聚模式, 揭示空间实体的分布规律。空间聚类分析进一步结合空间实体的非空间属性在空间上的分布与差异, 对于解释复杂的地理现象具有重要的意义[1]。Delaunay三角网是空间邻近关系表达[2, 3]和空间聚类[4-6]的一种有效工具。现有Delaunay三角网空间聚类方法主要是一体化法[7, 8]和空间位置上的非空间属性相似性聚类方法。这类方法将空间坐标和非空间属性数据加权融合构造距离函数, 将空间位置和属性特征纳入统一的空间距离测度[9, 10], 虽然能够简化变量提高效率, 但由于空间位置和非空间属性之间的不可比性[11]和属性阈值难以准确获得, 影响了聚类方法的可操作性。第二类方法首先考虑实体的空间邻近性, 再加入非空间属性约束, 聚类结果精度较高, 能够满足空间数据分布的分异特性, 但属性阈值采用的是全局参数[12, 13], 实质上假设了空间实体分布的均匀性, 如文献[12]和文献[14]将非空间属性阈值设为最邻近实体非空间属性差异的平均值, 难以满足非空间属性分布不均匀的地理现象(如城市商业中心), 有可能将局部相似的对象划入到噪声簇或者其他聚类簇中, 导致聚类精度降低。针对上述问题, 本文提出了一种顾及属性空间分布不均的空间聚类方法。
1 考虑属性空间分布不均的空间聚类方法
本文提出的空间聚类方法首先进行空间位置聚类, 再在此基础上顾及非空间属性聚类。
1.1 空间位置聚类
采用文献[15-16]结合的聚类策略, 分别对Delaunay三角网施加整体约束和局部约束, 具体表达如下。
定义1 给定一个空间数据集D, 包含对象生成的Delaunay三角网表示为DT。针对任一对象P, 与其直接相连的对象表示为DN(P), Lmean(P)是P与DN(P)相连的边长均值, 表示为:
$$ {L_{{\rm{mean}}}}\left( P \right) = \frac{1}{{d\left( P \right)}}\sum\nolimits_{i = 1}^{d\left( P \right)} {\left| {{e_i}} \right|} $$ (1) 式中, d(P)表示对象P直接邻近对象的个数；|ei|表示P与DN(P)相连的边长。
定义2 LSD(P)是对象P与DN(P)相连边长的标准差, 表示为:
$$ \begin{array}{l} {L_{{\rm{SD}}}}\left( P \right) = \\ \;\;\sqrt {\frac{{\sum\nolimits_{i = 1}^{d\left( P \right)} {{{\left( {{L_{{\rm{mean}}}}\left( P \right) - \left| {{e_i}} \right|} \right)}^2}} }}{{d\left( P \right)}}} \end{array} $$ (2) Lmean(P)和LSD(P)两个指标都只反映了点的局部变化, 无法满足不同密度的空间簇。
定义3 全局性判断GSD是DT内所有对象LSD(P)的平均值, 表示为:
$$ {G_{{\rm{SD}}}} = \frac{1}{N}\sum\nolimits_{i = 1}^N {{L_{{\rm{SD}}}}\left( P \right)} $$ (3) 式中, N表示空间数据集D所有对象的个数。
定义4 整体边长约束。当|ei|大于Lmean(P)加GSD时, ei被视为长边, 表示为:
$$ {L_{{\rm{Edge}}}}\left( P \right) = \left\{ {{e_i}\left| {\left| {{e_i}} \right| > {L_{{\rm{mean}}}}\left( P \right) + {G_{{\rm{SD}}}}} \right.} \right\} $$ (4) 如果网内任一对象P与DN(P)相连的边长长度大于或等于长边长度, 则将其删除。
定义5 局部边长约束。在完成整体边长约束的基础上, Delaunay三角网内依然存在若干不一致的边, 针对对象P进一步施加局部边长约束准则:
$$ S = \left( {F\left( P \right)\left| {F\left( P \right) = \frac{{{L_{{\rm{SD}}}}\left( P \right)}}{{{L_{{\rm{mean}}}}\left( P \right)}},F\left( P \right) \le \gamma } \right.} \right) $$ (5) 式中, F(P)表示对象P邻域内的紧凑程度, F(P)越小该邻域越紧凑, 该参数能够探测到异常的“短边”和“长边”；γ表示紧凑度阈值, 采用文献[15]启发式方法确定γ, 连接所有F(P)≤γ的点及其邻域。
1.2 非空间属性聚类
通常情况下属性空间分布是非均匀的, 为适应复杂的属性空间分布情况, 应要顾及非空间属性相似性的局部变化信息。为此, 给出以下定义。
定义6 属性密度。空间位置聚类后获得Sub_DT空间邻近图, 针对任一对象P, 与其直接相连的全部对象包括自身表示为Sub_DN(P), 空间对象P的属性密度 $\rho \left( P \right) = \frac{{{l_{{\rm{sd}}}}/{l_{{\rm{mean}}}}}}{N}$ , 其中, ${l_{{\rm{mean}}}}\left( P \right) = \frac{{\sum _{i = 1}^K{\rm{Sub}}\_{D_N}{{\left( P \right)}_i}.a}}{K},{\rm{ }}K$ 表示Sub_DN(P)的个数, Sub_DN(P)i.a表示Sub_DN(P)第i个对象的非空间属性值； ${l_{{\rm{sd}}}}\left( P \right) = \sqrt {\sum _{i = 1}^K\left( {{\rm{Sub}}\_{D_N}{{\left( P \right)}_i}.a - {l_{{\rm{mean}}}}\left( P \right)} \right)/K} $ 。lsd/lmean是一个相对参数, 能够比较量纲不同或者平均值差别较大的`两组数据的离散度, 其值越小说明该对象属性离散度越小；N表示DN(P)的个数, 可以用来表示对象的邻域密度大小；ρ(P)既考虑了对象直接邻域内的属性离散度, 又顾及了对象的邻域密度大小, 离散度小且密度大的对象属性密度越大, 属性空间分布越紧凑。
定义7 聚类中心点。在Sub_DT邻近图中, CP表示聚类中心点, 表示为:
$$ {C_P}\left( P \right) = \min \left( {\rho \left( P \right)} \right) $$ (6) 计算所有对象ρ(P)值, 按照升序排列, 取最小值作为聚类中心点。聚类中心不是固定的, 当一个聚类簇形成时, 在所有未被聚类的对象中, 按照上述定义重新选择中心点。
定义8 直接邻居。给定一个对象P, 存在一个对象Q∈DN(P), 则Q是P的直接邻居。
定义9 间接邻居。如果存在一个对象链P1, P2, …, Pn-1, Pn, 满足Pn仅属于DN(Pn-1), Pk属于{DN(P)k-1∩DN(Pk+1), 1 < k < n}, P2仅属于DN(P1), 那么P3, P4, …, Pn是P1的间接邻居。
定义10 属性变化率。设类A已有m个对象{P1, P2, …, Pm}, 若存在一个对象Q要加入到类A, 则必须满足：
$$ {\rm{dist}}\left( {Q.a,v} \right) \le k{S_D} $$ (7) 式中, Q.a表示对象Q的非空间属性值；v表示{P1.a, …, Pm.a, Q.a}的均值；SD表示类{P1.a, …, Pm.a, Q.a}的标准差, 反映待划分对象与已知空间簇质心的偏离程度；dist(Q.a, v)表示空间对象与聚类集合之间的差异, 采用欧氏距离进行度量, 针对多维非空间属性要归一化处理。当对象Q满足式(7) 时, Q可以加入到类A中。
定义11 聚类。给定一个聚类中心点P, 根据属性变化率按照广度优先遍历方法搜寻该对象的直接邻居和间接邻居, 直到没有新的对象加入, 一个聚类簇形成。
定义12 噪声。给定一个对象P, 如果P不属于任何簇, 认定P为噪声。
2 聚类阈值分析与算法实现
2.1 聚类阈值分析
如果Sub_DT中非空间属性分布不均匀, 采用全局参数聚类有可能将局部相似的对象划入噪声簇中或者其他簇中。以图 1(a)数据为例, 原始数据可分为两个簇C1和C2, 两簇的属性空间分布不均匀。若采用多约束聚类方法[13]可能得到两种结果：① 只能发现簇C1, 簇C2被划分为噪声点, 如图 1(b)所示；② 当数据集中存在明显的异常值时, 簇C1和簇C2会合并成一个类, 如图 1(c)所示。
本文提出的属性变化率能够描述对象间的相对变化信息, 可以同时满足属性空间分布不均匀和均匀两种情况。此处k是控制参数, 用于调节空间对象与聚类集合的偏离程度, k值越大属性变化率的敏感性越低。为了保证参数k能够自动地适应不同的聚类需求, 引入了最优分割指数(partitioning best method, PBM)[17]。PBM指数能够满足紧密性与分离性的聚类准则, 指数越大聚类结果越可靠, 具体为:
$$ {\rm{PBM}} = {\left( {\frac{1}{{{N_C}}}\frac{{{E_1}}}{{{E_{{N_C}}}}}{D_{{N_C}}}} \right)^2} $$ (8) $$ {E_{{N_C}}} = \sum\nolimits_{i = 1}^{{N_C}} {{E_i}} ,{E_i} = \sum\nolimits_{j = 1}^{{N_i}} {\left\| {{x_j} - {v_i}} \right\|} $$ (9) $$ {D_{{N_C}}} = \max \sum\nolimits_{i,j = 1}^{{N_C}} {\left( {\left\| {{v_i} - {v_j}} \right\|} \right)} $$ (10) 式中, NC表示簇的数量；Ni表示簇Ci中实体数量；vi表示簇i的质心；Ei表示簇Ci的内部距离(簇内所有空间对象到其质心的距离之和)；E1表示数据集只分为一类的聚类内部距离；ENC表示数据集分为NC个簇的聚类内部距离；DNC表示空间簇间的分离度, 随NC增大而增大, 最大值为数据集中最远两个簇的质心距离。
以图 2(a)的模拟数据为例阐述上述非空间属性聚类过程, 图 2中结点的属性密度值按照升序排序为(v4, v3, v1, v2, v5, v6, v12, v11, v8, v10, v7, v9), 以v4为聚类中心点按照ρ(P)升序访问v4的直接邻居{v3, v1, v5, v2, v6}, PBM值最大时属性变化率中k取1.8, {v4, v3, v1, v5, v2, v6}可以形成一个初始簇, 将{v3, v1, v5, v2, v6}作为初始点按照上述方式搜索符合阈值条件的邻居, 最终得到一个簇, 如图 2(b)所示。聚类1为{v4, v3, v1, v5, v2, v6, v8}在剩余未聚类的对象中, 以v12为聚类中心点, 按照广度优先遍历的方法聚类, 得到最后的结果, 如图 2(c)所示。聚类2为{v12, v13, v10, v11, v7, v9}
2.2 算法实现
本文方法采用“先空间后属性”的聚类策略, 具体步骤如下。
1) 构建Delaunay三角网并对其施加边长约束, 删除不一致边, 得到对象间的空间邻近关系。
2) 计算每个对象的属性密度, 对Delaunay三角网内每个对象属性密度进行升序排序。
3) 非空间属性聚类。首先选取属性密度最小值作为初始聚类中心；然后按照广度优先遍历方法搜索该对象的直接邻居, 将符合阈值的对象聚类合并, 并标识为已聚类；依次循环搜寻该对象的间接邻居, 向外不断扩散, 将符合阈值的对象加入簇中, 直到没有新对象加入, 一个聚类簇形成。最后对于未被标识聚类的对象, 迭代步骤1) ~3), 遍历完所有对象, 聚类结束, 没有被标识到任何一类簇的对象视为噪声。
3 实验例证
本文以城市商业中心提取为例来验证方法的可行性, 利用Visual Studio 2010 C#环境结合ArcEngine组件二次开发实现。采用的数据为2011年扬州市中心城区商业用地现状图, 商业用地图斑数为735个, 如图 3(a)所示。城市地价直接决定不同商业类型的选址和布局[18, 19], 本文以扬州市的商业用地价格为属性数据进行实证研究。
![]()
图 3 扬州市商业用地分布情况及商业用地离散点群Figure 3. Commercial Land Distribution and its Discrete Points of Yangzhou City首先将面状单元的商业地块抽象成离散点群(图 3(b))并构建Delaunay三角网, 对三角网进行整体边长约束和局部边长约束(γ=0.463 8), 其具体过程如图 4(a)、4(b)所示, 得到空间位置聚类结果(图 4(b))。由于篇幅限制, 图 4(a)和图 4(b)给出了聚类结果的主体部分。
![]()
图 4 顾及空间位置的Delaunay三角网聚类过程Figure 4. Delaunay Triangulation Clustering Based on Spatial Proximity in Commercial Discrete Points将商业用地价格归一化到[0, 10]区间内, 采用多约束聚类方法[13]和本文方法(k=1.4, k=1.7, k=2.0) 分别进行非空间属性聚类, 得到图 5的聚类结果。
![]()
图 5 不同方法的聚类结果对比Figure 5. Comparison of the Clustering Results Using Different Methods从图 5可以看出, 当属性变化率k=1.4时, 聚类数目、均值同多约束方法相似, 两者聚类效果整体一致, 也证明了本文方法的有效性。但多约束方法的属性阈值采用的是一种全局参数, 导致若干相似的簇无法识别, 被划分成孤立点或噪声, 因此其孤立点个数是最多的；当k=1.4时, 聚类阈值较小, 聚类数目也会增多, 可能导致簇间分离性不明显；随着k值不断变大, 当k=2.0时, 聚类阈值较大, 聚类数目也会减少, 但这有可能会使簇内对象属性值出现较大差异。为了确定合适的k值, 采用PBM值评价出最可靠的聚类结果, 图 6显示了不同k值PBM的取值情况。
当k取1.6时, PBM值最大, 计算出k=1.6时每个聚类的均值, 据此将扬州市商业用地分为4个等级：0.245 0~3.246 7, 3.246 8~4.940 0, 4.940 1~7.063 3, 7.063 4~9.797 3, 将分级范围7.063 4~9.797 3界定为扬州市商业中心, 如图 7(a)所示, 黑色圆圈即为聚类的城市商业中心。
![]()
图 7 扬州城市商业中心提取结果对比Figure 7. Comparison Between Result of City Commercial Centers Extraction and Actual Situation in Yangzhou1996年扬州市城市中心体系规划包括两个城市主中心(文昌阁商圈与河东商务中心), 一个城市副中心(西部副中心), 将城市商业中心提取结果与扬州市城市空间格局(1996~2010) (图 7(b))进行对比分析, 区域1、2、3在1996~2010年间稳步发展, 已形成一定的商业规模。另外, 2011年扬州市进行了行政区划调整, 江都撤市并区, 图 7(a)中提取的商业中心4表示江都城区中心。城市商业中心的识别可以为城市空间结构分析和未来城市规划提供必要的信息支持。
4 结语
本文方法能够顾及实体间空间位置与非空间属性相似性的局部变化信息, 更客观、准确地识别非空间属性相似的簇。属性密度、属性变化率的定义和广度优先聚类过程都兼顾了属性空间分布不均的情况, 能够适应复杂的属性空间分布情况和输出相对稳定的聚类结果。与现有的Delaunay三角网空间聚类方法相比, 本文方法具有在属性空间分布不均匀的情况下能够顾及属性分布的局部信息, 满足属性空间分布不均匀和均匀两种情况的优点。本文方法采用PBM值引导参数k的选取, 可以自动地适应不同聚类需求, 得到可靠的聚类结果。进一步的研究内容主要集中在高维数据相似性度量及其空间聚类方法上。
-
![]()
图 3 扬州市商业用地分布情况及商业用地离散点群
Figure 3. Commercial Land Distribution and its Discrete Points of Yangzhou City
![]()
图 4 顾及空间位置的Delaunay三角网聚类过程
Figure 4. Delaunay Triangulation Clustering Based on Spatial Proximity in Commercial Discrete Points
![]()
图 5 不同方法的聚类结果对比
Figure 5. Comparison of the Clustering Results Using Different Methods
-
[1] 邓敏, 刘启亮, 李光强, 等.空间聚类分析及应用[M].北京:科学出版社, 2011:2-5 Deng Min, Liu Qiliang, Li Guangqiang, et al. Spatial Clustering Analysis and its Application[M].Beijing:Science Press, 2011:2-5
[2] Kang I S, Kim T, Li K J. A Spatial Data Mining Method by Delaunay Triangulation[C]. The 5th International Workshop on Advances in Geographic Information Systems, Las Vegas, USA, 1997
[3] Okable A, Boots B, Sugihara K, et al. Spatial Tessellations:Concepts and Applications of Voronoi Diagrams[M]. Hoboken:John Wiley & Sons, Inc, 2009
[4] Eldershaw C, Hegland M. Cluster Analysis Using Triangulation[J]. Computational Techniques and Applications, 1997:201-208 https://www.researchgate.net/publication/2279990_Cluster_Analysis...
[5] Kolingerová I, Alik B. Reconstructing Domain Boundaries Within a Given Set of Points, Using Delaunay Triangulation[J]. Computers & Geosciences, 2006, 32(9):1310-1319 https://www.sciencedirect.com/science/article/pii/S009830040500275X
[6] Estivill-Castro V, Lee I. Multi-level Clustering and its Visualization for Exploratory Spatial Analysis[J]. GeoInformatica, 2002, 6(2):123-152 doi: 10.1023/A:1015279009755
[7] Deng M, Liu Q, Li G, et al. Field-Theory Based Spatial Clustering Method[J]. Journal of Remote Sensing, 2010, 14(4):694-700 https://www.researchgate.net/publication/296337869_Field-theory...
[8] 周翠竹, 朱建军, 石岩.一种基于双重距离约束的多层次空间聚类方法[J].测绘科学, 2014, 39(10):98-101 http://www.geog.com.cn/CN/abstract/abstract39121.shtml Zhou Cuizhu, Zhu Jianjun, Shi Yan. A Multi-level Spatial Clustering Based on Distance Constraints[J]. Science of Surveying and Mapping, 2014, 39(10):98-101 http://www.geog.com.cn/CN/abstract/abstract39121.shtml
[9] Mundur P, Rao Y, Yesha Y. Keyframe-Based V-ideo Summarization Using Delaunay Clustering[J]. International Journal on Digital Libraries, 2006, 6(2):219-232 doi: 10.1007/s00799-005-0129-9
[10] 邓敏, 彭东亮, 刘启亮, 等.一种基于场论的层次空间聚类算法[J].武汉大学学报·信息科学版, 2011, 36(7):847-852 http://ch.whu.edu.cn/CN/abstract/abstract589.shtml Deng Min, Peng Dongliang, Liu Qiliang, et al. A Hierarchical Spatial Clustering Algorithm Based on Field Theory[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7):847-852 http://ch.whu.edu.cn/CN/abstract/abstract589.shtml
[11] 焦利民, 洪晓峰, 刘耀林.空间和属性双重约束下的自组织空间聚类研究[J].武汉大学学报·信息科学版, 2011, 36(7):862-866 http://ch.whu.edu.cn/CN/abstract/abstract608.shtml Jiao Limin, Hong Xiaofeng, Liu Yaolin. Self-organizing Spatial Clustering Under Spatial and Attribute Constraints[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7):862-866 http://ch.whu.edu.cn/CN/abstract/abstract608.shtml
[12] 石岩, 刘启亮, 邓敏, 等.融合图论与密度思想的混合空间聚类方法[J].武汉大学学报·信息科学版, 2012, 37(11):1276-1280 http://ch.whu.edu.cn/CN/abstract/abstract379.shtml Shi Yan, Liu Qiliang, Deng Min, et al. A Hybrid Spatial Clustering Based on Graph Theory and Spatial Density[J]. Geomatics and Information Science of Wuhan University, 2012, 37(11):1276-1280 http://ch.whu.edu.cn/CN/abstract/abstract379.shtml
[13] 刘启亮, 邓敏, 石岩, 等.一种基于多约束的空间聚类方法[J].测绘学报, 2011, 4:509-516 http://www1.informatik.uni-wuerzburg.de/fileadmin/10030100/... Liu Qiliang, Deng Min, Shi Yan, et al. A Novel Spatial Clustering Method Based on Multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2011, 4:509-516 http://www1.informatik.uni-wuerzburg.de/fileadmin/10030100/...
[14] Liu Q, Deng M, Shi Y, et al. A Density-Based Spatial Clustering Algorithm Considering Both Spatialproximity and Attribute Similarity[J]. Computers & Geosciences, 2012, 46:296-309 https://www.sciencedirect.com/science/article/pii/S0098300411004419
[15] Estivill-Castro V, Lee I. Argument Free Clustering for Large Spatial Point-Data Sets Via Boundary Extraction from Delaunay Diagram[J]. Computers, Environment and Urban Systems, 2002, 26(4):315-334 doi: 10.1016/S0198-9715(01)00044-8
[16] Liu D, Sourina O. Free-Parameters Clustering of Spatial Data with Non-uniform Density[C].Cybernetics and Intelligent Systems, 2004 IEEE Conference on, Singapore, 2004
[17] Pakhira M K, Bandyopadhyay S, Maulik U. Validity Index for Crisp and Fuzzy Clusters[J]. Pattern Recognition, 2004, 37(3):487-501 doi: 10.1016/j.patcog.2003.06.005
[18] 张文忠.经济区位论[M].北京:科学出版社, 2000:100-107 Zhang Wenzhong. Economic Location Theory[M].Beijing:Science Press, 2000:100-107
[19] Battaglia F, Borruso G, Porceddu A. Real Estate Values, Urban Centrality, Economic Activities. A GIS Analysis on the City of Swindon (UK)[M]. Heidelberg:Springer Berlin, 2010
-
期刊类型引用(4)
1. 朱杰，郑加柱，陈红华，杨静，胡平昌，陆敏燕. 结合POI数据的南京市商业中心识别与集聚特征研究. 现代测绘. 2022(06): 34-39 . 
百度学术
2. 金澄，安晓亚，陈占龙，马啸川. 矢量居民地多边形多级图划分聚类方法. 武汉大学学报(信息科学版). 2021(01): 19-29 . 百度学术
3. 张铭龙，何贞铭. 基于因子分析法的城市商业中心抽取研究. 地理空间信息. 2021(08): 58-60+64+5 . 百度学术
4. 李卫东，张铭龙，段金龙. 基于POI数据的南京市空间格局定量研究. 世界地理研究. 2020(02): 317-326 . 百度学术
其他类型引用(3)
下载:
计量
- 文章访问数: 1434
- HTML全文浏览量: 208
- PDF下载量: 397
- 被引次数: 7
