点击上方关注，All in AI中国
作者：Georgios Drakos
决策树诞生于70多年前，如今已经成为最强大的机器学习工具之一。决策树的主要优点是一种"白盒"方法。这意味着人们可以轻松地解释他们的决策，而神经网络的复杂性通常过高。
它也可以表示为if-then规则集，以提高可读性。本文的目的是介绍决策树学习的基本理论基础，并提出ID3（迭代二分法3）算法。
决策树用于分类和回归问题，在这里我们将讨论分类问题。
决策树是什么？
决策树就像一棵倒置的树，其根位于顶部。决策树通过将树从树根到树叶节点（决策）向下排序来对实例进行分类，该节点提供实例的分类。决策树中的每个节点都指定了对实例的某些属性的测试，并且从该节点下降的每个分支对应于该属性的一个可能值。
举例说明一学习决策树。通过树对其分类，然后返回与该叶相关分类(是或否)。这棵树根据是否适合打网球来划
例如，实例（Outlook = Sunny，Temperature = Hot，Humidity = High，Wind = Strong）将被归类为否定实例（即，树预测PlayTennis = no）。
是什么让它与众不同？
- 它与其他工具不同，因为它可以直观地工作，即一个接一个地做出决定。
- 非参数：快速高效。
那么如何构建呢？
有几种算法可以构建决策树，其中一些是：
- CART（分类和回归树）→使用基尼指数（分类）作为指标。
- ID3（迭代二分法3）→使用熵功能和信息增益指标。
在此，我们将重点关注ID3算法。
什么是ID3算法？
ID3从"应该在树根处测试哪个属性？"这个问题开始。为了回答这个问题，每个实例属性都使用称为信息增益的统计测试进行评估，该测试测量给定属性根据训练样例分离训练样例的程度，并对他们的目标进行分类。选择最佳属性并将其用作树的根节点处的测试。
对每个分支重复此过程。这意味着我们在可能的决策树空间中执行自上而下的贪婪搜索，其中算法从不回溯到重新考虑先前的选择。
什么是熵？
熵是信息理论中常用的一种度量，它表征了实例的同质性。如果目标属性可以采用c个不同的值，那么相对于该c-分类的S的熵定义为：
其中pi是属于i类的S的比例。另请注意，如果目标属性可以采用c个可能的值，则熵可以与log2（c）一样大。
布尔目标分类的示例：
假设S是14个例子的集合，包括9个正例和5个负例 [9 +，5-]（c = 2）。然后S的熵是：
请注意，如果S的所有成员属于同一个类，则熵为0。如果所有成员都是正数（p⊕= 1），那么p⊖= 0，并且无法提取新信息。当p⊕= 1时，接收方知道所绘制的例子是正例，因此不需要发送消息，并且熵为零。另一方面，当p⊕=p⊖=0.5时，它会实现最大化。
相对于布尔分类的熵函数，作为正例的比例p+将在0和1之间变化。
什么是信息增益？
信息增益只是根据此属性对示例进行分区所导致的熵的预期减少。更确切地说，属性A的信息增益Gain（S，A）相对于示例集合S被定义为：
Gain（S，A）是关于目标函数值的信息，给定一些其他属性A的值。
示例：假设S是由包含Wind的属性描述的训练示例日的集合，其可以具有Weak值或Strong值。S包含9个正例和5个负例一共14个例子，也就是[9+，5-]。假设6个正例和2个负例具有Wind = Weak，其余的例子具有Wind=Strong。由于通过属性Wind对原始14个示例进行排序而导致的信息增益可以被计算为：
信息增益正是ID3用于在生长树的每个步骤中选择最佳属性的度量。
相对于目标分类，湿度提供了比风更大的信息增益。这里E代表熵，S代表原始集合的例子。给定最初收集的9个正的和5个负的例子，[9+，5 -]，根据它们的湿度对它们进行排序，会产生[3+，4 -](湿度=高)和[6+，1 -](湿度=正常)的集合。此分区获得的信息为.151，而属性Wind的增益仅为.048。
应用ID3算法的一个说明性示例
在此示例中，目标属性为打网球，其值为yes或no。必须通过考虑属性（Outlook, Temperature, Humidity, Wind）来预测。
训练目标概念打网球的示例
该算法的第一步是选择根节点的属性。ID3确定每个属性的信息增益，并选择信息增益最高的那个。
因此，选择Outlook作为根节点的决策属性，并且在根目录下为每个可能的值（即Sunny，Overcast和Rain）创建分支。请注意，Overcast所有样例只有正例，因此成为目标分类为Yes的叶结点（也称叶子节点）。因此，决策树的这个节点称为叶节点。相反，对于Outlook = Sunny和Outlook = Rain，我们有非零熵，决策树将在这些节点下面进一步阐述。
选择新属性和划分训练示例的过程仅考虑与该节点相关联的训练示例。此外，排除了在树中较高的属性，因此任何给定的属性最多只能沿决策树的任何路径出现一次。对于每个新叶节点都要继续进行这个过程，直到满足两个条件中的任何一个：（1）沿着该路径已经包括通过树的每个属性，或者（2）熵为零。
由ID3的第一步产生的部分学习的决策树。训练示例被分类到相应的后代节点。
我们可以观察到ID3的偏爱：
- 较短的树将超越较长的树。
- 放置高信息的树获得靠近根的属性。
结论
最终得出的结论是：
- 学习树可以表示为if-then规则集
- 信息增益测量是指导ID3爬山搜索的评估功能。
- ID3通过从根向下增长决策树来推断决策树，并贪婪地为添加到树中的每个新决策分支选择下一个最佳属性。
- ID3包括对较小决策树的偏好，为了对可用的训练样例进行分类，只需要根据需要增大决策树。
閱讀更多 AI中國 的文章
