决策树

        前面的学习介绍了机器学习回归模型创建的流程，并且知道了机器学习要做的事情是找到目标函数，优化它，通过每次迭代都使目标函数值最小，最优解就是目标函数最小化时侯对应的模型参数。

决策树是与回归模型流程相反的模型，它是通过建立树模型之后，才得到的损失函数，并且成为衡量决策树模型的指标。有时候数据特征众多且巨大，可以利用这种直观的树结构对数据特征进行切分，然后再构建模型。

一、算法思想

能否偿还债务表

通过给出10组数据来构建决策树判断是否能偿还贷款债务：

中红色结点（根结点）表示判断条件，橙色结点（叶子结点）表示决策结果。通过数据得到决策树的过程叫决策树的构建。

定义：

        决策树( Decision tree)是在已知各种情况发生概率的基础上,通过构建决策树来进行分析的一种方式,是一种直观应用概率分析的一种图解法;决策树是一种预测模型,代表的是对象属性与对象值之间的映射关系;决策树是-种树形结构,其中每个内部节点表示—个属性的测试,每个分支表示一个测试输出,每个叶节点代表一种类别;决策树是一种非常常用的有监督的分类算法。决策树分为两大类:分类树和回归树,前者用于分类标签值,后者用于预测连续值。

        决策树学习本质是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的条件概率模型有无穷多个，我们选择的条件概率模型应该不仅对训练数据有很好的你和，而且对未知数据有很好的预测。

决策树学习算法包含特征选择，决策树的生成与决策树的剪枝过程。

二、特征选择

        特征选择在于选择对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。通常特征选择的准则是信息增益或信息增益率。

熵：熵是表示随机变量不确定性的度量

（解释：说白了就是物体内部的混乱程度，比如杂货市场里面什么都有，那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦）

熵的计算公式

上式中的对数以2为底或以e为底，熵的单位分别称作比特或纳特。还可以记作H(p):

熵越大，随机变量的不确定性就越大：

熵H（p）随概率p变化的曲线如图：

当p=0或p=1时，H（p）=0,随机变量完全没有不确定性。当p=0.5时，H（p）=1,熵取值最大，随机变量不确定性最大。

条件熵：

信息增益：

        表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

        特征A对训练数据集D的信息增益g(D,A)定义为集合D的熵H（D）与特征A给定条件下D的条件熵H（D|A）之差，即：

        一般地，熵H(Y)与条件熵H(Y |X)之差称为互信息(mutual information).决策树学习中的信息增益等价于训练数据集中类与特征的互信息.信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。信息增益大的特征具有更强的分类能力。所以，信息增益大的特征优先作为最优特征选择。

例如：

        希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树来决定是否批准贷款申请。

信息增益比：

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，如ID特征。信息增益率比是选择特征的另一准则。

还可以使用基尼指数来选择最优特征，在下面具体介绍。

三、决策树的生成

ID3算法：

            ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树.具体方法是:从根结点(root node)开始，对结点计算所有可能的特征的信息增益， 选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点;再对子结点递归地调用以上方法，构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止.最后得到一个决策树，ID3 相当于用极大似然法进行概率模型的选择。

例：

ID3算法，容易产生过拟合。

C4.5算法：

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。

CART算法：

分类树（决策树）用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

基尼指数的值越大，样本集合的不确定性也越大。

例：

四、决策树的剪枝

        生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象.我们需要对已生成的树自下而上进行剪枝，  将树变得更简单，  从而使它具有更好的泛化能力.具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

对比（1）式和（2）式，哪个值大，哪个效果不好。（2）式效果比（1）式好，则可进行分类。

公式推导：

      剪枝，就是当a确定时， 选择损失函数最小的模型， 即损失函数最小的子树。当a值确定时，子树越大，往往与训练数据的拟合越好, 但是模型的复杂度就越高;相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好.损失函数正好表示了对两者的平衡。

      可以看出，决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

      式(5.11)或式(5.14)定义的损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

五、树的剪枝算法

决策树剪支过程的示意图：