一句话解释：主要针对分类问题，对已有数据，根据各个特征的表现情况进行二分类（或多分类），从而形成一个像树一样的分类结构。

---

这一部分公式比较多，配合例题进行理解。

5.1 定义

一个决策树，大概就是像下图一样的一个结构：

如果学习过数据结构，你可能很快反映出，这不就是“树”结构吗？我感觉差不多就是这样，一个二分类或者多分类的树结构，遇到分叉点就是做选择题。

一般分三个步骤：特征选择，树的生成，树的剪枝，常用于分类问题。

5.2 特征选择

为什么要选择特征？

因为特征很多，从不同特征开始分类，得到的树的效果可能不一样。

选择特征

我们怎么知道哪个特征更适合分类呢？或者说怎样来判断一个特征是不是适合分类呢？

用信息增益来判断。

信息增益

熵

$H(X)=-\Sigma^n_{i=1}p_ilogp_i$ 也可以记作 H(p)

其中，X是取有限值的离散随机变量，概率分布为$P(x=x_i)=p_i,i=1,2,…,n$，当 $p_i$ 为 0 时，log 0 = 0.

意义：熵越大，随机变量的不确定性越大。也就是说，熵是用来衡量随机变量的不确定性的！

条件熵

$H(Y|X)=\Sigma^n_{i=1}p_iH(Y|X=x_i)$

表示的是，在已知X的条件下，Y的不确定性。

经验熵与经验条件熵

如果概率 Pi 是由数据估计（特别是极大似然估计）得到的，所对应的熵和条件熵就是经验熵和经验条件熵。

互信息（也就是信息增益）

熵与条件熵的差值。

该差值表示了不确定性减少的程度，减少越多就说明这个“条件”适合进行分类。

因此，信息增益大的特征具有更强的分类能力。

计算方法

输入：训练数据集D和特征A

对数据集的处理：

1. $|D|$表示样本容量
2. 有 $K $个类别，分别为$C_k$，每个类别中的样本个数为 $|C_k|$
3. 根据特征 A 可以将 D 划分为 n 个子集，分别为 $D_i$，$D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$

输出：特征A对训练数据集D的信息增益 $g(D,A)$

步骤：

1. 计算数据集 D 的经验熵 H(D)

   $H(D)=-\Sigma^K_{k=1}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$

2. 计算特征A对数据机D的经验条件熵 H(D|A)

   $H(D|A)=\Sigma^n_{i=1}\frac{|D_i|}{|D|}H(D_i)=-\Sigma^n_{i=1}\frac{|D_i|}{|D|}\Sigma^K_{i=1}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{D_i}$

3. 计算信息增益

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

简单实用，但是缺点是：偏向于选择取值较多的特征。

改进方法

使用信息增益比

信息增益比是信息增益与熵的比值。

信息增益比$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$

其中$H_A(D)=-\Sigma^n_{i=1}\frac{|D_i|}{|D|}log_2{|D_i|}{|D|}$，和前面的经验条件熵 H(D|A) 还是有点不一样的！

5.3 决策树的生成

ID3算法

上面的内容只是选择了一个最优的特征值，大概相当于找到了一个比较好的根节点，但是还没有生成决策树。

使用下面的算法生成决策树：

缺点：容易过拟合

C4.5算法

不同之处：选择信息增益比来选择特征。并不比ID3算法强多少。

5.4 决策树的剪枝

剪枝就是让决策树的枝干少一点——这样鲁棒性更好。

是减小过拟合的一种方法。

一般方法是引入损失函数，衡量剪枝前后的效果（也就是比较剪枝前后的损失函数），选择损失函数最小的方式生成决策树。

决策树的损失函数：

$C_\alpha(T)=\Sigma^{|T|}_{t=1}N_tH_t(T)+\alpha|T|$

代入经验熵$H_t(T)=-\Sigma_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$即可。

其中$\alpha$的作用是：

• $\alpha$越大，促使选择简单模型
• $\alpha$越小，促使选择复杂模型
• $\alpha$为0，不考虑模型复杂度

$|T|$表示模型复杂度。

5.5 CART算法

分类与回归树（classsification and regression tree）

本方法不细讲了，主要思想其实很相近，只是完整地提出了从特征选择、决策树生成到剪枝的全过程，并且只使用二叉树（不管有几个选择），所以泛化程度可能更好！

生成：递归地构建二叉决策树

如何对输入空间进行划分

特征选择：使用基尼指数最小化原则

最小二乘回归树生成算法

其实本方法和前面的算法在逻辑上有相似之处，但是最大的不同是，这里的每一个子树都是二叉树。

---

举个栗子！

下面是一个贷款申请的训练数据，我们先关注最后一栏，类别——就是是否同意贷款。

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

OK，根据上面这个表格，如果给你一个新的数据，你怎样判断是不是要贷款给ta呢？

一步步来进行：

首先可以看到特征比较多，从不同特征开始可以形成不同的决策树。

经验熵$H(D)=-\frac{9}{15}log_2\frac{9}{15}-\frac{6}{15}log_2\frac{6}{15}=0.971$计算信息增益：

（1）条件经验熵：$D_1,D_2,D_3$分别是$D$中$A_1$(年龄)取值为青年、中年和老年的样本子集。

$H(D_1)=-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5} \ H(D_2)=-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5} \ H(D_3)=-\frac{4}{5}log_2\frac{4}{5}-\frac{1}{5}log_2\frac{1}{5}$

（2）分别以$A_1,A_2,A_3,A_4$ 表示年龄、有工作、有自己的房子和信贷情况四个特征，计算信息增益：

$g(D,A_1)=H(D)-[\frac{5}{15}H(D_1)+\frac{5}{15}H(D_2)+\frac{5}{15}H(D_3)]=0.971-0.888=0.083$

还没有完，这只是一个分类的信息增益！！

如果想要计算其他四个分类，还得重新计算条件经验熵，然后计算信息增益：

关于A2的信息增益：

首先有两个子集，计算$H(D_1),H(D_2)$，然后计算信息增益：$g(D,A_2)=H(D)-[\frac{5}{15}H(D_1)+\frac{5}{15}H(D_2)]=0.324$

关于A3的信息增益：

首先有两个子集，计算$H(D_1),H(D_2)$，然后计算信息增益：$g(D,A_1)=H(D)-[\frac{6}{15}H(D_1)+\frac{9}{15}H(D_2)]=0.420$

关于A4的信息增益：

首先有三个子集，计算$H(D_1),H(D_2),H(D_3)$，然后计算信息增益：$g(D,A_1)=0.363$

根据信息增益的比较，特征$A_3$（有自己的房子）的信息增益最大，所以选择特征$A_3$作为最优特征。

首先选取特征$A_3$作为根结点；然后$A_3$把数据集划分为两个子集$D_1$（表示有房子）和$D_2$（表示没有房子）。

分别观察：

（1）$D_1$只有同一类的样本点，所以是一个叶节点，标记为“是”。

（2）$D_2$需要对其它三个特征$A_1,A_2,A_4$中选择新的特征：计算信息增益：$g(D_2,A_1)=H(D_2)-H(D_2|A_1)=0.918-0.667=0.251\ g(D_2,A_2)=H(D_2)-H(D_2|A_2)=0.918\ g(D_2,A_4)=H(D_2)-H(D_2|A_4)=0.474$

信息增益最大的是$A_2$，所以$A_2$（有工作）成为一个子结点，然后再分支……计算，直到全部分类完毕。

本题比较巧，由$A_2$分类后，全部元素已经分类完毕了。例如，通过以上计算以后，我们得到的决策树就是：