大树荫：决策树的算法原理

灰太狼 2022-12-26 00:50 177阅读 0赞

### 本篇目录 ###

*  导读
 *  信息熵和信息量化
 *  信息增益
 *  信息增益的计算步骤
 *   *  根
     *  猫枝叶、部分日用品枝叶
     *  第一次分枝
     *  重要箱子枝叶、蛋糕箱枝叶和空箱子枝叶
     *  第二次分枝
     *  垃圾箱枝叶和剩余日用品箱枝叶
     *  总结
 *  题外话
 *   *  为什么概率越大越可靠？
     *  为什么代码中的 x x x不是从0开始？
     *  为什么要分类？

# 导读 #

**在之前写的一篇文章：[小树苗：决策树是什么？][Link 1]中说明了决策树的定义与目的，接下来我们就要开始了解决策树背后的数学意义了。**

# 信息熵和信息量化 #

**“等下，信息量有点大……”**

当我们面对有点难以接受和一时间反应不过来的信息时，我们经常说这句话（*这句话应该还没过气吧！*）。

要是你家的猫娘学习机器学习，一定是一脸不明所以地顶着屏幕上奇奇怪怪的数学公式；而如果是你和你的室友，那么说不定就会夸夸其谈。为什么会有这样的差别？因为你的室友和你的猫娘**所接收的信息量是不相同的**。

信息量**越是不足**，那么这件事情就**越不确定**，就像猫娘完全不知道机器学习是个啥玩意儿，要**把这件事情搞清楚所需要的信息就越多**；反之，信息量**越足**，各种事情事物也看得**愈发明朗**，你的室友甚至都能说出`kmeans`、决策树等等机器学习算法，要**把这件事情搞清楚所需要的信息就越少**。

那么，信息量怎么衡量？单纯的通过人的接受能力和反应时间实在是太主观了，也太武断了。更何况，如果不是使用数学方法衡量的话，现在也很难直接使用机器学习的方法帮助我们**充分挖掘信息中的潜在价值**。

> 1948年，像农在他著名的《通信的数学原理》中提出了**信息熵**的概念，从而解决了信息量化的问题。
> 
> ——摘自《scikit-learn机器学习常用算法原理与编程实战》 \[著\]黄永昌

如果你的脑海里还残存了一点点高中化学的知识，你应该知道，**熵是一种不稳定状态的度量方式**。**熵越大**，**空间内越混乱**。**那么信息熵也应当类似**。如果说对这件事**完全弄明白了**，那么就是一种**稳定状态**；而**半懂不懂**则是一种**不稳定的状态**。信息熵描述的就是对这个信息来说从不稳定（*也就是没有完全理解*）到稳定（*也就是彻底理解*）之间的差距。

信息熵的量化公式就是：

H ( X ) = − ∑ x ∈ X P ( x ) log ⁡ 2 P ( x ) H(X) = -\\sum\_\{x\\in X\}P(x)\\log\_2P(x) H(X)=−x∈X∑P(x)log2P(x)

其中， X X X指所研究的事件集合， x x x指事件集合中所出现的其中一个事件， P ( x ) P(x) P(x)则是事件 x x x所出现的概率。

如果在我面前有一个宝箱，出货率如下表所示：

<table> 
 <thead> 
 <tr> 
 <th>物品</th> 
 <th>概率</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>一次性湿纸巾一包</td> 
 <td> 25 % 25\% 25%</td> 
 </tr> 
 <tr> 
 <td>一次性纸手帕一包</td> 
 <td> 25 % 25\% 25%</td> 
 </tr> 
 <tr> 
 <td>一次性塑料碗一个</td> 
 <td> 25 % 25\% 25%</td> 
 </tr> 
 <tr> 
 <td>一次性木筷子一双</td> 
 <td> 25 % 25\% 25%</td> 
 </tr> 
 </tbody> 
</table>

既然每一种一次性用品抽中的概率都是 25 % 25\\% 25%，那么任意抽一次，也就只有这些结果：

*  一次性湿纸巾一包
 *  一次性纸手帕一包
 *  一次性塑料碗一个
 *  一次性木筷子一双

所以，信息熵也就是：

H ( 抽 奖 结 果 ) = − ( 1 4 log ⁡ 2 1 4 ) ∗ 4 = 2 ( b i t ) H(抽奖结果)=-(\\frac\{1\}\{4\}\\log\_2\\frac\{1\}\{4\})\*4=2(bit) H(抽奖结果)=−(41log241)∗4=2(bit)

没错，结果的单位实际上是**比特**。要确认我这次抽到的是4种一次性用具的哪一种，只需要**两个比特**就能解决，也就是一个字节的 1 4 \\frac\{1\}\{4\} 41就可以了，大概就是`00000000`到`00000011`，或者是`0x00`到`0x03`。

很神奇不是么？

# 信息增益 #

什么是信息增益？**就是信息量的差值**。**信息增益只是一个值**，**没有正负的矢量意义**。还记得之前提到的**权重**么？**这个权重就是信息增益**。如果增益非常大，那么权重就会非常大。在决策树彻底长成古老的巨树之后，信息增益就会帮我们从根出发，一直上升到对应的叶子。

好的，说明之前，让我们先换个场景：

现在你刚拿到你的小蛋糕店，也装修完了，现在剩下一地的箱子，共 100 100 100只。 8 8 8个装了垃圾， 16 16 16个是日用品， 16 16 16个是对蛋糕店来说有用的， 4 4 4个是极其重要的，还有 8 8 8个被你的猫娘们占用了，剩下 48 48 48个是空箱子。现在不再是抽奖了，而是你要逐一分类。当然，这个时候你完全可以看看里面是什么。

渐渐地，在分类的过程中，你也找到了诀窍：

*  空箱子非常轻，踢一脚就会滚两圈；
 *  装了垃圾的箱子会看起来脏一点，蒙着一层灰；
 *  装了日用品的箱子中，有的会伸出来衣架，有的会散发出沐浴露的香味等等；
 *  装了蛋糕店相关的箱子和极其重要的箱子会有很明显的警告标志；
 *  被猫娘们霸占的箱子则会伸出来一只猫尾巴或者猫爪爪

看起来很有规律了嘛。那么就开始分类吧！

# 信息增益的计算步骤 #

首先，我们先分析一下，对于这 100 100 100个箱子里面，随便选一个打开看的话，就会有这些事件：

X = \{ 空 箱 子 ⋯ x 1 垃 圾 箱 ⋯ x 2 日 用 品 箱 ⋯ x 3 蛋 糕 箱 ⋯ x 4 重 要 箱 子 ⋯ x 5 猫 娘 箱 ⋯ x 6 \} X= \\left\\\{ \\begin\{matrix\} 空箱子&\\cdots&x\_1\\\\垃圾箱&\\cdots&x\_2\\\\日用品箱&\\cdots&x\_3\\\\蛋糕箱&\\cdots&x\_4\\\\重要箱子&\\cdots&x\_5\\\\猫娘箱&\\cdots&x\_6 \\end\{matrix\} \\right\\\} X=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧空箱子垃圾箱日用品箱蛋糕箱重要箱子猫娘箱⋯⋯⋯⋯⋯⋯x1x2x3x4x5x6⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫

概率分布就是这样：

好的，接下来就是信息熵了。

## 根 ##

一开始就是一片混沌的6种箱子混在一起， H ( X ) = − ∑ x ∈ X P ( x ) ∗ log ⁡ x P ( x ) = 2.1231 H(X)=-\\sum\_\{x\\in X\}P(x)\*\\log\_xP(x)=2.1231 H(X)=−∑x∈XP(x)∗logxP(x)=2.1231。

## 猫枝叶、部分日用品枝叶 ##

为了先照顾你心目中最重要的几只小猫娘，你决定**先看看有没有猫**。于是，你看看箱子里伸出来了啥，然后发现了 4 4 4个伸出来猫爪爪的箱子和 4 4 4个伸出来猫尾巴的箱子，还发现了 8 8 8个伸出来衣架的日用品箱子。于是， H ( x 6 ) = − P ( x 6 ) ∗ log ⁡ 2 P ( x 6 ) = 3.64 ∗ 0.08 = 0.2912 H(x\_6)=-P(x\_6)\*\\log\_2P(x\_6)=3.64\*0.08=0.2912 H(x6)=−P(x6)∗log2P(x6)=3.64∗0.08=0.2912，这就是找到猫娘所需要的信息增益。对于突然发现的日用品箱 ( x 7 ) (x\_7) (x7)我们也计算一下， H ( x 7 ) = − P ( x 7 ) ∗ log ⁡ 2 P ( x 7 ) = 0.2915 H(x\_7)=-P(x\_7)\*\\log\_2P(x\_7)=0.2915 H(x7)=−P(x7)∗log2P(x7)=0.2915

## 第一次分枝 ##

那么，然后剩下来**空箱子**、**垃圾箱**、**蛋糕箱和剩下的日用品箱**，记为 Y Y Y， H ( Y ) = − ∑ x ∈ Y P ( x ) ∗ log ⁡ 2 P ( x ) = 1.5143 H(Y)=-\\sum\_\{x\\in Y\}P(x)\*\\log\_2P(x)=1.5143 H(Y)=−∑x∈YP(x)∗log2P(x)=1.5143

然后看看**有没有警告标记**。找到警告标记之后，会找到**蛋糕箱**和**对自己非常重要的箱子**，记为 Z Z Z， H ( Z ) = − ∑ x ∈ Z P ( x ) ∗ log ⁡ 2 P ( x ) = 0.6088 H(Z)=-\\sum\_\{x\\in Z\}P(x)\*\\log\_2P(x)=0.6088 H(Z)=−∑x∈ZP(x)∗log2P(x)=0.6088。

而剩下一些**空箱子**、**垃圾箱**和剩下的**日用品箱**，记为 A A A， H ( x ) = − ∑ x ∈ A P ( x ) ∗ log ⁡ 2 P ( x ) = 1.0913 H(x)=-\\sum\_\{x\\in A\}P(x)\*\\log\_2P(x)=1.0913 H(x)=−∑x∈AP(x)∗log2P(x)=1.0913

## 重要箱子枝叶、蛋糕箱枝叶和空箱子枝叶 ##

找出了蛋糕箱和重要箱子之后，我们再**打开看看**箱子里是个啥。打开之后如果发现了相册和笔记本，那就是**重要箱子**， H ( x 5 ) = − P ( x 5 ) ∗ log ⁡ 2 P ( x 5 ) = 0.1858 H(x\_5)=-P(x\_5)\*\\log\_2P(x\_5)=0.1858 H(x5)=−P(x5)∗log2P(x5)=0.1858。

同时，我们也找到了**蛋糕箱**， H ( x 4 ) = − P ( x 4 ) ∗ log ⁡ 2 P ( x 4 ) = 0.423 H(x\_4)=-P(x\_4)\*\\log\_2P(x\_4)=0.423 H(x4)=−P(x4)∗log2P(x4)=0.423。

我们刚刚通过有没有警示标志找出了**空箱子**、**垃圾箱**和剩下的**日用品箱**，我们接下来就**随便踢一脚试试**，如果瞬间就飞出去翻滚两圈，那就是**空箱子**。于是， H ( x 1 ) = − P ( x 1 ) ∗ log ⁡ 2 P ( x 1 ) = 0.5803 H(x\_1)=-P(x\_1)\*\\log\_2P(x\_1)=0.5803 H(x1)=−P(x1)∗log2P(x1)=0.5803

## 第二次分枝 ##

那么，踢不动的就是垃圾箱和日用品箱了，记为 B B B， H ( B ) = − ∑ x ∈ B P ( x ) ∗ log ⁡ 2 P ( x ) = 0.583 H(B)=-\\sum\_\{x\\in B\}P(x)\*\\log\_2P(x)=0.583 H(B)=−∑x∈BP(x)∗log2P(x)=0.583

## 垃圾箱枝叶和剩余日用品箱枝叶 ##

最后，我们在最后剩下的**箱子里间闻一闻**，就能够通过有没有沐浴露的清香来分辨最后的两种箱子。没有香味那就应该是充满了灰尘味道的**垃圾箱**了。于是， H ( x 2 ) = − P ( x 2 ) ∗ log ⁡ x P ( x 2 ) = 2.915 H(x\_2)=-P(x\_2)\*\\log\_xP(x\_2)=2.915 H(x2)=−P(x2)∗logxP(x2)=2.915。最后就是剩下的 8 8 8个**日用品箱**了，也就是 H ( x 3 ) = − P ( x 3 ) ∗ log ⁡ 2 P ( x 3 ) = 2.915 H(x\_3)=-P(x\_3)\*\\log\_2P(x\_3)=2.915 H(x3)=−P(x3)∗log2P(x3)=2.915。

## 总结 ##

这下整颗树就明了了呢。画张图总结一下吧：

![决策流程图][6d5158592654818b256af6df676d7ffe.png]

看起来非常不错啊！

# 题外话 #

## 为什么概率越大越可靠？ ##

我们一直在计算熵值，也就是这个函数 H ( x ) = − P ( x ) ∗ log ⁡ 2 P ( x ) H(x)=-P(x)\*\\log\_2P(x) H(x)=−P(x)∗log2P(x)。如果我们吧这个函数画出来：

使用了这样几行代码：

import matplotlib.pyplot as pyplot
    import numpy as np
    import math
    
    if __name__ == '__main__':
    	# 准备x轴，并不做变换
        x = np.linspace(0.01, 1, 100)
        # 准备y轴，做一些变换以生成新的序列
        y = x
    	# 使用map迭代变换，最后将得出来的迭代器强转为序列
        y = list(map(lambda y: -y * math.log(y) / math.log(2), y))
    	# 贴一些图表文字
        pyplot.title('-P(x)*logP(x)')
        pyplot.xlabel('range of X:0.01->1')
        pyplot.ylabel('value of Y')
    	# 画图
        pyplot.plot(x, y)
        pyplot.show()
        pass

然后就有了下图的结果。

![决策流程图][1b4e8286cc04d0ce0f977d1b5c665a1c.png]

可以看到，随着概率从 0 0 0到 1 1 1的变化过程中，**熵值不断变大**，**然后到达峰值**（*大约 0.5307290449339367 0.5307290449339367 0.5307290449339367左右*）**之后开始减小**，**逐渐到 0 0 0**。

这也正好说明了：**若是对于这件事发生的概率越大**、**对这件事越确定**，**熵值越低**，**也就越稳定**、**越可靠**。

## 为什么代码中的 x x x不是从0开始？ ##

细心的你会发现，为什么 P ( x ) P(x) P(x)不从 0 0 0开始？因为 log ⁡ 0 = − ∞ \\log0=-\\infin log0=−∞，于是 H ( 0 ) = − P ( 0 ) ∗ log ⁡ 2 P ( 0 ) H(0)=-P(0)\*\\log\_2P(0) H(0)=−P(0)∗log2P(0)嘛。

但是你肯定还会坚持，然后开始论证：

lim ⁡ x → 0 + H ( x ) = − lim ⁡ x → 0 + P ( x ) ∗ log ⁡ 2 P ( x ) 令 t = 1 P ( x ) 即 t → + ∞ ， 将 t 代 入 式 中 得 = − l i m t → + ∞ log ⁡ 2 1 t t 使 用 洛 必 达 法 则 得 = − l i m t → + ∞ − 1 t 2 ∗ 1 1 t ln ⁡ 2 1 = lim ⁡ t → + ∞ 1 t ln ⁡ 2 = 0 \\begin\{matrix\} \\lim\_\{x\\rightarrow0\_+\}H(x)&=&-\\lim\_\{x\\rightarrow0\_+\}P(x)\*\\log\_2P(x)\\\\ \\\\令t=\\frac\{1\}\{P(x)\}\\\\ \\\\即t\\rightarrow+\\infin，&&将t代入式中得\\\\ \\\\&=&-lim\_\{t\\rightarrow+\\infin\}\\frac\{\\log\_2\\frac\{1\}\{t\}\}\{t\}\\\\ \\\\使用洛必达法则得\\\\ &=&-lim\_\{t\\rightarrow+\\infin\}\\frac\{-\\frac\{1\}\{t^2\}\*\\frac\{1\}\{\\frac\{1\}\{t\}\\ln2\}\}\{1\}\\\\ \\\\&=&\\lim\_\{t\\rightarrow+\\infin\}\\frac\{1\}\{t\\ln2\}=0 \\end\{matrix\} limx→0\+H(x)令t=P(x)1即t→\+∞，使用洛必达法则得====−limx→0\+P(x)∗log2P(x)将t代入式中得−limt→\+∞tlog2t1−limt→\+∞1−t21∗t1ln21limt→\+∞tln21=0

**好嘛**！**干得漂亮**！

![niupi][]

那这我不得不佩服你的数学功底。**但是说了这么多有什么用嘛**，计算机到了 log ⁡ ( 0 ) \\log(0) log(0)**直接抛异常了**，**哪管你连续不连续的**。

## 为什么要分类？ ##

高中化学告诉我们，**只要一个独立的系统放在这里**，**熵值只会变大**，**只是不同的系统有着时间快慢的差别罢了**。

也就是说，要是就把本篇箱子分类这个案例中的一堆箱子放在这里，**箱子只会越来越乱**。再举个现实的例子吧，对于码农，一段时间只往电脑里塞文件而不分类，**电脑里面的文件也只会越来越乱**。

**为什么要分类**？

一方面，普通地说，那就是**让自己更快地找到自己想要的东西**；

另一方面，学术一点的表达就是：**让熵值减少**，**从而该事件更稳定**。

如果是要再表述得更哲学一点，那就是像书中说的一样：

>  *  希望笔者在暮年之时，回首往事，能自信地说，我给这个世界带来的信息增益是正数，且已经尽力做到最大了。
> 
> ——摘自《scikit-learn机器学习常用算法原理及编程实战》 \[著\]黄永昌

是不是有点能理解了呢？

[Link 1]: https://blog.csdn.net/ordinary_brony/article/details/110433041
[6d5158592654818b256af6df676d7ffe.png]: /images/20221120/15f5596dea3e4e2dbe5399056d39dbcb.png
[1b4e8286cc04d0ce0f977d1b5c665a1c.png]: /images/20221120/d90417b6624348efb106023929b65f1f.png
[niupi]: /images/20221120/61eade2688b9432f996bcd16ce314374.png