决策树

决策树算法是一种监督学习算法，英文是Decision tree

构建决策树的三个步骤

特征选择：选取有较强分类能力的特征。
决策树的选择：ID3基于信息增益最为特征，C4.5采用信息增益比率。CART算法：CART全称为分类回归树，既可以用于分类，也可以用于预测。利用CART构建回归树用到树的剪枝技术，用于防止树的过拟合。
决策树剪枝：基于决策树算法生成的树对与预测训练集比较准确，但是预测测试集差别较大。
注意：决策树的构建一直到没有特征可以构建过着信息增益很小时停止。这就造成决策树过于复杂，体现就是训练集预测较为准确，但是测试集差别较大也就是过拟合。防止构建的决策树过拟合的最佳办法就是较小树的复杂度（剪枝）。剪枝的目标是通过极小化决策树的整体损失函数来实现的。
下面我们从决策树目标入手，讲一下如何构建决策树模型。
决策树的目标：给定训练集，其中为输入实例，n为样本个数（），为类标记，i=1,2…..N;N为样本容量。构建决策树的目标是，根据给定的训练数据集学习一个决策树模型。
构建决策树通常是递归地选择最优特征，并根据该特征对训练数据进行分割，步骤如下：
构建根节点，所有的样本都位于根节点。
选择一个最优的特征。通过该特征将训练数据集分割成子集，确保各个子集有最好的分类，但要考虑以下两种情况：
若子集能够被“较好地”分类，则构建叶节点，并将子集划分到对应的叶节点中去。
若某个子集不能被“较好地”分类，则对该子集继续划分。
递归直到所有训练样本都被很好的分类，或没有合适的特征为止。对于是否较好的分类，我们借助“信息增益”、“信息增益率”、“基尼系数”、“分类错误率”等指标衡量。
通过上述步骤生成的决策树对训练样本有很好的分类能力，但是我们需要的是对未知样本的分类能力。因此通常需要对已生成的决策树进行剪枝，从而使得决策树有很好的泛化能力。剪枝的过程就是去掉过于细分的叶节点，从而提高泛化能力。

信息熵

熵

香农在他的<<信息论>>中借用德国物理学家发明的“熵”的概念提出了“信息熵”的概念。在物理学中“熵”通常是指物体能量的分布更加均匀，而香农首先定义了“信息”的概念：信息就是对不确定性的消除。因此，“信息熵”就表示事物不确定性的度量标准，可以根据数学中的概率计算，出现的概率就大，出现的机会就多，信息的分布越不均匀，不确定性就小（信息熵小）。

信息熵

下推公式

确定一个不确定函数I(x)=log(1/P)=-log(p)
求解不确定函数的期望-sum(pi*log(pi))
不确定期望就是我们的信息熵

如果基于信息熵选择特征

信息熵越大，信息的不确定性越大（1-1/32），信息确定性越小，信息纯度越低；
信息熵越小，信息的不确定性越小，信息的确定性越大（区分度越大），信息纯度越高，因此优先选择信息熵较小的值作为分支节点

信息增益

注：整个数据集信息熵与当前节点（划分节点）信息熵的差，就是信息增益
类似，Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048
所以，选择age作为第一个根节点（信息熵越小越好，所以信息增益越大越好）

ID3算法

算法根据信息增益选择较大的信息增益值作为根节点或分支节点，依次递归构建决策树

构建步骤

• 1-如果所有额属性都被处理完毕，直接返回
• 2-计算所有节点的信息增益最大的值对应的属性，作为根节点或分支节点，如果能够根据当前的节点划分结束，直接停止
• 3-否则从剩余的节点中选择次信息增益最大的值对应属性划分样本到叶子结点

• 4-递归构建决策树

  算法停止迭代条件

• 1-树的深度限定

• 2-树的叶子节点个数，如果低于叶子节点的个数可以停止迭代
• 3-树的分支节点个数，如果低于设定分支节点格式可以停止迭代

• 4-树的不纯度的下降速率(GIni),如果低于设定阈值停止迭代

  其他优化算法

  C4.5算法

  C4.5和ID3（1986年 Quinlan提出的）算法类似，只有在以下几个点作了改进。
  用信息增益率来选择属性，克服用信息增益选择时候偏向选择取值多属性不足。（了解）
  特征A对数据集D的信息增益：Gain(A) = Info(D)-Info_A(D)
  信息增益率：Gainr(A) =Gain(A) /H(A) ：其中H(A)为A的熵
  由于分类困难，也就是训练集的信息熵总和大的时候那么这时信息增益也会偏大，而在测试集总体信息熵小的时候，信息增益又偏小。因此使用信息增意率可以有效的避免类似的问题。
  1.经验熵(就是前面提到的信息熵，也就是信息量的大小问题)
  2.在树构造过程中进行剪支。
  3.能够完成连续属性的离散化处理。
  4.能够对不完整数据进行处理。

  CART

  Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone).
  共同点：都是贪心算法，自上而下(Top-down approach)
  区别：属性选择度量方法不同

  C4.5 （gain ratio)，CART(gini index)，ID3 (Information Gain)

  关于以上几点解释：
  贪心算法：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
  无论哪种方法构建树，因为树的构建过程是递归形式的，所以有可能出现树的过拟合情况，因此，我们对树过拟合情况有一种“树剪枝”技术，避免树由于过度生长而出现的过拟合现象。接下来我们讲解树的两种剪枝技术

  树的剪枝

  什么是剪枝

  剪枝就是将一个叶子树上的全部子节点全部删除，利用叶子节点替换子节点。(实质上是后剪枝技术)，也可以（假定当前对以root为根的子树进行剪枝）只保留根节点本身而删除所有的叶子，以下图为例：
  

  为什么要剪枝

  决策树是考虑了所有的数据而成的复杂的树，这样很容易出现过拟合。因此可以将前后分类误差不到的子节点修 剪掉，以此来降低树的复杂度。降低过拟合的概率。

  先剪枝

  先剪枝其实就是提前结束决策树的增长。在ID3算法中默认是节点分割到时同一类别的时候停止。对于实例少的有可能分割到同一实例。因此为了避免这种情况我们可以定义不纯度下降量。当一个节点分割导致的最大的不纯度下降小于a时，就把该节点看作是叶子结点。但是需要注意的时如果不纯度下降量如果定义的过大会造成节点的不纯度很大就停止了分割，但是如果接近与0又会使得树的分割过程接近原始。因此此方法虽然简单但是参数的设置尤为重要。
  算法停止迭代条件：

  - 树的深度限定
  - 树的叶子节点个数，如果低于叶子节点的个数可以停止迭代
  - 树的分支节点个数，如果低于设定分支节点格式可以停止迭代
  - 树的不纯度的下降速率(Gain),如果低于设定阈值停止迭代
        - Gain信息增益越大越好，下降的时候下降速率越大区分性越大
        - 如果下降速率=0.和没有设置是一样的
        - 如果下降速率=很大的值的时候，不会继续分裂，只剩下根节点

  后剪枝

  后剪枝是指在决策树生长完成之后再进行剪枝的过程。后剪枝是从一个充分生长的树中，按照自低向上的方式修剪掉多余的分支，有两种方法：
  （1）用新的叶子结点替换子树，该叶子结点的类标号由子树记录中的多数类决定。
  （2）用子树中最常用的分支替代子树。
  通常计算前后预期分类错误率，如果修剪导致预期分类错误率变大，则放弃修剪，保留相应的各个分支，否则就将相应的节点分支修剪删除。
  通常采用后剪枝技术是最小的错误剪枝(MEP)技术，即在产生一系列的经过修剪后的决策树候选之后，利用一个独立的测试数据集，对这些经过修剪之后的决策树的分类准确性进行评价，保留下预期分类错误率最小的（修剪后）决策树。
  除了最小错误剪枝技术外，还有悲观错误剪枝(MEP)和代价复杂度剪枝(CCP)。