决策树与随机森林

一、生活场景

1、点外卖问题

如何点到一个更心仪的外卖？

二、决策树

1、概念

决策树(Decision Tree)是一种树形结构的算法

一般情况下，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。

• 树中的“根节点”与每个“内部节点”都表示一个特征（比如例子中的 价格、配送时间），
• 每一个叶节点表示一个分类结果（比如最终是 点、不点）。
• 每一个特征下的分叉路径，代表这个特征的某个种类（比如 口味是西餐、还是别的）。

三、决策树生成过程

策树生成的过程包括三个部分：分别是特征选择、决策树生成、决策树剪枝。

1、特征选择

• 特征选择 是构建决策树的第一步，也是最关键的一步。它指的是：从样本的众多特征中，选择一个特征作为当前节点的分裂标准。

• 决策树的构造只会影响到算法的复杂度和计算的时间，而不会影响决策的结果，

• 优化决策树的结构，就是找到每一个节点时，最好的一个区分特征。

• 目标: 通过一种衡量标准，来计算通过不同特征进行分类选择后的分类情况找到最好的那个作为根节点，以此类推。

决策树中特征的选择，就是由信息增益来判断的，信息增益的计算过程中，就选择了 熵值 来作为当前的一个衡量标准。

(1) 熵

• “熵“： 表示随机变量不确定性的度量，即系统混乱的程度。(简单来说，就是指的物体内部的混乱程度比如杂货市场的混乱程度高，而苹果专卖店的混乱度就低)

计算公式

举例:

• A集合【1，1，1，1，1，1，1，1，1，1】
• B集合【1，1，1，1，1，1，2，2，2，2】
• C集合【1，2，3，4，5，6，7，8，9，10】

结论：经过一次信息节点分类之后，哪个数据类别的熵最大，就选取为根节点

(2) 信息增益

信息增益： 特征 X 使得类别 Y 的不确定性减少的程度。简单来说就是，经过特征 X 的一次分裂，使得整体样本的熵值降低的程度。-----简单来说：信息增益是指某个特征的取值带来的信息，信息越多，信息增益就越大。

在决策树生成的时候，优先选择信息增益大的特征，可以帮助我们更快的进行最终结果预测。也就是说信息增益可以帮助我们选择最佳的特征来生成更简单、高效的决策树模型。

三、决策树应用场景

1、银行办信用卡的审批过程

银行在决定要不要给某个客户办信用卡，以及确定卡片额度大小的时候，经常会对客户进行多方面的考量。具体怎么做呢？就是 将这个客户的职业、学历、房产信息、婚姻状况、有无贷款等等特征输入模型中，最后让模型来分析这个客户会不会产生逾期还款。

在构建模型前，首先要让模型知道普通客户使用信用卡有什么规律，因此需要取一批客户的信用卡还款记录输入模型中。

这个表里的数据记录了 10 个客户的一些重要特征，包括是否有房、婚姻状况、学历、月收入，以及最终的还款情况。

• 数据: 10个客户的特征及还款情况
• 特征: 4种用户的还款能力特征
• 目标: 构造决策树

要求：

我们可以把这几个特征分别记做 X1，X2，X3，X4，以及最终的结论是否逾期，Y。

我们需要根据这些数据构建一个决策树，判断一下当未来收到某一个申请者的各种信息后，判断它是否会逾期还款。

思路：

• 划分方式: 4种
• 问题: 谁当根节点?
• 依据: 信息增益

计算原始值

计算房产分类

计算婚姻状况分类

计算汇总

总结

在决策树的构建过程中，会在所有的特征中遍历找到最好的一个特征，作为我们的根节点，然后再依次选其他的内部节点。

直到我们把所有的特征都遍历完，或者达到一个终止条件，我们就可以认为这个决策树构建好了

四、决策树三大算法

• ID3 算法，相比其他两个更简单，可解释性更强，不过因为它的计算指标是通过信息增益来计算的，所以可能很容易就导致过拟合。
• C4.5 算法因为是使用的 信息增益率来计算的，所以相对而言，就能够避免过拟合的问题。
• CART 算法则是在上面的基础上，使用了基尼系数去作为计算的指标，所以计算的精准度就会相对更高一些。

五、决策树剪枝

决策树为什么要剪枝?

如果任由决策树无限制的庞大，那它学到数据中噪声的可能性就会很大，就会导致决策树模型变得复杂，所以模型的泛化能力就会下降。所以为了防止决策树模型过拟合，就需要对它进行剪枝操作。

决策树中，通常有两种剪枝的操作，一个是预剪枝，另一个是后剪枝。

• 预剪枝 是指的，当我们在建立决策树的过程中，一边建立决策树，一边进行剪枝。 也就是在选根节点，或者选每个内部节点的时候，先给定一些限制条件。比如树的深度，限制叶子结点个数，叶子结点样本数以及信息增益量。

• 后剪枝 是先让树完全生长，等完全建立好决策树之后，再从底部开始删除一些枝。 它这么做是因为它基于这样的假设：假设删除某些枝叶后，决策树在我们给的验证数据集上，能有更好的预测效果。

• 预剪枝: 建立决策树的过程中增加限制条件
• 后剪枝: 完全建立完决策树后进行剪枝

整体来看，两种方法都有利有弊，预剪枝可能会导致模型过于简单，不能充分捕捉到数据中的规律，可能造成欠拟合；而后剪枝虽然通常效果都不错，但它的计算成本更高，因为它需要先构造出一个完整的树来，再进行修剪。

在实际应用中，我们通常需要根据具体的问题，来决定使用哪一种剪枝策略。

六、随机森林

随机森林(Random Forest)：由多个决策树组成的一个集成，其中的每棵树都是独立训练的，并且在生成树的过程中加入了随机性。这种随机性主要就体现在：样本的随机性，即每一个决策树的样本是随机从原始数据集中采样得到的。

七、随机森林优缺点

优点：

• 抗过拟合能力强
• 对异常值的敏感性高

缺点：

• 计算成本高
• 可解释性差