决策树算法原理及实现（一种像人脑工作的算法）

点击上方关注，All in AI中国

作者：Emma Grimaldi

决策树是机器学习中最常用的算法之一，主要用于分类，也用于回归问题。在我们做出决定之前我们都会问自己一些问题，而这时候我们的大脑就会像决策树一样工作。例如：外面是阴天吗？如果是的话，我需要带一把雨伞。

在训练数据集以对变量进行分类时，决策树的思想就是基于特定的特征值将数据拆分为较小的数据集，直到目标变量全部属于一个类别。人脑决定基于经验（即多云的天空）选择"拆分特征"，而计算机基于最大信息增益拆分数据集。让我们定义一个简单的问题，并跳转到一些计算中，看看这意味着什么。

猫和狗的数据集

假设我们基于体重和身高想要建立一个决策树来确定宠物是猫还是狗。我们可以根据两个特征之一的某些值来划分这些数据点，例如：对于大于15磅重量的宠物，确信是狗。至少基于这个非常简单的数据集。但是如果重量小于15磅，我的子集将包含两只猫和一只狗，所以我需要再次拆分子集，直到只剩下一个类。换句话说，直到所有的子集都变得纯粹。我实际上为这些数据值绘制了一个决策树，得出以下这张示例图：

决策树示例

每个决策树都以根节点开始，即第一次拆分。在不考虑太多的情况下，我们可以轻松地提出不同类型的根节点，以便在相同数量的步骤中将数据分成一个解决方案。但是计算机如何决定如何定义节点？当然，它会寻找最有效的方式，为了理解这是什么，我们需要引入基尼（Gini）这个系数，这是最常用的不等式度量。该不等式是指节点后的每个子集中的目标类。因此，可以在每次拆分后计算，并且根据节点之后不等式的变化，我们也可以定义"信息增益"。

基尼的定义

为了计算基尼，我们考虑在节点之后找到每个类的概率，我们将这些值的平方求和，然后从1中减去这个数量。因此，当一个子集是纯粹的（即其中只有一个类）时候，基尼系数将为0，因为找到该等级的概率确实是1。在这种情况下，我们说已经达到了一个目标，因为在我们实现目标时不再需要拆分。但是如果我们看一下上面的图片，在False情况下的根节点之后，我们有一个包含3个观察的子集，其中2个是猫，1个是狗。如果我们想要计算该子集的基尼系数，我们得出：

所得出的数据集的基尼系数，重量大于或等于15磅

可用于计算类不等式的另一个度量标准是熵（Entopy），而不是基尼（Gini）。它们具有相同的目的，但熵的变化幅度略有不同;但是，为此我们只会使用基尼（Gini）。

根据我们选择的拆分策略，我们将为每个子集提供不同的基尼（Gini）值，并且根据节点后的Gins值，我们可以定义信息增益：

信息增益的定义

这被定义为父基尼系数与子基尼系数的加权平均数之间的差值。如果我们参考上面的例子，通过简单地应用定义知道初始数据集的基尼系数等于0.48，我们可以计算根节点之后的信息增益（以15磅的重量值拆分）：

根节点后的信息增益

然后，决策树将考虑所有可能的拆分，并选择具有最高信息增益的拆分。事实上，我们进行了一些编码，看看Python的决策树是什么！

根节点后的信息增益

通过运行下面的代码，我们从头开始构建数据框，并仅在几行中拟合模型。

注意：在训练模型之前训练/测试拆分是很好的做法，以防止过度拟合，并且还要仔细检查这种模型对看不见的数据的执行情况。在这种情况下，我们跳过了这一步骤，因为数据帧只包含少量观察。

需要指出的是，在实例化DecisionTreeClassifier时，我没有在括号中指定任何参数。在处理非常大的数据集时，为了防止决策树失去控制和过度拟合，查看max_depth以指定决策树的最大划分数量是非常有用的。此外，设置max_features非常有用，max_features是一个限制在搜索最佳拆分时要查看的预测变量数量的参数。此外，如果你希望决策树基于熵而不是基尼（Gini进）行优化，则只需在实例化对象时编写criterion =entropy。如果要进一步探索如何调整模型，请参阅决策树文档。（http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html）

太好了，我们建立了我们的模型！但这到底意味着什么呢？决策树的美妙之处在于它易于解释，所以让我们绘制它！为了运行下面的代码片段，你可能需要首先在电脑上运行!pip install pydotplus pydot2

这段代码的输出将是下图。

这很酷，对吗？在上面的"手工制作"决策树中，我选择了15磅的重量作为根节点，算法决定拆分相同的变量，但是值为12。这就创造了一个只有狗的叶节点（体重大于12，事实上，gini = 0））。从根节点之后的True条件生成的子集已经在值8.5上的高度变量上进一步拆分。最后一次拆分生成了两个带有空gini值的纯子集。

那么，为什么我们应该还是不应该使用决策树？以下是其优缺点的简要列表：

（1）优点

• 其解释清晰，特别是如果我们需要将发现传达给非技术受众
• 它可以很好地处理嘈杂或不完整的数据
• 它可用于回归和分类问题

（2）缺点

• 它可能不稳定，这意味着数据的微小变化可能会导致模型发生重大变化
• 它倾向于过度拟合，这意味着低偏差但是方差很大：即使训练数据得分很高，也可能对于看不见的数据表现不佳

幸运的是，还有许多技术可以处理过度拟合，这是决策树的主要缺点。通过使用bagging 或​​增强方法，我们可以从决策树概念开始，通过使用RandomForestClassifier或AdaBoostClassifier等模型来提出更准确的分析。这些都是集成（ensamble）方法，但随机森林通过boostrapping生成了许多"新数据集"（即用替换品对原始数据帧进行采样）；它适用于每个新数据帧的决策树，并通过平均森林中的所有决策树来预测。相反，Ada Boost是一个自适应树，它通过调整不正确的分类实例同时使用相同的数据帧来自我学习。

,