一、基本流程

决策树（decision tree） 是一种常见的机器学习方法。一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶节点对应于决策结果，其他每个结点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强的决策树，算法如下：

input: 
	训练集 D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)};
	属性集 A={a_1,a_2,...,a_d}.

process: 
	def TreeGenerate(D, A)
		生成结点 node；
		if D 中样本全属于同一类别 C
			将 node 标记为 C 类叶结点
			return
		if A 为空 or D 中样本在 A 上取值相同
			将 node 标记为叶结点，其类别标记为 D 中样本数量最多的类
		从 A 中选择最优划分属性 a_star
		for a_v in a_star:
			为 node 生成一个分支
			令 D_v 表示 D 中在 a_star 上取值为 a_v 的样本子集
			if D_v 为空:
				将分支结点标记为叶结点，其类别标记为 D 中样本最多的类
			else:
				以 TreeGenerate(D_v, A\{a_star}) 为分支节点

output:
	以 node 为根结点的一颗决策树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

由此可见，决策树的生成是一个递归过程。

二、划分选择

从算法中可以看出，决策树学习的关键是划分最优属性。一般来说，随着划分过程不断进行，要使决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（purity） 越来越高。

1. 信息增益

信息熵（information entropy） 是度量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k(k=1,2,...,|y|)$ ，则 $D$ 的信息熵定义为：

$$Ent(D)=-\sum _{k=1}^{|y|}{p}_k{\log }_2{p}_k$$

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

假定离散属性 $a$ 有 $V$ 个可能的取值 $a^1,a^2,...,a^V$ ，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。利用上式可以计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$ ，即样本数越多的分支结点的影响越大，于是可计算出用属性 $a$ 对样本集 $D$ 进行划分所获得的信息增益（information gain）：

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

信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的纯度提升越大。因此，可用信息增益来进行决策树的划分属性选择。

2. 增益率

信息增益准则对可取值树木较多的属性有所偏好，为减少这种偏好可能带来的不利影响，可以使用增益率（gain ratio）：

$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\text{\hspace{1em}(4.2)}$$

$$IV(a)=-\sum _{v=1}^V=\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$

其中 $IV(a)$ 称为 $a$ 的固有值（intrinsic value）。属性 $a$ 的可能取值数目越多，则 $IV(a)$ 的值通常会越大。需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此 $C4.5$ 算法使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3. 基尼指数

基尼值可以度量数据集纯度：

$$Gini(D)=\sum _{k=1}^{|y|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-\sum _{k=1}^{|y|}{p}_k^2$$

$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此基尼值越小则数据集纯度越高。基尼指数（Gini index） 定义：

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

因此在侯选属性集合 $A$ 中，选择使基尼指数最小的属性作为最优划分属性。

三、剪枝处理

剪枝（pruning） 是决策树学习算法中解决过拟合的主要手段。

决策树剪枝的基本策略有预剪枝（prepruning） 和后剪枝（post-pruning）。预剪枝指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

四、连续与缺失值

1. 连续值处理

要想使用连续属性来生成决策树，就需要对连续值进行处理。最简单的策略是采用二分法（bi-partition）。

假定有一个连续属性 $a$ ，它具有多个不同的取值，将这些值从小到大排序，使得其在某个划分点 $t$ 可以对样本集 $D$ 进行划分，此时 $t$ 就等于相邻两被划分元素取值的均值：

$$T_a=\left\{\frac{a^i+a^{i+1}}{2}|1\le i\le n-1\right\}$$

为选取最优的划分点，可对式 4.2 进行改造：

G a i n ( D , a ) = max ⁡ t ∈ T a G a i n ( D , a , t ) = max ⁡ t ∈ T a E n t ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ ) Gain(D,a)=\max_{t\in T_a}Gain(D,a,t)=\max_{t\in T_a}Ent(D)-\sum_{\lambda\in\left\{-,+\right\}}\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda) Gain(D,a)=t∈Ta​max​Gain(D,a,t)=t∈Ta​max​Ent(D)−λ∈{−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)

其中 $Gain(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益，因此可选择使其最大化的划分点。

2. 缺失值处理

如何在属性值缺失的情况下进行划分属性选择？

给定训练集 $D$ 和属性 $a$ ，令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。假定属性 $a$ 有 $V$ 个可取值 $\left\{a^1,a^2,...,a^V\right\}$ ，令 ${\tilde{D}}^v$ 表示 $\tilde{D}$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集，${\tilde{D}}_k$ 表示 $\tilde{D}$ 中属于第 $k(k=1,2,...,|\mathcal{Y}|)$ 类的样本子集，则显然有 $\tilde{D}={\bigcup }_{k=1}^{|y|}{\tilde{D}}_k$ ，$\tilde{D}={\bigcup }_{v=1}^V{\tilde{D}}^v$ 。假定为每个样本 $x$ 赋予一个权重 $w_x$ ，并定义：

$$\rho =\frac{{\sum }_{x\in \tilde{D}}{w}_x}{{\sum }_{x\in D}{w}_x}$$

$${\tilde{\rho }}_k=\frac{{\sum }_{x\in {\tilde{D}}_k}{w}_x}{{\sum }_{x\in D}{w}_x}(1\le k\le |\mathcal{Y}|)$$

$${\tilde{r}}_v=\frac{{\sum }_{x\in {\tilde{D}}^v}{w}_x}{{\sum }_{x\in D}{w}_x}(1\le v\le V)$$

直观来看，堆属性 $a$ ，$\rho$ 表示无缺失值样本所占的比例，${\tilde{p}}_k$ 表示无缺失值样本中第 $k$ 类所占的比例，${\tilde{r}}_v$ 表示无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占的比例。显然 ${\sum }_{k=1}^{|\mathcal{Y}|}{\tilde{p}}_k=1$ ，${\sum }_{v=1}^V{\tilde{r}}_v=1$ 。基于上述定义，可对式 4.2 进行改造：

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

其中，由式 4.1 ，有：

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

给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

若样本 $x$ 在划分属性 $a$ 上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_x$ 。若样本 $x$ 在划分属性 $a$ 上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为 ${\tilde{r}}_v\cdot w_x$ 。直观的看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

五、多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则 $d$ 个属性描述的样本就对应了 $d$ 维空间中的一个数据点，对样本分类则意味着在这个空间中寻找不同类样本之间的分类边界。决策树所形成分类边界的特点是轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。

因此，这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但是当学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似。

此时决策树非常复杂，由于要进行大量的属性测试，因此预测时间开销很大。若能使用斜的划分边界，如上图红色线断所示，决策树模型将被简化。多变量决策树（multivariate decision tree） 可以实现这个目标。在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，即每个叶结点是一个形如 ${\sum }_{i=1}^d{w}_i{a}_i=t$ 的线性分类器，其中 $w_i$ 是属性 $a_i$ 的权重，$w_i$ 和 $t$ 可在该结点所含的样本集和属性集上学得。于是，与传统的单决策树（univariate decision tree） 不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是建立一个合适的线性分类器。