2.3 决策树

决策树是通过一系列规则对数据进行分类的过程。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。作为分类、预测问题的典型支持技术，它在用户划分、行为预测、规则梳理等方面具有广泛的应用前景。缺点：趋向过拟合，可能或陷于局部最小值中，没有在线学习。

决策树的分类过程：

特征选择：从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树生长。
剪枝：在决策树构造时，由于训练数据中的噪音或孤立点，许多分枝反映的是训练数据中的异常，使用这样的判定树对类别未知的数据进行分类，分类的准确性不高。因此试图检测和减去这样的分支，检测和减去这些分支的过程被称为树剪枝。
- 作用：剪枝可缩小树结构规模，消除过拟合。
- 剪枝评测标准：在决策树的不断剪枝操作过程中，将原样本集合或新数据集合作为测试数据，检验决策树对测试数据的预测精度，并计算出相应的错误率，若剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低，那么剪掉该子树。
- 预剪枝：根据一些原则及早的停止树增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、不纯度指标下降的最大幅度小于用户指定的幅度等。
- 后剪枝：通过在完全生长的树上剪去分枝实现的，通过删除节点的分支来剪去树节点，可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。

基于信息论的决策树算法：

ID3算法：算法建立在“奥卡姆剃刀”的基础上，越是小型的决策树越优于大的决策树；根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块；没有剪枝的过程，为了避免过拟合，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点。
- 在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性。
- 不能处理连续分布的数据特征。
C4.5算法：ID3的改进算法，算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。
- 优点：分类规则易于理解、准确率较高。
- 缺点：效率低。因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。
CART算法：Classification And Regression Tree
- 采用Gini指数（选Gini指数最小的特征）作为分裂标准，同时它也是包含后剪枝操作。
- ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。