【机器学习算法篇】决策树

决策树是一种基本的分类与回归方法。

决策树的学习过程

• 特征选择：从训练数据的特征中选择一个特征作为当前节点的分裂标准（特征选择的标准不同产生了不同的特征决策树算法）。
• 决策树生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止。
• 剪枝：决策树容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝和后剪枝）。实现决策树的算法包括ID3、C4.5算法等

实现决策树的算法包括ID3（信息增益）、C4.5（信息增益率）和CARD（Gini）

决策树要达到寻找最纯净划分的目标要干两件事，建树和剪枝

建树：

信息熵（entropy）是用来衡量一个随机变量不确定性的度量。如果信息的不确定性越大，熵的值也就越大，出现的各种情况也就越多。

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

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

 

以信息增益作为划分训练数据集的特征，存在偏向于选择值较多的特征的问题，使用信息增益比可以对这一问题进行校正。

C4.5(信息增益率)：信息增益g(D,A)与训练数据集D关于特征A的值的熵之比，

其中，，n是特征A取值的个数，同样比较它们的大小,选择信息增益率最大的特征

 

CARD：既可以做分类，也可以做回归。只能形成二叉树。

对于分类树（目标变量为离散变量）：使用基尼系数作为分裂规则。比较分裂前的gini和分裂后的gini减少多少，减少的越多，则选取该分裂规则

对于回归树（目标变量为连续变量）：使用最小方差作为分裂规则。只能生成二叉树。

 

剪枝：

如何停止分裂

   下面这六种情况都会停止分裂。其中第一种其实属于树的完全长成，但这会出现过拟合问题，所有之前很流行一种抑制这种情况的方法，叫树的剪枝。树的剪枝分为预剪枝和后剪枝，预剪枝，及早的停止树增长控制树的规模，方法可以参考如下6点停止分类的条件。后剪枝在已生成过拟合决策树上进行剪枝，删除没有意义的组，可以得到简化版的剪枝决策树，包括REP（设定一定的误分类率，减掉对误分类率上升不超过阈值的多余树）、PEP，还有一种CCP，即给分裂准则—基尼系数加上惩罚项，此时树的层数越深，基尼系数的惩罚项会越大。