决策树学习笔记（二）
决策树学习笔记(二)
接着上一篇
接着上一篇笔记决策树学习笔记(一)继续学习，上一篇主要是对决策模型的初步认识和理解以及特征选择的一些规则；接下去就是决策树算法的具体实现和优化，包括决策树生成、剪枝以及分类与回归树(CART)详解。分类与回归树模型还会在后续的提高树学习中结合使用。web
作学习笔记确实是一件比较耗时的事情(已经快被实验室项目榨干精力，期盼周末TT)，仅剩的空闲时间勉强够我对最近的学习内容作些整理；看完一遍后书本知识再作整理的过程当中确实能加深对算法的理解，把算法原理步骤再表达一遍才能发现哪些地方本身并非很清楚，而后思考、搜索、解答。算法
5.决策树生成
决策树学习的生成算法主要有ID3算法和C4.5算法，其实它们的生成过程是相似的，前者用信息增益准则选择特征，后者则是增强版—信息增益比。(关于信息增益比的好处上一篇笔记中已经介绍)机器学习
ID3算法：在决策树的各个结点上采用信息增益准则选择特征，递归构建决策树。svg
具体实现：从根结点开始，对当前结点计算全部特征的信息增益，选择信息增益最大的特征做为当前结点特征，而后根据该特征的不一样取值构建子结点；接着对新生成带我子结点递归执行以上步骤，直到全部特征的信息增益都很小或者没有特征可选(分类完毕)为止。函数
书上说：ID3至关于用极大似然法进行几率模型的选择。—这里理解起来须要统计学知识，似懂非懂…工具
极大似然法是属于数理统计范畴，旨在由果溯因。好比扔一枚骰子(骰子每一个面上只标记1或2)，如今告诉你扔了n次骰子其中有k次朝上的是1；而后问你这个骰子标记为1的面所占的比例w是多少?极大似然法的思想就是估计当w取值为多少的时候，k次朝上的可能性最大。具体计算方法就是对表达式求最大值，获得参数值估计值：学习
通常就是对这个表达式求一阶导=0(二阶导<0)；测试
这就是极大似然估计方法的原理：用使几率达到最大的那个w来估计位置参数w。回到ID3，决策树生成的过程能够理解成对决策树模型的参数估计(就是基于特征空间划分的类的几率模型),根据训练数据的特征分布，选择使得模型最契合当前样本分布空间时的条件几率模型。优化
算法步骤：.net
算法案例(表数据见上一笔记)：
注：ID3算法至考虑了树的生成，即尽量的是模型拟合当前训练数据集，因此该算法生成的树容易过拟合。
C4.5生成算法:C4.5算法用信息增益比来选择特征，算法过程与ID3算法相似，故很少作阐述。
算法步骤：
6.决策树的剪枝
上一篇将决策树学习的时候就提到决策树生成算法会对当前数据集拟合，但对未知数据的分类预测并无那么准确，即过拟合现象。解决这个问题的办法就是适当的减小树的复杂度，在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。
具体地：剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点做为新的叶结点，从而简化分类模型。
剪枝每每经过极小化损失函数来实现，决策树学习的损失函数Ca(T)：
|T|为树T叶结点个数，t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个.
其中经验熵Ht(T)为:
损失函数第一项能够理解为全部叶结点的经验熵加权和：
损失函数第二项看下书上解释：
看到这里我想到了以前看Ng视频的内容，这部分不就是正则化嘛!有兴趣的同窗能够看下coursera上机器学习课程week-3-第5节.
利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。
剪枝算法步骤：
7.CART算法
分类与回归树(classification and regression tree,CART)，顾名思义，该算法既可用于分类也可用于回归。一样由特征选择、树的生成及剪枝组成。
CART是在给定输入随机变量X条件下输出随机变量Y的条件几率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每一个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上肯定预测的几率分布，也就是在输入给定的条件下输出的条件几率分布。
主要由两步组成：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽可能大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小做为剪枝的标准。
注：机器学习中一般将数据分为训练集、测试集、交叉验证数据集。
CART生成
决策树生成就是递归地构建二叉决策树的过程。对回归树用平方偏差最小化准则，对分类树用基尼指数最小化准则，进行特征选择生成二叉树。
（1）回归树的生成
假设X与Y分别为输入和输出变量，而且Y是连续变量，给定训练数据集：
一个回归树对应着输入空间(即特征空间)的一个划分以及在划分单元上的输出值。假设已将输入空间划分为M个单元R1，R2…,RM,而且在每一个单元有一个固定的输出值cm,回归树模型能够表示为：
当输入空间的划分肯定时，能够用平方偏差来表示回归树对于训练数据的预测偏差，用平方偏差最小化准则求解每一个单元上的最优输出值。单元Rm上的cm最优值是Rm上的全部输入xi对应的输出yi的均值，即
问题关键，输入空间怎么划分，一般采用启发式的方法，选择第j个变量x(j)和它的取值s，做为切分变量和切分点，并定义两个区域：
而后寻找最优切分变量j和最优切分点s，具体地，求解
对固定输入变量j能够找到最优切分点s。
遍历全部输入，找到最优的切分变量j，构成一个对(j,s)。依此将输入空间划分为两个区域。接着，对每一个区域重复以上划分过程，直到知足中止条件为止。这样就生成了一颗回归树。一般称为最小二乘回归树(least squares regression tree)。
最小二乘树生成算法步骤：
CART案例会在后续的提高树算法笔记中说起，可是那只用了树桩。
（2）分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼指数：分类问题中假设有K个类，样本点属于第k类的几率为pk，则几率分布的基尼指数定义为
对于二分类问题，弱样本点属于第一个类的几率为p，则几率分布的基尼指数为
对于给定的样本集合D，其基尼指数为
这里，Ck是D中属于第k类的样本子集，K是类的个数。
若是样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即：
则在特征A的条件下，集合D的基尼指数定义为：
基尼指数Gini(D)表示集合D三维不肯定性，基尼指数Gini(D,A)表示经A=a分割后的集合D的不肯定性。基尼指数越大，样本集合的不肯定性也就越大。读到这里想必已经想到上一博文中说的熵了吧，下面给出它们的对比：
熵H(p)随几率p的变化曲线：
二分类问题中基尼指数Gini(p)\熵(单位比特)之半1/2H(p)和分类偏差率的关系：
由上图可看出基尼指数与熵之半的曲线很接近，均可以近似的表明分类偏差率。
CART生成算法步骤：
CART生成算法案例：
CART剪枝
CART剪枝算法从“彻底生长”的决策树的地段剪去一些子树，使决策树变小，从而可以对未知数据有更准确的预测。CART剪枝算法步骤：
（1）首先从省城算法产生的决策树T0低端不断剪枝，知道T0的根结点，造成一个子序列{T0，T1，…Tn}
（2）经过交叉验证在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
(1)剪枝，造成一个子树序列
CART的剪枝与前面所讲的决策树剪枝大同小异，也是最小化损失函数的过程，即加上正则化项。
(2)在剪枝的子序列T0，T1,…,Tn中经过交叉验证选取最优子树Ta
CART剪枝算法步骤：
8.总结
决策树涉及的内容很广，这两篇笔记涵盖了决策树算法的原理公式（包括熵、基尼指数等概念）、多种决策树生成算法和剪枝算法，看完这些花了我两天的空闲时间，而后过第二遍作笔记也是断断续续接近一周的时间。李航老师的书仍是很符合个人学习思惟的，接下去要在理解原理的基础上作些实践。决策树算法提出至今已有几十年的时间，它们还在实际生产工做中发挥着重大做用，足见其威力。特别是基于决策树作的一些优化和改进的算法，如GBDT\Xgboost，都是很是简单高效的算法工具。
参考文献：
李航 《统计学习方法》
注：本文以及前一篇博文全部公式图片均来自《统计学习方法》