决策树

2018-09-07 本文已影响0人 owolf

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

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

一、算法思想

能否偿还债务表

通过给出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 相当于用极大似然法进行概率模型的选择。

例：