决策树算法详解

决策树算法是人工智能领域中的一种机器学习算法。本文将全面介绍决策树算法的相关知识。首先，来了解什么是分类。

分类

分类是将数据点分配到不同组或不同类别的过程，通过添加标签来实现。数据点被添加到哪个组将基于某些条件来决定。换句话说，分类技术就是将观察结果归入不同类别的方法。

例如，使用的Gmail会将邮件分类为垃圾邮件或非垃圾邮件，这就是使用分类技术实现的。分类还用于安全保护，比如检查交易是否真实。如果借记卡是印度的，而在其他国家使用这张卡，那么会收到通知提醒，因为它识别出这笔交易不真实。

一些分类算法包括决策树、随机森林、朴素贝叶斯、KNN、逻辑回归和SVM，其中决策树算法是最常用的算法之一。

决策树

决策树是一种监督学习算法，它是所有可能解决方案的图形表示。所有决策都是基于某些条件做出的。

这个算法之所以被称为决策树，是因为它从根节点开始，像树一样分叉到多个解决方案。树从根开始，随着生长，它的分支也会越来越多。

为了更好地理解，来看一个树模型的例子。根节点是询问是否饿了的问题。如果不饿，那就回去睡觉。如果饿了，那就检查是否有足够的100美元。如果有足够的钱，那就去餐馆。如果没有足够的钱，那就去买些果汁。

通过这种方式，决策树根据某些条件将数据分成不同的组。来看一个数据集来进一步理解。在这个数据集中，可以看到水果根据颜色和直径被标记为芒果、葡萄或柠檬。

在这里，以直径作为根节点。如果直径大于3，那么颜色可能是绿色或黄色。如果直径小于3，那么肯定是红色的葡萄。现在需要检查颜色。如果不是黄色，那么肯定是芒果。但如果是黄色，那么有两种选择，可能是芒果或柠檬。所以有50%的概率是芒果，50%的概率是柠檬。

但是哪个问题作为根节点，哪个问题接下来？这里需要看哪个属性在特定点上可以区分标签。可以使用基尼不纯度来衡量单个节点的不确定性，也可以使用信息增益来衡量一个问题减少了多少不确定性。使用这些来决定哪个问题被问到以及在哪个点上。

术语

根节点：根节点是树的基础节点，整个树从它开始。

终端节点/叶节点：这是最终节点，不再进行进一步的分割。

分支/子树：通过分割节点形成分支。

剪枝：剪枝是分割的相反过程。剪枝是移除节点以减小决策树大小的过程。

父节点/子节点：根节点始终是父节点，所有从父节点派生的其他节点都被称为子节点。

CART算法

CART（分类和回归树）算法是一种预测模型，它展示了如何根据其他值预测变量的结果。

来看这些数据。这里有像Outlook、温度、湿度、风等属性，以及一个标签Play。所有这些属性决定是否进行游戏。

那么，应该首先选择哪个属性呢？将首先选择最能分类训练数据的属性。为了决定这一点，需要学习一些术语。

基尼指数：基尼指数是用于构建决策树的CART算法中衡量不纯度或纯度的指标。

信息增益：信息增益是衡量一个特征关于类别的信息量。它是在基于属性分割数据集后熵的减少。

构建决策树就是找到具有最高信息增益的属性。

方差减少：一般来说，方差是衡量数据变化的指标。因此，具有较低方差的属性将首先被分割。

卡方：它是一个算法，用于找到子节点和父节点之间差异的统计显著性。

在解决决策树问题之前，首先要做的是熵，它用于找到信息增益。知道，分割将基于信息增益进行。具有最高信息增益的属性将首先被选择。

熵

熵是不确定性的度量。它是一个衡量某物不纯度的指标。

首先，来理解什么是不纯度。想象一个装满樱桃的篮子和一个装有写有樱桃标签的碗。现在，如果从篮子里拿一个水果，从碗里拿一个标签。那么樱桃与樱桃匹配的概率是1，这里没有不纯度。

现在想象另一种情况，篮子里有不同种类的水果，碗里有不同水果名称的标签。现在，如果从篮子里随机拿一个水果，从碗里随机拿一个标签，那么樱桃与樱桃匹配的概率肯定不是1。它小于1。这里有不纯度。

其中，s = 总样本空间，P(yes) = 是的概率，P(no) = 否的概率。

如果“是”的数量等于“否”的数量，那么P(s)=0.5，熵(s) = 1。如果它包含全部是或全部否，那么P(s) = 1或0，熵(s) = 0。

计算信息增益

信息增益 = 熵(s) - [（平均权重）* 每个特征的熵]

让计算这个数据集的熵。这里总共有14个数据点，其中9个是“是”，5个是“否”。

E(s) = -(9/14)log(9/14) - (5/14)log(5/14)，E(s) = 0.41 + 0.53，E(s) = 0.94。

所以这个数据集的熵是0.94。

现在，让看看Outlook、Temperature、Humidity、Windy中哪个节点被选为根节点？

以Outlook为例，对于晴天，有3个“是”和2个“否”。对于阴天，全部是“是”。对于雨天，有3个“是”和2个“否”。

E(outlook=Overcast) = -1log1 = 0，E(outlook=rainy) = -3/5log3/5 - 2/5log2/5 = 0.971。

来自Outlook的信息，I(outlook) = 5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693。

来自Outlook的信息增益，IG(Outlook) = E(s) - I(outlook) = 0.94 - 0.693 = 0.247。

所以Outlook的信息增益是0.247。

现在让考虑Windy作为根节点并计算信息增益。

在False的情况下，有6个“是”和2个“否”，而在True的情况下，有3个“是”和3个“否”。

I(windy) = 8/14 * 0.811 + 6/14 * 1 = 0.892，IG(windy) = 0.94 - 0.892 = 0.048。

所以Windy的信息增益是0.048。

类似地，计算其他属性的信息增益。最终会得到，信息增益(Outlook) = 0.247，信息增益(Temperature) = 0.029，信息增益(Humidity) = 0.152，信息增益(Windy) = 0.048。

具有最高信息增益的属性被选中。所以这里可以看到Outlook的信息增益大于其他属性。因此，Outlook被选为根节点。

可以观察到，如果Outlook是阴天，那么最终输出将是“是”。但如果是晴天或雨天，那么需要再次计算剩余属性的熵并计算信息增益来决定下一个节点。当所有这些计算完成后，最终的树将如下所示。

现在让看看代码。首先，通过从sklearn导入DecisionTreeClassifier来创建一个模型。使用熵作为标准。然后使用训练数据集训练模型。predict方法预测结果。可以看到图片中如何将REAL和FAKE分类。

这就是决策树算法的工作原理。

在本文中，讨论了与决策树算法相关的一切。它是一种用于监督学习的分类算法。而且它易于阅读和实现。已经看到了决策树算法中使用的术语，如基尼指数、信息增益、卡方。进一步，已经看到了如何使用信息增益构建决策树。已经在Jupyter笔记本中使用scikit learn库实现了代码。