【机器学习实战学习笔记(2-1)】决策树原理及相关概念细节

决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树种选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优(sub-optimal)的。

注释(了解)：

NP完全(Nondeterminism Polynomial complete,NPC)问题：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：
```
首先，它得是一个NP问题；
然后，所有的NP问题都可以约化到它。
```
NP(Nondeterministic polynominal,非确定性多项式)问题：能在多项式时间内验证得出一个正确解的问题。
NP难(NP-hard)问题：它满足NPC问题定义的第二条但不一定要满足第一条。即所有的NP问题都能约化到它，但是他不一定是一个NP问题。
启发式方法(heuristic algorithm)：它是相对于最优化算法提出的。可以认为它是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。

决策树学习(算法)通常包括3个步骤：特征选择、决策树的生成、决策树的修剪。下面就一一介绍这三个步骤。

2.特征选择

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。从特征空间的角度看，特征选择是决定用哪个特征来划分特征空间。

通常，特征选择的准则是信息增益或者信息增益比。

2.1 信息增益(information gain)

2.1.1 熵(entropy)

在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：
$P(X=x_i)=p_i,quad i=1,2,...,n$
则随机变量X的熵定义为：
$H(X)=-sum_{i=1}^{n}p_i*log p_i$

特别地，在上式中，若 $p_i=0$ ，则定义 $0log 0=0$

通常，上式中的对数：

以2为底：这时熵的单位称作比特(bit)

或以e为底(自然对数)：这时熵的单位称作纳特(nat)

由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记作 $H(p)$ ，即：
$H(p)=-sum_{i=1}^{n}p_i*log p_i$
熵越大，随机变量的不确定性就越大。从定义可验证：
$0leq H(p) leq log n（n为X的取值个数）$

2.1.2 条件熵(conditional entropy)

设有离散随机变量(X,Y)，其联合概率分布为：
$P(X=x_i,Y=y_i)=p_{ij}，quad i=1,2,..,n; quad j=1,2,...,m$
条件熵H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。

随机变量X给定条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
$H(Y|X)=sum_{i=1}^{n}p_iH(Y|X=x_i)$
其中， $p_i=P(X=x_i),quad i=1,2,...,n.$

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

2.1.3 信息增益计算

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

特征A对训练数据集D的信息增益g(D,A)计算式如下：
$g(D,A)=H(D)-H(D|A)$

H(D)：集合D的经验熵
H(D|A)：特征A给定条件下D的经验条件熵

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

决策树学习应用信息增益选择特征时，选信息增益最大的特征。信息增益大的特征具有更强的分类能力。

2.2 信息增益比(information gain ration)

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。使用信息增益比可以对这一问题进行校正。

特征A对训练数据集D的信息增益比 $g_R(D,A)$ 计算式如下：
$g_R(D,A)=frac{g(D,A)}{H(D)}$

g(D,A)：特征A对训练数据集D的信息增益
H(D)：集合D的经验熵

3.决策树的生成

决策树学习常用的生成算法有ID3、C4.5、CART。

3.1 ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构造决策树。
具体方法：

从根结点(root node)开始，对结点计算所有可能特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；
再对子结点递归地调用以上方法，构建决策树；

停止条件：

 直到所有特征的信息增益均很小(或者说每个分支下的所有实例都具有相同的类标签)
 或没有特征可以选择为止；

最后得到一个决策树

ID3相当于用极大似然法进行概率模型的选择。

3.2 C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。

C4.5与ID3的不同之处在特征选择的准则上：

ID3：信息增益
C4.5：信息增益比

4.决策树的剪枝

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自上而下进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地：

去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点；
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征

决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。
决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

关于决策树的基本原理就先介绍到这里，具体的决策树剪枝方法以及CART生成算法在后续再补充。

基于ID3算法的决策树python3.6实现及简单应用见决策树python3.6实现及简单应用

参考资料：
《统计学习方法》5.1-5.3