简述

决策树本事上是一棵树，树的根节点包含了样本全集，从根出发到叶节点的路径对应了一个判定测试序列，而每个内部节点包含的样本集合则根据相应属性的测试结果而划分到子节点中。

注：决策树在 Coursera 和 Stanford 的公开课中并未提到，相关知识完全通过《机器学习》和互联网获得。

基本过程

讲基本过程之前，先来搞懂“先验概率”、“后验概率”、“似然函数”。

先验概率：就是常识、经验或者统计方法所透露出的“因”的概率，$p$(原因)，就是先验概率。

后验概率：这种先知道结果，然后由结果估计原因的概率分布，$p$(原因|结果)，就是后验概率。

似然函数：这种先确定原因，根据原因来估计结果的固有性质的可能性（likelihood），是对固有性质的拟合程度，$L$(结果|原因)，就是似然估计。

于是有了贝叶斯公式：

$p(\theta|x)=\frac{p(x|\theta)p(\theta)}{p(x)}$

$x$ ：观察得到的数据（结果）

$\theta$ ：决定数据分布的参数（原因）

$p(\theta|x)$ ：后验概率（posterior probability）

$p(\theta)$ ：先验概率（prior probability）

$p(x|\theta)​$ ：似然估计（likelihood）

$p(x)$ ：evidence

懂了上述概念，接着讲讲基本流程，训练集 $D=\{(x_1,y_1),(x_2,y_2), \cdots , (x_m,y_m)\}$; 属性集 $A=\{a_1,a_2, \cdots,a_d\}$：

函数 TreeGenerate(D,A)
生成节点node:
if D 中的样本全属于同一类别 C then
    将node标记为C类叶子节点；return
end if
if A = ϕ OR D 中样本在 A 上取值相同 then
    将 node 标记为叶节点，其类别标记为 D 中样本数最多的类；return
end if
从A中选则最优划分属性a*;
for a* 的每一个值a*(v) do
    为node生成一个分支；令Dv表示D中在a*上取值为a*(v)的样本子集；
    if Dv 为空 then
        将分支节点标记为叶节点，其类别标记为D中样本最多的类；return
    else
        以Tree(Dv,A\{a*})为分支节点
    end if
end for

决策数的生成是一个递归的过程，在决策树基本算法中有三种情况会导致递归返回：

1. 当前节点包含的样本种类属于同一类别，无需划分
2. 当前样本属性集为空，或者所有样本在所有属性上的取值相同，无法划分
3. 当前节点包含的样本集合为空，不能划分

划分选择

上面的基本过程的的本质是构建一课树，核心是划分最优属性 $a_*$ ,且希望决策树的分支节点所包含的样本尽可能的属于同一类别，即节点的“纯度”尽可能高。

划分选择有多种算法，如：ID3、C4.5。

ID3

在一开始 我们提一下熵。熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，熵是对不确定性的测量。但是在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。
信息熵(information entropy)是度量样本集合纯度最常用的一种指标，假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,\cdots , |\mathcal{Y}|)$ ，则 $D$ 的信息熵定义为：

$Ent(D)=-\sum^{|\mathcal{Y}|}_{k=1}p_k\log_2p_k .$

Ent(D)的值越小，则D的纯度越高。

为了找出“纯度最大”的属性，我们引入“信息增熵”，简单来说就是“信息熵”与“条件熵”的差值，即信息增益代表了在一个条件下，信息复杂度（不确定性）减少的程度；表明了此条件的重要性。再给出“信息增熵”的定义：

$Gain(D,a)=Ent(D)-\sum^{V}_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$

所以：有了

$a_* = \mathop{\argmax} \limits_{a \in A}{Gain(D,a)}$

C4.5

为了解决信息增熵准则对可取数目较多的属性有所偏好，著名的 C4.5 决策树算法 [Quinlan,1993] 使用“增益率” （gain ration）来选择最优划分属性。

增益率定义为：

$Gain \_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

其中：

$\rm{IV}(a)=-\sum^V_{v=1}\frac{|\it{D}^{\it{v}}|}{|\it{D}|}\log_2{\frac{|\it{D}^{\it{v}}|}{|\it{D}|}}$

IV(a) 称为属性 a 的固有值，属性 a 的可能取值数目越多，则 IV(a) 的值通常会越大。增益率准则对取值数目较少的属性有所偏好。

因此，使用启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART

CART树(Classification and Regression Tree)使用基尼指数来选择属性的划分，通过基尼值来度量数据集的纯度
基尼值：

$\begin{aligned} Gini(D)&=\sum^{|\mathcal{Y}|}_{k=1}\sum_{k'\neq k}p_k p_{k'}\\\\ &=1-\sum^{|\mathcal{Y}|}_{k=1}p_k^2 \end{aligned}$

反映了从数据集 $D$ 中取出两个样本，不为同一种类的概率，因此 Gini(D) 越小，数据集的纯度越高。

转化成与“信息增熵”相似的定义：

$Gini\_index(D,a)=\sum^{V}_{v=1}\frac{|D^v|}{|D|}Gini(D^v)$

于是最优划分属性为：

$a_* = \mathop{\argmin} \limits_{a \in A}{Gini\\\_index(D,a)}$

防止过拟合

预剪枝

预剪枝是在决策树生成的过程中，对每个结点在划分前先进行预估，若当前结点的划分不能使决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。

即对比当前验证集精度与生成子决策树后的精度

后剪枝

后剪枝是先从训练集中生成一颗完整的决策树，然后自底向上的对非叶子结点进行考察，若将改结点对应的子树替换为叶子结点能提高泛化能力，则进行替换。

即，对每一分支，对比当前精度与去掉决策子树的精度。

优缺点

后剪枝决策树比预剪枝决策树保留了更多的分支，一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是生成完全决策树之后进行的，并且要自底向上地对书中的所有非叶子节点进行逐一考察，因此其训练时间开销比末剪纸决策树和预剪枝决策树都要大得多。

连续值缺失值处理

连续值处理

由于连续属性的可能取值不再有限，因此不能直接根据连续属性的可能取值进行划分。我们可以使用离散化技术对其进行处理。
二分法：
给定样本集 $D$ ，和连续属性 $a$ ，$a$ 在 $D$ 上出现了 $n$ 个不同的取值，
将其排序 ${a_1,a_2,\cdots,a_n}$ ，然后基于划分点 $t$ 将样本划分为 $D−t$ 和 $D+t$ ，$D−t$ 包括了在属性 $a$ 上取值小于 $t$ 的样本，$D+t$ 反之。即

$T_a=\{\frac{a_i+a_{i+1}}{2}|1 \leq i \leq n−1\}$

通常我们取区间 $[a^i,a^{a+1})$ 的中位点作为候选划分点。

然后有：

$\begin{aligned} Gain(D,a)&=\max \limits_{t \in T_a} Gain(D,a,t)\\ &=\max \limits_{t \in T_a} Ent(D)-\sum_{\lambda in \{-,+\}} \frac{|D^{\lambda}_t|}{|D|}Ent(D^{\lambda}_t) \end{aligned}$

缺失值处理

现实任务中常常会遇到不完整的样本，也就是样本中的某些属性值缺失的情况，最简单的方法是直接去除缺失的数据，但是这是对数据信息的极大浪费，我们可以考虑下利用有缺失属性值的样本来进行学习。
需解决的问题：

1. 在属性值缺失的情况下进行划分属性的选择
2. 给定划分属性，若样本在该属性上的值缺失，如何进行划分

给定训练集 $D$ ,属性集 $a$ ,令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。

对问题一：可依据 $\tilde{D}$ 来判断属性的优劣。假定属性 $a$ 有 $V$ 个可取的值 $\{a^1,a^2, \cdots , a^V\}$ ，令 $\tilde{D}^v$ 表示 $\tilde{D}$ 中在属性 $a$ 上的取值为 $a^v$ 的样本集， $\tilde{D}_k$ 表示 $\tilde{D}$ 中属于第 $k$ 类的样本子集。

显然有 $ \tilde{D} = \bigcup^{|\mathcal{Y}|}_{k=1}\tilde{D}_k,\tilde{D} = \bigcup^{|V|}_{v=1}\tilde{D} ^v$ 。

假定给每个样本一个权重 $w_x$ ，并定义：

$\begin{aligned} \rho&=\frac{\sum_{x \in \tilde{D} }w_x}{\sum_{x \in D}w_x}\\\\ \tilde{p}_k& = \frac{\sum_{x \in \tilde{D}_k }w_x}{\sum_{x \in D}w_x} &(1 \leq k \leq |\mathcal{Y}|)\\\\ \tilde{r}_v& = \frac{\sum_{x \in \tilde{D}^v }w_x}{\sum_{x \in D}w_x} &(1 \leq k \leq |\mathcal{Y}|) \end{aligned}$

$\rho$ ：在属性 $a$ 中 ，无缺失值所占样本比例；

$\tilde{p}_k$ ：无缺失值样本中第 $k$ 类所占的比例；

$\tilde{r}_v$ ：无缺失值样本中在属性 $a$ 上的取值 $a^v$ 的样本所占比例

显然有，$\sum^{ |\mathcal{Y}|}_{k=1} \tilde{p}_k=1,\sum^{ |V|}_{c=1} \tilde{r}_v=1$ 。

于是可以推广信息增益的计算式为：

$\begin{aligned} Gain(D,a)&=\rho \times Gain(\tilde{D},a)\\\\ &=\rho \times \left( Ent \left( \tilde{D} \right)-\sum^{V}_{v=1}\tilde{r}_vEnt(\tilde{D} ^v) \right) \end{aligned}$

其中：

$Ent(\tilde{D}) = -\sum^{|\mathcal{Y}|}_{k=1}\tilde{p}_k \log_2\tilde{p}\_k$

对问题二，样本 $x$ 在属性 $a$ 上的取值缺失，则将 $x$ 划分到所有叶子结点中，将权值变为 $\tilde{r}_v \cdot w_x$ 意思将同一个样本以不同的概率划入到同的子结点中去。