不确定性空间数据挖掘算法模型.pdf

第3 6 卷第1 期中国矿业大学学报 V 0 1 ．3 6N o ．1 2 0 0 7 年1 月J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g yJ a n ．2 0 0 7 文章编号1 0 0 0 1 9 6 4 2 0 0 7 0 1 0 1 2 1 0 5 不确定性空间数据挖掘算法模型 何彬彬1 ，方涛2 ，郭达志3 1 ．电子科技大学地表空间信息技术研究所，四川成都6 1 0 0 5 4 ； 2 ．上海交通大学图像处理与模式识别研究所，上海2 0 0 0 3 0 ； 3 ．中国矿业大学环境与测绘学院，江苏徐州 2 2 1 0 0 8 摘要在分析空间数据和空间数据挖掘的不确定性基础上，针对传统空间数据挖掘的局限性，将 空间数据的不确定性和空间数据挖掘的不确定性有机结合，以E M 算法和A p r i o r i 算法为基础， 建立了不确定性空间数据挖掘算法模型，包括不确定性空间数据聚类算法 U N E M 和不确定性 空间数据关联规则挖掘模型 U S A R ．并以中国3 7 个有代表性的大中城市的地理空间经济数据 为例，进行实验验证，结果表明采用不确定性空间数据挖掘算法模型比传统的空间数据挖掘方 法得到的知识更为真实客观． 关键词不确定性；空间数据挖掘；U N E M 算法；U S A R 模型；质量评价 中图分类号P2 ；T P3 9 l文献标识码A U n c e r t a i nS p a t i a lD a t aM i n i n gA l g o r i t h m s H EB i n - b i n l ，F A N GT a 0 2 ，G U OD a z h i 3 1 ．I n a t i t u t eo fG e o S p a t i a lI n f o r m a t i o nS c i e n c ea n dT e c h n o l o g y ，U n i v e r s i t yo fE l e c t r o n i cS c i e n c ea n d T e c h n o l o g yo fC h i n a ，C h e n g d u ，S i c h u a n6 1 0 0 5 4 ，C h i n a 2 ．I n s t i t u t eo fI m a g eP r o c e s s i n g P a t t e r nR e c o g n i t i o n ， S h a n g h a iJ i a oT o n gU n i v e r s i t y 。S h a n g h a i2 0 0 0 3 0 ，C h i n a ；3 ．S c h o o lo fE n v i r o n m e n t S p a t i a lI n f o r m a t i c s ， C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，X u z h o u ，J i a n g s u2 2 1 0 0 8 ，C h i n a A b s t r a c t O nt h eb a s i so fa n a l y z i n gt h eu n c e r t a i n t i e so fs p a t i a ld a t aa n ds p a t i a ld a t am i n i n g S D M ，i nv i e wo ft h e1 i m i t so ft r a d i t i o n a ls p a t i a ld a t am i n i n g ，t h eu n c e r t a i n t i e so fs p a t i a ld a t a a n ds p a t i a ld a t am i n i n gw e r ep r o p e r l yc o m b i n e d ．B a s e do nE Ma l g o r i t h ma n dA p r i o r ia l g o r i t h m ，t h eu n c e r t a i ns p a t i a ld a t am i n i n ga l g o r i t h m s ，i n c l u d i n gu n c e r t a i ns p a t i a lc l u s t e r i n ga l g o r i t h m u n c e r t a i nn e i g h b o r h o o de x p e c t a t i o nm a x i m u m ，U N E M a n du n c e r t a i ns p a t i a la s s o c i a t i o nr u l e sm i n i n g U S A R m o d e lw e r ep r e s e n t e d ．M e a n w h i l e ，t h ee x p e r i m e n t sc o n c e r n e dh a v e b e e np e r f o r m e du s i n gt h eg e o s p a t i a ld a t af r o m3 7t y p i f i e dc i t e si nC h i n a ．T h er e s u l t ss h o w t h a tt h ek n o w l e d g ea c q u i r e dt h r o u g ht h eu n c e r t a i ns p a t i a ld a t am i n i n ga l g o r i t h m si sm o r er e a l a n do b je c t i v et h a nt h o s et h r o u g ht r a d i t i o n a ls p a t i a ld a t am i n i n gm e t h o d s ． K e yw o r d s u n c e r t a i n t y ；s p a t i a ld a t am i n i n g ；U N E Ma l g o r i t h m ；U S A Rm o d e l ；q u a l i t ya s s e s s m e n t 空间数据挖掘 S p a t i a lD a t aM i n i n g ，是指从 空间数据库 空间数据仓库 中提取隐含的、用户感 兴趣的空间模式与规则、空间与非空间数据的普遍 关系及其他一些隐含在数据库中的普遍的数据特 征的过程‘1 ’2 | ．随着空间数据获取手段的自动化程 度的不断提高，空间数据库的数据呈指数级的增 收稿日期2 0 0 5 0 8 2 8 基金项目国家自然科学基金项目 6 0 2 7 5 0 2 1 ；中国博士后科学基金 2 0 0 6 0 3 9 0 3 2 6 作者简介何彬彬 1 9 7 2 一 ，男，湖南省邵阳市人，博士 博士后 ，从事空间数据库与数据挖掘、遥感信息处理方面的研究 E - m a i l b i n b i n h e u e s t c ．e d u ．c n T e l 0 2 8 8 3 2 0 6 5 8 6 万方数据 1 2 2中国矿业大学学报第3 6 卷 长，但专职处理空间数据的遥感和地理信息系统软 件在分析功能上的不足，使得海量空间数据与有用 知识获取之问存在尖锐的矛盾，致使“空间数据爆 炸但知识贫乏”[ 3 ] ．因此，近几年空间数据挖掘已成 为空间信息领域的一个重要研究热点，并取得了许 多重要成果．目前对于空间数据挖掘的研究主要集 中在空间数挖掘的原理及方法本身．而对其另一个 重要方面一空间数据挖掘不确定性还少有报道．事 实上，空间数据自身具有不确定性[ 4 书] ，空间数据挖 掘过程中也会带来一系列的不确定性，这些不确定 性在空间数据挖掘过程中会不断传播和积累，从而 可能导致挖掘出来的知识有较大的误差甚至毫无 意义．而传统的空间数据挖掘并未将这些特性考虑 进去，并且一般认为挖掘出来的知识都是有用的和 确定的，这显然是不科学和不妥当的．因此，研究空 间数据挖掘的不确定性显得尤为重要． 识，大都是经过归纳和抽象的定性知识，或是定性 和定量相结合的知识．对这些知识的最好表示方法 就是自然语言，至少在知识表示方法中含有语言 值，即用语言值表达其中的定性概念． 图1 空间数据挖掘的不确定性来源及其传播 F i g ．1U n c e r t a i n t yo r i g i n sa n dp r o p a g a t i o ni n s p a t i a ld a t am i n i n g 1 空间数据挖掘不确定性分析 2 不确定性空间数据挖掘算法模型 空间数据挖掘过程可分为4 个阶段数据选 取、数据预处理、数据挖掘、知识表示与评价．同样， 在空间数据挖掘的过程中也存在相当数量的不确 定性积累和传播 图1 ，而且比空间数据中的不确 定性更为复杂．空间数据选取阶段的不确定性主要 是指根据空间数据挖掘任务的要求，主观选择目标 数据过程中带来的不确定性，包括哪些数据应该被 选择、多少数据量才足够等．数据选取阶段的不确 定性主要受应用数据挖掘技术想要解决问题的定 义和参与人员的知识结构影响．空间数据预处理主 要包括数据清理、数据变换和数据归约．数据清理 主要是试图填充空缺的值、识别孤立点、消除噪声 和纠正数据中的不确定性；数据变换是将数据转换 成适合于挖掘的形式，主要包括平滑、聚集和数据 概化 用高层次新的属性归并属性集，以帮助挖掘 过程 ．在这一阶段中，一方面处理不确定性，另一 方面在处理过程中又可能带来新的不确定性．数据 挖掘本身带来的不确定性主要是指由于挖掘算法 的局限性而造成挖掘结果与真实情况的不完全一 致，这也是造成数据挖掘不确定性的重要原因之 一．每一种数据挖掘算法都有其优缺点和实用范 围，而且经典的数据挖掘算法一般并没有考虑算法 的不确定性和数据的不确定性。知识表示中的不确 定性主要是指知识本身隐含不确定性，包括随机 性、模糊性等．同一知识可以用多种方法表示．有些 知识用这种方法表示比较好，有些则可能采用另一 种表示方法比较合适．空间数据挖掘所获得的知 传统的空间数据挖掘方法是首先将空间数据 组织成关系表的形式，每一个元组 记录 表达一个 空间对象，每个元组包含空间对象的多个属性 一 般分为条件属性和决策属性 ，然后将表中连续型 空间属性进行离散化，再运用经典数据挖掘算法 如C 5 ，A p r i o r i 算法 提取规则．但是，该方法存在 4 个明显的缺陷1 用于空间数据挖掘的源数据 往往带有不同程度的不确定性，而传统方法认为源 数据是确定的，缺乏对原始空间数据真实性的合理 考虑；2 空间数据挖掘过程中尤其是连续型数据 离散化过程中会带来大量的不确定性，从而可能导 致挖掘出来的知识存在误差甚至毫无意义，而传统 方法并没有采取有效方法对其进行不确定性处理； 3 空间数据往往趋于高度空间自相关，而传统方 法是基于采样独立性的假设的，缺乏对空间自相关 的度量和考虑；4 缺乏对空间数据挖掘结果的质 量评价．针对以上4 个主要问题，以E M 算法和 A p r i o r i 算法为基础，构建了不确定性空间数据挖 掘算法模型，主要包括空间数据不确定性的 M o n t eC a r l o 模拟、基于不确定性空间数据空间自 相关度量、不确定性空间数据聚类算法和不确定性 空间数据关联规则挖掘模型． 2 ．1空间数据不确定性的M o n t eC a r l o 模拟 根据不同空间数据的不确定性 误差 分布采 用M o n t eC a r l o 模拟法进行不确定性模拟．本文中 取用2 0 0 2 年中国3 7 个主要大中城市的地理空间 经济数据的位置数据和若干属性数据 距海洋的距 万方数据 第1 期何彬彬等不确定性空间数据挖掘算法模型 离、人均G D P 、人均年可支配收入和商品房均价 ， 采用M o n t eC a r l o 模拟法对它们进行不确定性模 拟，根据不同空间对象的位置数据和不同属性数据 的均值和中误差，分别得到不同空间对象的位置数 据和不同属性数据的10 0 0 组模拟数据．对于位置 数据，采用圆形正态误差模型．对于空间对象的各 属性数据的误差，则用一维正态分布来估计．其算 法如下具体算法如下 1 确定每个待输入空间数据集的不确定性 类型 位置数据的圆形正态模型，属性数据的一维 正态模型 ； 2 取用依空间数据集分布的随机采样来代 替原输入空间数据； 3 对每一次实现，存储其结果； 4 随机抽取l0 0 0 组实验数据作为样本数据． 这里，随机数发生器采用普雷斯等人 1 9 9 6 推 荐的随机数发生器r a n 2 [ 7 ] ，随机向量的抽样方法 采用著名的博克斯一马勒 B o x - M u l l e r 方法[ 7 ] ， 2 ．2 基于不确定性空间数据的空间自相关度量 几乎所有空间数据都具有空间自相关性，因此 在处理地理区域或地带的离散数据时须考虑空间 数据的空间自相关性．空间自相关矩阵如式 1 所 示． 根据邻接或距离标准，当空间对象i 和空间对 象J 相邻时，空间权重矩阵的元素鲫。为1 ，其他情 况为0 ． 议n 1 Z ．U 2 1 ● 议‰l 1 式中m 为空间对象m ；咒为空间对象7 2 ；硼。为空 间对象m 和挖的空间权重元素． 本文借用V o r o n o i 和D e l a u n a y 图，结合距离 标准来构建空间权重矩阵．普通的距离计算技术一 般隐含地假设空间数据的位置是精确的．考虑到空 间数据的不确定性，采用3 种方法计算空间数据间 空间自相关矩阵中心法、最小法和最大法哺] ．假设 区域S 中有／, ／个位置不确定的点，第i 个点P 。的误 差带用一个圆形Q 。表示．具体算法如下 输入区域S 中的一组点的误差带Q 一{ Q 。， Q 。，⋯，Q 和邻域距离d 输出区域S 中一组点的邻域图和空间自相关 距阵 步骤1 构造点集P 的V o r o n o i 多边形 步骤2 对所有相邻的V o r o n o i 多边形进行如 下运算 步骤2 ．1 计算d 。。。。 C 。，C j ，d 。。， Q f ，Q ， ， d 。i 。 Q i ，Q ； 步骤2 ．2 如果d d 。，则在邻域图中连接P 。 和P i ，叫i 为1 ；否则叫i 为0 其中，d 。为邻域距离；d ⋯。， C i ，C ， 表示相邻误差 带 Q ，Q ， 质心之间的距离；d 。。。 Q 。，Q ， 表示相邻 误差带 Q ，Q ， 内空间数据之间的最大距离； dr a i n Q ，Q ， 表示相邻误差带 Q ，Q i 内空间数 据之间的最小距离． 2 ．3 不确定性空间数据聚类算法 传统的空间数据聚类算法是利用经典的聚类 算法 如K m e a n s ，K m e d o i d 进行聚类．这种方法 由于并未考虑空间数据的空间约束，其结果经常在 地理位置上很混乱．此外，这种聚类方法还有一个 共同的缺点是将空间对象集合划分为互不相交的 子集，其中每个空间对象最多只属于一个聚类．但 是当空间对象与2 个聚类之间的距离相等，或者空 间对象与2 个聚类区域同时相交时，强制聚类之间 不能相交的约束就不符合实际．鉴于此，以E M 算 法为基础，顾及空间数据的不确定性和空间聚类的 模糊性以及空间数据的空间自相关性，构建基于不 确定性的空间聚类算法 U N E M ，主要包括空间 数据不确定性的M o n t eC a r l o 模拟 见2 ．1 节 、空 间数据标准化、空间权重矩阵构建 见2 ．2 节 和顾 及空间自相关的E M 算法改进[ 9 ] ．其中，空间数据 标准化是为了避免对各度量单位选择的依赖． 2 ．4不确定性空间数据关联规则挖掘模型 在空间数据挖掘过程中，一方面须分析挖掘过 程中存在的不确定性，并采用有效方法处理其不确 定性；另一方面，又不可能消除所有的不确定性，因 为空间数据挖掘算法本身和不确定性处理过程中 均会带来不同程度的新的不确定性．所以，对空间 数据挖掘进行质量评价是十分必要，它可以帮助我 们更客观地度量空间数据挖掘的真实性．本文结合 传统数据挖掘质量评价方法[ 10 。，考虑空间数据不 确定性特点的基础上，初步建立了一套适合不确定 性空间数据关联规则挖掘的质量评价指标。包括覆 盖度、支持度、可信度、作用度、杠杆作用度和兴趣 度[ 1 1 ] 以及它们的均值 m e a n 和方差 v a r i a n c e ． 关联规则出现的概率 P r o b a b i l i t y 考虑空 间数据的不确定性基础上，如果从一组原始空间数 据集中依空间数据的不确定性分布模拟出咒组样 本进行实验，出现同一关联规则的个数为m ，则该 关联规则出现的概率为 万方数据 1 2 4中国矿业大学学报 第3 6 卷 P r o b a b i l i t y m ／n ． 2 关联规则质量评价指标的均值 m e a n 和方 差 v a r i a n c e 根据m 个同一规则的同一质量评价 指标的不同取值计算其相应的均值和方差，则其空 间质量评价指标的表示形式为Q P r o b a b i l i t y ， m e a n ，v a r i a n c e m e a n 一土y 咒， 3 m 置 式中X 。为关联规则的质量评价指标． v a r i a n c e 一 三∑ x m e a n 2 ． 4ml 士■ ’ 同时，结合上述的关联规则质量评价指标，以 A p r i o r i 算法为基础，采用2 ．3 节介绍的不确定性 空间聚类算法进行连续型空间数据离散化，建立了 不确定性空间数据关联规则挖掘模型 见图2 ． ⑨／MonteC a r l o 。 不确定性的＼ IJ L ，户 ＼堡塑／／ 臼圈臼霉 图2不确定性空间数据关联规则挖掘模型 F 培．2 U n c e r t a i ns p a t i a ld a t aa s s o c i a t i o n r u l e sm i n i n gm o d e l 定性、空间自相关性和分类模糊性的U N E M 聚类 结果与传统的E M 聚类 图3 不同．同时，采用以” 商品房均价”作为规则后件，其余属性作为规则前 件，最小支持度采用1 0 ％，最小可信度采用5 0 ％， 进行关联规则挖掘，实验结果如图4 和表2 ．图5 显示所挖掘的关联规则质量评价指标均较好．从表 2 中可以看出，不确定性空间数据关联规则挖掘模 型得到的规则／知识是不确定的，但通过质量评价 指标可以较客观的度量它． 图3中国3 7 个大中城市2 0 0 2 年 地理空间经济数据E M 聚类结果 F i g ．3 E Mc l u s t e r i n gr e s u l t so ft h i r t y - s e v e nc i t i e s ’ g e o g r a p h i c a le c o n o m yd a t ai n2 0 0 2 3实例分析 以2 0 0 2 年中国3 7 个主要大中城市地理空间 经济数据为例，进行基于U N E M 算法的空间数据 聚类和基于U S A R 模型的空间数据关联规则挖 掘．具体步骤如下1 根据地理空间经济数据的不 确定性类型进行不确定性的M o n t eC a r l o 模拟 2 ．1 节 ；2 空间属性数据标准化；3 空间自相 关矩阵计算 2 ．2 节 ；4 不确定性空间数据聚类 2 ．3 节 ；5 不确定性空间数据关联规则挖掘及质图4中国3 7 个大中城市2 0 0 2 年 量评价 2 ．4 节 ．分6 个类别进行聚类，实验结果 F i g ．4 美罐嚣慧鋈篓戛。U u N l 。。E M 。f 聚类。h i r 。篡三。n 。i 。i 。。， 如图3 和图4 所示，图4 中显示顾及空间数据不确 。 g e o g r a p h i c a le o n o m Yd a t ai n2 0 0 2 表1不确定空间数据关联规则挖掘结果 T a b l e1T h er e s u l t so fu n c e r t a i ns p a t i a ld a t aa s s o c i a t i o nr u l e sm i n i n g 万方数据 第1 期何彬彬等不确定性空间数据挖掘算法模型 1 2 5 续表 O ．1 0 越0 ．0 9 豫 锹0 ．0 8 0 ．0 7 1 0 藿 世4 0 12345678 关联规则编号 a 支持度 l2345678 关联规则编号 d 作用度 l 5 鐾1 ．o 詹O ．5 O 1 ．5 型 垂1 ．0 鲞o s O l2345678 关联规则编号 b 可信度 l2345678 关联规则编号 e 杠杆作用度 0 ．1 5 藉n 1 0 酶0 ．0 5 O 1 ．O 鞋 永0 ．4 0 ．2 O 12345678 关联规则编号 c 覆盖度 12345678 关联规则编号 f 兴趣度 图5不确定性空间数据关联规则挖掘质量评价指标变化图 F i g ．5Q u a l i t ya s s e s s m e n ti n d e x e sv a r i a t i o nd i a g r a mo fu n c e r t a i ns p a t i a ld a t aa s s o c i a t i o nr u l e sm i n i n g 4 结论 6 5 3 9 2 3 9 9 建立的不确定性空间数据挖掘算法模型，经实 [ 6 1 验验证结果表明采用不确定性空间数据挖掘算法 模型比传统的空间数据挖掘方法得到的知识更为 真实客观． 参考文献 [ 1 ]M I L L E RH ，H A NJ ．G e o g r a p h i cd a t am i n i n ga n d k n o w l e d g ed i s c o v e r y [ M ] ．L o n d o n T a y l o r F r a n c i s ，2 0 0 1 ． E 2 7 邸凯昌．空间数据发掘与知识发现[ M ] ．武汉武汉大 学出版社，2 0 0 0 ． [ 3 ] 李德仁，王树良，李德毅，等．论空间数据挖掘与知识 发现的理论与方法[ J ] ．武汉大学学报信息科学版， 2 0 0 2 ，2 7 3 2 2 1 2 3 3 ． L ID e ．- r e n ，W A N GS h u l i a n g ，L ID e - y i ，e ta 1 ．T h e o r i e sa n dt e c h n o l o g i e so fs p a t i a ld a t ak n o w l e d g ed i s c o v e r y [ J ] ．G e o m a t i c sa n dI n f o r m a t i o nS c i e n c eo f W u h a nU n i v e r s i t y ，2 0 0 2 ，9 7 3 2 2 1 ～2 3 3 ． [ 4 ] 郭达志，胡召玲，陈云浩．G I S 中空间对象的不确定性 研究[ J ] ．中国矿业大学学报，2 0 0 0 ，2 9 1 2 0 2 4 ． G U OD a - z h i ，H UZ h a o l i n g ，C H E NY u n - h a o ．S t u d y o nu n c e r t a i n t i e so fS p a t i a lO b j e c t si nG I S [ J ] ．J o u r n a l o fC h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，2 0 0 0 ， 2 9 1 2 0 2 4 ． [ 5 ]史文中，王树良．G I S 中属性不确定性的处理方法及 其发展[ J ] ．遥感学报，2 0 0 2 ，6 5 3 9 2 3 9 9 ． S H IW e n z h o n g ，W A N GS h u l i a n g ．F u r t h e rd e v e l o p m e n to ft h e o r i e sa n dm e t h o d so na t t r i b u t eu n c e r t a i n t yi nG I S [ J ] ．J o u r n a lo fR e m o t eS e n s i n g ，2 0 0 2 ， [ 7 ] [ 8 1 [ 9 1 [ 1 0 ] [ 1 1 ] 邬伦，于海龙，高振纪，等．G I S 不确定性框架体系 与数据不确定性研究方法[ J ] ．地理学与国土研究， 2 0 0 2 ，1 8 4 1 - 5 ． W UL u n ，Y UH a i l o n g ，G A OZ h e n - j i ，e ta 1 ．T h e f r a m eo fG I S u n c e r t a i n t ya n dm e t h o d so fG I S E J ] ．D a t aU n c e r t a i n t yG e o g r a p h ya n dT e r r i t o r i a lR e s e a r c h ， 2 0 0 2 。1 8 4 1 - 5 ． 徐利治．现代数学手册随机数学卷[ M ] ．武汉华中 科技大学出版社，2 0 0 1 ． S A D A H I R 0Y ．C l u s t e rd e t e c t i o ni nu n c e r t a i np o i n t d i s t r i b u t i o n s ac o m p a r i s o no ff o u rm e t h o d s [ J ] ． C o m p u t e r s ，E n v i r o n m e n ta n dU r h a nS y s t e m s ，2 0 0 3 ， 2 7 3 3 - 5 2 ． 何彬彬，方涛，郭达志．基于不确定性的空间聚类 [ J ] ．计算机科学，2 0 0 4 ，3 1 1 1 1 9 6 1 9 8 ． H EB i n - b i n 。F A N GT a o ．G U OD a - z h i ．U n c e r t a i n t y - b a s e dc l u s t e r i n gm e t h o df o rs p a t i a ld a t am i n i n g [ J ] ． C o m p u t e rS c i e n c e ，2 0 0 4 ，3 1 1 1 1 9 6 1 9 8 ． V A Z I R G I A N N I SM ，H A L K I D IM ，G U N O P U L O S D ．U n c e r t a i n t yh a n d l i n ga n dq u a l i t ya s s e s s m e n ti n d a t am i n i n g [ M ] ．L o n d o n S p r i n g e r - V e r l a g ，2 0 0 3 ． H EBB ，F A N GT ，G U ODZ ．Q u a l i t ya s s e s s m e n t a n du n c e r t a i n t yh a n d l i n gi nt h es p a t i a ld a t am i n i n g p r o c e s s e s [ C ] ／／P r o c e e d i n g so f 1 2 t hI n t e r n a t i o n a l C o n f e r e n c eo nG e o i n f o r m a t i c s ．S w e d e n G a v l eU n i v e r s i t yP r e s s ，2 0 0 4 2 0 3 2 1 0 ． 责任编辑姚志昌 万方数据