（计算机应用技术专业论文）以相关性确定条件属性的概化决策树.pdf

太原理工大学硕士研究生学位论文 以相关性确定条件属性的概化决策树 摘要 数据挖掘是一种可以从海量数据中智能的和自动的抽取一些 有用的、可信的、有效的和可以理解的模式的过程，也被称之为数 据库中的知识发现。分类是数据挖掘的一种非常重要的方法。分类 的概念是在已有数据的基础上学会一个分类函数或构造出一个分类 模型，即分类器。该函数或模型能够把数据库中的数据记录映像到 给定类别中的某一个。分类方法拥有大量的应用实例，如金融市场 走向分析、顾客信用度分析、医疗诊断等。 决策树是数据挖掘中一种应用最为广泛的分类器。其原因如 下：1 、决策树分类的直观表示方法较容易转化为标准的数据库查询； 2 、决策树分类归纳的方法行之有效、尤其适合于大型数据集；3 、 决策树在分类过程中，除了数据集中己包括的信息外，不再需要其 他额外的信，g ；4 、决策树分类模型的预测准确度较高。 文章在介绍了一些典型的决策树分类算法的基础上，研究了一 种基于相关性分析的决策树分类器。其主要思想足通过属性相关性 来压缩训练集的大小并在建立决策树过程中采用此度量值来确定划 分条件属性的顺序，通过闽值设定和处理简化了决策树的剪枝和优 化过程，提高了处理的效率和规模。文章最后详细描述了算法的执 行过程以及正确性证明和时间复杂性分析。 t 太原理工大学硕士研究生学位论文 本课题的主要内容分为数据预处理、决策树生成、分析预测三 个阶段。在数据预处理阶段，我们使用面向属性归约的方法对训练 集进行横向的压缩以降低下一步数据处理时的复杂性：然后在已压 缩规模的训练集上，应用相关性分析的方法选择划分的条件属性， 并且对与类别属性相关性较弱的属性进行纵向的压缩，更进一步地 降低处理的复杂性；最后建立起决策树分类模型后，对测试集进行 分类预测，主要是对生成的决策树模型进行准确率方面的评估。 关键词：数据挖掘，决策树，分类，相关性分析，面向属性归约 i i 奎堕型三盔堂堡主婴塞生堂垡堡塞 ag e n e r a l i z e dd e c i s i o nt r e eu s i n gr e l e v a n c e k r 龇s i st 0e n k l b 蕊 c o n d i t i o na i t r i b u t e s a b s t r a c t d a t am i n i n gi sa na d v a n c e dp r o c e s s ，i nw h i c hw ec a np i c ku pm a n y t r u s t f u l ，o p e r a t i v e ，u s e f u la n dr e a d a b l ep a t t e r n sf r o mv e r yl a g e ra m o u n t s o fd a t a ，a l s ob ec a l l e da sk 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 ) c l a s s i f i c a t i o ni sak e yd a t am i n i n gt e c h n i q u ew h e r e b yd a t a b a s et u p l e s ， a c t i n ga st r a i n i n gs a m p l e s ，a r ea n a l y z e di no r d e rt op r o d u c eam o d e lo f t h eg i v e nd a t a e a c ht u p l ei sa s s u m e dt ob e l o n gt oap r e d e f i n e dc l a s s ，a s d e t e r m i n e db yo n eo ft h ea t t r i b u t e s ，c a l l e dt h ec l a s s i f y i n ga t t r i b u t e o n c e d e r i v e d ，t h ec l a s s i f i c a t i o nm o d e lc a nb eu s e dt oc a t e g o r i z ef u t u r ed a t a s a m p l e s ，a sw e l l a sp r o v i d eab e t t e ru n d e r s t a n d i n go ft h ed a t a b a s e c o n t e n t s c l a s s i f i c a t i o nh a sn u m e r o u sa p p l i c a t i o n s i n c l u d i n g c r e d i t a p p r o v a l ，p r o d u c tm a r k e t i n g ，a n dm e d i c a ld i a g n o s i s d e c i s i o nt r e ec l a s s i f i e r sh a v ef o u n dt h ew i d e s t a p p l i c a t i o n i n l a r g e s c a l ed a t am i n i n ge n v i r o n m e n t s t h e r ea r es e v e r a lr e a s o n sf o rt h i s f i r s t ，d e c i s i o nt r e e so f f e rav e r yi n t u i t i v er e p r e s e n t a t i o nt h a ti se a s yt o i i i 奎堕堡三盔堂堡主堡窒生堂焦鲨塞 a s s i m i l a t ea n dt r a n s l a t et os t a n d a r d d a t a b a s eq u e r i e s s e c o n d ，d e c i s i o n t r e ei n d u c t i o ni se f f i c i e n ta n de s p e c i a l l ys u i t a b l ef o rl a r g et r a i n i n gs e t s f u r t h e r m o r e ，d e c i s i o nt r e e g e n e r a t i o na l g o r i t h m s d on o t r e q u i r e a d d i t i o n a li n f o r m a t i o nb e s i d e st h a ta l r e a d yc o n t a i n e di nt h et r a i n i n gd a t a f i n a l l y ，t h ea c c u r a c yo fd e c i s i o nt r e ec l a s s i f i e r si sc o m p a r a b l eo re v e n s u p e r i o rt ot h a to fo t h e rc l a s s i f i c a t i o nt e c h n i q u e s i nt h ep a p e rad e c i s i o nt r e ec l a s s i f i e rb a s e do nr e l e v a n c ea n a l y s i si s p r o p o s e da f t e rd i s c u s s i n gt r a d i t i o n a la l g o r i t h m s t h em a i ni d e ai st o c o m p a c t t h e t r a i n i n g d a t aa n de v a l u a t ec o n d i t i o na t t r i b u t e sw i t h c o r r e l a t i o n s ，a n dm a d ep r u n i n ga n do p t i m i z a t i o np r o c e s ss i m p l i f i e di n o r d e rt o g e th i g ha c c u r a c ya n df a s tc l a s s i f y i n gs p e e d ，w h i c hl e a d st o e f f i c i e n t ，h i g h q u a l i t y ，m u l t i p l e l e v e lc l a s s i f i c a t i o no fl a r g ea m o u n t so f d a t a t h ea c c u r a c yo ft h ea l g o r i t h mw a sp r o v e na n dt h ec o m p l e x i t yo f t i m ew a sa n a l y z e da l s oi nt h ep a p e r t h ec o n t e n t si n c l u d et h r e e p h a s e s ：d a t a - p r e p r o c e s s i n gp h a s e ， d e c i s i o nt r e e g r o w i n gp h a s e ，t r e ea n a l y s i sa n dp r e d i c t i n gp h a s e i n d a t a p r e p r o c e s s i n gp h a s e ，a p p l y i n ga t t r i b u t e - o r i e n t e di n d u c t i o nt o c o m p a c t t h e t r a i n i n g d a t ai nh o r i z o n t a ld i r e c t i o nr e d u c e st h e c o m p u t a t i o n a lc o m p l e x i t yo ft h i sd a t a i n t e n s i v ep r o c e s s i ns e c o n dp h a s e ， w ea d o p tt h em e t h o do fr e l e v a n c e a n a l y s i s t oe v a l u a t ec o n d i t i o n a t t r i b u t e s ，a n de v e ng e n e r a l i z et h et r a i n i n gd a t ai nv e r t i c a ld i r e c t i o ni f i v l 太原理工大学硕士研究生学位论文 a n ya t t r i b u t e si si r r e l e v a n tt ot h ec l a s s i f y i n ga t t r i b u t e i nt h el a s tp h a s e ， w ee s t i m a t et h ea c c u r a c yr a t eo ft h em o d e lw i t hat e s t i n gs e tt ov e r i f yt h e v a l i d i t yo ft h ea l g o r i t h m k e yw o r d s ：d 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 ，r e l e v a n c e a n a l y s i s ，a t t r i b u t e - o r i e n t e di n d u c t i o n v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：却懂日期：兰丝曼：! 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：搠型丝e ii 参i - _ _ 二塑i ：! ：! 一导师签名： 太原理工大学硕士研究生学位论文 1 1 数据挖掘 1 1 1 应用背景 第一章数据挖掘及其分类算法 随着计算机技术的迅速发展，企业信息化程度的提高，科学研究和政府部 门中信息化事务处理技术的运用，以及数据收集工具和技术的多元化( 从文本扫 描到卫星遥感1 等等，除此之外，互联网的发展更是为我们带来了海量的数据和 信息，但存储在各种数据媒介中的海量数据，在缺乏强有力工具的情况下，已 经远远超出了人的理解和概括的能力。从而导致了“数据爆炸但知识贫乏”的 现象。我们色经被淹没在数据和信息的汪洋大海之中，存储数据的爆炸性增长 已经提出了对新技术和新工具的需求，以便帮助我们将海量数据转换成有用的 知识。 计算机技术的另一领域人工智能( a r t i f i c i a li n t e l l i g e n c e ) 1 9 5 6 年诞生之后取 得了重大进展。该领域目前的研究热点是机器学习一一用计算机模拟人类学习 的一门科学。用数据库管理系统来存储数据，用机器学习的方法来分析数据， 挖掘大量数据背后的知识，这两者的结合促成了数据挖掘的产生。 数据挖掘，简单地说就是从大量数据中提取或“挖掘”知识。它的定义为： 从大型数据库的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知 的潜在有用信息m 引。许多人认为数据挖掘和数据库中的知识发现或k d d t 4 】是 等价的概念。人工智能f a j ) 领域习惯称k d d ，而数据库领域习惯称数据挖掘。 也有的学者认为k d d 是发现知识的完整过程，而数据挖掘只是这个过程中的一 个部分。我们遵循后一种观点，所以数据挖掘是从存放在数据库、数据仓库或 其他信息库中的大量数据中挖掘有趣的知识的过程。它可以使用智能的方法提 取数据模式，有趣的模式可提供给用户或者作为新的知识存放在知识库中。数 据挖掘是一门交叉学科，它涉及的学科领域包括：数据库技术、人工智能、机 器学习、神经网络、统计学、模式识别、知识库系统、知识获取、信息检索、 太原理工大学硕士研究生学位论文 高性能计算和数据可视化等。数据挖掘的成果可以用在信息管理、过程控制、 科学研究、决策支持等许多方面。 1 1 2 历史 一切新事物的产生都是由需求而驱动的。随着数据库技术和数据库系统在 各行业的广泛应用，当今的人们生活在数据和信息的海洋中。有些公司经过长 年累月积累下来的商业数据目前已经超过几百万条记录，数据量动辄可能达到 t b 级。几乎每一项事务都会生成一条计算机记录，这些大量数据中包含了富有 价值的信息，如趋势和模式，可以用于改进和优化事务决策。决策者们发现要 想获得竞争的优势，需要从大量的数据中( 包括业务数据、历史数据等) 提取出关 于自身业务的运作以及整个市场相关行业态势的数据进行分析，从而做出有利 的决策。例如，超级市场的经理可以从历年的销售记录中找到顾客的消费习惯 和爱好，而且通过对商品的销售情况分析，可以得到影响销售的因素，从而指 导上货，减少可能的积压。目前的数据库技术虽可以高效地实现数据的查询、 统计等功能，但却无法发现数据中存在的关系和规则，无法根据现有的数据预 测未来的发展趋势。因此，重要的决定常常不是基于数据库中信息丰富的数据， 而是凭决策者的直觉，但这样往往容易出现偏差和错误。因此，快速、准确、 高效地收集和分析信息是企业提高决策水平和增强企业竞争力的重要手段，于 是人们更希望让计算机能帮助我们自动地、智能地分析数据、理解数据，从而 进一步帮助我们做出决策。正是这种自然的需求成为数据挖掘研究蓬勃发展的 强大动力。 1 1 3 定义和处理阶段 数据挖掘也称为数据库中的知识发现( k d d ) 。指的是从存放在数据库、数 据仓库或其他信息库中的大量数据中挖掘出人们感兴趣的知识，这些知识是隐 含的、事先未知的潜在有用信息。目的是帮助决策者寻找数据间潜在的关联， 发现被忽略的要素，而这些信息对预测趋势和决策行为也许是十分有用的。 2 太原理工大学硕士研究生学位论文 数据挖掘技术能从d w 中自动分析数据，进行归纳性推理，从中发掘出潜 在的模式，或产生联想，建立新的业务模型，这是一个高级的处理过程。高级 的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形 成一种螺旋式上升过程。这个过程与人类问题求解的过程是存在巨大相似性的。 具体比较见表1 - 1 。挖掘过程可能需要多次的循环反复，每一个步骤一旦与预期 目标不符，都要回到前面的步骤，重新调整，重新执行。 表1 - 1 解决问题的步骤 t a b l e1 - 1 s t e p si ns o l v i n gap r o b l e m t y p i c a lh u m a nd e c i s i o nm a k i n gk n o w l e d g ed i s c o v e r yp r o c e s s d e f i n et h ep r o b l e md e f i n et h ep r o b l e m c o u e c tt h ef a c t so b t a i nd a t at od e m o n s t r a t e r e v i e wt h eq u a l i t yo fy o u rf a c t s p r e p r o c e s st h ed a t a g e n e r a l i z eo ny o u rf a c t s r e v i e w d e v e l o pam o d e l p o t e n t i a ls o l u t i o n s c h e c ky o u rg e n e r a l i z a t i o n sv a l i d a t et h em o d e l r e v i e wy o u ro b j e c t i v e sd e f i n ey o u ro b j e c t i ”c s e v a l u a t ea l ls o l u t i o n st od e t e r m i n et h e o p t i m i z e t h e p r o b l e m f m dt h e b e s t b e s t s o l u t i o ns o l u t i o n 1 1 4 系统结构及功能 典型的数据挖掘系统具有以下成分。见图1 2 3 太原理工大学硕士研究生学位论文 图1 - 2 数据挖掘系统结构 f i g u r e1 - 2s t r u c t u r eo fd a t am i n i n gs y s t e m 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、 电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求负责提取相关数 据。 知识库：这是领域知识，用于指导、搜索或评估结果模式的兴趣度。 数据挖掘引擎：这是数据挖掘系统的基本部分。由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此模块使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系 统交互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根据数据挖掘 的中间结果进行探索式数据挖掘。此外，次模块还允许用户浏览数据库和数据 仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型，其任务一般可 分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，预测 4 太原理工大学硕士研究生学位论文 性挖掘任务在当前数据上进行推断，以进行预测。在实际应用中，往往根据模 式的实际应用细分为以下6 种： 1 分类模式 2 回归模式 3 时间序列模式 4 聚类模式 5 关联模式 6 序列模式 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使 用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识， 因为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模 式的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数 据作为样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列 模式则是非监督知识，因为在模式建立前结果是未知的，模式的产生不受任何 监督。 1 2 分类算法 1 2 1 分类算法概述 数据分类( c l a s s i f i c a t i o n ) 是数据挖掘的一个重要内容，在统计学、机器学习、 神经网络和专家系统中得到了较早的研究，但只是近些年来，人们才将它与数 据库技术结合起来解决实际问题。数据分类实际上就是从数据库对象中发现共 j 性，并将数据对象分成不同几类的一个过程。通常分为两步：第一步，建立一 个模型，描述预定的数据类集或概念集。通过分析由属性描述的数据库元组来 构造模型。输入数据，即为建立模型而被分析的数据元组形成训练集( t r a i n i n g s e t ) ，是由一条条的数据库记录( r e c o r d ) 组成的。每一条记录包含若干条属性 ( a t t r i b u t e ) ，组成一个特征向量。训练集的每条记录还有一个特定的类标签( c l a s s l a b e l ) 与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具 5 太原理工大学硕士研究生学位论文 体样本的形式可为样本向量：( v - ，v z ，v n ：c ) 。在这里v 1 表示字段值，c 表示类别。这一步的目标是对训练数据进行分析，使用数据的某些特征属性， 给出每个类的准确描述。第二步，使用建好的模型进行分类。首先评估模型， 预测准确率，如果认为模型的准确率可以接受，就可以用它对类标号未知的数 据元组或对象进行分类。 分类和预测可以根据以下标准进行比较和评估 1 预测准确度预测准确度是用得最多的一种比较尺度，特别是对于预测 型分类任务，目前公认的方法是1 0 折分层交叉验证法。 2 计算复杂度计算复杂度依赖于具体的实现细节和硬件环境，在数据挖 掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常 重要的一个环节。 3 模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢迎； 例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就 难以理解。 4 强壮性这涉及给定噪声数据或具有空缺值的数据，模型正确预测的能 力。 5 可伸缩性这涉及当给定大量数据时，算法有效构造模型的能力。一个 算法是可伸缩的，如果给定内存和磁盘空间等可利用的系统资源，其运行时间 应当随数据库大小线性增加。 分类的典型应用：信用卡系统中的信用分级、市场调查、疗效诊断、寻找 店址等等。 1 2 2 举例说明分类的过程 信用卡系统的信用分级是分类的典型应用。图1 3 和图1 - 4 描述了信用分级 系统的运行机制。我们可以看到：这是一个分为两步走的过程，第一步是利用 训练数据集进行学习的过程，第二步是进行模型评估，降低模型噪音并投入实 际运行的过程。 6 太原理工大学硕士研究生学位论文 图1 - 3 学习 f i g u r e1 - 3l e a r n i n g 训练集( t r a i n i n gd a t a ) 被分类算法( c l a s s i f i c a t i o na l g o r i t h m ) 分析进而生成分 类规则( c l a s s i f i c a t i o nr u l e s ) 。 样本向量为( n a m e ，a g e ，i n c o m e ；c r e d i tr a t i n g ) ，c r e d i tr a t i n g 为类标签 7 太原理工大学硕士研究生学位论文 图1 - 4 分类 f i g u r e1 - 4c l a s s i f i c a t i o n 测试数据( r e s td a t a ) 用来建立准确的分类规则，如果准确性能被接受，则分 类规则将用来对新数据进行分类。 1 _ 3 主要工作 本文研究的就是归纳学习方法中的决策树算法。与其他算法相比，决策树 算法有如下优点： 1 速度快。 2 容易转化成分类规则。 3 更高的准确性。 4 模型简单，易理解。 目前，决策树的算法己有很多。1 9 7 9 年q u i n l a nj r 在m a c h i n el e a r n i n g j o u r n a l 发表了题为“i n d u c t i o no fd e c i s i o nt r e e ”的论文，引入了一种新的i d 3 算法，引起了很大的反响。在此基础上，他又于1 9 9 3 年，在其“p r o g r a mf o r 8 太原理工大学硕士研究生学位论文 m a c h i n e l e a r n i n g ”一书中，对i d 3 算法进行了补充和改进，提出了后来非常流 行的c 4 5 算法。之后又出现了c 4 5 的商业改进版c 5 0 算法，在大数据量情况 下的效率和生成规则的数量与正确性方面有了显著的提高。此外，c h a i d 算法 也有相当广泛的应用。1 9 9 6 年又有学者提出了s l i q 和s p r i n t 算法，它们强 调算法的可伸缩性。 由于数据挖掘的对象是规模庞大的数据，己有的分类算法在数据量小时能 够准确、高效的分类，效果很好。但当用于处理大量数据时，己有的算法都会 不同程度的出现各种问题，分类效果不理想。因此，研究数据挖掘中准确、有 效的分类算法，虽然是一个传统的问题，但其仍具有挑战性【5 ，6 】。 我的主要工作首先对决策树已有的算法进行研究。然后在这些算法的基础 上进行了改进，提出了基于属性相关性度量的方法，从而提高决策树生成的效 ， 率和规模。 1 4 论文的组织 豢 本论文的结构安排如下：第一章介绍数据挖掘及其分类算法；第二章描述 与本文工作相关的决策树的基本算法；第三章描述面向属性归约和相关性分析； 第四章提出对决策树算法的改进；第五章运用实验证明分析算法的正确性；最 后是整篇论文的总结。 。 9 太原理工大学硕士研究生学位论文 2 1 决策树简介 第二章决策树分类算法 分类技术流行的几个技术是贝叶斯分类、神经网络、遗传算法和决策树等。 与神经网络和贝叶斯分类比较，决策树更容易被人理解。而且，训练一个神经 网络将花费大量的时间和进行上千次的迭代，生成一个决策树就要有效的多， 因此适用于大的训练集。还有，决策树生成算法除了包含在训练数据中的信息 外不要求其他的信息( 例如领域知识或数据、类的概率分布的预知信息) 。最后， 与其他技术相比，决策树还表现了很好的分类精确度。 一个决策树包含零个或多个内部节点和一个或更多的叶子节点。全部的内 部节点有两个或更多的子节点。所有的内部节点包含一个划分，这个划分测试 属性的数字或逻辑表达式的值。连接内部节点和它的子节点的边用测试的不同 的输出来标注。每一个叶子有一个相关联的类。树的建立一般都是通过在内部 节点选择一个最优的测试对训练集反复的划分并建立下一级的节点，直到每个 划分都只包含同一种类的样本为止，这时我们称这个划( p u r e ) 。这个最 终的纯的划分形成了叶节点。 下面是构造决策树的一般性的描述： ( 1 ) 开始时是一个训练集和空树，接下去对训练集进行划分，使其最终归 属于不同的节点。 ( 2 ) 如果所有的当前节点的训练样本属于同一个类别，创建一个带有该类 的标签的叶子节点并停止。 ( 3 ) 否则，使用最优测量( g o o d n e s sm e a s u r e ) 计算每一个集合的每一个可能 的划分。 ( 4 ) 选择最优划分作为当前节点的测试。创建与该划分的不同输出数同样 多的子节点。 ( 5 ) 使用该划分的输出标注父亲和儿子之间的边并使用该划分把训练数据 1 0 太原理工大学硕士研究生学位论文 划分到子节点中。 ( 6 ) 把子节点作为当前节点，循环进行2 - 5 步骤，直到不存在可以划分的 节点为止。 建造好决策树以后，就要使用决策树对新的事例进行分类。分类是根据一 个事例的属性值计算它的类标签。一个事例计算它的类标签是将其从树的根节 点开始通过整个树。该事例从根节点开始，相继通过内部节点，最终到达某个 叶子节点。在每一个内部节点中，节点中的测试对事例进行测试，其结果决定 了该事例要通过哪一个分支到达下面哪一个节点。该事例的类就是最终叶子节 点的类。如果分类结果和事例所应属于的类不一致，那么该树对该事例分类出 错。决策树正确的分类的比例被称作正确率，相反错误分类的事例的比率称作 错误率。单变量决策树是一种在选择划分条件时只使用一个属性的树。一个多 变量树的测试可能使用包含多个属性的表达式。多变量树的一个例子是倾斜决 。策树( o b l i q u et r e e ) 。倾斜决策树的测试使用属性的线性联合。 寸 。 在决策树的建立过程中，另一个重要的问题是树的精确性和复杂度之间要 口 “取得一定的平衡。一种方法是反复的对模式进行简单化直到树的精确性和复杂 幸 “度达到所需的平衡。这种方法是使训练数据保持一定，而不停的对模式进行调 、 整。另一种方法是同时调整模式和训练集。这种方法先建立一个模式，然后删 除一些样本，使模式的在训练集上的自我评估能够最大程度的提高。这两步交 替执行直到达到预期的标准。这个过程称之为e s t e e m 旧i m i n a t i o no fs u s p i c i o u s t r a i n i n ge x a m p l e sw i t he r r o ro nt h em o d e l ) 。 自从h u n t ，m a r i n 和s t o n e 于1 9 6 6 年研制了第一个可用于决策树的概念学习 系统c l s 7 】以来，产生了不少决策树系统，如：q u i n l a n 于1 9 7 9 年提出的i d 3 1 8 】 算法并于1 9 9 3 年提出的c 4 5 【9 】算法，l e ob r e i m a n ，j e r o m ef r i e d m a n ，r i c h a r d o l s h e n h e 和c h a r l e ss t o n e 于1 9 8 4 年研制的c a r t t l 0 】等等。下面将对一些系统的 学习算法进行介绍。 太原理工大学硕士研究生学位论文 2 2 构造决策树算法 2 2 1c l s 学习算法 c l s 学习算法是1 9 6 6 年由h u n t ，m a r t i n e 和s t o n e 提出的早期的决策树学 习算法。后来的许多决策树学习算法都可以看作是c l s 算法的改进与更新。 c l s 算法的主要思想是从个空的决策树出发，通过添加新的判定结点来 改善原来的决策树，直至该决策树能够正确地将训练实例分类为止。 c l s 算法的主要步骤如下： ( 1 ) 令决策树t 的初始状态只含有一个树根( x ，q ) ，其中x 是全体训练实 例的集合，q 是全体测试属性的集合； ( 2 ) 若t 的所有叶结点( ) ( ，q ) 都有如下状态：或者第一个分量x f 中的训练 实例都属于同一个类，或者第二个分量q 为空，则停止执行学习算法，学习的 结果为t ； ( 3 ) 否则，选取一个不具有步骤( 2 ) 所述状态的叶结点( ) ( ，q ) ； ( 4 ) 对于q ，按照一定规则选取测试属性b ，设x 被b 的不同取值分为m 个不相交的子集x j ，l i m ，从，q ) 伸出m 个分叉，每个分叉代表b 的一个不 同取值，从而形成m 个新的叶结点( x i ，q 一 b ) ) ，l l 。 在算法的步骤( 4 ) 中，并未明确给出测试属性的选取标准，所以c l s 有很大 的改进空间。 2 2 2 i d 3 算法 在c l s 的基础上，后人陆续提出了多种决策树学习算法，其中最为有影响 的是q u i n l a n 于1 9 7 9 年提出的i d 3 算法。 i d 3 算法： ( 1 ) 选出整个训练实例集x 的规模为w 的随机子集x ，( w 称为窗口规模， 子集称为窗口) ； ：( 2 ) 以分类信息熵值最小为标准，选取每次的测试属性，形成当前窗口的 决策树； 。( 3 ) 顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外则 ，训练结束； k ( 4 ) 组合当前窗口的一些训练实例与某些在( 3 ) 中找到的例外形成新的窗 1 3 ，转( 2 ) 。 i d 3 对c l s 主要做了两方面的修改，即增加了窗口技术和提出了以信息熵 的下降速度作为选择测试属性的标准。 窗口技术：在c l s 算法中，因为每次运行开始的时候算法要知道所有训练 实例，当训练实例集过大的时候，实例无法立刻全部放入内存，会发生一些问 题。q u i n l a n 在i d 3 算法中引入了窗口( w i n d o w s ) 的方法进行增量式学习来解决 这个问题。为了在步骤( 4 ) 建立新的窗口，q u i n l a n 试验了两种不同的策略：一种 策略是保留窗口的所有实例，并添加从步骤( 3 ) 中获得的用户指定数目的例外， 这将大大扩充窗口；第二种策略相当于当前决策树的每一个叶结点保留一个训 练实例，其余实例则从窗口中删除，并用例外进行替换。实验证明两种方法都 工作得很好，但是如果概念复杂到不能发现固定规模w 的任意窗口的时候，第 1 3 太原理工大学硕士研究生学位论文 二种方法可能不收敛。 信息熵【“】：信息熵的下降速度是i d 3 中关键的选取测试属性的标准。信息 熵的下降也就是信息不确定性的下降。其基本内容是：设e = f i * f 2 聿- + f 。是n 维有穷向量空间，e 中的元素e = 称为样本，其中v i f j ，j = l ，2 ， n 。设p e 和n e 是e 的两个训练集，分别叫作正例集和反例集。 假设向量空间e 中的正例集p e 和反例集n e 的大小分别为p 和n 。则在该 空间中的信息熵为： l ( p ，n ) ：一旦_ + l o g ( 上一) 一生+ l o g ( 一)( 2 1 ) p 十np + np + np + n 假设属性a 作为决策树根的测试属性，a 具有v 个不同的离散值v 1 ，v 2 ， v 。，它将e 分为v 个子集e 1 ，e 2 ，日，假设e i 中含有p j 个正例和n j 个反例，子 集e j 的信息熵为i ( p i ，n j ) ，以属性a 为测试属性的期望信息熵为： 删= 享等v 吣) ( 2 2 ) 因此，以a 为根的信息增益是： g a i n ( a ) = i ( p ，n ) - e ( 2 3 ) 式( 2 2 ) 的值越小则式( 2 3 ) 的值越大，说明选择测试属性a 对于分类提供的 信息越大，选择a 之后对分类的不确定程度越小。i d 3 就是选择g a i n ( a ) 最大的 属性a 作为测试属性。根据a 的不同取值，生成a 1 的子节点a 1 ，a 2 ，a 。 i d 3 的基本原理是基于二叉分类问题，但很容易将其扩展到多叉分类上。 假设训练集中共有m 个样本，样本分别属于c 个不同的类，每个类的样本个数 为p i ，i = 1 ，2 ，c 。假设还以属性a 作为测试属性，e i 中含有第j 类样本的个数 为，j = 1 ，2 ，c ，那么，子集e i 的信息熵是： - _ 。辜詈q 。g ( 害) ( z 4 ) 属性a 的期望信息熵为： 1 4 太原理工大学硕士研究生学位论文 2 2 3c 4 5 算法 e ( 爿) ：萝盟+ ，( 巨) 乍m ( 2 5 ) c 4 5 是以i d 3 算法为核心的完整的决策树生成系统。它通过两个步骤来建 立决策树：树的生成阶段和树的剪枝阶段。c 4 5 在每一个节点通过使用测试评 估函数来选取具有最大函数值的测试作为最优测试来划分该节点。c 4 5 使用两 种测试评估函数，分别为：信息增益函数和信息增益率函数。信息增益函数的 定义己经在上部分加以介绍。 信息增益率函数的定义如下： 鲫r n t i o ( a ) = 揣 媳。 s p l i t ) 。毫鲁* l o g ( 争 ( 2 7 ) 信息增益函数对于那些可能产生多分支输出的测试倾向于产生大的函数 值，但是输出分支多不表示该测试对未知的对象具有更好的预测效果。信息增 益率函数可以弥补这个缺陷。以往的经验说明信息增益率函数比信息增益函数 更健壮，能稳定的选择好的测试。因此c 4 5 将信息增益率作为缺省的测试评估 函数。 信息增益率函数也有它的缺陷。如果划分的优度非常小，也就是划分的信 息熵值非常小，信息增益率会不稳定。c 4 5 引入一个限制来解决这个问题：待 选的测试的信息增益值不能小于所有的检测过的测试的平均信息增益值。然而 这个限制有其负面的影响。如果属性集中存在无关属性，即便该属性没有被选 为测试属性，也将影响信息增益率的效果。因为引进的无关属性会降低测试的 信息增益的平均值，所以一些具有高信息增益率而低信息增益的属性将成为最 优的测试属性。这种情况就不会在使用信息增益函数的决策树中出现。 对于连续值属性a ，c 4 5 使用如下的测试形式：a r ，r 是l 艋界值。 1 5 太原理工大学硕士研究生学位论文 c 4 5 寻找最优的r 的方法是： 1 先将训练集的样本根据属性a 的值排序。 2 按顺序逐一将两个相邻的样本a 的平均值r = ( a 1 + a 2 ) 2 作为分割点。 假设训练集有n 个样本，则共有n 1 个分割点。分割点将训练集划分为两部分， 一部分a 的值小于等于分割点，另一部分a 的值大于分割点。比较所有可能的 分割点并将最优的分割点作为临界值r 对于测试的输出，c 4 5 除了将属性的所有可能的值作为输出这一种方法外， 还使用另外一种方法。它将属性的所有的可能的值分成几个子集。每个子集对 应一个输出。对于一个有n 个值的属性来说，有2 - l 1 个不同二分划分。所以要 确定如何对属性的值域进行划分是能通过对属性值域的所有可能划分空间进行 完全搜索来实现的。c 4 5 开始时，生成一系列的属性值子集，每个子集有且仅 有该属性值域的一个元素。然后将这些集合进行合并。c 4 5 将任意的两个子集 合并，然后使用测试评估函数来检测其结果，将结果最优的一对合并。这个过 程循环进行直到剩下两个子集或合并再也不能产生更好的划分为止。 c 4 5 处理丢失的属性值的方法是：在计算期望信息熵时，只计算那些已知 测试属性值的样本，然后乘以这些样本在当前节点的训练集中的比例作为整个 训练集的期望信息熵：在计算划分信息熵时，把那些丢失测试属性值的样本作 为一个新的类别对待，单独计算这些样本的期望信息熵；在划分训练集时，先 将正常的样本按照一般的算法划分成几个子集，然后把那些丢失测试属性值的 样本按照一定的概率分布到各个子集中。子集中的丢失测试属性值的样本与测 试属性值的样本保持一个比例关系：在对丢失测试属性值的未知事例的分类时， c 4 5 将该事例通过所有的分支，然后将结果进行合并，使它成为在类上的概率 分布而不是某一个类。最终结果是具有最大概率的类。 c 4 5 的剪枝使用悲观剪枝法，该方法我们将在后章进行介绍。 c 4 5 使用以下的标准终止树的增长： 1 当前节点的所有的训练样本属于一个类别。 2 每一个可能的测试的潜在的子树中少于两个的子树有比预定义的数量多 的样本。该数量的缺省值是2 。 1 6 太原理工大学硕士研究生学位论文 3 找不到具有正的测试评估函数值的测试。 2 1 3 处理大规模数据集的决策树 i d 3 或者c 4 5 算法都是在建树时将训练集一次性装载入内存的。但当面对 大型的有着上百万条纪录的数据库时，就无法实际应用这些算法。针对这一问 题，前人提出了不少改进方法，如数据采样法、连续属性离散化法或将数据分 为若干小块分别建树然后综合成一个最终的树，但这些改进都以降低了树的准 确性为代价。直到m e t h a ，a g r a w a l 和r i s s a n e 在1 9 9 6 年提出了s l i q ”j 方法，以 及在此基础上进行改进得到的s p r i n t ”j 方法。 2 3 1s l i q 算法 ? s l i q 采用了预排序，广度优先增长策略和m d l l l 4 1 剪枝等一系列技术来建 立和修剪决策树，使s l i q 可以对常驻磁盘的大量数据集进行快速的分类。 一 0 、 当在决策树节点上发现一个好的划分，对于连续属性，排序时间是一个主 擞要的