（应用数学专业论文）空间数据挖掘分类算法的研究.pdf

摘要 随着计算机技术特别是数据库技术的迅猛发展，以及人类活动范围的扩展、生活节 奏的加快，人们能以更快速更容易更廉价的方式获取和存储数据，这就使得数据及其信 息量以指数方式增长。面对这些极度膨胀的数据，人们受到“信息爆炸”和“数据过剩” ( d a t ag l u t ) 的巨大压力。这些海量数据如果不能有效利用起来，将只会成为“数据垃 圾”。对人类社会进步起到巨大作用的是知识。 数据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技术。数据挖掘 包含的内容很多，其中很重要的一个方面是分类规则挖掘。分类规则可以根据训练数据， 利用适当的算法训练出分类器，从而对新的未知样本做出预测。支持向量机是基于统计 学习理论的一种新的分类方法。同其它分类器相比，支持向量机具有很好的推广性能， 对未知样本的预测有较高的准确率，因此得到广泛应用。 本文首先将可拓学基元理论应用与对象之间的空间关系。将支持向量机理论应用于 对空间数据进行分类，简单的支持向量机只能处理二值分类问题，本文在已有多分类支 持向量机基础上，将支持向量机基理论与传统的二叉树分类方法结合，提出了基于距的 二叉树多类s v m 算法，并且通过实验验证了算法的有效性。 关键词：数据挖掘；支持向量机：距；分类 i l l t h er e s e a r c ho f i n t e r s p a c ed a t am i n i n gc l a s s i f ya r i t h m e t i c a b s t r a c t i nt h ep a s ty e a r s ，c o m p u t e rt e c h niq u e se s p e ci a ll yo fd a t a b a s et e c h n i q u e sh a v ed e v e l o p e dg r e a t l y ，a r e ao fp e o p l e sa n t i v i t i e sh a sb e e ne x t e n d e d ， r h y t h mo f1i f eh a ss p e e d e du p p e o p l ea r ea b l et og e ta n ds t o r ed a t am o r eq u i c k l y ， e a s i l ya n dc h e a p l y ，w h i c hm a k et h ed a t aa n di n f o r m a t i o ni n c r e a s ee x p o n e n t i a l l y f a c i n gt h eg r e a tc a p a c i t yo fd a t a ，p e e p ea r eu n d e rt h ep r e s s u r eo fi n f o r m a t i o n e x p l o s i o na n dd a t ag l u t i tw i i ib eg a r b a g ei ft h em a s s i v ed a t ac a n tb ee x p l o i t e d i t st h ek n o w l e d g et h a th a sg r e a te f f e c to nt h ed e v e l o p m e n to fs o c i e t y d a t a m i n i n gi sat e c h n o l o g yt h a tf i n d su n d e r s t a n dr u l e sa n de x t r a c t sv a l u a b l e k n o w le d g e t h e r ea r el o t s o fb r a n c h e si nd a t am i n i n g ，o n eo ft h e mi sc l a s s i f i c a t i o n r u l e sm i n i n g w i t hp r o p e rt r a i n i n ga l g o r i t h mo nt r a i n i n gd a t a ，i tw i l lg e n e r a t e c l a s s i f i e f st h a tc o u l dg e tp r e d i c t i o nt ou n k n o w ne x a m p l e s s u p p o r tv e c t o r m a c h i n e ( s v m ) i san e wc l a s s i f i c a t i o na l g o r i t h mb a s e do ns t a t i s t i c a ll e a r n i n g t h e o r y c o m p a r e dt oo t h e rc l a s s i f i e r s ，s v mh a sb e t t e rg e n e r a l i z a t i o np e r f o r m a n c e a n dh i g h e rp r e d i c t i o na c c u r a c yt o t e s te x a m p l e s os v mh a sh a dal o to f a p p l i c a t i o n n a iv es v mi so n l ya b l et od e a lw i t hb i n a r yc l a s s i f i c a t i o n i nt h i st h e s i s ， a f t e rd i s c u s s e dt h ec u r r e n tm u l t i c l a s ss v m s ，an o v e lm u l t i c l a s ss v mc l a s s i f i e r b a s e do nd i s t a n c ei sp r o p o s e d ig i v ean e wa l g o r i s ma n dt h r o u g he x p e r i m e n tt e s t i t v a l i d i t y k e y w o r d s ：d a t an i n i n g ：s v m ：d i s t a n c e ：c l a s s i f i c a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成 博士硕士学位论文： ：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的 成果。 本声明的法律责任由本人承担。 论文作者签名：年月日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、版权使 用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论文的复印件 和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或 部分内容编入有关数据库迸行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密嘶青在以上方框内打“”) 论文作者签名：搬掣 f 日期 n 0 1 师签名：叫【 年月，角 引言 数据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技术。 数据挖掘包含的内容很多，其中很重要的个方面是分类规则挖掘。分类规则可以根据 训练数据，利用适当的算法训练出分类器，从而对新的未知样本做出预测。支持向量机 是基于统计学习理论的一种新的分类方法。同其它分类器相比，支持向量机具有很好的 推广性能，对未知样本的预测有较高的准确率，因此得到广泛应用。 本文首先将可拓学基元理论应用与对象之间的空间关系。将支持向量机理论应用于 对空间数据进行分类，本文在已有多分类支持向量机基础上，将支持向量机基理论与传 统的二叉树分类方法结合，提出了基于距的二叉树多类s v m 算法，并且通过实验验证了 算法的有效性。 第1 章绪论 1 1 空间数据挖掘的提出与意义“”“5 1 随着空间数据库技术的高速发展，人类积累大量空间数据，例如其在地理信息系统 ( g i s ) 、遥感、医疗影像、计算机辅助设计( c a d ) 、动植物生态领域等方面广泛应用导 致空间数据急剧地产生和增加，如美国国家航空和宇宙航行局( n a t i o n a la e r o n a u t i c s a n ds p a c ea d m i n i s t r a t i o n ，n a s a ) 对地观测系统( e a r t ho b s e r v i n gs y s t e m ，f o s ) 每天 都要产生1 t b 空间数据：中国建成的覆盖全国、全省的大型地理空间数据库和专题数据 库的数据总量超过1 2 5 0 g b ：有关火灾数据、地形分布数据等等，都收集大量数据类型和 特征繁多的空间数据。据统计：全球拥有的数据量每2 0 个月翻一番，因此我们不仅拥有 极其庞大的空间数据，而且其空间数据类型越来越复杂、结构越来越多样。日益丰富具 有空间特征的数据在一定程度上己超出了人类大脑的分析能力，从而形成空间数据虽 多，但知识贫乏、用处不大的局面。从这些空间数据中发现领域知识迫切需求产生一个 多学科、多领域综合交叉的新兴研究领域一空间数据挖掘【1 4 1 。 空间数据挖掘是指对空间数据库中非显式存在知识、空间关系或其他有意义模式等 的提取。空间数据挖掘需要综合数据挖掘、空间数据库、空间信息学、计算机科学等技 术。它可用于对空间数据的理解，空间关系和空问与非空间数据间关系的发现，空间知 识库的构造，空间数据库的充足和空间查询的优化。空间数据挖掘总体可以分为空间关 联规则技术、空间同位、空间离群技术、空间分类、时空序列等技术。其在地理信息系 统，地理市场( g e o m a r k e t i n g ) 、遥感、c a d 、图像数据库探测、医学图像处理、导航、 交通控制、环境研究等许多使用空间数据领域中有广泛的应用【1 5 1 。由于空间数据的海量 性、空间数据类型和空间访问方法的复杂性，因此在充分考虑空间相关性情况下研究高 效空间数据挖掘技术已成为空间数据挖掘发展的必然。 1 2 空间数据的特点1 6 1 1 ” 1 2 1 空间数据的类型 对于空问信息搜集中，最为通用的形状是由空间表不体系所描述的几何体来表的， 空间表示体系是一个坐标系统，类似于经度纬度或其它公认框架。几何体分为四类：点 ( p o i n t ) 、线( c u r v e ) 、面( s u r f a c e ) 和儿何体集合( g e o m e t r yc o l l e c t i o n ) 。点描述个 零维对象的形状，如重点单位，火灾地点等等：线描述一维对象的形状，如河流、道路 线等：线对象通常用线串( 1 i n e s t r i n g ) 来近似表示，它有两个或更多点表示。最简单的 线串是一条连接两个或更多点的直线段。面则描述了二维对象的形状，如湖泊，小区， 国家等。面通常用多边形建模。几何体集合表不复杂的形状，湖泊群等，几何体集合有 三种类型，即多点( m u l t i p o i n t ) 、多线( m u l t i c u r v e ) 和多面( m u l t i s u r f a c e ) 。儿何体集 合空间数据类型保证了g i s 空间数据类型在几何操作上的闭合性呻4 ”( c l o s u r e ) ，这些 操作包括几何并、几何差或集合交操作。图1 1 描述了用u m l 符号表示的二维空问几何体 的基本构件及其相互关系，当然这些关系也可以用在三维空间中。 图1 ig i s 的关于卒间几i i 可体的摹本构件 12 2 空间数据的复杂特性“”2 ”。“ dj 于空恻属性的存在空间的对蒙才具有了空间位置和距离的概念，并且空闻对象 dj 于空恻属性的存在空间的对蒙才具有了空间位置和距离的概念，并且空闻对象 1 ，2 空间数据的特点1 6 1 1 ” 1 2 1 空间数据的类型 对于空间信息搜集中，最为通用的形状是由空间表示体系所描述的几何体来表的， 空间表示体系是一个坐标系统，类似于经度纬度或其它公认框架。几何体分为四类：点 ( p o i n t ) 、线( c u r v e ) 、面( s u r f a c e ) 和儿何体集合( g e o m e t r yc o l l e c t i o n ) 。点描述个 零维对象的形状，如重点单位，火灾地点等等：线描述维对象的形状，如河流、道路 线等：线对象通常用线串( 1 i n e s t r i n g ) 来近似表示，它有两个或更多点表示。最简单的 线串是一条连接两个或更多点的直线段。面则描述了二维对象的形状，如湖泊，小区， 国家等。面通常用多边形建模。几何体集合表不复杂的形状，湖泊群等。几何体集合有 三种类型，即多点( m u l t i p o i n t ) 、多线( m u lt i c u r v e ) 和多面( m u l t i s u r f a c e ) 。几何体集 合空间数据类型保证了g i s 空间数据类型在几何操作上的闭合性1 1 6 - 1 7 1 ( c l o s u r e ) ，这些 操作包括几何并、几何差或集合交操作。图1 1 描述了用u m l 符号表示的二维空间几何体 的基本构件及其相互关系，当然这些关系也可以用在三维空间中。 图1 1g i s 的关于窄间几何体的草本构件 1 2 2 空间数据的复杂特性“洲“ 由于空间属性的存在，空间的对象才具有了空间位置和距离的概念，并且空问对象 3 特征的变化可以影响它其余特征或者邻近空间对特征的变化，同时，空间对象之间还包 括拓扑关系、方位关系，而且度量关系还与空间位置和个体之间的距离有关，因此空间 数据之间的关系类型因此也就更为复杂，这些使得空间数据比其它类型的数据要复杂得 多。空间数据的复杂性特征主要表现在以下几个方面： 1 空间属性之间的非线性关系 空间属性之间的非线性关系是空间系统复杂性的重要标志，在多维空间中， 一个对象多个属性、多个对象单个属性、多个对象多个属性之间的关系中有的是 相互对立的，但是有的是彼此相关的，因此空间属性之间蕴涵着系统内部作用的 复杂机制，因而提取其之间的关系被作为空间数据挖掘的主要任务之一。 2 空间信息的模糊性 空间数据复杂性的另一个特征就是模糊性。模糊性几乎存在于各种类型的空 间信息中，如空间位置的模糊性、空间相关性的模糊性以及模糊的属性值等等。 3 空间数据的多尺度特征 空间数据的多尺度性是指空间数据在不同观察层次上所遵循的规律以及体 现出的特征小尽相同。多尺度特征是空间数据复杂性的又一表现形式，利用该性 质可以探究空间信息在概化和细化过程中所反映出的特征渐变规律。 4 空间数据的缺值 数据的缺值现象源自山于某种不可抗拒的外力而使数据无法获得或发生丢 失，空间数据也小可避免很多项会缺值。如何对丢失数据进行恢复井估计数据的 固有分布参数，成为解决数据复杂性的难点，其大致可以分为两步：首先利用各 种统计手段模拟出缺失值，然后再利用包含己知观测值和模拟出的缺失值的全集 进行统计分布函数的参数估计。用于产生缺失值的方法包括均值转嫁、有补充的 随机替代、无补充的随机替代，时问序列转嫁、完全均位转嫁等。 5 空间维数的增高 空间数据的属性增加极为迅速，如在遥感领域，由于传感器技术的犯速发展， 波段的数目也山几个增加到几十甚至上百个，如何从几十甚至儿百维空间中提取 信息、发现知识则成为研究中的又一难题。型数据的挖掘方法之间存在明显的差 异从而也使得空间数据挖掘比一般的数据挖掘更复杂、困难“2 ”。 4 1 3 分类挖掘m 1 3 1 基于关系数据库的分类挖掘 1 3 1 1 什么是分类 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类要解决的 问题是为一个事件或对象归类。在使用上，既可以用此模型分析己有的数据，也可以用 它来预测未来的数据。例如，用分类来预测哪些客户最倾向于对直接邮件推销做出回应， 又有哪些客户可能会换他的手机服务提供商，或在医疗领域当遇到一个病例时用分类来 判断一下从哪些药品着手比较好。 分类挖掘算法的工作方法是通过分析已知分类信息的历史数据总结出一个预测模 型。分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为每一个 类找到一种准确的描述或者模型。这种描述常常用谓词表示呻】。由此生成的类描述用来 对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以 由此预测这些新数据所属的类。要构造分类器，需要有一个训练样本数据集作为输入。 通常是已经掌握的历史数据，如，已经不再接受服务的用户，你很可能还保存了他们在 接受服务时的历史记录。训练集也可以是通过实际的实验得到的数据，比如你从包含公 司所有顾客的数据库中取出部分数据做实验，向他们发送介绍新产品的推销信，然后 收集对此做出回应的客户名单，然后你就可以用这些推销回应记录建立一个预测哪些用 户会对新产品感兴趣的模型，最后把这个模型应用到公司的所有客户上。训练集由一组 数据库记录或元组构成，每个元组是个由有关字段( 又称属性或特征) 值组成的特征向 量，此外，训练样本还有一个类别标记。一个具体样本的形式可为：( v 。，v ：，p 。：c ) ： 其中v i 表示字段值，c 表示类别。 例，信用卡系统的信用分级是分类的典型应用。图1 2 和图1 3 描述了信用分级系统 的运行机制。 图i 2 生成分类规则 图1 3 用分类规则进行分类 我们可以看到：这是一个分两步走的过程，第一步是利用训练数据集进行学习的过 程，第二步是进行模型评估，降低模型噪音并投入实际运行的过程。 1 3 1 2 分类挖掘的方法 1 3 1 2 1 一般的分类挖掘方法 分类器的构造方法d 9 2 4 有统计方法、机器学习方法、神经网络方法等等。统计方法 包括贝叶斯法和非参数法( 近邻学习和基于事例的学习) ，对应的知识表示为判别函数和 原型事例。机器学习方法包括决策树法和规则归纳法，前者表示为决策树或判别树，后 者则一般为产生式规则。神经网络方法主要是b p 算法，它的模型表示为前向反馈神经网 络模型( 由代表神经元的节点和代表连接权值的边组成的一种体系结构) ，b p 算法本质卜 是一种非线性判别函数。另外，最近又兴起了一种新的方法：粗糙集( r o u g hs e t ) 方法， 其知识表示是产生式规则。实际上最常用的分类方法仍然是传统的决策树方法，基于关 系数据库的决策树分类算法中，有很多是比较著名的，如i d 3 ，c 4 5 ，c a r t ，考虑到伸 缩性的s l i q ，s p r n t ，r a i n f o r e s t 框架等 3 7 - 3 8 1 ，在这些算法中，有的是边建树边剪枝，有 的是先建树后剪枝。已有的剪枝方法有代价复杂性剪枝、减少错误剪枝、悲观估计剪枝 及基于m d l 的剪枝法。 不同的分类器有不同的特点。有三种分类器评价或比较尺度： 1 预测准确度： 2 计算复杂度： 3 模型描述的简洁度 预测准确度是用得较多的一种比较尺度，特别是对于预测型分类任务，目前公认的 方法是l o 番分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境。在数据挖 掘中，由于操作对象是海量的数据库，因此空间和时间的复杂度问题将是非常重要的一 个环节。对于描述型的分类任务，模型描述越简洁越受欢迎，例如，采用规则表示的分 类器构造法就更为有用，而神经网络方法产生的结果则难以理解。 另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的数据 有缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的属性是 连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。 1 3 1 2 2 决策树分类法 决策树( d e c i s i o nt r e e ) 是一个类似于流程图的树结构，其中每个内部节点表示在 一个属性上的测试，每个分枝代表个测试的输出，而每个树叶节点代表类或类分布。 树的最顶层节点是根节点。一棵典型的判定树如图1 4 所示。它表示概念b u y s c o m p u t e r ， 它预测a 11 e l e c t r o n i c s 的顾客是否可能购买计算机。内部节点用矩形表示，而树叶节点 用椭圆表示。为了对未知的样本分类，样本的属性值在判定树上测试。路径由根到存放 该样本预测的叶节点，判定树容易转换成分类规则。 图1 4 决策树 决策树分类的基本算法是贪心算法，它以自顶向下递归的各个击破方法构造决策 树。算法概述在图1 5 中，是一种著名的判定树归纳算法i d 3 版本。算法的策略如下： 树以代表训练样本的单个节点开始。 如果样本都在同一个类，则该节点成为树叶，并用该类标记。 否则，算法使用称为信息增益( i n f o r m a t i o ng a i n ) 的基于熵的度量作为启发信息， 选择能够最好地将样本分类的属性。该属性成为该节点的“测试”或“判定”属 性。在算法的这个版本中，所有的属性都是分类的，即取离散值的连续值的属 性必须离散化。 对测试属性的每个己知的值，创建一个分枝，并据此划分样本。 算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现 在一个节点上，就不必考虑该节点的任何后代。 递归划分仅当下列条件之一成立时停止： 1 给定节点的所有样本属于同一类。 2 没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。 这涉及将给定的节点转换成树叶，并用s a m p l e s 5 6 多数所在的类标记它。换一种 方式，可以存放节点样本的类分布。 3 分枝t e s ta t t r i b u t e = a ，没有样本。在这种情况下，以s a m p l e s 中的 多数类创建一个树叶。 8 算法：g e n e r a t e _ d e c i s i o nt r e e 由给定的训练致据产生一掇判定树 输入：训练样本s a m p l e s 由彦数值属性表示 候选属性的集台a t t r i b u t el i s t 输出：一棵判定树 方法： 1 ) 刨建节点n ； 2 ) i f s a m p l e s 都在同一个类c t i 拂n 3 ) 返回n 作为父节点，以类c 标记； 4 ) i fa t t r i b u t el i s t 为空t h e n 5 ) 返回n 作为叶节点，标记为s a m p l e s 中最普通的类l 6 ) 选择s m i b u 把j i s t 中具有最高信息增盏的性作为l e s tm t r i b u l e ： 7 ) 标记节点n 为t e s t 叭曲u l e ： 8 ) f o re a c ht e s ta u r i b u 钯中的已知值 9 )由节点n 长出一个条件为t e s t 的分枝：_atmbute鼍 10 ) 设s i 是s a m p l e s 中l e s t 神研b 懒的撵本的集合l 】1 ) i f s i 为空t h e n 1 加上一个树叶标记为s a m p l e s 中最普通的类； 1 3 ) e l s e 加上一个由o 哪岫d e d s j 啦坤自越灯i b u t e j i s t 。吲a 蛐b u 哟返回的节点 图1 5 决策树贪心算法 在树的每个节点上使用信息增益( i n f o r m a t i o ng a i n ) 度量选择测试属性。这种度量 称作为属性选择度量或分裂的优良性度量。选择具有最高信增益的属性作为当前节点的 测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小 随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到 最小，并确保找到一棵简单的( 但不必是最简单的) 树。 设s 是s 个数据样本的集合。假定类属性( c l a s sl a b e l ) 具有m 个不同值，定义1 1 1 个不 同的类e ：( i = l ，m ) 。设只是类c f 中的样本数。对一个给定的样本分类所需的期望信 息由下式给出： 。( s l s s 2 ，- , s m ) 2 一善_ p l * 1 0 9 z p j ( 1 1 ) 其中p ：是任意样本属于类c i 的概率，并用5 。s 估计。注意，对数函数以2 为底，因 为信息用= 进制编码。 设属性a 具有v 个不同值( 口。，口：，口。) 。可以用属性a 将s 划分为v 个子集 s 9 s z ，s 。 ：其中，s ，包含s 中这样一些样本，它们在a 上具有值口。如果a 选作测试属 性( 即最好的分裂属性) ，则这些子集对应于包含集合s 的节点生长出来的分枝。设5 i 是 子集s ，中类c ，的样本数根据由a 划分成子集的熵( e n t r o p y ) 或期望信息由下式给出 刚) 2 毫卫竽s l j , ，s m j ) 项( 岛十“+ s 州) s 充当第j 个子集的权，并且等于子集( 即a 值为a j ) 中的 样本个数除以s 中的样本总数。熵值越小，子集划分的纯度越高。注意：对于给 定的子集氐 7 ( s ，s ：，。，5 吲) 。, 善p o1 0 9 ：( p ) 其中，p = 岛1 s j l ：是s ，中样本属于类g ，的概率。 在a 上分枝将获得的编码信息是 g a i n 口) = l ( s 1 ，s 2 ，s ，) 一e ) ( 1 2 ) ( 1 3 ) ( 1 4 ) 换言之，g a i n ( a ) 是由于知道属性a 的值而导致的熵的期望压缩。 算法计算每个属性的信息增益。具有最高信息增益的属性选作给定集合s 的测试属 性。创建一个节点，并以该属性标记，对属性的每个值创建分枝，并据此分样本。 1 3 2 空间分类挖掘 1 3 2 1 什么是空间分类 空间分类指分析如地区、高速公路或河流的邻域等的空间对象而导出与空间特征有 关的分类模式，如需要根据平均家庭收入将地区按贫富分类就是一典型的空间分类问 题。空阃分类的目的是在空间数据库对象的空间属性和非空属性之间发现分类规则，它 与基于关系数据库的分类之间的最大区别在于分析间对象时不仅要考虑目标对象的非 空间属性，而且还要考虑其邻接对象的非空属性对它类别的影响。空问分类是近年来数 据挖掘领域中比较活跃的一个方向。 1 3 2 2 空间分类挖掘的相关工作 在空问分类挖掘中常常使用决策树方法。f a y y a d 等人使用决策树的方法对星形结构 对象的图像进行分类，从而探测星与银河。他们的方法是使用f o c a s 系统为选中的对象， 例如天空图像，生成区、方向等的基本属性。训练集中的对象由宇航员来分类，基于这 些分类，构成于决策树算法的十个训练集。决策树是通过学习算法得到的。最后，由决 策树成一个健壮、通用、正确的最小分类规则集合。该方法处理的是图像数据库，应用 于天文研究领域。但它却不善于处理常用于g i s 的向量数据格式。 e s t e r 等人在邻接图理论的基础上提出了一个基于i d 3 算法的空间分类算法。算法不 仅考虑了待分类对象的非空间属性，同时也考虑了其邻接对象的非空间性对其分类的影 响。只要是满足任何一种邻接关系的对象都会被看成是邻接对。但是，该算法却不具备 分析邻接对象非空间属性聚合值和进行相关分析的能力，并且没有考虑到非空间属性和 空间属性之间可能存在的概念层次关系。因此，p e r s k i 等人提出了一个高效的两步分类 算法：第一步：通过较少代价的空间计算获得一个近似的空间谓词，在这个阶段同时进行 相关分析：第二步，对模型进行进一步的精确计算，从而获得一个更小、更精确的决策 树。 1 4 本文结构 全文共分为五章。 第一章是绪论，概括性的介绍了空间数据挖掘的背景以及空间分类挖掘的常用算 法。 第二章是技术基础，介绍可拓学以及支持向量机的基本概念。 第三章介绍了属性相关分析，将可拓学基元理论应用与空间对象的位置关系的描 述。 第四章提出了一种基于距的二插树多类s v m 分类算法。并且给出具体的算法步骤， 以及实验及其结果。 第五章对整篇文章作了一个总结。 第2 章技术基础 2 可拓学的逻辑细胞及基本概念2 3 嘲嘲嘲 2 1 1 可拓学的逻辑细胞 要利用形式化方法处理客观世界中的各种矛盾问题，首先必须研究如何描述客观世 界中的种种事物。客观世界由万物构成，物的各种特征描述了它的各个侧面，物及其相 互联系构成了世界的静态结构。另一方面，万物之间的相互作用使它们处于运动和变化 之中，物与物之间的相互作用称为事。物、事以及它们之间的关系，构成了五彩缤纷、 变化力千的动态世界。要研究世界，就要从研究物、事和关系的各个侧面开始，通过对 它们的分析，使我们可以描述世界的各种事物，进而描述各种矛盾问题。 一物具有多个特征，这些特征由特征的名称及相应的量值所构成。因此，由物n 、 特征和量值，这三个要素组成的物元月一o v ，c ，p ) ，就成为描述物的基本元1 1 1 。物元的概 念把物及其特性构成一个统一体来考虑，物与量的统一使我们可以方便地去描述客观世 界中各种各样的物。类似地，我们建立了事元和关系元的概念，事元和关系元描述事和 关系的各个侧面。 在可拓学中，建立了以物元、事元和关系元为基本元的形式化描述体系，物元 r ，( n ，c ，v ) ，事元，1q ，b ，h ) 和关系元q 一( 5 ，n ，w ) ，就构成描述千变万化的大干世界的 基本元，统称为基元弘i 。基元具有很多重要的性质，它们形成了基元理论。用这种理论 可以简洁地表示客观世界中的物、事和关系，便于计算机处理。基于这种形式化体系来 表达信息、知识和问题等的模型，称为可拓模型。可拓模型既描述了事物的数量关系， 又考虑事物的质的方面。 可拓学的逻辑细胞是基元，包括物元、事元和关系元。 2 1 2 基元理论 2 。1 2 1 物元的概念 定义2 1把物n ，特征c 及n 关于c 的量值v 构成的有序三元组 r = ( ，c ，v ) 1 2 作为描述物的基本单元，称为一维物元，n ，c ，v 三者称为物元r 的三要素，其中c 和v 构 成的二元组 m = ( c ，v ) 称为物n 的特征元。为方便起见，把物元的全体记为( r ) ，物的全体记为( n ) ，征的全 体记为( c ) 。关于特征。的取值范围记为v ( c ) ，称为c 的量域。 一物具有多个特征，规定 定义2 2 物n 有n 个特征c 1 ，c 2 ，c 。以及n 关于c ，( i = 1 ，2 ，n ) 对应的量值 v ( i = l ，2 ，r 1 ) 所构成的阵列 称为n 维物元，其中 r ； n ，c 1 ，v 1 1 。嚣_ 刈，c ， c ，ki c 互 卜 墨= 蒸馏水a 翥篇：篡姜】 r 2 - l直径，6 e r a 3 0 c m i 工件b ，长度，1 i重量，2 k gi ( 2 1 ) ( 2 2 ) ( 2 - 3 ) r ( t ) = ( n ( t ) ，c ，v ( t ” 来描述。类似地，物也随空间位置和其他条件的改变而改变。为此，我们定义了参变量 物元。 定- s l 2 3 在物元r ：( ，c ，v ) 中，若n ( t ) 是参数t 的函数，称r 为参变量物元， 1 3 记作 r ( t ) = ( n ( t ) ，c ，v ( t ) ) ( 2 4 ) 这时， v ( t ) ，c ( n ( t ) ) 。为了书写方便起见，再不引起混淆的地方，省略参数t ，简记为 v = c ( n ) ，它描述了物与量之间的关系。 对于多个特征，有多维参变量物元，记作： r ( t ) n ( t ) ， c 1 ，v i ( t ) c 2 ，v 2 ( t ) mm c 。，v 。( t ) 昔( n ( t ) ，c v ( t ) ) ( 2 5 ) 给定一物，它关于任一特征名都有对应的量值，并且在同一时刻是惟一的。当该量 值不存在时，用空量值0 表示。如果物关于特征c 的量值为非空量值，称c 为的非空 特征，对应的特征元称为非空特征元。 定义2 4 称物的切非空特征所对应的物元 n ，c 1 ，v 1 1 m 划 hi 娩- 6 m 划 为物的全征物元，记 f g c p r ( n ) 。全征物元表达了物和物元的关系tc p r ( n ) 。 在确定的时刻，物的全征物元是惟一的。对任意两个不同的物l 和。，至少可 以找到一个特征c ，使c ( 。) _ c ( n ：) 。 对两个物元r = ( l ，q ，h ) ，r 2 2 ( n 2 ，c 2 ，v 2 ) 当且仅当l = n 2 ，q = c 2 ，v l = v ：时，称 r ，和r ：相等，记作蜀= r ：。 物元的基本要素： 1 物 ( 1 ) 物的分类 客观世界中存在各种各样的物，它们都有许多特征。物由于特征的差异形成了 各种不同的类，特征值在确定范围内( 或确定值) 的某些物形成了一类，其他跳则不 1 4 属于该类。 按照物的外延，物可以分为类物和个物：按物的存在性，物分为存在物和期望 物：按物的系统性，物又分为聚合物和系统。 1 ) 类物和个物 类物是反映一类对象的概念，它的外延是指一类对象中的每一个个体。也就是 说，类物的外延是由一些对象组成的，它的外延是指许多个体组成的类。例如，“茶 杯”、“人”、“汽车”、“有理数”、“多边形”、“原子”等等。类物的外延 所指的物数量是不定的，一般说来，是不计其数的。个物是反映单个对象的概念。 它的外延是指个独一无二的对象。例如，“北京市”、“亚洲最大的国家”、“张 三”、“大象爿”等等。 2 ) 存在物和期望物 现在存在或过去存在过的物n ，称为存在物，记作号，假设的、尚未实现的或 者是幻想的、期望的物，称为期望物。存在物的全体记作，( n ) ：期望物的全体 记作：( ) 。显然，一切物的全体 ( n ) 一1 ( ) y 2 ( ) ( 2 7 ) 3 ) 聚合物和系统 物，如果它的各个组成部分之间没有相互作用( 或者没有明显的相互作用) ， 没有有机的联系，则认为该物缺乏整体性和质的新颖性。这类物称为聚合物。例如， 一盘散沙、一堆石头等。反之，一物，如果它的组成部分之间存在着相互联系和相 互作用，以至于产生了其组成部分本身所不具有的整体性和质的新颖性，则称之为 系统。例如，由氢和氧原子结合而成的水分子、一问工厂等。 ( 2 ) 物的四对共扼部及其物元表示 对物的结构的研究，有助于利用物的各部分去解决矛盾问题。系统论从系统的组 成部分和内外关系去研究物。通过对客观世界中的物的分析，我们发现，除了系统 性以外，物的结构还可以从物质性、动态性和对立性去研究。从物质性考虑，物n 由虚部i r o n 和实部r e n 所组成：从系统性考虑，物由软部和硬部h r n 所组成： 从动态性考虑，物由潜部l t n 和显部a p n 所组成：从对立性考虑，物n 由关于特征 名的负部鸭。n 和正部p s 。n 所组成。也就是说，物的结构可以表示为 = i r o n o r e n = s t i r ( 9 h r n i t n a p n = ，l g 。o 芦。n ( 2 - 8 ) 这个式子表明，物的结构可以从四个角度进行研究，而每一个部分c p ( c ) ) 可 以具有不同的特征，用物元表示为 ( r ，c ，v ) 其中f e i m n ，r e n ，s i n ，h r n ，l t n ，a p n ，n g 。n ，p s 。) 。若r 具有多个特征，则表示为 r 1 r ，c l ，p 1 1 。兹_ c 绷， l or - ，i 2 特征元 凡能表示物的性质、功能、行为状态以及物间的关系等征象的都是物的特征。一物， 具有各种各样的特征元。 ( 1 ) 特征元的涵义 对于物的了解，表现在对该物的特征的了解。掌握了某物具有哪些特征或不具 哪些特征，也就有了关于该物的知识。 例如 m 1 = 颜色， 比重， 原子量， 化学性质， 白色 7 8 6 5 5 8 4 7 活泼 m ，是“铁”的特征元，记作m ，| 铁。显然，m ：= ( 熔点，3 0 0 0 c ) 不是“铁”的特征元， 记作肘，陡铁。 ( 2 ) 本质特征元和非本质特征元 特征元分为本质特征元和非本质特征元。人们在长期的实践活动中，在感性认 识的基础上，运用比较、分析、综合、抽象和概括等方法，抽象出一类物所具有、 它类物所不具有的那些特征元，称为物的本质特征元。例如，等腰三角形这一概念 所反映的物的特征有三条边、三个顶点、三个内角、二边相等，记 其对应的物元为 m ( 等腰三角形) = rl 边数，3 顶点数，3 内角数，3 等边数，2v3 等腰三角形，边数， 3 顶点数，3 内角数， 3 等边数，2 v3 r 或m 中前三个特征元是所有三角形都具有的，而( 等边数，2v3 ) 这个特征元是等 腰三角形所特有的，它能把等腰三角形与其它三角形区别开来，所以，它是等腰三角形 这一概念所反映的物的本质特征元。( 边数，3 ) ，( 顶点数，3 ) ，( 内角数，3 ) 是它反映的 物的特征元，但非本质特征元。 ( 3 ) 特征元的分类 从使用的角度考虑，特征元又可分为三种类型： 1 ) 功能特征元。描述物的作用或用途等的特征元称为功能特征元。如运输能力 和发光程度等。 2 ) 性质特征元。描述物的性质的特征元称为性质特征元。如酸碱度和导电率等。 3 ) 实义特征元。描述物的物质性部分的特征元称为实义特征元。如长、宽、重 量和体积等。 3 量值 一物关于某一特征的数量、程度或范围，成为该物关于这一特征的量值。量值分为 数量量值和非数量量值。用实数及某一量纲来表示的量值称为数量量值，不是使用实数 来表示的量值称为非数量量值。非数量量值可以通过数量化变为数量量值，以便进行定 量计算。4 4 0 ，1 0 0 c m 和3 7 。c 是数量量值：甲级、黑色、优等是非数量量值。 2 1 2 2 事元的概念 物与物的相互作用称为事，事以事元p _ 6 1 来描述。 定义2 5 把动词d 、动词的特征b 及d 关于b 所取得的量值l l 勾成的有序三元组 ，= ( d ，b ，“) 作为描述事的基本元，称为一维事元。与物元类似，称( b ，u ) 为事元i 的特征元。 动词的基本特征有：支配对象、施动对象、接受对象、时间、地点、程度、方式、 工具等。 定义2 6 动词d ，n 个特征6 。，b ：钆和d 关于6 ，b ：，b 。取得的量值 “1 ，“2 ，u 。构成的阵列 称为l q 维事元，其中 d ，b l ，1 1 6 蔷刊嘏蹦盘 “。 b = ( 2 一1 0 ) 定义2 7若i = ( d b ，u ) 中，d 和u 是某参数t 的函数，称i 为参变量事元，记作 i ( t ) = ( d ( t ) ，b ，u ( t ) ) 对多维事元，有 i ( t ) = ( d t ) ，b ，u ( t ) ) 给定事元l = ( d 。，b 1 ，u 1 ) ，j 2 = ( d2 ，b 2 ，2 ) ，称l 和j ：相等，当且仅当d 1 3 d2 ，b 1 = b 2 ， u i = u 2 ，记作1 1 = j 2 。 2 1 2 3 关系元的概念 在大干世界中，任何物、事、人、信息、知识等与其他的物、事、人、信息、知识， 都有千丝万缕的关系。由于这些关系之间又有互相作用、互相影响。因此，描述它们的 物元、事元也与其他的物元、事元有各种各样的关系，这些关系的变化也会互相作用、 互相影响。关系元是描述这类现象的形式化工具。 定义2 8 以关系词或关系符( 简称关系名) s 、n 个特征口，a ：，a 。和相应的量值 w i ，w 2 ，h 构成的n 维阵列 w 1 w 2 m w ；( s ，a ，) t q 用于描述w 。和m 的关系，称为n 维关系元，其中 4 = ，w 一 ( 2 1 1 ) a 。和n ：分别表示前项和后项，a ，表示程度，a 。，a 分别表示关系名s 的其他特 征。例如 q _ 借贷关系，前项， 后项， 程度， 维系方式， 联系通道， 联系方式， 地点， 公司一 银彻 1 0 0 0 万元 合同 经理c 科长d 电话v e m a i l e 市 描述了公司a 向银行b 贷款1 0 0 0 万元形成的借贷关系。 而 q 一 朋友关系，前项， 后项， 程度， 维系方式， 联系通道， 联系方式， 地点， 爿 口 密切 感情 直接见面 谈话 d 地 描述了a 和b 的朋友关系。 在卜述特征中，n 。，n ：，n 。是常用的基本特征，它们表述了关系的对象及其程度。 m s 悱以加以肌悱竹 卯舻缸彩绯却 j 定义2 9 在关系元q 中，若q 描述的关系是某参数t 的函数，称 q p ) = s o ) ，a l ， n 2 m 以n ， m w ，o ) w 2 ( f ) m ( f ) m ( 2 1 2 ) 为参变量关系元。参变量关系元描述了w 。和w ：的关系s 随参数t 的变化而变化，当t 是时 间参数时。q ( t ) 描述了w l 和w ：的关系s 随时间r 的改变而产生的动态变化( 包括关系程度 的变化) 。不同的人、事、物的影响也使关系产生变化，这些变化表现为关系程度的改