[数据结构与算法]机器学习决策树总结

1、原理：决策树是一种树结构，他包括根节点，分支，叶子结点三部分，根节点表示树的一个属性，叶子表示分类的标记，分支表示输出的结果。该方法从根节点开始循环反复遍历 ，根据测试所得出的结果，将实例分配到其子节点，每个子节点都会对应该特征的一个取值，通过递归的方法，继续对实例进行测试与分配，直到到达 叶节点，最后将实例分到叶节点的类中。

2、生成树的过程：

1?? 特征选择：

方法：ID3，C4.5,CART决策树

ID3:选择信息增益大的特征，但是信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好带来的不利影响，可以通过C4.5来降低影响。

C4.5:选择信息增益率大的特征（信息增益率=信息增益/IV(a)），但是信息增益率可能对取值数目较少的属性有所偏好，因此有一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART决策树：使用基尼指数来选择划分属性，直观来说，基尼指数反映了从数据集D中随机抽取两个样本，其类别标志不一样的概率，因此，基尼指数越小，则数据集D的纯度就越高。

2??决策树的生成

通过以上三种方法，可以递归的生成一颗决策树。

3??决策树的剪枝

剪枝主要是为了对付“过拟合”的问题，即模型对训练样本学的太好了，以至于把训练样本自身的一些特点当作所有数据都具备的特点，而导致了过拟合的问题，因此，可通过主动剪掉一些分支来降低过拟合的风险。

主要方法有预剪枝和后剪枝。

1）预剪枝：是指在决策树生成的过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来泛化能力的提升，则停止划分，并将当前结点标记为叶子结点。

评价预剪枝：

优点：不仅降低了过拟合的风险，还显著减少了训练时间和测试时间的开销

缺点：虽然有些分支在当前的划分不能提升泛化能力，甚至导致泛化能力暂时下降，但在其基础上进行的后续划分，却有可能导致性能显著提高；预剪枝基于这种贪心的本质，禁止这些分支展开，可能会带来欠拟合的风险。

2）后剪枝：先从训练集生成一颗完整的决策树，并且自底向上的对非叶子结点进行考察，若将该结点对应的子数替换成叶子结点，能够带来泛化能力的提升，则将该子数替换成叶子结点。

评价后剪枝：

优点：后剪枝的欠拟合风险很小，泛化能力往往优于预剪枝

缺点：后剪枝是在生成完全决策树之后进行的，并且要自底向上的对决策树中所有非叶子结点进行考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。