（计算机应用技术专业论文）基于决策树算法的多关系数据分类研究.pdf

学位论文版权使用授权书 i u i i ii ii ii i iii ii i ii iiiil y 17 8 0 4 8 1 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 篇沈驷 厉一“ 氰 年 签 加 者 加 作 ： 文 期 沦 日 位 字 学 签 中图分类号：t p l 8 2 u d c ：0 0 4 8 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 基于决策树算法的多关系数据分类研究 m u l t i r e l a t i o n a lc l a s s i f i c a t i o nb a s e do nd e c i s i o nt r e ea l g o r i t h m 作者姓名：黄昆 导师姓名：林友芳 学位类别：工学 学号：0 6 1 2 0 5 2 8 职称：副教授 学位级别：硕士 学科专业：计算机应用技术研究方向：数据与知识工程 北京交通大学 2 0 10 年6 月 r k 卜 - l l 的适应关系数据库中多关系的数据组织，很好的完成挖掘任务。因此本文以多关 系数据挖掘算法作为研究对象。 对于多关系数据挖掘算法而言，高效性和可扩展性一直是该领域的研究重点。 因为多关系数据挖掘任务的复杂性对算法性能提出了更高的要求，同时，由于在 多关系模式下，算法的搜索空间比单一关系模式下变得更大，更复杂。对于每个 优化假设的评价也更为复杂。针对多关系数据挖掘算法存在的这些问题，本文的 研究重点放在了提高多关系数据挖掘算法的效率上。 制约多关系数据挖掘算法的瓶颈在于搜索空间的大小，因此提高效率的关键 在于减少搜索空间的大小。本文以多关系数据分类算法为切入点，用决策树算法 建立多关系分类模型实现多关系数据分类的目标。在提高算法效率上面，本文主 要做了以下的工作： 在多关系决策树算法中加入充分表，减少了对每个假设模式评价过程中，所 需连接数据表的数量。同时，引入目标元组i d 传播技术，使得每个假设模式评价 过程的连接都不浪费，即使该模式不是最优的，也会进行目标元组i d 的传播，从 而保留该连接信息。使得算法模式评价的效率有所提高。 使用p k d d 9 9 中的f i n a n c i a l 数据集对改进的多关系决策树算法进行了实验， 通过十次交叉迭代验证法证实了充分表结构和目标元组传播技术对提高多关系 决策树分类算法运行效率是有帮助的。 本文的最后，提出继续对多关系决策树算法效率的改进的一些展望，可以在 状态空间的搜索算法以及利用数据集背景知识等方面继续做出改进。 关键词：关系学习；多关系数据挖掘；决策树分类；多关系决策树算法；目标元 组i d 传播 分类号：t p l 8 2 0r i p a bs t r a c t a b s t r a c t ：m u l t i - r e l a t i o n a ld a t am i n i n gi so n eo ft h er a p i d l yd e v e l o p i n gs u b f i e l d so f d a t am i n i n g t h ec l a s s i c a ld a t am i n i n ga p p r o a c h e sc a no n l yl o o kf o rp a t t e r n si ns i n g l e r e l a t i o n , a n di t i sd i f f i c u l tt ol o o kf o rc o m p l e xr e l a t i o n a lp a t t e r n sw h i c hi n v o l v e di n m u l t i r e l a t i o n a ld a t a b a s e s b u ti nr e a lw o r l d ，t h eo r g a n i z a t i o n so fd a t au s u a l l yu s et h e m u l t i r e l a t i o n a lm o d e l si nr e l a t i o n a ld a t a b a s e s s ot h ec l a s s i c a ld a t am i n i n ga p p r o a c h e s a r en o ts u i tf o rt h i ss i t u a t i o n t h a ti sw h yt h i sp a p e rc h o o s e sam u l t i r e l a t i o n a ld a t a m i n i n ga l g o r i t h ma so u rr e s e a r c ho b j e c t e f f i c i e n c ya n ds c a l a b i l i t yh a v ea l w a y sb e e ni m p o r t a n tc o n c e r n si nt h ef i e l do fd a t a m i n i n g t h ec o m p l i c a t i o no fm u l t i r e l a t i o n a ld a t am i n i n gh a sm a d eh i g h e rd e m a n d s ， b e c a u s eo ft h el a r g e rh y p o t h e s i ss p a c e sa n dt h em o r ec o m p l e xe v a l u a t i o nm e t h o d s s o w ef o c u so nt h ei m p r o v i n go fe f f i c i e n c ya n ds c a l a b i l i t yo ft h em u l t i r e l a t i o n a ld a t a m i n i n ga l g o r i t h m t h em a i nb o t t l e n e c ko fi m p r o v i n ge f f i c i e n c yo ft h ea l g o r i t h mi st h e s i z eo ft h e h y p o t h e s i ss p a c e t h e r e f o r e ，t h ek e yt oi m p r o v ee f f i c i e n c yi sd e c r e a s i n gt h es i z e i nt h i s p a p e rw et a l ka b o u tm u l t i - r e l a t i o n a lc l a s s i f i c a t i o na p p r o a c hb a s e do nt h ed e c i s i o nt r e e a l g o r i t h m w ei m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h mo nt w oa s p e c t sa sf o l l o w s f i r s to fa l l ，w eu s eas u f f i c i e n tt a b l et or e d u c et h en u m b e ro ft a b l e sw h i c hw i l lb e j o i n e di ne a c hh y p o t h e s i sm o d e li nt h ee v a l u a t i o np r o c e s s i na d d i t i o n ，t h et a r g e tt u p l e i d p r o p a g a t i o na p p r o a c h i su s e dt os a v et h ec o n n e c t i o ni n f o r m a t i o n , t h u st h e c o n n e c t i o n sw i l ln o tb ew a s t e de v e ni f t h eh y p o t h e s i sm o d e li sn o t o p t i m a l f i n a l l y , i nt h i sp a p e rp r o p o s e san e wm u l t i r e l a t i o n a lc l a s s i f i c a t i o na l g o r i t h ma n d e x p e r i m e n t so nt h ep k d dc u p 9 9f i n a n c i a ld a t as e t t h ee x p e r i m e n t a lr e s u l t ss h o w t h a to u r a l g o r i t h mi m p r o v e st h ee f f i c i e n c yo fm r d t lo b v i o u s l y k e y w o r d s ：r e l a t i o n a ll e a r n i n g ；m u l t i r e l a t i o n a ld a t am i n i n g ；d e c i s i o nt r e e c l a s s i f i c a t i o n ；m u l t i r e l a t i o n a ld e c i s i o nt r e e ；t a r g e tt u p l ei dp r o p a g a t i o n c l a s s n o ：t p l8 2 r 0 li 目录 中文摘要i i a b s t r a c t i i i 1 引言1 1 。l数据挖掘与知识发现。1 1 2数据分类。2 1 2 1 概j 丕。2 1 2 2 决策树分类3 1 3 关系数据挖掘的产生和背景6 1 4研究目标。8 1 5 论文的结构组织9 2多关系数据挖掘的一般方法。1 0 2 1 归纳逻辑程序设计：1 0 2 2统计关系学习1 3 2 3关联分析1 4 2 4利用数据库查询技术的i l p 算法1 4 3多关系决策树分类算法1 6 3 1关系数据库1 6 3 2多关系数据挖掘框架1 7 3 2 1 选择图。18 3 2 2 选择图的优化2 0 3 3多关系决策树学习算法m r d t l 2 5 3 4m r d t l 算法执行示例2 7 4 对m r d t l 算法的改进31 4 1问题的提出31 4 2改进m r d t l 算法设计思想31 4 3 m i t l 一2 算法3 2 4 4目标元组i d 传播技术3 4 4 5改进的m r d t l 算法3 7 4 5 1 改进算法的流程图。3 7 4 5 2 改进算法的伪代码3 9 4 6信息增益的计算4 0 ll卜f l r 5 实验部分4 2 5 1 实验环境_ 一4 2 5 2 实验数据4 2 5 3 实验结果4 3 5 4 实验分析4 3 6 结论一4 5 参考文献_ 4 6 独创性声明4 8 学位论文数据集4 9 l l 引言 1 1 数据挖掘与知识发现 随着数据库技术的成熟和数据应用的普及，人类积累的数据量正在以指数速 度迅速增长。特别是进入9 0 年代，伴随着互联网的出现和发展，人们可以跨越 时空地在网上交换数据信息和协同工作。这样，展现在人们面前的就不再是局限 于本部门、本单位、本行业的庞大数据库，而是浩瀚无垠的信息海洋。人们需要 有从大量数据资源中提取对各类决策有指导意义的一般知识的技术，这些知识是 对大量数据的高度浓缩与抽象，是对数据整体全面而深刻的认识。 从数据库中大量琐碎数据中提取隐含的、预测未知和潜在有用信息的知识发 现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 以及数据挖掘d m ( d a t am i n i n g ) 技术就 在这样一个时代背景下应运而生的，它们的目的就是分析处理数据库中的大量数 据，发现有用的知识，为用户提供所需问题的答案。 长期以来，k d d 和d m 这两个术语的范畴和使用界限一直不很清晰。因此， f a y y a d 等人给出了k d d 和d m 的确切定义。k d d 的定义为：从数据中辨别出 有效模式的非平凡过程，该模式是新颖的、潜在有用的和最终可理解的。而将 d m 定义为：知识发现过程中通过特定的算法在可接受的计算效率限制内生成特 定模式的一个步骤。k d d 系统由完成从访问数据库数据、使用模式提取算法、 直至评价和解释结果这一知识发现完整过程的所有组件的集成。k d d 过程可划 分为三个主要阶段：数据准备、数据挖掘、结果表达及解释。数据准备主要包括 数据集成、数据选择、数据预处理、数据转换等步骤；数据挖掘过程就是针对所 要发现任务的所属类别，设计或选择某个特定的数据挖掘算法进行处理，找出数 据中的模式；结果表达及解释是解释并评估发现的模式，去掉多余的不切题意的 模式，并将有用的模式以用户能理解的方式呈现。在整个知识发现过程中，数据 挖掘是核心步骤。由于知识发现过程中各部分之间的紧密相关和d m 技术的核 心作用，通常不严格区分k d d 和d m ，现在，人们倾向于将两者一起使用，成 为数据挖掘和知识发现( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ，简称d m k d ) d m k d 是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、 机器学习、模式识别、可视化和专家系统等。此外，依赖于所用的数据挖掘方法， 还涉及到其他学科的技术，如神经网络、模糊或粗糙集理论、知识表示、归纳逻 辑程序设计和高性能计算。数据挖掘发现的知识可以用在信息管理、过程控制、 科学研究、决策支持等许多方面。 从d m k d 可发现的知识类型看，主要包括以下几类知识： 广义知识根据数据的微观特性发现其表征的、带有普遍性的、较高层次 概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的概括、精炼和 抽象。 关联知识反映一个事件和其他事件之间依赖或关联的知识，这类知识可 用于数据库中的归一化，查询优化等。 分类知识反映同类事物共同性质的特征型知识和不同事物之间的差异 型特征知识。用于反映数据的汇聚模式或根据对象的属性区分其所属类别。 预测知识根据时间序列型数据，由历史的和当前的数据去推测未来的数 据，其实是一种以时间为关键属性的关联知识。 偏差型知识是对差异和极端特例的描述，揭示事物偏离常规的异常现 象，如标准类外的特例，数据聚类外的离群值等。 可用d m k d 的方法有很多种，主要有：统计方法、归纳方法、聚类分析方 法、关联分析方法、粗糙集方法、模糊集方法、决策树方法、证据理论方法、神 经网络方法、遗传算法方法等等。这些方法往往是结合在一起使用的。 1 2数据分类 1 2 1概述 分类在数据挖掘中是一项非常重要的任务。分类要解决的问题是为一个事件 或对象归类。通过建立一个模型，既可以用此模型分析已有的数据，也可以用它 来预测未来的数据。例如，在银行业，常常用分类来对客户的信用等级做出评价， 以作为贷款的依据，或者在邮件系统中，用分类辨认出哪一封邮件是垃圾邮件。 分类的目的是建立一个分类函数或分类模型( 也称作分类器) ，该模型能够 把数据库中的数据记录映射到给定类别中的某一个。分类还可用于预测，通过从 历史数据记录中自动推导出对给定数据分类的统一模式，建立分类器，从而通过 这个统一模式对未来数据的类别进行预测。 因此，要构建一个分类器，需要有一个训练样本数据集作为输入，也就是历 史数据。训练样本数据集也称为训练集，一般是由一条条的数据库记录组成的。 每条记录包含若干属性，组成一个特征向量。训练集的每条记录还有一个特定的 类标签( c l a s sl a b e l ) 与之对应。该类标签就是分类的一个标准，通常是一些经 验数据或实际实验数据。一个具体样式的形式可为样本向量：( v ，y ：，v 3 一。，v 矗；c ) 。 v ，表示字段值，c 表示类别属性的值。 2 分类可描述为：给定一个训练集t 。t 中的记录有若干个属性描述，在所有 属性中有且仅有一个属性作为类别属性。属性集合用矢量x = ( x ，毪) ，表示， 其中x ( 1 i n ) 对应各非类别属性，可以有不同的值域，即对任一属性 k = ( x ”。) ，氇随属性的不同而变化。当一个属性的值域为连续域时，该 属性称为连续属性，否则称为离散属性。用c 表示类别属性，c = ( c 】一，c k ) ， 即训练集t 有k 种不同的类别。那么t 就隐含地确定了一个从矢量x 到类别属 性c 的映射函数h ：厂( 石) oc ，分类的目的就是采用某种方法，或者称为模型， 将隐含的函数h 表示出来。 分类器的构造方法有很多种，如统计方法、机器学习方法、神经网络方法、 粗糙集方法等等，不同的分类器有不同的特点。有三种分类器的评价或比较尺度： ( 1 ) 预测准确度；( 2 ) 计算复杂度；( 3 ) 模型描述的简洁度。预测准确度是用 得最多的一种比较迟度，特别是对于预测型分类任务，目前公认的方法是1 0 次 交叉迭代验证法( 10 f o l ds t r a t i f i e dc r o s sv a l i d a t i o n ) 。计算复杂度依赖于算法具体 实现的细节和硬件环境。在k d d 中，由于操作对象是有海量数据的数据库，因 此空间和时间的复杂度问题将是非常重要的环节。对于描述型的分类任务，模型 描述越简洁越受欢迎；例如，采用规则表示的分类器就更有用，而神经网络方法 产生的结果就难以理解。 另外，分类的效果往往和数据的特点有关，有的数据噪声大，有的有缺省值， 有的分布稀疏，有的各属性间相关性强，有的属性是连续值。针对数据的各种情 况，目前没有一种分类方法能够适应于各种特点的数据。 1 2 2 决策树分类 决策树作为分类器的一种，是用树形结构来表示一个预测模型，代表了对象 属性与对象值之间的一种映射关系。决策树构建的输入是一组带有类别属性的 训练集，构建的结果是一棵二叉或多叉树。 该树的内部节点一般表示为一个逻辑判断，其形式为( 龟= v i ) ，其中a ；是非 类别属性，v i 是该属性的某个属性值；树的边是逻辑判断的分支结果。如i d 3 决 策树算法，该算法建立一颗多叉树，其内部节点是非类别属性，节点下的边是该 属性的所有取值，有几个属性值，就有几个分支。 决策树的每个叶子节点都对应一个类别属性c 的值：每个内部节点都对应 与一个用于分割数据集的属性k ，称为分割属性，分割属性为每一个可能的属性 值生成一个分支。这样，就把输入的训练集和划分成了多个子集合，该属性的每 一个值划分为一个子集合。若属性值不同，划分方法也不一样。如果x i 是连续属 性，那么其分割判断规则q 的形式为k x i ，其中每d o m ( x i ) ，毪就是该节点的 分割点；如果k 是离散属性，那么q l 的形式为x iey i ，其中x d o m ( x i ) ，x 就是 该节点的分割子集。 每一种决策树的算法，其分割属性的划分方法都有所不同，具有代表性的决 策树算法有c l s 、i d 3 、c a r t 、c 4 5 、s l i q 、s p r i n t 等。如i d 3 算法，就是 基于信息论的方法。在i d 3 建立决策树的过程中，选择分割属性采用了信息增益 啪标准。每次都选择信息增益最大的属性作为分割属性，递归地对训练集进行划 分，直至每个子集的记录全属于同一类别属性或某一类别属性占压倒性多数。建 立好决策树后，就可以由某条记录的非类别属性值在该决策树的路径走向的叶子 节点的所属类别预测该记录的类别属性值，也就实现了分类的要求。 如图1 2 就给出了一个基于图1 1 中数据的i d 3 算法决策树分类器。在计算 了o u t l o o k 、t e m p e r a t u r e 、h u m i d i t y 和w i n d y 各属性的信息增益后，发现o u t l o o k 属性的信息增益最大，选择o u t l o o k 属性作为第一个分割点，也就是根节点，然 后递归对分割后的每个子集中的属性计算信息增益，选择增益最大的属性作为分 割点，最后将整个训练集分成5 个子集。这颗决策树就可以用于鉴别o u t l o o k 、 t e m p e r a t u r e 、h u m i d i t y 、w i n d y 属性值组合不在训练集中的记录的类别属性是否 适合去玩了，沿着决策树取值走到叶子节点就可以判断出来。 4 图1 1 天气数据训练集 f i g u r e l 1w e a t h e rd a t as e t 图1 2i d 3 决策树 f i g u r e l 2i d 3d e c i s i o nt r e e 与其它的分类算法相比较，决策树算法有如下优点： ( 1 )速度快：计算量相对较小，且容易转化成分类规则。只要沿着根节 点向下一直走到树叶，沿途的分割条件就能够唯一确定一条分类规 5 则。 ( 2 )准确性高：挖掘出的分类规则准确性较高。 ( 3 )便于理解：该分类规则的语义式很容易翻译为人们理解的解释。 1 3关系数据挖掘的产生和背景 从历史的角度看，如同k d d 的早期发展受机器学习领域的研究影响一样， 关系数据挖掘也是在关系学习发展的背景下产生发展起来的。关系学习的核心方 法是归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n g ，i l p ) 。关系数据挖掘 ( r e l a t i o n a ld a t am i n i n g ，r d m ) 的起源，可以追溯到2 0 世纪9 0 年代初的i l p 研究。 从那时起，基于i l p 技术与思想便更新了传统的数据挖掘方法，大量的关系数据 挖掘算法和系统已经开发出来。 大多数经典的学习方法( 如决策树、朴素贝叶斯) 是属性值的学习 ( a t t r i b u t e v a l u el e a r n i n g ) 方法，历史上数据挖掘主要专注于这类学习方式。在属性 值学习情况下，每一个样例以属性值元组的形式表示。在这种形式下， 属性种类是固定的，每个属性有一个给定的值相对应，从而整个数据集可以被视 为关系数据库中的一个表或关系，表中的每一行相应于一个样例，而每一列相应 于一个属性。假设语言是命题逻辑语言，相应的命题以如下形式给出：“a t t r i b u t e 0v a l u e ，其中。是预先定义的一个操作符集和鼍 ，= ) 中的一个元素。因此， 属性值学习使用的算法又被称为命题化学习( p r o p o s i t i o n a ll e a r n i n g ) 算法。 而与上述情况相反，实际应用中的关系数据库为了有效地组织和访问数据， 数据以多关系的形式组织。一个样例信息由位于多个关系中的多个元组描述。进 一步来看，关系数据库中的结构表达了位于不同关系中的元组间的联系，而这种 联系体现了问题域中某些重要的背景知识和样例信息的结构内容。属性值学 习的单表假定无法直接利用这类联系及其蕴涵的信息内容，因而无法发现现实世 界数据中隐藏的更为复杂的模式。 虽然在理论上，多个关系表可以集成到一个单一关系表中，但是在实践中这 一方法存在许多问题。一般情况下，如果使用传统命题学习算法，组成一个关系 数据库的多个关系表就应该集成到一个单一关系表中。有如下两种方法实现这种 集成： ( 1 ) 在所有的关系上通过关系连接操作重构一个单一的泛关系。 ( 2 ) 为了避免冗余，可以在某些表上作聚合操作，所得聚合值代表这些表 中的信息加入一个核心关系表中，而这些表的原始元组不必加入。 对于第一种方法，实践起来存在着许多问题： 6 1 、计算泛关系的时空代价异常大。最终得到的泛关系中，存在大量冗余数 据，更为重要的是，整体数据量与原始数据比，异常地大一最糟情况下最终数 据量随数据库中原始关系数量与单一关系中元组数指数生长，这样加剧了海量数 据处理问题的难度。 2 、在多对一关系形成的泛关系中，一个样例由多行组成，按照属性值 学习方法的每一行代表一样例的假定，结果会出现语义偏差。另外，对于涉及自 连接的关系表，难以确定其连接深度。 3 、如果将样例的所有信息放入结果关系的单一元组中，则对于复杂数据库。 一方面会出现大量空值属性，另一方面，更为重要的是确定结果关系的全部属 性非常困难。 4 、数据重复导致统计偏差。 5 、属性值的学习效率非常低。 对于第二种方法，依然存在两个问题： 1 、许多细节信息在聚合操作后丢失了。 2 、聚合属性的选择需要对问题域有良好的理解，如果理解出现错误，那么 与使用细节信息的情况相比，结果会较差。 最后值得指出的是，属性值学习使用的命题逻辑知识表示方式在表达复 杂模式方面表达不简洁，表达力差。 因此，机器学习与数据挖掘技术明确地需要考虑学习任务的关系表示方式及 其相关搜索机制，即直接在多关系数据集上学习涉及复杂关系结构的模式。在机 器学习领域。这类学习问题及其解决方法被称为关系学y - j ( r e l a t i o n a ll e a r n i n g ) 。 在k d d 领域，这类挖掘方法的研究形成了多关系数据挖掘。如同k d d 的早期 发展受机器学习领域的研究影响一样，多关系数据挖掘是在关系学习发展的背景 下产生发生发展起来的。 近年来，关系数据挖掘方法引起了学术界的关注。在该领域，大多数的研究 集中在i l p 方面。同时也存在其他的方法，g e t o o r 、k n o b b e 提出了不基于逻辑 形式的方法，k e r s t i n g 提出了基于逻辑的、改进的i l p 方法【6 1 。 至今为止，已提出了一些关系数据挖掘算法，涉及了数据挖掘的各个方面， 例如，归纳逻辑程序设计系统c l a u d i e n 、i c l 和t i l d e 分别是传统的关联规则、 分类、决策树归纳算法的一阶扩展 2 7 1 ；最后，k n o b b e 提出的决策树归纳算法【4 】 是对t i l d e 的扩展。总之，以上的算法都遵循了这样一种方式：对传统的属性一 值算法进行更新来处理关系数据挖掘。 图1 3 中显示了传统命题学习算法和关系学习算法之间的一些关系。在下一 章将详细阐述。 7 re l a t i o n a il e a r n i n g a l g o r i t h m s s i n g l et a b l e m u i t i # et a l 磕e s i p r o p o s i t i o n a ll e a r n i n gl e a r n i n g i 下k bb 精_ a 致 c rl 廿f o b n f o i li c l p i p s i p w a r m r 图1 3 命题学习算法与关系学习算法之间的关系 f i g u r e l 3r e l a t i o n s h i p sb e t w e e np r o p o s i t i o n a la n dr e l a t i o n a ll e a r n i n ga l g o r i t h m s 图中算法简称注释： 掌幸：p r o p o s i o n a l i z a t i o n ( 命题化) d t ：d e c i s i o nt r e e n b ：n a 慨b a y e s b n ：b a y e s i a nn e t w o r k s a r ：a s s o c i a t i o nr u l e s c r ：c l a s s i f i c a t i o nr l l l e s i l p ：i n d u c t i v el o g i cp r o g r a m m i n g f o b n ：f i r s to r d e rb a y e s i a nn e t w o r k s f o i l ：f i r s to r d e ri n d u c t i v el o g i c 1 4研究目标 t i l d e ：t o p d o w ni n d u c t i o no f - f i r s t o r d e rl o g i c a ld e c i s i o nt r e e s i c l ：i n d u c t i v ec l a s s i f i c a t i o nl o g i c p i 蝴：p r o b a b i l i s t i cr e l a t i o n a lm o d e l p l p ：p r o b a b i l i s t i cl o g i cp r o g r a m b l p ：b a y e s i a nl o g i cp r o g r a m s l p ：s t o c h a s t i cl o g i cp r o g r a m m r d m ：m u l t i r e l a t i o n a ld a t am i n i n g n 衄t ：m u l t i - r e l a t i o n a ld e c i s i o nt 诧e 目前关系数据挖掘领域，大部分的研究都是基于i l p 技术的，但i l p 系统在 输入的限制使其在实际应用中有很大的局限，并且效率也不高。因此，人们开始 寻找一些新的方法，可以利用成熟的数据库技术，使得用户不再需要利用逻辑表 示问题，而是用熟悉的数据库的关系就可以表示。 但是，目前的多关系数据挖掘技术还不算成熟，其中亟待解决的问题就是效 率问题。k n o b b c 等人在文 4 】中描述了一个与关系数据库耦合较为紧密的多关系 数据挖掘框架及其计算体系结构。基于该框架，文 1 0 1 中提出了一种实现多关系 8 m ，趴 rm 决策树学习的算法( m r d t l ) ，该算法用s q l 查询得到优化模式评价中的各种 参数。随着关系数据关系模式复杂度的增长，该算法在将搜索空间中的模式转化 为s q l 命令时代价太高，效率很低。针对以上m r d t l 算法的种种不足，本文 主要研究了对多关系决策树分类算法在效率以及可扩展性上的一些改进，以提高 算法效率。其中主要包括 1 、探讨了m r d t l 的改进算法m r d t l 2 算法，在建立决策树之前构建一 个充分表用以减少转换s q l 命令时所需连接的表的数量。 2 、讨论了目标元组i d 传播技术以及该技术与m r d t l - 2 算法的结合，进一 步提高多关系决策树分类算法在模式评价计算中的效率，并且提出了一个融合目 标元组i d 传播技术以及增加充分表的对m r d t l 算法的改进算法。 1 5 论文的结构组织 本文主要基于多关系决策树分类算法方面，做了一些提高算法效率的改进工 作，进行了一些理论和实验的研究工作。除了第一章绪论介绍多关系数据挖掘研 究领域的背景外，全文共分6 章，主要内容组织如下： 第二章简述了多关系学习领域的基本理论和技术，主要介绍了多关系数据挖 掘的几种主要的方法与技术。 第三章具体描述了多关系数据挖掘框架及其基于该框架的多关系决策树算 法( m r d t l ) 。 第四章详细描述了对多关系决策树算法( m r d t l ) 的一些改进，以提高其 效率和改进其可扩展性，并提出了一个改进的算法。 第五章是对改进的多关系决策树算法进行实验验证和结果分析。 第六章是对本文所做工作的一个总结以及对未来研究方向的一些展望。 9 2 多关系数据挖掘的一般方法 关系数据挖掘领域可以分为以下几个的方向：( 1 ) 归纳逻辑程序设计( i l p ) ； ( 2 ) 统计关系学习；( 3 ) 关联分析：( 4 ) 借用i l p 技术，但搜索策略利用数据库 查询技术。 2 1归纳逻辑程序设计 归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n g ，i l p ) 是由归纳学习( i n d u c t i v e l e a m i n g ) 与逻辑程序设计( l o g i cp r o g r a m m i n g ) 发展并融合的产物。归纳学习的 目标是从大量的经验数据中抽取一般的判定规则和模式，而逻辑程序设计是一种 程序设计范例，用一阶逻辑表示对象之间的关系。i l p 继承了逻辑程序设计的坚实 理论基础，继承了归纳学习的实验方法和面向实际的应用方向。 i l p 最初的目的是从样例与背景知识中归纳合成逻辑程序，学习关系的逻辑定 义。解决上述任务的早期代表性i l p 系统有m i s ，c i g o l ，f o i l ，g o l e m ，较为 晚的近期代表性i l p 系统有p r o g o l 和a l e p h 。 i l p 方法一般使用知识表示语言为逻辑程序，逻辑程序是一阶谓词逻辑的重要 子集。i l p 方法使用护包含格给出子句构成的搜索空间结构。i l p 搜索策略包括盲 目搜索( 如深度优先搜索、广度优先搜索等) 和启发式搜索( 如最佳优先搜索、 爬山法搜索等) 。 归纳逻辑程序设计涉及利用背景知识从目标谓词中发现描述该目标谓词定义 的规则。为了计算上的方便，i l p 系统通常采用确定语义：即正例和负例分别以目 标谓词基原子的正例集合睾和负例集合e 一形式给出，背景知识和得到的规则均为 确定子句集。 在标准问题环境中，学习得到的规则和背景知识一起应该蕴含集合中所有 给定的正例，满足其完备性，并不与e 一中给定的负例矛盾，满足其相容性。完备 性和相容性合起来构成了正确性。i l p 一般的问题背景如下所述： 给定：目标谓词p 尸的正例集e ( p 的基原子集合) 尸的负例集e 一( p 的基原子集合) 背景知识b k ( 确定子句的有限集) 找到：p 的定义日( p 的定义子句) ，使得日ub e 对于e 毒和一是正确的。 即： 1 0 1 日u 肷对于矿是完备的，即v e e + ，日u 胀i - - 4e 。我们也称日ub k 覆 盖所有的正例。 2 日u 脒对于e 一是相容的，即日u 肷u 1 e 一是可满足的，其中 e 一= e l ，e 2 ， ，1 e 一= - - , e l ，- , e 2 ， 。 其中l 和2 分别对应后验完备性和后验可满足性。问题中的背景知识b k 和例 子要满足以下的先验条件： 1 ) 先验必要性：b k 对于是不完备的e 。否则根本没有学习任务。 2 ) 先验可满足性：b eue + 对于三一是相容的。否则没有解。 为了对归纳逻辑程序设计( i l p ) 的任务及其与逻辑程序的关系有直观的理解， 这里用一个涉及家族关系的例子来示例说明。问题涉及的谓词如下：谓词h ( x ， 表示x 是y 的丈夫；谓词m ( x ，表示x 是y 的母亲；谓词f ( x ，表示x 是y 的 父亲；谓词g m ( x ，表示x 是y 的祖母( 包含外祖母) ；谓词g f ( x ，表示x 是y 的祖父( 包含外祖父) 。问题描述如下： 首先确定要学习的目标概念，如g f ( x ， 给出的目标概念的正负例： 正例集合e ：酸孔d ) ，g f ( a , d 1 ) ，g f ( a , d 2 ) ，g f ( a , d 3 ) ； 负例集合e 一：g f ( a , a ) ，g f ( a , c ) ， 给出背景知识旧目，该背景知识确定的家族关系树如图2 1 所示： f 1 ) h ( a ，c l 2 ) m ( c ，e c 3 ) m ( c ，f ) 4 ) m ( c ，g l 5 ) m ( g ，d ) 6 ) f i e ，d 1 ) e 7 ) f ( e ，d 2 ) e 8 ) f ( e ，d 3 图2 1 背景知识及其对应的家族关系树 f i g u r e 2 1b a c k g r o u n da n dc o r r e s p o n d i n gf a m i l yt r e e 求目标概念的g f ( x ，的逻辑定义，使得该定义能正确的解释e 和e 一。 一般的i l p 系统可从上述输入中学习到如下描述目标概念g f ( x ，的规则： ( 9 ) g f ( x ，：一f ( x ，z ) ，m ( z ， ( 10 ) g f ( x ，：一f ( x ，z ) ，f ( z ， 上述背景知识是以基原子的形式给出的，我们也可以以子句规则的形式给出， 如若我们还已知祖母( 外祖母) 的定义规则为： ( 1 1 ) g m ( x ，：- m ( x ，z ) ，m ( z ， ( 1 2 ) g m ( x ，：- m ( x ，z ) ，f ( z ， 将( 1 1 ) 和( 1 2 ) 作为附加的背景知识提供给i l p 系统，则有能学出以下的更简单 规则 。( 13 ) g f ( x ，：一h ( x ，z ) ，g m ( z ， 上述( 1 ) 到( 1 2 ) 式或( 1 ) 到( 8 ) 式加上( 1 1 ) 到( 1 3 ) 式可组成计算家族关系的逻辑程 序，其中( 1 ) 到( 8 ) 是逻辑程序的领域事实，( 9 ) 到( 1 3 ) 是分别反映了祖母，外祖母以 及祖父，外祖父关系的逻辑程序的领域规则。我们可通过提出相关的领域问题， 比如求a 的孙辈w ，在有p r o l o g 解释器的计算机上运行上面的逻辑程序来得到需 要的结果，即d 1 ，d 2 ，d 3 和d 。 “ i l p 使用逻辑程序作为知识表示方式，这种知识表示方式更具表达力，可以表 示许多专业领域难以用命题逻辑表示的知识。此外，逻辑程序语言是一阶谓词逻 辑的子集，逻辑程序基本概念与数据库基本概念之间有明确的对应关系，图2 2 给 出了逻辑程序基本概念与关系数据库基本概念间的对应关系。因此，i l p 能够灵活 方便地表示关系学习与多关系数据挖掘过程中的多关系数据、背景知识以及涉及 多关系的复杂模式。 关系数据库概念逻辑程序概念 关系名p谓词符号p 关系p 的属性 谓词p 的参数 元组a ：，a 2 a a 基事实p ( a i ，a 2 。a 矗) 由元组集合表示的关系p由基事实集外延定义的谓词p 由视图定义的关系p由子句集合内涵定义的谓词p 图2 2 关系数据库基本概念与逻辑程序基本概念间的对应关系 f i g u r e 2 1r e l a t i o n s h i pb e t w e e n t h eb a s i cc o n c e p t so fr e l a t i o n a ld a t a b a s ea n dt h el o g i cp r o g r a m 如果能够应用以上的这种对应关系，无疑能够使i l p 系统与关系数据库系统 集成，使i l p 系统能够充分利用关系数据库优异的数据存储优化能力查询优化 能力和高效的查询执行能力，从而提高数据挖掘算法的效率和扩展性。 但是，在大多数多关系数据挖掘的研究中，i l p 技术与数据库系统的集成是松 散耦合的。在经典的i