决策树

在所有的机器学习模型中，决策树是最贴近咱们生活的！

从数据中学习决策树，需要学习三样东西：

• 树的形状
• 每一个决策的阈值θ
• 叶节点的值

一棵决策树也具有大量的参数，但树本身是具有结构的。结构的学习也叫作Structured Prediction，因为这种问题不像之前讨论的比如回归问题只需要预测一个值就可以了，而是同时也要学出一种具体的结构。

结构的学习一般来说都很难，很多都是NP-hard问题。简单来讲NP-hard问题就是那些多项式时间复杂度内基本上解不出来的问题，一般需要指数级复杂度。

一般对于这类的问题是没有一个很好的方式来求出全局最优解的。既然这样，我们通常会使用近似算法来找到“相对”最好的解。一个经典的近似算法叫作“贪心算法”。这类的算法每次只考虑局部最好的情况，所以一般带来的是相对最好的解决方案。但在某些特定的情况下，也可以给出全局最优解。

给定数据并学出最好的决策树本身也是很难的问题。在这个问题上，我们也通常使用贪心算法来做每一步的决策，比如使用信息增益来判断下一个节点上需要放哪一个特征。

不确定性的减少也叫作信息增益(information gain)。构建决策树的过程无非是每一步通过信息增益来选择最好的特征作为当前的根节点，以此类推，持续把树构造起来。

决策树的构建过程：
每一步的构建其实就是选择当前最好的特征作为根节点。然后持续地重复以上过程把整棵树构建起来。其中，信息增益充当着每次选择特征的标准。

当然，除了信息增益，我们也可以选择其他的指标作为选择特征的标准。

到此为止，决策树的构建过程已经说完了。除了这些其实还有几个重要问题需要考虑，比如如何让决策树避免过拟合、如何处理连续型特征、如何使用决策树来解决回归问题等。

什么时候可以停止分裂？

• 当一个叶节点里包含的所有样本都属于同一个类别时可以停止分裂
• 当一个叶节点里包含的所有样本的特征都一样时可以停止分裂

所以，满足上面的条件就说明我们已经构建了完整的决策树。但这里有一点非常重要：决策树很容易过拟合！

之前学习逻辑回归时也接触过过拟合现象。在逻辑回归里，我们可以使用加入正则的方式来减少过拟合现象。加入正则相当于限制了参数的大小，小的参数会有效防止过拟合现象。

那这里的问题是：对于决策树我们如何减少过拟合现象？ 答案就是：决策树越简单越好！

一个重要标准是来判断决策树中节点的个数，节点个数越少说明这棵决策树就越简单。

因为节点个数越多，可以理解成模型的复杂度越高。

但直接减少节点个数在实际操作中不太容易实现，因为决策树的构建过程其实是递归的过程。实际上，我们也可以通过限制其他的方式来调节节点个数比如树的深度。树的深度越深，一般来讲节点个数也会越多，所以都是有一定的关系的。

所以，只要是跟节点个数相关的变量，其实都可以用来控制决策树的复杂度。总体来讲，有以下几种方法可以用来减少决策树的过拟合。

• 设置树的最大深度
• 当叶节点里的样本个数少于阈值时停止分裂
• 具体阈值选择多少取决于交叉验证的结果

对决策树调参的时候，无非主要来调整树的深度、每一个叶节点样本的个数等等。具体最优的参数一般通过交叉验证的方式来获得，这一点跟其他模型是一样的。

对于连续型特征，我们可能会有“如果一个年龄大于20”，则怎么怎么样，不到20再怎么怎么样。所以这里的核心问题是数字“20”，也叫作阈值。

那这个阈值又是怎么算出来的呢？ 对于这个问题其实有很多种答案。其中最简单的答案是每个阈值都尝试一遍！

除此之外，处理方式跟类别型特征一模一样。这里需要注意的一点是，连续型特征是可以重复使用的，比如在一个节点上有“年龄”特征，则在子树上我们可以仍然使用“年龄”这个特征。

如何使用决策树来解决回归问题？
简单的方法是取平均

当我们使用决策树解决分类问题时，可以计算准确率来评估一个决策树的好坏。但对于回归问题则需要使用不同的指标，其中一个常用的指标叫作MSE(mean square error)，也是线性回归模型所使用的评估标准。

由于回归问题里实际值和真实值都是数值型的，所以需要计算出它俩之间的差异，这就是MSE的精髓。

最后，我们还没有解决的问题是如何构造一棵决策树来做预测，或者说如何构造一棵回归树？

之前做分类任务时，我们每次使用信息增益来选取当前最好的特征并作为根节点。信息增益的基础又是信息熵，它是用来表示不确定性的。

细心的朋友应该也可以联想到一点：对于连续型变量，方差或者标准差是表示不确定性的重要指标！

不确定性已经知道如何表示了。自然而然地，连续型变量的“信息增益”或者“不确定性的减少”无非就是前后标准差的变化！

如果一个特征能让一个标准差前后变化很大，即可以认为大大地降低不确定性，是好的特征！

唯一的区别是把分类问题里的信息熵替换成了变量的标准差。

最后

以上就是贪玩硬币为你收集整理的决策树的全部内容，希望文章能够帮你解决决策树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。