3.7 决策树算法与随机森林
3.7.1 决策树算法
1.决策树算法
决策树是机器学习领域中，用于分类的一种常用的工具，它已经被广泛应用到很多具体问题中。例如,在医疗方面，根据患者的疾病数据记录，可以用计算机直接分类患者的病症;在商场超市等零售业领域，根据消费者消费物品的记录，将消费者的可购买力进行分类，以期更好地安排物品摆放顺序和举办定期优惠等促销活动，以提高整体的营业额;在金融方面，根据用户账户上拖欠支付的信息来分类贷款申请等。对于这些分类问题，都可以通过决策树这种分类工具，把未知类别的样例分类到各个对应的类别中去。这种方法分类速度快、精度高，生成的分类规则相对简单。
2.决策树的结构
决策树是典型的树形结构，一般都是以自上而下的方式生成的。每个决策或者属性的选择都可能引出不同的事件，导致不同的分类结果，因此把这种决策分支画成图形就很像一棵倒长着的树，底端则是分类的结果。
图3-32中给出了决策树的一般结构示意图。
图3-32 决策树的一般结构
整体来看，决策树由节点和分支组成。决策树中的每一个内节点都代表一个属性，其中节点有两种:内节点和叶子节点。最顶端的内节点称为根节点(如R1)，整棵树最下端的称为叶子节点，每一个叶子节点，都代表一个分类的类别标签如L1、L2、L3和L4。其他内节点为图3-32中的R21和R22节点。每一个树形的分支，也就是树的边，代表属性值的一个判断标准，如图中的f1、f2、f3、f4、f5和f6。
用决策树进行分类，就是把所有样例从根节点按照分类标准，逐级分配到某个叶子节点的过程，叶子节点则标识了样例的最终类别。
决策树这种分类方式表达形式简洁、直观，从决策树中就可以直接看出属性的重要程度，越靠近根节点，属性重要程度越高。同时，从根节点到一个叶子节点，即是一条分类规则，统计出这些规则和数目也很简单。
3.决策树生成算法
为了描述决策树的生成过程，我们对决策树分类时用到的相关概念和数据定义给予解释。
(1)整个数据集在分类时，被分为训练集和测试集。我们用S表示全体s个样例的集合。
(2)样例的条件属性和类别属性：数据集中表示样例类别的决策属性个数为k个，分别为C={C1，C2，…，Ck}，用于将样例进行分类的条件属性个数为j个，分别为A1,A2,…，Aj。
我们可以用一个简单的示意图表示用决策树对数据集进行分类的过程，如图3-33所示。首先用训练数据集构造一棵决策树；对于每一个测试样例ti∈S，用构造好的决策树来确定它的类别。
图3-33 决策树的分类过程
3.7.2 ID3算法
1.ID3详述
著名的ID3算法是由昆兰(Quinlan)在1986年提出的。这个算法以信息熵和信息增益作为属性选取的标准，这个标准的使用使每一个非叶子节点在进行属性选择时，都能够选择得到能获得最大数据类别信息的属性。
具体做法是:首先验证所有的属性，选择信息增益最大的属性作为决策树的根节点，由该属性的不同取值进行分支，产生下级子树的根节点。然后对子树的各分支使用同样的属性选择标准，生成其下一级的子树，直到生成的节点上只包含同一类别的数据记录为止。当算法结束后即可得到一棵决策树，对新来的无类别标签的样本就可以进行分类操作了。
通过计算每个属性的信息增益，并比较它们的大小，就能获得当前数据集中具有最大信息增益的属性。ID3算法的原理如下。
设S=E1×E2×E3×…×En是n维的有穷向量空间，其中Ej是有穷的离散符号集，S中的元素e=〈d1,d2,d3,…,dn〉称为样例，其中dj∈Ej,j=1,2,3,…，n，即E1,E2,E3,…,En是整个数据集的属性集合，d1,d2,d3,…,dn是相应属性下的具体属性值。
通常数据集中有两个相对的样例子集，一个正例集合和一个反例集合。假设向量空间S中正例集合和反例集合中样例的大小分别为p和n，则ID3算法基于一种常见的假设:在向量空间S中，一颗决策树对正例和反例的判断概率相同。
ID3算法确定决策树对一个样例做出正确判断所需的信息量为
(3-70)
对于多类问题，信息熵则为
(3-71)
pi表示第i类样例在整个样例集中所占的比例。
如果以属性Q作为选取的属性，成为当选的节点，Q具有m个值{M1，M2，M3，…，Mm}，这些属性的取值将数据集S分为i个子集{S1，S2，S3，…，Si}。假设Si中含有pi个正例和ni个反例，那么子集Si中所需的期望信息是I(pi,ni)，属性Q作为当前所选节点的期望熵就为
(3-72)
那么Q作为所选节点的信息增益就为
gain(Q)=I(p,n)-E(Q)
(3-73)
ID3算法在对每个节点进行选择时，都会选择信息增益gain(Q)最大的属性。在以后生成节点时递归调用上述过程就可以生成所有的节点。直到在一个节点上，样例的类别一致，选择属性结束。此时的节点就是叶子节点。
ID3算法的优点是理论清晰并且简单，对比较小的数据集效果不错。当数据集很大时，决策树规模可能非常大，并且对噪声比较敏感，可能影响分类的准确性。
2.ID3算法在MATLAB中的应用
本节利用基于决策树理论的分类方法对酒瓶进行分类识别，其实现步骤如下。
(1)构建训练样本集：从酒瓶样本库中的各类中分别提取29个训练样本，共59个样本。每个酒瓶样本只有3个特征，分别代表red、blue、green 3个颜色隶属度，酒瓶类别为训练类别，为1、2、3、4共4类。
(2)构建分类决策树：本文采用MATLAB中的决策树工具箱函数进行分类决策树的构建。构建分类决策树函数的基本定义为T =treefit(X，y)。
其中参数X为训练样本属性集合，对应酒瓶三原色数据训练集为X的矩阵，矩阵每一行为一个训练样本，每列对应一个属性。参数y为类别集合，对于酒瓶三原色数据训练集:y为29维的向量，每一维对应一个训练样本的类别，一共有4类，返回值T是一个决策树结构，保存了已建好的分类决策树的信息。
(3)利用决策树分类：输入待测样本，利用MATLAB中的决策树工具箱函数进行决策树分类。决策树分类函数的基本定义为：YFIT = treeval (T，Z)。
其中，参数T为步骤(2)中已构建的决策树结构，Z为待测样本特征矩阵，可以表示多个待测样本。YFIT为分类结果向量，保存每个待测样本的分类结果。
(4)显示决策树：为了更清楚地检验决策树分类，将决策树显示出来，可以更加直观地理解决策树理论，MALLAB中决策树工具箱提供了显示决策树功能。
显示决策树函数为treedisp(T)，参数T为已构建的决策树结构。
程序如下所示：
程序输出结果：
决策树结构如图3-34所示。
决策树分类结果3D图像化显示如图3-35所示。
图3-34 决策树结构图
图3-35 决策树分类结果3D图像化显示
显示原始分类结果：
应用以上程序进行决策树分类的正确率为0.9333。
由此可见，对于简单的数据，使用ID3算法能够较为有效地分类，但是还有进一步提升的空间。算法还可以进一步优化使分类的准确性提高。
3.7.3 随机森林算法
随机森林是一种比较新的机器学习模型。经典的机器学习模型是神经网络，神经网络模型的应用已有半个多世纪的历史了。神经网络预测精确，但是计算量很大。随机森林在运算量没有显著提高的前提下提高了预测精度。随机森林对多元共线性不敏感，结果对缺失数据和非平衡的数据比较稳健，可以很好地预测多达几千个解释变量的作用，被誉为当前最好的算法之一。
随机森林是由一棵棵决策树组成的，属于一种包含多个决策树的分类器。这些决策树中，每一棵决策树都是由一些随机选择的属性(一个或确定的数目)组合，通过决策树生成算法构造成的，这些决策树就组成了随机森林。而随机森林的输出类别是由个别树输出的类别的众数而定的。
1.随机森林算法
可以根据下列算法建造每棵树：
(1)用 N 来表示训练例子的个数，M表示变量的数目。
(2)我们会被告知一个数 m，被用来决定当在一个节点上做决定时，会使用到多少个变量,m应小于M。
(3)从N个训练例子中以可重复取样的方式，取样N次，形成一组训练集(即bootstrap取样)。并使用这棵树来对剩余例子预测类别，并评估其误差。
(4)对于每一个节点，随机选择m个基于此点的变量。根据这 m 个变量，计算最佳的分割方式。
(5)每棵树都会完整成长而不会剪枝(Pruning)(有可能在建完一棵正常树状分类器后被采用)。
2.随机森林算法的优缺点
随机森林的优点有：
对于很多种资料，它可以产生高准确度的分类器。
它可以处理大量的输入变量。
它可以在决定类别时，评估变量的重要性。
在建造森林时，它可以在内部对一般化后的误差产生不偏差的估计。
它包含一个好方法，可以估计遗失的资料，并且如果有很大一部分资料遗失，那么也可以维持准确度。
它提供一个实验方法，可以去侦测 variable interactions。
对不平衡的分类资料集来说，它可以平衡误差。
它计算各例子的亲近度，对数据挖掘、侦测偏离者(Outlier)和将资料视觉化非常有用。
它可被延伸应用在未标记的资料上，这类资料通常使用非监督式聚类，也可侦测偏离者和观看资料。
学习过程是很快速的。
随机森林算法的缺点有：
随机森林已经被证明在某些噪声较大的分类或回归问题上会过拟合。
对于有不同级别属性的数据，级别划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。
3.随机森林应用——酒瓶分类三原色数据
(1)设计思路：将酒瓶的3个量化特征作为网络输入，将酒瓶分类结果作为网络输出。用训练数据对设计的随机森林网络进行训练，然后对测试数据进行测试并对测试结果进行分析。
(2)设计步骤：根据上述设计思路，设计步骤主要包括以下几个方面，如图3-36所示。
图3-36 设计步骤
采集数据：本方案采用酒瓶分类三原色数据。
网络创建：数据输入后，利用MATLAB自带的神经网络工具箱函数TreeBagger创建随机森林神经网络。
网络训练：网络创建完毕后，将训练集的酒瓶分类三原色数据输入网络，便可以对网络进行训练。
网络仿真：网络通过训练后，将测试集中的数据输入网络，便可以得到对应的输出(即分类)。
结果分析：通过对网络仿真结果的分析，对该方法的可行性进行评价。
(3)MATLAB程序实现：
寻找最佳叶片尺寸：对于回归树模型，一般的规则是设置叶的大小为5，并选择1/3的袋外样本。在接下来的步骤中，通过比较各种叶片尺寸的回归得到的平均平方误差来验证最佳叶片尺寸，袋外数据计算均方误差与生长树的数量程序如下。
均方误差对比曲线如图3-37所示。
图3-37 均方误差对比曲线
总结
随机森林网络分类结果如表3-4所示。
表3-4 随机森林网络分类结果
由以上结果可知，随着森林中树木的增加，分类准确率能够得到较大的提升，当森林中树木足够多时，如案例中的20棵树时，随机森林算法袋外数据均方误差趋于平缓，分类准确率最高。
思考与练习
(1)什么是判别函数法？
(2)怎样确定线性判别函数的系数？
(3)线性判别函数的分类器设计方法有哪些？非线性判别函数的分类器设计方法有哪些？它们有什么异同？