通过C#实现深入理解决策树和C4.5算法
3.67/5 (6投票s)
如何在 C# 中实现决策树？
引言
决策树是一种流行的机器学习算法，用于分类和回归任务。它们用途广泛，可应用于广泛的问题，易于理解和解释，是机器学习初学者和专家宝贵的工具。它们适用于数值型和类别型数据，并能处理特征与目标变量之间的非线性关系。C4.5算法是构建决策树的知名算法之一，本系列文章旨在实现它。
以下关于此主题的教科书值得参考。这些书籍涵盖了决策树之外的许多广泛而普遍的机器学习主题。
此文章最初发布于此处。
深入理解熵
决策树采用C4.5算法，而C4.5算法又利用了熵的概念。在本节中，我们将尝试阐明香农在20世纪40年代末引入的这一关键概念。
重要
我们不应该被“熵”这个词吓倒。虽然它可能会勾起人们对热力学的回忆，并似乎令人望而生畏，但我们会发现，只要有效地呈现，它完全是可以理解的。
你应该称之为熵（...）。因为没有人知道熵是什么，所以当你使用这个词时，你总会占上风！（冯·诺依曼对香农说）
熵起源于信息论，并且首先解决这个方面至关重要。
什么是信息论？
严格来说，信息论是应用数学和电气工程的一个分支，涉及信息的量化。具体来说，它试图量化消息中的信息含量，并探索压缩它的方法，以便有效地传输到另一个位置。
这个定义有些非正式，可能显得抽象，但实际上，我们在日常生活中会不自觉地应用它的原理。
在这里，大卫通过告知萨曼莎约翰在假期期间去了意大利，来**压缩**信息。一旦萨曼莎得知约翰谈论了意大利，她就可以推断出他可能强调了该国的各种著名古迹或分享了其他广为人知的关于该国的事实。无论如何，当大卫提到约翰谈论了罗马斗兽场或提到了去罗马或米兰时，她都不会感到惊讶。
但是，如果大卫突然提到了一些意想不到的事情，萨曼莎可能会感到惊讶，因为这些信息在给定的上下文中并不明显。
熵仅仅是将这种情况用数学方式表达出来，仅此而已。熵试图量化消息中包含的惊喜或不确定性的程度。
熵（他参观了罗马）=0
熵（他遇到了他的女朋友）>0
如何做到这一点？引入惊喜概念
因此，熵试图在数学上表达这样的想法：**某些事件**是可预测的，并且不提供重要信息，而另一些事件则非常罕见（甚至**不可能**），反之亦然，提供有价值的信息。重新审视上一句话：我们使用事件、确定性、不可能性等术语。这些术语与概率相关，利用概率论来阐述我们的概念是恰当的。
非正式地说，我们为事件分配的概率越低，它就越令人惊讶，所以惊喜似乎是概率的某种递减函数。
P（他参观了意大利并遇到了意大利人）=1 ⟹ 惊喜（他参观了意大利并遇到了意大利人）=0
P（他参观了意大利并遇到了但丁）=0 ⟹ 惊喜（他参观了意大利并遇到了但丁）=+∞
由于概率只能存在于0到1的范围内，我们的目标是找到一个函数I，它将[0,1]映射到[0,+∞]，并且满足I(0)=+∞和I(1)=0的条件。
以下示例满足该属性，可以作为我们惊喜定义的候选。
I(P)=1/P−1
I(P)=−log2(P)
I(P)=−lnP
最终选择哪个函数？
事实上，我们还没有讲完。由于我们可以在几个函数中进行选择，因此选择一个不仅能量化惊喜，还能验证一些理想属性的函数将是有利的。如果我们能一举两得，那岂不是很棒？
考虑事件A：“约翰在比萨斜塔遇到了他的女朋友”和事件B：“约翰在地上捡到了钱”。这两个事件显然是独立的（约翰可能遇到他的女朋友而没捡到钱，或捡到钱而没遇到他的女朋友），我们可以看到，当萨曼莎听到这两个事件时，她的惊喜感会逐渐增加：**她的惊喜是累加的**。
在数学上，我们希望有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)=-log2P，依此类推。
香农选择了a=-ln2。
因此，I(P)=−log2P
熵去了哪里？
考虑以下两种情况
- 抛一枚公平的硬币。预期的结果是什么？如果它落地是正面，我们不会感到非常惊讶，但获得了我们之前不知道的信息。如果它落地是反面，我们也不会感到非常惊讶，但同样获得了我们之前不知道的信息。无论如何，无论结果如何，我们都获得了信息。
- 抛一枚不公平的硬币（10次中有9次落地是正面）。预期的结果是什么？如果落地是正面，我们根本不会感到惊讶，事实上，我们可以说获得的信息并不多。相反，如果落地是反面，我们会非常惊讶，并且获得了信息。
熵试图量化这些事实：**平均而言**，抛掷后我们可以获得多少信息？从这个意义上说，熵与概率中的期望非常相似。
熵通常用H表示。在第一种情况下，H(P)=(1/2)(−log2(1/2))+(1/2)(−log2(1/2))=1。在第二种情况下，H(P)=(1/10)(−log2(1/10))+(9/10)(−log2(9/10))=0.469。
这个结果符合直觉：在第一种情况下，我们每次都能获得信息，而在第二种情况下，我们获得的频率较低。第一种情况下的熵高于第二种情况是正常的。
简而言之，熵量化了随机变量中包含的信息量。当所有结果的可能性均等时，它达到最大值，并且随着概率分布变得更加确定或集中而减小。
在决策树和C4.5算法的上下文中，熵通常用于衡量数据集的纯度或无序度，以指导选择分裂以构建有效的决策树。
它具体量化什么？
想象一个场景，一个人被要求在1到100之间选择一个数字，我们的目标是通过问二元问题来猜测这个数字。我们应该如何处理？作为开发人员，我们知道最有效的方法是采用二分法，如下图所示
根据我们从计算机科学中获得的知识，我们知道到达选定数字所需的步数恰好是log2100。如果我们计算此场景的熵H，则H=log2100。因此，熵衡量在二元方案中获取消息中所有信息所需的最小步数（术语中的熵单位）。
现在，我们深入研究**ID3算法**的细节，运用我们获得的知识来深刻理解它的工作原理。
决策树具有简单性，使其易于初学者和经验丰富的机器学习实践者使用。它们像基于规则的引擎一样运行，其决策过程易于解释，是机器学习领域的重要数据结构。
当前的挑战在于自动化这些决策树的构建，而我们的旅程从深入研究ID3算法开始。
重要
目标确实是构建树，但真正的挑战在于获得尽可能小的树，以确保在对未知输入进行分类时能够快速使用。
什么是ID3算法？
我们必须意识到，根据我们逐步考虑的特征，可以构建多个树。例如，对于上面的例子，我们可以从“湿度”特征开始，而不是“天气”特征。
由于构建树的方法有多种，因此我们需要依靠启发式方法来构建它。启发式方法如下：算法以**贪婪**的方式构建树，从根节点开始，在每一步选择**信息量最大**的特征。
最后一句话包含两个重要的直觉。
- 贪婪地构建：根据提供最多信息量的特征进行分裂似乎是直观和自然的。
- 选择信息量最大的特征：信息量最大的特征的概念最初可能显得非正式，但幸运的是，我们在上一篇文章中学习了如何以数学方式定义这个概念。因此，我们将选择熵最高的特征，这表明信息量最大。
本文的后续部分需要一些在本网站上不易书写的数学公式。如果您想理解IC3算法的实际应用并学习如何实现C4.5算法，请访问此链接。或者，您可以下载随附的源代码来开始使用决策树。
历史
- 2023年12月19日：初稿