决策树是如何工作的

作者：Rahul Saxena

译者：java达人

来源：http://dataaspirant.com/2017/01/30/how-decision-tree-algorithm-works/（点击文末阅读原文前往）

人工智能时代悄然而至，你可以继续安心地敲着代码，但必须对崭新的技术，陌生的算法保持高度的警惕和关注。 —— java达人

决策树算法属于监督学习算法系列。与其他监督学习算法不同，决策树算法也可用于求解关于回归和分类问题。

使用决策树的目的通常是创建一个训练模型，可以通过学习根据先验数据（训练数据）推导的决策规则，来预测目标变量的类别或数值。

与其他分类算法相比，决策树算法是非常容易的。决策树算法尝试通过使用树表示来解决问题。树的每个内部节点对应一个属性，每个叶节点对应一个类标签。

决策树算法伪码

1. 将数据集的最优属性放在树的根节点。 2. 将训练集分为子集。子集应以这样一种方式组织：每个子集包含相同属性值的数据。 3. 在每个子集上重复步骤1和步骤2，直到在树的所有分支中都有叶节点。

在决策树中，为了预测从根节点开始的记录的类标签。我们将根属性的值与记录的属性值进行比较。在比较的基础上，我们选择与该值对应的分支，并跳转到下一个节点。

我们继续将我们的记录的属性值与树的其他内部节点进行比较，直到我们到达预测类型值的叶节点。我们知道如何使用模型决策树来预测目标类别或数值，现在让我们了解如何创建决策树模型。

创建决策树时的假设

下面是我们使用决策树时所做的一些假设：

• 一开始，整个训练集被视为根节点。
• 特征值更倾向于分类。如果这些值是连续的，那么在构建模型之前，它们将被离散化。
• 记录根据属性值递归分布。
• 将属性作为树的根或内部节点的顺序是通过使用统计方法完成的。

决策树遵循Sum of Product（SOP）表述形式。对于上面的图片，你可以看到我们如何通过从根节点到叶节点的遍历预测我们是否接受新的工作机会或者是否每天使用电脑。

这就是Sum of Product。Sum of Product（SOP）也称为析取范式(Disjunctive Normal Form)。对于一个类，从树根到具有相同类的叶节点的每个分支都是值的合取(Product)，在该类中结束的不同分支构成了析取(Sum)。

决策树实现中的主要挑战是确定哪些属性作为根节点以及每个级别的节点。处理这些需要知道属性选择。我们有不同的属性选择方法来识别这些属性。

普遍的属性选择方法：

• 信息增益
• 基尼指数

属性选择

如果数据集由“n”个属性组成，则决定在树的根节点或不同级别放置哪个属性作为内部节点是一个复杂的步骤。通过随机选择任意节点作为根，无法解决问题。如果我们遵循随机的方法，它可能会给我们带来准确性很低的结果。

为了解决这个属性选择问题，研究人员制定了一些解决方案。他们建议使用一些标准，如信息增益，基尼指数等。这些标准将计算每个属性的值。值会被排序，并且按照顺序将属性放置在树中，即大数值的属性（在信息增益的情况下）被放置在根的位置。

当信息增益作为标准时，我们假设属性是分类的，对于基尼系数，则假设属性是连续的。

信息增益

当信息增益作为标准，我们尝试估计每个属性所包含的信息。我们使用信息理论中的一些知识点。

随机变量X的随机性或不确定性由熵定义。

对于二分类问题，只有两个类，正负类。

• 如果所有的例子都是正的或全部是负的，则熵为0，也就是低。
• 如果一半的记录是正，一半是负类，那么熵是1，也就是高。

通过计算每个属性的熵测度，我们可以计算其信息增益。信息增益计算了由于属性排序而产生的熵的预期减少值。信息增益可以被计算出来。

为了清楚地了解信息增益和熵的计算，我们尝试在样本数据上作操作。

示例：以“信息增益”为标准构建决策树

我们尝试以信息增益为标准，使用这些数据样本。在这里，我们有5列数据，其中4列是连续数据，第5列由类标签组成。

A，B，C，D属性当作是预测变量，E列类标签当作是目标变量。为了根据这些数据构建决策树，我们必须将连续数据转换为分类数据。

我们选择了一些随机值来对每个属性进行分类：

1. 计算目标熵。计算每个属性的信息增益有两个步骤：

2. 需要计算每个属性A，B，C，D的熵。使用信息增益公式，我们将从目标熵减去该熵，其结果就是信息增益。

目标熵：我们有8个负类型的记录和8个正类型的记录。所以我们可以直接估计目标熵为1。

使用公式计算熵：

E(8,8) = -1*( (p(+ve)*log( p(+ve)) + (p(-ve)*log( p(-ve)) )

= -1*( (8/16)*log2(8/16)) + (8/16) * log2(8/16) ) = 1

Var A的信息增益

Var A的16个记录中，有12个记录值>=5, 4个记录的值<5。

• Var A >= 5 & class == positive: 5/12
• Var A >= 5 & class == negative: 7/12
  • Entropy(5,7) = -1 * ( (5/12)*log2(5/12) + (7/12)*log2(7/12)) = 0.9799
• Var A <5 & class == positive: 3/4
• Var A <5 & class == negative: 1/4
  • Entropy(3,1) = -1 * ( (3/4)*log2(3/4) + (1/4)*log2(1/4)) = 0.81128

Entropy(Target, A) = P(>=5) * E(5,7) + P(<5) * E(3,1) = (12/16) * 0.9799 + (4/16) * 0.81128 = 0.937745

Var B的信息增益

Var B16个记录中,12个记录的值> = 3，4个记录值 <5。

• Var B >= 3 & class == positive: 8/12
• Var B >= 3 & class == negative: 4/12
  • Entropy(8,4) = -1 * ( (8/12)*log2(8/12) + (4/12)*log2(4/12)) = 0.39054
• VarB <3 & class == positive: 0/4
• Var B <3 & class == negative: 4/4
  • Entropy(0,4) = -1 * ( (0/4)*log2(0/4) + (4/4)*log2(4/4)) = 0

Entropy(Target, B) = P(>=3) * E(8,4) + P(<3) * E(0,4) = (12/16) * 0.39054 + (4/16) * 0 = 0.292905

Var C的信息增益 Var C 16个记录中的6个记录值<4.2，10个记录值> = 4.2。

• Var C >= 4.2 & class == positive: 0/6
• Var C >= 4.2 & class == negative: 6/6
  • Entropy(0,6) = 0
• VarC < 4.2 & class == positive: 8/10
• Var C < 4.2 & class == negative: 2/10
  • Entropy(8,2) = 0.72193

Entropy(Target, C) = P(>=4.2) * E(0,6) + P(< 4.2) * E(8,2) = (6/16) * 0 + (10/16) * 0.72193 = 0.4512

Var D的信息增益

Var D 16个记录中的5个记录值<5，11个记录值> = 1.4。

• Var D >= 1.4 & class == positive: 0/5
• Var D >= 1.4 & class == negative: 5/5
  • Entropy(0,5) = 0
• Var D < 1.4 & class == positive: 8/11
• Var D < 14 & class == negative: 3/11
  • Entropy(8,3) = -1 * ( (8/11)*log2(8/11) + (3/11)*log2(3/11)) = 0.84532

Entropy(Target, D) = P(>=1.4) * E(0,5) + P(< 1.4) * E(8,3) = 5/16 * 0 + (11/16) * 0.84532 = 0.5811575

具有更高值的属性应该作为根，并且熵0的分支应该被转换为叶节点。熵大于0的分支需要进一步分解。根据上述信息增益计算，我们可以构建一个决策树。我们应根据它们的值将属性放在树上。

基尼指数

基尼系数是衡量随机选择元素被错误识别的频率的度量标准。这意味着应该优选具有较低gini指数的属性。

示例：使用“gini index”作为标准构造决策树

我们将使用与信息增益示例相同的数据样本。我们试着用基尼系数作为标准。在这里，我们有5列，其中4列具有连续数据，第5列由类标签组成。

A，B，C，D属性可以被认为是预测变量，E列类标签可以被认为是目标变量。为了从这些数据构建决策树，我们必须将连续数据转换为分类数据。

我们选择了一些随机值来对每个属性进行分类：

Var A的基尼指数

Var A16个记录中的12个记录值<5，4个记录的值> = 5。

• Var A >= 5 & class == positive: 5/12
• Var A >= 5 & class == negative: 7/12
  • gini(5,7) = 1- ( (5/12)2 + (7/12)2 ) = 0.4860
• Var A <5 & class == positive: 3/4
• Var A <5 & class == negative: 1/4
  • gini(3,1) = 1- ( (3/4)2 + (1/4)2 ) = 0.375

将基尼指数加权汇总:

Var B的基尼指数

Var B16个记录中的12个记录值> = 3，4个记录值<5。

• Var B >= 3 & class == positive: 8/12
• Var B >= 3 & class == negative: 4/12
  • gini(8,4) = 1- ( (8/12)2 + (4/12)2 ) = 0.446
• Var B <3 & class == positive: 0/4
• Var B <3 & class == negative: 4/4
  • gin(0,4) = 1- ( (0/4)2 + (4/4)2 ) = 0

Var C的基尼指数

Var C16个记录中的6个记录值<4.2，10个记录值> = 4.2。

• Var C >= 4.2 & class == positive: 0/6
• Var C >= 4.2 & class == negative: 6/6
  • gini(0,6) = 1- ( (0/8)2 + (6/6)2 ) = 0
• Var C < 4.2& class == positive: 8/10
• Var C < 4.2 & class == negative: 2/10
  • gin(8,2) = 1- ( (8/10)2 + (2/10)2 ) = 0.32

Var D的基尼指数

Var D16个记录中的5个记录值<1.4值，11个记录值> = 1.4。

• Var D >= 1.4 & class == positive: 0/5
• Var D >= 1.4 & class == negative: 5/5
  • gini(0,5) = 1- ( (0/5)2 + (5/5)2 ) = 0
• Var D < 1.4 & class == positive: 8/11
• Var D < 1.4 & class == negative: 3/11
  • gin(8,3) = 1- ( (8/11)2 + (3/11)2 ) = 0.397

过拟合

构建决策树模型时，过拟合是一个实际问题。当算法越来越深入以减少训练集误差时，测试集误差却会增加，我们的模型的预测精度会下降。它通常发生于由于异常值和数据不规则而构建多个分支的时候。

我们可以使用两种方法来避免过拟合：

• 预修剪
• 后修剪

预先剪枝

预先剪枝，提前结束树的构建。如果分裂节点的良好度低于阈值，则倾向于不分裂节点。但是要选择一个合适的阀值是不容易的。

后剪枝

后剪枝中，先逐步构建一棵完整的树。如果树显示了过拟合的问题，那么剪枝是作为一个后剪枝步骤完成的。我们使用交叉验证数据来检查修剪的效果。通过使用交叉验证数据，测试扩展节点是否会带来改进。如果显示会带来改进，那么我们可以继续扩展该节点。但是，如果精度降低，则不应该扩展，节点应该转换为叶节点。

决策树算法优点和缺点

优点：

决策树很容易解释。它产生一组规则。 它遵循的方法与人类平时做出决策时的方法相同的。 复杂决策树模型的解释可以通过可视化来简化。即使门外汉也能够理解其逻辑。 要调整的超参数的数量几乎为零。

缺点：

决策树中过拟合的概率很高。 相比于其他机器学习算法，它对数据集预测精度较低。 带有分类变量的决策树对具有较大编号的类别得出的信息增益具有偏差。 当有很多类标签时，计算可能变得复杂。