7.1基本概念

决策树(Decision Tree)实际上是通过树形的结构来进行分类或者回归
- 在分类问题中可以根据样本的不同特征属性的不同属性值来进行多次分类的决策最终确定输入样本的类别，也就相当于执行了一连串嵌套的if-else语句，也可以被认为是定义在特征空间和类空间上的条件概率分布。
- 决策树的优点是模型具有较好的可读性，分类的速度比较快。
决策树中有一系列节点和有向边，节点又分为内部节点和也节点，内部节点表示一个特征或者属性，叶节点表示一种类别。

7.1.1决策树模型的建立

决策树主要依靠训练数据，采取损失函数最小化的原则来建立决策树模型，分为特征选择、决策树的生成和剪枝三个步骤。建立决策树的过程用的特点主要有：
- 采用递归的方法构建决策树
- 当所有的样本都属于同一类或者在这一层已经对所有的特征都进行了分类，决策树的建立就停止
- 在决策树的每一层选取一个最优的特征并用这个特征来进行分类，这也是决策树算法最关键的地方
- 一般而言我们希望，随着划分过程的不断进行，决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度越来越高

因为决策树考虑到了样本中的所有点，对所有的样本点都有正确的分类，因此决策树的bias实际上是0，因此评价一棵树的主要标准是variance，
一般来说规模比较小的决策树的performance更好。

7.2最优特征的选取

上面已经说到决策树构建的最重要的部分就是在每一层选择合适的特征来进行划分，常见的评估方式有熵、信息增益等等。

7.2.1信息熵Entropy

熵可以用来表示随机变量的不确定性。如果X是一个取值个数为有限个值即 $七、决策树Decision Tree - 图1$ %3Dp_i#card=math&code=P%28X%3Dx_i%29%3Dp_i)，那么随机变量X的熵的定义就是：

$七、决策树Decision Tree - 图2$ %3D-%5Csum%7Bi%3D1%7D%5Enp_i%20%5Clog%20p_i%20%5Cin%20%5B0%2C%20%5Clog%20n%5D%0A#card=math&code=H%28x%29%3D-%5Csum%7Bi%3D1%7D%5Enp_i%20%5Clog%20p_i%20%5Cin%20%5B0%2C%20%5Clog%20n%5D%0A)

而对于随机变量X和Y，如果 $七、决策树Decision Tree - 图3$ %3Dp%7Bij%7D#card=math&code=P%28X%3Dx_i%2CY%3Dy_i%29%3Dp%7Bij%7D)，那么在X给定的情况下随机变量Y的条件熵代表了X给定条件下Y的条件概率分布的
熵对于X的数学期望：

$七、决策树Decision Tree - 图4$ %3D%5Csum%7Bi%3D1%7D%5Enp_iH(Y%7CX%3Dx_i)%0A#card=math&code=H%28Y%7CX%29%3D%5Csum%7Bi%3D1%7D%5Enp_iH%28Y%7CX%3Dx_i%29%0A)

当信息信息量比较大的时候

7.2.2信息增益

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度

特征A对于训练数据集D的信息增益 $七、决策树Decision Tree - 图5$ #card=math&code=g%28D%2CA%29)可以定义为D的经验熵和特征A给定条件下D的经验条件熵的差值，即：

$七、决策树Decision Tree - 图6$ %3DH(D)-H(D%7CA)%0A#card=math&code=g%28D%2CA%29%3DH%28D%29-H%28D%7CA%29%0A)

信息增益又叫做互信息(mutual information)，两个概念是等价的。基于信息增益的特征选择方法一般都是对于当前训练集D，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征来进行当前层的分类。

假设训练的数据集是D，有K个不同的分类 $七、决策树Decision Tree - 图7$ 满足 $七、决策树Decision Tree - 图8$ ，其中特征A有n个不同的取值 $七、决策树Decision Tree - 图9$ ，根据特征的取值将D划分成了n个不同的子集 $七、决策树Decision Tree - 图10$ ，而每个子集中 $七、决策树Decision Tree - 图11$ 表示属于类别 $七、决策树Decision Tree - 图12$ 的样本，那么数据集D的经验熵可以表示为：

$七、决策树Decision Tree - 图13$ %3D-%5Csum%7Bk%3D1%7D%5E%7BK%7D%5Cfrac%7B%7C%0AC_k%7C%7D%7B%7CD%7C%7D%5Clog_2%5Cfrac%7B%7C%0AC_k%7C%7D%7B%7CD%7C%7D#card=math&code=H%28D%29%3D-%5Csum%7Bk%3D1%7D%5E%7BK%7D%5Cfrac%7B%7C%0AC_k%7C%7D%7B%7CD%7C%7D%5Clog_2%5Cfrac%7B%7C%0AC_k%7C%7D%7B%7CD%7C%7D)

特征A对于数据集D的条件经验熵可以表示为：

$七、决策树Decision Tree - 图14$ %3D%5Csum%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7B%7C%0AD_i%7C%7D%7B%7CD%7C%7DH(D_i)%3D-%5Csum%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7B%7C%0ADi%7C%7D%7B%7CD%7C%7D%5Csum%5EK%7Bk%3D1%7D%5Cfrac%7B%7CD%7Bik%7D%7C%7D%7B%7CD_i%7C%7D%5Clog_2%5Cfrac%7B%7CD%7Bik%7D%7C%7D%7B%7CDi%7C%7D#card=math&code=H%28D%7CA%29%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7B%7C%0ADi%7C%7D%7B%7CD%7C%7DH%28D_i%29%3D-%5Csum%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7B%7C%0ADi%7C%7D%7B%7CD%7C%7D%5Csum%5EK%7Bk%3D1%7D%5Cfrac%7B%7CD%7Bik%7D%7C%7D%7B%7CD_i%7C%7D%5Clog_2%5Cfrac%7B%7CD%7Bik%7D%7C%7D%7B%7CD_i%7C%7D)

7.2.3信息增益比

以信息增益作为数据集划分依据的时候，容易偏向于选择取值更多的特征作为分类标准，但是使用信息增益比，可以校正这一偏差

信息增益比是数据集D关于特征A的信息增益和熵之比，即

$七、决策树Decision Tree - 图15$ %3D%5Cfrac%7Bg(D%2CA)%7D%7BHA(D)%7D%3D%5Cfrac%7Bg(D%2CA)%7D%7B-%5Csum%5Climits%7Bi%3D1%7D%5En%5Cfrac%7B%7CDi%7C%7D%7B%7CD%7C%7D%5Clog_2%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7D%7D%0A#card=math&code=g_R%28D%2CA%29%3D%5Cfrac%7Bg%28D%2CA%29%7D%7BH_A%28D%29%7D%3D%5Cfrac%7Bg%28D%2CA%29%7D%7B-%5Csum%5Climits%7Bi%3D1%7D%5En%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7D%5Clog_2%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7D%7D%0A)

7.3决策树的生成与剪枝

7.3.1 ID3算法

ID3算法的核心是在决策树的各个节点上用Information Gain来进行特征的选择，并且递归地建立决策树：

从根结点开始，对于当前节点计算所有可能的特征值的信息赠一，选择信息增益最大的特征作为划分的一句并建立字节点
直到所有的特征的信息增益都很小或者没有子节点位置停止调用

7.3.2 C4.5算法

和ID3算法类似，但是采用信息增益比作为选择的特征，其他的好像区别不是很大

7.3.3决策树的剪枝Pruning

各类决策树算法生成的决策树可能会有非常高的复杂度，可以用剪枝的办法对决策树进行一定的简化
- 决策树的剪枝往往通过极小化决策树整体的损失函数或者代价函数来实现。设决策树T的每个叶节点t有 $七、决策树Decision Tree - 图16$ 个样本点，其中属于类别k的有 $七、决策树Decision Tree - 图17$ 个， $七、决策树Decision Tree - 图18$ #card=math&code=Ht%28T%29)是节点t的经验熵 $七、决策树Decision Tree - 图19$ %3D-%5Csum%7Bk%3D1%7D%5E%7Bn%7D%5Cfrac%7BN%7Btk%7D%7D%7BN_t%7D%5Clog%20%5Cfrac%7BN%7Btk%7D%7D%7BNt%7D%0A#card=math&code=H_t%28T%29%3D-%5Csum%7Bk%3D1%7D%5E%7Bn%7D%5Cfrac%7BN%7Btk%7D%7D%7BN_t%7D%5Clog%20%5Cfrac%7BN%7Btk%7D%7D%7BN_t%7D%0A)
- 那么决策树学习的损失函数可以定义为：

$七、决策树Decision Tree - 图20$ %3D%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7DN_tH_t(T)%2B%5Calpha%7CT%7C%3D-%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7D%5Csum%7Bk%3D1%7D%5E%7Bn%7DN%7Btk%7D%5Clog%20%5Cfrac%7BN%7Btk%7D%7D%7BN_t%7D%2B%5Calpha%7CT%7C%0A#card=math&code=C%7B%5Calpha%7D%28T%29%3D%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7DN_tH_t%28T%29%2B%5Calpha%7CT%7C%3D-%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7D%5Csum%7Bk%3D1%7D%5E%7Bn%7DN%7Btk%7D%5Clog%20%5Cfrac%7BN_%7Btk%7D%7D%7BN_t%7D%2B%5Calpha%7CT%7C%0A)

而其中是一个自己确定的参数值，比较大的可以是的损失函数偏向于更简单的模型，而比较小的则似的损失函数的优化偏向于比较复杂的模型，的时候完全无视了模型的复杂度，而只考虑模型和训练数据的匹配程度
- 剪枝过程是一个从底部向上的递归过程，首先需要计算每个节点的经验熵，如果剪掉某一段子树之后损失函数比剪掉之前更小，就进行剪枝，将父节点作为新的叶节点，重复下去直到不能继续为止。

7.5 CART算法

7.5.1基本介绍

CART算法是Classification and Regression Tree分类与回归树的简称，从字面意思就可以看出来这种决策树既可以用于分类，也可以用于回归。
- CART树的一个基本假设就是决策树都是二叉树，决策的结果只有是与否两种，这等价于递归地二分每个特征，将输入空间划分成优先个但愿，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布
- CART算法由生成和剪枝两个部分组成
  - 对于生成的决策树希望它尽可能要大
  - 剪枝的时候使用验证数据集来选择最优子树，这时候用损失函数最小作为剪枝的标准
回归树需要用平方误差最小化准则，分类数使用基尼指数最小化准则来进行特征的选择

7.5.2回归树的生成

回归树对应的是输入空间的一个划分和输出值的映射关系，假如说输入的空间被划分成了M个单元 $七、决策树Decision Tree - 图24$ ，每个分别对应了固定的输出值 $七、决策树Decision Tree - 图25$ ，那么回归树模型可以表示为：

$七、决策树Decision Tree - 图26$ %3D%5Csum%7Bm%3D1%7D%5E%7BM%7Dc_m%5Cmathbb%20I(x%5Cin%20R_m)%0A#card=math&code=f%28x%29%3D%5Csum%7Bm%3D1%7D%5E%7BM%7Dc_m%5Cmathbb%20I%28x%5Cin%20R_m%29%0A)

如果输入空间的划分确定的时候可以用平方误差来估计训练数据的预测误差，用平方误差最小的准则来求解每个单元上的最优输出值。用平方误差最小的原则来求解每个单元上的最优输出值。
- 单元 $七、决策树Decision Tree - 图27$ 上的最优输出值是这个单元中所有的 $七、决策树Decision Tree - 图28$ 的平均值，即

$七、决策树Decision Tree - 图29$

现在的问题在于如何对输入空间进行合理的划分，《统计学习方法》里采用了一种启发式的方法，选择选择特征空间中的第 $七、决策树Decision Tree - 图30$ 个变量 $七、决策树Decision Tree - 图31$ %7D#card=math&code=x%5E%7B%28j%29%7D)和它取的值s作为切分变量(splitting variable)和切分点。并定义两个区域：

$七、决策树Decision Tree - 图32$ %3D%5Clbrace%20x%7Cx%5E%7B(j)%7D%5Cle%20s%5Crbrace%20%0A#card=math&code=R_1%28j%2Cs%29%3D%5Clbrace%20x%7Cx%5E%7B%28j%29%7D%5Cle%20s%5Crbrace%20%0A)

$七、决策树Decision Tree - 图33$ %3D%5Clbrace%20x%7Cx%5E%7B(j)%7D%3E%20s%5Crbrace%20%0A#card=math&code=R_2%28j%2Cs%29%3D%5Clbrace%20x%7Cx%5E%7B%28j%29%7D%3E%20s%5Crbrace%20%0A)

然后来寻找最优切分变量和最优的切分点，在上面划分出的两个区域内寻找出最优切分点，也就是需要求解表达式：

$七、决策树Decision Tree - 图34$ %7D%5Cleft%5B%5Cmin%7Bc_1%7D%5Csum%7Bxi%5Cin%20R_1(j%2Cs)%7D(y_i-c_1)%5E2%2B%5Cmin%20%7Bc2%7D%5Csum%7Bxi%5Cin%20R_1(j%2Cs)%7D(y_i-c_2)%5E2%5Cright%5D%0A#card=math&code=%5Cmin%7B%28j%2Cs%29%7D%5Cleft%5B%5Cmin%7Bc_1%7D%5Csum%7Bxi%5Cin%20R_1%28j%2Cs%29%7D%28y_i-c_1%29%5E2%2B%5Cmin%20%7Bc2%7D%5Csum%7Bx_i%5Cin%20R_1%28j%2Cs%29%7D%28y_i-c_2%29%5E2%5Cright%5D%0A)

对于一个固定的j而言， $七、决策树Decision Tree - 图35$ 的值是确定的，即按照上面所说的取这一范围内的平均值即可，而通过遍历所有的输入变量可以找到最优的切分变量j，然后就可以根据一个pair $七、决策树Decision Tree - 图36$ #card=math&code=%28j%2Cs%29)将决策树划分成两个区域，然后在每个区域中重复上述操作机课，最后就可以生成一棵最小二乘回归树

7.5.3分类树的生成

分类树采用基尼指数选择最优的特征，同时决定该特征的最优二值切分点

(基尼指数)：在分类问题中假设有K个不同的类，则样本点属于第K类的概率为 $七、决策树Decision Tree - 图37$ ，那么基于概率分布的基尼指数可以定义为：

$七、决策树Decision Tree - 图38$ %3D%5Csum%7Bk%3D1%7D%5EKp_k(1-p_k)%3D1-%5Csum%7Bk%3D1%7D%5EKpk%5E2%0A#card=math&code=G%28p%29%3D%5Csum%7Bk%3D1%7D%5EKpk%281-p_k%29%3D1-%5Csum%7Bk%3D1%7D%5EKp_k%5E2%0A)

而在样本集合D中，基尼指数的定义为：

$七、决策树Decision Tree - 图39$ %3D1-%5Csum%7Bk%3D1%7D%5EK%5Cleft(%5Cfrac%7B%7CC_k%7C%7D%7B%7CD%7C%7D%5Cright)%5E2%0A#card=math&code=G%28D%29%3D1-%5Csum%7Bk%3D1%7D%5EK%5Cleft%28%5Cfrac%7B%7CC_k%7C%7D%7B%7CD%7C%7D%5Cright%29%5E2%0A)

如果样本集合D根据某特征A被分成了两个部分，那么在特征A的条件下，集合D的基尼指数的定义为：

$七、决策树Decision Tree - 图40$ %3D%5Csum%7Bi%3D1%7D%5E2%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7DG(D_i)%0A#card=math&code=G%28D%2CA%29%3D%5Csum%7Bi%3D1%7D%5E2%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7DG%28D_i%29%0A)

基尼指数可以表示集合D的不确定性
使用基尼指数构造CART决策树的方法是：
- 从根结点开始，递归地对每个节点进行如下操作
- 计算当前节点的基尼指数，对于每个特征A的每种取值a，按照是否有A=a来对当前节点中的数据集进行分割，并计算条件基尼指数
- 在特征A的所有条件基尼指数中选择最小的作为一个划分依据，产生两个子节点
- 对子节点递归地调用上面的操作
- 生成完整的CART决策树

7.5.4 CART树剪枝

太抽象了，没搞懂，后面再说