《统计学习方法》读书笔记——决策树

（仅记录自己的学习心得，默认记录自己之前不太清楚或者有新的心得的部分，所以可能并不全面。）

ID3 算法：依据信息增益选择作为结点的特征，且不能重复选取。

C4.5 算法：依据信息增益比选择结点的特征，也不能重复选特征。

剪枝【重要的部分】：通过极小化决策树整体的损失函数或代价函数实现。

【介绍损失函数】

一些概念：

经验熵： $H_{t}(T) = -\sum_{k} \frac{N_{tk} }{N_{t} }log\frac{N_{tk} }{N_{t} }$

某个叶子的样本个数为 $N_{t}$ , 其中属于第k类的有 $N_{tk}$ 个。

这个形式跟熵的定义很像： $H(X)=-\sum_{i=1}^np_{i}logp_{i}$ , $p_{i}$ 为随机变量X取不同值的概率。（如果仅有两种取值，概率为0或1时熵的值最小是0，因为是确定情况，0.5时熵的值最大，因为不确定性最大，因此熵越大代表随机变量取值不确定性越强，如下图：）（我猜公式里取log也是因为需要在自变量为1时需要为0，又因为log函数小于1时是负数，所以整个公式需要取负号）

继续看经验熵的公式，可以看出概率的位置为每个叶子里第k类样本占整个叶子样本的比例，也就可以将经验熵理解为以类别为随机变量的熵，而因为是在同一个叶子里，所以我们希望这个熵越小越好。因为一个叶子的类别由里面大多数的类别决定，所以经验熵越小，预测误差越小。

损失函数的概念：

整个决策树T的损失函数： $\sum_{t=1}^TN_{t} H_{t}(T)+\alpha \vert T \vert$ ， $\vert T \vert$ 为叶结点的个数，t为叶结点

公式第一项为每个叶子的结点数*经验熵，书中说这表明了模型对训练数据的预测误差。由此可以推测经验熵表示了对每一个样本的预测误差，（因为我理解的熵的含义一直是一个度量的概念，我不太清楚这是否是一个量化的值，所以这块理解不是很透彻）

公式的第二项表示模型的复杂程度。

剪枝的过程就是在 $\alpha$ 确定时，选择损失函数最小的子树。因此：

$\alpha$ 较大意味着会选择复杂度低的子树，简单的模型； $\alpha$ 较小意味着选择较复杂的子树； $\alpha$ =0意味着只考虑模型对训练数据的拟合程度，不考虑复杂度。因此损失函数平衡了拟合效果和复杂度两种因素。

【CART算法】：分类与回归树，二叉树，包括决策树生成和剪枝过程。

1）生成树：

回归树：依据平方误差最小化准则进行最优特征的最优分割点。

寻找最优特征的最优分割点：对第j个特征（书里说是第j个变量，我理解就是特征），假设切分点为s，使得把该特征的所有取值分成两个部分： $R_{1} （j,s）=\left\{ x\vert x^j\leq s \right\}$ , $R_{1} （j,s）=\left\{ x\vert x^j > s \right\}$ 。根据平方误差最小准则，每个区域上的最优输出值应为：

$c_{1}=\frac{1}{N_{1} } \sum_{x_{i}\in N_{1} } y_{i}$ , $c_{2}=\frac{1}{N_{2} } \sum_{x_{i}\in N_{2} } y_{i}$ 。总体的平方误差为：

$m(s)=min[min_{c1} \sum_{x_{i} \in R_{1} }(y_{i} -c1)^2+min_{c2} \sum_{x_{i} \in R_{2} }(y_{i} -c2)^2 ]$ 。

则选取的步骤是：将该特征的取值按大小排序，通常在两个相邻值之间取一个划分点s，计算 $m(s)$ ,找到最小的对应的s，就是该特征下的最优划分点；遍历所有的特征，找到所有特征中最小的 $m(s)$ ，构成的 $(j,s)$ 就是最优切分变量的最优划分点。

找到最优划分点后，分别对每一个区域重复上述步骤，直至平方误差低于设定的阈值，整个树构建完毕。

（回归树这里参考了https://blog.csdn.net/aaa_aaa1sdf/article/details/81588382这篇里的例子，就很好懂了。）

分类树：依据基尼指数选择最优划分特征。

假设样本为第k类的概率为 $p_{k}$ ,则基尼指数为：

$Gini(p)=\sum_{k=1}^K p_{k} (1-p_{k})$ , 反应了从一个数据集中随机抽取两个样本，其类别不一致的概率。由此可知，基尼指数越小，说明数据集纯度越高（与熵类似）。

CART分类树选取特征不同于ID3等算法直接选某一个特征作为划分点，它是根据某个特征是否取其中某个值划分成两个叉（因为是二叉树）。所以它的步骤是：

对每个特征的每个取值，根据是否将数据集分成两份，计算基尼指数：

$Gini(D,A)=\frac{\vert D1 \vert }{\vert D \vert } Gini(D1)+\frac{\vert D2 \vert }{\vert D \vert } Gini(D2)$ ,

选择基尼指数最小的特征及最优划分点，将数据集D分割到两个子结点中，对每个结点重复上述步骤。

2）CART剪枝：

拢共分两步：从底向上不断剪枝，形成子树序列；选择损失函数值最小的子树。

先说怎么生成子树序列吧，我觉得他这个思考的过程很牛的：

从整体树 $T_{0}$ 开始剪枝。对于 $T_{0}$ 内部任意结点t，

以t为单结点树的损失函数： $C_{\alpha }（t）=C(t)+\alpha$ ,

以t为根结点的子树 $T_{t}$ 的损失函数： $C_{\alpha }（T_{t} ）=C(T_{t} )+\alpha\vert T_{t} \vert$ ,可知，

当 $\alpha$ 等于0或者充分小时， $C_{\alpha }（T_{t} ）< C_{\alpha }（t ）$ ,

$\alpha$ 增大，到某一值时，有， $C_{\alpha }（T_{t} ）= C_{\alpha }（t ）$ ，

$\alpha$ 继续增大，有 $C_{\alpha }（T_{t} ）> C_{\alpha }（t ）$ 。

即当 $\alpha =\frac{C_{\alpha }（t ）-C_{\alpha }（T_{t} ）}{\vert T_{t} \vert-1 }$ 时， $T_{t}$ 与t有相同的损失函数，而t比 $T_{t}$ 的结点少，所以可以剪枝。

因此我们如果找到一些这样的 $\alpha$ 值，就可以剪枝了。

所以具体的步骤是：对 $T_{0}$ 的每一个内部节点t，计算 $g(t) =\frac{C_{\alpha }（t ）-C_{\alpha }（T_{t} ）}{\vert T_{t} \vert-1 }$ ,先减去g(t)最小的 $T_{t}$ （从小到大一点一点剪），得到子树 $T_{1}$ ，这个g(t)设为 $\alpha _{1}$ 。依次减去所有g(t)的 $T_{t}$ ，得到一个子树序列 $\left\{ T_{0}，T_{1}，...，T_{n} \right\}$ 。

选择最优子树：

使用验证集，计算子树序列中各棵子树的平方误差或基尼指数，最小的子树为最优子树，对应的 $\alpha$ 也确定了。

本章完。

一点补充：

书中说，决策树学习的损失函数通常是正则化的极大似然函数。不是很理解，看到有大佬推导出，经验误差函数（也就是损失函数的第一项）是通过对数极大似然函数取反得到的。在概率模型中，二者是相同的概念（只有符号不一样）。其意义作者个人理解为：先对各叶节点之间进行极大似然估计，再对各叶节点内部进行极大似然估计，由此得到决策树模型中的极大似然函数。

妈耶，最后一句没看懂，还要去补一补极大似然估计的概念……

大佬链接在这里https://blog.csdn.net/wzk1996/article/details/81941572