机器学习之决策树
前提概要
决策树是一个预测模型，它表示对象属性和对象类别之间的一种映射。决策树中的非叶子节点表示对象属性的判断条件，其分支表示符合节点条件的所有对象，树的叶子节点表示对象所属的类别。
来个例子
比如我们用贷款业务中的一个例子来讲，如下：
- 对象属性 - 比如贷款用户的年龄、是否工作、是否有房产、信用评分等
- 对象类别 - 是否批准其贷款申请。
构建的决策树如下：
贷款情况表训练出来的决策树
决策树可以转化为一系列的规则（Rule）,从而构成一个规则集（Rule Set），这样的规则很容易理解和运用。
比如上述决策树，最左边的分支对应的规则是：如果客户年龄属于青年，而且有工作，那么就可以批准其贷款申请。
决策树的构造过程
- 确定一个属性，根据不同记录在该属性上的取值，对所有记录进行划分。
- 对每个分支重复这个过程，即对每个分支选择另外一个未参与树的创建的属性，继续对样本进行划分；
属性的选择（特征选择）的目的是使分类后的数据集比较纯，即数据集里主要是某个类别的样本，因为决策树的目标就是把数据庥按对应的类别标签进行分类。
最理解的情况下：通过特征的选择，能把不同类别的数据集贴上对应的类别标签。
引入几个概念
我们一般会引入数据纯度函数（即信息增益函数）来衡量一个数据集的纯度。
信息熵： 表示的是不确定性，非均匀分布时，不确定性最大，此时熵就最大。
信息增益： 当选择某个特征，对数据集进行分类时，分类后的数据集的信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
对于一个数据集，特征A作用之前的信息熵计算公式为：
- D - 为训练数据集；
- c - 为类别数量；
- Pi - 为类别i样本数量点所有样本的比例；
对应数据集D，选择特征A作为决策树判断节点时，在特征A作用后的信息熵为：
- k - 为样本D被分数k个子集；
信息增益表示数据集D在特征A的作用后，其信息熵减少的值（信息熵差值），其计算公式如下：
决策树的剪枝
在决策树建立的过程中，很容易出现过拟合（Overfitting）的现象。过拟合是指模型非常逼近训练样本，模型是在训练样本上训练出来的，在训练样本上预测的准确率很高，但是对测试样本的预测准确率不高，效果并不好,也就是模型的eneralization泛化能力(Generalization)差.
当把模型应用到新数据上时，其预测效果不好，过拟合不利于模型的实际应用。
