5.4基本决策树方法的改进

5.4基本决策树方法的改进基本决策树方法的改进改进方法连续属性的处理测试属性的改进属性的选择遗失数据的处理基本决策树方法的改进1、连续属性的处理上一章节的算法

要求所有的属性都必须是符号量或是无序的离散值。因此该算法首先需要改进以便容许可取连续值的属性。

连续属性离散化技术可派上用场。

最简单的策略是采用二分法（bi-partition）对连续属性进行处理，这正是C4.5决策树算法中采用的机制[Quinlan,1993]。基本决策树方法的改进

对连续值属性的处理

假设ci有连续的属性值，先将其值排序为A1，A2，……Am

对每个值Aj（j=1,….m），将所有记录划分成两部分

(<=Aj,.和>Aj)

针对每个划分分别计算信息增益

选择取最大增益值的值进行划分基

本

决

策

树

方

法

的

改

进

信用卡促销数据库incomeLifeInsurance?SexAge4w----5wNMale453w---4wYFemale404w----5wNMale423w---4wYMale435w—6wYFemale382w----3wNFemale523w---4wYMale352w----3wNMale273w---4wNFemale433w---4wYFemale414w----5wYMale432w----3wYFemale295w—6wYFemale554w----5wNMale19基本决策树方法的改进对年龄属性age的处理

年龄首先排序:

1927293538404142434343455255NNYYYYYNYYNNNY

然后依次计算每两个数之间的二元分裂，并比较大小发现43是最好的分割点基本决策树方法的改进2、测试属性的改进

基本的决策树归纳方法对一个测试属性的每个取值均产生一个相应分支，且划分相应的数据样本集。这样的划分会导致产生许多小的子集。随着子集被划分得越来越小，划分过程将会由于子集规模过小所造成的统计特征不充分而停止。（如按key分类）基本决策树方法的改进

可以将一个（取离散值）属性的若干值组合在一起，这样在测试该属性时，将是对属性的一组取值进行测试。基

本

决

策

树

方

法

的

改

进3、属性的选择信息增益选择方法有一个很大的缺陷，它总是会倾向于选择属性值多的属性，如果我们在上面的数据记录中加一个姓名属性，假设14条记录中的每个人姓名不同，那么信息增益就会选择姓名作为最佳属性，因为按姓名分裂后，每个组只包含一条记录，而每个记录只属于一类（每个记录只有一个类别标签），因此纯度最高，以姓名作为测试分裂的结点下面有14个分支。但是这样的分类没有意义，它没有任何泛化能力。基

本

决

策

树

方

法

的

改

进3、属性的选择

基本决策树方法的改进

增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。基本决策树方法的改进与ID3相比，C4.5增加的功能如下：用增益比例的概念合并连续值的属性可以缺少属性值的训练样本通过使用不同的修剪技术以避免树的不平衡K次迭代交叉验证规则的产生基本决策树方法的改进还有：Gini指数，最优距离划分，条件概率，goodman_kruskal关联索引……这些度量并非是无偏的。基

本

决

策

树

方

法

的

改

进3、属性的选择

基

本

决

策

树

方

法

的

改

进基本决策树方法的改进——属性的选择

视

觉

感

知

与

认

知基本决策树方法的改进——属性的选择

RID压入硬度微钻钻速岩石岩石等级Class:岩石可钻性1<1000highno0yes2<1000highno0yes3900~4400highno1no4>4200mediumyes2yes5>4200lowyes2yes6>4200lowyes3no7900~4400lowyes1no8<1000highno0yes9<1000highyes1yes10>4200mediumyes2yes11<1000highyes0yes12900~4400mediumno2no13900~4400highyes2yes14>4200mediumyes3no表5.1

岩石可钻性数据元组基

本

决

策

树

方

法

的

改

进基本决策树方法的改进——属性的选择为了找出D中元组的分裂准则，需要计算每个属性的基尼指数。从属性微钻钻速开始，微钻钻速有3个元素，子集有8个，考虑其真子集（6个），存在6种形成数据集D的两个分区的可能方法。二元划分{low,medium}和{high}{low,high}和{medium}{medium,high}和{low}基

本

决

策

树

方

法

的

改

进基本决策树方法的改进——属性的选择

基

本

决

策

树

方

法

的

改

进基本决策树方法的改进——属性的选择

同理可算出第二种划分的基尼指数为0.443，第三种划分的基尼指数为0.407。因此微钻钻速属性的最好二元划分为第一种，即{low,medium}和{high}。

然后再考虑压入硬度，压入硬度根据其取值可分位{low,medium,high}。同理可以找出最好的分割点是{medium,high}和{low}基尼指数为0.317，同理可求得属性岩石和岩石等级。

若只考虑属性“微钻钻速”和“压入硬度”最终，属性压入硬度和分裂子集产生最小的基尼指数，不纯度降低为：0.459-0.317=0.142；二元划分{medium,high}和{low}导致D中元组的不纯度降低最大，返回做为分裂准则，用节点N做标记，由它长出两个分支。基本决策树方法的改进

4、遗失数据的处理

可以利用属性A中最常见的值来替代一个遗失或未知属性A的值。基本决策树方法的改进五、树剪枝

在决策树学习算法中，除去分类的正确性应放在第一位考虑之外，决策树的大小是另外一个重要考虑的因素。

基

本

决

策

树

方

法

的

改

进图4.4

剪枝前的树a基

本

决

策

树

方

法

的

改

进图4.5

剪枝后的树基本决策树方法的改进1.为什么要修剪?

消除决策树中的过拟合（在学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策分支过多，这时就可能因训练样本学得“太好”了，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合）(1)

数据有噪音包括属性噪音和属性值噪音(2)重复的子树基

本

决

策

树

方

法

的

改

进图4.6

剪枝前的树b基

本

决

策

树

方

法

的

改

进对异常模型进行调整，使用统计度量，剪去最不可靠的分枝，提高分类的速度和分类识别新数据的能力。目标是选择尽可能小的决策树（NP-Hard问题）。常用剪枝方法事前剪枝事后剪枝基本决策树方法的改进3.两种修剪方法

(1)事前修剪方法（Prepruning，预剪枝）

通过提前停止分支生成过程，即通过在当前结点上就判断是否需要继续划分该结点所含训练样本集来实现。Public算法中采用的就是先剪枝方法。一旦停止分支，当前节点就成为树叶。该树叶可能包含多个不同类别的训练样本。

基本决策树方法的改进

在构造树时，可以利用统计意义下的

信息增益等度量，用于评估分裂的优良性。先计算在一个节点划分对系统性能的增益，如果这个增益小于某个指定阈值，则划分将停止。然而，选取一个适当的阈值是困难的。较高的阈值可能导致过分简化的树，而较低的阈值可能导致多余树枝无法修剪。基

本

决

策

树

方

法

的

改

进

决策树的产生过程是一个递归过程，不断递归分解相应的数据集合将会导致所分析的数据对象（数据子集）变得越来越小，因而从统计角度来看没有任何意义。有关的统计方法可以帮助决定最大的无意义数据子集的规模。为较好解决这一问题，可以引入意外阈值（exceptionthreshold），若一个给定子集的样本数小于这一阈值，就停止分解这一子集，产生一个叶结点并标记为其中类别个数最多的类别。基本决策树方法的改进

由于大规模数据库中数据的变化程度和规模都较大，因此假设一个叶结点所含数据子集中的样本均属同一个类别是不太合理的，这时可以引入分类阈值（classificationthreshold）来帮助解决这一问题。即若一个结点所含数据集中属于某一类别的样本数大于这一阈值，就可以停止分解这一子集。基本决策树方法的改进(2)事后修剪方法(post-pruning，后剪枝，如Sprint算法中采用)

它由“完全生长”的树剪去多余分枝。剪枝过程中，将一些子树删除而用叶节点来代替，这个叶节点所属的类用这棵子树中大多数实例所属的类代替，并且在相应叶子上标记出所属这个类的训练实例所占的比例。

基

本

决

策

树

方

法

的

改

进

一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此，其训练时间开销比未剪枝决策树和预剪枝决策树要大得多。视

觉

感

知

与

认

知树剪枝——事后剪枝后剪枝一般依据两种剪枝标准：期望错误率最小原则，对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍，通过选择期望错误率最小的子树剪枝；最小描述长度原则，依据“最简单的解释最期望的”思想，对决策树进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”。剪枝标准期望错误率最小原则最小描述长度原则视

觉

感

知

与

认

知树剪枝——事后剪枝代价复杂性剪枝悲观错误剪枝后剪枝算法很多，如CART算法中采用的代价复杂性剪枝(CostComplexityPruning，CCP)、C4.5中采用的悲观错误剪枝(PessimisticErrorPruning，PEP)、SLIQ算法中采用的最小描述长度剪枝(MinimalDescriptionLength，MDL)。后剪枝算法最小描述长度剪枝基

本

决

策

树

方

法

的

改

进树剪枝——事后剪枝(a)代价复杂性剪枝该方法把树的复杂度看做树中树叶节点的个数和树误分类的元组所占百分比，即错误率，的函数。对于树中每个非树叶节点，算法计算出该节点被修剪后可能出现的期望错误率。同时，根据每个分枝的分类错误率，以及每个每个分枝权重（样本分布），计算不对该节点剪枝的期望错误率。如果剪去该节点导致较高的期望错误率，则保留该子树；否则剪去该子树。在产生一组经过修剪的候选决策树之后，使用一个独立的测试集（剪枝集）评估每棵树的准确率，就能得到具有最小期望错误率的判定树。基

本

决

策

树

方

法

的

改

进树剪枝——事后剪枝

基

本

决

策

树

方

法

的

改

进树剪枝——事后剪枝

基本决策树方法的改进树剪枝——事后剪枝(c)最小描述长度(MDL)剪枝根据对树编码（如对树编码、对树的异常编码）所需要的二进位位数对树进行剪枝。“最佳”剪枝树是最小化编码二进位位数的树。这一原则遵循的理念是：最简单的就是最好的。基

本

决

策

树

方

法

的

改

进六、由决策树（判定树）提取分类规则

1.规则的表示形式

决策树所表示的分类知识可用IF-THEN形式表示。

IF条件THEN结论对从根到树叶的每条路经创建一个规则。沿着给定路径上的每个属性—值对形成规则前件（“IF”部分）的一个合取项。叶节点包含类预测，形成规则后件（“THEN”部分）。基

本

决

策

树

方

法

的

改

进例4.3

由判定树产生分类规则。沿着由根节点到树叶节点的路径，图4.3的判定树可以转换成IF-THEN分类规则。由图4.3提取的规则是：age？credit_rating？student？YESNOYESNOYESnoyes30..40>40<30fairexcellent图4.3

购买电脑的分类模型基

本

决

策

树

方

法

的

改

进IFage=“<=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“<=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31．．．40”THENbuys_computer=“yes”IFage=“>=40”ANDcredit_rating=“excellent”THENbuys_computer=“no”IFage=“>40”ANDcredit_rating=“fair”THENbuys_computer=“yes”所提取的每个规则之间蕴涵着析取（逻辑OR）关系，不可能存在规则冲突，且每种可能的属性-值组合都存在一个规则。基本决策树方法的改进2.规则的准确率和覆盖率

对于给定的元组，如果规则前件中的条件都成立，则说规则前件被满足，并且规则覆盖了该元组。

规则R可用它的覆盖率和准确率来评估：

给定类标记的数据集中的一个元组X,设ncover为规则R覆盖的元组数，ncorrect为R正确分类的元组数|D|是D中的元组数

则coverage(R)=ncover/|D|accuracy(R)=ncorrect/|D|基本决策树方法的改进七、决策树归纳的可扩展性

现有决策树算法，诸如ID3算法和C4.5算法的有效性已经通过对许多小数据集的学习归纳而得到了验证。但当应用这些算法对大规模现实世界数据库进行数据挖掘时，算法的有效性和可扩展性就成为应用的关键。基

本

决

策

树

方

法

的

改

进

大多数决策树算法都局限于在计算机内存中处理整个数据集；而在数据挖掘应用领域，数据集通常都包含数以百万计的记录，因此现有决策树算法的局限性就使得这类算法的可扩展性受到较大限制。这主要是因为利用这些算法构造相应决策树时，会不断地进行内存与外存之间的数据交换，从而使数据挖掘性能变得很差。基本决策树方法的改进内存管理及时间复杂性分析

构建树过程所需要的内存大小，直接取决于学习样本集的大小。因此在执行构建过程之前，需对样本集进行容量估计。

若所需内存小于可用内存，则直接将学习样本集调入内存进行树的构建；否则，需要采用优化算法（如ＳＬＩＱ）进行优化或借助数据库管理实现“内存扩充”来解决内存不足的问题。基本决策树方法的改进

设学习样本集S中有N个样本可以估计构建树Tmax

算法的时间复杂性为O（N３log2N)设Tmax含有N个节点，可以估计修剪树的时间复杂性为

O（N３)

测试样本评估算法的时间复杂性O（N３)基本决策树方法的改进决策树算法的研究热点属性选取（如分类的准确率，新分类标准）可扩展性（如增量学习，与其他技术结合）语义信息处理基

本

决

策

树

方

法

的

改

进八.常用评估分类器性能的方法(1)

两分法(Holdout，保持法)被标记的原始数据集被分成两个独立的子集

Trainingset与Testset或

Positiveset

与Negativeset(2)随机二次抽样(randomsubsampling)多次重复保持法来改进对分类器性能的估计。基

本

决

策

树

方

法

的

改

进(3)

K次迭代交叉验证(K-FoldCrossValidation)

将数据集分成K个（大小相同）子集，一个用于测试，另外k-1个用于训练。该过程重复k次，使得每个子集都用于测试恰好一次。总误差是所有k次运行的误差之和（平均）。(4)自助法(bootstrapmethod)训练数据采用有放回抽样。可以证明，大小为N的自助样本大约包含原始数据中63.2%的数据。没有抽中的数据就成为测试集的一部分。抽样过程重复b次，产生b个自主样本。基本决策树方法的改进4.4

其它分类方法一、基于距离的分类策略相似性用距离来表征，距离越近，相似性越大，距离越远，相似性越小距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。典型：KNN基

本

决

策

树

方

法

的

改

进K-最临近（近邻）分类（KNN，K-NearestNeighbor）

KNN是20世纪50年代早期首次引进的。指导思想：“近朱者赤,近墨者黑”

基于类比学习。训练样本用n维数值属性描述。每个样本代表n维空间的一个点。这样，所有的训练样本都存放在n维模式空间中。描述给定—个未知样本，KNN分类法搜索模式空间，找出最接近未知样本的k个训练样本。这k个阶训练样本是未知样本的k个“近邻”。“临近性”用距离度量，如欧几里德距离定义，其中两个点的欧几里德距离是

（4.8）基

本

决

策

树

方

法

的

改

进算法

KNN分类算法输入：训练数据T

；近邻数目K

；待分类的元组t

。输出：输出类别c。（1）N=

；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）N=N∪{d}；（5）ELSE（6） IF

u∈Nsuchthatsim(t，u)<sim(t，d)THEN

BEGIN/*sim相似性*/（7） N=N-{u}；（8） N=N∪{d}；（9） END（10）END（11）c=classtowhichthemostu∈N。/*类别判断*/类别的判定

投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。

加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）基

本

决

策

树

方

法

的

改

进KNN的例子-训练数据判断<范可可，女，1.50>高度参与距离计算，K=5基本决策树方法的改进KNN的例子-挖掘过程第11个记录=<刘冰冰，女，1.68>，需要替换掉<马大华，女，1.70>，得到N={<李莉，女，

1.50>，<张烨，女，1.50>，<刘冰冰，女，1.68>，<戴维，男，1.60>，<刘敏杰，女，1.60>}。第12～14个记录，没变化。第15个记录=<徐甜甜，女，1.65>，需要替换掉<刘冰冰，女，1.68>，得到

N={<李莉，女，1.50>，<张烨，女，1.50>，<徐甜甜，女，1.65>，<戴维，男，1.60>，<刘敏杰，女，1.60>}。最后的输出={<李莉，女，1.50>，<张烨，女，1.50>，<徐甜甜，女，1.65>，<戴维，男，1.60>，<刘敏杰，女，1.60>}。对照表4-2，在这五项中，四个属于矮个，一个属于中等。最终-最临近算法认为范可可为矮个。讨论：合理性？基

本

决

策

树

方

法

的

改

进KNN优缺点优点简单，易于理解，易于实现，无需估计参数，无需训练；适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）；特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好。缺点懒惰学习法（平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）），对测试样本分类时的计算量大，内存开销大，评分慢；可解释性较差，无法给出决策树那样的规则。基本决策树方法的改进二、

基于统计的分类策略朴素贝叶斯分类器

(NaïveBayesClassifier)统计学分类方法，基于贝叶斯定理。可以预测类隶属关系的概率，如一个给定的元组属于一个特定类的概率。假定一个属性值对给定类的影响独立于其他属性的值（类条件独立性，属性条件独立性假设），预测未知样本的类别为后验概率最大的那个类别。基

本

决

策

树

方

法

的

改

进基

本

决

策

树

方

法

的

改

进贝叶斯定理提供了后验概率的计算方法：

其中：

P（X）：X的先验概率(priorprobability)；

P（H）：H的先验概率；

P（X|H）：条件H下X的后验概率(posteriorprobability)；

P（H|X）：条件X下H的后验概率。设X是数据元组，通常用n个属性集的测量值描述。令H为某种假设，如数据元组X属于某个特定类C。基

本

决

策

树

方

法

的

改

进

贝叶斯定理来估计后验概率P（H|X)困难在于P(X|H)是所有属性上的联合概率，难以从有限的训练样本直接估计而得。为避开这个障碍，朴素贝叶斯分类器采用了属性条件独立性假设，即每个属性独立地对分类结果发生影响。则公式可重写：

其中d为属性数目，xi为X在第i个属性上的取值。基本决策树方法的改进朴素贝叶斯分类法工作过程（预测类标号）：（1）设样本有n个属性(A1,A2,...,An)，每个样本可看作是n维空间的一个点X=(x1,x2,...,xn)。（2）假定有m个不同的类别，C1,C2,....Cm。给定X是一个未知类别的样本。预测X的类别为后验概率最大的那个类别，即算法将未知类别的样本X归到类Ci，当且仅当

P(Ci|X)>P(Cj|X)，对于所有的j成立

(1≤j≤m，j≠i）即P(Ci|X)最大。基

本

决

策

树

方

法

的

改

进(3)根据贝叶斯定理得知

P(Ci|X)=P(X|Ci)P(Ci)/P(X)。

P(X)对于所有类为常数，因此只需

P(X|Ci)P(Ci)取最大即可。类的先验概率P(Ci)由P(Ci)=si/s估算。

其中Si为训练样本中属于类Ci的样本数，s为全部训练样本的样本数。

P(X|Ci)＝P(x1|Ci)P(x2|Ci)...P(xn|Ci)(4)对未知样本X分类，对每个类Ci，计算P(X|Ci)P(Ci)。样本X被指派到类Ci，当且仅当P(X|Ci)P(Ci)>P(X|Cj)P(Cj),(1≤j≤m，j≠i)即X被指派到其P(X|Ci)P(Ci)最大的类Ci。

视

觉

感

知

与

认

知朴素贝叶斯分类的流程可以由下图表示（