(计算机软件与理论专业论文)决策树分类算法的研究与改进.pdf_第1页
(计算机软件与理论专业论文)决策树分类算法的研究与改进.pdf_第2页
(计算机软件与理论专业论文)决策树分类算法的研究与改进.pdf_第3页
(计算机软件与理论专业论文)决策树分类算法的研究与改进.pdf_第4页
(计算机软件与理论专业论文)决策树分类算法的研究与改进.pdf_第5页
已阅读5页,还剩41页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

盗茎塑坌耋竺婆竺塑塞量堕垄一 摘要 ( 数据挖掘又称数据库中的知识发现,是数据库研究最活跃的领域之一。通过数 据挖掘可以从数据库中提取出可信、新颖、有效并易于理解的知识、规律或高层信 息。发现的知识可用于决策、过程控制、信息管理、查询处理等方面,因此数据挖 掘的技术和应用有了飞快的发展,正日益引起国内外学术界和产业界的,“泛关注。 数据分类是数据挖掘中一个重要的内容。分类的方法很多,其中决策树是一种 常用的算法。与其他分类算法相比,它能够较快的建立简单、易于理解的模型,容 易转换成规则,而且具有与其他分类模型同样的,有时甚至更好的分类准确性。“。 本文主要对达筮挝筮差篁鎏展开研究,主要包含两个内容: 1 研究了l ! q 篡鎏和;! 曼型! 箕法,因为这两个算法可以说是目前决策树算法中 最有效的。其中主要对两个算法分别在串行、并行情况下的执行时间进行了分析、 比较,得出了一些建设性的结论。 2 对s l i q 算法和s p r i n t 算法进行了改进。目前这两种算法所处理的都是固定人 小的训练集。将增量式学习的方法与建树算法相结合,使其能够处理不断生长的 训练集,提高算法的实时、有效性。本文还证明了改进算法的正确性。 2 决策树分类算法的研究与改进 a b s t r a c t d a t am i n i n g ,a l s ok n o w na sk n o w l e d g ed i s c o v e r yi nd a t a b a s e ( k d d ) ,i so n eo ft h e m o s ta c t i v ef i e l d si nd a t a b a s e d a t am i n i n ga i m st od i s c o v e rm a n yt r u s t f u l n o v e l - u s e f u l a n dr e a d a b l ek n o w l e d g e ,r u l e so ra b s t r a c ti n f o r m a t i o n ,w h i c hc a l lb ea p p l i e di nd e c i s i o n , p r o c e s sc o n t r o l ,i n f o r m a t i o nm a n a g e m e n t ,q u e r yp r o c e s sa n d s oo n s ot h et e c h n i q u ea n d a p p l i c a t i o no f d a t am i n i n g d r a w u p o n t h ea t t e n t i o no f t h ei n t e r n a t i o n a la c a d e m i c s o c i e t ya n d d e v e l o pr a p i d l y c l a s s i f i c a t i o ni sa ni m p o r t a n tp a r to fd a t a m i n i n gp r o b l e m s s e v e r a lc l a s s i f i c a t i o n m o d e l sh a v eb e e np r o p o s e do v e rt h e y e a r s a m o n g t h o s em o d e l s ,d e c i s i o nt r e ei sak i n do f m o d e lu s e di nf o r e c a s t d e c i s i o nt r e em o d e l sa r es i m p l ea n de a s yt o u n d e r s t a n d ,e a s i l y c o n v e n e di n t or u l e s i ta l s oc a nb ec o n s t r u c t e dr e l a t i v e l yf a s tc o m p a r et os o m eo fo t h e r m e t h o d s m o r e o v e r ,d e c i s i o nt r e ec l a s s i f i e r so b t a i ns i m i l a ra n ds o m e t i m e sb e t t e ra c c u r a c y w h e n c o m p a r e d w i t hs o m eo f o t h e rc l a s s i f i c a t i o nm e t h o d s t h i sp a p e ri sas t u d yo nd e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h m s ,w h i c h m a i n l yi n c l u d e s t w o p a r t s i nt h ef i r s tp a r t , t w od e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h m s ,s l i qa n ds p r i n t , i s s t u d i e d ,b e c a u s et h e ya r et h em o s tu s e f u la tp r e s e n t w ea n a l y s i st h e s p e n d t i m ei nb u i l d i n g ad e c i s i o nt r e ew i t h s l i qa n ds p r i n t ,b o t hi ns e r i a la n di np a r a l l e le n v i r o n m e n t f i n a l l y ,w ec o m et os o m ec o n s t r u c t i v ec o n c l u s i o n s i nt h es e c o n dp a r t ,a n i m p r o v e m e n to fs l i qa n ds p r i n ta l g o r i t h mi sp r o p o s e d s l f qa n ds p r i n ta r ea l lf a c e dw i t hf i x e dt r a i n i n gs e t w ec o m b i n ei n c r e m e n t a lm e t h o d s w i t ht r e eb u i l d i n ga l g o r i t h ma n d p r e s e n tan e wa l g o r i t h m ,w h i c hi ss u i t a b l ef o ri n c r e a s i n g l y t r a i n i n gs e ta n di sv e r ye f f i c i e n t t h ec o l t e c t o e s so fo u ri m p r o v e m e n ta l g o r i t h mi sa l s o g i v e n i nt h i sp a r t 3 第一章数据挖掘及其分类算法 1 1 数据挖掘 1 1 1 历史 一切新事物的产生都是由需求而驱动的。随着数据库技术和数据库系统在各行 业的广泛应用,当今的人们生活在数据和信息的海洋中。有些公司经过长年累月积 累下来的商业数据目前已经超过几百万条记录,而象气象部门每天的数据量就达到 了1 g ( i g = 1 0 0 0 m ) 。几乎每一项事务都会生成一条计算机记录,这些大量数据中包含 了富有价值的信息,如趋势和模式,可以用于改进和优化事务决策。决策者们发现 要想获得竞争的优势,需要从大量的数据中( 包括业务数据、历史数据等) 提取出 关于自身业务的运作以及整个市场相关行业态势的数据进行分析,从而作出有利的 决策。例如:超级市场的经理可以从历年的销售记录中找到顾客的消费习惯和爱好, 而且通过对商品的销售情况分析,可以得到影响销售的因素,从而指导上货,减少 可能的积压。目前的数据库技术虽可以高效地实现数据的查询、统计等功能,但却 无法发现数据中存在的关系和规则,无法根据现有的数据预测未来的发展趋势。因 此,重要的决定常常不是基于数据库中信息丰富的数据,而是凭决策者的直觉,但 这样往往容易出现偏差和错误。因此,快速、准确、高效地收集和分析信息是企业 提高决策水平和增强企业竞争力的重要的手段,于是人们更希望让计算机能帮助我 们自动、智能地分析数据、理解数据,从而进一步帮助我们作出决策。止是这种自 然的需求成为数据挖掘研究蓬勃发展的强大动力。 1 1 2 定义和处理阶段 数据挖掘也称为数据库中的知识发现( k d d ) 。指的是从存放在数据库、数据 仓库或其他信息库中的大量数据中挖掘出人们感兴趣的知识,这些知识是隐含的、 事先未知的潜在有用信息。目的是帮助决策者寻找数据间潜在的关联,发现被忽略 的要素,而这些信息对预测趋势和决策行为也许是十分有用的。 数据挖掘技术能从d w 中自动分析数据,进行归纳性推理,从中发掘出潜在的 模式,或产生联想,建立新的业务模型,这是一个高级的处理过程。高级的处理过 程是指一个多步骤的处理过程,多步骤之间相互影响、反复调整,形成一种螺旋式 上升过程。这个过程与人类问题求解的过程是存在巨大相似性的。具体比较见图1 1 。 4 决策树分类算法的研究与改进 挖掘过程可能需要多次的循环反复,每一个步骤一旦与预期目标不符,都要回到前 面的步骤,重新调整,重新执行。 b p i lh u m a n d e c i s i o nm a k i n g k n o w l e d g ed i s c o v e r y p 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 e p r o b l e m c o l l 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 p a s te x p e r i e n c e r e v i e wt h e q u a l i t yo f y o u r f a c t s p r e p r o c e s s t h ed a t a g e n e r a l i z eo n y o u r f a c t s r e v i e w d e v e l o p am 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 k y o u rg e n e r a l i z a t i o n s v a l i d a t et h em o d e l r e v i e wy o u r o b j e c t i v e s d e f i n ey o u r o b j e c t i v e 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 i n d t h eb e s t b e s ts o l u t i o n s o l u t i o n 图1 - 1 s t e p si ns o l v i n ga p r o b l e m 1 1 3 系统结构及功能 典型的数据挖掘系统具有以下成分。见图1 - 2 数据规范和鼻 图1 - 2 数据挖掘系统结构 堡篁盟坌耋竺鲨塑竺茎兰垦堂一 数据库、数据仓库或其他信息库:这是一个或一组数据库、数据仓库、电子 表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器:根据用户的数据挖掘请求负责提取相关数据。 知识库:这是领域知识,用于指导、搜索或评估结果模式的兴趣度。 数据挖掘引擎:这是数据挖掘系统的基本部分。由一组功能模块组成,用丁 特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块:通常,此模块使用兴趣度度量,并与数据挖掘模块交互,以 便将搜索聚焦在有趣的模式上。 图形用户界面:本模块在用户和数据挖掘系统之间通信,允许用户与系统交 互,指定数据挖掘查询或任务,提供信息,帮助搜索聚焦,根据数据挖掘的中 间结果进行探索式数据挖掘。此外,次模块还允许用户浏览数据库和数据仓库 模式或数据结构,评估挖掘的模式,以不同的形式对模式可视化。 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型,其任务一般可分为 两类:描述和预测。描述性挖掘任务刻划数据库中数据的一般特性,预测性挖掘任 务在当前数据上进行推断,以进行预测。在实际应用中,往往根据模式的实际应用 细分为以下6 种: 1 分类模式 2 回归模式 3 时间序列模式 4 聚类模式 5 关联模式 6 序列模式 在解决实际问题时,经常要同时使用多种模式。分类模式和回归模式是使用最 普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识,因为在 建立模式前数据的结果是已知的,可以直接用来检测模式的准确性,模式的产生是 在受监督的情况下进行的。一般在建立这些模式时,使用一部分数据作为样本,用 另一部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是非监督知识, 因为在模式建立前结果是未知的,模式的产生不受任何监督。 1 2 分类算法 6 迭箜垫坌耋竺鲨盟竺窒皇堕垄一 1 2 1 分类算法概述 数据分类( c l a s s i f i c a t i o n ) 是数据挖掘的一个重要内容,在统计学,机器学习、 神经网络和专家系统中得到了较早的研究,但只是近些年来,人们才将它与数据库 技术结合起来解决实际问题。数据分类实际上就是从数据库对象中发现共性,并将 数据对象分成不同几类的一个过程,分为两步:第一步,建立一个模型,描述预定 的数据类集或概念集。通过分析由属性描述的数据库元组来构造模型。输入数据, 即为建立模型而被分析的数据元组形成训练集( t r a i n i n gs e t ) ,是由一条条的数据库 记录( r e c o r d ) 组成的。每一条记录包含若干条属性( a t t r i b u t e ) ,组成一个特征向 量。训练集的每条记录还有一个特定的类标签( c l a s sl a b e l ) 与之对应。该类标签是 系统的输入,通常是以往的一些经验数据。一个具体样本的形式可为样本向量:( v 。, v 。,v n :c ) 。在这里v :表示字段值,c 表示类别。这一步的目标是对训练数据 进行分析,使用数据的某些特征属性,给出每个类的准确描述。第二步,使用建好 的模型进行分类。首先评估模型,预测准确率,如果认为模型的准确率可以接受, 就可以用它对类标号未知的数据元组或对象进行分类。 分类和预测可以根据以下标准进行比较和评估 1 预测准确度预测准确度是用得最多的一种比较尺度,特别是对于预测型分 类任务,目前公认的方法是l o 一折分层交叉验证法。 2 计算复杂度计算复杂度依赖于具体的实现细节和硬件环境,在数据挖掘中, 由于操作对象是巨量的数据库,因此空间和时间的复杂度问题将是非常重要 的一个环节。 3 模型描述的简洁度对于描述型的分类任务,模型描述越简洁越受欢迎:例如, 采用规则表示的分类器构造法就更有用,而神经网络方法产生的结果就难以 理解。 4 强壮性这涉及给定噪声数据或具有空缺值的数据,模型正确预测的能力。 5 可伸缩性这涉及当给定大量数据时,算法有效构造模型的能力。一个算法 是可伸缩的,如果给定内存和磁盘空间等可利用的系统资源,其运行时间应 当随数据库大小线性增加。 分类的典型应用:信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址 等等。 7 盗篁堕坌耋竺鲨塑竺塞皇塾鲎 1 2 2 举例说明分类的过程 信用卡系统的信用分级是分类的典型应用。图1 - 3 和图1 - 4 描述了信用分级系统 的运行机制。我们可以看到:这是一个分为两步走的过程,第一步是利用训练数据 集进行学习的过程,第二步是进行模型评估,降低模型噪音并投入实际运行的过程。 图1 _ 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 8 决策树分类算法的研究与改进 e x c e l l e n t 图1 - 4c l a s s i f i c a t i o n测试数据( t e s td a t a ) 用来建立准确的分类规则,如果准确 性能被接受,则分类规则将用来对新数据进行分类。 1 3 主要工作 本文研究的就是归纳学习方法中的决策树算法。与其他算法相比,决策树算法 有如下优点: l 。速度快。 2 容易转化成分类规则。 3 更高的准确性。 4 模型简单,易理解。 目前,决策树的算法已有很多。1 9 8 6 年j r o s s q u i n l a n 在m a c h i n e l e a m i n g j o u r n a l 发表了题为“i n d u c t i o no f d 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 rm a c h i n el 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 算法,它们强调算法的可伸缩性。 9 决策树分类算法的研究与改进 由于数据挖掘的对象是规模庞大的数据,已有的分类算法在数据量小时能够准 确、高效的分类,效果很好。但当用丁二处理人量数据时,已有的算法都会不同程度 的出现各种问题,分类效果不理想。因此,研究数据挖掘中准确、有效的分类算法, 虽然是一个传统的问题,但其仍具有挑战性。 我的主要工作首先对决策树已有的算法进行研究,其中重点研究了s l i q 和 s p r i n t 算法,因为这两个算法可以说是目前决策树算法中最有效的,对二者的性能 进行了分析、比较,得出了一些建设性的结论。然后在此算法的基础上进行了改进, 使其能够适应不断生长的训练集,从而提高算法的实时有效性。 1 4 论文的组织 本论文的结构安排如下:第一章介绍数据挖掘及其分类算法;第二章描述与本 文工作相关的决策树的基本算法、s l i q 和s p r i n t 算法;第三章分析、比较s l i q 和s p r l n 算法:第四章对s l i q 和s p r i n t 算法的改进;最后是整篇论文的总结。 1 0 决策树分类算法的研究与改进 第二章决策树分类算法 2 1 决策树 一棵决策树是这样一棵树,该树的每个非终端点均表示被考察数据项目的一个 测试或决策。根据测试结果,选择某个分支。为了分类一个特定数据项目,我们从 根结点开始,一直向下判定,直到到达一个终端结点( 或叶子) 为止。当到达一个 终端结点时,一个决策便形成了。 决策树( d e c i s i o nt r e e ) 是运用于分类的一种类似于流程图的树结构。其中的每 个内部节点( i n t e r n a ln o d e ) 代表对某个属性的一次测试,一条边代表一个测试结果, 叶子( 1 e a f ) 代表某个类( c l a s s ) 或者类的分布( c l a s sd i s t r i b u t i o n ) 。最上面的节点 是根结点。图2 - 1 给出了一个商业上使用的决策树的例子。它表示了一个关心电子 厂品的用户是否会购买p c 机的知识,用它可以预测某条记录( 某个人) 的购买意向。 图2 - 1ad e c i s i o nt r e ed e m o这棵决策树对“买计算机”的销售记录进行分类。 指出一个电子产品消费者是否会购买台计算机。每个内部节点( 方形框) 代表对 某个属性的一次检测。每片叶子( 椭圆框) 代表一个类( b u y sc o m p u t e r s = y e s 或者 b u y s _ c o m p u t e r s - - a o ) 。这个例子中,样本向量如f :( a g e ,s t u d e n t ,c r e d i t _ r a t i n g ; b u y s _ c o m p u t e r s ) ,被决策数据的格式为( a g e ,s t u d e n t ,c r e d i t _ r a t i n g ) 。输入新的被决策 的记录,可以预测该记录隶属于哪个类。 2 2 决策树的生成算法 决策树分类算法的研究与改进 用决策树进行分类分两步走。第一步是利用训练集建立并精化一棵决策树,建 立决策树模型。这个过程实际上是一个从数据中获取知识,进行机器学习的过程。 第二步是利用生成完毕的决策树对输入数据进行分类。对输入的纪录,从根节点依 次测试记录的属性值,直到到达某个叶子节点,从而找到该记录所在的类。 问题的关键是建立棵决策树。这个过程通常分为两个阶段:建树( t r e e b u i l d i n g ) 和剪枝( t r e ep r u n i n g ) 。决策树的基本算法是贪心算法,它以自顶向下递 归的各个击破方式构造决策树。算法概述见图2 2 是著名的决策树归纳算法i d 3 版 本。剪枝的目的是降低由于训练集存在噪声而产生的起伏。 2 2 1 建树算法 算法:g e n e r a t e _ d e c i s i o n _ t r e e 由给定的训练数据产生一棵决策树 输入:训练样本s a m p | 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 h e n ( 3 ) 返回n 作为叶节点,以类c 标记; ( 4 ) i f a t t r i b u t e _ l i s t 为空t h e n ( 5 ) 返回n 作为叶节点,标记为s a m p l e s 中最普通的类;多数表决 ( 6 ) 选择a t t r i b u t e _ l i s t 中具有最高信息增益的属性t e s ta t t r i b u t e : ( 7 ) 标记节点n 为t e s ta t t r i b u t e ; ( 8 ) f o r e a c h t e s t _ a t t r i n u t e 中的已知值a i 划分s a m p l e s ( 9 ) 由节点n 长出一个条件为t e s t _ a t t r i b u t e = a j 的分支: ( 1 0 ) 设s ,是s a m p l e s 中t e s t _ a t t r i b u t e = a i 的样本的集合:一个划分 ( 】1 ) i f 为空t h e n ( 1 2 ) 加上一个树叶,标记为s a m p l e s 中最普通的类: ( 1 3 ) e l s e 加上一个由 g e n a r a t e _ d e c i s i o nt r e e ( s i ,a t t r i b u t e _ ) i s t t e s l _ a t m b u t e ) 返回的节点; 图2 - 2 由训练样本归纳决策树的基本算法 1 2 决策树分类算法的研究与改进 树以代表训练样本的单个节点开始( 步骤1 ) 如果样本都在同一个类,则该节点成为树叶,并用该类标记( 步骤2 和3 ) 否则,算法使用称为信息增益的基于熵的度量作为启发信息,选择能够最好的将样 本分类的属性( 步骤6 ) 。该属性成为该节点的“测试”或“判定”属性( 步骤7 ) 。 算法的这个版本中,所有的属性都是分类的,即取离散值,连续值的属性必须离散 化。 对测试属性的每个已知的值,创建一个分支,并据此划分样本( 步骤8 1 0 ) 算法使用同样的过程,递归地形成每个划分上的样本决策树。一旦一个属性出现在 一个节点上,就不必考虑该节点的任何后代上( 步骤1 3 ) 递归划分步骤仅当下列条件之一成立时停止: ( a ) 给定节点的所有样本属于同一类( 步骤2 和3 ) 。 ( b ) 没有剩余属性可以用来进一步划分样本( 步骤4 ) 。在此情况下,使用多数表决 ( 步骤5 ) 。这涉及将给定节点转换成树叶,并用s a m p l e s 中的多数所在的类标记 它。换一种方式,可以存放节点样本的类分布。 ( c ) 分支t e s t _ a t t r i b u t e = a _ i 没有样本( 步骤l1 ) 。在这种情况卜,以s a m p l e s 中的多数 类创建一个树叶( 步骤1 2 ) 。 在树的每个节点上使用信息增益( i n f o r m a t i o ng a i n ) 作为衡量节点分裂质量的指 标,这种度量称作属性选择度量或分裂的优良性度量。选择具有最高信息增益( 或 最人熵压缩) 的属性作为当前节点的测试属性,该属性使得对结果划分中的样本分 类所需信息量最小,并反映划分的最小随机性或“不纯性”。这种信息理论方法使得 对一个对象分类所需的期望测试数目达到最小,并确保找到一棵简单的( 但不必是 最简单的) 树。 1 9 4 8 年,香农( c e s h a n n o n ) 提出了信息论。其中对信息量( i n f o r m a t i o n ) 和熵( e n t r o p y ) 的定义: i n f o r m a t i o n = 一i n 9 2b e n t r o p y = - jp i l 0 9 2 ( p i ) 熵实际上是系统信息量的加权平均,也就是系统的平均信息量。i n f o r m a t i o ng a i n 指 标的原理就取自信息论。 因为这是一个递归过程,所以仅仅需要讨论对某个特定节点n 的分裂方法。 分割前: 1 3 盗丝盟坌鲞苎鲨塑堕塞皇堕鲎 一 设指向n 的训练集为s ,其中包含m 个不同的类c ,( f o r i 2 1 ,m ) 。设s t 是s 中 属于类c 的记录的个数。那么分裂之前,系统的总熵: i ( s ”8 2 ,s 。) = 一俨l 协。) p i i 0 9 2 ( p j 其中p l 是任意样本属于c 的概率,并用s , s 估计。容易看出,总熵是属r 各个类的 记录的信息量的加权平均。 分割后: 现在属性a 是带有v 个不同值的属性 a 。,a 2 ,a ,a 可以把s 分成v 个子集 s t , s :,s v 其中s = xix s & x a = 吗 。如果a 被选为测试属性,那么那些子集表 示从代表集合s 的出发的所有树枝。设s 。表示在s j 中类为c 。的记录个数。那么,这 时按a 的每个属性值( 更一般的是取a 的一个子集) 进行分割后的信息量,也就是 系统总熵为: e ( a ) = o 1 l o ”( ( s i i + s z j + ”+ s m j ) s ) l ( s q + s 2 j + “+ s m j ) 项( ( s 。+ s :+ 。+ s m ) s ) 表示第j 个子集的权重,s = isl 。熵值越小,子集划分的纯度越高。 子集s 的信息量( 子集的总熵) : i ( s l j + 8 动+ + 8 m j ) = ( h l t o m ) p q i 0 9 2 ( p i j ) 总熵e ( a 、是各个子集信息量的加权平均。 从而,引入一个量:信息增益( i n f o r m a t i o ng a i n ) ,表示系统由于分类获得的 信息量。由系统熵的减少值定量描述。对n 用属性a 分类后的信息增益为: g a i n ( a ) = i ( s l ,s z ,s 。) 一e ( a ) 即g a i n ( a ) 是由于知道属性a 的值而导致的熵的期望压缩。 熵是一个衡量系统混乱程度的统计量。熵越大,表示系统越混乱。分类的目的 是提取系统信息,使系统向更加有序、有规则组织的方向发展。所以自然而然的, 最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是i n f o r m a t i o ng a i n ,所 以,算法计算每个属性的信息增益,具有最高信息增益的属性作为测试属性。创建 一个节点,并以该属性标记,对属性的每个值创建分支,并据此划分样本。通常, 最佳方案是用“贪心算法+ 深度优先搜索”得到的。 2 2 2 剪枝 当决策树创建时,由于数据中的噪声和孤立点,许多分支反映的是训练数据中 的异常。剪枝方法处理这种过分适应数据问题。通常使用统计度量,剪去最不可靠 1 4 达丝塑坌耋竺鲨箜翌窒皇垦垄 的分支,这将导致较快的分类,提高树独立于测试数据正确分类的能力。主要有两 类剪枝方法: 1 同步修剪( p r e - p r u n i n g ) : 在建树的过程中,当满足一定条件,例如i n f o r m a t i o ng a i n 或者某些有效统计量 达到某个预先设定的阈值时,节点不再继续分裂,内部节点成为一个叶子节点。 叶子节点取子集中频率最大的类作为自己的标识,或者可能仅仅存储这些实例的 概率分布函数。然而,选取一个适当的阈值是困难的,因为较高的闽值可能导致 过分简化的数,而较低的阈值可能使得树的化简太少。 2 迟滞修剪( p o s - p r u n i n g ) : 与建树时的训练集独立的训练数据进入决策树并到达叶节点时,训练数据的c l a s s l a b e l 与叶子节点的c l a s sl a b e l 不同,这时称为发生了分类错误。当树建好之后, 对每个内部节点,算法通过每个枝条的出错率进行加权平均,计算如果不剪枝该 节点的错误率。如果裁减能够降低错误率,那么该节点的所有儿子就被剪掉,而 该节点成为一片叶子。出错率用与训练集数据独立的测试数据校验。最终形成一 棵错误率尽可能小的决策树。 在实际应用中可以交叉使用同步修剪和迟滞修剪,形成组合式方法。迟滞修剪所 需的计算比同步修剪多,但通常产生更可靠的树。 2 2 3 一般决策树的劣势 】缺乏伸缩性:由于进行深度优先搜索,所以算法受内存大小限制,难于处理大训练 集。一个例子:在l r v i n e 机器学习知识库中,最大可以允许的数据集仅仅为7 0 0 k b , 2 0 0 0 条记录。而现代的数据仓库动辄存储几个g b y t e s 的海量数据。用以前的方 法是显然不行的。 2 不能处理连续属性,必须先对其离散化、取样,而为了这种处理大数据集的种种 算法,不仅增加了分类算法的额外开销,而且降低了分类的准确性。 2 3s l i q 算法 s l i q 算法是i b ma l m a d e nr e s e a r c hc e n t e r 于1 9 9 6 年提出的一种高速可伸缩的 数据挖掘分类算法。它通过预排序技术,着重解决当数据量巨大,无法全部装入内 存时,如何高速准确地生成决策树。该算法定义使用新的数据结构,以利于树的构 1 5 迭丝堕坌耋竺鲨塑婴窒皇垦苎 一 造,能同时处理离散字段和连续字段。 2 3 1s l i q 的可伸缩性指标 2 3 1 1g i n ii n d e x 一般决策树中,使用信息量作为评价节点分裂质量的参数。s l i q 算法中,我们 使用g i n i 指标( g i n ii n d e x ) 代替信息量( i n f o r m a t i o ng a i n ) ,g i n i 指标比信息鼍性能 更好,且计算方便。对数据集包含n 个类的数据集s ,g i n i ( s ) 定义为: g i n i ( s ) = 1 - e p j + p j p j 是s 中第j 类数据的频率。g i n i 越小,i n f o r m a t i o ng a i n 越大。g i n i 指标最火的特点 是计算时只需考虑类值在被划分的每一部分的分布情况。 2 3 1 2 属性的分裂方法 区别于一般的决策树,s l i q 采用二分查找树结构。对每个节点都需要先计算最 佳分裂方案,然后执行分裂。 对于数值型连续字段( n u m e r i ca t t r i b u t e ) 分裂的形式a - - v 。所以,可以先对 数值型字段排序,假设排序后的结果为v 。,v :,v 。,因为分裂只会发生在两个节点 之间,所以有n 1 种可能性。通常取中点( m + 7 ) 2 作为分裂点。从小到大依次取 不同的s p l i tp o i n t ,取i n f o r m a t i o ng a i n 指标最大( g i n i 最小) 的一个就是分裂点。因 为每个节点都需要排序,所以这项操作的代价极大,降低排序成本成为一个重要的 问题,s l i q 算法对排序有很好的解决方案,在后面对算法的描述中,将很详细的看 到这一点。 对于离散型字段( c a t e g o r i c a la t t r i b u t e ) ,设s ( a ) 为a 的所有可能的值,分裂 测试将要取遍s 的所有子集s 。寻找当分裂成s 和s s 两块时的g i n i 指标,取到 g i n i 最小的时候,就是最佳分裂方法。显然,这是一个对集合s 的所有子集进行遍历 的过程,共需要计算2i s l 次,代价也是很大的。s l i q 算法对此也有一定程度的优化。 2 3 1 3 剪枝 s l i q 的剪枝算法m d l 属于迟滞剪枝( p o s p r u n n i n g ) 算法。通常的迟滞剪枝的 数据源采用一个t r a i n i n gs e t 的一个子集或者与t r a i n i n gs e t 独立的数据集进行操作。 例如下面的两个算法: 1 6 决策树分类算法的研究与改进 1 交叉校验:用训练集的若干个子集分别生成几棵测试树,与原树比较,测 试出错率。这样比较准确,但是,数据量巨大时,这样做的系统代价过于 昂贵。 2 把训练集分成两部分,一部分建立决策树,另一部分用于剪枝。用于剪枝 的数据集捕获数据出错的概率分布,然后用2 2 2 的方法进行剪枝。这样做 的缺陷是浪费了一部分训练数据,降低了系统的准确性。测试数据的选取 原则,测试数据的规模也是很难有一个统一的标准进行确定的。 m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) 的目标是生成一棵描述长度最小的决策树。 m d l 原理认为:最优的编码模型是描述数据代价最小的模型。如果模型m 对数据集 d 进行编码,那么描述代价: c o s t ( m ,d ) = c o s t ( d i m ) + c o s t ( m ) 其中,c o s t ( mld ) 表示用模型m 对数据d 编码的编码代价,单位b i t s ,c o s t ( m ) 表示描述模型本身所需的编码长度。 假设对决策树的一个叶子节点上的训练集d 进行编码,编码长度为:l o g :( k ) + x ( 1 0 9 2 ( i ) + l 0 9 2 ( k - 1 ) ) 。x 是叶子节点上的不同于叶子类标签的样本个数,i 是该叶子上 的样本个数,k 是类别的个数。l 0 9 2 ( k ) 个比特用于确定叶子节点的类标签,对于x 个 例外中的每一个来说都需要l 0 9 2 ( i ) 个比特用于在i 个样本中确定该样本,i 0 9 2 ( k - 1 ) 个 比特用于在除去叶子节点的类别以外的其它k _ 1 个类别中来确定该样本所属的类别。 对树的结构的编码c o s tc m ) ,对于每个节点来说,它可能包含0 个,1 个, n 个子分支,假设剪枝阶段只有两种可能:( 1 ) 将该节点的所有的分支剪去使其成为 叶子。( 2 ) 不剪枝,则我们要用l 0 9 2 ( n + 1 ) 个比特来表示一个节点。 2 3 2 算法的描述 2 3 2 1 算法的总流程 首先介绍整个算法的框架,然后对几个关键步骤作详细的解释。 输入数据:训练集,配置信息( 决策树大小) ; 输出数据:用线性方式表示的二分决策树。 1 ) c r e a t en o d e ( r o o o ; 2 ) p r e p a r e f o rd a t ao f a t t r i b u t el i s ta n dc l a s sl i s t : 3 ) e n t e rq u e u e ( r o o t ) ; 】7 盗墨塑坌耋竺鲨塑翌壅皇整垄一一 4 1 w h i l e ( n o te m p t y ( q u e u e ) ) d o 5 ) e v a l u a t es p l i t s ( ) ; 6 1 f o r a l l t h e l e a f n o d e s i n t h eq u e u ed o 7 1 u p d a t el a b e l s ( ) ; 8 、c l e a nt h en e wi n t e r n a ln o d ea n dt h ep u r el e a f n o d eo u to f t h eq u e u e ; 9 ) l e t t h en e wl e a f n o d ee n t e rt h eq u e u e ; 1 0 ) m d lp r u n i n g ( r o o t ) ; 算法的控制结构是一个队列。这个队列存放当前的所有叶子节点。这是为了控 制广度优先搜索的结束。当队列空时,说明所有的叶子都已经被处理过。这时建树 算法结束。第1 0 步是利用m d l 算法进行裁剪。 2 3 2 2 第2 ) 步数据准备 系统输入是训练集( t r a i n i n gd a t a ) ,每个属性对应训练集的一列。训练集进入以 后,分成一个一个的属性表( a t t r i b u t e l i s t ) f ( v i ,i ) li = o ) , i 是属性的记录索引号。将所有类标识放入类表( c l a s sl i s t ) ,类表中的l e a f 字段 指向该记录对应的决策树的叶子,初始状态下,所有记录指向树根。对属性表进行 内部排序,交换属性值v ,同时交换i ,生成有序的属性表序列。不久我们可以看到, 这是s l i q 算法中对属性进行的唯一一次排序,也是s l i q 算法的重要优点之一。排 序完成后,属性表中的i 是属性值指向类表的指针。完成属性表的排序后,数据初始 化工作就完成了。例子见图2 3 a 露 s a l a r yc i f l s 8 3 06 5g 2 31 5b 4 07 5g 5 54 0b 5 51 0 0g 4 56 0g c l a s s l i s td a s s l l s t s a l a r y 1 52 4 04 6 06 6 51 7 53 1 0 05 f c l a s sk e f f lgn i lbn i | g n 1 l bn 1 lgn i g n 1 图2 - 3 预排序的例子这里,初始时根节点为n 1 1 8 决策树分类算法的研究与改进 2 3 2 3 第5 ) 步计算最佳分裂 当完成数据预处理之后算法进入往复的求最佳分裂指标的阶段a 这一阶段,经 过一次对所有属性表的遍历,可以找出所有叶子节点的最佳分裂方案。算法如f 。在 这个阶段有一个重要的结构:类直方图( c l a s sh i s t o g r a m ) 。它位于决策树的每个顶 点内,存放每个节点当前的类信息左、右子树的每个类各拥有多少节点。 e v a l u a t e s p l i t s ( ) f o re a c ha t t r i b u t ead o t r a v e r s ea t t r i b u t el i s to f a f o re a c hv a l h evi nt h ea t t r i b u t el i s td o f i n dt h ec o r r e c te n t r yi nt h ec l a s sl i s t , t h e nr e a d o u t t h ec o r r e c tc l a s s l a b e la n d l e a f n o d e ( s a y l ) u p d a t et h ec l a s sh i s t o g r a m i nt h el e a f i i f ai san u m e r i ca t t r i b u t et h e n c o m p u t es p l i t t i n gi n d e x

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论