决策树

熵(Entropy)

信息熵是信息的量化度量，举一个例子：我任意从 1~8 中任选一个数，让你来猜。你可能会提问“你猜的数字在 1~4 中吗？”通过得到的答案是或否，就可以缩小你的选择范围。只需这样回答三次 $(\log_28=3)$，他便可以知道你所选择的数字具体是哪个。那么 $3$ 就是刚才举的例子中“我刚选了一个数，你来猜呀！”这个信息的量化度量，用比特(bit)来表示。

信息论的创始人香农老爷子给出了一个公式，可以更准确的描述信息的量化度量，被称作信息熵，公式如下：

$$H(X) = -\sum_{x\in X}P(x)\log P(x)$$

其中 $X$ 为随机变量，$\log$ 以 $2$ 为底。

决策树(Decision Tree)

我第一次听见决策树这个名词时在管理学的课上讲的，但是我没有听，没想到在机器学习里面还有这个东西。

决策树在机器学习中比较常见，可以解决分类与回归问题。先看下面就“在实验室干点什么”为主题而生成的决策树：

决策树分为根节点，中间节点，叶节点。根节点是决策树的起源，也是第一个对特征的决策；每个叶节点都是分类问题对应的标签，也对应每个样本的分类结果。

假设现在有一个二分类问题，根据已有标签的样本的周老师的西瓜是不是好瓜进行决策树分类。现有西瓜数据集如下：

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
7	乌黑	稍蜷	浊响	清晰	稍凹	软粘	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	沉闷	清晰	平坦	软粘	否
11	浅白	硬挺	沉闷	模糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

现在想构建一个判断次数尽可能小、可以对瓜进行分类的决策树，先从哪里开始呢？开始。之前提到的熵是用来描述信息确定性的度量，在决策树中可以表示样本的纯度，纯度越高，信息的熵就越小；相反，熵就越大。那么分类结果的好换就可以用熵的大小来表示。熵的公式为：

$$\text{Ent}(X) = -\sum_{k=1}^{|\mathcal Y|}p_k\log p_k$$

其中$X$表示西瓜样本全体，$|\mathcal Y|$表示样本空间中所有样本的类别个数，当然在二分类问题中$|\mathcal Y| = 2$。

信息增益(Information Gain)

信息增益是指在某一节点对属性$a$进行判定前后熵的变化，公式为：

$$\text{Gain}(X,a_j) = \text{Ent}(X) - \sum_{v=1}^V\frac{m^v}{m}\text{Ent}(X^v)$$

其中样本的第$j$个属性$a_j$有$V$个可能的取值${a^1_j,a^2_j,\cdots,a^V_j}$，$m$为总体样本数，$X^v$为属性$a=v$的样本，$m^v$为总样本中属性$a=v$的样本个数。比如对于属性“色泽”来说，分为青绿、乌黑、浅白三种可能取值，那么$V=3$，样本中有6个青绿色的瓜，则$m^1=6$。信息增益就是我们我握在手中判断先对那个样本属性开始的重要依据。

就以上面的例子来说，当决策开始，样本整体$X$未进行判断时，17个瓜里面有8个好瓜，9个坏瓜，则根节点的信息熵为：

$$\text{End}(X)=-\sum_{i=1}^{2}p_k\log p_k=-(\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17})=0.998$$

之后就是计算决策树的根节点以属性$a_j$进行决策得到的信息增益。以属性“色泽”为例，先求样本经过划分后每个子集的信息熵：

$$\begin{align} \text{Ent}(X^1) &= -\left(\frac3 6\log_2 \frac3 6 + \frac3 6\log_2 \frac3 6\right) = 1.000\\ \text{Ent}(X^2) &= -\left(\frac4 6\log_2 \frac4 6 + \frac2 6\log_2 \frac2 6\right) = 0.918\\ \text{Ent}(X^3) &= -\left(\frac1 5\log_2 \frac1 5 + \frac4 5\log_2 \frac4 5\right) = 0.722 \end{align}$$

之后就可以求得属性“色泽”的信息增益：

$$\begin{align} \text{Gain}(X,a_j=色泽) &= \text{Ent}(X) - \sum_{v=1}^3\frac{m^v}{m}\text{Ent}(X^v)\\ &=0.998-\left(\frac{6}{17}\times1.000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722\right)\\ &=0.109 \end{align}$$

同样的，还可以求出其他属性的信息增益。信息增益越大，则经过属性判断后的信息熵就越小，每个叶节点的数据就越“纯净”，那么决策树效率就越高。所以我们需要找到最大的信息增益对应的属性$\hat a_j=\arg\max_j\text{Gain}(X,a_j)$来进行划分判断。依据信息增益进行属性选择的决策树也被称为ID3决策树算法。

增益率(Gain Ratio)

ID3决策树看似很优秀，但实际上也有着不小的瑕疵：如果我把编号也当作像本的属性来进行判断，那么就会得到$\text{Gain}(X,编号)=\text{Ent}(X)-0$。那么编号属性就会被首先选中。很显然这不是我们想要的结果。

我们运用可以运用信息增益率来选择最优划分属性，定义为：

$$\text{Gain ratio}(X,a_j) = \frac{\text{Gain}(X,a_j)}{\text{IV}(a_j)}$$

其中$\text{IV}(a_j)$为属性$a_j$的固有值(intrinsic value)

$$\text{IV}(a_j) = - \sum_{v=1}^V\frac{m^v}{m}\log\frac{m^v}{m}$$

当属性$a_j$可能取值越多，则$\text{IV}(a_j)$就会越大，导致$\text{Gain ratio}(X,a_j)$越小，可以修正ID3决策树的缺陷，这种据增益率进行属性选择的决策树也被称为C4.5决策树算法。当然增益率会对有取值少的属性有所偏好，我们可以先找到信息增益率高于平均水平的属性，再比较信息增益得到最优划分属性。

基尼系数(Gini Index)

基尼系数是另一种判断信息是否“纯净”的指标，用$\text{Gini}(X)$从样本$X$中随机抽取两个样本标的签不一样的概率：

$$\text{Gini}(X)=\sum_{k=1}^{|\mathcal Y|} \sum_{k'\neq k}p_kp_{k'}=1-\sum_{k=1}^{|\mathcal Y|}p_k^2$$

属性$a_j$的基尼系数$\text{Gini index}(X,a_j)$定义为：

$$\text{Gini index}(X,a_j) = \sum_{v=1}^V \frac {m^v} {m}\text{Gini}(X^v)$$

与信息增益相似，可以求出其他属性的基尼系数进行比较。基尼系数越小，每个叶节点的数据就越“纯净”。所以我们需要找到最小的基尼系数对应的属性$\hat a_j=\arg\min_j\text{Gini index}(X,a_j)$来进行划分判断。依据信息增益进行属性选择的决策树也被称为CART决策树算法。

剪枝(Pruning)

在运筹学整数规划的部分接触过分支定界法，在进行分支选择时，会找尽可能最优的目标值进行分支，这是因为这样可以最快找到最优解，减少计算时间。为了防止决策树深度过深而过拟合，需要对决策树进行剪枝操作。剪枝分为预剪枝与后剪枝两种策略。

预剪枝

预剪枝是指决策树在对某个节点进行划分之前，首先对每个节点进行估计，若当前节点划分后不能到来更高的准确率，那么就停止划分该节点。

将西瓜数据集划分为训练集（标号没加粗）与测试集（标号加粗），以属性“色泽”为例，对数据集进行划分：

在根据属性“色泽”划分后，测试集的精度提升，说明该决策树的泛化度提高。接下来对最右侧节点根据“敲声”进行划分，测试集的精度降低了，那么就不能用“敲声”进行划分。同样的，对其它节点也进行类似的判断。预剪枝是基于“贪心”的本质，禁止比已有树精度低的属性进行判断，这也给决策树带来欠拟合的风险。

后剪枝

后剪枝是指一棵决策树在训练完成后，从下至上对每个中间节点的测试集精度进行比较，如果剪枝之后有所提高或者不变，那么则进行剪枝处理。