决策树(Decision Tree)

决策树(Decision Tree)

决策树是一种自顶而下的树形结构。每一个节点为一种属性，利用该属性来做出判断。模仿了人类做出决定时的思考流程。

显然，对于同一数据集，每个节点考虑的属性不同，生成的树的形状是不一样的。那么我们在实际生成决策树的时候应该选择哪一棵树呢？为此，可以利用奥卡姆剃刀原理——简单有效原理。即如果有两个模型的性能是一样的，我们倾向于选择简单的那个模型。反过来说，在保证分类效果的前提下，我们应该选择结构上最简单的决策树模型来做分类。

1.ID3算法(Iterative Dichotomizer 3)

其基本思路为：在越靠近根节点的节点，选择分类能力较强的属性。

首先，引入信息熵(Entropy)，其衡量的是一个系统的不确定性或一个变量的取值的不确定性。计算公式如下
$Entropy(S)=-\sum_{i=1}^{C}p_i\log{(p_i)}$Entropy(S)=−i=1∑C​pi​log(pi​)
其中，$C$C为变量$S$S的取值数，$p_i$pi​为变量$S$S取第$i$i种值时的概率大小。在决策树模型中，变量$S$S为最后不同的决定结果，如是否决定打网球，其有两种决定结果去或不去。

引入信息熵后，我们定义一个名叫“信息增益(Gain)”的变量。其含义为，变量$S$S在某属性下的划分后的信息熵的降低程度。计算公式如下
$Gain(S,A)=Entropy(S)-\sum_{v\in{A}}\frac{|S_v|}{|S|}Entropy(S_v)$Gain(S,A)=Entropy(S)−v∈A∑​∣S∣∣Sv​∣​Entropy(Sv​)
其中，$S_v$Sv​为属性$A$A时$S$S的子集，如$S$S仍为去打网球或不去，属性$A$A为天气，其可能的取值有：晴，阴，雨等。那么$S_v$Sv​就可以描述为天气为晴，阴，雨时的决定结果。

信息增益$Gain$Gain的值越大，代表这个属性的分类能力越强，我们更倾向于选择此属性做划分。

在引入了上述变量之后，ID3算法框架可描述如下

ID3(Examples, Target_attribute, Attributes)
1.退化结果即递归基
	如果数据中含有一样的目标属性T即该节点是纯的，直接返回树根并设置标记为T
	如果没有属性，直接返回树根并设置标记为数据中出现较多的目标属性

2.A <- 数据分类效果最好的属性；然后将当前根节点的决定属性设置为A

3.考虑A的每一种可能取值v
	在当前树根节点上新建一个节点，其满足 A = v，代表一个子集
	如果这个子集是纯的，即子集样本是一类的
		算法终止，并设置当前节点的标记为目标属性中出现多的那一个
	如果不纯
		在当前子集的基础上递归调用ID3算法，需刨开属性A,即
		ID3(Examples(v), Target_attribute, Attributes-{A})
		
4.return Root

过度学习(overfitting)

过度学习指的是：有两个分类器$A,B$A,B，$A$A在训练集上的误差比$B$B小，但在测试集的误差比$B$B大，那么我们则称$A$A过度学习了。

从理论上说，决策树的高度可以达到属性的个数。但是树太复杂很容易造成过度学习的情况。因此在训练决策树模型时，我们通常会控制树的规模。

防止过度学习的措施一般有：1.控制树高；2.生成检验集(Validation Set)来对生成的决策树做剪枝(Pruning)。

剪枝(Pruning)

剪枝实际上是一种合并(Merge)操作，从树梢开始往下合并。合并过程如下图

图片来自袁博老师慕课PPT

显然，这种合并操作并不能无止尽地进行，否则会只剩下树根。在实际过程中，利用Validation Set中，找到误差从降低到升高的拐点，停止剪枝。

熵的偏移值(Entropy Bias)

考虑属性生日、ID等，其通常能够很好地将数据分类，但这些分类并不是有意义的，因为它们往往将数据分得过细，每个人都可能是一条规则。因此，我们可以得出不同属性其信息熵是存在差值的，而如果不考虑这一点，那么在应用ID3算法的时候，这些属性的信息增益(Gain)往往是很大的，因此算法会倾向于选择此类属性做分类。

于是引入惩罚项，考虑变量$splitInfomation$splitInfomation，其定义如下
$splitInfomation(S,A)=-\sum_{i=1}^{C}\frac{|S_i|}{|S|}\log{\frac{|S_i|}{|S|}}$splitInfomation(S,A)=−i=1∑C​∣S∣∣Si​∣​log∣S∣∣Si​∣​
其衡量的是属性对数据的分类粗细程度，属性将数据切分得越细，则该值越大。

因此惩罚项可以定义如下
$GainRatio(S,A)=\frac{Gain(S,A)}{SplitInfomation(S,A)}=\frac{Entropy(S)-\sum_{v\in{A}}\frac{|S_v|}{|S|}Entropy(S_v)}{-\sum_{i=1}^{C}\frac{|S_i|}{|S|}\log{\frac{|S_i|}{|S|}}}$GainRatio(S,A)=SplitInfomation(S,A)Gain(S,A)​=−∑i=1C​∣S∣∣Si​∣​log∣S∣∣Si​∣​Entropy(S)−∑v∈A​∣S∣∣Sv​∣​Entropy(Sv​)​
在此变量约束下，$Gain$Gain越大的属性，其$SplitInfomation$SplitInfomation也会越大。因此利用此值作为某属性的信息增益可以限制一些没有意义的划分，同时找到更合适的划分。