留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例

朱杰 孙毅中 陈律余 周卫 孟耀伟

朱杰, 孙毅中, 陈律余, 周卫, 孟耀伟. 顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
引用本文: 朱杰, 孙毅中, 陈律余, 周卫, 孟耀伟. 顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
ZHU Jie, SUN Yizhong, CHEN Lvyu, ZHOU Wei, MENG Yaowei. A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes——Identifying City Commercial Center[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
Citation: ZHU Jie, SUN Yizhong, CHEN Lvyu, ZHOU Wei, MENG Yaowei. A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes——Identifying City Commercial Center[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590

顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例

doi: 10.13203/j.whugis20150590
基金项目: 

国家自然科学基金 41671392

国家自然科学基金 41371374

国家自然科学基金 41301405

公安部科技强警基础工作专项项目 2015GABJC39

详细信息
    作者简介:

    朱杰, 博士生, 主要从事空间数据表达与挖掘研究。Chu_Je@163.com

    通讯作者: 孙毅中, 博士, 教授。sunyizhong_cz@163.com
  • 中图分类号: P208

A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes——Identifying City Commercial Center

Funds: 

The National Natural Science Foundation of China 41671392

The National Natural Science Foundation of China 41371374

The National Natural Science Foundation of China 41301405

Special Program for Basic Research of Sci-tech Police of Ministry of Public Security 2015GABJC39

More Information
    Author Bio:

    ZHU Jie, PhD candidate, specializes in spatial data representation and mining. E-mail:Chu_Je@163.com

    Corresponding author: SUN Yizhong, PhD, professor. E-mail:sunyizhong_cz@163.com
图(7)
计量
  • 文章访问数:  1008
  • HTML全文浏览量:  126
  • PDF下载量:  388
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-14
  • 刊出日期:  2017-12-05

顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例

doi: 10.13203/j.whugis20150590
    基金项目:

    国家自然科学基金 41671392

    国家自然科学基金 41371374

    国家自然科学基金 41301405

    公安部科技强警基础工作专项项目 2015GABJC39

    作者简介:

    朱杰, 博士生, 主要从事空间数据表达与挖掘研究。Chu_Je@163.com

    通讯作者: 孙毅中, 博士, 教授。sunyizhong_cz@163.com
  • 中图分类号: P208

摘要: 针对Delaunay三角网空间聚类存在的不足,提出一种顾及属性空间分布不均的空间聚类方法。首先将Delaunay三角网空间位置聚类作为约束条件,采用广度优先搜索方法,以局部参数"属性变化率"作为阈值识别非空间属性相似簇的聚类过程。以城市商业中心为例,验证了该方法能够更客观地识别非空间属性相似的簇,且自适应属性阈值可以满足不同聚类需求,为城市商业中心等空间实体的提取提供了一种有效方法。

English Abstract

朱杰, 孙毅中, 陈律余, 周卫, 孟耀伟. 顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
引用本文: 朱杰, 孙毅中, 陈律余, 周卫, 孟耀伟. 顾及属性空间分布不均的空间聚类方法——以城市商业中心的提取为例[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
ZHU Jie, SUN Yizhong, CHEN Lvyu, ZHOU Wei, MENG Yaowei. A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes——Identifying City Commercial Center[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
Citation: ZHU Jie, SUN Yizhong, CHEN Lvyu, ZHOU Wei, MENG Yaowei. A Spatial Clustering Method Based on Uneven Distribution of Non-spatial Attributes——Identifying City Commercial Center[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1696-1702. doi: 10.13203/j.whugis20150590
  • 空间聚类分析是空间数据挖掘与知识发现的重要内容, 能够发现空间实体的空间集聚模式, 揭示空间实体的分布规律。空间聚类分析进一步结合空间实体的非空间属性在空间上的分布与差异, 对于解释复杂的地理现象具有重要的意义[1]。Delaunay三角网是空间邻近关系表达[2, 3]和空间聚类[4-6]的一种有效工具。现有Delaunay三角网空间聚类方法主要是一体化法[7, 8]和空间位置上的非空间属性相似性聚类方法。这类方法将空间坐标和非空间属性数据加权融合构造距离函数, 将空间位置和属性特征纳入统一的空间距离测度[9, 10], 虽然能够简化变量提高效率, 但由于空间位置和非空间属性之间的不可比性[11]和属性阈值难以准确获得, 影响了聚类方法的可操作性。第二类方法首先考虑实体的空间邻近性, 再加入非空间属性约束, 聚类结果精度较高, 能够满足空间数据分布的分异特性, 但属性阈值采用的是全局参数[12, 13], 实质上假设了空间实体分布的均匀性, 如文献[12]和文献[14]将非空间属性阈值设为最邻近实体非空间属性差异的平均值, 难以满足非空间属性分布不均匀的地理现象(如城市商业中心), 有可能将局部相似的对象划入到噪声簇或者其他聚类簇中, 导致聚类精度降低。针对上述问题, 本文提出了一种顾及属性空间分布不均的空间聚类方法。

    • 本文提出的空间聚类方法首先进行空间位置聚类, 再在此基础上顾及非空间属性聚类。

    • 采用文献[15-16]结合的聚类策略, 分别对Delaunay三角网施加整体约束和局部约束, 具体表达如下。

      定义1  给定一个空间数据集D, 包含对象生成的Delaunay三角网表示为DT。针对任一对象P, 与其直接相连的对象表示为DN(P), Lmean(P)是PDN(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|表示PDN(P)相连的边长。

      定义2   LSD(P)是对象PDN(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  全局性判断GSDDT内所有对象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)

      如果网内任一对象PDN(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)≤γ的点及其邻域。

    • 通常情况下属性空间分布是非均匀的, 为适应复杂的属性空间分布情况, 应要顾及非空间属性相似性的局部变化信息。为此, 给出以下定义。

      定义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, 存在一个对象QDN(P), 则QP的直接邻居。

      定义9  间接邻居。如果存在一个对象链P1, P2, …, Pn-1, Pn, 满足Pn仅属于DN(Pn-1), Pk属于{DN(P)k-1DN(Pk+1), 1 < k < n}, P2仅属于DN(P1), 那么P3, P4, …, PnP1的间接邻居。

      定义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为噪声。

    • 如果Sub_DT中非空间属性分布不均匀, 采用全局参数聚类有可能将局部相似的对象划入噪声簇中或者其他簇中。以图 1(a)数据为例, 原始数据可分为两个簇C1C2, 两簇的属性空间分布不均匀。若采用多约束聚类方法[13]可能得到两种结果:① 只能发现簇C1, 簇C2被划分为噪声点, 如图 1(b)所示;② 当数据集中存在明显的异常值时, 簇C1和簇C2会合并成一个类, 如图 1(c)所示。

      图  1  全局参数聚类结果

      Figure 1.  Clustering Results Based on Global Parameter

      本文提出的属性变化率能够描述对象间的相对变化信息, 可以同时满足属性空间分布不均匀和均匀两种情况。此处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  基于属性密度的广度优先聚类结果

      Figure 2.  Clustering Result Based on Breadth First Traverse

    • 本文方法采用“先空间后属性”的聚类策略, 具体步骤如下。

      1) 构建Delaunay三角网并对其施加边长约束, 删除不一致边, 得到对象间的空间邻近关系。

      2) 计算每个对象的属性密度, 对Delaunay三角网内每个对象属性密度进行升序排序。

      3) 非空间属性聚类。首先选取属性密度最小值作为初始聚类中心;然后按照广度优先遍历方法搜索该对象的直接邻居, 将符合阈值的对象聚类合并, 并标识为已聚类;依次循环搜寻该对象的间接邻居, 向外不断扩散, 将符合阈值的对象加入簇中, 直到没有新对象加入, 一个聚类簇形成。最后对于未被标识聚类的对象, 迭代步骤1) ~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的取值情况。

      图  6  不同k值PBM取值

      Figure 6.  PBM Value With the Change of Kvalue

      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 Yangzhou

      1996年扬州市城市中心体系规划包括两个城市主中心(文昌阁商圈与河东商务中心), 一个城市副中心(西部副中心), 将城市商业中心提取结果与扬州市城市空间格局(1996~2010) (图 7(b))进行对比分析, 区域1、2、3在1996~2010年间稳步发展, 已形成一定的商业规模。另外, 2011年扬州市进行了行政区划调整, 江都撤市并区, 图 7(a)中提取的商业中心4表示江都城区中心。城市商业中心的识别可以为城市空间结构分析和未来城市规划提供必要的信息支持。

    • 本文方法能够顾及实体间空间位置与非空间属性相似性的局部变化信息, 更客观、准确地识别非空间属性相似的簇。属性密度、属性变化率的定义和广度优先聚类过程都兼顾了属性空间分布不均的情况, 能够适应复杂的属性空间分布情况和输出相对稳定的聚类结果。与现有的Delaunay三角网空间聚类方法相比, 本文方法具有在属性空间分布不均匀的情况下能够顾及属性分布的局部信息, 满足属性空间分布不均匀和均匀两种情况的优点。本文方法采用PBM值引导参数k的选取, 可以自动地适应不同聚类需求, 得到可靠的聚类结果。进一步的研究内容主要集中在高维数据相似性度量及其空间聚类方法上。

参考文献 (19)

目录

    /

    返回文章
    返回