Python編程入門：接地氣的決策樹算法基礎講解

決策樹算是比較常見的數據挖掘算法了，最近也想寫點算法的東西，想著這期的 Python編程入門 就先寫個決策樹吧。

一. 什么是決策樹

決策樹是什么，我們來“決策樹”這個詞進行分詞，那么就會是 決策/樹 。大家不妨思考一下，重點是決策還是樹呢？其實啊，決策樹的關鍵點在 樹 上。

我們平時寫代碼的那一串一串的If Else其實就是決策樹的思想了。看下面的圖是不是覺得很熟悉呢？

當然決策樹算法比這復雜那么一丟丟，所以在說決策樹之前，我們需要先了解一些基本知識，先來說說信息論中的信息熵。

二.決策樹介紹

決策樹之所以叫決策樹，就是因為它的結構是樹形狀的，如果你之前沒了解過樹這種數據結構，那么你至少要知道以下幾個名詞是什么意思。

根節點：最頂部的那個節點

葉子節點：每條路徑最末尾的那個節點，也就是最外層的節點

非葉子節點：一些條件的節點，下面會有更多分支，也叫做分支節點

分支：也就是分叉

學過樹這種數據結構的同學可能一看就明白了，沒有學過也沒關系，我們可以用上面的圖來說明各部分分別是什么。

三.信息熵

要說決策樹，那信息熵是繞不過去的一座山~

3.1 信息熵是什么？

假設你要知道一件未知的事情，比如明天會不會下雨。這時候你就需要去獲取一些信息，比如空氣干濕度，今天是萬里無云還是多云等等（假設沒有天氣預報）。這些信息中，有的可以讓你能更加準確判斷明天會不會下雨（比如今天有沒有云），而有信息些則不會（比如今天晚餐吃什么）。如何度量這些信息對你決策的幫助呢？這里要使用到的就是信息熵了，信息熵正是對信息量有效性的一種度量方法。

如果你還記得高中化學的知識的話，那對 熵 這個字應該不會陌生。 熵在化學中是表示分子的混亂程度，分子越混亂，它的熵就越大，而若分子越有序，熵值就越小 。

信息熵也是一樣的，它能對信息的不確定性進行恒量， 如果某個信息讓我們的判斷更加有序，清晰，則它信息熵越小，反之越大。

還是接上面的例子，現在你知道了空氣的濕度，那么你就能更準確得判斷明天是否會下雨。你得到的信息讓你的結論更加清晰，準確，所以它的熵值就比較小，因為它讓信息更加準確。而對今天晚餐吃什么這個信息，顯然它對你判斷明天會不會下雨是沒什么幫助的，所以它的信息熵是比較大的，因為這個信息和明天有沒有下雨沒有關系，它并沒有讓我們的判斷更加清晰，甚至讓我們的判斷趨于混亂。

計算信息熵的公式如下：

其中U指的是某一信息，pi則是指信息中各種可能出現的結果的概率。

比如U為空氣濕度，空氣濕度一共有3中（ 干燥，微濕，濕潤 ），則可以p1表示空氣干燥的概率，p2表示空氣微濕的概率，p3表示空氣濕潤的概率，這些概率都是可以通過樣本統計出來的。

然后空氣濕度的信息熵就可以計算出來了：

H(空氣濕度) = p1 * log(p1) + p2 * log(p2) + p3 * log(p3)

我們可以舉吳軍老師的「數學之美」中的一個例子來解釋這條式子。

假設2018年，有32支球隊參加世界杯，每只球隊最終獲得冠軍的概率一樣。在世界杯之后，你去問別人世界杯冠軍是哪個國家的？那個人不直接跟你說，讓你猜！并且每猜一次，你需要支付1塊錢，這時你怎么才能花最少的錢呢？

學過算法的我們自然知道可以用二分法，把32支球隊分成兩半，猜對猜錯之后自然知道球隊在哪一半，再二分再猜，這樣最終你需要猜5次，也就是需要支付5塊錢，沒錯吧。這樣一來，這條信息的價值就是5塊錢，而在計算機中，則用***bit***表示。假如一共有64支球隊，那我們就需要多猜一次，這條信息的價格就變成了6。從這里我們就可以看出信息的度量跟log有關，log32=5，log64=6嘛。

現在我們來運用上面的公司，我們讓p1,p2,p3...p32表示每支球隊獲勝的概率，運用公式，則

H(獲勝) = p1*logp1 + p2*logp2 + ... + p32*log32

這樣最終算出的結果正是等于5，就是說哪個國家獲勝這條信息的信息熵是5。

3.2 信息熵與決策樹

信息熵最早是用在通信領域的，而決策樹的誕生是緣于澳大利亞計算機科學家昆蘭，在一次研究生課程大作業中，引入了信息增益準則來改進程序。而后在1979年發表這一相關論文后，決策樹算法正式問世，并掀起一股決策樹算法的研究熱潮。

那么它被用在哪里呢？

我們知道決策樹由許多屬性和分支組成，那么如何決定哪個屬性在前，哪個在后呢。這里就需要用到信息熵了。

前面我們提到過信息熵是對信息不確定性的度量，既然信息可以度量，那每次我們只要找到信息熵的值最小，也就是讓決策更加清晰的那個屬性來作為根進行分支，那不就行了嗎？什么，你說分支后怎么辦，對樹處理的基本方法就是遞歸，分支后，每一分支節點都可以當作一棵新的樹，然后再來重復上面的步驟啦。