最近实验室一直再说决策树和随机森林很有前景，我也开始找了点资料自己看了下。决策树是一种依托于策略抉择而建立起来的树。代表了对象属性与对象值之间映射关系的预测模型，树中每个节点用于表示某个对象，每个分叉路径用于代表某个可能的属性值，从根节点到某叶节点所经历的路径表示的对象值则对应该叶节点。

信息增益的度量标准

为了提高识别京都，必须要通过某种衡量准则选择特征，使得分割后的数据集的标签信息增益最大。信息增益就是原始数据集标签熵减去分割后的数据集标签上，信息增益大则熵变小，使得数据集更有序。其处理流程如下。

  1. 计算熵：
    $$Entropy(S)=H=-\sum^{n}_{i=1}p(x_i)log_2p(x_i)$$
  2. 依据按照信息增益变大原则选择特征代码，选择信息增益最大的特征作为分割特征。
  3. 构建决策树，采用递归思想一次分割下去，知道执行完成就构建好了决策树
  4. 最后依据决策树进行分类，给出序列化决策树。

用于衡量给定树形区分训练样本能力的度量值称作信息增益(Information Gain)。熵表征集合的混乱程度。假设S是包含关于某个目标概念的政府样本的样本集，一个属性A相对样本集S的信息增益Gain(S,A)计算公式为：
$$Gain(S,A)=Entropy(S)-\sum_{v\in V(A)}\dfrac{|S_v|}{S}Entropy(S_v)$$

其中， $V(A)$ 是属性A的值域，$S$ 是样本集合，$S_v$ 是$S$ 在属性$A$ 上值等于$v$ 的样本集合。

举个例子就比较好理解了。

现在假设有14个训练样本，样本中含有两个属性，一个是Temperature，一个是Rainfall，Temperature有两个值：low和high，Rainfall有两个值：Strong和normal。以Temperature为例
$$S=[9+,5-]$$ $$S_{low}\leftarrow[6+,2-]$$ $$S_{high}\leftarrow[3+,3-]$$ $$Gain(S,Temperature)=Entropy(S)-\sum_{V\in (low,high)}\dfrac{|S_v|}{|S|}Entropy(S_v)$$ $$=Entropy(S)-\frac{8}{14}Entropy(S_{low})-\frac{6}{14}Entropy(S_{high})=0.048$$ 同理对于Rainfall这个属性来说，$S_{strong}\leftarrow [3+,4-]$,$S_{normal}\leftarrow [6+,1-]$
它的Gain(S,Rainfall)=0.151因此，采用Rainfall比采用Temperature作为分类属性更佳。

剪枝

决策树学习方法是一种简单，广泛使用的分类技术，训练时间复杂度低，预测速度快，但容易过拟合，创建决策树不够稳定，训练数据少量变化可能导致决策树变化很大，可以采用剪枝方式尽量避免。剪枝方法包括先剪枝和后剪枝策略。先剪枝是在对整个训练数据完全拟合之前进行剪枝的策略，使得决策树停止继续生长，后剪枝是在决策树最大化生长后剪枝。

ID3

ID3是一种用于决策树改进的算法，越是小型的决策树越优于大的决策树，判断测试哪个属性为最佳的分类数性是ID3算法的核心问题。其大致流程如下：

  1. 使用统计测试来确定每一个实例属性单独分类训练样本的能力，选择分类能力最好的属性作为树的根节点。
  2. 为根结点属性的每个可能值产生一个分支，把训练样本分配到适当的分支之下；重复改过成，用每个分支结点关联的训练样本选取在该点北侧是的最佳属性，从而形成对合格决策树的贪婪搜索。

由此我们可以看出，ID3无回溯，属于局部最优，并不是全局最优。

有了ID3后，后来对其又有大量的改进算法，比较有名的是C4.5，C4.5使用信息增益率来代替信息增益选择分裂属性。还有一些其他的决策树改进算法，如SLIQ，SPRINT算法等等，大都是对建树过程进行优化。