知识发现及地理元胞自动机.pdf

中国科学 D 辑 地球科学 2004 34 9 865 872 865 SCIENCE IN CHINA Ser D Earth Sciences 知识发现及地理元胞自动机 黎 夏 中山大学地理科学与规划学院 广州 510275 叶嘉安 香港大学城市规划及环境管理研究中心 香港 摘要 提出了将数据挖掘技术应用于元胞自动机 CA 进行地理模拟的新方法 CA 具有很强的 模拟复杂系统的能力 CA 的核心是如何定义转换规则 但目前还没有很好定义转换规则的方法 主要是采用启发式的方法来定义转换规则 受主观因素影响很大 而且 这些转换规则基本是通 过数学公式来隐含表达 在反映复杂关系时有一定的局限性 利用数据挖掘技术从 GIS 和遥感数 据中发现知识 自动找到 CA 的转换规则 大大缩短了建模所需要的时间 并改善了模拟效果 关键词 知识挖掘 元胞自动机 地理模拟 地理信息系统 2003 09 22 收稿 2004 01 23 收修改稿 国家自然科学基金资助项目 批准号 40071060 E mail qplx 近年来 Cellular automata CA 已经被较多地应 用在地理现象的模拟中 特别是用于城市模拟 1 2 国内学者也较早地开展了有关工作 并在国内外刊 物上发表了许多有关城市 CA 的论文 3 7 CA 的中文 译法有多种 包括 元胞自动机 细胞自动机 和 单 元自动机 等 3 4 CA 用于地理现象模拟的例子包括 山火蔓延 8 动物群种数目的动态变化 9 城市系统 和土地利用的演变 1 2 优化城市形态的形成 3 6 可 持续土地利用规划 10 农田保护区自动生成 11 等 许多地理现象都属于复杂系统 无法利用数学 公式来对它们进行表达和模拟 研究表明 CA 是模 拟复杂系统十分有用的工具 12 城市系统正是应用 CA 进行模拟的最成功例子之一 1 2 6 Couclelis 13 较 早地进行了城市的 CA 模拟 她认为 CA 的模拟结果 可以作为各种真实城市的类比物 Batty等 1 也在城市 CA 方面进行了有影响的研究 他们开始是使用与 CA 类似的技术 即 diffusion limited aggregation DLA 来模拟建成区的扩张 后来 他们也采用了 起源于计算科学和生物学的 CA 进行城市模拟 1 转换规则是 CA 模型的核心 但定义这些规则往 866 中国科学 D 辑 地球科学 第 34 卷 SCIENCE IN CHINA Ser D Earth Sciences 往是十分繁琐的 学者们主要是采用启发式的方法 来定义转换规则 14 例如包括矩阵 2 多准则判断 15 和灰度 6 等方法 这些方法受主观因素影响很大 在 形式上相互有明显的差别 而且 这些转换规则大多 数都是隐含的 是通过数学公式来表达 如何确定公 式中的参数十分困难 为此 我们提出了利用训练神 经网络的方法来自动获取 CA 的参数值 7 16 从而减 少 CA 的不确定性 不足的是 神经网络方法属于黑 箱结构 用户不能清晰地知道模型运行的机制 对模 型参数的具体物理意义很难理解 上述这些方法都 是通过数学公式来表达转换规则 但数学公式在反映 复杂的关系时有很大的局限性 本文提出了利用数据挖掘技术 data mining 来自 动获取 CA 转换规则的新方法 数据挖掘技术已经被 应用于遥感专家系统的分类中 它能解决专家知识 获取的瓶颈难题 提高遥感的分类效率 最近 有些 学者也开始利用数据挖掘技术从 GIS 数据库中获取 知识 包括进行土壤分类的研究 17 CA 在地理学领域 应用时往往涉及到大量的空间数据 使用知识挖掘 技术将能大大提高 CA 的模拟能力 所获得的转换规 则无需通过数学公式来表达 能更方便和准确地描 述自然界中的复杂关系 目前还没有利用数据挖掘 技术来建立 CA 模型的研究报道 1 数据挖掘及地理元胞自动机 数据挖掘是从数据库中发现知识的技术 它是 针对知识获取的困难和不确定性而提出来的 可以 自动地从海量数据中挖掘出知识 具体的知识获取 过程是借助机器学习的算法来实现的 常用的机器 学习的算法有 ID3 C4 5 CART IB1 IB2 MPIL1 和 MPIL2 其中 Quinlan 18 所提出的C4 5算法最为广泛 使用 C4 5目前最新的版本为See5 C5 0 分别对应于 Window 和 Unix 这两个不同的操作平台 C4 5 系列是根据 信息增加的比值 来决定整 个决策树的生成 18 首先 假设有一训练数据集 S 它的任意一样品 s 隶属于类别 Cj 数据集 S 的平均信 息量 熵 根据下式计算 2 1 log k jj j freq CSfreq CS info S SS 1 其中 j freq CS 为 S 中属于类别 Cj的样品数目 S 为样品总数目 假设把 S分解为n 个 Si的子集 则分解后的平均 信息量为 1 n i xi i S infoSinfo S S 2 分解后信息增加值为 x gain Xinfo Sinfo S 3 为了防止产生过多的分解数目 要用split info X 对 gain X 进行标准化 Split info X 的计算如下 2 1 log n ii i SS splitinfo X SS 4 最后有 gainratio Xgain Xsplitinfo X 5 分类树在每个节点的分解必须满足熵的减少值 达到最大的条件 根据上面算法 利用计算机递归的 方法 反复寻找最佳的分解 从而生成决策树 利用 这个算法 可以从训练数据中自动获得规则 数据挖掘技术能有效地从 GIS 数据库中挖取出 地理知识 包括空间分布规律等 将数据挖掘技术与 地理元胞自动机结合 可以自动从观察数据中生成 模拟所需要的转换规则 并同时完成模型的纠正过 程 CA 的转换规则决定每个单元 cell 状态的转换 例如从农业用地变为城市用地 大多数的 CA 是采用 数学表达式 例如线性方程或 logistic 公式等 来隐含 地代表转换规则 而确定公式中的参数往往很困难 而采用数据挖掘的方法则能获取明确的转换规则 例如 规则 1 假如 土地利用类型 森林 或 湿地 则 禁止土地开发 置信度 0 85 规则 2 假如 土地利用类型 粮田 离市中心距离 16 则 该中心单元转变为城市用地 置信度 0 95 本文以城市模拟为例 从 GIS 和遥感自动挖掘 出 CA 的转换规则 图 1 利用两年的遥感图像来监 测城市增长的情况 转换规则主要是从这两年的遥 第 9 期 黎夏等 知识发现及地理元胞自动机 867 图 1 利用数据挖掘技术自动生成地理元胞自动机的转换规则 感图像上挖掘出来的 遥感图像的观测间隔 T 往往 比 CA 模拟的迭代间隔 t 大很多 只有观测间隔与 迭代间隔完成相同时 所获得的转换规则才能直接 使用 但现实中无法获得短至迭代间隔的观测数据 因为遥感的观测间隔往往是以年为单位的 另外 观 测间隔太短 无法掌握长期的动态趋势 将从 T 间隔内获得的转换规则应用于每次 CA 的迭代运算中 需要做一些调整 首先 CA 模拟在 T 间隔内迭代运行的次数 K 为 KTt 6 从遥感图像可以确定观测间隔 T 内的土地转 换量 Q0 由于 T t 在 t 间隔内只有一部分土 地的状态发生了转变 CA 在 t 间隔内的土地转换量 为 00 qQK 7 因此 除了利用从观测间隔获得的原始规则外 还需要采用如下的补充规则获得在迭代 t 中 CA 状态 的转变 假如 根据原始规则判断单元 x i j 应该转变为城市 用地 x i j 在迭代 t 1 中为非城市用地 且 0 则 x i j 在迭代 t 转变为城市用地 这里 x i j 为对应位置 i j 的单元 为随机变量 0 0 0 1 q QK 8 只用两个时间的观测数据只能假设城市增长速 度是固定的 不能反映城市增长的变化趋势 当有多 个观测数据来获得城市增长量的动态变化 Qt 时 上面的补充规则变为 假如 根据原始规则判断单元 x i j 应该转变为城市 用地 x i j 在迭代 t 1 中为非城市用地 且 t 则 x i j 在迭代 t 转变为城市用地 这里 0 00 1 tt t QQ QKQ 9 2 模型应用及结果 2 1 试验区及空间数据 试验区选在曾经进行过有关 CA 模拟的东莞市 选用同一地区可以更有效地对比不同模型的模拟效 868 中国科学 D 辑 地球科学 第 34 卷 SCIENCE IN CHINA Ser D Earth Sciences 果 我们原来所提出的神经网络的方法虽然能自动 获得模型的参数 16 但该模型属于黑箱结构 而且神 经元之间的关系复杂 很难理解参数的物理意义 通 过数据挖掘方法来获取明确的转换规则 对了解城 市复杂系统的动态机制十分重要 本模型比原来的 模型有更大的优越性 目前还没有从观察数据直接 获得具体的 CA 转换规则的研究 第一步是准备用于转换规则挖掘的空间数据 这些空间数据包括从遥感和 GIS 获得的各种空间变 量 表 1 遥感数据包括 1988 年 12 月 10 日 1993 年 12 月 24 日 1997 年 8 月 29 日和 2001 年 11 月 20 日 这 4 个时相的 TM 图像 只有 1988 和 1993 年的图像 被用来直接获取转换规则 其他时相只是辅助用来 获取城市增长的动态总量 本方法只需要至少两个 时相的遥感数据 城市增长的动态总量也可以从统 计年鉴上获取 这样可以增加其实用性 表 1 自动挖掘转换规则所需要的空间变量 空间变量 获取方法 目标变量 转变为城市用地 1988 1993 年 遥感分类 距离变量 离市中心距离 Dprop 离镇中心距离 Dtown 离公路距离 Droad 离高速公路距离 Dexpr 离铁路距离 Drail ARC INFO GRID Eucdistance 命 令 邻近函数 ARC INFO GRID Focalsum 命令 7 7 窗口城市用地单元数目 Nsum 自然属性 土地利用类型 Tland TM 图像遥感分类 农业适宜性 Sag 土地评价 坡度 Pslope DEM 模型 2 2 CA转换规则的自动挖掘 这些空间变量的数据量很大 尽管 See5 系统的 运算速度很快 为了提高数据挖掘的效率 并不是把 上面所有的空间数据都用于分析 采用 See5 系统中 所提供的随机采样功能 选取部分样品进行数据挖 掘 采用较少部分的数据进行分析会造成精度的减 小 将训练数据分成两组 一组用来挖掘规则 另一 组用来经验预测精度 图 2 显示采样百分比与预测精 度的关系曲线 采样百分比为 1 时 预测精度只为 35 2 采样百分比为10 时 预测精度升为25 0 采样百分比大于 10 后 精度的改善不明显 因此 本研究采用 20 的样品来进行数据挖掘 避免使用 过多的空间数据 图 2 采样率和预测误差 当决策树太复杂时 会使得预测结果与训练数 据过度拟合 如果训练数据带有误差 这种过度拟合 会有问题 因此 决策树往往需要修剪 以除掉可能 造成较大误差的部分 本研究采用 See5 0 系统提供 的缺省值 即 25 修剪率 来简化决策树 利用1988和1993年的遥感图像来获得具体的转 换规则 以模拟研究区在1988 2005 年期间内的城市 空间演变情况 图 3 是从 1988 年 1993 年 1997 年 和 2001 年遥感图像获得的城市用地总量 反映城市 增长的趋势 可以看到 初期城市扩张很快 后期慢 慢趋于平缓 其变化不是固定不变或呈线性关系的 如果仅用两个时间的观测数据 就无法掌握城市的 发展趋势 但目前也只有用两个时间的观测数据进 行 CA 模型纠正的研究 7 14 图 3 利用 1988 年 1993 年 1997 年和 2001 年 TM 遥感 图像获得的东莞城市发展趋势 第 9 期 黎夏等 知识发现及地理元胞自动机 869 CA 需要循环迭代运算多次才能获得最终的模拟 结果 但对循环迭代运算次数的多少 目前并没有统 一的意见 在每次循环迭代运算中 局部的相互作用 是模拟的关键 循环迭代运算次数太少 就很难产生 较真实的空间分布细节 一般来讲 CA 进行迭代运 算 100 200 次是很正常的 根据数据挖掘自动生成的转换规则 分别模拟 了 1988 1993 年 1993 1997 年 1997 2001 年及 2001 2005 年期间东莞市城市的空间演变情况 每一 模拟期间 CA 迭代运算次数为 200 根据从多时相遥 感图像获得每一时期的城市用地总量 Qt 利用公 式 9 计算出 t来反映转换量的动态变化 表2 为模拟 所用的基本参数 表 2 模拟不同时期城市增长所需要的循环迭代次数 城 市用地总量及 t参数值 模拟间隔 1988 1993 年 1993 1997 年 1997 2001 年 2001 2005 年 K 200 200 200 200 T a 5 4 4 4 t a 1 40 1 50 1 50 1 50 Qt km2 233 3 90 6 62 9 25 0 qt km2 1 167 0 453 0 315 0 125 t 0 0050 0 0019 0 0013 0 0005 利用See5 0系统 对所获得的GIS和遥感数据进 行数据挖掘 以发现知识 自动获得城市演变的转换 规则 下们列出了所获得的转换规则的部分例子 规则 1 假如 Dprop 18 Sag 7 Nsum 12 Sag 0 5 Tland 4 Pslope 6 则 转变为城市用地 置信度 0 86 规则 3 假如 Dprop 48 Dtown 13 Droad 1 Droad 5 Nsum 9 Sag 0 2 Sag 0 4 则 转变为城市用地 置信度 0 90 这些转换规则比一般 CA 所用的数学公式要清 晰和简单 更能反映城市演变的机制 每一条规则对 其所预测的转变类型进行 表决 其权重就等于置 信度 该置信度也是从训练数据中自动挖掘出来的 将所有规则 表决 的权重相加 以最大值来确定 CA 状态的转变类型 由于观测间隔与迭代间隔不一样 还需要计算 t 并使用如下的补充规则来决定从 t 到 t 1 时状态的 转换 见公式 9 补充规则 假如 0 0050 1988 1993 0 0019 1993 1997 0 0013 1997 2001 0 0005 2001 2005 年 年 年 年 则 转变为城市用地 2 3 模拟结果及检验 以 1988 年东莞城市用地作为开始点 对 1988 1993 年 1993 1997 年和 1997 2001 年期间的东莞城 市用地变化进行模拟 图 4 a 分别是各个时间的模拟 结果 作为对比 图 4 b 是根据卫星图像分类所获得 的实际城市用地 根据城市扩张的趋势 也对 2005 年的城市用地进行了预测 图 5 可以看到 东莞市 在上世纪 90 年代初经历了快速城市扩张的阶段 但 近年来城市扩张的速度已经比当时的快速扩张大为 减慢 反映了城市用地的规模已经得到了较为有效 的控制 同时也可以看到 该地区主要是沿公路进行 土地开发 没有形成紧凑式的城市形态 这种松散式 的城市发展形态会大大地增加能源的消耗 并造成 浪费土地资源的现象 对城市发展的模拟可以分析 和预测不同的土地利用政策对土地利用变化的影响 基于CA的模拟方法为城市规划工作者提供了一种有 效的分析工具 地理现象是复杂系统 受许多不确定性因素影 响 完全准确地模拟其动态变化是不可能的 但将 CA 应用于模拟真实的城市时 还是需要检验其与实 际情况吻合的程度 在这方面目前所开展的工作不 多 还没有统一的评价 CA 的精度或有效性的方法 一般是采用逐点对比和整体对比的方法 前一种方 法较简单 将模拟的结果和实际情况迭合起来 然后 870 中国科学 D 辑 地球科学 第 34 卷 SCIENCE IN CHINA Ser D Earth Sciences 图 4 东莞 1988 年 1993 年 1997 年和 2001 年城市用地模拟 a 和实际情况 b 对比 逐点对比就能计算其精度 后一种方法能提供更为 合理的评价结果 它所关注的是模拟出来的整个空间 格局 而不是强调每一个点的位置是否准确 但地理 现象的空间格局所涉及的方面较多 包括连通性 分 形和紧凑性等 首先 我们将模拟的 1993 年 1997 年和 2001 第 9 期 黎夏等 知识发现及地理元胞自动机 871 图 5 根据发展趋势模拟东莞市 2005 年城市用地 年城市用地和遥感图像获得的对应实际城市用地进 行点对点的对比 表 3 列出了它们的总精度 1993 年 城市用地的模拟总精度为82 0 1997和2001年城市 用地的模拟总精度分别为74 8 和72 4 其精度是 可以接受的 但需要说明的是 真正的模拟精度的评 价还需要考虑到遥感分类的精度 这里只是给出了 一种简便的评价方法 表 3 对比模拟结果和遥感观测结果获得的总精度 年份 1993 1997 2001 精度 82 0 74 8 72 4 我们也对模拟的空间格局与实际的情况进行对 比 描述空间格局的指标很多 没有统一的方法 不 同的指标有其优劣性 有的学者甚至认为在评价 CA 的模拟结果时 采用肉眼对比的方法更为有效 19 采 用肉眼对比的方法 也不难看到模拟的结果还是很 接近实际的 见图 5 为了比较客观地评价模拟结果 与实际情况在空间格局方面的吻合程度 我们采用 Moron I 指数来获得定量的评价结果 Moran I 一般是 用来描述空间的自相关性 由于该指数也可以分析 集中和分散的程度 它可以用来定量对比 CA 模拟结 果和观测情况在空间格局方面的接近程度 14 Moron I 的最大值为 1 反映被描述现象呈最集 中的情形 该值减小 反映该现象分散程度增大 表 4 是 1993 年 1997 年和 2001 年 Moron I 指数的对比 结果 可以看到各个时期的模拟结果和实际情况还 是十分接近的 城市用地在 1993 年还比较分散 可 能与当时土地发展较混乱有关 随着城市的发展 分 散的城市用地慢慢连接起来 表 4 1993 年 1997 年和 2001 年模拟结果和实际情况的 Moron I 指数对比 年份 1993 1997 2001 实际情况 0 44 0 66 0 76 模拟结果 0 41 0 58 0 71 我们也计算了基于神经网络的 CA 模型在模拟 872 中国科学 D 辑 地球科学 第 34 卷 SCIENCE IN CHINA Ser D Earth Sciences 1993 年城市用地时的总精度和 Moron I 指数值 其总 精度为 0 79 Moron I 指数值为 0 40 可见 本模型比 基于神经网络的 CA 模型在模拟精度方面有所改善 这是由于本方法比一般采用数学表达式更能反映复 杂的空间关系 然而 本方法最大的好处是能够从观 测数据中自动生成明确的转换关系 无需使用数学 公式 有更大的灵活性 3 结论 数据挖掘已经开始被应用于地理学领域 可以 获得与地理有关的空间分布规律等 CA 是模拟地理 现象的十分有用的工具 CA 的关键是如何定义转换 规则 必须采用系统和一致性的方法来定义转换规 则 否则就无法获得理想的模拟结果 但目前在定义 CA 的转换规则方面受主观因素影响很大 而且这些 转换规则大多数是用数学公式来隐含表达的 数学 表达式在表达复杂的自然现象会有局限性 本研究首次通过数据挖掘的方法从 GIS 和遥感 图像自动生成 CA 的转换规则 比以往的方法有了很 大的改善 本方法的优点是能从大量的空间数据中 自动获取明确的转换规则 无需使用数学表达式来 定义转换规则 并能在生成转换规则的同时对模型 自动进行纠正 一般 CA 模型在使用数学表达式时会 涉及许多变量 通过模型纠正的方法来确定变量对 应的参数值是比较困难的 将该模型应用在珠江三角洲地区 利用不同年 份的卫星遥感图像作为主要观察数据 根据所提出 的方法来获取转换规则 模拟该地区在1988 2001 年 的城市空间增长情况 并对 2005 年的城市用地进行 预测 利用逐点对比和 Moran I 指数来评价模型的精 度或有效性 发现本模型能获得较理想的模拟效果 比以往方法有一定的改进 参 考 文 献 1 Batty M Xie Y From cells to cities Environment and Planning B 1994 21 531 548 2 White R Engelen G Cellular automata and fractal urban form a cellular modelling approach to the evolution of urban land use patterns Environment and Planning A 1993 25 1175 1199 3 黎 夏 叶嘉安 约束性单元自动演化 CA 模型及可持续城市 发展形态的模拟 地理学报 1999 54 4 289 298 4 周成虎 孙战利 谢一春 地理元胞自动机研究 北京 科学出 版社 1999 1 163 5 黎 夏 叶嘉安 主成分分析与 Cellular Automata 在空间决策 与城市模拟中的应用 中国科学 D 辑 2001 31 8 683 690 6 Li Xia Yeh A G O Modelling sustainable urban development by the integration of constrained cellular automata and GIS International Journal of Geographical Information Science 2000 14 2 131 152 7 Li Xia Yeh A G O Neural network based cellular automata for simulating multiple land use changes using GIS International Journal of Geographical Information Science 2002 16 4 323 343 8 Clarke K C Brass J A Riggan P J A cellular automata model of wildfire propagation and extinction Photogrammetric Engineering Remote Sensing 1994 60 1355 1367 9 Couclelis H Of mice and men what rodent populations can teach us about complex spatial dynamics Environment and Planning A 1988 20 99 109 10 Yeh A G O Li Xia A constrained CA model for the simulation and planning of sustainable urban forms by using GIS Environment and Planning B 2001 28 733 753 11 Li Xia Yeh A G O Zoning for agricultural land protection by the integration of remote sensing GIS and cellular automata P