（计算机软件与理论专业论文）决策树优化算法研究.pdf

决策树优化算法研究 摘要 数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ，k d d ) 是当前涉 及人工智能、数据库、统计学等学科的一门相当活跃的研究领域。决策树是发现 分类模型的常用技术之一，已被广泛研究并取得了很大的进展。然而，由于在决 策树的构造过程中采用贪心算法，因而造成了决策树容易过分拟合、规模过大、 产生的规则长度过长等缺点。针对这些问题，研究人员提出了多种优化方法。本 文在对现有的这些决策树优化方法进行了全面研究的基础上，提出了一种基于粗 糙集合理论的决策树优化方法。，一 本文主要工作包括以下三部分： 1 综述了k d d 的定义、基本过程、主要技术及其发展情况。重点介绍了 用于挖掘分类规则的决策树方法和其他几种较为常用的方法。 2 对现有的各类优化决策树的技术进行了详细的综述，如修改测试属性空 间、修改测试属性选择、对实例的数据限制和采用其他数据结构等方法，并介绍 了每类方法中比较经典的几种算法。同时对各种方法进行了定性分析，比较了各 类方法的优缺点。 3 以粗糙集合中的知识约简为基础，提出了对决策树的测试属性进行约简 的方法，剔除了训练集中与分类无关的属性，用较小的训练集建造出较小规模的 决策树而分类正确率不受影响。最后通过实验将该方法与i d 3 算法进行了比较， 证明了该方法的可行性。 关键词：k d d ：数据挖掘；决策树优化；粗糙集合 t h er e s e a r c ho nt h e a l g o r i t h m s o f o p t i m i z i n g d e c i s i o nt r e e s a b s t r a c t 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 s ( k d d ) i s am u l t i d i s c i p l i n a r yf i e l d ，d r a w i n g w o r kf r o ma r e a si n c l u d i n gd a t a b a s et e c h n o l o g y , a r t i f i c i a li n t e l l i g e n c e ，s t a t i s t i c sa n ds o o n d e c i s i o nt r e ei sam e t h o do fk d dt h a ti su s e dw i d e l yt om i n i n gc l a s s i f i c a t i o n m o d e l s i th a sb e e ns t u d i e dw i d e l ya n dm a d eag r e a tp r o g r e s s w h i l et h ed e c i s i o n t r e e sa r ea l w a y st e n d st ob eo v e r f i t t i n g ，t oh a v el a r g e rs c a l e sa n dt oi n d u c el o n g e r c l a s s i f i c a t i o nr u l e si nt h a tt h et r e ei n d u c t i o na l g o r i t h ma d o p t sg r e e d ym e t h o d m a n y m e t h o d sa r ep r o p o s e dt oi m p r o v et h e s ef l a w sm e n t i o n e da b o r e i nt h i st h e s i st h e s e m e t h o d sa r es t u d i e dc o m p l e t e l ya n ds e q u e n t i a l l yf ln e wm e t h o dt oo p t i m i z ed e c i s i o n t r e e si sp u tf o r w a r d t h e r ea r et h r e em a i n p o i n t si nt h i st h e s i sa sf o l l o w s ： 1 ag e n e r a ls u r v e yo fk d di sg i v e ni n c l u d i n gt h ed e f i n i t i o n ，b a s i cp r o c e s s ，m a i n m e t h o da n dt h es t a t u so fd e v e l o p m e n t 1 1 1 ed e c i s i o nt r e ea n ds e v e r a lo t h e rm e t h o d s u s e dt om i n i n gc l a s s i f i c a t i o nr u l e sa r ei n t r o d u c e da se m p h a s i s 2 ad e t a i l e ds u r v e yo fa l lt h ed e c i s i o nt r e eo p t i m i z a t i o na p p r o a c h e si s g i v e n ， s u c ha s m o d i f y i n g t e s t s p a c e ，m o d i f y i n g t e s t s e a r c h ，r e s t r i c t i n g d a t a b a s ea n d a l t e r n a t i n gd a t as t r u c t u r e s t h ec l a s s i c a la i g o d t h m so fe a c hk i n do fa p p r o a c ha r ea l s o s u m m a r i z e da n d c r i t i q u e d 3 au e w a p p r o a c hi sp r o p o s e dt or e d u c et h et e s t i n ga t t r i b u t es e t so fd e c i s i o n t r e e so nt h eb a s eo fk n o w l e d g er e d u c t i o nc o m i n gf r o mt h er o u g hs e tt h e o r y w i 也 m i sa p p r o a c hs o m et e s ta t t r i b u t e su n r e l a t e dt ot h ec l a s s i f i c a t i o n a r er e m o v e d t h e r e f o r er e l a t i v e l ys m a l l e rt r a i n i n gs e t sc a nb ef o u n dt oi n d u c er e l a t i v e l ys m a l l e r d e c i s i o nt r e e sw i t h o u tr e d u c i n ga c c u r a c y i nt h el a s tp a r t ，w ee v a l u a t et h em e t h o do n s e v e r a ld a t as e t sc o m p a r e d 、i mi d 3a l g o r i t h m k e yw o r d s ：k d d ；d a t am i n i n g ；d e c i s i o nt r e e0 p t i m i z a t i o n ；r o u g hs e t s 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学 硕士学位论文质量要求。 主席： 委员： 导师 梭鱼辛 i 乙 答辩委员会签名 嚣籀 吕吕 易 0 八 “ 列 幻 。 、 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒蟹王些盔堂或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名 签字日期：伊4 年7 月g 日 学位论文版权使用授权书 本学位论文作者完全了解金蟹王些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘允许论文被查阅和借阅。本人授权合肥 王、业盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名- 诵 签字日期：口舡年7 月驴日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字臼期 电话 邮编 致谢 在此论文完成之际，非常感谢我的导师胡学钢教授，谨向我的导师胡学钢 教授表示最真诚的谢意! 胡老师知识广博，治学严谨认真，对科研问题有敏锐的 洞察力，在学习上和生活上给了我无微不至的关心和帮助。我在硕士期间所取得 的成绩，离不开胡老师的悉心指导和鼓励。我的硕士论文也是在胡老师的精心修 改和反复提炼下完成的。在此谨向胡老师致以衷心的感谢和深深的敬意。 同时十分感谢我的同学张玉红、张晶、刘桂庆、周红鹃和杨静等，大家一 起对数据挖掘课题进行研讨，集思广益，这对我的论文有很大的启发。感谢人工 智能与数据挖掘研究室的王浩、欧阳一鸣等各位老师给我的指导和帮助。 感谢计算机学院的王新生老师和徐静老师。感谢所有关心我、帮助我的老 师和同学。 在这里，还要特别感谢我的父母，一直以来他们对我的生活和学习都倾注了 的大量心血。谢谢陈彬。 第一章k d d 技术概述 由于计算机数据采集工具以及关系数据库技术的发展，目前各行业 存储了大量的数据，航空航天、气象、医疗、农业等行业尤为突出。传 统的数据分析手段难以应付，导致越来越严重的数据灾难，追使决策者 穷于应付，甚或只能置之不理。关系数据库提供的简单查询及报表生成 功能，只能获得数据的表层信息，而不能获得数据属性的内在关系和隐 含的信息，即淹没了包含的知识，造成了资源的浪费川。为了使消耗大 量财力与物力所收集与整理的宝贵数据资源得以利用，有效解决数据丰 富性及知识贫乏性的矛盾，需要新技术智能、自动地分析处理原始数据， 从而促使了数据库中的知识发现( k d d ，k n o w l e d g ed i s c o v e r y i n d a t a b a s e ) 技术的出现m j 。 k d d 是一个综合的过程，包括数据录入、迭代求解、用户交互以 及许多定制要求和决策设计等。这一研究领域兴起于八十年代初，是由 众多学科诸如人工智能、机器学习、模式识别、统计学、数据库和知识 库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前景 的领域。知识发现的应用范围非常广泛，从数据库中发现出来的知识可 以用在信息管理、过程控制、科学研究、决策支持等许多方面口一，”。 k d d 术语是在1 9 8 9 年于美国底特律召开的国际人工智能会议中的知识 发现专题讨论会上正式形成的。之后于1 9 9 1 、1 9 9 3 和1 9 9 4 年相继举行了 i ( d d 专题研讨会。随着k d d 的深入研究以及k d d 在许多领域的成功应 用，于1 9 9 5 年在加拿大举行了第一届知识发现和数据挖掘国际学术会 议，此后每年都召开大规模的国际会议。第一本关于k d d 的国际学术杂 志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 也于1 9 9 7 年3 月创刊发行。 亚太区于1 9 9 7 年在新加坡召开了首次k d d 研讨会其后又在澳大利亚 的墨尔本召开了第二届，在中国北京召开了第三届。 1 9 9 8 年第四届知识发现与数据挖掘国际会议上不仅进行了学术讨 论，并且有3 0 多家软件公司展示了数据挖掘软件产品，在北美、欧洲 等国得到较大应用。在我国，许多学术会议如中国人工智能联合学术会 议、数据库学术会议、机器学习学术会议等也都将k d d 列为了重要的 研究专题，许多高校与科研机构也开展了k d d 系统的研究。知识发现 的研究已经成为当今计算机科学与技术研究、应用的热点领域之一。 1 2 知识发现的基本概念及一般步骤 1 2 1 基本概念 在k d d 9 6 国际会议上，f a y y a d ，p i a t e t s k y s h a p i r o 和s m y t h 对k d d 作了如下描述：指从数据集中识别出有效的、新颖的、潜在有用的和最 终可理解的模式的非平凡过程。i 6 1 在上面这个定义中，数据集是一组事实f ( 如关系数据库中的记录) ； 模式是一个用语言l 来表示的一个表达式e ，可用来描述数据集f 的某 个子集f e ，e 作为一个模式要求它比对数据子集f e 的枚举要简单( 所 用的描述信息量要少) ；过程是在k d d 中包含的多阶段的处理，涉及数 据的预处理、模式搜索、知识评价以及反复的修改求精等；该过程要求 是非平凡的，是指它具有一定程度的智能性、自动性( 例如，仅仅给出 所有数据的总和不能算作是一个发现过程) ；有效性是指发现的模式对 于新的数据仍保持有定的可信度；新颖性是要求发现的模式应该是新 的；潜在有用性是指发现的知识将来有实际的效用，如用于决策系统里 可提高经济效益；最终可理解性要求发现的模式能被用户理解，目前它 主要体现在简洁性上。 数据挖掘是k d d 过程中的一个阶段，由应用数据分析和发现算法 在可接受的计算效率内产生数据的一个特定模式序列组成。 模式的空间常常是无限的，模式的列举包括在该空间的一些搜索。 实际的算法严格限制搜索在可由数据挖掘算法探索的子空间内。 k d d 过程是按照任意需要的选择、预处理、抽样、转换、应用数 据挖掘方法( 算法) 从数据库中列举模式、估价数据挖掘的结果以及标 识所列举出的被认为是知识的模式子集的过程。 k d d 过程的数据挖掘组件与算法相关，是指通过这些算法可以从 数据中提取并列模式。整个k d d 过程包括对挖掘出的模式的估价和可 能的解释以确定哪些模式可以作为知识。 1 2 2k d d 过程 知识发现过程是交互的、重复的、包含大量由用户决策的阶段。根据 b r a c h m a n 和a n a n d 的观点，k d d 过程一般可粗略地分为以下三步：数据准 备、数据挖掘以及结果的表达和解释( 见图1 1 ) 【 。 1 数据准备 数据准备又包含三个子步骤：数据集成、数据选择、数据预处理。数据 集成是将多文件或多数据库运行环境中的数据进行合并处理，解决语义模糊 2 性、处理数据中的遗漏和清洗脏数据等。数据选择的目的是确定发现任务的 操作对象，即目标数据，它是根据用户的需要从原始数据库中抽取的一组数 据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完 成数据类型转换( 如把连续值转换为离散型的数据，以便于符号归纳，或是 把离散型的转换为连续值型的。以便于神经网络归纳) 等工作。数据预处理 的目的是为了克服目前数据挖掘工具的局限性a 2 数据挖掘阶段 图1 1 知识发现过程 数据挖掘阶段首先确定的是挖掘的任务或目的，如分类、聚类、关 联规则发现或序列模式发现等。等确定了开采任务后，就要决定使用什 么样的开采算法。同样的任务可以用不同的算法来实现，选择实现算法 有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关 的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获 取描述型的( d e s c r i p t i v e ) 、容易理解的知识( 采用规则表示的开采方法 可能要好于神经网络之类的方法) ，而有的用户或系统的目的是获取预 测准确度尽可能商的预测型( p r e d i c t i v e ) 知识。完成了上述准备工作之 后，就可以实施数据挖掘操作了。 3 结果表达和解释 数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在 冗余或无关的模式，因而需要将其剔除；某些模式也可能不满足用户要 求，因而发现过程需要回到前面的某个发现阶段，例如，重新选取数据、 采用新的数据变换方法、设定新的数据挖掘参数值，甚至换一种采掘算 法( 如当发现任务是分类时，有多种分类方法，不同的方法对不同的数 据有不同的效果) 。另外，k d d 由于最终是面向人类用户的，因此可能要 对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示， 如把分类决策树转换为“i f t h e n ”规则。 1 3 知识发现的核心数据挖掘 数据挖掘是k d d 最关键的步骤，也是技术难点所在。数据挖掘算法 的好坏将直接影响到所发现知识的准确性。目前k d d 研究大部分集中在 数据挖掘算法和应用的技术上。人们往往不严格区分数据挖掘和数据库 中的知识发现，两者互为使用。一般在科研领域中称为k d d ，而在工程 领域则称为数据挖掘。 1 3 1 数据挖掘的任务 数据挖掘的任务是从数据中发现模式。模式按功能分为预测型( p r e d i c t i v e ) 和描述型( d e s c r i p t i v e ) ，而按实际作用可分为以下6 种： 1 分类模式 分类模式把数据集中的数据项映射到某个给定的类上。分类模式往 往表现为一棵分类树，从树根开始搜索，沿着数据满足的分支走，走到 树叶就能确定类别。已有许多数据分类方法，如决策树方法、统计方法 及粗糙集方法等。m e h t a ，a g r a w a l ，r is s a n e n 等人开始研究面向数据库 的分类方法。j h a n 等人在他们开发的知识发现系统d b m i n e r 中采用了 基于概括的决策树方法，该方法集成了面向属性的归纳和决策归纳技 术。 2 回归模式 回归模式的函数定义与分类模式相似，其差别在于分类模式的预测 值是离散的，回归模式的预测值是连续的。 3 关联模式 关联规则分析就是发现关联规则，这些关联规则反映了在给定的一 组数据中某些属性值高频率同时出现的一种状态。其表现形式是形如 x = j y ，即规则a l 八 a b l 八 b n ，其中 a i ( i 1 ，m ) ，b j ( j 1 ，n ) 是属性值，关联规则x j y 解释为“满足条 件x 的数据组也可能同时满足条件y ”，但需满足一定的支持度和可信 度。关联规则有单维和多维规则之分，关联规则广泛用于购物篮或事务 的数据分析。 4 时间序列模式 时间序列模式根据数据随时间变化的趋势，发现某一时间段内数据 的相关处理模型，预测将来可能出现值的分布。它可看成是一种特定的 关联模型，它在关联模型中增加了时间属性。 5 聚类模式 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相 似，不同类中的数据相异。 与分类不同，一般情况下，训练数据中不提供类标记，聚类可以用 于产生这种标记。对象根据最大化类内相似性、最小化类别间相似性的 原则进行聚类或分组。即对象的簇( 聚类) 是使得在个簇中的对象具 有很高的相似性，而与另外簇中的对象很不相似。所形成的每个簇可以 看成一个对象类，由它导出规则。 6 序列模式 序列模式与关联模式相仿，差别在于数据间关联性与时间联系起 来。即不仅需知道事件是否发生，而且需确定事件发生的时间。 在实际工作中，分类模式和回归模式使用最普遍，但通常多种模式 结合使用。分类模式、回归模式、时间序列模式属于受监督知识，可直 接用来检测模式的准确性。一般在建立这些模式时，使用一部分数据作 为样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序 列模式则是非监督知识，因为在模式建立前结果是未知的，模式的产生 不受任何监督。 1 3 2 数据挖掘的典型方法及工具 1 神经网络( n e u r a ln e t w o r k ) 神经网络基于自学习数学模型，通过数据的编码及神经元的迭代求解 完成复杂的模式抽取及趋势分析功能。神经网络系统由一系列类似于人脑神 经元一样的处理单元( 称之为节点，n o d e ) 组成，节点间彼此互连，分为输 入层、中间( 隐藏) 层、输出层。神经网络的一般结构，如图1 2 所示。 神经网络通过网络的学习功能得到一个恰当的连接加权值，较典型的学 习方法是b p 法( b a c k p r o p a g a t i o n ) 。通过将实际输出结果同期望值进行比较， 调整加权值，重新计算输出值，使得误梯度下降。不断重复学习过程，直至 满足终止判断条件。 神经网络系统具有非线性学习、联想记忆的优点，但也存在些问题： 神经网络系统是一个黑盒子，不能观察中间的学习过程，最后的输出结果也 较难解释，影响结果的可信度及可接受程度。其次，神经网络需要较长的学 习时间，对大数据量，性能出现严重问题。 输八层中间屡输出层 图1 2 神经网络的结构 2 决策树( d e c i s i o nt r e e ) 决策树是通过一系列规则对数据进行分类的过程。采用决策树，可以将 数据规则可视化，也不需要长时间的构造过程，输出结果容易理解，精度较 高，因此决策树在知识发现系统中应用较广。 然而，采用决策树方法也有其缺点。决策树方法很难基于多个变量组合 发现规则。不同决策树分支之间的分裂也不平滑。同时决策树自身的构造方 法也决定了其分类时只能根据个属性来分类，且训练集中的所有属性及属 性值都会参与决策树的构造，使由决策树学习产生的规则长度偏大。 3 联机分析处理( o l a p ) 联机分析处理( o n l n ca n a l y t i c a lp r o c e s s i n g ，0 l a p ) 主要通过多维的方式 ；! m 矮垮| 一。j ：蠹 一- _ i - 对数据进行分析、查询和报表。o l a p 应用主要是对用户当前及历史数据进行 分析，辅助领导决策。主要是进行大量的查询操作，对时间的要求不太严格。 目前常见的o l a p 主要有基于多维数据库的m o l a p 及基于关系数据库的 r o l a p 。 4 数据可视化( d a t av i s u a l i z a t i o n ) 可视化工具能很好地使用户理解数据并向用户解释发现的知识，其本质 是对数据子集进行拓扑变换，将规则映射到拓扑。通过定义的标准接口，知 识发现系统和数据可视化工具应很好地协作。由于数据处理阶段的数据量大， 知识发现系统通过设定富有成效的探索起点并按恰当的可视化方式表示数据， 可视化后的数据，将使用户可以直观地发现数据特征与数据隐含的依赖关系， 为数据分析人员提供很好的帮助。对于发现的知识，通过可视化工具，帮助 用户好地理解与评价知识的功用性。 1 3 3 数据挖掘系统的发展 根据r g r o s s m a n 的观点【8 1 ，数据挖掘的发展过程可分四代： 第一代：第一代的数据挖掘系统仅支持一个或少数几个数据挖掘算法， 这些算法只能够挖掘向量数据。如果数据足够大，并且频繁的变化，这就需 要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。 第二代：第二代系统的主要特点是支持与数据库和数据仓库的高性能接 口，并有高的可测量性和功能性。例如，第二代较第一代系统可挖掘更大型 以及更高维数的复杂的数据集。第二代系统提供了数据挖掘模式和数据挖掘 查询语言，从而具有更高的灵活性。然而第二代系统只注重模型的生成，如 何和预言模型系统集成的问题导致了第三代数据挖掘系统的开发。 第三代：第三代数据挖掘系统可挖掘i n t r a n e t s 和e x t r a n c t s 上的分布的和 高度异质的数据，并能有效的和操作系统结合。这一代数据挖掘系统的关键 技术之一是提高对建立在异质系统上的多个预言模型以及管理这些预言模型 的元数据提供第一级别的支持。 第三代数据挖掘和预言模式系统与搜索引擎不同。后者只是简单的提供 一个网络上数据的定位方法；而前者则提供的是发现网上数据的模式、关联、 变化和异常的方法。 第四代：第四代数据挖掘系统可以挖掘嵌入式、移动式以及一般性的计 算设备所产生的各种数据。第四代数据挖掘原型或商业系统尚未见报导， p k d d 2 0 0 1 上k a r g u p t a 发表了一篇在移动环境下挖掘决策树的论文，k a r g u p t a 7 是马里兰巴尔的摩州立大学( u n i v e r s i t yo fm a r y l a n db a l t i m o r ec o u n t y ) 正在 研制的c a r e e r 数据挖掘项目的负责人，该项目研究期限是2 0 0 1 年4 月到 2 0 0 6 年4 月，目的是开发挖掘分布式和异质数据( u b i q u i t o u s 设备) 的第四 代数据挖掘系统。 1 4k d d 面临的挑战 经过近十多年的发展，k d d 在研究和应用方面取得丰硕的成果，但依然 面临来自研究和应用方面的挑战。在k d d 的研究领域中，随着数据的激增和 数据形式的不断发展，必须解决下列问题： 1 数据库的多样性问题 关系的和复杂的数据类型的处理。由于关系数据库和数据仓库已经广泛 应用，因而数据库中可能包括复杂的数据对象、超文本和多媒体数据、空间 数据、时间数据或事务数据等。由于数据不同，数据挖掘任务不同，实现所 有的挖掘任务的通用方法是不现实的。而各种挖掘系统都是根据数据类型和 挖掘任务来决定挖掘系统。 2 挖掘数据的海量问题 数据挖掘由于面向的是大规模数据库，因而算法的运算量较大，因此， 改进算法的时间和空间性能一直是个重要问题。当前较常用的方法有并行 的挖掘、分布式的挖掘和增量挖掘方法以及利用先验知识来提高挖掘的效率 和精度。 3 数据的预处理问题 噪声数据和不完全数据的存在， 此之上而进行的挖掘必然受到影响， 此必须在预处理的过程中予以删除。 4 先验知识的应用问题 使得数据集合呈现过分拟合的状态，在 使得挖掘的效率和精度得不到保障，因 利用背景知识指导挖掘过程，并使发现的模式以简捷的形式表达。先验 知识的运用可以提高挖掘的速度和准确率，同时，先验知识来自于过去的实 际数据，需要适应现在的数据和进一步地调整。 知识发现技术正处在发展当中。知识发现涉及到数理统计、模糊理论、 神经网络和人工智能等多种技术，技术含量较高，实现难度较大。此外，知 识发现系统同可视化技术、地理信息系统、统计分析系统相结合，丰富数据 挖掘技术及工具的功能与性能。 随着数据量的急剧增长和分析决策难度的增强，以及人们对决策分析工 作的智能化、自动化要求的不断提高，人们将广泛地接受并使用知识发现技 术及工具。可以预见，在今后各类数据库的深层次利用上，知识发现将会得 到充分的发展。 1 5 本文的主要内容及组织 本文主要研究了目前较为成熟的几类对决策树算法的优化方法，比较了 各类方法的优缺点，并在此基础上提出了一种基于粗糙集合理论的对决策树 进行优化的方法。 全文内容组织如下： 第一章简述数据库中的知识发现的产生背景以及发展前景，知识发现中 的核心技术数据挖掘的主要内容，以及知识发现所涉及的典型方法与技术。 最后说明本文的研究重点和课题研究的意义，简要给出文章的组织结构。 第二章介绍了分类问题的一般概念，阐述了分类研究中的常见方法，详 细阐述了分类问题中最常使用的决策树学习方法。 第三章对目前比较成熟优良的决策树学习算法的改进方法进行了详细 的研究，并指出了它们各自的优缺点。 第四章将粗糙集合中的思想引入决策树构造算法中，对算法进行了优化 改进。利用粗糙集合中知识约简的思想对决策树训练集中的测试属性进行约 简，去除与分类无关的属性，以控制其规模。最后通过实验将改进后的方法 与i d 3 算法进行了比较。 第五章全文的总结，对本文的主要研究工作进行简要的阐述和说明，并 对下一步的工作进行了展望和探讨。 本章主要介绍了k d d 技术发展的背景，相关概念和基本内容。着重阐述 了k d d 的核心部分数据挖掘技术，介绍了数据挖掘的几类基本任务、典 型方法以及数据挖掘系统的发展历程。接着指出了k d d 研究中所需面对的困 难和发展趋势。最后给出了本文主要内容和组织结构。 9 第二章分类问题及相关研究 人类认识事物从分类开始，分类能力是人类智能的基础。在从大规模数 据库获得知识的过程中必然涉及到数据分类问题f 9 1 。分类是数据挖掘中的一项 非常重要的任务，目前在商业上应用最多，也一直是k d d 领域的研究热点之 分类的主要目标是提出一个分类模型( 或分类器) ，所得的这个分类模型 能够将数据库中的数据项映射到给定类别中的某一个b o l 。定义2 1 给出了分 类器的一般定义。 定义2 1 令x l ，x 2 ，x 。，c 为随机变量且x l 具有域d o m ( x i ) ，一般假定 d o r n ( c ) = 1 , 2 3 j 。则分类器被定义为一个函数： d ：d o r a ( x 1 ) d o m ( x 2 ) d o m ( x m ) - - ) d o m ( c ) 使e ( x ，c ) 为d o m ( x 1 ) d o r e ( x 2 ) x x d o m ( x m ) d o m ( c ) 上的一 个概率分布函数，并且有卢 是一个由p 随机得出的记录， 也就是说，t 有概率p ( x ，c ) 当 x 并且t c c 。 因此，一般来说分类分为两个步骤： 第一步，构建分类器。构造的主要方法有决策树、贝叶斯网、神经网络、 概念格和粗糙集合等。 第二步是利用模型进行分类。模型分类的首要问题是评价模型的准确率， 一般的方法是保持法( h o l d ) 和k 一交叉确认( k c r o s s ) 法。如果模型的准确率 是可接受的，则利用这个模型来分类。 当前分类问题的研究主要集中在分类算法的优化和分类模型的评估上， 为了解决大规模数据库所带来的算法的低效率问题，先验知识被引入分类中， 这种先验知识可以大大提高效率，而这种先验知识的应用主要体现在对模型 的剪枝上，如判定树的剪枝和神经网络的剪枝等。而算法的灵活性方面，主 要强调算法对不同数据的适应、有效性和伸缩性。如判定树的s l i q 算法， s p r i n t 算法和f o r e s t 算法等。模型的评估方面，除了分层的k 一折交叉确 认方法( k f o l dc r o s s v a l i d a t i o n ) # b ，还发展了适应模型对过拟合数据的方法，如 装袋( b a g g i n g ) 和推进( b o o s t i n g ) 等以及这些方法的组合来提高分类的整体的准 确率，并进一步地提出准确率度量对数据的适应性。 l o 2 2 分类研究的常用模型 国内外的研究人员在数据挖掘、统计分析、机器学习、神经网络、专家 系统等领域中进行了大量的研究。多年来，围绕分类问题进行了积极的研究 并取得了许多成果，主要集中在知识的模型表示上，如决策树、贝叶斯网、 神经网络、概念格和粗糙集合等 1 t , 1 2 , 1 3 , 1 4 ，1 。 2 2 1 决策树分类 决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属 性上的测试。每个分支代表一个测试输出，而每个叶子节点代表类或类分布。 为了对未知的样本进行分类，样本的属性值在判定树上测试，路径由树根到 存放该样本预测的叶子节点。决策树很容易转换成分类规则。 最早的决策树学习系统要追述到h u n t ，m a n 协和s t o n e 于1 9 6 6 年研制的 一个概念学习系统c l s ，该系统第一次提出使用决策树进行概念学习。接着 是q u i l a n 的i d 3 1 1 t ”1 算法，而c 4 5 1 “】算法是i d 3 的后续改进版。 在树的每个节点上使用信息增益( i n f o r m a t i o ng a i n ) 度量选择测试属性。 这种度量称作属性选择度量或分裂的优良性度量。选择具有最高信息增益( 最 大熵压缩) 的属性作为当前结点的测试属性。这种理论方法使得对一个对象 分类所需的期望测试数目达到最小，并确保找到一棵简单的( 但不必是最简 单的) 树。 判定树中由于数据中的噪声和孤立点的存在，使其中的有些分支表达的 是训练数据中的异常。剪枝的方法可以处理这种过分拟合的问题。通常这种 方法使用统计的度量，剪去其中最不可靠的分支，从而导致较快的分类，提 高判定树的正确分类能力。 树剪枝的方法有两种【1 7 】： l 、先剪枝，通过提前停止树的构造而对树剪枝。判定树中的保持有子集 样本中最频繁的类或这些样本的概率分布，这种方法的困难在于选取合适的 阈值来控制剪枝。 2 、后剪枝，一棵完全生长的判定树剪枝。通过删除节点的分支，剪掉树 节点。代价复杂性剪枝即为这种方法。最下面的未剪节点成为树叶节点，并 以其作为先前剪枝的最频繁的类标记； 3 、交叉使用先剪枝和后剪枝的方法，形成组合剪枝的方法。后剪枝的计 算更大，但其所得的判定树更可靠。 由判定树提取分类规则，提取的分类规则以i f t h e n 的形式表达。对 从根到树叶的每条路径创建一条规则。沿着给定路径上的每个属性值对形 成规则前件( i f 部分) 的合取项。叶节点包含类预测，形成规则的后件( t h e n 鄱分) 。 c 4 5 使用训练样本估计每个规则的准确率。这将导致规则准确率乐观估 计，c 4 5 使用一种悲观的估计来补偿偏差。作为选择，也可以使用一组独立 于训练样本的测试样本来评估准确性。 c 4 ，5 是以i d 3 算法为核心的完整的决策树生成系统。他通过两个步骤建 立决策树：树的生成阶段和树的剪枝阶段。c 4 5 在每个节点通过测试评估函 数来选取具有最大函数值的测试作为最优测试来划分该节点。c 4 5 使用两种 测试评估函数，分别是：信息增益函数和信息增益率函数。信息增益函数如 i d 3 算法中的定义。 信息增益函数对于那些可能产生多分支的测试倾向于产生大的函数值， 但是输出分支多并不表示该测试对未知的对象具有更好的预测效果。信息增 益率函数可以弥补这个缺陷，经验说明信息增益率比信息增益函数更健壮， 选择更好的测试。因而c 4 5 选择信息增益率作为缺省的测试评估函数。 对于大型的数据和现实的数据库挖掘时，有效性和可伸缩性就成了关注 的问题。最近的强调可伸缩性的大数据集的判定树归纳的算法s l i q t l 3 】和 s p r i n t i 旧】：它们都能处理连续属性和分类属性。这两种算法都使用了预排序 的技术，对非常大的数据集进行预排序。都定义了新的数据结构以利于树的 构造。关于决策树的分类研究问题在以后的章节中还将进行详细的介绍。 2 2 2 贝叶斯分类 贝叶斯分类是统计学分类方法。它可以预测类成员关系的可能性。 贝叶斯分类基于贝叶斯定理。通过对分类算法的比较发现，一种称作朴 素贝叶斯分类【20 】的简单贝叶斯分类算法可以与判定树和神经网络算法相媲 美。用于大型的数据库，贝叶斯分类表现出高准确率和高速度。 朴素贝叶斯分类假定一个属性值对给定的影响独立于其它的属性的值。 这一假定称作条件独立性。贝叶斯信念网络是图形模型，能表达属性之间的 依赖。贝叶斯信念网络也可用于分类。 2 2 2 1 朴素贝时斯分类 分类过程： ( 1 ) 每个数据样本用一个r l 维特征向量x 一( x l ，x 2 ，x n ) 表示，分别描述 对n 个属性a l ，a 2 ，a 。样本的n 个度量。 ( 2 ) 假定有m 个类c l ，c 2 ，c 。给定一个未知的数据样本x ( 即没有类 标号) ，分类法将预测x 属于具有最高后验概率( 条件x 下) 的类。即是说， 朴素贝叶斯分类将未知的样本分配给类c 。当且仅当p ( c i t x ) p ( c i x ) ， l j mj i ，这样，最大化p ( c i i x ) 。其中p ( c i i x ) 最大的类c 称为最大后 验假定。根据贝叶斯定理 p ( c i | x ) _ 里堕! 璺型盟 ( 2 1 ) 。p ( x ) ( 3 ) 由于p ( x ) 对所有类为常数，因此只需要p ( x i c i ) p ( c i ) 最大即可。 如果类的先验概率未知，则通常假定这些类是等概率的，即 p ( c 】) = p ( c 2 ) = = p ( c 。) 。并据此对只p ( c , l x ) 最大化。否则，最大化p ( x l c i ) p ( c i ) 。 注意，类的先验概率可以用p ( c i ) = s 。s 计算其中s i 是类c i 中的训练样本数，丽 s 是训练样本数。 ( 4 ) 给定具有许多属性的数据集，计算p ( x l c i ) 的开销可能很大。为了降低 计算p ( x l c ，) 的开销，可以作条件独立性的朴素假定。给定样本的类标号，假 定属性值相互独立，即属性问，不存在依赖关系。则 p ( x l c o = ii p ( x c ) ( 2 2 ) 1 i 概率p ( x l i c i ) ，p ( x 2 l c i ) ，p ( x 。l c j ) 可以由训练样本估值，其中 a ) 如果a k 是分类属性，则p ( x k l c i ) = s i k s i 是在属性a k 上具有值x k 的类c i 的训练样本数，而s i 是类c 。训练样本数。 b ) 如果a k 是连续值属性，则通常假定该属性服从高斯分布。因而 p ( x k l c i ) = g ( x k ，斗。，o c ) ，其中，给定类c i 的训练样本a k 的值，g ( x k ，o 。) 是属性 a k 的高斯密度函数，而。，a 。分别是平均值和标准差。 ( 5 ) 为未知的样本x 分类，对每个类c i ，计算p ( x i c 0 p ( c d 。x 被指派到类 c i ，当且仅当p ( x l c i ) p ( c i ) p ( x i c j ) p ( c j ) ，1 j m ，j i ，即x 被指派至0 其p ( x i c j ) 最大的类c ， 2 2 2 2 贝叶斯信念网络 贝叶斯信念网络1 2 0 】说明联合条件概率分布。它允许在变量的子集之间定 义条件独立性。他提供一种因果关系的图形，可以在其上进行学习。这个网 络也被叫做信念网络、贝叶斯网络或者概率网络。 信念网络由两部分组成。第一部分是有向无环图，其每个节点代表一 个随机变量，而每条弧代表一个概率依赖。第二部分是一个属性条件概率表 ( c p t ) 。 例如，已知贝叶斯信念网络( 图2 1 ) 和其对应的c p t 表( 表21 ) ，求解 其中存在的条件概率。 lf h ，s f h sf h sf h s 【 c 0 8o 5o 7 o 1 f l c 0 2o 5 0 3o 9 表2 。i l u n g c a n c e rc p t 表 f h - - f a m i l yh i s t o r y l c - - l u n g c a n c e r s s m o k e r 图21 一个简单的贝叶新信念网络 对于属性或者变量z l ，z 2 ，z 。的任意元组( z l ，z 。) 联合概率计算如下： 三 e ( z l ，z 2 ，z 。) = i i p ( z ii p a r e n t ( z 。) ) ( 2 3 ) i = 1 其中，p a r e n t ( z i ) 为z i 的直接前驱或者双亲节点( 有一条弧直接指向z i 的 节点) ，p ( 五ip a r e n t ( z 。) ) 对应c p t 中z i 的表项。网络的内节点可以选作“输出” 节点，代表类标号属性。可以有多个输出节点。学习推理算法可以用于网络。 分类过程不是返回单个类标号，而是返回类标号属性的概率分布。 在实际的信念网络中，网络的结构往往是给定的，如果变量是可见的， 训练网络只是计算c p t 项，与朴素贝叶斯网络中的计算概率相似；当某些变 量隐藏时，则可以使用梯度下降方法训练信念网络，目标是学习c p t 的值。 2 2 3 神经网络 神经网络【2 i 】是一组连接的输入和输出单元，其中每个连接都与一个权值 相联。在学习阶段，通过调整神经网络的权值，使得能够预测输入样本正确 的类标号来学习。由于单元之间的连接，神经网络的学习又称为连接学习。 后向传播是一种神经网络学习算法，它通过迭代处理训练样本，将每个样本 的网络预测和实际类标号比较，进行学习。 神经网络中的知识可解释为规则，其规则提取的第一步是网络剪枝，通 过剪去对训练网络影响最小的加权链简化网络结构，剪枝简化后的网络可进 行链、单元或活跃值的聚类。发现处于每个隐藏单元的共同活跃值的集合。 分析每个隐藏单元的这些活跃值，导出涉及这些活跃值与对应输出单元值组 合的规则。类似地导出输入和隐藏单元层联系的规则，再结合这两个规则集 台形成i f t h e n 规则。 现在存在对隐藏层和输出层之间的改进，如利用遗传算法等方法对网络 进行剪枝，然后利用决策树提取其中的规则。 2 2 4 基于概念格的分类 r w i l l e 等提出的根据二元关系建立的概念格( g a l o i s 格) 是一种完备的 层次结构t 9 1 ，在本质上描述了对象与属性之间的联系，表明了概念之间泛化与 例化的关系。 概念格【9 】是基于二元关系构造的，作为知识的一种表示形式，有助于挖掘 概念间的各种规则。概念是把所感知的事物的共同本质特点抽象出来，并加 以概括。概念都具