一、理解决策树

  决策树在机器学习领域的地位很高，而且又是几个经典集成模型(随机森林，提升树)的基础。 为了更好地理解这些集成模型，需要先理解决策树。那什么叫决策树呢?其实我们每天都在使用决策树，这是我们做日常决策的工具。举个例子，“明天如果下雨我就不出门了。” 在这里我们用了一个决策条件:是否下雨，然后基于这个条件会有不同的结果:出门和不出门。 这就是一个经典的决策树。

  再举个稍微复杂点的，张三和李四都是医生，曾经都被评为国家级专家，但他们的诊断逻辑还是不太一样的，具体如上图所示。虽然都去关注“肌肉疼痛”和“发烧”两个症状，张医生首先判断患者是否有发烧症状，李医生则先看患者是否有肌肉疼痛感。这个例子中涉及到了几个核心点。第一、两位医生都具有属于自己的决策树，而且他们在诊断过程中都会按照自己的决策树逻辑来诊断。第二、医生的能力也有好坏之分，在这里我们可以把这两个决策树看作是两位医生的能力，而且这种能力是由大量的临床经验获得的。这样一来，哪一个决策树好就等同于哪一位医生的医术更加高明。我们把临床经验可以看作是历史样本数据。第三、为了判断哪位医生的医术更高明，需要知道哪一个决策树更好，这就要求我们定义出一种评估决策树好坏的标准。

  利用机器学习语言来描述的话，基于历史的诊断样本或者经验，我们可以构造出不同的决策树(也就是的不同医生)，但只要我们定义出了一种评估方式则可以选出其中最好的那棵决策树，这其实就是决策树的训练过程。

二、决策树的训练

  决策树由节点和边组成，那我们如何得到决策树，我们需要从数据中学习决策树的三样东西：树的形状、每一个决策的阈值,叶节点的值。

  一棵决策树也拥有大量的参数，但树本身是具有一定结构的。结构的学习也叫作Structured Prediction，因为这种问题不像之前讨论的比如回归问题只需要预测一个值就可以了，而是同时也要学出树的结构。结构的学习一般来说都很难，很多都是$NP-hard$问题。那具体什么叫$NP-hard$呢? 如果学过数据结构与算法，就应该有所了解。简单来讲$NP-hard$问题就是那些多项式时间复杂度内基本上解不出来的问题，一般需要指数级复杂度。

  在计算机世界里存在大量的$NP-hard$问题等待我们去解决。一般对于这类的问题是没有一个很好的方式来求出全局最优解的。既然这样，我们通常会使用近似算法来找到“相对”最好的解。一个经典的近似算法叫作“贪心算法”。这类的算法每次只考虑局部最好的情况，所以一般带来的是相对最好的解决方案。但在某些特定的情况下，也可以给出全局最优解。给定数据并学出最好的决策树本身也是很难的问题。在这个问题上，我们也通常使用贪心算法来做每一步的决策，比如使用信息增益来判断下一个节点上需要放哪一个特征。

三、决策树中的不确定性

  上一节里谈到了决策树算法，那这又是什么呢。首先，决策树算法本身是贪心算法。所以在决策树的训练上，每一步的最优选择局限在局部。那如何最优选择每一步，即挑选好的特征，而好的特征就是减少不确定性。那如何衡量不确定性，在信息论和概率论统计中，熵是表示随机变量不确定性的度量，令熵为$H(p)$，则：
$$H(p)=-\sum _{i=1}^K{p}_i(1-p_i)$$

  已经知道如何用数学来表示不确定性了。 接下来，我们再回到决策树的问题上。那又如何表示不确定性的减少呢? 无非就是原来的不确定性减去现在的不确定性。假设数据集A共有$K$个特征，记为$x_i,i=1,2,...,K$。数据集A的不确定性越大，则数据集A包含的信息也越多。假设数据集A的信息为$H(A)$，经过特征$x_i$筛选后的信息为$H(A|x_i)$,定义信息增益$g(A,x_i)$为两者的差值，即：
$$g(A,x_i)=H(A)-H(A|x_i)$$
这种不确定性的减少也叫作信息增益(information gain)。构建决策树的过程无非是每一步通过信息增益来选择最好的特征作为当前的根节点，以此类推，持续把树构造起来。选择使数据集A信息增益最大的特征作为筛选特征，公式表示为：
$$x=max(g(A,x_i))=H(A)-min(H(A|x_i))$$

  以上是决策树的构建过程。总结一下，每一步的构建其实就是选择当前最好的特征作为根节点。然后持续地重复以上过程把整棵树构建起来。其中，信息增益充当着每次选择特征的标准。当然，除了信息增益，我们也可以选择其他的指标作为选择特征的标准。到此为止，决策树的构建过程已经说完了。除了这些其实还有几个重要问题需要考虑，比如如何让决策树避免过拟合、如何处理连续型特征、如何使用决策树来解决回归问题等。

四、决策树的过拟合

  在决策树的训练过程，什么时候可以停止训练？只要满足以下两个条件：

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

  简单来讲，如满足以上两个条件我们就可以停止继续构建决策树了。首先，当所有的样本属于同一类别时就可以停下来，因为已经达成了我们最终的目的。另外，所有的特征都一样的时候其实也没办法继续了。所以，满足上面的条件就说明我们已经构建了完整的决策树。但这里有一点非常重要:决策树很容易过拟合!

  那什么叫过拟合呢？就是在训练数据上表现特别好，但放到测试数据就表现很糟糕。之前学习逻辑回归时也接触过过拟合现象。在逻辑回归里，我们可以使用加入正则的方式来减少过拟合现象。加入正则相当于限制了参数的大小，小的参数会有效防止过拟合现象。那这里的问题是：对于决策树我们如何减少过拟合现象？答案就是：决策树越简单越好。那什么叫更简单的决策树呢？一个重要标准是来判断决策树中节点的个数，节点个数越少说明这棵决策树就越简单。
  所以，决策树里的节点个数跟过拟合有着很大的关系。因为节点个数越多，可以理解成模型的复杂度越高。直接减少节点个数在实际操作中不太容易实现，因为决策树的构建过程其实是递归的过程。实际上，我们也可以通过限制其他的方式来调节节点个数比如树的深度。树的深度越深，一般来讲节点个数也会越多，所以都是有一定的关系的。所以，只要是跟节点个数相关的变量，其实都可以用来控制决策树的复杂度。总体来讲，有以下几种方法可以用来减少决策树的过拟合。
  如何避免决策树的过拟合？可以通过以下三点：

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

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

五、决策树最优模型的构建步骤

  说了那么多，那究竟如何针对某个数据集构建决策树的最佳模型呢？
  首先定义决策树的损失函数，令决策树的叶节点数为T，损失函数为:
$$C_a(T)=C(T)+\alpha |T|$$
  其中$C(T)$为决策树的训练误差，决策树模型用不确定性表示，不确定性越大，则训练误差亦越大。$T$表示决策树的复杂度惩罚， $\alpha$参数权衡训练数据的训练误差与模型复杂度的关系，意义相当于正则化参数。考虑极端情况：当 $\alpha$趋于0的时候，最优决策树模型的训练误差接近0，模型处于过拟合；当 $\alpha$ 趋于无穷大的时候，最优决策树模型是由根节点组成的单节点树。
  然后将数据集A通过一定的比例划分为训练集和测试集。决策树最优模型的构建步骤包括训练阶段和测试阶段:

训练阶段:

1. 最小化决策树的不确定性值得到的生成模型，即决策树生成；
2. 通过决策树剪枝，得到不同的正则化参数$\alpha$ 下的最优决策树模型，即决策树剪枝。

  下面重点讨论训练阶段的决策树生成步骤和决策树剪枝步骤。

  决策树生成步骤:

1. 根据决策树的特征筛选准则，选择数据集信息增益最大的特征；
2. 重复第一个步骤，直到所有叶节点的不确定性为0。

  决策树剪枝步骤:

1. 将正则化参数$\alpha$从小到大分成不同的区间$[{\alpha }_i,{\alpha }_{i+1}),\alpha =0,1,...,n$，对决策树的非叶节点进行剪枝，令该节点为$T$，以该节点为根节点的子树为$T_t$。

2. 当$\alpha$满足如下条件时;:
   $$\alpha =\frac{C(T)-C(T_t)}{|T_t-1|}$$

   即节点为单节点树的损失函数与子树Tt的损失函数相等，而剪枝后的复杂度降低了，泛化性能较好，因此，对该节点进行剪枝。

3. 遍历所有非叶节点，得到每个剪枝后的最优子树与对应的$\alpha$ 参数。

测试阶段:
  通过测试集评估不同$\alpha$参数下的最优决策树模型，选择测试误差最小的最优决策树模型和相应的正则化参数 $\alpha$。

最后

以上就是笑点低小鸽子为你收集整理的从零开始学NLP（二）决策树一、理解决策树二、决策树的训练三、决策树中的不确定性四、决策树的过拟合五、决策树最优模型的构建步骤的全部内容，希望文章能够帮你解决从零开始学NLP（二）决策树一、理解决策树二、决策树的训练三、决策树中的不确定性四、决策树的过拟合五、决策树最优模型的构建步骤所遇到的程序开发问题。

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