决策树学习通常包含三个步骤：特征选择、决策树的生成、决策树的修剪。

决策树学习的思想主要来源于：

由Quinlan提出的ID3算法和C4.5算法
由Breiman等人提出的CART算法

决策树模型与学习

决策树模型

决策树由节点（node）和有向边（directed edge）组成。

节点分为内部节点（表示特征/属性）和叶子节点（表示分类）。

> 决策树与if-then规则

从根节点到叶子节点对应一条路径，亦即一条规则，不同规则间互斥，所有规则组成全体，即互斥完备性。

> 决策树与条件概率分布

给定特征条件下类的条件概率分布。

决策树分类时强行将样本分到条件概率最大的那一类中去。

决策树学习

给定训练数据集
$$
D = { (x_1, y_1),(x_2,y_2), \cdots, (x_N,y_N) }
$$
其中

$x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$为输入向量（特征向量），$n$为样本的特征维度
$y_i \in { 1,2,\cdots,K }$为每个样本的类标记，$K$为总类数
$i=1,2,\cdots,N$，$N$为样本容量

与训练数据集不矛盾的决策树可能有多个，也可能没有；我们需要求矛盾最小、对测试集泛化能力较高的那个决策树。

特征选择

经典的特征选择准则有两个：信息增益，信息增益比。

信息增益

熵&经验熵

在信息论和概率统计中，熵（Entropy）是随机变量不确定性的度量。

设$X$是有限取值的离散型随机变量，其概率分布为
$$
P(X=x_i)=p_i \text{, $i=1,2,\cdots,n$}
$$
随机变量$X$的熵为
$$
H(X)=-\sum_{i=1}^N p_i \log p_i \text{, 特别的 $0 \log 0 = 0$}
$$
由熵的定义可知，随机变量的熵（不确定性）与随机变量的取值无关。这其实不难理解：确定性变量是随机性变量的一种特例，对于确定性变量取值1还是1000它们的不确定性应该是一样的，都为0。

熵的单位：bit（当对数底为2时）或者nat（当对数底为$e$时）。

当随机变量$X$完全确定（$P(X=x_k)=1$且$P(X=x_{\text{else}})=0$）或者完全不确定（$P(X=x_{\text{any}})=1/n$）时，$H(X)$取得最小值（0）或者最大值（$\log n$）。

当随机变量只取0、1时
$$
H(p) = -p \log_2 p - (1-p) \log_2 (1-p)
$$

如果此随机变量的熵值通过极大似然估计得到，称之为经验熵。

条件熵&经验条件熵

条件熵（Conditional Entropy）

设随机变量$X$和$Y$的联合分布为
$$
P(X=x_i, Y=y_j) = p_{ij}, i=1,2,\cdots,n;j=1,2,\cdots,m
$$
条件熵$H(Y|X)$表示已知随机变量$X$的条件下随机变量$Y$的不确定性
$$
H(Y|X) = \sum_{i=1}^n [ P(X=x_i) \cdot H(Y|X=x_i) ]
$$
如果随机变量$X$和$Y$独立，则$H(Y|X=x_i)=H(Y)$，此时条件熵
$$
H(Y|X) = \sum_{i=1}^n [ P(X=x_i) \cdot H(Y) ] = H(Y)
$$
如果随机变量$Y$的条件熵通过极大似然估计得到，称之为经验条件熵。

经验之意，即从观察数据中进行推断。

我们将随机变量Y的熵与已知X条件下Y的条件熵的差称之为互信息（Mutual Information）。

信息增益

信息增益（Information Gain）指，当得知特征$X$的信息时，类$Y$不确定性减少的程度。

特征A对训练数据集D的信息增益为
$$
g(D,A) = H(D) - H(D|A)
$$
决策树中信息增益的概念就相当于训练数据集中类与特征的互信息。

训练数据集中不同的特征具有不同的信息增益，信息增益较大的特征具有更强的分类能力。

计算信息增益举例：

类别的先验分布：$P(Y=是)=9/15=3/5$, $P(Y=否)=9/15=2/5$

类别的熵：$H(Y)=-3/5\log3/5-2/5\log2/5 = 0.971$

该训练数据集有4个特征：年龄、有工作、有自己的房子、信贷情况，分别用A、B、C、D表示。

以年龄为例计算其对训练数据集的信息增益：

随机变量取值数值化（有序分类）：青年 $\to$ 1, 中年 $\to$ 2，老年 $\to$ 3
年龄的先验分布: $P(A=1)=P(A=2)=P(A=3)=1/3$
训练数据集D在年龄A已知时的条件概率分布：
$$
\begin{split}
P(Y=0|A=1)=3/5, P(Y=1|A=1)=2/5 \\
P(Y=0|A=2)=2/5, P(Y=1|A=2)=3/5 \\
P(Y=0|A=3)=1/5, P(Y=1|A=3)=4/5
\end{split}
$$
此时
$$
\begin{split}
H(Y|A=1) &= - 3/5 \log_2 3/5 - 2/5 \log_2 2/5 = 0.9709506 \\
H(Y|A=2) &= - 2/5 \log_2 2/5 - 3/5 \log_2 3/5 = 0.9709506 \\
H(Y|A=3) &= - 1/5 \log_2 1/5 - 4/5 \log_2 4/5 = 0.7219281
\end{split}
$$

训练数据集D在年龄A已知时的条件熵：
$$
\begin{split}
H(Y|A) &= P(A=1)H(Y|A=1) + P(A=2)H(Y|A=2) + P(A=3)H(Y|A=3) \\
&= 1/3 \times 0.9709506 + 1/3 \times 0.9709506 + 1/3 \times 0.7219281 \\
&= 0.8879431 \\
\end{split}
$$
信息增益
$$
\begin{split}
g(Y,A) &= H(Y) - H(Y|A) \\
&= 0.971 - 0.8879431 \\
&= 0.083
\end{split}
$$
同理得
$$
\begin{split}
g(Y,B) &= 0.324 \\
g(Y,C) &= 0.420 \\
g(Y,D) &= 0.363
\end{split}
$$
经过比较，特征C（有自己的房子）对训练数据集的信息增益最大，所以选择特征C作为最优的分类特征。

信息增益比

信息增益的偏向性

根据信息增益的定义$H(D,A)=H(D)-H(D|A)$，如果数据集D中某个特征A的采样值为恒定常数，那么$H(D|A)=0$，即$H(D,A)=H(D)$，此时特征A对数据集D的信息增益达到最大值——D的熵值。那么我们应该选择特征A作为最优划分特征吗？显然不。这是信息增益在描述采样值为常数的特征时的弊端。除此之外，信息增益在计算连续型随机变量时也会遇到不小的问题。

所以信息增益适合于计算离散特征，并且该随机变量取值的采样数不宜过少。

信息增益的相对性

所谓的信息增益，字面意思就是确定性的增加量，这个确定性的增加是相对数据集D的熵的，这意味着，D的熵越大，信息增益就可能越大；反之越小。

信息增益比的定义

于是，我们将信息增益除以数据集的熵，用相对的确定性增量来描述最优分类特征：
$$
g_R(D,A) = \frac{g(D,A)}{H(D)} = \frac{H(D)-H(D|A)}{H(D)} = 1 - \frac{H(D|A)}{H(D)}
$$

决策树的生成

决策树学习的两个经典算法：ID3算法、C4.5算法。

生成算法只能用来生成树，十分容易过拟合。

生成的树需要进行剪枝，去拟合。

ID3算法

算法核心是在决策树的各个节点应用信息增益的准则选择特征。

根据信息增益选择特征的方法还是属于极大似然。

> ID3算法

CONST 信息增益阈值
DEF ID3算法(数据集D, 特征集合A):
    IF D中所有样本属于同一类C:
        T为单节点树，将C作为该节点的类标记，返回T
    ELSE IF A为空：
        T为单节点树，将D中样本数最多的那个类作为该节点的类标记，返回T
    ELSE:
        计算特征集合A中各个特征对数据集D的信息增益，确定信息增益最大的特征Ag
    IF Ag < 信息增益阈值:
        T为单节点树，将D中样本数最多的那个类作为该节点的类标记，返回T
    ELSE:
        FOR 采样值v IN 特征Ag中的所有采样值的集合:
            从数据集D中划分出特征Ag值为v的子集Dv
            T的一个子节点 = 递归调用 ID3算法(数据集Dv, 特征集合{A-Ag})
        返回T

C4.5算法

将ID3算法中的 信息增益 替换为 信息增益比 即可。

为什么叫做C4.5算法而不叫ID4算法呢？据说作者发表完ID3算法后此领域过于火爆导致ID4、ID5等名字有人用了。

决策树的剪枝

前面提到，决策树的生成算法倾向于拟合训练数据，极易出现过拟合。

剪枝（Pruning）即考虑模型的复杂度，对生成的树进行简化。

剪枝通过极小化 损失函数 实现。

> 剪枝原理

假设：树$T$的叶子节点的个数为$|T|$，$t$是树$T$的一个叶子节点，该叶子节点有$N_t$个样本点，其中属于第$k$类的样本点有$N_{tk}$个。

则，叶子节点$t$的经验熵为
$$
H_t(T) = - \sum_{k=1}^K \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}
$$
决策树学习的损失函数为
$$
L_\alpha(T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T|
$$
每个叶子节点的样本数越少、经验熵越小，同时总叶子节点数越少，损失越小。

这里损失函数由两部分组成：