分类挖掘决策树课件

决策树算法概述决策树算法最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测。决策树算法属于有指导的学习。根结点叶结点内部结点兄弟结点2叉树多叉树决策树算法概述决策树算法最早源于人工智能的机器学习技术，用以1分类预测分类预测，就是通过向现有数据学习，使模型具备对未来新数据的分类预测能力。数据包含：输入变量输出变量分类和预测分类：分类型输出变量预测：数值型输出变量分类预测分类预测，就是通过向现有数据学习，使模型具备对未来新2决策树算法概述决策树的种类：分类决策树：树叶结点所含样本的输出变量的众数就是分类结果。回归决策树：树叶结点所含样本的输出变量的平均值就是预测结果。利用决策树进行分类预测：对新数据进行分类预测时，只需按照决策树的层次，从根结点开始依次对新数据输入变量值进行判断并进入不同的决策树分支，直至叶结点为止。特点：分类预测是基于逻辑的。IFTHEN每个叶节点对应一条推理规则决策树算法概述决策树的种类：31建立决策树，利用训练样本生成决策树模型。

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

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

按照决策树上采用的分割属性逐层往下，直到一个叶子节点使用决策树进行分类判定树分类算法output训练集决策树input2022/11/221建立决策树，利用训练样本生成决策树模型。使用决策树进4决策树的核心问题第一，决策树的生长，即利用训练样本集完成决策树的建立过程；1.如何从众多的输入变量中选择一个当前最佳的分组变量；2.如何从分组变量的众多取值中找到一个最佳的分割点。决策树的核心问题第一，决策树的生长，即利用训练样本集完成决策5决策树的核心问题第二，决策树的修剪，即利用检验样本集对形成的决策树进行优化处。过度拟和（Overfitting）预修剪（pre-pruning）、后修剪（post-pruning）决策树的核心问题第二，决策树的修剪，即利用检验样本集对形成的6训练集(Train)：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,...,vn;c);其中vi表示属性值,c表示类别。测试集(Test)：用于模型参数的估计，评估分类模型的准确率。

验证集(Validation):用于模型误差的估计。训练集与测试集2022/11/22训练集(Train)：数据库中为建立模型而被分析的数据元组形7a.模型训练阶段

训练集b.使用模型分类阶段评估准确率（测试集）对类标号未知的新数据分类

分类的两个阶段2022/11/22a.模型训练阶段分类的两个阶段2022/11/218基本算法自上而下分而治之的方法开始时，所有的数据都在根节点所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割2022/11/22基本算法2022/11/219建树阶段MakeTree(TrainingDataT)

Partition(T);

Partition(DataS)

if(allpointsinSareinthesameclass)thenreturn;

evaluatesplitsforeachattributeA

UsebestsplitfoundtopartitionSintoS1andS2;

Partition(S1);

Partition(S2);2022/11/222022/11/2110属性选择度量标准－－分支指标信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5,C5.0）基尼指数——Giniindex

(SLIQ，SPRINT)

…………2022/11/22属性选择度量标准－－分支指标信息增益——Informatio11

1、信息是用来消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。信息量的数学定义：2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为：信息论的基本概念1、信息是用来消除随机不确定性的度量。信息量的大小可由121、信源熵H(X)信源熵是度量整个信源X整体的平均不确定性，也称先验熵。2、条件熵H(X/Y)条件熵是一个确定值，表示收信者在收到Y后，信源X仍然存在的不确定度，也称为后验熵。3、互信息量熵差H(X)－H(X/Y)是不确定性的消除，即互信息才是接收端所获得的信息量。信息论的基本概念

2022/11/221、信源熵H(X)信息论的基本概念

2022/11/2113

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

ID3算法2022/11/22ID3算法是借用信息论中的互信息寻找训练集具有最大14

ID3算法2022/11/22

ID3算法2022/11/2115ID3Tree(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该结点对应的样本子集只有唯一的一种决策类别，则将该结点标记为该类别的叶结点;ELSE在该结点上执行ID3Tree(T’，T’-attributelist)，对它继续进行分裂;}其中，T’为由结点N划分而来的子集，T’-attributeslit为去除被选分裂属性后的属性集。2.ID3算法描述2022/11/22ID3Tree(T，T-attributelist)2.I16

用决策树考察某顾客是否会购买PC年龄收入是否学生信用购买PC<=30高否中否<=30高否优否31~40高否中是>40中否中是>40低是中是>40低是优否31~40低是优是<=30中否中否<=30低是中是>40中是中是<=30中是优是31~40中否优是31~40高是中是>40中否优否顾客数据表2022/11/22用决策树考察某顾客是否会购买PC年龄收入是17

类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设p对应“是”，n对应“否”，则p=9，n=5。1)创建根结点先计算对给定样本分类所需的期望信息。

=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

在所有的属性中，年龄的信息增益最高，被选作测试属性。创建一个根结点，用年龄标记，并对每个属性值引出一个分支。2022/11/22类标号属性为购买PC，它有两个不同的值(“是182)分支建立考虑分支“年龄=‘<=30’”的结点。因为Gain(收入)=0.571Gain(学生)=0.971Gain(信用)=0.02所以分支“年龄=‘<=30’”结点的测试属性为“学生”。考虑分支“年龄=31~40”的结点，由于所有记录属于同一类别“是”，所以分支“年龄=‘31~40’”的结点为叶结点。考虑分支“年龄=‘>40’”的结点。因为Gain(收入)=0.02Gain(学生)=0.02Gain(信用)=0.971所以分支“年龄=‘>40’”结点的测试属性为“信用”。考虑分支“学生=‘否’”的结点，由于所有记录属于同一类别“否”，所以分支“学生=‘否’”的结点为叶结点。考虑分支“学生=‘是’”的结点，由于所有记录属于同一类别“是”，所以分支“学生=‘是’”的结点为叶结点。考虑分支“信用=‘优’”的结点，由于所有记录属于同一类别“否”，所以分支“信用=‘否’”的结点为叶结点。考虑分支“信用=‘中’”的结点，由于所有记录属于同一类别“是”，所以分支“信用=‘是’”的结点为叶结点。2022/11/222)分支建立2022/11/2119建立的决策树：2022/11/22建立的决策树：2022/11/21202022/11/222022/11/2121C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;

视为senior.C4.5(C5.0)算法1993年由Quinlan提出，采用22LOGO1、增益率Why？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。LOGO1、增益率W23LOGO

使用分裂信息(splitinformation)将信息增益规范化。该值表示数据集按属性测试的个划分产生的信息。增益率：选择具有最大信息率的属性作为分裂属性。LOGO使用分24增益率income其他属性的信息率可类似求出。增益率income其他属性的信息率可类似求出。25在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随机的，其平均不确定性为：决策树建立过程中，随着信宿接收到信息（输入变量如T1），则条件熵为：信息增益：T1作为最佳分组变量而非T3将输出变量（是否购买）看作信源发出的信息U输入变量看作是信宿接收到的一系列信息V在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随26类别值多的输入变量比少的有更多的机会成为当前最佳分组变量C5.0算法:信息增益率信息增益率的数学定义为：类别值多的输入变量比少的有更多的机会成为当前最佳分组变量C527数值型输入变量首先对它进行分组处理，分组方法采用基于MDLP的熵分组方法2、C5.0算法：数值型输入变量数值型输入变量2、C5.0算法：数值型输入变量28把连续值属性的值域分割为离散的区间集合。基于MDLP的熵分组方法。（MinimunDescriptionLengthPrinciple）信息增益大于编码长度合并连续值属性2022/11/22把连续值属性的值域合并连续值属性2022/11/2129选择最佳分组变量时，通常将带有缺失值的样本当临时剔除样本看待，并进行权数调整

3、C5.0算法:对缺失值问题的处理计算输出变量熵计算关于T1的条件熵计算经权数调整的T1信息增益计算信息增益率选择最佳分组变量时，通常将带有缺失值的样本当临时剔除样本看待30不继续确定关于分组变量的最佳分割点分类型输入变量：K叉树数值型输入变量：2叉树Clementine：ChiMerge分箱法在分组变量上取缺失值：第1个样本被分配到各组中的权数分别为5/13、3/13、5/13，之后各组的样本数分别为5＋5/13、3＋3/13、5＋5/13

4、C5.0算法:最佳分割点不继续确定关于分组变量的最佳分割点4、C5.0算法:最佳分割31后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题通常应在检验样本集上估计误差并进行剪枝利用统计中置信度的思想直接在训练样本集中估计误差：当为0.25时，5、C5.0算法：剪枝后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题32按照“减少－误差（reduce-error）”法判断是否剪枝C5.0算法：剪枝考虑是否可以剪掉最下层的3个叶结点3个结点的错误率：分别为：0.55、0.91、0.55；加权：计算父结点C的误差估计为0.50。由于0.60大于0.50，因此可以剪掉3个叶结点。按照“减少－误差（reduce-error）”法判断是否剪枝33预测的置信度（或误差）会影响决策，错判的损失也会影响决策损失矩阵：6、C5.0算法：损失矩阵预测值YesNo实际值Yes0mNon0预测的置信度（或误差）会影响决策，错判的损失也会影响决策6、34从损失角度决策，在各类错判损失不相等时（不能仅从置信角度判断。事实上，默认在损失相同时才考虑置信度）：

c(i|j)是将j类错判为i类的损失，p(j|t)是被节点t判为j类的归一化概率C5.0算法：损失矩阵从损失角度决策，在各类错判损失不相等时（不能仅从置信角度判断35C5.0仅在剪枝时考虑损失，以二分类为例：C5.0算法：损失矩阵示例：取伪损失较大，给出yes判断的置信度都很高。模型复杂，决策树修剪程度低；如果取伪损失指定为10，则模型都判为NoC5.0仅在剪枝时考虑损失，以二分类为例：C5.0算法：损失36偏差和方差决策树算法具有一定的不稳健性，可以考虑利用多组样本建立多个模型，形成模型“委员会”制度Bagging技术Boosting技术C5.0算法：

模型“委员会”偏差和方差C5.0算法：模型“委员会”37建模过程（输入：训练样本集T，训练次数k；输出：多个决策树模型C1,C2,…Ck)Fori=1,2,…,kdo

从T中随机有放回抽取样本，形成有相同样本容量的样本集合Ti

以Ti为训练集构造模型CiEndfor决策过程（输入：新数据X，多个决策树模型C1,C2,…Ck；输出：分类预测结果C(X)）Fori=1,2,…,kdo

根据Ci对X做预测，结果为Ci(X)Endfor统计各类别得票，得票数最高的为C(X)，或计算平均值

C5.0算法：Bagging技术建模过程（输入：训练样本集T，训练次数k；输出：多个决策树模38两个阶段：建立k个模型；k个模型投票C5.0算法：Boosting技术两个阶段：建立k个模型；k个模型投票C5.0算法：Boos39Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据样本权数wj(i)，从T中有放回地抽取n个样本形成训练样本集Ti；根据训练集Ti得到模型Ci；计算模型的误差e(i)如果e(i)>0.5或者e(i)=0，则终止建模过程；C5.0算法：Boosting技术Boosting技术：建模过程C5.0算法：Boosting40Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据误差更新每个样本的权数：正确分类的样本权数：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算法：Boosting技术Boosting技术：建模过程C5.0算法：Boosting41Boosting技术：投票过程（决策过程）采用加权投票，给不同的模型赋予不同的权数，权数与模型的误差成反比，具体为：对新样本X，每个模型Ci都给出预测值Ci(X)，给预测类Ci(X)加权：求各类权数的总和，总权数最高的类即为最终的分类结果Bagging与Boosting技术的比较Boosting示例C5.0算法：Boosting技术Boosting技术：投票过程（决策过程）C5.0算法：Bo42交叉验证：对于n折交叉验证，则在训练样本集合中重抽样n组样本建立n个模型，并计算每个模型训练样本集上的预测精度，且给出n个模型预测精度的平均值和标准差未剪枝的决策树Pruningseverity中输入置信度。默认为100%－25%。值越大树越精简，预测精度会不理想（误差较高）；需要反复尝试C5.0算法：其他交叉验证：对于n折交叉验证，则在训练样本集合中重抽样n组样本43C5.0算法：推理规则直接从决策树得到推理规则很容易决策树对逻辑关系的表述不是最简洁的abccddyesnoyesnoyesnonoyyyyyynnnnnnIFaANDbTHENyesIFcANDdTHENyesOTHERWISEnoC5.0算法：推理规则直接从决策树得到推理规则很容易abcc44生成推理规则的一般算法是PRISM(PatientRuleInductionSpaceMethod)算法，Cendrowska于1987年提出.是一种“覆盖”算法,所生成的规则在训练样本集上是100％正确的

确定期望类别:yes年龄段=A(2/5)，年龄段=B(4/4)，年龄段=C(3/5)，性别=0(6/8)，性别=1(3/6)IF年龄段=BTHEN是否购买=yes规则100％正确，更新数据集：生成推理规则的一般算法是PRISM(PatientRule45规则100％正确，更新数据集年龄段=A(2/5)，年龄段=C(3/5)，性别=0(4/6)，性别=1(1/4)IF性别=0THEN是否购买=yes

年龄段=A(1/3),年龄段=C(3/3)IF性别=0AND年龄段=CTHEN是否购买=yes规则100％正确，更新数据集年龄段=A(2/5)，年龄段=C46年龄段=A(2/5)，年龄段=C(0/2)，性别=0(1/3)，性别=1(1/4)IF年龄段=ATHEN是否购买=yes性别=0(1/3)，性别=1(1/2)IF年龄段=AAND性别=1THEN是否购买=yes(略去)年龄段=A(2/5)，年龄段=C(0/2)，性别=0(1/347C5.0算法：推理规则利用规则集合对样本进行分类可能产生的问题：样本可能符合多个分类结果相同的规则样本可能符合多个分类结果不相同的规则样本不符合任何规则示例：推理规则的预测置信度是普拉斯估计器调整后的结果

C5.0算法：推理规则利用规则集合对样本进行分类可能产生的问48模型评价Analysis结点对比模型在训练样本集和检验样本集上的性能差异对比不同模型的性能确定相对合理的置信水平折：如果总体的正确率为90%，错误率为10%，则2折表示10%的一半，即错误率下降一半（2折，3折为33%）。如果改进2折，则总体正确率为95%，C5.0算法：模型的评价模型评价C5.0算法：模型的评价492022/11/22R中的实现R中决策树的实现，主要用到四个软件包：1、rpart:用于建立二分类树及相关递归划分算法的实现；2、rpart.plot：专用来对rpart模型绘制决策树；3、maptree：用来修剪、绘制不仅仅局限于rpart模型的树型结构图；4、Rweka：提供了R与Weka的连接，Weka中集合了用Java编写的一系列机器学习的算法。5、C50:运用C5.0算法建立决策树算法名称软件包核心函数CARTrpartrpart()、prune.rpart()、post()rpart.plotrpart.plot()maptreedraw.tree()C4.5RWekaJ48()C5.0C50C5.0()2022/11/21R中的实现R中决策树的实现，主要用到四个502022/11/22R中的实现2022/11/21R中的实现51R中的实现

C5.0：识别高分险客户2022/11/22R中的实现

C5.0：识别高分险客户2022/11/21522022/11/22R中的实现

C5.0：识别高分险客户探索分类变量：table()函数用来产生单个类别变量的不同类别取值及对应的数量2022/11/21R中的实现

C5.0：识别高分险客户探索532022/11/22R中的实现

C5.0：识别高分险客户创建随机的训练集和测试集2022/11/21R中的实现

C5.0：识别高分险客户创建542022/11/22R中的实现

C5.0：识别高分险客户2022/11/21R中的实现

C5.0：识别高分险客户552022/11/22R中的实现C5.0：识别高分险客户2022/11/21R中的实现C5.0：识别高分险客562022/11/22R中的实现

C5.0：识别高分险客户2022/11/21R中的实现

C5.0：识别高分险客户572022/11/22R中的实现

C5.0：识别高分险客户2022/11/21R中的实现

C5.0：识别高分险客户582022/11/22R中的实现C5.0：识别高分险客户2022/11/21R中的实现C5.0：识别高分险客户592022/11/22R中的实现C5.0：识别高分险客户2022/11/21R中的实现C5.0：识别高分险客户602022/11/22R中的实现C5.0：识别高分险客户2022/11/21R中的实现C5.0：识别高分险客户612022/11/22R中的实现C5.0：识别高分险客户2022/11/21R中的实现C5.0：识别高分险客户622022/11/22R中的实现C5.0：识别高分险客户2022/11/21R中的实现C5.0：识别高分险客户632022/11/222022/11/2164决策树算法概述决策树算法最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测。决策树算法属于有指导的学习。根结点叶结点内部结点兄弟结点2叉树多叉树决策树算法概述决策树算法最早源于人工智能的机器学习技术，用以65分类预测分类预测，就是通过向现有数据学习，使模型具备对未来新数据的分类预测能力。数据包含：输入变量输出变量分类和预测分类：分类型输出变量预测：数值型输出变量分类预测分类预测，就是通过向现有数据学习，使模型具备对未来新66决策树算法概述决策树的种类：分类决策树：树叶结点所含样本的输出变量的众数就是分类结果。回归决策树：树叶结点所含样本的输出变量的平均值就是预测结果。利用决策树进行分类预测：对新数据进行分类预测时，只需按照决策树的层次，从根结点开始依次对新数据输入变量值进行判断并进入不同的决策树分支，直至叶结点为止。特点：分类预测是基于逻辑的。IFTHEN每个叶节点对应一条推理规则决策树算法概述决策树的种类：671建立决策树，利用训练样本生成决策树模型。

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

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

按照决策树上采用的分割属性逐层往下，直到一个叶子节点使用决策树进行分类判定树分类算法output训练集决策树input2022/11/221建立决策树，利用训练样本生成决策树模型。使用决策树进68决策树的核心问题第一，决策树的生长，即利用训练样本集完成决策树的建立过程；1.如何从众多的输入变量中选择一个当前最佳的分组变量；2.如何从分组变量的众多取值中找到一个最佳的分割点。决策树的核心问题第一，决策树的生长，即利用训练样本集完成决策69决策树的核心问题第二，决策树的修剪，即利用检验样本集对形成的决策树进行优化处。过度拟和（Overfitting）预修剪（pre-pruning）、后修剪（post-pruning）决策树的核心问题第二，决策树的修剪，即利用检验样本集对形成的70训练集(Train)：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,...,vn;c);其中vi表示属性值,c表示类别。测试集(Test)：用于模型参数的估计，评估分类模型的准确率。

验证集(Validation):用于模型误差的估计。训练集与测试集2022/11/22训练集(Train)：数据库中为建立模型而被分析的数据元组形71a.模型训练阶段

训练集b.使用模型分类阶段评估准确率（测试集）对类标号未知的新数据分类

分类的两个阶段2022/11/22a.模型训练阶段分类的两个阶段2022/11/2172基本算法自上而下分而治之的方法开始时，所有的数据都在根节点所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,informationgain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割2022/11/22基本算法2022/11/2173建树阶段MakeTree(TrainingDataT)

Partition(T);

Partition(DataS)

if(allpointsinSareinthesameclass)thenreturn;

evaluatesplitsforeachattributeA

UsebestsplitfoundtopartitionSintoS1andS2;

Partition(S1);

Partition(S2);2022/11/222022/11/2174属性选择度量标准－－分支指标信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5,C5.0）基尼指数——Giniindex

(SLIQ，SPRINT)

…………2022/11/22属性选择度量标准－－分支指标信息增益——Informatio75

1、信息是用来消除随机不确定性的度量。信息量的大小可由所消除的不确定性大小来计量。信息量的数学定义：2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为：信息论的基本概念1、信息是用来消除随机不确定性的度量。信息量的大小可由761、信源熵H(X)信源熵是度量整个信源X整体的平均不确定性，也称先验熵。2、条件熵H(X/Y)条件熵是一个确定值，表示收信者在收到Y后，信源X仍然存在的不确定度，也称为后验熵。3、互信息量熵差H(X)－H(X/Y)是不确定性的消除，即互信息才是接收端所获得的信息量。信息论的基本概念

2022/11/221、信源熵H(X)信息论的基本概念

2022/11/2177

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

ID3算法2022/11/22ID3算法是借用信息论中的互信息寻找训练集具有最大78

ID3算法2022/11/22

ID3算法2022/11/2179ID3Tree(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该结点对应的样本子集只有唯一的一种决策类别，则将该结点标记为该类别的叶结点;ELSE在该结点上执行ID3Tree(T’，T’-attributelist)，对它继续进行分裂;}其中，T’为由结点N划分而来的子集，T’-attributeslit为去除被选分裂属性后的属性集。2.ID3算法描述2022/11/22ID3Tree(T，T-attributelist)2.I80

用决策树考察某顾客是否会购买PC年龄收入是否学生信用购买PC<=30高否中否<=30高否优否31~40高否中是>40中否中是>40低是中是>40低是优否31~40低是优是<=30中否中否<=30低是中是>40中是中是<=30中是优是31~40中否优是31~40高是中是>40中否优否顾客数据表2022/11/22用决策树考察某顾客是否会购买PC年龄收入是81

类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设p对应“是”，n对应“否”，则p=9，n=5。1)创建根结点先计算对给定样本分类所需的期望信息。

=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

在所有的属性中，年龄的信息增益最高，被选作测试属性。创建一个根结点，用年龄标记，并对每个属性值引出一个分支。2022/11/22类标号属性为购买PC，它有两个不同的值(“是822)分支建立考虑分支“年龄=‘<=30’”的结点。因为Gain(收入)=0.571Gain(学生)=0.971Gain(信用)=0.02所以分支“年龄=‘<=30’”结点的测试属性为“学生”。考虑分支“年龄=31~40”的结点，由于所有记录属于同一类别“是”，所以分支“年龄=‘31~40’”的结点为叶结点。考虑分支“年龄=‘>40’”的结点。因为Gain(收入)=0.02Gain(学生)=0.02Gain(信用)=0.971所以分支“年龄=‘>40’”结点的测试属性为“信用”。考虑分支“学生=‘否’”的结点，由于所有记录属于同一类别“否”，所以分支“学生=‘否’”的结点为叶结点。考虑分支“学生=‘是’”的结点，由于所有记录属于同一类别“是”，所以分支“学生=‘是’”的结点为叶结点。考虑分支“信用=‘优’”的结点，由于所有记录属于同一类别“否”，所以分支“信用=‘否’”的结点为叶结点。考虑分支“信用=‘中’”的结点，由于所有记录属于同一类别“是”，所以分支“信用=‘是’”的结点为叶结点。2022/11/222)分支建立2022/11/2183建立的决策树：2022/11/22建立的决策树：2022/11/21842022/11/222022/11/2185C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;

视为senior.C4.5(C5.0)算法1993年由Quinlan提出，采用86LOGO1、增益率Why？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。LOGO1、增益率W87LOGO

使用分裂信息(splitinformation)将信息增益规范化。该值表示数据集按属性测试的个划分产生的信息。增益率：选择具有最大信息率的属性作为分裂属性。LOGO使用分88增益率income其他属性的信息率可类似求出。增益率income其他属性的信息率可类似求出。89在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随机的，其平均不确定性为：决策树建立过程中，随着信宿接收到信息（输入变量如T1），则条件熵为：信息增益：T1作为最佳分组变量而非T3将输出变量（是否购买）看作信源发出的信息U输入变量看作是信宿接收到的一系列信息V在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随90类别值多的输入变量比少的有更多的机会成为当前最佳分组变量C5.0算法:信息增益率信息增益率的数学定义为：类别值多的输入变量比少的有更多的机会成为当前最佳分组变量C591数值型输入变量首先对它进行分组处理，分组方法采用基于MDLP的熵分组方法2、C5.0算法：数值型输入变量数值型输入变量2、C5.0算法：数值型输入变量92把连续值属性的值域分割为离散的区间集合。基于MDLP的熵分组方法。（MinimunDescriptionLengthPrinciple）信息增益大于编码长度合并连续值属性2022/11/22把连续值属性的值域合并连续值属性2022/11/2193选择最佳分组变量时，通常将带有缺失值的样本当临时剔除样本看待，并进行权数调整

3、C5.0算法:对缺失值问题的处理计算输出变量熵计算关于T1的条件熵计算经权数调整的T1信息增益计算信息增益率选择最佳分组变量时，通常将带有缺失值的样本当临时剔除样本看待94不继续确定关于分组变量的最佳分割点分类型输入变量：K叉树数值型输入变量：2叉树Clementine：ChiMerge分箱法在分组变量上取缺失值：第1个样本被分配到各组中的权数分别为5/13、3/13、5/13，之后各组的样本数分别为5＋5/13、3＋3/13、5＋5/13

4、C5.0算法:最佳分割点不继续确定关于分组变量的最佳分割点4、C5.0算法:最佳分割95后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题通常应在检验样本集上估计误差并进行剪枝利用统计中置信度的思想直接在训练样本集中估计误差：当为0.25时，5、C5.0算法：剪枝后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题96按照“减少－误差（reduce-error）”法判断是否剪枝C5.0算法：剪枝考虑是否可以剪掉最下层的3个叶结点3个结点的错误率：分别为：0.55、0.91、0.55；加权：计算父结点C的误差估计为0.50。由于0.60大于0.50，因此可以剪掉3个叶结点。按照“减少－误差（reduce-error）”法判断是否剪枝97预测的置信度（或误差）会影响决策，错判的损失也会影响决策损失矩阵：6、C5.0算法：损失矩阵预测值YesNo实际值Yes0mNon0预测的置信度（或误差）会影响决策，错判的损失也会影响决策6、98从损失角度决策，在各类错判损失不相等时（不能仅从置信角度判断。事实上，默认在损失相同时才考虑置信度）：

c(i|j)是将j类错判为i类的损失，p(j|t)是被节点t判为j类的归一化概率C5.0算法：损失矩阵从损失角度决策，在各类错判损失不相等时（不能仅从置信角度判断99C5.0仅在剪枝时考虑损失，以二分类为例：C5.0算法：损失矩阵示例：取伪损失较大，给出yes判断的置信度都很高。模型复杂，决策树修剪程度低；如果取伪损失指定为10，则模型都判为NoC5.0仅在剪枝时考虑损失，以二分类为例：C5.0算法：损失100偏差和方差决策树算法具有一定的不稳健性，可以考虑利用多组样本建立多个模型，形成模型“委员会”制度Bagging技术Boosting技术C5.0算法：

模型“委员会”偏差和方差C5.0算法：模型“委员会”101建模过程（输入：训练样本集T，训练次数k；输出：多个决策树模型C1,C2,…Ck)Fori=1,2,…,kdo

从T中随机有放回抽取样本，形成有相同样本容量的样本集合Ti

以Ti为训练集构造模型CiEndfor决策过程（输入：新数据X，多个决策树模型C1,C2,…Ck；输出：分类预测结果C(X)）Fori=1,2,…,kdo

根据Ci对X做预测，结果为Ci(X)Endfor统计各类别得票，得票数最高的为C(X)，或计算平均值

C5.0算法：Bagging技术建模过程（输入：训练样本集T，训练次数k；输出：多个决策树模102两个阶段：建立k个模型；k个模型投票C5.0算法：Boosting技术两个阶段：建立k个模型；k个模型投票C5.0算法：Boos103Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据样本权数wj(i)，从T中有放回地抽取n个样本形成训练样本集Ti；根据训练集Ti得到模型Ci；计算模型的误差e(i)如果e(i)>0.5或者e(i)=0，则终止建模过程；C5.0算法：Boosting技术Boosting技术：建模过程C5.0算法：Boosting104Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每次迭代：根据误差更新每个样本的权数：正确分类的样本权数：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算法：Boosting技术Boosting技术：建模过程C5.0算法：Boosting105Boosting技术：投票过程（决策过程）采用加权投票，给不同的模型赋予不同的权数，权数与模型的误差成反比，具体为：对新样本X，每个模型Ci都给出预测值Ci(X)，给预测类Ci(X)加权：求各类权数的总和，总权数最高的类即为最终的分类结果Bagging与Boosting技术的比较Boosting示例C5.0算法：Boosting技术Boosting技术：投票过程（决策过程）C5.0算法：Bo106交叉验证：对于n折交叉验证，则在训练样本集合中重抽样n组样本建立n个模型，并计算每个模型训练样本集上的预测精度，且给出n个模型预测精度的平均值和标准差未剪枝的决策树Pruningseverity中输入置信度。默认为100%－25%。值越大树越精简，预测精度会不理想（误差较高）；需要反复尝试C5.0算法：其他交叉验证：对于n折交叉验证，则在训练样本集合中重抽样n组样本107C5.0算法：推理规则直接从决策树得到推理规则很容易决策树对逻辑关系的表述不是最简洁的abccddyesnoyesnoyesnonoyyyyyynnnnnnIFaANDbTHENyesIFcANDdTHENyesOTHERWISEnoC5.0算法：推理规则直接从决策树得到推理规则很容易abcc108生成推理规则的一般算法是PRISM(PatientRuleInductionSpaceMethod)算法，Cendrowska于1987年提出.是一种“覆盖”算法,所生成的规则在训练样本集上是100％正确