决策树模型的简介
分类决策树模型是一种描述对实例进行分类的树形结构。我们可以理解这种树形结构是符合if-then的规则，也可以认为是定义在特征空间与类空间上的条件概率分布。我们希望我们构建的树结构的泛化能力尽可能强。在学习时，我们利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新数据利用决策树模型进行分类。
决策树学习通常包括三个步骤：1.特征选择 2.决策树的生成和 3. 决策树的修剪。
决策树的模型有许多种，主要的区别就是信息增益的计算函数不同。
特征选择
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随即分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
我们进行特征选择是希望决定用哪个特征来划分特征空间。
直观熵，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下具有最好的分类，那么就更应该选择这个特征。信息增益(information gain)就能够很好地表示这一直观地准测。
这里会用到的信息论知识：
- 1.信息熵(information entropy)
- 2.信息增益(information gain)
- 3.信息增益率(information gain ratio)
- 4.基尼指数(Gini index)
信息增益
在信息论与概率统计中，熵(entropy)是表示随机变量不确定性地度量，设X是一个取有限个值的离散随机变量，其概率分布为$P(X=x_i)=p_i$, i=1,2,3….,n
熵
则随机变量X的熵定义为：
也常称为经验熵
条件熵
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。
其中$p_i=P(X=x_i)$,i=1,2,…,n
也常称为经验条件熵
信息增益(information gain)： 特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵与特征A给定跳进啊下D的经验条件熵H(D|A)之差。
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
直观的理解互信息，就是在我们给定特征X以后，训练集的确定性增加的量。
根据信息增益准则的特征选择方法是：对训练数据集(或子集)D,计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
信息增益(information gain)算法：
输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益g(D,A)
(1)计算数据集D的经验熵H(D)
(2)计算特征A对数据集D的经验条件熵H(D|A)
(3)计算信息增益
决策树的生成
ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
ID3算法：
输入：训练数据集D,特征集A,阈值$\epsilon$
输出：决策树T
(1)若D中所有实例属于同一类$C_k$,则T为单节点树，并将类$C_k$作为该结点的类标记，返回T
(2)若A=∅，则T为单结点树，并将D中实例数最大的类$C_k$作为该结点的类标记，返回T;
(3)否则，按信息增益算法计算A中各个特征对D的信息增益，选择信息增益最大的特征$A_g$;
(4)如果$A_g$的信息增益小于阈值$\epsilon$,则置T为单结点树，并将D中实例数最大的类$C_k$作为该结点的类标记，返回T
(5)否则，对$A_g$的每一可能值$a_i$,依$A_g=a_i$将D分割为若干非空子集$D_i$,将$D_i$中的实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T,返回$T$;
(6)对第i个子结点，以$D_i$为训练集，以$A-{A_g}$为特征集，递归地调用步(1)~(5),得到子树$T_i$,返回$T_i$
ID3算法只有树地生成，所以该算法生成的树容易产生过拟合
C4.5算法
C4.5是对ID3的改进。C4.5在生成的过程中，用信息增益比(information gain ratio)来选择特征
C4.5算法
输入：训练数据集D,特征集A,阈值$\epsilon$
输出：决策树T
(1)若D中所有实例属于同一类$C_k$,则T为单节点树，并将类$C_k$作为该结点的类标记，返回T
(2)若A=$\empty$，则T为单结点树，并将D中实例数最大的类$C_k$作为该结点的类标记，返回T;
(3)否则，按下式计算A中各特征对D的信息增益比，选择信息增益比最大的特征$A_g$
其中，$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$, n是特征A的取值的个数
(4)若果$A_g$的信息增益比小于阈值$\epsilon$,则置T为单结点树，并将D中实例数最大的类$C_k$作为该结点的类，返回T
(5)否则,对$A_g$的每一可能值$a_i$，依$A_g=a_i$将D分割为子集若干非空$D_i$,将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构建树T,返回T；
(6)对结点i,以$D_i$为训练集，以$A-{A_g}$为特征集,递归地调用步(1)~步(5),得到子数$T_i$,返回$T_i$
需注意，信息增益比对可取值数目较少的属性有所偏好，因此，C4.5算法可以使用一个启发式的方法:先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益比最高的。
CART算法
CART的全程是classification and regression tree 分类与回归树模型。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。CART常用的特征选择方式是Gini指数。
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为”是”的分支，右分支是取值为”否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法由以下两步组成:
(1)决策树生成:基于训练数据集生成决策树，生成的决策树要尽量大；
(2)决策树剪枝
回归树生成
假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集$D={(x_1,y_1),(x_2,y_2),….,(x_N,y_N)}$
考虑如何生成回归树。
一个回归树对应着输入空间(即特征空间)的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元$R_1,R_2,….,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$.于是回归树模型可以表示为
当输入空间的划分确定时，可以用平方误差$\sum_{x_i∈R_m}(y_i-f(X_i))^2$来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元$R_m$上的$c_m$的最优值$\hat{c_m}$是$R_m$上的所有输入实例$x_i$对应的输出$y_i$的均值，即
问题是怎样对输入空间进行划分，这里采用启发式的方法，选择第j个变量$x^{(j)}$和它取的值s，作为切分变量和切分点。并定义两个区域：
$R_1(j,s)={x|x^{(j)}≤s} $ 和$R_2(j,s)={x|x^{(j)}＞s}$
然后寻找最优切分变量j和最优切分点s.具体地，求解
对于固定输入变量j可以找到最优切分点s.
$\hat{c_1}=ave(y_i|x_i∈R_1(j,s))$和$\hat{c_2}=ave(y_i|x_i∈R_2(j,s))$
遍历所有输入变量，找到最优地切分变量j，构成一个对(j,s).依此将输入空间划分为两个区域。接着对每个区域重复上述分过程。直到满足停止条件为止。
这里$c$的选择只需要计算该区域内的点的y值的平均值即可,而j,s是另外的几个需要我们求得参数,j是最优特征,s是该特征下得最优特征切分点.
最小回归树生成算法：
输入:训练数据集D
输出:回归树f(x)
在训练数据集所在的输入空进啊中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值。构建二叉决策树：
(1)选择最优切分变量j与切分点s，求解
遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小的对(j,s)
(2)用选定的对(j,s)划分区域并决定相应的输出值:
$R_1(j,s)={x|x^{(j)}≤s}$, $R_2(j,s)={x|x^{(j)}＞s}$
(3)继续对两个子区域调用步骤(1)(2)，直到满足停止条件
(4)将输入空间划分为M个区域$R_1,R_2,…,R_M,$生成决策树：
分类树的生成
分类树用基尼指数(Gini index)选择最优特征，同时决定该特征的最优二值切分点
基尼指数：
分类问题中，假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为
如果样本集合D根据特征A是否取某一可能值a被分割成$D_1$和$D_2$两部分，即
则在特征A的条件下，集合D的基尼指数定义为
基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大。这与熵类似。
CART生成算法
输入:训练数据集D,停止计算的条件;
输出:CART决策树
(1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。此时，对每一个特征A,对其可能的每个值a，根据样本点对A=a的测试为”是”或否将D分割为$D_1$和$D_2$两部分，利用Gini(D,A)的公式其中A=a.
(2)在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征和最优切分点.依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去
(3)对两个子结点递归地调用(1)(2)直至满足停止条件
(4)生成CART决策树
算法停止计算地条件是结点中的样本个数i小于预定阈值，或样本集的基尼指数小于预定阈值(样本基本属于同一类)，或者没有更多特征。
三种决策树对比
ID3是采用信息增益作为评价标准，往往会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少的程度。特征取值越多就意味着确定性越高，也就是条件熵越小，信息增益越大。这实际熵是一个缺陷。
C4.5实际上是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力
从样本类型的角度上来看，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换为多个取值区间的离散型变量。 而对于CART,由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量
从应用的角度，ID3和C4.5只能用于分类任务，而CART从名字就可以看出来不仅可以用于分类还可以应用于回归任务(回归树使用最小平方误差准则)。
从实现细节、优化过程等角度，这三种决策树还有一些不同。比如，ID3对样本特征缺失比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理;ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一棵二叉树，且每个特征可以重复使用。 ID3和C4.5通过剪枝来权衡树的准确性和泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。
决策树的剪枝
常用的剪枝方法分为1. 预剪枝2. 后剪枝
预剪枝很简单就是在训练集上选择出划分特征后,再在验证集上确认是否该对该特征进行划分.判断的标准很简单,就是看在划分前后泛化性能是否有提升. 可以看到预剪枝使得决策树的很多分支都没有”展开”,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销.另一方面,因为预剪枝是基于”贪心”的,所以,虽然当前划分不能提升泛化性能,但是基于该划分的后续划分却有可能导致性能提升,因此预剪枝决策树有可能带来欠拟合的风险
后剪枝就是先构造一棵完整的决策树,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛化性能的提升,则把该子树替换成叶结点.
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即 出现过拟合。过拟合的原因在于学习时过多地考虑如何提高对训练数据地正确分类，从而构建出了过于复杂地决策树。
在决策树学习中将已生成的树进行简化的过程的过程称为剪枝(pruning).具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根节点或父结点作为新的叶结点，从而简化分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶结点个树为|T|，t是树T的叶结点，叶结点有$N_t$个样本点，其中k类的样本点有$N_{tk}$个，k=1,2,…,K，$H_t(T)$为叶结点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为：
其中经验熵为
在损失函数中右端第一项记为：
这时有：
其中C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度。|T|表示模型复杂度。参数α≥0控制两者之间的影响。
树的剪枝算法
输入:生成算法产生的整个树T，参数α
输出:修建后的子树$T_α$
(1)计算每个结点的经验熵
(2)递归地从树的叶结点向上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_B$与$T_A$,其对应的损失函数值分别为$C_α(T_B)$与$C_α(T_A)$,如果
则进行剪枝，即将父结点变为新的叶结点
(3)返回(2),直至不能继续为止，得到损失函数最小的子树$T_α$
CART 剪枝
CART剪枝算法从”完全生长”的决策树的底端剪去一些子树，使决策树变小(模型更简单)，从而能够对未知数据有更准确的预测.CART剪枝算法由两步组成：首先从生成算法产生的决策树$T_0$底端开始不断剪枝。直到$T_0$的根节点。形成一个子树序列${T_0,T_1,…,T_n}$;然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
1.剪枝，形成一个子树序列
在剪枝过程中，计算子树的损失函数：
其中，T为任意子树,C(T)为对训练数据的预测误差(如基尼指数),|T|为子树的叶结点个数，α≥0为参数。$C_α(T)$为参数是α时的子树T的整体损失。参数α权衡训练数据的拟合程度与模型的复杂度。
对固定的α，一定存在使损失函数$C_α(T)$最小的子树，将其表示为$T_α$.$T_α$在损失函数$C_α(T)$最小的意义下是最优的。容易验证这样的最优子树是唯一的.当α大时,最优子树$T_α$偏小；当α小的时候，最优子树$T_α$偏大。极端情况，当α=0时，整体树是最优的。当$α\rightarrow∞$时，根据点组成的单结点树是最优的。
具体地，从整体树$T_0$开始剪枝，对$T_0$的任意内部结点t,以t为单结点树的损失函数是:
以t为根节点的子树$T_t$的损失函数是:
当α=0及α充分小时，有不等式
当α增大时，在某一α有
当α再增大时只要$α=\frac{C(t)-C(T_t)}{|T_t|-1}$,$T_t$与t有相同的损失函数值，而t的结点少，因此t比$T_t$更可取，对$T_t$进行剪枝。
为此，对$T_0$中每一内部结点t,计算
它表示剪枝后整体损失函数减少的程度。在$T_0$中减去g(t)最小的$T_t$,将得到的子树作为$T_t$,同时将最小的g(t)设$α_1$.$T_1$为区间$[α_1,α_2)$的最优子树。
如此剪枝下去，直至得到根节点。在这一过程中不断地增加α的值，产生新的区间。
2.在剪枝得到的子树序列$T_0,T_1,…,T_n$中通过交叉验证选取最优子树$T_α$
具体地，利用独立的验证数据集，测试子树序列$T_0,T_1,…,T_n$中各棵子树的平方误差或基尼指数.平方误差或基尼指数.平方误差或基尼指数最小的决策树被认为是最优的决策树.在子树序列中，每棵子树$T_1,T_2,…,T_n$都对应于一个参数$α_1,α_2,..α_n$.所以当最优子树$T_k$确定时,对应的$α_k$也确定了，即得到最优决策树$T_α$.
CART剪枝算法
输入:CART算法生成的决策树$T_0$;
输出:最优决策树$T_α$
(1)设k=0,T=$T_0$
(2)设α=+∞.
(3)自上而下地对各内部结点t计算$C(T_t)$,$|T_t|$以及
这里，$T_t$表示以t为根结点的子树。$C(T_t)$是对训练数据的预测误差,$|T_t|是T_t$的叶结点个数.
(4)自上而下地访问内部结点t,如果有g(t)=α,进行剪枝,并对叶结点t以多数表决法决定其类,得到树T.
(5)设k=k+1,$α_k$=α,$T_k$=T.
(6)如果T不是由根结点单独构成的树,则回到步骤(4)[至底向上切直到只剩下根节点为止]
(7)采用交叉验证法在子树序列$T_0,T_1,…,T_n$中选取最优子树$T_α$
连续和缺失值的处理
连续值的离散化处理
由于连续属性的可取值数目不再有限，因此不能直接根据连续属性的取值来对结点进行划分。此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。
缺失值的处理
现实任务中常会遇到不完整样本，即样本的某些属性值缺失.
在这里我们必须要考虑利用缺失属性值的训练样例来进行学习。
我们需解决两个问题:(1)如何在属性值缺失的情况下进行划分属性选择?
(2)给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分?
问题一的解决
给定训练集D和属性a令$\overline{D}$表示D中在属性a上没有缺失值的样本子集。对问题(1),显然我们智能根据$\overline{D}$来判断属性a的优劣。
假定属性a有V个可取值${a^1,a^2,…,a^V}$,令$\overline{D}^v$表示在属性a上取值为$a^v$的样本子集，$\overline{D}_k$表示$\overline{D}$中属于第k类的样本子集，则显然，有$\overline{D}=∪_ k\overline{D}_k=∪_ v\overline{D}^v $,假定我们为每个样本x赋予一个权重$w_x$,并定义
直观来看，$\rho$表示无缺失值样本所占的比例,$\overline{p}_k$表示无缺失值样本中第k类所占的比例,$\overline{r}^v$则表示无缺失值样本中在属性a上取值为$a^v$的样本所占的比例。
基于上述定义，我们可以将信息增益的公式推广为
问题二的解决
若样本x在划分属性a上的取值已知,则将x划入与其取值对应的子结点，且样本权值在子结点中保持为$w_x$.若样本x在划分属性a上的取值未知,则将x同时划入所有子结点(即每个分支中都有该样本),且样本权值在与属性值$a^v$对应的子结点中调整为$\overline{r}_v·w_x$;直观地看，这就是让同一个样本以不同的概率划入到不同子结点中去
多变量决策树
若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同样本之间的分类边界。决策树所形成的分类边界有一个明显的特点:轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。平行坐标轴的分类边界有较好的解释性
但同时考虑一下能否用斜的分类边界，？如果我们用斜的分类边界显然这条边界关系到两个坐标轴的属性，因此若作用于决策树，这将是一个含有多个属性来分类的结点，我们称这样的决策树为多变量决策树。
在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试;换言之，每个非叶子结点是一个形如$\sum_{i=1}^dw_ia_i=t$的线性分类器，其中$w_i$是属性$a_i$的权重，$w_i$和t可在该结点所含的样本集和属性集上学习得到。
总结
决策树的优劣：
优点：
- 1 决策树易于理解和实现.人们在通过解释后都有能力去理解决策树所表达的意义。
- 2 对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
- 3 能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。
- 4 是一个白盒模型如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
- 5 易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
- 6 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
- 7 计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。
缺点: - 1 容易过拟合。
- 2 对于那些各类别样本数量不一致的数据，在决策树当中信息增益的结果偏向于那些具有更多数值的特征。
- 3.模型不稳定,数据微小变化都有可能造成完全不同的树生成.(?????)
增量学习——有些决策树学习算法可进行”增量学习”,即在接收到新样本后可对已学得的模型进行调整,而不需要完全重新学习。增量学习可有效地降低每次接收到新样本后的训练时间开销,但多步增量学习后的模型会与基于全部数据训练而得的模型有较大差别。