本文旨在详细解释ID3算法（用于构建决策树的众多算法之一）。我们使用伪造的Covid-19样本数据集解释该算法。

> Image Courtesy: http://keeperofthesouls.com/uncategorized/hello-world/

什么是决策树？

简而言之，决策树是一种包含节点（矩形框）和边线（箭头）的结构，并从数据集（代表要素/属性的列表和对应于记录的表）构建而成。每个节点要么用于制定决策（称为决策节点），要么代表结果（称为叶节点）。

决策树示例

上图描绘了一个决策树，用于对一个人是健康还是不健康进行分类。这里的决策节点是诸如''这个人是否小于30岁？'，'这个人吃垃圾吗？'之类的问题，叶子是两种可能的结果之一。适合与不适合看决策树，我们可以说做出以下决定：如果一个人不到30岁并且不吃垃圾食品，那么他就适合了;如果一个人不到30岁并且吃垃圾食品，然后他变得不健康，依此类推。

初始节点称为根节点（蓝色），最终节点称为叶节点（绿色），其余节点称为中间或内部节点。根节点和中间节点代表决策，而中间节点代表决策。叶节点代表结果。

ID3简介

ID3代表迭代二分器3，之所以这样命名，是因为该算法在每个步骤中将迭代（重复）地将特征二分（划分）为两个或更多组。

ID3由Ross Quinlan发明，它使用自上而下的贪婪方法来构建决策树。简而言之，自上而下的方法意味着我们从顶部开始构建树，而贪婪的方法则意味着在每次迭代中，我们都选择当前最好的特征来创建节点。

通常，ID3仅用于仅具有名义特征的分类问题。

数据集描述

在本文中，我们将使用COVID-19感染的样本数据集。整个数据集的预览如下所示。

+----+-------+-------+------------------+----------+
| ID | Fever | Cough | Breathing issues | Infected |
+----+-------+-------+------------------+----------+
| 1 | NO | NO | NO | NO |
+----+-------+-------+------------------+----------+
| 2 | YES | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 3 | YES | YES | NO | NO |
+----+-------+-------+------------------+----------+
| 4 | YES | NO | YES | YES |
+----+-------+-------+------------------+----------+
| 5 | YES | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 6 | NO | YES | NO | NO |
+----+-------+-------+------------------+----------+
| 7 | YES | NO | YES | YES |
+----+-------+-------+------------------+----------+
| 8 | YES | NO | YES | YES |
+----+-------+-------+------------------+----------+
| 9 | NO | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 10 | YES | YES | NO | YES |
+----+-------+-------+------------------+----------+
| 11 | NO | YES | NO | NO |
+----+-------+-------+------------------+----------+
| 12 | NO | YES | YES | NO |
+----+-------+-------+------------------+----------+
| 13 | NO | YES | YES | NO |
+----+-------+-------+------------------+----------+
| 14 | YES | YES | NO | NO |
+----+-------+-------+------------------+----------+

这些列是不言自明的。 Y和N分别代表是和否。 '已感染'列Y和N中的值或类别分别表示'已感染'和'未感染'。

用于制作决策节点的列。 '呼吸问题'，'咳嗽'和'发烧'称为特征列，或仅称为特征，而用于叶节点的列（即'感染'）称为目标列。

ID3中的指标

如前所述，ID3算法在构建决策树时的每一步都会选择最佳功能。在您问之前，问题的答案是：' ID3如何选择最佳功能？'是ID3使用信息增益或仅通过增益来找到最佳功能。

信息增益可计算熵的减少量，并衡量给定要素对目标类别的区分或分类的程度。信息增益最高的功能被选为最佳功能。

简而言之，熵是数据集的无序量度，数据集的熵是数据集的目标特征中无序量度。对于二进制分类（目标列只有两种类型的类别），熵为0 如果目标列中的所有值都是同质的（相似），并且如果目标列中两个类的值均相等，则为1。

我们将数据集表示为S，熵的计算公式为：

Entropy(S) = - ∑ pᵢ * log₂(pᵢ) ; i = 1 to n

其中，n是目标列中类的总数（在我们的案例中，n = 2，即I和NI）pᵢ是类' i'的概率或'目标列中具有类i的行数'的比率到数据集中的'总行数'。

特征列A的信息增益计算为：

IG(S, A) = Entropy(S) - ∑((|Sᵥ| / |S|) * Entropy(Sᵥ))

其中Sᵥ是S中特征列A的值为v的行集合|Sᵥ| 是Sᵥ中的行数，同样| S | 是S中的行数。

ID3步骤

· 计算每个功能的信息增益。

· 考虑到所有行都不属于同一类，请使用信息增益最大的功能将数据集S分成子集。

· 使用具有最大信息增益的功能创建决策树节点。

· 如果所有行都属于同一类，则将当前节点作为以该类为标签的叶节点。

· 重复其余功能，直到用尽所有功能，或者决策树具有所有叶节点。

在我们的数据集上实施

如上一节所述，第一步是找到最佳功能，即具有最大信息增益（IG）的功能。现在，我们将为每个功能计算IG，但为此，我们首先需要计算S的熵

在我们的数据集S中，总共有14行，其中有8行的目标值为YES，有6行的目标值为NO。 S的熵计算为：

Entropy(S) = — (8/14) * log₂(8/14) — (6/14) * log₂(6/14) = 0.99

注意：如果目标列中的所有值都相同，则熵将为零（这意味着它没有随机性或随机性为零）。

现在，我们计算每个功能的信息增益：

发烧的IG计算：在此（发烧）功能中，有8行的值为YES和6行的值为NO。目标值NO

+-------+-------+------------------+----------+
| Fever | Cough | Breathing issues | Infected |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
+-------+-------+------------------+----------+
| YES | YES | NO | NO |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | YES | NO | YES |
+-------+-------+------------------+----------+
| YES | YES | NO | NO |
+-------+-------+------------------+----------+

如下所示，在具有否的6行中，有2行具有目标值YES和4行具有目标值NO。

+-------+-------+------------------+----------+| Fever | Cough | Breathing issues | Infected |+-------+-------+------------------+----------+| NO | NO | NO | NO |+-------+-------+------------------+----------+| NO | YES | NO | NO |+-------+-------+------------------+----------+| NO | YES | YES | YES |+-------+-------+------------------+----------+| NO | YES | NO | NO |+-------+-------+------------------+----------+| NO | YES | YES | YES |+-------+-------+------------------+----------+| NO | YES | YES | NO |+-------+-------+------------------+----------+

下面的方框演示了发烧信息增益的计算。

# total rows|S| = 14For v = YES, |Sᵥ| = 8Entropy(Sᵥ) = - (6/8) * log₂(6/8) - (2/8) * log₂(2/8) = 0.81For v = NO, |Sᵥ| = 6Entropy(Sᵥ) = - (2/6) * log₂(2/6) - (4/6) * log₂(4/6) = 0.91# Expanding the summation in the IG formula:IG(S, Fever) = Entropy(S) - (|Sʏᴇꜱ| / |S|) * Entropy(Sʏᴇꜱ) - (|Sɴᴏ| / |S|) * Entropy(Sɴᴏ)∴ IG(S, Fever) = 0.99 - (8/14) * 0.81 - (6/14) * 0.91 = 0.13

接下来，我们计算'咳嗽'和'呼吸问题'特征的IG。您可以使用此免费的在线工具来计算信息增益。

IG(S, Cough) = 0.04

IG(S, BreathingIssues) = 0.40

由于功能``呼吸问题''具有最高的信息增益，因此可用于创建根节点。因此，在此初始步骤之后，我们的树如下所示：

接下来，从剩余的两个未使用功能（发烧和咳嗽）中，我们确定哪个最适合呼吸问题的左分支。由于呼吸问题的左分支表示是，因此我们将使用原始数据的子集也就是说，'呼吸问题'列中值为YES的行集。这8行如下所示：

+-------+-------+------------------+----------+
| Fever | Cough | Breathing issues | Infected |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | NO |
+-------+-------+------------------+----------+

接下来，我们使用子集Sʙʏ（设置呼吸问题为是）计算发烧和咳嗽特征的IG，如上所示：

注意：对于IG计算，熵将根据子集Sʙʏ而非原始数据集S计算得出。

IG(Sʙʏ, Fever) = 0.20

IG(Sʙʏ, Cough) = 0.09

发烧的IG大于咳嗽的IG，因此我们选择发烧作为呼吸问题的左分支：我们的树现在如下所示：

接下来，我们为'呼吸问题'的右分支找到具有最大IG的特征。但是，由于只剩下一个未使用的功能，我们别无选择，只能使其成为根节点的右分支，所以我们的树现在看起来像这样：

没有更多未使用的功能，因此我们在此处停止并跳至创建叶节点的最后一步。对于Fever的左叶节点，我们看到原始数据集中具有呼吸问题和Fever两个值的行的子集如是。

+-------+-------+------------------+----------+| Fever | Cough | Breathing issues | Infected |+-------+-------+------------------+----------+| YES | YES | YES | YES |+-------+-------+------------------+----------+| YES | NO | YES | YES |+-------+-------+------------------+----------+| YES | YES | YES | YES |+-------+-------+------------------+----------+| YES | NO | YES | YES |+-------+-------+------------------+----------+| YES | NO | YES | YES |+-------+-------+------------------+----------+

由于目标列中的所有值均为YES，因此我们将左侧叶子节点标记为YES，但为了使其更具逻辑性，我们将其标记为Infected。

同样，对于发烧的右侧节点，我们会看到原始数据集中行的子集，其呼吸问题值为YES，发烧值为NO。

+-------+-------+------------------+----------+| Fever | Cough | Breathing issues | Infected |+-------+-------+------------------+----------+| NO    | YES   | YES              | YES      |+-------+-------+------------------+----------+| NO    | YES   | YES              | NO       |+-------+-------+------------------+----------+| NO    | YES   | YES              | NO       |+-------+-------+------------------+----------+

在这里，不是所有值，而是所有值都是NO，因此NO或Not Infected成为我们的右叶节点。现在，我们的树如下所示：

我们对节点Cough重复相同的过程，但是此处的左右叶子都相同，即NO或Not Infected如下图所示：

看起来很奇怪，不是吗？我知道！呼吸问题的正确节点与'未感染'类别的叶子节点一样好。这是ID3的缺点之一，它不会修剪。

修剪是一种通过删除不必要的节点来减少决策树的大小和复杂性的机制。有关修剪的更多信息，请参见此处。

ID3的另一个缺点是过拟合或高方差，即它很好地学习了它使用的数据集，因此无法归纳为新数据。

摘要

我们详细介绍了ID3算法的过程，并看到仅使用两个度量标准即使用该算法创建决策树是多么容易。熵和信息增益。

希望你喜欢它，伙计们！谢谢阅读

参考文献：

https://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm

任何人都可以根据我们的政策在'中'上发布，但我们并没有对每个故事进行事实检查。有关冠状病毒的更多信息，请参见cdc.gov。

(本文翻译自Yaser Sakkaf的文章《Decision Trees: ID3 Algorithm Explained》，参考：
https://towardsdatascience.com/decision-trees-for-classification-id3-algorithm-explained-89df76e72df1)

决策树：ID3算法解释