1、概述

决策树（decision tree）： 是一种基本的分类与回归方法，此处主要讨论分类的决策树。

在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-then的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

2、决策树模型

定义： 分类决策树模型是一种描述对实例进行分类的树形结构。

决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类。 一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中，圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。

下图为决策树示意图，圆点——内部节点，方框——叶节点

上节介绍的k-近邻算法可以完成很多分类任务，但是其最大的缺点是无法给出数据的内在含义，决策树的优势在于数据形式非常容易理解。

3、决策树学习

假设给定训练数据集：

$D=\{ (x_1 ,y_1 ),(x_2,y_2 ),⋯,(x_N,y_N) \}$D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}
其中，$x_i=(x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T$xi​=(xi(1)​,xi(2)​,...,xi(n)​)T 为输入实例，即特征向量，n为特征个数，$y_i \in \{ 1, 2, ..., K\}$yi​∈{1,2,...,K} 为类标,$i=1,2,...,N;N为样本容量$i=1,2,...,N;N为样本容量。

• 决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

• 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。

• 决策树学习的损失函数：正则化的极大似然函数

• 决策树学习的策略：最小化损失函数

• 决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。

决策树学习的算法通常是一个递归地选择最优特征， 并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

1. 开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。

2. 如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去，如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。

3. 如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。

4. 最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

基本算法如下：

输入：
$\qquad$ 训练集： $D=\{ (x_1 ,y_1 ),(x_2,y_2 ),⋯,(x_N,y_N) \}$D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}
$\qquad$属性(特征)集：$A=\{ a_1,a_2,...,a_d \}$A={a1​,a2​,...,ad​}
过程：
$\qquad$ 函数$TreeGenerate(D,A)$TreeGenerate(D,A)
（ 1 ） 生成结点根node
（ 2 ） if D中样本全属于同一类别$C_k$Ck​ then
（ 3 ）$\qquad$ 将node标记为$C_k$Ck​ 类叶节点； return
（ 4 ）end if
（ 5 ）if $A = \varnothing$A=∅ OR D中样本在 A 上取值相同 then
（ 6 ）$\qquad$ 将node标记为叶结点，其类别标记为D中样本数最多的类 return
（ 7 ）end if
（ 8 ）从A中选择最优划分属性$a_*$a∗​
（ 9 ）for $a_*$a∗​ 的每一个值$a_*^v$a∗v​ do
（10）$\qquad$ 为node生成一个分支：令$D_v$Dv​表示D中在$a_*$a∗​上取值为$a_*^v$a∗v​的样本子集
（11 ）$\qquad$if $D_v$Dv​为空 then
（12）$\qquad$$\qquad$将分支结点标记为叶结点，其类别标记为D中样本最多的类
（13 ）$\qquad$else
（14 ）$\qquad$$\qquad$以$TreeGenerate(D_v, A - \{a_*\})$TreeGenerate(Dv​,A−{a∗​})为分支结点
（15 ）$\qquad$end if
（16）end for
输出：
$\qquad$ 以node为根节点的决策树

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

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

使用决策树做预测需要以下过程：

• 收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。

• 准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。

• 分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。

• 训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。

• 测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。

• 使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

4、决策树构建-三步骤

使用决策树做预测的每一步骤都很重要，数据收集不到位，将会导致没有足够的特征让我们构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，将会导致无法构建出分类效果好的决策树模型。从算法方面看，决策树的构建是我们的核心内容。

决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和决策树的修剪。

4.1 特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。

特征选择的准则是信息增益(information gain)或信息增益比。

那么，什么是信息增益？在讲解信息增益之前，让我们看一组实例，贷款申请样本数据表。
特征选择是决定用哪个特征来划分特征空间。

希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。

特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。

图5.3(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图5.3(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

4.1.1 熵(entropy)

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

设$X$X是一个取有限个值的离散随机变量，其概率分布为:
$P(X=x_i )=p_i,i=1,2,⋯,n$P(X=xi​)=pi​,i=1,2,⋯,n
则随机变量$X$X的熵定义为：
$H(X)=− \sum_{i=1}^np_ilogp_i$H(X)=−i=1∑n​pi​logpi​

4.1.2 条件熵(entropy)

条件熵$H(Y|X)$H(Y∣X)表示在已知随机变量$X$X的条件下随机变量$Y$Y的不确定性。

设有随机变量$(X, Y)$(X,Y)其联合概率分布为：
$P(X=x_i,Y=y_j)=p_{ij} ,i=1,2,...,n;j=1,2,...,m$P(X=xi​,Y=yj​)=pij​,i=1,2,...,n;j=1,2,...,m

随机变量$X$X给定的条件下随机变量$Y$Y的条件熵（conditional entropy）$H(Y|X)$H(Y∣X)，定义为$X$X给定条件下$Y$Y的条件概率分布的熵对$X$X的数学期望：
$H(Y|X) = \sum_{i = 1}^n p_iH(Y|X = x_i)$H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)

其中，$p_i=p(X=x_i),i=1,2,...,n$pi​=p(X=xi​),i=1,2,...,n

当熵和条件熵中的概率由数据估计（如极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，如果有0概率，令$0log0=0$0log0=0。

4.1.3 信息增益

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

特征A对训练数据集D的信息增益$g(D,A)$g(D,A)，定义为集合D的经验熵$H(D)$H(D)与特征A给定条件下D的经验条件熵$H(D|A)$H(D∣A)之差，即：

$g(D,A)=H(D)-H(D|A)$g(D,A)=H(D)−H(D∣A)

一般地，熵$H(Y)$H(Y)与条件熵$H(Y|X)$H(Y∣X)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

根据信息增益准则的特征选择方法：

对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

算法（信息增益算法）
输入：训练数据集$D$D和特征$A$A
输出：特征$A$A对训练数据集$D$D的信息增益$g(D,A)$g(D,A)

总结

优缺点：
计算复杂度不高
对中间缺失值不敏感
解释性强，在解释性方面甚至比线性回归更强
与传统的回归和分类方法相比，决策树更接近人的决策模式
可以用图形表示，非专业人士也可以轻松理解
可以直接处理定性的预测变量而不需创建哑变量
决策树的预测准确性一般比回归和分类方法弱，但可以通过用集成学习方法组合大量决策树，显著提升树的预测效果
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配的问题
适用数据类型：数值型和标称型

未完待续
参考资料：
李航《统计学习方法》