决策树是机器学习领域中一种非常强大且灵活的工具，它被广泛应用于分类和回归任务。决策树易于理解且解释性强，无论是机器学习新手还是专家，都能从中获益。它们能够处理数值型和分类型数据，并且能够处理特征与目标变量之间的非线性关系。C4.5算法是构建决策树的著名算法之一，本文旨在实现这一算法。
在深入理解决策树之前，推荐阅读以下几本书籍，它们不仅涵盖了决策树，还涉及了广泛的机器学习主题。
本文最初发布于此处。
决策树使用C4.5算法，该算法利用了信息熵的概念。本节将尝试阐明这一由Shannon在20世纪40年代末引入的关键概念。
重要提示：不应该被“信息熵”这个术语吓倒。尽管它可能让人联想到热力学并显得难以理解，但当有效地呈现它时，就会发现它是完全可理解的。
正如冯·诺依曼对香农所说：“应该称之为信息熵（...）。因为没有人知道信息熵是什么，所以每当使用这个术语时，总是处于有利地位！”
信息熵起源于信息论，首先需要解决这个方面。
严格来说，信息论是应用数学和电气工程的一个分支，涉及信息的量化。具体来说，它试图量化消息中的信息内容，并探索压缩它的方法，以便于有效地传输到另一个位置。
这个定义可能有些非正式，看起来可能很抽象，但实际上，在日常生活中无意识地应用了它的原则。
例如，David通过告诉Samantha John在假期访问了意大利，从而压缩了信息。一旦Samantha得知John讨论了意大利，她可以推断他可能突出了各种著名的纪念碑或分享了该国其他众所周知的事实。无论如何，如果David提到John谈论了斗兽场或提到访问罗马或米兰，她不会感到惊讶。
但是，如果David突然提到了意料之外的事情，Samantha可能会感到惊讶，因为这些信息在给定的上下文中并不明显。
信息熵简单地用数学术语表达了这种情况，不多也不少。
信息熵试图量化消息中的惊讶或不确定性水平。
信息熵(He visited Roma)=0
信息熵(He met his girlfriend)>0
因此，信息熵试图用数学表达某些事件是可预测的，并不提供重要信息，而其他事件则非常罕见（甚至不可能），相反，提供了有价值的信息。回想一下前一句话：使用了事件、确定性和不可能性等术语。这个术语与概率有关，使用概率理论来表达概念是合适的。
非正式地说，分配给事件的概率越低，它就越令人惊讶，所以惊喜似乎是概率的某种递减函数。
P(He visited Italy and met Italian people)=1 ⟹ surprise(He visited Italy and met Italian people)=0
P(He visited Italy and met Dante)=0 ⟹ surprise(He visited Italy and met Dante)=+∞
由于概率只能在0和1的范围内存在，目标是找到一个函数，记为I，它从[0,1]映射到[0,+∞]，条件是I(0)=+∞和I(1)=0。
以下示例满足该属性，可以作为定义惊喜的候选。
I(P)=1/P−1
I(P)=−log
2
(P)
I(P)=−lnP
事实上，故事还没有结束。由于可以选择多个函数，选择一个不仅量化惊喜而且验证一些理想属性的函数将是有利的。如果能用一块石头杀死两只鸟，那岂不是很棒吗？
考虑事件A：“John在比萨斜塔遇到了他的女朋友”和事件B：“John在地上发现了钱”。这两个事件显然是独立的（John可以在不发现钱的情况下遇到他的女朋友，或者在不遇到他的女朋友的情况下发现钱），可以观察到，当她听到这两个事件时，Samantha的惊讶逐渐增加：
她的惊讶是加性的。
数学上，希望有I(P(A,B)=I(P(A)P(B))=I(P(A))+I(P(B))。这个方程是柯西函数方程，知道解是对数。
更精确地说，必须存在a∈R，使得I(P)=alnP。如果a=−1，那么I(P)=−lnP，如果a=−ln2，那么I(P)=−log 2 P，依此类推。
Shannon选择了a=−ln2。
因此，I(P)=−log 2 P
考虑以下两种情况：
一枚公平的硬币被抛掷一次。预期的结果是什么？如果它落在正面，不会感到非常惊讶，但获得了没有的信息。如果它落在反面，也不会感到惊讶，事实上，可以说没有获得太多信息。无论如何，不管结果如何，都获得了信息。
一枚有偏见的硬币（10次中有9次落在正面）被抛掷一次。预期的结果是什么？如果它落在正面，一点也不会感到惊讶，实际上，可以说没有获得太多信息。相反，如果它落在反面，会非常惊讶并获得了信息。
信息熵试图量化这些事实：平均在抛掷后可以获得多少信息？从这个意义上说，信息熵与概率中的期望非常相似。
信息熵通常表示为H。在第一种情况下，H(P)=(1/2)(−log 2(1/2) )+(1/2)(−log 2 (1/2))=1。在第二种情况下，H(P)=(1/10)(−log 2 (1/10))+(9/10)(−log 2 (9/10))=0.469。
这个结果与直觉一致：在第一种情况下，每次都能获得信息，而在第二种情况下，很少获得信息。第一种情况下的信息熵高于第二种情况似乎是合理的。
简而言之，信息熵量化了随机变量中包含的信息量。当所有结果都同样可能时，它达到最大值，并且随着概率分布变得更加确定或集中而减少。
在决策树和C4.5算法的背景下，信息熵通常用于衡量一组数据点的不纯度或混乱程度，帮助指导选择分割以构建有效的决策树。
想象一个场景，一个人被要求在1到100之间选择一个数字，目标是通过询问二元问题来猜测这个数字。应该如何接近这个问题？作为开发人员，理解最有效的方法是使用二分法，如下图所示：
借鉴从计算机科学中的知识，认识到到达所选数字所需的步骤数量正是log 2 100。如果计算这个场景的熵H，有H=log 2 100。因此，信息熵衡量了在二元方案中获取消息中包含的所有信息所需的最小步骤数（用熵的术语来说）。
现在深入探讨ID3算法的复杂性，应用所学的知识来深刻理解其工作原理。
决策树的简单性使其对新手和经验丰富的机器学习从业者都易于理解。它们的决策过程类似于基于规则的引擎，易于解释，使它们成为机器学习领域的关键数据结构。
目前的挑战在于自动化构建这些决策树，旅程从深入研究ID3算法开始。
重要提示：目标确实是构建树，但真正的挑战在于获得尽可能小的树，以确保在分类未知输入时快速使用。
必须意识到，基于连续考虑的特征，可以构建多棵树。例如，在上面的例子中，可以先从“湿度”特征开始，而不是“天气”特征。
由于有多种方法可以构建树，因此需要依赖启发式方法来构建它。启发式方法如下：算法以贪婪的方式构建树，从根开始，并在每一步选择最具信息量的特征。
最后一句话包含了两个重要的直觉。
以贪婪的方式构建：基于提供最多信息的特征进行分割似乎是直观和自然的。
选择最具信息量的特征：最具信息量的特征的概念最初可能看起来是非正式的，但幸运的是，在前一篇文章中学到了如何用数学定义这个概念。因此，将选择信息熵最高的特征，表明信息量最大。