内嵌空间聚类算法的分区地理元胞自动机建模与应用

1、第 12卷 第 3期2010年 6月地 球 信 息 科 学 学 报journal o f geo 2in forma t ion sc iencevo l112 , no13j un1, 2010内嵌空间聚类算法的分区地理元胞自动机建模与应用柯新利 1 , 2 ,邓祥征 1 3( 1. 中国科学院地理科学与资源研究所 ,北京 100101; 2. 咸宁学院资源与环境科学学院 ,咸宁 437100 )摘要 : 传统的地理元胞自动机 ( geo2ce llu la r a u tom a ta; geoca )模型 ,大多采用统一的转换规则驱动元胞空间内的所有元胞进行演变 。然而 ,许多地理现象都

2、存在着空间异质性 ,统一的元胞转换规则忽略了空间异质性的存在 。针对 这一问题 ,本文提出了空间聚类的分区地理元胞自动机模型 ,采用空间聚类算法对元胞空间进行分区 ,对不同的分区分别求取转换规则 ,以此来提高地理元胞自动机的模拟精度 。以杭州市为案例区 ,采用本文提出的空间聚类的分区地理元胞自动机模型 ,对研究区 2000 - 2005年的城市用地变化进行了模拟 。结果表明 : 与采用统一转换规则的geoca 相比 ,引入空间聚类算法的分区 geoca 具有较高的模拟精度 ,尤其是在空间形态和整体结构上 ,具有较好的 模拟效果 。关键词 : 元胞自动机 ;空间聚类 ;分区 ;土地利用 ;模拟分

3、区的元 胞 转 换 规 则 , 驱 动 该 分 区 的 元 胞 进 行 演化 ,从而在一定程度上提高了地理元胞自动机模型 的模拟精度 。作为空间数据挖掘的重要技术 ,空间聚类能够 发现空间数 据 隐 含 的 知 识 和 规 律 , 包 括 空 间 实 体的分异规律 、凝聚趋势和发展变化趋势等 。因此 , 可以采用空间聚类方法对地理现象及其变化进行 分析 ,发现地理现象及其变化的空间差异性 ,为地 理元胞 自 动 机 模 型 元 胞 空 间 的 分 区 提 供 方 法 支 撑 。1 引言元胞自动机模型 ( ce llu la r a u tom a ta) ,提供了研究复杂自适应系统的框架 ,可

4、以模拟由大量简单元 素组成的宏观结构 ,具有简化的特征 1 。地理元胞自动机 ( geo2ce llu la r a u tom a ta, geoca )具有模拟复 杂系统时空演化过程的能力 ,在地理学研究中具有技术优势 2 。近年来 ,越来越多的学者利用元胞自动 机 模 拟 复 杂 的 地 理 现 象 , 取 得 了 许 多 研 究 成果 3 - 12 。目前 ,地理元胞自动机模型在模拟大多数地理 现象时 ,常常假设在整个元胞空间内所有元胞 , 都 按相同的转换规则演化 ,采用统一的转换规则驱动 地理元胞自动机模型中所有元胞的演化来模拟地 理现象的变化 ,忽略了被模拟地理现象变化的空间 异

5、质性 ,从而影响了地理元胞自动机模型的模拟精 度 。针对这一问题 ,本文提出了空间聚类的分区地 理元胞自动机模型 ,采用空间聚类方法对元胞空间 进行分区 ,使每一个分区内具有相对一致的元胞转 换规则 , 然后采用 c510 决策树算法分别获取不同2 内 嵌空 间 聚 类 算 法 的 分 区 地 理 元胞自动机模型211k2m ean s空间聚类算法空间聚类是空间数据划分或分组处理的重 要 手段和方法 。它根据研究对象的空间距离将研究 对象划分到若干个子集中 ,使得相同子集中各元素 间差别最小 ,而不同子集中各元素间差别最大 。距 离是空间聚类的依据和基础 ,空间聚类中常用的距收稿日期 : 20

6、09 - 10 - 20;修回日期 : 2010 - 03 - 17.基金项目 : 国家自然科学基金项目 ( 70873118 ) ;国家重点基础研究发展计划 ( 2010cb950904 ) ; 湖北省自然科学基金项目( 2009cdb342) ;湖北省教育厅人文社会科学项目 ( 2010q130 ) 。作者简介 : 柯新利 ( 1977 - ) ,湖北天门人 ,博士 ,讲师 ,现为中国科学院地理科学与资源研究所博士后 ,主要从事地理模拟 、 土地利用变化研究 。 e2m a il: kexl igsn rr. ac. cn3 通讯作者 : 邓祥征 ( 1971 - ) ,男 ,博士 ,副研

7、究员 ,研究方向为区域环境变化 、土地系统变化与效应 。e2m a il: dengxz. ccap igsn rr. ac. cn离有欧几里得距离 、曼哈顿距离和明考斯距离等 。其中 ,最常用的是欧几里得距离 。k2m ean s算法是应用广泛的空间聚类算法 , 它 的基本原理是 : 首先 , 由用户确定所要聚类的数目k,并随机选择 k个对 象 , 每 一个 对象 代表 一 个类(簇 )的均值或中心 ,对剩余的每个对象 ,根据其与 各簇中心的距离 , 将它赋给最近的簇 。然后 , 重新 计算每个簇的平均值形成新的聚类中心 ,这个过程重复进行 ,直到准则函数收敛为止 13 。k负责空间数据的处

8、理 、转换与显示 ; 空间聚类模块实现 k2m ean s空间聚类算法 ,以及根据聚类结果将 土地利用数据归入每一个类别 ; c5. 0 决策树模块的功能是实现各类转换规则的挖掘 ; 地理元胞自动机 模型模块的功能是实现土地利用的模拟及对模拟 结果的精度评估 。空间数据挖掘的分区地理元胞自动机模型 的 建模过程 ,大致包括 5 个前后紧密联系的步骤 。首先 ,用于土地利用变化模拟的数据在 g is模块中经 过数据预处理 、对齐与裁剪等处理后 , 转换成空间 聚类模块可以识别和处理的数据 ; 其次 , 在空间聚 类模块中经过 k2m ean s算法进行空间聚类分析 ; 接 着 ,根据空 间 聚

9、类 的 结 果 对 土 地 利 用 数 据 进 行 分区 ,将分区得到的结果输出到 c5. 0 决策树模块 ; 然 后 ,利用 c5. 0 决策树算法挖掘每一个分区的元胞 转换规则 ,并将分区结果和各分区的转换规则输出 到地理元胞自动机模块中进行土地利用变化模拟 |e =p - m i |i = 1 pc i其中 , e 是所有研究对象的平方误差总和 , p为空间的点 , 即数据对象 , m i 是簇 ci 的平均值 。按照 这个准则生成的结果簇趋向于独立和紧凑 。2. 2 空间聚类的分区地理元胞自动机模型空间聚类的分区元胞自动机模型由 4 个模块 组成 : g is模块 、空间聚类模块 、c

10、510 决策树模块和地理元胞自动机模型模块 (图 1 ) 。其中 , g is模块并进行精度评估 ; 最后 , 将模拟结果送回到块显示 。g is模图 1 空间聚类的分区 geoca 建模流程f ig. 1 techn ica l flow of p a rtitioned geoca mode ling em bedded sp a tia l c lu ste r a lgo rithm的最小面积单元 , 某时刻 t元胞状态只可能是有限状态中的一种 ; s 为元胞状态 , 本研究中元胞状态只 有两种 , 即城市用地和非城市用地 ; n 为邻域 , 元胞 的邻域结构决定元胞的转换状态 ,最常

11、用的邻域结 构有 n eum ann 邻域和 moo re 邻域 , 本文采用 moo re 邻域 ; r 为转换规则 ,转换规则的定义是元胞自动机的核心 ,传统的转换规则只考虑邻域的影响 , 本文 中的转换规则综合考虑了邻域影响 、全局因素的影 响 ,以及扰动因素的影响 。本文选择杭州市为案例区 。杭 州市 地 处杭 嘉 湖 平 原 和 浙 西 丘 陵 山 地 的 连 接 地 带 , 全 市 面 积3 k2m ean s算法的 geoca 模拟应用3. 1 geoca 模拟分析元胞自动机是一种时间 、空间 、状态都离散 ,空 间相互作用和时间因果关系都为局部的网格动力学 模 型 , 具 有

12、模 拟 复 杂 系 统 时 空 演 化 过 程 的 能 力 2 。元胞自动机有四个基本要素 : 元胞 、状态 、邻 域和转换规则 ,可以用形式语言表示为 14 :ca = f ( c, s , n , r )式中 , ca 为元胞自动机 ; c 为元胞 , 是研究区域3期柯新利 等 :内嵌空间聚类算法的分区地理元胞自动机建模与应用36716 596 km2 ,其中 , 市 辖 区 3 068 km2 。其 辖 上 城 、下城 、拱 墅 、江 干 、西 湖 、滨 江 、萧 山 、余 杭 8 个 区 , 临 安 、富阳 、建德 3 个县级市 ,桐庐 、淳安 2个县 。本文选择的研究范围主要包括杭州

13、市城市规划的一主三 副区域 ,即主城 、下沙城 、江南城及临平城 (图 2) 。在不对模拟区域进行分区的情况下 ,本文采用c510决策树算法获取整个元胞空间的元胞转换规 则 ,并用这一转换规则驱动地理元胞自动机模型 ,对杭州市 2000年到 2005年的土地利用变化进行了 模拟 (结果如图 3所示 ) 。图 3 ( c)是在非分区的情况下 ,利用地理元胞自图 2 研究区域范围f ig. 2 cove rage of the ca se study a rea本文的数据包括研究区域 2000 年及 2005年两个时相 的 l and sa t tm / etm +遥 感 影 像 、交 通 数 据

14、 集 、地形数据 、人口数据集和水系数据 。遥感 影像 数据经过几何校正 、辐射校正 、边界裁剪 、监督分类及人工目视解译 、精度检验的一系列处理过程后 ,最后生成土地利用图层 。地形图经过数字化后生 成了 d em 数据 , 相应地 , 将交通数据集 、水系和人口等数据集经过处理后 , 分别生成了交通图层 、水 域图层和人口密度图层数据 , 并在此基础上 , 生成 道路距离栅格 、铁路距离栅格及水域距离栅格等数据 。在空间聚类的分区元胞自 动 机模 型中 , 首 先 ,根据期初土地利用数据和期末土地利用叠加得到 土地利用变化数据 , 其次 , 采 用 k2m ean s空 间 聚类算法对土地

15、利用变化数据进行空间聚类 ,用得到的空间聚类结果对期末土地利用的采样数据进行处 理 ,使得采样数据的每一点都落实到对应的聚类之中 ,然后 ,对每一聚类采用 c510 决策树算法进行元 胞转换规则的挖掘 ,用得到的元胞转换规则驱动元胞自动机模型进行土地利用变化的模拟 , 最后 , 对 模拟的结果进行精度评估 。如果精度能满足要求 , 则可以用于土地利用变化的预测 ; 否则 , 重复进行采样 ,直到模拟精度满足要求为止 。( 1 )非分区 ca 模拟与结果分析图 3 杭州市 2005年城市用地实际情况与非分区 geoca 模拟结果对比f ig. 3 r ea l u rban land u se

16、con tra sted w ith the sim u la ted u rban land u se u sing geoca mode ling in h angzhou c ity:( a) r ea l u rban land u se, 2005; ( b) sim u la ted u rban landu se, 2005; ( c) e rro rs of unp a rtitioned geoca mode ling动机模型模拟杭州市土地利用演变结果的误差图 。为了论述方便 ,本文定义了过模拟误差与欠模拟误 差两个概念 , 并在此基础上就模拟精度做了判定 。过模拟误差表达了

17、实际土地利用并没有由非城市 用地演变为城市用地 ,模拟结果却由非城市用地转变为了城市用地 (图 3 ( c)中的亮色部分 ) 。欠模拟 误差表达的是实际土地利用由非城市用地转变为了城市用地 ,但模拟结果却并没有由非城市用地转 变为城市用地 (图 3 ( c)中的深色部分 ) 。在这种设定情况下 ,对模拟精度的判断可以分 解如下五种情况进行讨论 。第一类情况是过模拟误差和欠模拟误差都存在 ,并且两种误差各自集中 分布 、彼此独立聚集 ; 第二类情况是以过模拟误差为主要特征 ,过模拟误差均匀分布 , 中间夹杂着一 定程度的欠模拟误差 ; 第三种情况是以欠模拟误差 为主要特征 ,欠模拟误差集中分布

18、, 中间夹杂少量均匀的过模拟误差 ;第四种情况是过模拟误差和欠模拟误差分布没有明显的空间特征 ,表现出随机分 布的模式 。第五种情况是过模拟误差和欠模拟误差都存在 ,并且在空间上都基本呈均匀分布 。 不难理解 ,由于模拟区土地利用变化存在显著的空间分异性特征 ,当采用统一的元胞转变规则模 拟整个区域土地利用变化情况时 ,就会产生如图 3 ( c)所示的呈区域规律性分布的误差 。因此 , 有必要对地理元胞自动机模型进行改进 ,采用局部元胞 转换规则代替统一的元胞转换规则 ,使其更符合土 地利用变化区域分异规律 。采用前面讨论的空间聚类 方法 , 首 先 , 我们 对杭州市 2000年和 2005

19、年的土地利用数据进行叠加 运算 ,得到杭州市 2000 年到 2005 年的土地利用变化图层 。然后 ,采用 k2m ean s算法对土地利用变化 图层进行空间聚类 ,得到研究区空间聚类结果 (图4 ) 。图 4 空间聚类结果f ig. 4 r e su lt of sp a tia l c lu ste r由图 4 可见 , k2m ean s空间聚类的结果与非分区地理元胞自动机模型模拟结果误差图中的人工 分类基本上是相对应的 ,这在一定程度上反映了利用 k2m ean s空间聚类算法提高土地利用 变 化模 拟精度的做法是有效的与合理的 。 在采用空间聚类的方法对元胞空间进行分区的基础上 ,

20、采用 c5. 0 决策树算法分别获取不同分区的元胞转换规则 ,以此驱动不同分区的元胞进行演化 ,得到杭州市 2005年土地利用模拟结果 (图 5) 。( 2 )分区geoca 模型模拟与结果分析图 5 地理元胞自动机模型模拟结果( a) 2005年实际城市用地( b)空间聚类 geoca 模拟结果f ig. 5 l and u se p a tte rn sim u la ted by geoca mode ling( a) r ea l u rban land u se, 2005; ( b) r e su lt of sp a tia l c lu ste r geoca mode lin

21、g3期柯新利 等 :内嵌空间聚类算法的分区地理元胞自动机建模与应用369由图 5可见 ,空间聚类的分区地理元胞自动机模型的模拟结果 ,更接近实际的土地利用总体结构 和形态 ,该模型的模拟结果在土地利用空间格局方面与实际土地利用空间格局更为接近 。最简单直观 的 方 法 , 也 是 最 常 用 的 地 理 元 胞 自 动机模型精度评估方法之一 。它通过逐像元对比地 理元胞自动机模型的模拟结果与实际的土地利用来衡量地理 元 胞 自 动 机 模 型 的 模 拟 精 度 , 通 常 采 用混淆矩阵进行精度评估 。本文采用混淆矩阵分 别对传 统 的 非 分 区 地 理 元 胞 自 动 机 模 型 和 空

22、 间 聚类的地理元胞 自 动 机 模型 进 行了 精度 评 估 (表1 ) 。3. 2 精度检验( 1 )逐点对比精度 逐点对比法是地理元胞自动机模型精度检验表 1 分区与非分区模拟精度的比较ta b. 1 c om pa r ison for the s im u la t ion a ccura cy of pa r t it ion ed an d un pa r t it ion ed geoca m ode l in g模拟结果 (元胞数 )精度 ( % )城市用地非城市用地非分区分区非分区分区非分区分区城市用地非城市用地98 79117 83098 794170 82718 006

23、147 86417 617148 25384. 5889. 2487. 3184. 8789. 2787. 45实际情况 (元胞数 )总精度由表 1可见 ,在空间聚类的分区地理元胞自动机模拟结果中 ,城市用地的准确率为 84. 87 % ,非城 市用地的模拟准确率为 89. 27 % ,总精度也高达 87.45 % ,可以满足城市用地变化的动态模拟 。与非分区地理元胞自动机模型相比 ,空间聚类的分区地理 元胞自动机模型模拟结果的逐点对比精度略有提 升 。( 2 )整体对比精度 为了衡量模拟结果的总体结构和形态 ,可采用紧凑度 、分形维和 mo ran i指数等 ,对地理元胞自动 机模型的模拟精

24、度进行评估 。mo ran i指数一般用 来描述空间的自相关性 。由于该指数可以反映集中和分散的程度 ,可用以衡量地理元胞自动机模型 模拟结果和实际情况在空间格局和整体形态方面 的接近程度 。因此 ,本文选用 mo ran i来度量模拟 结果和实际土地利用空间格局和整体形态的相似性 (表 2 ) 。表 2 杭州市 2005年实际土地利用图与模拟土地 利用图计算的 m oran i指数对比表ta b. 2 c om pa r ison ta b le of ca lcu la ted m ora l i ba sed on the rea l an d the s im u la ted lan

25、 d u se m a p s of han gzhou c ity in 2005 从 mo ran i指数来看 , 空间聚类的分区地理元胞自 动 机模 型模 拟 结果 的 mo ran i指 数与 杭 州 市2005 年实际土地利用的 mo ran i指数十分接近 ,因 此 ,可以认为基于空间聚类的分区地理元胞自动机模型模拟结果 ,能较好地反映土地利用变化的总体结构与形态 ,具有较好的整体性能 。与非分区地理 元胞自动机模型相比 ,空间聚类的分区地理元胞自 动机模型的模拟结果具有更接近实际情况的 mo ran i指数 ,模拟结果在土地利用结构和空间布局上表 现出较好的性能 。4 结论针对地

26、理元胞自动机模型的统一元胞转换 规则不能反映地理现象空间异质性的问题 ,本文提出 了采用分区转换规则替代统一转换规则的观点 ,采用空间聚类的方法将研究区域划分成不同的子区域 。在此基础上 , 对不同的分区采用 c5. 0 决策 树 方法 ,挖掘每一个子区域的元胞转换规则 。由于不 同的子区域具有相对一致的性质 , 因此 , 各分区的元胞转换规则可以较好地反映该区域的地理现象演变规律 。采用分区的元胞转换规则驱动地理元 胞自动机模型模拟区域土地利用变化可以获得较好的模拟效果 。利用本文提出的空间聚类的分区地理元胞 自 动机模型 ,对杭州市土地利用变化进行了模拟 。结土地利用实际土地利用图非分区c

27、a 模拟结果分区ca 模拟结果 mo ran i 0. 461 0. 508 0. 489 6 a lm e ida c m d , b a ttym , mon te iro a m v , e t a l. stocha s2 tic ce llu la r a u tom a ta mode ling of u rban l and u se d ynam 2 ic s j . comp u te r, environm en t and u rban system s,2003 , 27: 481 - 509. 7 黎夏 ,叶嘉安 . 基于神经网络的单元自动机 ca 模拟及真 实和优化

28、城市的模拟 j . 地理学报 , 2002, 57 ( 2 ) : 159 -166. 8 杨青生 ,黎夏 ,刘小平 . 基于 a gen t和 ca 的城市土地利 用变化研究 j . 地球信息科学 , 2005 , 7 ( 2 ) : 78 - 81. 9 杨青生 ,黎夏 . 基于支持向量机的元胞自动机及土地利 用变化模拟 j . 遥感学报 , 2006, 10 ( 6) : 836 - 846. 10 邓祥征 . 土地系统动态模拟 m . 北京 :中国大地出版 社 , 2008. 11 邓祥征 ,林英志 ,黄河清 . 土地系统动态模拟方法进展 j . 生态学杂志 , 2009 , 28 (

29、 10 ) : 2123 - 2129. 12 董婷婷 ,左丽君 ,张增祥 . 基于 ann 2ca 模型的土壤侵 蚀时空演化分析 j . 地球信息科学学报 , 2009, 11 ( 1 ) :132 - 138. 13 sheh roz s k, a hm ad a. c lu ste r cen te r in itia liza tion a lgo2 rithm fo r k - m ean s c lu ste ring j . pa tte rn r ecogn ition l e tte rs ( s0167 - 8655) , 2004, 25 ( 11 ) : 1293 -

30、1302. 14 刘耀林 ,刘艳芳 ,明冬萍 . 基于灰色局势决策规则的元胞自动机城市扩展模型 j . 武汉大学学报 . 信息科学 版 , 2004 , 29 ( 1 ) : 7 - 13.果表明 :采用逐点对比法进行精度评估时 , 空间聚类的分区地理元胞自动机模型 ,模拟结果的逐点对 比精度比非分区地理元胞自动机模型的模拟结果略有提升 ; 采用 mo ran i评估模拟结果与实际情况 的空间结构一致性时 ,空间聚类的分区地理元胞自 动机模型模拟结果 ,明显比非分区地理元胞自动机 模型 ,具有与实际情况更加接近的 mo ran i指数 ,这 说明空间聚类的分区地理元胞自动机模型模拟结果 ,能模

31、拟出更接近实际的土地利用结构和空间布 局 ,可获得更加真实的模拟结果 。参考文献 : 1 田光进 ,邬建国 . 基于智能体模型的土地利用动态模拟 研究进展 j . 生态学报 , 2008, 28 ( 9) : 4451 - 4459. 2 黎夏 ,叶嘉安 ,刘小平等 . 地理模拟系统 : 元胞自动机与 多智能体 m . 北京 :科学出版社 , 2007. 3 卢远 ,莫建飞 ,韦亮英 . 生态约束性城市扩展模型与应用 分析 以南宁市区为例 j . 地 球信息科学 , 2008 , 10( 6 ) : 710 - 715. 4 陈志强 ,陈健飞 . 福州城市用地变化的 ca 模型动态模拟 研究

32、j . 地球信息科学 , 2007, 9 ( 2 ) : 70 - 73. 5 b a tty m , x ie y c, sun z l. mode ling u rban d ynam ic s th rough g is2ba sed ce llu la r a u tom a ta j . comp u te rs, en2vironm en t and u rban system s, 1999 , 23: 205 - 233.pa r t it ion ed geo2c e llu la r a u tom a ta m ode ll in g em beddedspa t ia

33、l c lu ster a lgor ithmke x in li1 , d en g x iangzheng1 3( 1. institu te of geog raph ica l s ciences and n a tu ra l r esou rces r esea rch, cas , b eijing 100101, ch ina;2. s chool of r esou rces & environm en t s cience, x iann ing college, x iann ing 437000, ch ina)a b stra c t: a ll ce lls und

34、e r the unp a rtitioned geo2ce llu la r au tom a ta ( geoca ) mode ling evo lved acco rd ing the tran s2fe r p robab ility wh ich is dec ided by gene ric tran sfe r ru le fixed fo r the en tire region. howeve r, the re a lways exists sp a tia l he te rogene ity in mo st geograp h ica l p henom enon,

35、 and the se sp a tia l he te rogene itie s a re qu ite often igno red in gene ric unp a rtitioned geo2ce llu la r au tom a ta mode ling due to the gene ric tran sfe r ru le s a re emp loyed to d rive a ll ce lls to evo lve. the accu racy of unp a rtitioned geoca sim u la tion re su lt is lim ited be

36、cau se of the igno rance of sp a tia l he te rogene itie s in th is k ind of geoca mode ls. to ove rcom e th is d isadvan tage of unp a rtitioned geoca , a p a rti2 tioned geoca ba sed on sp a tia l c lu ste r is d iscu ssed in th is p ap e r. u nde r the p a rtitioned geoca mode ling fram e2 wo rk,

37、 ce llu la r sp ace is dep a rted in to seve ra l p a rtition s by sp a tia l c lu ste r, and then a se t of tran sfe r ru le s co rre2 spond ing to each p a rtition a re ca lcu la ted acco rd ingly. a nd then, tak ing h angzhou c ity a s a ca se, the pa rtitioned geoca mode ling ba sed on sp a tia l c lu ste r is emp loyed to sim u la te the land u se change in the p e riod be tween 2000 and 2005. in th is ca se study, the study a rea