决策树

先举例子，如下：左子树热恋，右子树单身。决策树的算法是如何构建，而不是如何用。

 决策树分两大类分类树和回归树。其中，分类树比如C4.5、ID3决策树，分类树用于分类标签值，那么回归树的话，用于预测实际的值比如，温度，年龄，相关程度。分类树的输出是定性的，回归树的输出是定量的。

 

构造决策树的过程

决策树的特征选择 ——> 决策树的生成（ID3,C4.5........） ——>  决策树的剪枝

决策树的特征选择：因为决策树是分类做决策的，那么对分类有影响的，就是决策树的特征，那么在决策树算法中，专业称之为信息增益，或信息增益比（算信息增益和信息增益比，就是来求这个特征）。这个是决策树的第一个步骤，即特征选择。

决策树的生成：当完成特征选择后，如何生成呢？就是确定那个点是根节点，那个是子节点，（信息增益对应的决策树算法就是ID3算法；信息增益比对应的决策树算法就是C4.5）信息增益最大的根节点。

决策树的 剪枝：如果一颗树只针对一个训练集来生成一棵树。那可能这棵树只适用于这个训练集。那这时候很可能出现过拟合。 所以，为了更好的泛化，我们要把那些只适合这个训练集，或者说非常极端的枝叶给它剪掉。这个过程就叫剪枝，目的是防止过拟合。 

经过第二步的决策树的生成，只能得到片面的局部最优化，那如何得到全局最优化呢？那就应该作一个决策树的剪枝。通俗点说，就是把多余的枝枝叶叶剪掉，让其更具有普适性。

 

如何计算特征值

信息增益

对应ID3算法

输入：训练集D和特征集A

输出：特征A对训练数据集D的信息增益g(D,A)

(1) 计算数据集D的经验熵H(D)

（2）计算特征A对数据集D的经验条件熵H(D|A)

(3) 计算信息增益

 

信息增益比

对应C4.5算法

信息增益的缺点是会更偏向取值更多的那些属性。所以说，这时候就会产生信息增益比这个概念。如下：

信息增益与训练数据集D关于特征A的值的熵之比：

其中，

,n是特征A取值的个数。

信息增益会偏向取值更多的属性，而信息增益比不会。

 

ID3算法

输入：训练数据集，特征集A，阕值ε；

输出：决策树T

（1）若D中所有实例属于同一类别Ck,则T为单结点树，并将Ck作为该节点的类标记，返回T；

（前几步都是几种特殊情况，第一步，是讲如果说D中的所有实例属于同一类 ，那么这个树就是一个单节点树，通俗点讲，所有数据集都是同一类，那构造的树肯定是单节点了。   ）

（2）若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T；
（这一步是说，我的特征集是A，那么T也是作为单节点树，通俗点讲，就是我没有特征集，那我就在整个数据集当中选择一个类别次数最多的  ，这个类别作为整个数据集的一个类别。）

（3）否则，按算法5.1计算A中个特征对D的信息增益，选择信息增益最大的的特征Ag；

（如果上述的特殊情况都不存在，就执行真正计算的过程。）

（4）若Ag的信息增益小于阕值ε，则置A为单结点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T;

 （如果信息增益计算出来的非常小，意味着特征没有划分性，  ）

（5）否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由节点及其子结点构成树T，返回树T;

（真正的构造决策树，对特征集当中的每个可能值，将这个数据集D划分为若干个非空子集，即，每个数据集D都会取最大类别，作为这个类别的标记  ）

（6）对第i个子结点，以Di为训练集，以A-{Ag}为特征集，递归的调用（1）~（5），得到字数Ti，返回Ti;

（不断循环迭代上述过程）

 

决策树的剪枝

采用极小化决策树整体的损失函数。

决策树只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树的剪枝通过优化损失函数还考虑了减少模型复杂度。

决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

 

CART（分类回归树）

既可以分类也可以回归。

递归的构建二叉决策树，如果是分类用基尼指数最小化准则进行特征选择，如果是回归用平方误差最小化准则。(两种构建方式)

找到最优切分变量j和最优切分点s

剪枝过程：

（1）形成一个子树序列 ; (2) 在子树序列中通过交叉验证选取最优子树。