0 树模型与线性模型

1. 定义

二叉树: 二叉树是每个结点最多有两个子树的树结构，有根节点（节点A），内部节点（B，C,D,E），叶子节点(#)，树的深度几个概念。其中叶子结点指的是树的最后一层节点，如图1所示。

图1

决策树是一个预测模型，代表的是对象属性与对象值之间的一种映射关系。它基于树形结构，从树的根节点开始，到叶子结点的父节点，期间的每个节点表示一个属性（特征）上的测试，每个分支代表一个测试输出（通常的测试输出基于样本的该属性满足某一阈值条件决定分裂到哪一边），每个叶节点代表一种类别（预测输出）。
我们可以把决策树看成一个if-then规则的集合：由决策树的根结点(root node)到叶子结点(leaf node)的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶子结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

核心思想： 在一个数据集上找到一个最优特征（又称属性），然后从这个特征的选值中找一个最优候选值，根据该值将数据集分为2个子数据集（满足候选值条件的样本集合，不满足不候选值条件的样本集合），然后递归的重复上述操作至满足停止条件
优点： 模型可读，训练速度快，分类速度快
缺点： 训练的过程就是确定每个节点应使用的最佳特征，严重依赖训练集，容易造成过拟合

2 使用流程

使用决策树做预测需要以下过程：
收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。
准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。
分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。
训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。
测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。
使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义

3 训练

决策树训练的过程就是利用标注好的训练数据集，为每个分裂节点（除叶子结点以外的其他所有节点）找到一个最好的特征属性，并确定该节点分裂的最优条件，通常为阈值条件，即输入实例（样本）的该项特征值大于某一最优阈值时向左分裂，否则向右分裂。当树达到一定深度或所有特征都已使用完毕等满足停止条件时，训练完毕。
因此，概括来讲，决策树的训练过程包括以下3个步骤：
特征选择 -> 决策树的生成 -> 剪枝

3.1 特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。选择特征的过程就是要找出能够使所有子节点数据最纯的属性（尽可能地通过分裂阈值条件将数据集完全分开）。
衡量特征分类能力的好坏，即特征选择的依据，常用的有3种指标：

信息增益(ID3)
信息
熵
信息增益
经验熵

缺点： 倾向选择分支比较多的属性进行分裂

信息增益率(C4.5)
基尼比(CART)

使用信息增益作为选择分裂的条件有一个不可避免的缺点：。为了解决这个问题，引入了信息增益率这个概念

3.2 决策树的生成

生成决策树，主要依赖所选择的算法，分为：

ID3（最基本）
- 采用信息增益作为特征选择的标准
- 只能处理离散数据，不能处理连续型数据
- 没有剪枝操作
C4.5
- 采用信息增益率作为特征选择的标准，准确率比信息增益高
- 能够处理连续型数据
- PEP后剪枝降低过拟合
CART（分类回归树）
- 用作分类树时，采用基尼比作为特征选择的标准
- 用作回归树时，采用样本的最小方差作为特征选择的标准
- 是一颗二叉树
- CCP剪枝

3.3 停止条件

最小节点数
熵或基尼值小于预设定的的阈值
树的深度达到指定条件
所有特征都已使用完毕，不能继续分裂

4 剪枝

将一棵子树的子节点全部删掉，将根节点作为叶子结点，用于解决过拟合问题。分为预剪枝和后剪枝两种方式。
预剪枝：提前结束树的增长
后剪枝： 生长完成之后剪枝，为了减少过拟合影响，通过交叉验证的方式，计算剪去某些子树或节点后在验证集上的精度的变化，如果精度无明显降低，则说明剪枝有效。常用的方法有：