# 决策树
闲话决策树
案例1 贷款申请样本数据表 （李航统计学习p71）
| ID | 年龄 | 工作 | 房子 | 信贷 | 类别（同意贷款） |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
现在要干的一件事是通过以上的一个数据生成一个规则。例如我的贷款规则是，凡是有房子的我都给他贷款。或者我的贷款规则是有房有工作才给他贷款，（这样的贷款条件是否太苛刻了？）
那么如何生成这些规则？这就是决策树要干的事情。
何为决策树？
决策树就是if then的规则集合。
为什么叫树？
原因在于if then的规则集合的排列类似于倒着的树。
如何生成决策树？
这就是下面要答的问题。
在此之前补充一下树的概念
树的概念
树：树状结构。
根节点-->子节点-->叶节点
决策树思路
分类树
特征选择
看回案例1（分类情形），我们要用if then的规则集合来生决策。那么一般来说树有一个顶点，于是需要一个特征来作出一定的判断。例如张三说的规则中先判断有没有工作这一特征作为筛选信贷资格。王建国说规则说先判断这个人信贷信用来作为筛选指标。那么这就涉及到if then的规则生成前需要有一个特征排序：这里称特征选择
问题又来了，如何特征选择，特征选择的依据是啥？怎么才算是好的特征？
信息论领域有一个概念叫熵，这玩意是衡量一个系统的紊乱程度，不确定程度。
熵的公式： \[ H\left( X \right) =-\sum_{i=1}^n{p\left( x_i \right) \log p\left( x_i \right)} \]
条件熵的公式： \[
H\left( X|Y \right) =-\sum_{i=1}^n{p\left( x_i|y_j \right) \log p\left(
x_i,y_j \right)}
\]
上述公式表示，在Y发生后，X系统包含的不确定性。
在Y加入后X的不确定性开始变换，这种变化的差异叫作互信息。也就是知道Y之后就能知道多少X的信息，此时就称之为共同的信息。
互信息的公式： \[ I\left( X;Y \right) =H\left( X \right) -H\left( X|Y \right) \]
- 为什么它能衡量一个系统的不确定程度？
- 为什么它的公式长这样？
- 何为不确定性?
- 等等
回答上面两个问题需要单独开坑，暂时不展开，暂且先承认熵它能衡量一个系统的不确定程度、互信息表示两个随机变量的共同信息。
另外特征选择的标准还有信息增益比 \[ G_R=\frac{I\left( X;L \right)}{H\left( L \right)},L\ means\ label\ set \]
还有基尼指数
基尼指数越大样本的不确定性就越大（why？继续挖坑）（针对概率为函数时）
\[
GiniP\left( p \right) =1-\sum_{k=1}^K{p_{k}^{2}}
\]
正对样本为函数时：其中Dk表示D中的第k个类别。
\[
Gini\left( D \right) =1-\sum_{k=1}^K{\left( \frac{|D_k|}{|D|} \right)
^2}
\]
若样本集合D由特征X分为D1、D2,基尼系数的计算则如下：
\[
Gini\left( D,X \right) =\frac{|D_1|}{|D|}Gini\left( D_1 \right)
+\frac{|D_2|}{|D|}Gini\left( D_2 \right)
\]
决策树生成
一旦承认之后，那么第一个特征显然是选和标签最大互信息的特征。一旦选出这个特征就能将样本分开。然后重复计算现有样本的和标签
互信息，再找到特征反反复复就生成一个决策树。
剪枝
决策树如果一直生成下去，导致节点的样本的类别不再变化则停止，分到了极端状态，这样这个树也很大。另外可能会过拟合。因此产生剪枝这种操作。
剪枝分为预剪枝和后剪枝。
预剪枝
决策树分裂时，对每个节点分裂前预先进行评估。如果一个节点分裂后，并不对模型产生泛化能力的提升则不再分裂。
这里就有一个问题，如何判定泛化能力。 \[ C_{\alpha}\left( T \right) =C\left( T \right) +\alpha |T|\ \]
\[ 其中C\left( T \right) 表示损失函数，例如基尼指数，\alpha |T|是正则项，|T|代表叶子节点的个数 \ \]
后剪枝
先生成完整的决策树，然后自底向上对非叶子节点进行评估，如果该非叶子节点剪枝有利于泛化性能提升则将该节点子树减去，使之成为叶子节点。