机器学习与应用

作者简介

弗兰克·帕特诺伊（Frank Partnoy），耶鲁大学法学学士。曾从事过投资银行衍生产品经纪、公司和证券律师等多种职业，1997年后任圣迭戈大学法学院教授，是证券市场监管和金融衍生产品方面的专家，曾在安然公司破产后作为专家证人在美国参议院立法委员会作证。

内容简介

第5章 决策树决策树是一种基于规则的方法,它用一组嵌套的规则进行预测。在树的每个决策节点处,根据判断结果进入一个分支,反复执行这种操作直到到达叶子节点,得到预测结果。这些规则是通过训练得到的,而不是人工制定的。 5.1树形决策过程 首先看一个简单的例子。银行要确定是否给客户发放贷款,为此需要考察客户的收入与房产情况。在做决策之前,会先获取客户的这两个数据。如果把这个决策看作分类问题,两个指标就是特征向量的两个分量,分类的类别标签是可以贷款和不能贷款。银行按照下面的过程进行决策。 (1) 首先判断客户的年收入指标。如果大于20万元,可以贷款;否则继续判断。 (2) 然后判断客户是否有房产。如果有房产,可以贷款;否则不能贷款。 用图形表示这个过程就是一棵决策树。决策过程从树的根节点开始,在内部节点处需要做判断,直到到达一个叶子节点处,得到决策结果。决策树由一系列分层嵌套的判定规则组成,是一个递归的结构。这个例子的决策树如图5.1所示。 图5.1决策树的一个例子 收入为数值型特征,可以比较大小,这种特征为整数或小数。房产情况为类别型特征,取值为有房产或没有房产两种情况,这种特征不能比较大小。图5.1中决策树所有的内部节点为矩形,叶子节点即决策结果为椭圆形。 为便于用程序实现,一般将决策树设计成二叉树。与树的叶子节点、非叶子节点相对应,决策树的节点分为两种类型。 (1) 决策节点。在这些节点处需要进行判断以决定进入哪个分支,如用一个特征和设定的阈值进行比较。决策节点一定有两个子节点,它是非叶子节点。 (2) 叶子节点。表示最终的决策结果,它们没有子节点。在上面的例子中,叶子节点的值有两种,即可以贷款和不能贷款。对于分类问题,叶子节点中存储的是类别标签。 决策树是一个分层结构,可以为每个节点赋予一个层次数。根节点的层次数为0,子节点的层次数为父节点层次数加1。树的深度定义为所有节点的最大层次数。图5.1决策树的深度为2,要得到一个决策结果最多经过两次判定。 典型的决策树有ID3［1］、C4.5［3］、CART(Classification And Regression Tree,分类与回归树)［4］等,它们的区别在于树的结构与构造算法。分类与回归树既支持分类问题,也可用于回归问题。决策树是一种判别模型,天然支持多类分类问题。限于篇幅,本章只介绍分类与回归树。 〖1〗〖2〗机器学习与应用〖1〗第5章决策树分类树的映射函数是多维空间的分段线性划分,即用平行于各坐标轴的超平面对空间进行切分;回归树的映射函数是分段常数函数。决策树是分段线性函数而不是线性函数,它具有非线性建模的能力。只要划分得足够细,分段常数函数可以逼近闭区间上任意函数到任意指定精度,因此，决策树在理论上可以对任意复杂度的数据进行拟合。对于分类问题,如果决策树深度够大,它可以将训练样本集的所有样本正确分类。但如果特征向量维数过高,可能会面临维数灾难导致准确率下降,维数灾难的概念在第14章介绍。 图5.2是决策树对空间划分的一个例子。这里有红色和蓝色两类训练样本,用下面两条平行于坐标轴的直线可以将这两类样本分开。 这个划分方案对应的决策树如图5.3所示。 图5.2决策树对空间的划分 图5.3决策树 5.2分类与回归树 下面介绍分类与回归树的原理,它们是二叉决策树。预测时从根节点开始,每次只对一个特征进行判定，然后进入左子节点或者右子节点,直至到达一个叶子节点处,得到类别值或回归函数值。预测算法的时间复杂度与树的深度有关,判定的执行次数不超过决策树的深度。 5.3训练算法 现在要解决的关键问题是如何用训练样本建立决策树。无论是分类问题还是回归问题,决策树都要尽可能地对训练样本进行正确的预测。直观的想法是从根节点开始构造,递归地用训练样本集建立起决策树,这棵树能够将训练集正确分类,或者对训练集的回归误差最小化。为此要解决以下问题。 特征向量有多个分量,每个决策节点上应该选择哪个分量做判定？这个判定会将训练样本集一分为二,然后用这两个子集构造左右子树。 选定一个特征后,判定的规则是什么？也就是说，满足什么条件时进入左子树分支。对数值型变量要寻找一个分裂阈值进行判断,小于该阈值进入左子树,否则进入右子树。对于类别型变量则需要为它确定一个子集划分,将特征的取值集合划分成两个不相交的子集,如果特征的值属于第一个子集则进入左子树,否则进入右子树。 何时停止分裂,把节点设置为叶子节点？对于分类问题,当节点的样本都属于同一类型时停止,但这样可能会导致树的节点过多、深度过大,产生过拟合问题。另一种方法是当节点中的样本数小于一个阈值时停止分裂。 如何为每个叶节点赋予类别标签或者回归值？也就是说，到达叶子节点时样本被分为哪一类或者赋予一个什么实数值。 下面给出这几个问题的答案。特征有数值型变量和类别型变量两种情况,决策树有分类树和回归树两种类型,组合起来一共有4种情况。限于篇幅,只对数值型变量进行介绍。 5.3.1递归分裂过程 训练算法是一个递归的过程。首先创建根节点,然后递归地建立左子树和右子树。如果练样本集为D,训练算法的整体流程如下。 (1) 用样本集D建立根节点,找到一个判定规则,将样本集分裂成D1和D2两部分,同时为根节点设置判定规则。 (2) 用样本集D1递归建立左子树。 (3) 用样本集D2递归建立右子树。 (4) 如果不能再进行分裂,则把节点标记为叶子节点,同时为它赋值。 在确定这个递归流程之后,接下来要解决的核心问题是怎样对训练样本集进行分裂。 5.3.2寻找最佳分裂 训练时需要找到一个分裂规则把训练样本集分裂成两个子集,因此，要确定分裂的评价标准,根据它寻找最佳分裂。对于分类问题,要保证分裂之后左右子树的样本尽可能纯,即它们的样本尽可能属于不相交的某一类或者几类。为此需要定义不纯度的指标: 当样本都属于某一类时不纯度为0;当样本均匀地属于所有类时不纯度最大。满足这个条件的有熵不纯度、Gini不纯度,以及误分类不纯度等,下面分别进行介绍。 不纯度指标用样本集中每类样本出现的概率值构造。因此，首先要计算每个类出现的概率,这通过训练样本集中每类样本数除以样本总数得到 pi=NiN其中，Ni是第i类样本数;N为总样本数。根据这个概率值可以定义各种不纯度指标,下面分别介绍。 样本集D的熵不纯度定义为E(D)=-∑ipilog2pi熵是信息论中的一个重要概念,用来度量一组数据包含的信息量大小。当样本只属于某一类时熵最小,当样本均匀地分布于所有类中时熵最大。因此,如果能找到一个分裂让熵最小,这就是我们想要的最佳分裂。 样本集的Gini不纯度定义为G(D)=1-∑ip2i当样本属于某一类时Gini不纯度的值最小,此时最小值为0;当样本均匀地分布于每一类时Gini不纯度的值最大。这源自于如下数学结论,在下面的约束条件下:∑ipi=1 pi≥0对于如下目标函数: ∑ip2i所有变量相等时它有极小值,只有一个变量为1其他变量为0时该函数有极大值,这对应于Gini不纯度的极小值，即所有样本都来自同一类时Gini不纯度的值最小,样本均匀地属于每一类时Gini不纯度的值最大。将类概率的计算公式代入Gini不纯度的定义,可以得到简化的计算公式: G(D)=1-∑ip2i=1-∑iNiN2=1-∑iN2iN2样本集的误分类不纯度定义为E(D)=1-max(pi)之所以这样定义是因为人们会把样本判定为频率最大的那一类,因此，其他样本都会被错分,故错误分类率为上面的值。和上面的两个指标一样,当样本只属于某一类时误分类不纯度有最小值0,样本均匀地属于每一类时该值最大。 上面定义的是样本集的不纯度,我们需要评价的是分裂的好坏,因此，需要根据样本集的不纯度构造出分裂的不纯度。分裂规则将节点的训练样本集分裂成左右两个子集,分裂的目标是把数据分成两部分之后这两个子集都尽可能纯。因此，我们计算左右子集的不纯度之和作为分裂的不纯度,显然求和需要加上权重,以反映左右两边的训练样本数。由此得到分裂的不纯度计算公式为G=NLNG(DL)+NRNG(DR)其中，G(DL)是左子集的不纯度;G(DR)是右子集的不纯度;N是总样本数;NL是左子集的样本数;NR是右子集的样本数。 如果采用Gini不纯度指标,将Gini不纯度的计算公式代入上式可以得到 G=NLN1-∑iN2L,iN2L+NRN1-∑iN2R,iN2R =1NNL-∑iN2L,iNL+NR-∑iN2R,iNR =1-1N∑iN2L,iNL+∑iN2R,iNR其中，NL,i是左子节点中第i类样本数;NR,i是右子节点中第i类样本数。由于N是常数,要让Gini不纯度最小化等价于让下面的值最大化: G=∑iN2L,iNL+∑iN2R,iNR这个值可以看作Gini纯度,它的值越大,样本越纯。寻找最佳分裂时需要计算用每个阈值对样本集进行分裂后的这个值,寻找该值最大时对应的分裂,它就是最佳分裂。如果是数值型特征,对于每个特征将l个训练样本按照该特征的值从小到大排序,假设排序后的值为x1,x2,…,xl接下来从x1开始,依次用每个xi作为阈值,将样本分成左右两部分,计算上面的纯度值,该值最大的那个分裂阈值就是此特征的最佳分裂阈值。在计算出每个特征的最佳分裂阈值和上面的纯度值后,比较所有这些分裂的纯度值大小,该值最大的分裂为所有特征的最佳分裂。这里采用贪心法的策略,每次都是选择当前条件下最好的分裂作为当前节点的分裂。对单个变量寻找最佳分裂阈值的过程如图5.4所示。 图5.4为数值型变量寻找最佳分裂阈值 对于回归树,衡量分裂的标准是回归误差（即样本方差）,每次分裂时选用使得方差最小化的那个分裂。假设节点的训练样本集有l个样本(xi,yi),其中，xi为特征向量,yi为实数的标签值。节点的回归值为所有样本的均值,回归误差为所有样本的标签值与回归值的均方和误差,定义为E(D)=1l∑li=1(yi-)2把均值的定义带入上式,得到 E(D)=1l∑li=1yi-1l∑lj=1yj2 =1l∑li=1y2i-2yi1l∑lj=1yj+1l2∑lj=1yj2 =1l∑li=1y2i-2l∑li=1yi2+1l∑lj=1yj2 =1l∑li=1y2i-1l∑lj=1yj2根据样本集的回归误差,我们同样可以构造出分裂的回归误差。分裂的目标是最大程度地减小回归误差,因此，把分裂的误差指标定义为分裂之前的回归误差减去分裂之后左右子树的回归误差: E=E(D)-NLNE(DL)-NRNE(DR)将误差的计算公式代入上式,可以得到 E=1N∑Ni=1y2i-1N∑Ni=1yi2-NLN1NL∑NLi=1y2i-1NL∑NLi=1yi2- NRN1NR∑NRi=1y2i-1NR∑NRi=1yi2 =-1N2∑Ni=1yi2+1N1NL∑NLi=1yi2+1NR∑NRi=1yi2由于N和-1N2∑Ni=1yi2是常数,要让上式最大化等价于让下式最大化: E=1NL∑NLi=1yi2+1NR∑NRi=1yi2寻找最佳分裂时要计算上面的值,让该值最大化的分裂就是最佳分裂。回归树对类别型特征的处理和分类树类似,只是E值的计算公式不同,其他的过程相同。 5.3.3叶子节点值的设定 如果不能继续分裂,则将该节点设置为叶子节点。对于分类树,将叶子节点的值设置成本节点的训练样本集中出现概率最大的那个类;对于回归树,则设置为本节点训练样本标签值的均值。 5.3.4属性缺失问题 在某些情况下样本特征向量中一些分量没有值,这称为属性缺失。例如，晚上我们无法观察到物体的颜色值,颜色属性就缺失了。在决策树的训练过程中,寻找最佳分裂时如果某一个属性上有些样本有属性缺失,可以把这些缺失该属性的样本剔除掉,然后照常训练,这是最简单的做法。 此外，还可以使用替代分裂规则。对于每个决策树节点除了计算出一个最佳分裂规则作为主分裂规则,还会生成一个或者多个替代分裂规则作为备选。在预测时如果主分裂规则对应的特征出现缺失,则使用替代分裂规则进行判定。需要注意的是,替代分裂对于分类问题和回归问题是做相同的处理。 现在的关键问题是怎样生成替代分裂规则。主分裂和替代分裂对所有样本的分裂结果有4种情况,分别为 LL,LR,RL,RR LL表示被主分裂、替代分裂都分到了左子树的样本数;LR表示被主分裂分到了左子树,被替代分裂分到了右子树的样本数;RL表示被主分裂分到了右子树,被替代分裂分到了左子树的样本数;RR表示被主分裂和替代分裂都分到了右子树的样本数。 LL+RR是被替代分裂正确分类的样本数,LR+RL是被替代分裂错分的样本数。由于可以将左右子树反过来,因此，给定一个特征分量,在寻找替代分裂的分裂阈值时要让LL+RR或者LR+RL最大化,最后取它们的最大值: max (LL+RR,LR+RL) 该值对应的分裂阈值为替代分裂的分裂阈值。对于除最佳分裂所用特征之外的其他所有特征,都找出该特征的最佳分裂和上面的值。最后取该值最大的那个特征和分裂阈值作为替代分裂规则。 5.3.5剪枝算法 如果决策树的结构过于复杂,可能会导致过拟合问题。此时需要对树进行剪枝,消掉某些节点让它变得更简单。剪枝的关键问题是确定剪掉哪些树节点以及剪掉它们之后如何进行节点合并。决策树的剪枝算法可以分为两类,分别称为预剪枝和后剪枝。前者在树的训练过程中通过停止分裂对树的规模进行限制;后者先构造出一棵完整的树,然后通过某种规则消除掉部分节点,用叶子节点替代。 预剪枝可以通过限定树的高度、节点的训练样本数、分裂所带来的纯度提升的最小值来来实现,具体做法在前面已经讲述,在源代码分析中会介绍实现细节。后剪枝的典型实现有降低错误剪枝(ReducedError Pruning,REP)、悲观错误剪枝(PesimisticError Pruning,PEP)、代价复杂度剪枝(CostComplexity Pruning,CCP)［5］等方案。分类与回归树采用的是代价复杂度剪枝算法,下面重点介绍它的原理。 代价是指剪枝后导致的错误率的变化值,复杂度是指决策树的规模。训练出一棵决策树之后,剪枝算法首先计算该决策树每个非叶子节点的α值,它是代价与复杂度的比值。该值定义为α=E(n)-E(nt)|nt|-1其中，E(n)是节点n的错误率,E(nt)是以节点n为根的子树的错误率。|nt|为子树的叶子节点数,即复杂度。α值是用树的复杂度归一化之后的错误率增加值,即将整个子树剪掉之后用一个叶子节点替代,相对于原来的子树错误率的增加值。该值越小,剪枝之后树的分类效果和剪枝之前越接近。上面的定义依赖于节点的错误率指标,下面对分类问题和回归问题介绍它的计算公式。对于分类问题,错误率定义为E(n)=N-max(Ni)N其中，N是节点的总样本数;Ni是第i类样本数,这就是之前定义的误分类指标。对于回归问题,错误率为节点样本集的均方误差: E(n)=1N∑i(y2i)-1N∑iyi2子树的错误率为树的所有叶子节点错误率之和。计算出α值之后,剪掉该值最小的节点得到剪枝后的树,然后重复这种操作直到剩下根节点,由此得到一个决策树序列: T0,T1,…,Tm其中，T0是初始训练得到的决策树;Ti+1是在Ti的基础上剪枝得到的,即剪掉Ti中α值最小的那个节点为根的子树并用一个叶子节点替代后得到的树。 整个剪枝算法分为两步完成。 第一步先训练出T0,然后用上面的方法逐步剪掉树的所有非叶子节点,直到只剩下根节点得到剪枝后的树序列。这一步的误差计算采用的是训练样本集。 第二步根据真实误差值从上面的树序列中挑选出一棵树作为剪枝后的结果。这可以通过交叉验证实现,用交叉验证的测试集对上一步得到的树序列的每一棵树进行测试,得到这些树的错误率,然后根据错误率选择最佳的树作为剪枝后的结果。 5.4实验程序 下面通过实验程序介绍决策树的使用,程序使用OpenCV的决策树类。与贝叶斯分类器的实验程序一样,这里也有3类样本,每类样本的特征向量用正态分布随机数生成。训练得到决策树模型之后,用它对图像内的所有点进行预测,根据预测分类结果将像素显示成不同颜色。 程序源代码如下: int main(int argc, char argv) { const int kWidth = 512, kHeight = 512;// 显示分类结果图像的宽度和高度 Vec3b red(0, 0, 255), green(0, 255, 0), blue(255, 0, 0);// 显示分类结果的3种颜色 Mat image = Mat::zeros(kHeight, kWidth, CV_8UC3); // 为3类训练样本标签赋值 int labels\\\\\\\\[30\\\\\\\\]; for (int i= 0 ; i < 10; i++) labels\\\\\\\\[i\\\\\\\\] = 1; for (int i = 10; i < 20; i++) labels\\\\\\\\[i\\\\\\\\] = 2; for (int i = 20; i < 30; i++) labels\\\\\\\\[i\\\\\\\\] = 3; Mat trainResponse(30, 1, CV_32SC1, labels); // 用随机数生成训练样本特征向量数组 float trainDataArray\\\\\\\\[30\\\\\\\\]\\\\\\\\[2\\\\\\\\]; RNG rng; for (int i = 0; i < 10; i++) { trainDataArray\\\\\\\\[i\\\\\\\\]\\\\\\\\[0\\\\\\\\] = 250 + static_cast(rng.gaussian(30)); trainDataArray\\\\\\\\[i\\\\\\\\]\\\\\\\\[1\\\\\\\\] = 250 + static_cast(rng.gaussian(30)); } for (int i = 10; i < 20; i++) { trainDataArray\\\\\\\\[i\\\\\\\\]\\\\\\\\[0\\\\\\\\] = 150 + static_cast(rng.gaussian(30)); trainDataArray\\\\\\\\[i\\\\\\\\]\\\\\\\\[1\\\\\\\\] = 150 + static_cast(rng.gaussian(30)); } for (int i = 20; i < 30; i++) { trainDataArray\\\\\\\\[i\\\\\\\\]\\\\\\\\[0\\\\\\\\] = 320 + static_cast(rng.gaussian(30)); trainDataArray\\\\\\\\[i\\\\\\\\]\\\\\\\\[1\\\\\\\\] = 150 + static_cast(rng.gaussian(30)); } Mat trainData(30, 2, CV_32FC1, trainDataArray); CvDTree dtree; // 决策树的训练参数,在后面的源代码分析中会详细讲解 CvDTreeParams params(5, 1, 0, true, 2, 0, true, true, NULL); // 训练决策树 dtree.train (trainData, CV_ROW_SAMPLE, trainResponse, cv::Mat(), cv::Mat(), cv::Mat(), cv::Mat(), params); // 对图像平面内所有点进行预测,根据分类结果显示不同的颜色 for (int i = 0; i < image.rows; i++) { for (int j = 0; j < image.cols; j++) { Mat sampleMat = (Mat_(1, 2) << j, i); // 用决策树进行预测,返回分类结果 float response = dtree.predict(sampleMat)->value; // 根据分类结果显示不同的颜色 if (response == 1) image.at(i, j) = red; else if (response == 2) image.at(i, j) = green; else image.at(i, j) = blue; } } // 用不同的亮度显示3类训练样本 for (int i = 0; i < trainData.rows; i++) { const float v = trainData.ptr(i); Point pt = Point((int)v\\\\\\\\[0\\\\\\\\], (int)v\\\\\\\\[1\\\\\\\\]); if (labels\\\\\\\\[i\\\\\\\\] == 1) circle(image, pt, 5, Scalar::all(0), -1, 8); else if (labels\\\\\\\\[i\\\\\\\\] == 2) circle(image, pt, 5, Scalar::all(128), -1, 8); else circle(image, pt, 5, Scalar::all(255), -1, 8); } imshow(\\\\\\\"Decision tree classifier demo\\\\\\\", image); waitKey(0); return 0; }程序的运行结果如图5.5所示。 图5.5决策树的分类结果 图5.5中3类训练样本都被正确分类,它们的分类决策线为直线,这也证明决策树是分段线性函数。 5.5源代码分析 下面分析OpenCV中决策树的实现。它实现了分类与回归树的完整功能,支持数值型变量和类别型变量,可以处理属性缺失问题,支持输出变量的重要性,还实现了CCP剪枝算法。 5.5.1主要数据结构 结构体CvDTreeSplit为决策树节点的分裂规则,即判定规则。预测时使用该规则进行判定,训练时它将训练样本集划分成两个不相交的子集,训练算法要为每个节点计算出该规则。结构体的定义如下: struct CvDTreeSplit { int var_idx;// 分裂所使用的特征分量的编号 int condensed_idx; int inversed;// 分支方向,左右子树是否交换方向 1. 内容全面深入。全书系统地讲解机器学习算法与理论，主要算法的理论讲解透彻、结构清晰，均有详细的推导和证明过程。 2. 内容新。对于深度学习等重点算法，涵盖和反映了截至2017年学术界与工业界的新成果，确保本书的内容能够紧跟当前的学术和技术趋势。 3. 理论与实践相结合。对于所有重点算法，除深入讲解算法的原理之外，还介绍了算法的工程实现细节，对各种算法的实际应用也进行了介绍。 4. 对机器学习所需的数学知识进行全面系统的介绍，确保读者无须单独再看其他数学教材也能顺利学习。