雲栖号資訊：【 點選檢視更多行業資訊】
在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！
決策樹的定義
決策樹是我本人非常喜歡的機器學習模型，非常直覺容易了解，并且和資料結構的結合很緊密。我們學習的門檻也很低，相比于那些動辄一堆公式的模型來說，實在是簡單得多。
其實我們生活當中經常在用決策樹，隻是我們自己沒有發現。決策樹的本質就是一堆if-else的組合，舉個經典的例子，比如我們去小攤子上買西瓜。水果攤的小販都是怎麼做的？拿起西瓜翻滾一圈，看一眼，然後伸手一拍，就知道西瓜甜不甜。我們把這些動作相關的因素去除，把核心本質提取出來，基本上是這麼三條：
- 西瓜表面的顔色，顔色鮮豔的往往比較甜
- 西瓜拍打的聲音，聲音清脆的往往比較甜
- 西瓜是否有瓜藤，有藤的往往比較甜
這三條顯然不是平等的，因為拍打的聲音是最重要的，可能其次表面顔色，最後是瓜藤。是以我們挑選的時候，肯定也是先聽聲音，然後看瓜藤，最後看顔色。我們把其中的邏輯抽象出來然後整理一下，變成一棵樹結構，于是這就成了決策樹。
這個決策樹本質上做的還是分類的工作，将西瓜分成了甜的和不甜的。也就是說決策樹是一個樹形的分類器，這個也是決策樹的基本定義。另外從圖中我們還有一個啟示，在這個問題當中，決策樹的特征都是離散值，而不是連續值。也就是說決策樹可以接受像是類别、辨別這樣非數值型的特征，而邏輯回歸這些模型則不太行。
如果你對這些細節還了解不深刻也沒有關系，我們可以先放一放，至少我們明白了決策樹的大概結構以及工作原理。
對于每一條資料來說，它分類的過程其實就是在決策樹上周遊的過程。每到一個中間節點都會面臨一次判斷，根據判斷的結果選擇下一個子樹。而樹上的葉子節點代表一種分類，當資料到了葉子節點，這個葉子節點的值就代表它的分類結果。
決策樹的訓練
明白了決策樹的結構和工作原理之後，下面就是訓練的過程了。
在理清楚原理之前，我們先來看下資料。我們根據上面決策樹的結構，很容易發現，訓練資料應該是這樣的表格：
那麼最後我們想要實作什麼效果呢？當然是得到的準确率越高越好，而根據決策樹的原理，樹上的每一個葉子節點代表一個分類。那麼我們顯然希望最後到達葉子節點的資料盡可能純粹，舉個例子，如果一個葉子節點代表甜，那麼我們肯定希望根據樹結構被劃歸到這裡的資料盡可能都是甜的，不甜的比例盡可能低。
那麼我們怎麼實作這一點呢？這就需要我們在越頂層提取規則的時候，越選擇一些區分度大的特征作為切分的依據。所謂區分度大的特征，也就是能夠将資料很好分開的特征。這是明顯的貪心做法，使用這樣的方法，我們隻可以保證在盡可能高層取得盡可能好的分類結果，但是并不能保證這樣得到的模型是最優的。生成最優的決策樹本質上也是一個NP問題，我們目前的做法可以保證在盡量短的時間内獲得一個足夠優秀的解，但是沒辦法保證是最優解。
回到問題本身，我們想要用區分度大的特征來進行資料劃分。要做到這一點的前提就是首先定義區分度這個概念，将它量化，這樣我們才好進行選擇。否則總不能憑感覺去衡量區分度，好在這個區分度還是很好解決的，我們隻需要再一次引入資訊熵的概念就可以了。
資訊熵與資訊增益
資訊熵這個詞很令人費解，它英文原文是information entropy，其實一樣難以了解。因為entropy本身是實體學和熱力學當中的概念，用來衡量物體分散的不均勻程度。也就是說熵越大，說明物體分散得程度越大，可以簡單了解成越散亂。比如我們把房間裡一盒整理好的乒乓球打翻，那麼裡面的乒乓球顯然會散亂到房間的各個地方，這個散亂的過程可以了解成熵增大的過程。
資訊熵也是一樣的含義，用來衡量一份資訊的散亂程度。熵越大，說明資訊越雜亂無章，否則說明資訊越有調理。資訊熵出自大名鼎鼎的資訊學巨著《資訊論》，它的作者就是赫赫有名的香農。但是這個詞并不是香農原創，據說是計算機之父馮諾依曼取的，他去這個名字的含義也很簡單，因為大家都不明白這個詞究竟是什麼意思。
之前我們曾經在介紹交叉熵的時候詳細解釋過這個概念，我們來簡單回顧一下。對于一個事件X來說，假設它發生的機率是P(X)，那麼這個事件本身的資訊量就是：
比如說世界杯中國隊奪冠的機率是1/128，那麼我們需要用8個比特才能表示，說明它資訊量很大。假如巴西隊奪冠的機率是1/4，那麼隻要2個比特就足夠了，說明它的資訊量就很小。同樣一件事情，根據發生的機率不同，它的資訊量也是不同的。
那麼資訊熵的含義其實就是資訊量的期望，也就是用資訊量乘上它的機率：
同樣，假設我們有一份資料集合，其中一共有K類樣本，每一類樣本所占的比例是
，那麼我們把這個比例看成是機率的話，就可以寫出這整個集合的資訊熵：
了解了資訊熵的概念之後，再來看資訊增益就很簡單了。資訊增益說白了就是我們劃分前後資訊熵的變化量，假設我們選擇了某一個特征進行切分，将資料集D切分成了D1和D2。那麼
就叫做資訊增益，也就是切分之後資訊熵與之前的變化量。
我們根據熵的定義可以知道，如果資料變得純粹了，那麼資訊熵應該會減少。減少得越多，說明切分的效果越好。是以我們就找到了衡量切分效果的方法，就是資訊增益。我們根據資訊增益的定義，可以很簡單地理出整個決策樹建立的過程。就是我們每次在選擇切分特征的時候，都會周遊所有的特征，特征的每一個取值對應一棵子樹，我們通過計算資訊增益找到切分之後增益最大的特征。上層的結建構立好了之後， 通過遞歸的形式往下繼續建樹，直到切分之後的資料集變得純粹，或者是所有特征都使用結束了為止。
這個算法稱為ID3算法，它也是決策樹最基礎的建構算法。這裡有一個小細節， 根據ID3算法的定義，每一次切分選擇的是特征，而不是特征的取值。并且被選中作為切分特征的特征的每一個取值都會建立一棵子樹，也就是說每一個特征在決策樹當中都隻會最多出現一次。因為使用一次之後，這個特征的所有取值就都被使用完了。
舉個例子，比如拍打聲音是否清脆這個特征，我們在一開始就選擇了它。根據它的兩個取值，是和否都建立了一棵子樹。那麼如果我們在子樹當中再根據這個特征拆分顯然沒有意義，因為子樹中的所有資料的這個特征都是一樣的。另外，ID3算法用到的所有特征必須是離散值，因為連續值無法完全切分。如果西瓜的重量是一個特征，那麼理論上來說所有有理數都可能是西瓜的品質，我們顯然不可能窮盡所有的取值。
這一點非常重要，不僅關系到我們實作的決策樹是否正确，也直接關系到我們之後了解其他的建樹算法。
代碼實作
了解了算法原理和流程之後，就到了我們緊張刺激的編碼環節。老實講決策樹的算法實作并不難，比之前的FP-growth還要簡單，大家不要有壓力。
首先，我們來創造實驗資料：
這份資料模拟的是學生考試，一共考三門，一共要考到150分以上才算是通過。由于ID3算法隻能接受離散值的特征，是以我們要先将連續值轉成離散值，我們根據每一門的考試分數，生成三個檔次。大于70分的是2檔，40到70分的是1檔，小于40分的是0檔。
為了友善編碼，我們把預測值Y放在特征的最後，并且傳回這三個特征的名稱，友善以後用來建樹。
我們運作一下資料檢視一下結果：
下面，我們實作計算集合資訊熵的函數。這個函數也很簡單，我們隻需要計算出每個類别的占比，然後套用一下資訊熵的公式即可。
有了資訊熵的計算函數之後，我們接下來實作拆分函數，也就是根據特征的取值将資料集進行拆分的函數。
本質上就是根據特征取值歸類的過程，我們可以随便調用測試一下：
和我們預期一樣，根據特征的取值将資料分成了若幹份。接下來我們就要實作核心的特征的選擇函數了，也就是要選擇資訊增益最大的特征對資料進行切分。
到這裡，我們所有工具方法都已經開發完了，下面就到了我們緊張刺激的建樹部分了。建樹其實并沒有什麼大不了的，無非是通過遞歸來重複調用上面的方法來創造每一個分支節點而已。如果你熟悉樹形資料結構，會發現它和其他樹形資料結構的建構過程并沒有什麼兩樣。
我們來看下代碼，整個過程也隻有十幾行而已。
我們運作一下這段代碼，會得到一份dict，這個dict當中的層次結構其實就是決策樹的結構：
我們這樣看可能不太清楚，但是我們把這個dict展開就得到了下圖的這棵樹結構：
我們觀察一下上圖當中紅圈的部分，這個節點隻有兩個分叉，而其他的節點都有三個分叉。這并不是代碼有bug，而是說明資料當中缺失了這種情況，是以少了一個分叉。這其實非常正常，當我們訓練資料的樣本量不夠的時候，很有可能無法覆寫所有的情況，就會出現這種沒有分叉的情況。
到這裡雖然決策樹是實作完了，但是還沒有結束，還有一個關鍵的部分我們沒有做，就是預測。我們訓練完了，總得把模型用起來，顯然需要一個預測的函數。這個預測的函數也簡單，它介紹一條資料以及我們訓練完的樹結構，傳回分類的結果。其實也是一個遞歸調用的過程：
我們來創造一些簡單的資料測試一下：
基本上和我們的預期一緻，說明我們決策樹就實作完了。
總結
我們的決策樹雖然建構完了，但是仍然有很多不完美的地方。比如說，目前我們的模型隻能接受離散值的特征，如果是連續值則無法進行拆分。而且我們每個特征隻能用一次，有時候我們希望能夠多次使用同一個特征。在這種情況下ID3就無法實作了。是以我們還需要引入其他的優化。
在後序的文章當中我們将會讨論這些相關的優化，以及決策樹這個模型本身的一些特性。如果對此感興趣，一定不要錯過。
【雲栖号線上課堂】每天都有産品技術專家分享！
課程位址：
https://yqh.aliyun.com/live立即加入社群，與專家面對面，及時了解課程最新動态！
【雲栖号線上課堂 社群】
https://c.tb.cn/F3.Z8gvnK
原文釋出時間：2020-05-22
本文作者：承志
本文來自：“
掘金”，了解相關資訊可以關注“掘金”