今天開始進(jìn)入決策樹的算法部分，首先介紹一下這部分涉及到的知識點。

一、大綱

1、信息熵

決策樹在生成過程中，對于評判是否要對樹進(jìn)行劃分的關(guān)鍵指標(biāo)。即樹生成時的決策根本。

2、決策樹
之前提過KD樹的劃分標(biāo)準(zhǔn)。02 KNN算法 - KD Tree KD樹是基于一個劃分的標(biāo)準(zhǔn)(中位數(shù))，最后構(gòu)建起了整個KD樹。決策樹同樣也是一個樹形結(jié)構(gòu)，同樣需要某些決策指標(biāo)來構(gòu)建起決策樹。最后幫助我們實現(xiàn)回歸或分類的目標(biāo)。

3、決策樹優(yōu)化
和KD樹一樣，決策樹模型生成以后同樣會存在欠擬合和過擬合的問題。如何解決這些問題就是決策樹優(yōu)化需要考慮的。

4、剪枝
防止決策樹過擬合的過程，實際生產(chǎn)過程中剪枝的操作用的很少，但面試可能會提問，了解即可。

5、決策樹可視化
導(dǎo)入一些新的模塊，最后將決策樹展現(xiàn)在用戶面前。

二、決策樹的直觀理解

根據(jù)一個人是否有房產(chǎn)、婚姻情況、年收入情況判斷一個人是否有能力償還債務(wù)。
根據(jù)樣本構(gòu)建出一個模型：

相比Logistic模型、回歸模型中參數(shù)的理解，決策樹是一個解釋性更強的模型。

三、比特化

數(shù)據(jù)：BACADCBD...
這里ABCD出現(xiàn)的概率都是1/4，等概率。
即P(X=A) =P(X=B) =P(X=C) =P(X=D) =1/4

令A(yù)-00 B-01 C-10 D-11（等概率，用兩個比特位表示4個變量即可）
BACADC = 01001011100111
E = 1×1/4 *4 = 1
(每個變量占用一個比特位，出現(xiàn)概率是1/4，一共4個變量，平均每個變量占1個比特位)

---

如果X變量出現(xiàn)概率不同：
即P(X=A)=1/2; P(X=B) = 1/4; P(X=C) =P(X=D) =1/8;

用更少的比特位描述出現(xiàn)概率更大的事件，能夠讓總的比特位數(shù)量最少：
令A(yù)-0 B-10 C-110 D-111

E=1×1/2 + 2×1/4 + 3×1/8 + 3×1/8 = 1.75
平均每個變量占1.75個比特位。其他任何一種編碼方式最終得到的期望都會大于1.75，耗費了多余的計算機資源。

還可以用下面的公式表示__平均每個變量占用的比特位__數(shù)量：

$color{red}{每個變量出現(xiàn)的概率：}$ p
$color{red}{每個變量占用的比特位：}$ -log₂p

所以，m個變量在不同的出現(xiàn)概率p1~pm時，平均每個變量占用的比特位公式如下：

四、信息熵

__信息熵__是描述一個信息量的指標(biāo)。如果一個事件發(fā)生的概率越大，那么認(rèn)為該事件蘊含的信息越少。

當(dāng)一個事件百分百確定的時候，我們得不到其他推論。那么認(rèn)為信息量為0。

只有當(dāng)事件的出現(xiàn)存在概率性，說明有額外的信息影響事件發(fā)生，那么針對這些信息我們才需要推理判斷 。

__信息熵__是系統(tǒng)有序程度的度量，一個系統(tǒng)越是有序，信息熵就越低。信息熵就是用來描述系統(tǒng)信息量的不確定度。

信息熵 = 比特化隨機變量X占用比特位的數(shù)學(xué)期望

五、條件熵

回顧H(X)的概念，并看下面的例子：

令L(S) = -P(S) × log2(S)
H(X) = L(X=數(shù)學(xué)) + L(X=IT) + L(X=英語)

= -0.5 × log2(0.5) - 0.25 × log2(0.25) - 0.25×log2(0.25) = 0.5 + 0.5 + 0.5 = 1.5

H(Y) = L(Y = M) + L(Y = F)

= -0.5 × log2(0.5) - 0.5 × log2(0.5) = 0.5 + 0.5 = 1

H(X, Y) = L(X=數(shù)學(xué), Y=M) + L(X=IT, Y=M) + L(X=英語, Y=F) +
L(X=數(shù)學(xué), Y=F) = -0.25 × log2(0.25) × 4 = 2

看明白上面的例子后，接下來引入__條件熵__的概念：
給定條件X的情況下，隨機變量Y的信息熵就是__條件熵__。
給定條件X的情況下，所有不同x值情況下，Y的信息熵的平均值，叫做__條件熵__。

當(dāng)專業(yè)X為數(shù)學(xué)時，Y的信息熵的值為：H(Y|X=數(shù)學(xué))
怎么計算H(Y|X=數(shù)學(xué))？先把數(shù)學(xué)相關(guān)的項提取出來：

現(xiàn)在姓別出現(xiàn)的概率都是2/4，根據(jù)公式：

$color{red}{每個變量出現(xiàn)的概率：}$ p

$color{red}{每個變量占用的比特位：}$ -log₂p

-log₂(0.5)=1：單個性別的信息熵。
H(Y|X=數(shù)學(xué)) = -0.5 × log₂(0.5) × 2 = 1

---

H(Y|X=數(shù)學(xué)) 是 H(Y|X) 的一部分，H(Y|X)還包括H(Y|X=IT)、H(Y|X=英語) 根據(jù)上述的方式能夠依次計算出H(Y|X=IT)、H(Y|X=英語) 的值。

回顧一下定義：
給定條件X的情況下，所有不同x值情況下，Y的信息熵的平均值，叫做__條件熵__。

以下log表示log2

條件熵 H(X/Y)
= H(X/Y=M)×P(Y=M) + H(X/Y=F)×P(Y=F) 即加權(quán)平均熵

= [L(X=數(shù)學(xué)/Y=M)+L(X=數(shù)學(xué)/Y=M)]×P(Y=M) + H(X/Y=F)×P(Y=F)= [-0.5 × log(0.5) × 2] × 0.5 + H(X/Y=F)×P(Y=F)= 0.5 + H(X/Y=F)×P(Y=F) = 0.5 + 0.5 = 1= __H(X, Y) - H(Y)__

條件熵 H(Y/X)
= H(Y/X=數(shù)學(xué))×P(X=數(shù)學(xué))+H(Y/X=IT)×P(X=IT)+H(Y/X=英語)×P(X=英語)

= [-0.5 × log(0.5) × 2] × 0.5+H(Y/X=IT)×P(X=IT)+H(Y/X=英語)×P(X=英語)= 0.5 + 0 + 0 = 0.5= __H(X, Y) - H(X)__

條件熵__的另一個公式： __H(Y/X) = H(X, Y) - H(X)
事件(X,Y)發(fā)生所包含的熵，減去事件X單獨發(fā)生的熵，即為事件X發(fā)生前提下，Y發(fā)生“新”帶來的熵。

結(jié)合概率論中的Venn圖思考上面公式的意義：

最后給出一個推導(dǎo)公式：

總結(jié)

以上是生活随笔為你收集整理的01 决策树 - 数学理论概述 - 熵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。