第10章 决策树教学课件R语言数据分析与挖掘.pptx
第10章 决策树教学课件R 语言数据分析与挖掘目录PAGE决策树概述01202决策树基本原理010103决策树R实现PAGE决策树概述301PAGE4决策树概述 决策树呈树形结构，是一种基本的回归和分类方法。决策树的基本思想由两个关键步骤组成：（1）第一步对特征空间按变量对分类效果影响大小进行变量和变量值选择；（2）第二步用选出的变量和变量值对数据区域进行矩阵划分，在不同的划分区间进行效果和模型复杂性比较，从而确定最合适的划分，分类结果由最终划分区域的优势类确定。决策树主要用于分类，也可用于回归，回归与分类的主要差异在于选择变量的标准不是分类的效果，而是预测误差。当决策树的输出变量(因变量)是分类变量时，叫分类树，而当决策树的输出变量为连续变量时称为回归树。虽然回归树的因变量是连续变量，但叶节点数据是有穷的，因此输出的值也是在这个叶节点上的观测值平均。回归树不用假定经典回归中的诸如独立性、正态性、线性等特性，自变量无论是数量变量还是定性变量都同样适用。和经典回归不同，决策树不需要对总体进行分布的假设。而且，决策树对于预测很容易解释，这是其优点。此外，决策树很容易计算，但有必要设定不使其过分生长的停止规则或者修剪方法。决策树的一个缺点是每次分叉只和前一次分叉有关，而且并不考虑对以后的影响。因此，每个节点都依赖于前面的节点，如果一开始的划分不同，结果也可能很不一样。4R 语言数据分析与挖掘（微课版）PAGE5决策树生成 从理论上概述决策树的构建过程，这一过程包括如下四个步骤。5R 语言数据分析与挖掘（微课版）1.决策树的生成这一过程将初始的包含大量信息的数据集，按照一定的划分条件逐层分类至不可再分或不需再分，充分生成树。具体的，在每一次分类中：先找出各个可以作为分类变量的自变量所有可能的划分条件，再对每一个自变量，比较在各个划分条件下所得分支的差异大小，选出使得分支差异最大的划分条件作为该自变量的最优划分；再将各个自变量在最优划分下所得分支的差异大小进行比较，选出差异最大者作为该节点的分类变量，并采用该变量的最优划分。2.生成树的剪枝利用决策树算法构建了初始的树之后，为了有效地分类，还要对其进行剪枝。这是因为，由于数据表示不当、有噪声等原因，会造成生成的决策树过大或过度拟合。因此为了简化决策树，寻找一颗最优的决策树，剪枝是一个必不可少的过程。不同的算法，其剪枝的方法也不尽相同。常用的剪枝方法有预剪枝和后剪枝两种。例如CHILD和C5.0采用预剪枝，CART则采用后剪枝。（1）预剪枝：是指在构建决策树之前，先指定好生长停止准则(例如指定某个评估参数的阈值)，此做法适合应用于大规模问题。（2）后剪枝：是指待决策树完全生长结束后，再根据一定的规则，剪去决策树中那些不具一般代表性的叶子节点或者分支。3.生成规则在生成一颗最优的决策树之后，就可以根据这颗决策树来生成一系列规则。这些规则采用“if,then”的形式。从根节点到叶子节点的每一条路径，都可以生成一条规则。这条路径上的分裂属性和分裂谓词形成规则的前件(if部分)，叶子节点的类标号形成规则的后件(then部分)。4.模型性能评估及预测建立好模型后，可以利用测试数据对生成的决策树进行测试，常用混淆矩阵和预测误差率来验证模型的性能。选择最优模型后，就可以对新数据进行预测分类。PAGE6决策树的优缺点6R 语言数据分析与挖掘（微课版）接下来，让我们总结下决策树算法的优点：（1）决策树算法易理解，机理解释起来简单。（2）决策树算法的时间复杂度较小，为用于训练决策树的数据样本的对数。（3）决策树算法既能用于分类也能用于回归。（4）能够处理多输出的问题。（5）对缺失值不敏感。（6）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。当然，决策树算法也不是没有缺点的，主要缺点如下：（1）对连续型的因变量比较难预测，因为其是利用叶节点样本的平均值计算得到。（2）容易出现过拟合。（3）当类别太多时，错误可能就会增加的比较快。（4）在处理特征关联性比较强的数据时表现得不是太好。（5）对于各类别样本数量不一致的数据（类失衡问题），在决策树当中，信息增益的结果偏向于那些具有更多数量的特征。PAGE决策树基本原理702PAGE8决策树基本原理8R 语言数据分析与挖掘（微课版）决策树算法在分类、预测、规则提取等领域有着广泛应用。在20世纪80年代初期，J.Ross Quinlan提出了ID3算法（Iterative Dichotomiser 3，迭代二叉树3代）以后，决策树在数据挖掘、机器学习领域得到极大的发展。Quinlan后来又提出了C4.5，随后又发布了C5.0算法。1984年，多位统计学家在著名的Classification and regression tree一书中提出了CART算法。ID3和CART几乎同时被提出，但都采用类似的方法从训练样本中学习决策树。决策树算法 算法描述ID3算法其核心是在决策树的各级分裂节点上，使用信息增益作为分裂变量的选择标准，来帮助确定生成每个节点时所应采用的合适自变量C4.5算法C4.5决策树算法相对于ID3算法的重要改进是使用信息增益率来选择节点属性。C4.5算法可以克服ID3算法存在的不足：ID3算法只适用于离散的自变量，而C4.5算法既能处理离散的自变量，也可以处理连续的自变量C5.0算法C5.0是C4.5应用于大数据集上的分类算法，主要在执行效率和内存使用方面进行了改进。适用于处理大数据集，采用Boosting方式提高模型准确率，又称为BoostingTrees。CART算法CART决策树是一种非常有效的非参数分类和回归方法，通过构建树、修剪树、评估树来构建一个决策树。当因变量是连续型时，该树称为回归树；当因变量是离散型时，该树称为分类树。CART算法也使用目标变量的纯度来分裂决策节点，只是它使用的分裂度量是Gini增益。需要注意的是，CART内部只支持二分叉树。条件推理决策树算法条件推理决策树算法的分裂方式不再以自变量分裂后的目标变量的纯度（如C4.5和CART算法）为分裂度量指标，而是以自变量与目标变量的相关性（一些统计检验）为分裂度量指标。后来又发展出快速无偏有效统计树（QUEST算法）。PAGE9ID3 算法基本原理9R 语言数据分析与挖掘（微课版）PAGE10ID3 算法流程10R 语言数据分析与挖掘（微课版）决策树是一种贪心算法，它以从上到下递归的方式构建决策树，每次选择分裂数据的变量都是当前的最佳选择，并不关心是否达到全局最优。PAGE11C4.5 算法11R 语言数据分析与挖掘（微课版）PAGE12CAR T 算法12R 语言数据分析与挖掘（微课版）PAGE13ID3、C4.5 和CAR T 算法比较13R 语言数据分析与挖掘（微课版）算法 支持模型 树结构 特征选择 连续值处理 缺失值处理 剪枝ID3 分类 多叉树 信息增益 不支持 不支持 不支持C4.5 分类 多叉树 信息增益比 支持 支持 支持CART 分类、回归 二叉树基尼系数，均方差支持 支持 支持PAGE决策树R 实现1403PAGE15决策树R 语言实现15R 语言数据分析与挖掘（微课版）各种决策树算法在R语言均有对应的函数实现。可以通过RWeka扩展包中的J48()函数来调用weka的C4.5算法；通过C50扩展包中的C5.0()函数实现C5.0算法；通过rpart扩展包中的rpart()函数实现CART算法；通过party扩展包中的ctree()函数实现条件推理决策树算法。1.J48()函数J48(formula,data,subset,na.action,control=Weka_control()其中，formula为建模公式；data为包含formula参数变量的数据框；subset为用于data中选取部分样本；na.action为缺失数据的处理方法，默认是删除目标变量的数据，保留自变量的数据；control为C4.5算法的参数，使用Weka_control()函数进行设置。2.C5.0()函数C5.0(x,y,trials=1,rules=FALSE,weights=NULL,costs=NULL,.)其中，x为一个包含训练数据的自变量；y为包含训练数据的因变量；trials为一个可选值，用于控制自助法循环的次数（默认为1）；costs为一个可选矩阵，用于给出与各种类型错误相对应的成本。3.rp ar t()函数rpart(formula,data,subset,na.action=na.rpart,method,parms,control,)其中，formula为建模公式；data为包含formula参数变量的数据框；subset为用于data中选取部分样本进行建模；na.action为缺失数据的处理方法，默认是删除目标变量的数据，保留自变量的数据；method为变量分割方法，该参数4种取值：连续型对应anova，分类型（因子）对应class，计数型对应poisson（泊松），生存分析型对应exp。一般情况下，函数会自动检验目标变量的数据类型，自动匹配合适的取值；control为模型建立时用于停止分裂的一些参数，其值是rpart.control函数的输出对象。4.ctr ee()函数ctree(formula,data,subset=NULL,weights=NULL,control=ctree_control(),)其中，formula为建模公式；data为包含formula参数变量的数据框；subset为用于data中选取部分样本进行建模；control为模型建立时用于停止分裂的一些参数，其值是ctree.control函数的输出对象。PAGE16C5.0 案例16R 语言数据分析与挖掘（微课版）#install.packages(C50)library(C50)tree_mod tree_modCall:C5.0.default(x=iris,c(Petal.Length,Petal.Width),y=iris$Species)Classification TreeNumber of samples:150 Number of predictors:2 Tree size:4 Non-standard options:attempt to group attributes summary(tree_mod)#查看详细信息Decision tree:Petal.Length 1.9:.Petal.Width 1.7:virginica(46/1)Petal.Width=1.7:.Petal.Length 4.9:virginica(6/2)Evaluation on training data(150 cases):Decision Tree-Size Errors 4 4(2.7%)(a)(b)(c)plot(tree_mod)#树模型可视化PAGE17C5.0 案例-提高模型性能17R 语言数据分析与挖掘（微课版）C5.0算法对C4.5算法改进的一个优点就是通过加入自适应增强（adaptive boosting）算法。众所周知，决策树容易造成过拟合。故以决策树作为基分类器，生成许多决策树，然后这些决策树通过投票表决的方式为每个样本选择最佳的分类。由于boosting算法可以更广泛地应用与任何机器学习算法，所以在下一小节将介绍该算法。C5.0()函数的参数trials，可以很轻松地将boosting算法添加到C5.0决策树中。与更多统计方法（例如随机梯度增强）相比，该方法的模型与AdaBoost相似。data(churn)#构建模型 treeModel treeModel1#查看模型对训练数据集的混淆矩阵(t0(t1 cat(普通模型对训练集的预测准确率:,+paste0(round(sum(diag(t0)*100/sum(t0),2),%)普通模型对训练集的预测准确率:95.92%cat(增加boosting的模模型对训练集的预测准确率:,+paste0(round(sum(diag(t1)*100/sum(t1),2),%)增加boosting的模模型对训练集的预测准确率:98.08%增加boosting的模模型对训练集的预测准确率:98.08%#查看模型对测试数据集的混淆矩阵(c0(c1 cat(普通模型对测试集的预测准确率:,+paste0(round(sum(diag(c0)*100/sum(c0),2),%)普通模型对测试集的预测准确率:94.72%cat(增加boosting的模模型对测试集的预测准确率:,+paste0(round(sum(diag(c1)*100/sum(c1),2),%)增加boosting的模模型对测试集的预测准确率:95.2%PAGE18C5.0 案例-增加代价函数18R 语言数据分析与挖掘（微课版）C5.0算法允许我们将一个惩罚因子分配到不同类型的错误上，这些惩罚因子设定在一个代价矩阵中，通过指定参数costs实现。假设将实际正样本错误预测为负样本（false negative）的代价为2；将实际负样本错误预测为正样本（false positive）的代价为1；样本预测正确的代价为0。则通过以下代码定义代价矩阵。cost_mat rownames(cost_mat)-colnames(cost_mat)cost_mat no yesno 0 2yes 1 0#增加代价矩阵的决策树模型 treeModel2#普通模型的预测结果 pred#增加代价矩阵模型的预测结果 pred2#普通模型预测结果的混淆矩阵 table(Actual=churnTrain$churn,+Prediction=pred)PredictionActual yes no yes 365 118 no 18 2832#普通模型的查全率 paste0(round(sum(pred=yes)*100/sum(churnTrain$churn=yes),2),%)1 79.3%#增加代价矩阵模型预测结果的混淆矩阵 table(Actual=churnTrain$churn,+Prediction=pred2)PredictionActual yes no yes 379 104 no 24 2826#增加代价矩阵模型的查全率 paste0(round(sum(pred2=yes)*100/sum(churnTrain$churn=yes),2),%)1 83.44%PAGE19CAR T 案例-分类树构建及预测19R 语言数据分析与挖掘（微课版）为了理解CART算法构建的分类树，以下代码对鸢尾花数据iris做决策树分类、打印结果，并用rpart.plot()函数绘制的决策树 library(rpart)library(rpart.plot)tree_clf tree_clfn=150 node),split,n,loss,yval,(yprob)*denotes terminal node1)root 150 100 setosa(0.33333333 0.33333333 0.33333333)2)Petal.Length=2.45 100 50 versicolor(0.00000000 0.50000000 0.50000000)6)Petal.Width=1.75 46 1 virginica(0.00000000 0.02173913 0.97826087)*rpart.plot(tree_clf,extra=3,digits=4)predict(tree_clf,newdata=data.frame(Petal.Length=5,+Petal.Width=1.5),+type=class)1 versicolor Levels:setosa versicolor virginica predict(tree_clf,newdata=data.frame(Petal.Length=5,+Petal.Width=1.5)setosa versicolor virginica1 0 0.9074074 0.09259259PAGE20CAR T 案例-回归树构建及预测20R 语言数据分析与挖掘（微课版）下面通过一个简单的医疗保费数据集来描述用作回归的决策树的原理。数据集中一共有1338个观测值和7个变量，将连续变量charges作为因变量来考虑回归问题。以下代码将数据集分成训练集和测试集，利用训练集构建回归决策树，并绘制回归决策树 insurance insurance$children train test tree_reg tree_regn=1000 node),split,n,deviance,yval*denotes terminal node1)root 1000 143518700000 13075.760 2)smoker=no 804 29251870000 8435.581 4)age=42.5 364 9867831000 12411.480*3)smoker=yes 196 25944900000 32109.940 6)bmi=30.1 102 2963050000 41926.490*rpart.plot(tree_reg,type=4,extra=1,digits=4)PAGE21CAR T 案例-决策树剪枝21R 语言数据分析与挖掘（微课版）决策树对训练样本有很好的预测能力，但是对于未知的新样本未必有很好的预测能力，泛化能力弱，即可能发生过拟合现象。为了防止过拟合，我们需要进行剪枝。决策树的剪枝通常有两种方法，一种是预剪枝（也叫先剪枝、前剪枝），另一种是后剪枝。预剪枝的一般方法有以下几种。（1）限制树生长的最大深度，即决策树的层数。如果决策树的层次已经达到指定深度，则停止生长。（2）限制决策树中间节点或叶节点中所包含的最小样本量以及限制决策树生成的最多叶节点数量。后剪枝的一般方法有以下几种。（1）计算节点中因变量预测精度或误差。这种方法将原始数据分为两部分，一部分用于生成决策树，一部分用于验证。首先使树充分生长，在剪枝过程中，不断计算当前决策树对测试样本的预测精度或误差，若某节点展开后验证数据的误差大于不展开的情况，则将该节点作为叶节点，从而达到剪枝的目的。这种方法是C4.5算法中的剪枝思想。（2）综合考虑误差与复杂度进行剪枝。考虑到虽然决策树对训练样本有很好的预测精度，但在测试样本和未来新样本上仍不会有令人满意的预测效果，因此决策树剪枝的目的是得到一颗“恰当”的树。决策树首先要具有一定的预测精度，其次决策树的复杂程度应该也是恰当的。这种是CART算法的剪枝思想。PAGE22CAR T 案例-后剪枝案例22R 语言数据分析与挖掘（微课版）我们让树自由生长，然后调用printcp()函数输出树模型的复杂性信息，并使用plotcp()函数绘制成本复杂性参数。tree_clf1 printcp(tree_clf1)#查看复杂性信息Classification tree:rpart(formula=RainTomorrow.,data=weather,c(input,output)Variables actually used in tree construction:1 Humidity3pm MaxTemp Pressure3pm Sunshine WindGustDir WindGustSpeedRoot node error:66/366=0.18033n=366 CP nsplit rel error xerror xstd1 0.196970 0 1.00000 1.00000 0.111442 0.090909 1 0.80303 0.95455 0.109423 0.037879 2 0.71212 0.93939 0.108734 0.030303 4 0.63636 0.96970 0.110115 0.010000 7 0.54545 1.04545 0.11338 plotcp(tree_clf1)#绘制CP表的信息图PAGE23CAR T 案例-后剪枝案例23R 语言数据分析与挖掘（微课版）可以利用prune()函数实现最小代价复杂度剪枝法。以下代码实现通过后剪枝得到最优的决策树。#对决策树进行剪枝 tree_clf1_pru tree_clf1_prun=366 node),split,n,loss,yval,(yprob)*denotes terminal node1)root 366 66 No(0.8196721 0.1803279)2)Humidity3pm 71.5 339 46 No(0.8643068 0.1356932)4)WindGustSpeed=64 18 6 Yes(0.3333333 0.6666667)*3)Humidity3pm=71.5 27 7 Yes(0.2592593 0.7407407)*PAGE24条件推理决策树案例24R 语言数据分析与挖掘（微课版）除了传统决策树（rpart）算法，条件推理决策树（ctree）是另外一类比较常用的基于树的分类算法。条件推理决策树算法的分裂方式不再以自变量分裂后因变量的纯度（如C5.0和CART算法）为分裂度量指标，而是以自变量与目标变量的相关性（一些统计检验的显著性测量）为分裂度量指标。if(!require(party)install.packages(party)#加载party包 tree_ctree tree_ctree#查看模型树 Conditional inference tree with 4 terminal nodesResponse:RainTomorrow Inputs:MinTemp,MaxTemp,Rainfall,Evaporation,Sunshine,WindGustDir,WindGustSpeed,WindDir9am,WindDir3pm,WindSpeed9am,WindSpeed3pm,Humidity9am,Humidity3pm,Pressure9am,Pressure3pm,Cloud9am,Cloud3pm,Temp9am,Temp3pm,RainToday Number of observations:366 1)Cloud3pm=6;criterion=1,statistic=54.954 2)Pressure3pm 1011.8 4)*weights=210 1)Cloud3pm 6 5)Humidity3pm 73 7)*weights=21 plot(tree_ctree)#绘制决策树PAGE25绘制决策边界25R 语言数据分析与挖掘（微课版）决策树采用非常直观的方式对事物进行预测。二叉树分支方法可以非常有效地进行预测，其每个节点都根据一个特征的阈值将数据分成两组，即决策树实质是通过与特征轴平行的分类边界分割数据。#编写绘制决策边界函数 visualize_classifier-function(model,X,y,xlim,ylim,type=c(n,n)+x1s-seq(xlim1,xlim2,length.out=200)+x2s-seq(ylim1,ylim2,length.out=200)+Z-expand.grid(x1s,x2s)+colnames(Z)-colnames(X)+y_pred-predict(model,Z,type=class)+y_pred-matrix(y_pred,length(x1s)+filled.contour(x1s,x2s,y_pred,+levels=1:(length(unique(y)+1),+col=RColorBrewer:brewer.pal(length(unique(y),Pastel1),+key.axes=FALSE,+plot.axes=axis(1);axis(2);+points(X,1,X,2,pch=as.numeric(y)+15,col=as.numeric(y)+1,cex=1.5);+points(c(2.45,2.45),c(0,3),type=type1,lwd=2)+points(c(2.45,7.5),c(1.75,1.75),type=type2,lwd=2,lty=2)+,+xlab=colnames(X)1,ylab=colnames(X)2+)+
