机器学习（三） 决策树

决策树是最经典的机器学习模型之一。它的预测效果容易理解，易于向业务部门解释，可以做分类问题和回归问题。
本篇文章主要做以下几个方面的归纳总结：

• 3.1 决策树的算法原理
• 3.2 怎样进行特征选择
• 3.3 决策树的创建过程
• 3.4 决策树的剪枝处理
• 3.5 sklearn调用以及相关参数解释

3.1 决策树的算法原理

算法思想：从决策到决策树

3.1.1 决策

什么是决策？
我们在生活中经常会依靠各种信息做出各种决策，比如说选择大学，选择专业，找工作，找对象。
以找工作为例，假如我们要对“我们是否要找一份数据分析相关的工作？”这样的问题进行决策时，通常会进行一系列的判断或者“子决策”：我们先看”这份工作是自己喜欢的吗？”，如果是自己喜欢的，则我们再看“它的待遇好吗？”，如果待遇不错，我们再判断“它是否有前景呢？”，最后我们得出最终结论：我们要从事一份数据分析相关的工作。

决策的过程为我们理解决策树的建立提供了很大的帮助。计算机是通过数据来对事情做出预测，下面给一个更加直观的例子如图：

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

3.1.2 决策树

对于是否有能力偿还贷款债，我们根据年收入、房产信息、婚姻情况来判断他是否有能力偿还贷款。
分别对年收入、房产信息、婚姻情况三个特征进行测试，并根据测试结果决定行为的类别。每选择一个特征进行测试，数据集就被划分成多个子数据集。接着继续在子数据集上选择特征，并进行数据集划分，直到创建一个完整的决策树。
问题来了，在决策树的创建过程中，要先对哪个特征进行分裂？怎样进行特征的选择呢？

3.2 怎样进行特征选择

遍历所有的特征，分别计算，使用这个特征划分数据集前后信息熵的变化值，然后选择信息熵变化幅度最大的那个特征，来优化作为数据集划分的依据。即选择信息增益最大的特征作为分裂节点。
特征选择标准除了信息增益，还有增益率和基尼不纯度。

3.2.1 信息增益

信息熵主要解决的是信息量化的问题。一条信息的信息量和它的不确定性有直接的关系。一个问题不确定性越大，要搞清楚这个问题，需要了解的信息量就越多，其信息熵就越大。
信息熵计算公式：

信息增益：
信息增益指的是当按照这个特征划分之后，信息熵下降的量。在特征选择的过程中，选信息增益最大的特征。

ID3算法使用信息增益作为特征选择指标的决策树构建算法。

3.2.2 增益率

由于权重的存在，信息增益准则对包含数目较多的属性有偏好。为了减少这种不“客观”的判定，选择增益率来作为划分指标。

C4.5算法是使用增益率作为特征选择指标的决策树构建算法。

3.2.2 基尼不纯度

信息熵是衡量信息不确定性的指标，也是衡量信息纯度的指标。除此之外，基尼不纯度也是衡量信息不纯度的指标，其计算公式如下：

CART算法是使用基尼不纯度来作为特征选择指标的决策树构建算法。

3.3 决策树的创建过程

• 计算数据集划分前的信息熵
• 遍历所有未作为划分条件的特征，分别计算根据每个特征划分数据集后的信息熵。
• 选择信息增益最大的特征，并使用这个特征作为数据划分节点来划分数据。
• 递归地处理被划分后的所有子数据集，从未被选择的特征里继续选择最优数据划分特征来划分子数据集。
  递归过程结束的条件：
• 所有的特征都使用完了
• 划分后的信息增益足够小了

3.4 决策树的剪枝过程

使用决策树模型拟合数据时，容易造成过拟合。解决过拟合的方法是对决策树进行剪枝处理。决策树的剪枝有两种思路：预剪枝和后剪枝。

3.4.1 预剪枝

预剪枝是在构造决策树的同时进行剪枝。在决策树的构建过程中，如果无法进一步降低信息熵的情况下，就会停止创建分支。为了避免过拟合，可以设置一个阈值，即使还可以继续降低信息熵，但如果信息熵的减少量低于这个阈值，也停止创建分支。
其他的预剪枝算法：如限制叶子节点的样本个数等。

3.4.1 后剪枝

后减枝是指决策树构造完成之后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，信息熵的增加量是否小于某一阈值。如果小于阈值，则这一组节点可以合并一个节点。

3.5 sklearn调用以及相关参数解释

scikit-learn 使用 sklearn.tree.DecisionTreeClassifier类实现决策树分类算法。其中几个典型的参数类型解释如下：

• criterion: 特征选择算法。
• splitter: 创建决策树分支的选项，一种是选择最优的分支创建原则，另外一种是从排名靠前的特征中，随机选择一个特征来创建分支，这个方法和正则项的效果类似，可以避免过拟合的问题。
• max_depth: 指定决策树的最大深度。通过指定该参数，用来解决模型的过拟合问题。
• min_samples_split: 这个参数指定能创建分支的数据集大小。默认为2，如果一个节点的样本个数小于这个数值，则不再创建分支。
• min_samples_leaf: 创建分支后的节点样本数量必须大于等于这个数值。
• max_samples_nodes: 限制最大的样本节点个数。
• min_impurity_split: 可以使用该参数来指定信息增益的阈值。

总结

决策树的建立过程就是信息熵减少的过程。
怎样来选择要划分的特征？决策树的停止指标？为了避免过拟合，采取了哪些剪枝方法？调用sklearn时，需要调整的参数有哪些？参数的含义？
弄懂上面这些，应该达到了一个调参侠的入门标准吧。

文章参考：机器学习（6）——决策树
《scikit-learn 机器学习》