1、决策树算法概述决策树算法概述 决策树算法最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测。决策树算法属于有指导的学习。根结点叶结点内部结点兄弟结点2叉树多叉树分类预测分类预测 分类预测，就是通过向现有数据学习，使模型具备对未来新数据的分类预测能力。数据包含：输入变量 输出变量 分类和预测 分类：分类型输出变量 预测：数值型输出变量决策树算法概述决策树算法概述 决策树的种类：分类决策树：树叶结点所含样本的输出变量的众数就是分类结果。回归决策树：树叶结点所含样本的输出变量的平均值就是预测结果。利用决策树进行分类预测：对新数据进行分类预测时，只需按照决策树的层次，从根
2、结点开始依次对新数据输入变量值进行判断并进入不同的决策树分支，直至叶结点为止。特点：分类预测是基于逻辑的。IF THEN 每个叶节点对应一条推理规则1 1 建立决策树，利用训练样本生成决策树模型。建立决策树，利用训练样本生成决策树模型。开始，数据都在根节点 递归的进行数据分片2 2 修剪决策树修剪决策树 去掉一些可能是噪音或者异常的数据3 3 使用决策树使用决策树对未知数据进行分类对未知数据进行分类 按照决策树上采用的分割属性逐层往下，直 到一个叶子节点判定树分类算法output训练集决策树input2023-1-7决策树的核心问题决策树的核心问题 第一，决策树的生长，即利用训练样本集完成决策
3、树的建立过程；1.1.如何从众多的输入变量中选择一个当前如何从众多的输入变量中选择一个当前最佳的分组变量；最佳的分组变量；2.2.如何从分组变量的众多取值中找到一个如何从分组变量的众多取值中找到一个最佳的分割点最佳的分割点。决策树的核心问题决策树的核心问题 第二，决策树的修剪，即利用检验样本集对形成的决策树进行优化处。过度拟和（Overfitting）预修剪（pre-pruning）、后修剪（post-pruning）训练集训练集(Train)(Train)：数据库中为建立模型而被分析的数据元组形成训练集。训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v
4、1,v2,.,vn;c);其中vi表示属性值,c表示类别。测试集测试集(Test)(Test)：用于模型参数的估计，评估分类模型的准确率。验证集(Validation):用于模型误差的估计。2023-1-7a.模型训练阶段 训练集b.使用模型 分类阶段评估准确率（测试集）对类标号未知的新数据分类 2023-1-7 基本算法自上而下分而治之的方法开始时，所有的数据都在根节点所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割2023-1-7建树阶段M
5、akeTree(Training Data T)Partition(T);Partition(Data S)if(all points in S are in the same class)then return;Use best split found to partition S into S1 and S2;Partition(S1);Partition(S2);2023-1-7属性选择度量标准分支指标 （ID3ID3）（C4.5,C5.0C4.5,C5.0）(SLIQ(SLIQ，SPRINT)SPRINT)2023-1-7 1、信息是用来消除随机不确定性的度量。信息量的大小可由所消除的
6、不确定性大小来计量。信息量的数学定义：2、信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也称先验熵，信息熵的数学定义为：信息论的基本概念)(log)(1log)(22iiiuPuPuI)(log)()(1log)()(22iiiiiiuPuPuPuPUEnt1、信源熵H(X)信源熵是度量整个信源X整体的平均不确定性，也称先验熵。2、条件熵H(X/Y)条件熵是一个确定值，表示收信者在收到Y后，信源X仍然存在的不确定度，也称为后验熵。3、互信息量熵差H(X)H(X/Y)是不确定性的消除，即互信息才是接收端所获得的信息量。2023-1-7 ID3算法是借用信息论中的互信息寻找训练集具有最
7、大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支;在每个分支子集中重复建立树的下层节点和分支过程。2023-1-722(,)loglogppnnI p npnpnpnpn 2023-1-7ID3Tree(T，T-attributelist)T为样本空间，T-attributelist为属性集。(1)创建根结点N。(2)IF T都属于同一类C，则返回N为叶结点，标记为类C。(3)IF T-attributelist为空或T中所剩的样本数少于某给定值，则返回N为叶结点，标记为T中出现最多的类。(4)FOR EACH T-attributelist中的属性，计算信息增
8、益information gain。(5)结点N的分裂属性为T-attributelist中具有最高信息增益的属性。(6)FOR EACH由结点N长出的新结点IF 该结点对应的样本子集只有唯一的一种决策类别，则将该结点标记为该类别的叶结点;ELSE在该结点上执行ID3Tree(T，T-attributelist)，对它继续进行分裂;其中，T为由结点N划分而来的子集，T-attributeslit为去除被选分裂属性后的属性集。2023-1-7 用决策树考察某顾客是否会购买PC年 龄收 入是否学生信 用购买PC=30高否中否40中否中是40低是中是40低是优否3140低是优是=30中否中否40中是
9、中是40中否优否顾客数据表2023-1-7 类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设p对应“是”，n对应“否”，则p=9，n=5。1)创建根结点先计算对给定样本分类所需的期望信息。=0.94下面计算每个属性的熵。从年龄开始计算。年龄=“40”：p13=3，n13=2 I(p13，n13)=0.971如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下 =0.694 因此，这种划分的信息增益是：Gain(年龄)=I(P，N)-E(年龄)=0.246。同理可得Gain(收入)=0.029 Gain(是否学生)=0.151 Gain(信用)=0.0
10、48 在所有的属性中，年龄的信息增益最高，被选作测试属性。创建一个根结点，用年龄标记，并对每个属性值引出一个分支。22(,)loglogppnnI p npnpnpnpn 2023-1-72)2)分支建立分支建立考虑分支“年龄=30”的结点。因为Gain(收入)=0.571Gain(学生)=0.971 Gain(信用)=0.02所以分支“年龄=40”的结点。因为Gain(收入)=0.02Gain(学生)=0.02Gain(信用)=0.971所以分支“年龄=40”结点的测试属性为“信用”。考虑分支“学生=否”的结点，由于所有记录属于同一类别“否”，所以分支“学生=否”的结点为叶结点。考虑分支“学
11、生=是”的结点，由于所有记录属于同一类别“是”，所以分支“学生=是”的结点为叶结点。考虑分支“信用=优”的结点，由于所有记录属于同一类别“否”，所以分支“信用=否”的结点为叶结点。考虑分支“信用=中”的结点，由于所有记录属于同一类别“是”，所以分支“信用=是”的结点为叶结点。2023-1-7建立的决策树：2023-1-72023-1-7C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_
12、aged;视为senior.30age 30,40age40age LOGO信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。2()111(log)14110PIDInfoD()()()0.940PIDGain PIDInfo DInfoD对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。LOGO 使用分裂信息(split information)将信息增益规范化。4.5C21()*logvjjAjDDSplitInfoD
13、DD 该值表示数据集 按属性 测试的 个划分产生的信息。DAv增益率：()()()AGain AGainRatio ASplitInfoD选择具有最大信息率的属性作为分裂属性。增益率增益率222()44log141466 log141444 log14141.557incom eSplitInfoD()0.029()0.019()1.557incomeGain incomeGainRatio incomeSplitInfoD其他属性的信息率可类似求出。在实际通信之前（决策树建立之前），输出变量对信宿来讲是完全随机的，其平均不确定性为：决策树建立过程中，随着信宿接收到信息（输入变量如T1），则条
14、件熵为：信息增益：T1作为最佳分组变量而非T3940.0)145(log145)149(log149)(log)()(1log)()(2222iiiiiiuPuPuPuPUEnt694.0)52(log52)53(log53(145)40(log40)44(log44(144)53(log53)52(log52(145)1|(log)1|()1()1|(2222222jiijijjtuPtuPtPTUEnt将输出变量（是否购买）看作信源发出的信息U输入变量看作是信宿接收到的一系列信息V246.0694.0940.0)1|()()1,(TUEntUEntTUGains048.0892.0940.
15、0)3|()()3,(TUEntUEntTUGains类别值多的输入变量比少的有更多的机会成为当前最佳分组变量C5.0算法:信息增益率686867.0)52(log52)53(log53(145)40(log40)44(log44(144 )21(log21)21(log21(142)32(log32)31(log31(143)1|(log)1|()1()1|(222222222jiijijjtuPtuPtPTUEnt253133.069686867.0940.0)1|()()1,(TUEntUEntTUGains信息增益率的数学定义为：)(/),(),(VEntVUGainVUGainsR1
16、32.0924174.1/2531.0)145(log145)144(log144)142(log142)143(log143/(2531.0)1,(2222TUGainsR数值型输入变量首先对它进行分组处理，分组方法采用基于MDLP的熵分组方法2、C5.0算法：数值型输入变量把连续值属性的值域分割为离散的区间集合。基于MDLP的熵分组方法。（Minimun DescriptionLength Principle）信息增益大于编码长度2023-1-7选择最佳分组变量时，通常将带有缺失值的样本当临时剔除样本看待，并进行权数调整 3、C5.0算法:对缺失值问题的处理计算输出变量熵961.0)135
17、(log135)138(log138)(log)()(1log)()(2222iiiiiiuPuPuPuPUEnt计算关于T1的条件熵 747.0)52(log52)53(log53(135)30(log30)33(log33(133)53(log53)52(log52(135)1|(log)1|()1()1|(2222222jiijijjtuPtuPtPTUEnt计算经权数调整的T1信息增益 199.0)747.0961.0(1413)1|()(1413)1,(TUEntUEntTUGains计算信息增益率 128.0549.1/199.0)135(log135)133(log133)135
18、(log135/(199.0)1,(222TUGainsR不继续确定关于分组变量的最佳分割点分类型输入变量：K叉树数值型输入变量：2叉树Clementine：ChiMerge分箱法在分组变量上取缺失值：第1个样本被分配到各组中的权数分别为5/13、3/13、5/13，之后各组的样本数分别为55/13、33/13、55/13 4、C5.0算法:最佳分割点后修剪方法从叶结点向上逐层剪枝，关键是错误率即误差的估计问题通常应在检验样本集上估计误差并进行剪枝利用统计中置信度的思想直接在训练样本集中估计误差：当为0.25时，5、C5.0算法：剪枝1|)|)1(2zNffefPiiiiiNffzfeiiii
19、)1(215.12z按照“减少误差（reduce-error）”法判断是否剪枝C5.0算法：剪枝考虑是否可以剪掉最下层的3个叶结点3个结点的错误率：分别为：0.55、0.91、0.55；加权：计算父结点C的误差估计为0.50。由于0.60大于0.50，因此可以剪掉3个叶结点。60.0146*55.0142*91.0146*55.0),.,2,1(1kieepkiii预测的置信度（或误差）会影响决策，错判的损失也会影响决策损失矩阵：6、C5.0算法：损失矩阵预测值YesNo实际值Yes0mNon0从损失角度决策，在各类错判损失不相等时（不能仅从置信角度判断。事实上，默认在损失相同时才考虑置信度）
20、：c(i|j)是将j类错判为i类的损失，p(j|t)是被节点t判为j类的归一化概率C5.0算法：损失矩阵jtjjNNtjptjptjptjp,),(,),(),()|()|()|()|(mintiptjpjicjiC5.0仅在剪枝时考虑损失，以二分类为例：C5.0算法：损失矩阵),.,2,1(1kieccepkiiii示例：取伪损失较大，给出yes判断的置信度都很高。模型复杂，决策树修剪程度低；如果取伪损失指定为10，则模型都判为No偏差和方差决策树算法具有一定的不稳健性，可以考虑利用多组样本建立多个模型，形成模型“委员会”制度Bagging技术Boosting技术C5.0算法：模型“委员会”
21、建模过程（输入：训练样本集T，训练次数k；输出：多个决策树模型C1,C2,Ck)For i=1,2,k do 从T中随机有放回抽取样本，形成有相同样本容量的样本集合Ti 以Ti为训练集构造模型CiEnd for决策过程（输入：新数据X，多个决策树模型C1,C2,Ck；输出：分类预测结果C(X)）For i=1,2,k do 根据Ci对X做预测，结果为Ci(X)End for统计各类别得票，得票数最高的为C(X)，或计算平均值 C5.0算法：Bagging技术两个阶段：建立k个模型；k个模型投票C5.0算法：Boosting技术Boosting技术：建模过程初试化样本权数：wj(i)=1/n对每
22、次迭代：根据样本权数wj(i)，从T中有放回地抽取n个样本形成训练样本集Ti；根据训练集Ti得到模型Ci；计算模型的误差e(i)如果e(i)0.5 或者e(i)=0，则终止建模过程；C5.0算法：Boosting技术Boosting技术：建模过程初试化样本权数：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个误差nmjjjiwiwiw1)1()1()1(C5.0算法
23、：Boosting技术Boosting技术：投票过程（决策过程）采用加权投票，给不同的模型赋予不同的权数，权数与模型的误差成反比，具体为：对新样本X，每个模型Ci都给出预测值Ci(X)，给预测类Ci(X)加权：求各类权数的总和，总权数最高的类即为最终的分类结果Bagging与Boosting技术的比较Boosting示例)(1)(log()(ieieXWiC5.0算法：Boosting技术交叉验证：对于n折交叉验证，则在训练样本集合中重抽样n组样本建立n个模型，并计算每个模型训练样本集上的预测精度，且给出n个模型预测精度的平均值和标准差未剪枝的决策树Pruning severity中输入置信度
24、。默认为100%25%。值越大树越精简，预测精度会不理想（误差较高）；需要反复尝试 C5.0算法：其他C5.0算法：推理规则直接从决策树得到推理规则很容易决策树对逻辑关系的表述不是最简洁的abccddyesnoyesnoyesnonoyyyyyynnnnnnIF a AND b THEN yesIF c AND d THEN yesOTHERWISE no生成推理规则的一般算法是PRISM(Patient Rule Induction Space Method)算法，Cendrowska于1987年提出.是一种“覆盖”算法,所生成的规则在训练样本集上是100正确的 确定期望类别:yes年龄段=
25、A(2/5)，年龄段=B(4/4)，年龄段=C(3/5)，性别=0(6/8)，性别=1(3/6)IF 年龄段=B THEN 是否购买=yes 规则100正确，更新数据集：规则100正确，更新数据集年龄段=A(2/5)，年龄段=C(3/5)，性别=0(4/6)，性别=1(1/4)IF 性别=0 THEN 是否购买=yes 年龄段=A(1/3),年龄段=C(3/3)IF 性别=0 AND 年龄段=C THEN 是否购买=yes 年龄段=A(2/5)，年龄段=C(0/2)，性别=0(1/3)，性别=1(1/4)IF 年龄段=A THEN 是否购买=yes 性别=0(1/3)，性别=1(1/2)IF
26、年龄段=A AND 性别=1 THEN 是否购买=yes(略去)C5.0算法：推理规则利用规则集合对样本进行分类可能产生的问题：样本可能符合多个分类结果相同的规则样本可能符合多个分类结果不相同的规则样本不符合任何规则示例：推理规则的预测置信度是普拉斯估计器调整后的结果 模型评价Analysis结点对比模型在训练样本集和检验样本集上的性能差异对比不同模型的性能确定相对合理的置信水平折：如果总体的正确率为90%，错误率为10%，则2折表示10%的一半，即错误率下降一半（2折，3折为33%）。如果改进2折，则总体正确率为95%，C5.0算法：模型的评价2023-1-7R中的实现中的实现R中决策树的实
27、现，主要用到四个软件包：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()2023-1-7R中的实现中的实现2023-1-72023-1-7探索分类变量：table()函数用来产生单个类别变量的不同类别取值及对应的数量2023-1-7创建随机的训练集和测试集2023-1-72023-1-72023-1-72023-1-72023-1-72023-1-72023-1-72023-1-72023-1-72023-1-7
