分类挖掘之决策树

分类(fēnlèi)挖掘：决策树

2026/4/28第一页，共六十六页。决策树算法(suànfǎ)概述决策树算法最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测(yùcè)。决策树算法属于有指导的学习。根结点叶结点内部(nèibù)结点兄弟结点2叉树多叉树第二页，共六十六页。分类(fēnlèi)预测分类预测，就是通过向现有数据学习，使模型(móxíng)具备对未来新数据的分类预测能力。数据包含：输入变量输出变量分类和预测分类：分类型输出变量预测：数值型输出变量第三页，共六十六页。决策树算法(suànfǎ)概述决策树的种类：分类决策树：树叶结点所含样本的输出变量的众数就是分类结果。回归决策树：树叶结点所含样本的输出变量的平均值就是预测结果。利用决策树进行分类预测：对新数据进行分类预测时，只需按照决策树的层次，从根结点开始依次对新数据输入变量值进行判断并进入不同的决策树分支，直至叶结点为止。特点：分类预测是基于逻辑(luójí)的。IFTHEN每个叶节点对应一条推理规那么第四页，共六十六页。1建立(jiànlì)决策树，利用训练样本生成决策树模型。

开始，数据都在根节点递归的进行数据分片2修剪决策树

去掉一些可能是噪音或者异常的数据3使用决策树对未知数据进行分类

按照决策树上采用的分割属性逐层往下，直到一个叶子节点使用(shǐyòng)决策树进行分类判定树分类算法output训练集决策树input2026/4/28第五页，共六十六页。决策树的核心(héxīn)问题第一，决策树的生长(shēngzhǎng)，即利用训练样本集完成决策树的建立过程；1.如何从众多的输入变量中选择一个当前(dāngqián)最正确的分组变量；2.如何从分组变量的众多取值中找到一个最正确的分割点。第六页，共六十六页。决策树的核心(héxīn)问题第二，决策树的修剪，即利用检验样本集对形成(xíngchéng)的决策树进行优化处。过度拟和〔Overfitting〕预修剪〔pre-pruning〕、后修剪〔post-pruning〕第七页，共六十六页。训练(xùnliàn)集(Train)：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,...,vn;c);其中vi表示属性值,c表示类别。测试集(Test)：用于模型参数的估计，评估分类模型的准确率。

验证集(Validation):用于模型误差的估计。训练(xùnliàn)集与测试集2026/4/28第八页，共六十六页。a.模型训练阶段训练集b.使用模型分类阶段评估准确率〔测试(cèshì)集〕对类标号未知的新数据分类分类的两个(liǎnɡɡè)阶段2026/4/28第九页，共六十六页。根本算法自上而下分而治之的方法开始时，所有的数据都在根节点所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规那么或者一个统计(tǒngjì)的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割2026/4/28第十页，共六十六页。建树(jiànshù)阶段MakeTree(TrainingDataT)

Partition(T);

Partition(DataS)

if(allpointsinSareinthesameclass)thenreturn;

evaluatesplitsforeachattributeA

UsebestsplitfoundtopartitionSintoS1andS2;

Partition(S1);

Partition(S2);2026/4/28第十一页，共六十六页。属性选择度量(dùliàng)标准－－分支指标信息增益(zēngyì)——Informationgain〔ID3〕增益比率——Gainration〔C4.5,C5.0〕基尼指数——Giniindex(SLIQ，SPRINT)

…………2026/4/28第十二页，共六十六页。

1、信息是用来(yònɡlái)消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。信息量的数学定义：2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为：信息论的根本(gēnběn)概念第十三页，共六十六页。1、信源熵H(X)信源熵是度量整个信源X整体的平均不确定性，也称先验熵。2、条件熵H(X/Y)条件熵是一个确定值，表示收信者在收到Y后，信源X仍然(réngrán)存在的不确定度，也称为后验熵。3、互信息量熵差H(X)－H(X/Y)是不确定性的消除，即互信息才是接收端所获得的信息量。信息论的根本(gēnběn)概念

2026/4/28第十四页，共六十六页。

ID3算法是借用信息论中的互信息寻找训练集具有最大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支;在每个分支子集中重复建立树的下层(xiàcéng)节点和分支过程。

ID3算法(suànfǎ)2026/4/28第十五页，共六十六页。

ID3算法(suànfǎ)2026/4/28第十六页，共六十六页。ID3Tree(T，T-attributelist)T为样本空间，T-attributelist为属性集。(1)创立根结点N。(2)IFT都属于同一类C，那么返回N为叶结点，标记为类C。(3)IFT-attributelist为空或T中所剩的样本数少于某给定值，那么返回N为叶结点，标记为T中出现最多的类。(4)

FOREACHT-attributelist中的属性，计算信息增益informationgain。(5)结点N的分裂属性为T-attributelist中具有最高信息增益的属性。(6)

FOREACH由结点N长出的新结点{IF该结点对应的样本子集只有(zhǐyǒu)唯一的一种决策类别，那么将该结点标记为该类别的叶结点;ELSE在该结点上执行ID3Tree(T’，T’-attributelist)，对它继续进行分裂;}其中，T’为由结点N划分而来的子集，T’-attributeslit为去除被选分裂属性后的属性集。2.ID3算法(suànfǎ)描述2026/4/28第十七页，共六十六页。用决策树考察某顾客(gùkè)是否会购置PC顾客(gùkè)数据表2026/4/28第十八页，共六十六页。类标号属性为购置PC，它有两个不同的值(“是〞、“否〞)，即有两个不同的类，m=2；设p对应“是〞，n对应“否〞，那么p=9，n=5。1)创立根结点(jiédiǎn)先计算对给定样本分类所需的期望信息。=0.94下面计算每个属性的熵。从年龄开始计算。年龄=“<=30〞： p11=2，n11=3I(p11，n11)=0.971年龄=“30~40〞： p12=4，n12=0I(p12，n12)=0年龄=“>40〞： p13=3，n13=2I(p13，n13)=0.971如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下

=0.694因此，这种划分的信息增益是：Gain(年龄)=I(P，N)-E(年龄)=0.246。同理可得Gain(收入)=0.029Gain(是否学生)=0.151Gain(信用)=0.048在所有的属性中，年龄的信息增益最高，被选作测试属性。创立一个根结点，用年龄标记，并对每个属性值引出一个分支。2026/4/28第十九页，共六十六页。2)分支建立考虑分支“年龄=‘<=30’〞的结点。因为Gain(收入)=0.571Gain(学生)=0.971Gain(信用)=0.02所以分支“年龄=‘<=30’〞结点的测试属性为“学生〞。考虑分支“年龄=31~40〞的结点，由于所有记录属于(shǔyú)同一类别“是〞，所以分支“年龄=‘31~40’〞的结点为叶结点。考虑分支“年龄=‘>40’〞的结点。因为Gain(收入)=0.02Gain(学生)=0.02Gain(信用)=0.971所以分支“年龄=‘>40’〞结点的测试属性为“信用〞。考虑分支“学生=‘否’〞的结点，由于所有记录属于同一类别“否〞，所以分支“学生=‘否’〞的结点为叶结点。考虑分支“学生=‘是’〞的结点，由于所有记录属于同一类别“是〞，所以分支“学生=‘是’〞的结点为叶结点。考虑分支“信用=‘优’〞的结点，由于所有记录属于同一类别“否〞，所以分支“信用=‘否’〞的结点为叶结点。考虑分支“信用=‘中’〞的结点，由于所有记录属于同一类别“是〞，所以分支“信用=‘是’〞的结点为叶结点。2026/4/28第二十页，共六十六页。建立(jiànlì)的决策树：2026/4/28第二十一页，共六十六页。2026/4/28第二十二页，共六十六页。C4.5(C5.0)算法(suànfǎ)1993年由Quinlan提出，采用信息增益比(信息率)来选择(xuǎnzé)属性。克服偏向选择取值较多属性的缺点用阈值对属性(shǔxìng)划分，即把训练集中该属性(shǔxìng)的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;

视为senior.第二十三页，共六十六页。LOGO1、增益(zēngyì)率Why？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。第二十四页，共六十六页。LOGO

使用分裂信息(splitinformation)将信息增益规范化。该值表示数据集按属性测试的个划分产生的信息。增益率：选择具有最大信息率的属性作为分裂属性。第二十五页，共六十六页。增益(zēngyì)率income其他(qítā)属性的信息率可类似求出。第二十六页，共六十六页。在实际通信之前〔决策树建立之前〕，输出变量对信宿来讲是完全随机的，其平均不确定性为：决策树建立过程中，随着信宿接收到信息〔输入(shūrù)变量如T1〕，那么条件熵为：信息增益：T1作为最正确分组变量而非T3将输出变量(biànliàng)〔是否购置〕看作信源发出的信息U输入变量看作是信宿接收到的一系列信息V第二十七页，共六十六页。类别值多的输入变量比少的有更多的时机成为(chéngwéi)当前最正确分组变量C5.0算法:信息(xìnxī)增益率信息增益率的数学(shùxué)定义为：第二十八页，共六十六页。数值型输入变量首先对它进行分组处理，分组方法(fāngfǎ)采用基于MDLP的熵分组方法2、C5.0算法：数值型输入(shūrù)变量第二十九页，共六十六页。把连续(liánxù)值属性的值域分割为离散的区间集合。基于MDLP的熵分组方法。〔MinimunDescriptionLengthPrinciple〕信息增益大于编码长度合并连续(liánxù)值属性2026/4/28第三十页，共六十六页。选择最正确分组变量时，通常将带有缺失(quēshī)值的样本当临时剔除样本看待，并进行权数调整3、C5.0算法(suànfǎ):对缺失值问题的处理计算输出(shūchū)变量熵计算关于T1的条件熵计算经权数调整的T1信息增益计算信息增益率第三十一页，共六十六页。不继续确定关于分组变量的最正确分割点分类型输入变量：K叉树数值型输入变量：2叉树Clementine：ChiMerge分箱法在分组变量上取缺失值：第1个样本被分配到各组中的权数分别(fēnbié)为5/13、3/13、5/13，之后各组的样本数分别(fēnbié)为5＋5/13、3＋3/13、5＋5/13

4、C5.0算法:最正确(zhèngquè)分割点第三十二页，共六十六页。后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题通常应在检验样本集上估计误差并进行(jìnxíng)剪枝利用统计中置信度的思想直接在训练样本集中估计误差：当

为0.25时，5、C5.0算法(suànfǎ)：剪枝第三十三页，共六十六页。按照(ànzhào)“减少－误差〔reduce-error〕〞法判断是否剪枝C5.0算法(suànfǎ)：剪枝考虑是否可以剪掉最下层的3个叶结点3个结点的错误率：分别为：0.55、0.91、0.55；加权：计算父结点C的误差估计为0.50。由于(yóuyú)0.60大于0.50，因此可以剪掉3个叶结点。第三十四页，共六十六页。预测(yùcè)的置信度〔或误差〕会影响决策，错判的损失也会影响决策损失矩阵：6、C5.0算法(suànfǎ)：损失矩阵第三十五页，共六十六页。从损失角度决策，在各类错判损失不相等时〔不能仅从置信角度判断。事实上，默认(mòrèn)在损失相同时才考虑置信度〕：

c(i|j)是将j类错判为i类的损失，p(j|t)是被节点t判为j类的归一化概率C5.0算法：损失(sǔnshī)矩阵第三十六页，共六十六页。C5.0仅在剪枝时考虑损失(sǔnshī)，以二分类为例：C5.0算法：损失(sǔnshī)矩阵例如：取伪损失较大，给出yes判断的置信度都很高。模型复杂，决策树修剪程度低；如果取伪损失指定(zhǐdìng)为10，那么模型都判为No第三十七页，共六十六页。偏差和方差决策树算法具有一定的不稳健性，可以考虑利用多组样本建立多个模型(móxíng)，形成模型(móxíng)“委员会〞制度Bagging技术Boosting技术C5.0算法(suànfǎ)：模型“委员会〞第三十八页，共六十六页。建模过程〔输入：训练样本集T，训练次数k；输出：多个决策树模型C1,C2,…Ck)Fori=1,2,…,kdo从T中随机有放回抽取样本(yàngběn)，形成有相同样本(yàngběn)容量的样本(yàngběn)集合Ti以Ti为训练集构造模型CiEndfor决策过程〔输入：新数据X，多个决策树模型C1,C2,…Ck；输出：分类预测结果C(X)〕Fori=1,2,…,kdo根据Ci对X做预测，结果为Ci(X)Endfor统计各类别得票，得票数最高的为C(X)，或计算平均值C5.0算法(suànfǎ)：Bagging技术第三十九页，共六十六页。两个阶段(jiēduàn)：建立k个模型；k个模型投票C5.0算法(suànfǎ)：Boosting技术第四十页，共六十六页。Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据样本权数wj(i)，从T中有放回地抽取(chōuqǔ)n个样本形成训练样本集Ti；根据训练集Ti得到模型Ci；计算模型的误差e(i)如果e(i)>0.5或者e(i)=0，那么终止建模过程；C5.0算法(suànfǎ)：Boosting技术第四十一页，共六十六页。Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据误差更新每个样本的权数：正确分类(fēnlèi)的样本权数：wj(i+1)=wj(i)*ß(i)，ß(i)＝e(i)/(1-e(i))；错误分类的样本权数保持不变：wj(i+1)=wj(i)；调整wj(i+1)使得各样本的权重之和等于1经过k次迭代，将得到k个模型和k个误差C5.0算法(suànfǎ)：Boosting技术第四十二页，共六十六页。Boosting技术：投票过程〔决策过程〕采用加权投票，给不同的模型赋予不同的权数，权数与模型的误差成反比，具体(jùtǐ)为：对新样本X，每个模型Ci都给出预测值Ci(X)，给预测类Ci(X)加权：求各类权数的总和，总权数最高的类即为最终的分类结果Bagging与Boosting技术的比较Boosting例如C5.0算法(suànfǎ)：Boosting技术第四十三页，共六十六页。交叉验证：对于n折交叉验证，那么在训练样本集合中重抽样n组样本建立n个模型，并计算(jìsuàn)每个模型训练样本集上的预测精度，且给出n个模型预测精度的平均值和标准差未剪枝的决策树Pruningseverity中输入置信度。默认为100%－25%。值越大树越精简，预测精度会不理想〔误差较高〕；需要反复尝试C5.0算法(suànfǎ)：其他第四十四页，共六十六页。C5.0算法(suànfǎ)：推理规那么直接从决策树得到推理规那么很容易决策树对逻辑关系的表述(biǎoshù)不是最简洁的abccddyesnoyesnoyesnonoyyyyyynnnnnnIFaANDbTHENyesIFcANDdTHENyesOTHERWISEno第四十五页，共六十六页。生成推理规那么的一般算法是PRISM(PatientRuleInductionSpaceMethod)算法，Cendrowska于1987年提出.是一种(yīzhǒnɡ)“覆盖〞算法,所生成的规那么在训练样本集上是100％正确的确定期望(qīwàng)类别:yes年龄段=A(2/5)，年龄段=B(4/4)，年龄段=C(3/5)，性别=0(6/8)，性别=1(3/6)IF年龄段=BTHEN是否购置=yes规那么100％正确(zhèngquè)，更新数据集：第四十六页，共六十六页。规那么100％正确，更新(gēngxīn)数据集年龄段=A(2/5)，年龄段=C(3/5)，性别(xìngbié)=0(4/6)，性别(xìngbié)=1(1/4)IF性别=0THEN是否购置=yes年龄段=A(1/3),年龄段=C(3/3)IF性别=0AND年龄段=CTHEN是否购置=yes第四十七页，共六十六页。年龄段=A(2/5)，年龄段=C(0/2)，性别(xìngbié)=0(1/3)，性别(xìngbié)=1(1/4)IF年龄段=ATHEN是否购置=yes性别=0(1/3)，性别=1(1/2)IF年龄段=AAND性别(xìngbié)=1THEN是否购置=yes(略去)第四十八页，共六十六页。C5.0算法(suànfǎ)：推理规那么利用规那么集合对样本进行分类可能产生的问题：样本可能符合多个分类结果相同的规那么样本可能符合多个分类结果不相同的规那么样本不符合任何规那么例如：推理(tuīlǐ)规那么的预测置信度是普拉斯估计器调整后的结果第四十九页，共六十六页。模型评价Analysis结点比照模型在训练样本集和检验(jiǎnyàn)样本集上的性能差异比照不同模型的性能确定相对合理的置信水平折：如果总体的正确率为90%，错误率为10%，那么2折表示10%的一半，即错误率下降一半〔2折，3折为33%〕。如果改进2折，那么总体正确率为95%，C5.0算法(suànfǎ)：模型的评价第五十页，共六十六页。2026/4/28R中的实现(shíxiàn)R中决策树的实现，主要用到四个软件包：1、rpart:用于建立二分类树及相关递归划分算法的实现；2、rpart.plot：专用来对rpart模型绘制决策树；3、maptree：用来修剪、绘制不仅仅局限于rpart模型的树型结构图；4、Rweka：提供了R与Weka的连接，Weka中集合(jíhé)了用Java编写的一系列机器学习的算法。5、C50:运用C5.0算法建立决策树第五十一页，共六十六页。2026/4/28R中的实现(shíxiàn)第五十二页，共六十六页。R中的实现(shíxiàn)

C5.0：识别高分险客户2026/4/28使用read.csv()函数(hánshù)导入数据Str()函数(hánshù)用来创立数据字典，即显示了数据框结构。第五十三页，共六十六页。2026/4/28R中的实现(shíxiàn)

C5.0：识别高分险客户探索分类变量：table()函数用来产生单个类别变量的不同类别取值及对应(duìy