（概率论与数理统计专业论文）数据挖掘中的高速可伸缩分类算法.pdf

摘要 数据挖掘又称数据库中的知识发现，是数据库研究最活跃的领域之一。通过 数据挖掘可以从大量数据中提取出可信、新颖、有效并易于理解的知识、规律和 高层信息。发现的知识可用于决策、过程控制、信息管理、查询处理等方面，因 此数据挖掘的技术和应用有了飞快的发展。 分类是数据挖掘中的一个重要部分。分类的目的是学会一个分类函数或分类 模型，也常常称作分类器。该模型能把数据库中的数据项映射到给定类别中的某 一个。分类可用于预测，分类的输出是离散的类别值。 分类的方法很多，其中决策树是一种最常用的算法。与其他分类算法相比， 他能够较快的建立简单、易于理解的模型，容易转换成规则，而且具有与其他分 类模型同样的甚至更好的分类准确性。 高速可伸缩分类算法叮s c a ) 是我设计的一种数据挖掘算法。他通过预排序技 术，着重解决当训练集数据量巨大，无法全部放入内存时，如何高速准确地生成 决策树，能同时处理离散字段和连续字段。 关键词：数据挖掘、分类、决策树 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 f t h em 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 la 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 nb ea p p l i e di n d 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 ds oo n s ot h e t e c h n i q u ea n da p p l i c a t i o no f d a t am i n i n gd 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 so n eo ft h em o s ti m p o r t a n tb r a n c h e so fd a t am i n i n gr e s e a r c h w o r k s t a r g e to fc l a s s i f i c a t i o ni st of i n do u tac l a s s i f i c a t i o nf u n c t i o no rm o d e l ( a l s o c a l l e dc l a s s i f i e r ) t h em o d e lc a nm a pas i n g l er e c o r di nd a t a b a s et oap r e a s s u m e d c l a s s c l a s s i f i c a t i o nc a nb eu s e dt of o r e c a s t t h eo u t p u to fc l a s s i f i c a t i o ni sd i s c r e t e c l a s sl a b e l s e v e r a lc l a s s i f i c a t i o nm o d e l sh a v eb e e np r o p o s e do v e rt h ey e a r s a m o n gt h o s e m o d e l s ，d e c i s i o nt r e ei sak i n do fm 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 e s i m p l ea n de a s yt ou n d e r s t a n d , e a s i l yc 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 d r 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 rm 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 s o 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 yw h e nc o m p a r e dw i t hs o m eo fo t h e r c l a s s i t i c a t i o nm e t h o d s f a s ta n ds c a l a b l ec l a s s i f i c a t i o na l g o r i t h m ( f s c a ) i saa l g o r i t h mf o rd a t am i n i n g d e s i g n e db ym e i tu s e san o v e lp r e s o r t i n gt e c h n i q u et ob u i l dad e c i s i o nt r e ef a s tm a d a c c u r a t e l yw h e nt h er e c o r d so ft r a i n i n gs e ta r et o ol a r g et of i ti nm e m o r ya n dr e s i d e n t i nt h ed i s k i te n a b l e sb o t hd i s c r e t ea n dn u m e r i ca t t r i b u t e s k e y w o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n ，d e c i s i o nt r e e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 北京工业大学或其它教育机构的学位或证书而使用过的材料与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意 签名：梃垦坠日期：竺! 苎：墅 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文 ( 保密的论文在解密后应遵守此规定) 签名导师签名 描日期 第1 章绪论 第1 章绪论 1 1 数据挖掘概述 1 1 1数据挖掘的历史 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更 高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数 据的录入、查询、统计等功能但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了 “数据爆炸但知识贫乏”的现象。 计算机技术的另一领域一人工智能自诞生之后取得了重大进展。经历了博 弈时期、自然语言理解、知识工程等阶段，目前研究热点是机器学习。机器学习 是用计算机模拟人类学习的一门科学，比较成熟的算法有神经网络、遗传算法等。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数 据背后的知识，这两者的结合促成了数据库中的知识发现( k d d ：k n o w l e d g e d i s c o v e r y i nd a t a b a s e s ) 的产生。实际上，数据库中的知识发现是- - f - 交叉性学科， 涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高 性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息管理、 过程控制、科学研究、决策支持等许多方面。 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论 会上首次出现k d d 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 号题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、 海量数据分析算法、知谚 表习i 、知识运用等问题。随着参与人员的不断增多 k d d 旧i h t 会议z 之塍成为年会 1 9 9 8 印柏：爻川鲥约举i r 的第川川为 b ：发现i 数： l l ： 北京工业大学理学硕士学位论文 挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了他们的 数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。 数据挖掘是k d d 最核心的部分，是采用机器学习、统计等方法进行知识学 习的阶段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多数的 研究都集中在数据挖掘算法和应用上。人们往往不严格区分数据挖掘和数据库中 的知识发现，把两者混淆使用。一般在科研领域中称为k d d ，而在工程领域则 称为数据挖掘， 1 1 2 数据挖掘的几种模式 数据挖掘的模式有多种，按功能可分有两大类：预测型( p r e d i c t i v e ) 模式和描 述型( d e s c r i p t i v e ) 模式。在实际应用中，往往根据模式的实际作用分为以下6 种： ( 1 ) 分类模式分类模式是一个分类器，能够把数据集中的数据项映射到某个 给定的类上。分类模式往往表现为一棵分类树，根据数据的值从树根开始搜索， 沿着数据满足的分支往下走，走到树叶就能确定类别。 2 ) 回归模式回归模式的函数定义与分类模式相似，它们的差别在于分类模 式的预测值是离散的，回归模式的预测值是连续的。 ( 3 ) 时间序列模式时间序列模式根据数据随时间变化的趋势预测将来的值。 这里要考虑到时间的特殊性质，像一些周期性的时间定义如星期、月、季节、年 等，不同的日子如节假日可能造成的影响，日期本身的计算方法，还有一些需要 特殊考虑的地方如时间前后的相关性等。 ( 4 ) 聚类模式聚类模式把数据划分到不同的组中，组之间的差别尽可能大， 组内的差别尽可能小。与分类模式不同，进行聚类时并f i 知道将要划分成几个组 垌| t 卜么样的绑，也小知道撤射，知邪儿个数 i i 61 采证义纠【， 第1 章绪论 ( 5 ) 关联模式关联模式是数据项之间的关联规则。 ( 6 ) 序列模式与关联模式相仿，它把数据之间的关联性与时间联系起来。为 了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用 最普遍的模式。分类模式、回归模式、时问序列模式也被认为是受监督知识，因 为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的 产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为 样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是 非监督知识，因为在模式建立前结果是未知的，模式的产生不受任何监督。 1 2 分类算法 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 ) 与之对应。该类标签是系统的输入，通常是以往的一 些经验数据。个具体样本的形式可为样本向量：( vj ，v 2 ，v n ；c ) 。在这里v ，表 承7 产段值，c 衷示类别。 北京工业大学理学硕士学位论文 第二步，使用建好的模型进行分类。首先评估模型，预测准确率，如果认为 模型的准确率可以接收，就可以用它对类标号未知的数据元组或对象进行分类。 分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为 每一个类找到一种准确的描述或者模型。由此生成的类描述用来对未来的测试数 据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测 这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每 一个类有更好的理解。也就是说：我们获得了对这个类的知识。 分类和预测可以根据以下标准进行比较和评估： ( 1 ) 预测准确度这是用得最多的一种尺度，特别是对于预测型分类任务。 ( 2 ) 计算复杂度计算复杂度依赖于具体的实现细节和硬件环境，由于操作对 象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。 ( 3 ) 模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢迎， 例如，采用规则表示的分类器构造法就更有用。 ( 4 ) 鲁棒性这涉及给定噪声数据或具有空缺值数据，模型正确预测的能力。 ( 5 ) 可伸缩性这涉及当给定大量数据时，算法有效构造模型的能力。一个算 法是可伸缩的，如果给定内存和磁盘空间等可利用的系统资源，其运行时间应当 随数据库大小线形增加。 分类的典型应用：信用卡系统中的信用分级、市场调查、疗效诊断等。 1 2 2 举例说明分类的过程 信用卡系统的信用分级是分类的典型应用。如图1 - 1 和图1 - 2 所示，描述了 信用分级系统的运行机制。我们可以看到：这是一个分为两步走的过程，第一步 是利用训练数据集进行学习的过程，第二步是进行模型评估，降低模型噪音并投 入实际运行的过程。 4 第1 章绪论 注：训练集( 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 n r u l e s ) 。样本向量：( n a m e ，a g e ，i n c o m e ；c r e d i t m f i n g ) ，类标签c r e d i tr a t i n g 图1 - 1 学习过程 注：测试数据( t e s td a t a ) 用来建立准确的分类规则，如果准确性能被接受，! i ! | j 分类规则将 瑚来对新数据进行分类。 北京工业大学理学硕士学位论文 i 3本文结构 本文首先在绪论中简单介绍了数据挖掘和分类算法。在第2 章将详细介绍决 策树理论，对几种具有代表性的决策树算法进行了较详细的阐述，并对各种算法 的性能作了分析比较，指出了他们的优缺点。在第3 章，我在受到并行算法思想 的影响下，在原有算法的基础上进行了改进，提出了高速可伸缩分类算法 ( f s c a ) ，详细介绍了该算法的思想和整个流程，并对其性能作了比较和分析。 第4 章中，我具体描述了如何实现算法。在结论中，对全文进行了总结并指出进 一步研究方向。 第2 章决策树理论基础 2 1 决策树介绍 第2 章决策树理论基础 2 1 1 决策树概述 在各种分类方法中，决策树是其中最常用和最重要的一种，它是以实例为基 础的归纳学习算法。它从一组无次序、无规则的事例中推理出决策树表示形式的 分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较 并根据不同的属性值判断从该节点向下的分支，在树的叶节点得到结论。所以从 根到叶节点的一条路径对应一条分类规则，整个决策树对应一组分类规则。 决策树的内部节点是属性或属性的集合，叶节点是所要划分的类。经过一批 训练实例集的训练产生一颗决策树，决策树可以根据属性的取值对一个未知实例 集进行分类。使用决策树对实例集进行分类时，由树根开始对该对象的属性测试 其取值，并顺着分支往下走，直到走到某个叶节点。此时，叶节点的类标号即为 该对象的类。 图2 1 给出了一个商业上使用决策树的例子，它表示了一个关心电子厂品 的用户是否会购买p c 的知识，用它可以预测某个人的购买意向。这棵决策树对 “买计算机”的销售记录进行分类，指出一个电子产品消费者是否会购买一台计算 机。每个内部节点( 方形框) 代表对某个属性的一次检测。每片叶子( 椭圆框) 代表一个类。输入新的被决策的纪录，可以预测该记录隶属于哪个类。 北京工业大学理学硕士学位论文 2 1 2 决策树的优点 采用决策树算法的主要优点有 图2 1 决策树 ( 1 ) 在学习的过程中不需要使用者了解很多的背景知识。 ( 2 ) 能够直接体现数据的特点，容易被人们理解。 ( 3 ) 运算速度快。 ( 4 ) 容易转化为分类规则。 ( 5 ) 分类准确性高。 2 2 几种常见的决策树算法 2 2 11 1 ) 3 算法 早期著名的决策树算法是1 9 8 6 年由q u i l a n 提出的i d 3 算法。i d 3 算法的具 体描述为i d 3 f o r m t r e e ( t , ta t t r i b u t e l i s t ) ，其中t 代表当前样本集，ta t t r i b u t e l i s t 代表当前的候选属性集，候选属性集中的所有属性都为离散值，连续值属性必须 事先经过预处理转化为离散型。 第2 章决策树理论基础 i d 3 f o r m t r e e ( t , t _ a t t r i b u t e l i s t ) ( 1 ) 创建根节点n ； ( 2 ) 皿t 都属于同一类c ，则返回n 为时节点，标记为类c ； ( 3 ) i ft _ a t t r i b u t e l i s t 为空 则返回n 为叶节点，标记n 为t 中出现最多的类； ( 4 ) f o re a c ht _ a t t r i b u t e l i s t 中的属性 计算信息增益g a i m ( 5 ) n 的测试属性t e s t a t t r i b u t e = t a t t r i b u t e l i s t 中具有最高g a i n 值的属性； ( 6 ) f o re a c ht e s t _ a t t r i b u t e 的取值 由节点n 长出一个新叶子节点； 环新叶节点对应的样本子集t 为空 则不再分裂此叶节点，将其标记为t 中出现最多的类： e l s e 在该叶节点上执行i d 3 f o r m t r e e ( t ，t _ a t t r i b u t e l i s t ) ，继续分裂； ) i d 3 算法将样本集分为训练样本集和测试样本集，决策树的构建是在对训练 样本集的学习上产生的，决策树生成之后，再运用测试样本集对树进行后剪枝， 将分类预测准确率不符合条件的叶节点剪去。 i d 3 算法非常简单易用，但是它存在明显的不足，不能在算法中直接处理连 续型属性，不能处理属性值空缺的样本，生成的决策树分支较多、规模较大。为 改进这些不足，产生了c 4 5 算法。 2 2 2c 4 5 算法 c 4 5 算法是q u i l a n 在1 9 9 3 年提出的，它既是i d 3 算法的后继，也成为以后 诸多决策树的基础。c 45 算法分类准确率高，而且速度根快。 北京工业大学理学硕士学位论文 c 4 5 算法在i d 3 算法的基础上加进了对连续型属性，属性值空缺情况的处理， 对树剪枝也有了较成熟的算法。c 4 5 算法的具体描述为c 4 5 f o r m t r e e ( t ) ，其中t 代表当前样本集，t _ a t t r i b u t e l i s t 代表当前的候选属性集。 c 4 5 f o 珊缸e e ( t ta t t r i b u t e l i s t ) ( 1 ) 创建根节点n ； ( 2 ) i f t 都属于同一类c ，则返回n 为叶节点，标记为类c ； ( 3 ) mta t t r i b u t e l i s t 为空o rt 中所剩的样本树少于某给定值 则返回n 为叶节点，标记n 为t 中出现最多的类； ( 4 ) f o re a c hta t t r i b u t e l i s t 中的属性 计算信息增益率i n f o m a t i o ng a i nr a t i o ； ( 5 ) n 的测试属性t e s ta t t r i b u t e = t a t w i b u t e l i s t 中具有最高信息增益率属性； ( 6 ) 测试属性为连续型 则找到该属性的分割阈值； ( 7 ) f o re a c h 由节点n 长出的新叶节点 i f 该叶节点对应的样本子集t 为空 则分裂该叶节点生成一个新叶节点，标记t 中出现最多的类； e l s e 在该叶节点上执行c 4 5 f o r m t r e e ( t ，t _ a t t r i b u t e l i s t ) ，继续分裂； ( 8 ) 计算每个节点的分类错误，进行树剪枝。 与1 1 ) 3 不同，c 4 5 采用基于信息增益率的方法选择测试属性。信息增益率等 于信息增益对分割信息量( s p l i ti n f o m a t i o n ) 的比值。c 4 5 算法在效率上有了很大 提高，不仅可以直接处理连续型属性，还可以允许训练样本集中出现属性空缺的 样本。但是，c 4 5 算法在选择测试属性，分割样本集上所采用的技术仍然没有 h 范离信息熵原理，园此生成的决策树仍然是多叉树。如果想，卜成结构更为简洁的 叉树必须采j ； j 新的原理柬分割样本岔! 。 0 第2 章决策树理论基础 2 2 3 c a r t 算法 c a r t 算法采用一种二分递归分割的技术，总是将当前样本集分割为两个子样 本集，使得生成的决策树的每个非叶节点都有两个分枝，因此c a r t 算法生成的 决策树是结构简单的二叉树。 c a r t 算法的具体描述为c a r t f o r m t r e e ( t ) ，其中t 代表当前样本集 ta t t r i b u t e l i s t 代表当前的候选属性集。 c a r t f o r m t r e e ( t ) ( 1 ) 创建根节点n ； ( 2 ) 为n 分配类别： ( 3 ) i ft 都属于同一类别o rt 中只剩一个样本 则返回n 为叶节点，为其分配类别； ( 4 ) f o re a c hta t t r i b u t e l i s t 中的属性 执行该属性上的一个划分，计算此次划分的g i n i 系数； ( 5 ) n 的测试属t e s ta t u i b u t e = ta t t r i b u t e l i s t 中具有最小g i n i 系数的属性； ( 6 ) 划分t 得t l ，t 2 两个子集； ( 7 ) 调用c a r t f o r m t r e e ( t 1 ) ； ( 8 ) 调用c a r t f o r m t r e e ( t 2 ) ； 与基于信息熵的理论不同，c a r t 算法对每次样本集的划分计算g i n l 系数， g i n i 系数越小越合理。对候选属性集中的每一个属性，c a r t 算法计算该属性 上每种可能划分的g i n i 系数，找到g i n i 系数最小的划分作为该属性上的最佳 划分，然后比较所有候选属性上最佳划分的g i n i 系数，拥有最小划分g i n i 系 数的属性成为最终测试属性。 与c 4 5 算法样c a r t 算法仍然使用后剪技。存树生成过程中，考虑剑多 j 。；b 北会仃彭”j f l o f ，；鬯、做发现c a r t 算刊i 延 j 剑0 ：能 f k 分 l 乃1 1 ， 北京工业大学理学硕士学位论文 从而得到一颗最大的决策树。然后c a r t 算法对这颗超大的决策树进行剪枝。这 种先建树后剪枝的算法将生成好的分枝再减去是一种效率较低的重复劳动。 2 2 4p u b l i c 算法 前面介绍的决策树算法都分两步走，即先建树，后剪枝。然而考虑到先建树 后剪枝的算法将生成好的分枝再减去是一种效率较低的重复劳动，于是提出将剪 枝融入到建树的过程中，郎预剪枝。 p u b l i c 算法是r 旬e e v r a s t o g i 等人在2 0 0 0 年提出的运用预剪枝技术的算法。 与同类后剪枝算法相比，p u b l i c 算法的最大优点是它生成的决策树与同一样本 集使用后剪枝算法的决策树基本相同，而效率确比后者有大幅度提高。 p u b l i c 算法在选择测试属性上采用计算g i n i 系数的技术，在剪枝时使用 基于最小编码代价的m d l 算法。p u b l i c 算法并非在建树的最初就同时使用剪 枝算法，而是在树生成了一部分之后，对尚未完全生成的决策树进行剪技，对最 终将成为叶子的节点不再分割，从而减少工作量，提高效率。 p u b l i c 算法的建树b u i l d t r e e ( t ) 和m d l 剪枝算法c o m p u t e c o s t & p r u n e ( n ) 分别描述如下。 b u i l d t r e e ( t ) ( 1 ) 预处理训练样本集t ，初始化根节点： ( 2 ) 初始化队列q ，将根节点进队； ( 3 ) w h i l e q 不为空d o 取队列0 的头节点n ： i f n 中的样本一i 属j 。同类 f o re a c h 心陀1 1a l t r i b u t e l i s t 2 第2 章决策树理论基础 找出最佳划分将t 划分为t 1 ，t 2 将t 1 ，t 2 进队； c o m p u t e c o s t & p r u n e ( n ) ( 1 ) i fn 是尚可分割的叶节点返回n 的编码代价下限； ( 2 ) i fn 是被剪过枝的节点o r n 是不可再分割的叶节点返回c ( s ) + 1 ； ( 3 ) n 1 ，n 2 是节点n 的两个子集； 4 ) m i n c o s t l = c o m p u t e c o s t & p r u n e ( n 1 ) ； ( 5 ) m i n c o s t 2 = c o m p u t e c o s t & p r u n n 2 ) ； ( 6 ) m i n c o s t n - - m i n c ( s ) + l ，cs p l j t ( n ) + m i n c o s t i + m i n c o s t 2 ； ( 7 ) i fm i n c o s t n = c ( s ) + l 将n 1 ，n 2 剪去，在队列q 中删除n 1 ，n 2 及它们的所有后继节点 将n 标记为被剪过枝的节点； ) ( 8 ) 返回m i n c o s t n ； 与分类错误判断决策树的某一分枝是否要剪去不同，p u b l i c 算法采用基于 m d l 的剪枝标准。根据m d l 原理，具有最小编码代价的决策树为最优决策树。 一颗决策树的编码代价包括三部分：树结构本身的编码代价，每个非叶节点上的 测试属性及其测试值的编码代价，每个叶节点所表示的样本集的编码代价。 p u b l i c 算法继承了c a r t 算法建树的基本原理，却使用了更加高效的剪枝策略。 北京工业大学理学硕士学位论文 2 3 本章小结 基于决策树分类算法自出现至今，种类已有很多种。各种算法在执行速度、 可扩展性和分类预测的准确性等方面个有千秋。决策树分类算法的发展可分为这 样几个阶段：首先，最早出现的i d 3 算法采用信息熵原理选择测试属性分割样本 集，只能处理具有离散型属性和属性值齐全的样本，生成形如多叉树的决策树。 后来出现的c 4 5 算法经过改进，能够直接处理连续型属性，也能够处理属 性值空缺的训练样本。i d 3 系列算法和c 4 5 系列算法虽然在对训练样本集的学 习中尽可能多的挖掘信息，但其生成的决策树分枝较多，规模较大。 为了简化决策树的规模，提高生成决策树的效率，又出现了根据g i n i 系数 来选择测试属性的决策树算法，使得生成的决策树可以是结构简单、易于理解的 二叉树。 根据树剪枝的出现时间，决策树算法使用的剪枝策略可以分为预剪枝和后剪 枝。大多数决策树算法都采用后剪枝策略，但是，后剪枝策略明显存在将已经生 成的分枝再剪去的重复劳动，降低了决策树的生成效率，因此出现了以p u b l i c 算法为代表的预剪枝决策树算法。 近年来，为了增加决策树算法的可扩展性和并行性，又出现了一些并行的决 策树算法。上文介绍的是几种极具代表性的决策树算法，表2 1 对它们进行了 些比较。 第2 章决策树理论基础 表2 - 1 几种决策树算法的比较 决策树选择测试属 连续属 剪枝算法 运行剪是否必须可伸并 的结构性的技术性的处枝的时独立测试缩性行 理间样本集性 i d 3 多叉树信息增益离散化分类错误后剪枝是差差 c 4 5 多叉树信息增益率预排序 分类错误 后剪枝 否差差 c a r t二叉树 g i n i 系数 预排序分类错误 后剪枝 否差差 p u b l c 二叉树g i n i 系数预排序m d l预剪枝 否差 差 并行法二叉树g i n i 系数预排序m d l后剪枝否好好 北京工业大学理学硕士学位论文 第3 章高速可伸缩分类算法 3 1 课题背景 分类算法已有很多，但大多算法都存在一个致命的问题，即不能进行扩展， 可伸缩性差。在计算机已得到大量普及的今天，积累的数据在急剧增长，原有的 很多算法无法处理这些数据，主要表现在内存及c p u 时间上的有限性。 大多分类算法缺乏伸缩性，主要是由于进行深度优先搜索，所以算法受内存 大小限制，而现代的数据仓库存储几个g b y t e s 的海量数据，用以前的方法是显 然不行的。 我在受到并行算法思想的影响下，在p u b l i c 算法的基础上进行了改进，提 出了高速可伸缩分类算法( f s c a ) 。f s c a 算法通过预排序技术，着重解决当训练 集数据量巨大，无法全部放入内存时，如何高速准确地生成决策树，能同时处理 离散字段和连续字段。 3 2 高速可伸缩分类算法技术简介 3 2 1 算法使用的技术 高速可伸缩算法( f s c a ) 是一个能够处理连续及离散属性的决策树算法，在 树的构建阶段使用了预排序技术以减少计算连续属性的代价，这种预排序过程与 广度优先搜索策略集成在一起，使f s c a 能够分类驻留在磁盘上的数据集。 f s c a 算法在选择测试属性上采用计算g i n i 系数的技术，在剪枝时也使用基 于最小编码代价的m d l 算法。浚算法代价不高而且生成紧凑与精确的树。这些 技术的组合使f s c a 算法能够处理大规模的数据集，并能对具有大量的类、属性 与样术的数据集分类。 第3 章高速可伸缩分类算法 高速可伸缩算法( f s c a ) 有以下特点： ( 1 ) 运算速度快，对属性值只作一次排序。 ( 2 ) 利用整个训练集的所有数据，不做取样处理，不丧失精确度。 ( 3 ) 轻松处理磁盘常驻的大型训练集，适合处理数据仓库的海量历史数据。 ( 4 ) 更快的，更小的目标树。 ( 5 ) 低代价的i v i d l 剪枝算法。 3 2 2g i n i 系数 在些决策树中，使用信息增益作为评价节点分裂质量的参数。f s c a 算法 中，我们使用g i n i 系数代替信息增益，g i n i 系数比信息增益性能更好，且计算 方便。对数据集包含n 个类的数据集t ，g i n i 系数g i n i ( t ) 定义为： g i n i ( t ) = 1 一p ，p 其中p ；是t 中第j 类数据的频率，g i n i 系数越小，信息增益越大。 如果集合t 分成两部分t 1 和t 2 ，那么这个分割的g i n i 系数砌l j p l i t ( 丁) 为 g 嘛。( n = 等枷( 五) + 等加强) 提供最小的g 抽f 。( ，) 就被选择作为分割的标准，对于每个属性都要遍历所有可 以的分割方法。 3 2 3 属性的分裂方法 与p u b l i c 算法相同，f s c a 采用二叉树结构，对每个节点都需要先计算最 佳分裂方案，然后执行分裂。 对二数值型连续字段分裂属性a = v 。先对数值型字段排序，假设排序后的结 果为、，、，、i 列为分裂j l 会发中住眄个1 7 t i 之f l i j ，嘶以仃n1 种，tj 能陀。 北京工业大学理学硕士学位论文 通常取中点( v ，+ v 。) 2 作为分裂点。从小到大依次取不同的分裂点，取g i n i 系数最小的一个就是分裂点。因为每个节点都需要排序，所以这项操作的代价很 大，降低排序成本成为一个重要的问题。 对于离散型字段，设s ( a ) 为属性a 的所有可能的值，分裂测试将要取遍s 的 所有子集s 。寻找当分裂成s 和s s 两块时的g i n i 系数，取到g i n i 系数 最小的时候，就是最佳分裂方法。显然，这是一个对集合s 的所有子集进行遍历 的过程，共需要计算2 ”。次，代价也很大，可以用以下方法寻找最佳的子集。 离散型字段的最佳子集生成方法： ( 1 ) 属性可能的值的个数小于m a x s e t s i z e 时，遍历所有子集，寻找最佳分割。 ( 2 ) 属性可能的值的个数大于m a x s e t s i z e 时，使用贪心算法寻找最佳分割的 近似解。 ( 3 ) m a x s e t s i z e 一般取1 0 ，2 的1 0 次方被认为可以接受。 3 2 4m d l 剪枝算法 与p u b l i c 算法一样，我在f s c a 算法中仍然用基于最小编码代价的m d l 剪枝算法。m d l 原理指出，对数据编码的最好模型是使依据模型描述数据代价 的总和最小及描述模型的代价最小，m d l 算法描述为： c o m p u t e c o s t & p r u n e ( n ) ( 1 ) n 是尚可分割的叶节点返回n 的编码代价下限； ( 2 ) 口n 是被剪过枝的节点o rn 是不可再分割的叶节点返回c ( s ) + l ( 3 ) n 1 ，n 2 是节点n 的两个子集； ( 4 ) m i n c o s t i = c o m p u t e c o s t & p r u n e ( n 1 ) ： ( 5 ) m i n c o s t 2 = c o m p u t e c o s t & p r u n e ( n 2 ) ； ( 6 ) m i n c o s t n = m i n c ( s ) + l ，cs p l i l ( n ) + m i n c o s t i + m i n c o s t 2 ； 第3 章高速可伸缩分类算法 ( 7 ，i fm i n c o s t n = c ( s ) + 1 将n 1 ，n 2 剪去，在队列q 中删除n 1 ，n 2 及它们的所有后继节点 将n 标记为被剪过枝的节点； ) ( 8 ) 返回m i n c o s t n ； 根据m d l 原理，具有最小编码代价的决策树为最优决策树。一颗决策树的 编码代价包括三部分：树结构本身的编码代价，每个非叶节点上的测试属性及其 测试值的编码代价，每个叶节点所表示的样本集的编码代价。 由于生成的是二叉树，对树的任一节点的结构的编码代价为1 ( 位) ，即用一 个二进制位表示节点为非叶节点和叶节点两种情况。 若n 为叶节点，则对n 的最小编码代价为c ( s ) + l ，其中i 是对节点结构的 编码代价，设n i 是类别为i 的样本数，n 所代表的样本集s 的最小编码代价记为 c ( s ) ，由下式给出， c ( s ) = ”r o g n 。 若n 是非叶节点，则其最小编码代价为编码节点结构、编码分裂n 的测试 条件c 。( ) ，和编码n 的两棵子数的最小代价之和。其中测试条件的编码代价 c 0 。( ) 的计算由测试属性的类型而定。 m d l 剪枝算法就是计算每个节点的最小编码代价，如果此代价大于将此节 点作为叶节点所需的编码代价，则将此节点作为叶节点，不再对其分裂，否则继 续对其分裂。保证生成的最终决策树编码代价最小。 北京工业大学理学硕士学位论文 3 3 高速可伸缩分类算法流程 3 3 1 整个算法总流程 把整个算法看成一个整体，那么系统在逻辑上 输入数据：训练集； 输出数据：用线性方式表示的二叉决策树。 f s c a 算法总流程 ( 1 ) c r e a t en o d e ( r o o t ) ； ( 2 ) p r e p a r ef 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 ) ； ( 4 ) 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 so ； ( 6 ) f o ra l lt h el e a f n o d e si nt h eq u e u ed o ( 7 )u p d a t el a b e l s0 ； ( 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 ；) 0 0 ) m d lp r u n i n g ( r o o t ) ； 算法的控制结构是一个队列，这个队列存放当前的所有叶节点，这是为了控 制广度优先搜索的结束。当队列空时，说明所有的叶子都已经被处理过，这时建 树算法结束。 3 3 2 数据准备 对应算法流程( 1 ) 和( 2 ) 。系统输入训练集，训练集是样本向量( v 1 v 2 ，v n ；c ) 组成的集合，每个属性对应训练集的一列。训练集进入以后，分成一个一个的属 性表。将所有类标识放入类表，类表中的l e a f 字段指向该畦录对应的决策树的 叶f - ，初始状态f ，所有记录指囱树根， 第3 章高速可伸缩分类算法 对属性表进行内部排序，交换属性值v i ，同时交换i ，生成有序的属性表序 列。我们可以看到，这是f s c a 算法中对属性进行的难一一次排序，也是f s c a 算法的重要优点之一。排序完成后，属性表中的i 是属性值指向类表的指针。完 成属性表的预排序后，数据初始化工作就完成了。 预排序在f s c a 算法中起到了十分重要的作用。对于连续属性，在寻找决策 节点的最优分枝时，排序时间是最主要的因素。因此，在f s c a 算法中就是要减 少在决策树的每一个节点对数据的排序，在数增长阶段的开始，针对每个连续属 性，数据集的排序只进行一次。 为了完成这种预排序，使用下面的数据结构。属性表有两个字段：一个是属 性值；另一个是指向类表的索引。类表也有两个字段：一个是类标号；另一个是 决策树叶节点的指针。类表中的i 个值对应者着训练数据中的第i 个样本。 决策树中的每一个节点代表训练数据中的一个划分，该划分依赖于从节点到 根的路径，于是类表在任何时间都可以找到样本所属的划分。开始时，所有类表 的叶指针字段都指向决策树的根节点。通过对训练数据训练一次后，将所有样本 的属性值都分布到表中。每一个属性值都对应着相应的类表索引，连续属性的属 性表独立地进行预排序，如图3 - 1 所示： 3 6 5 g 2 3 1 5b 柚 7 5g 5 54 nb 5 51 0 0c 4 56 0g i i c l l l s s c h “ u缸lhl 幻2 ，ol 4 0】 4 56 5 5 5 s 5 】善13 1 棚排 2 l l s2 4 0 枷6 6 5l 7 53 l 呻5 c ， ll 晗f gn i bn i gn l bn 1 cn 1 gn l l 2 3 4 s 6 北京工业大学理学硕士学位论文 3 3 3 计算最佳分裂 对应算法总流程( 5 ) 。当完成数据预处理之后算法进入往复的求最佳分裂指 标的阶段。我受到并行算法的影响，在f s c a 算法中放弃了大多决策树算法使用 的深度优先算法，使用基于广度优先的方法来进行数的构建。其结果是当前树的 所有叶节点的分枝计算都是在遍历数据的过程中一次完成的。 这一阶段，经过一次对所有属性表的遍历，可以找出所有叶子节点的最佳分 裂方案。在这个阶段有一个重要的结构：类直方i 虱( c l a s sh i s t o g r a m ) 。它位于决策 树的每个顶点内，存放每个节点