你是否玩過20個問題的游戲？游戲的規(guī)則很簡單：參與游戲的一方在腦海里想某個事物，其他參與者向他提問題，只允許提20個問題为迈，問題的答案也只能用對或錯來回答。問問題的人通過推斷分解缺菌，逐步縮小待猜測事物的范圍葫辐。
如果你玩過這個游戲，那么恭喜你伴郁，你已經掌握了決策樹算法的應用耿战。是不是非常簡單？
什么是決策樹
一圖表示決策樹
所有的機器學習算法中焊傅，決策樹應該是最友好的了剂陡。它呢，在整個運行機制上可以很容易地被翻譯成人們能看懂的語言狐胎，也因此被歸為“白盒模型”鸭栖。
為了更直觀地理解決策樹，我們現(xiàn)在來構建一個簡單的郵件分類系統(tǒng)顽爹，如圖：
首先檢測發(fā)送郵件域名地址
如果地址為com纤泵，則放置于“無聊時需要閱讀的郵件”分類
如果不是這個地址，那么再次檢測
檢查郵件是否有單詞“曲棍球”
包含單詞“曲棍球”镜粤，則放置于“需要及時處理的朋友郵件”分類
不包含單詞“曲棍球”，則放置于“無需閱讀的垃圾郵件”分類
現(xiàn)在玻褪，我們來總結一下決策樹的構成：
根節(jié)點肉渴。第一個需要判斷的條件，往往也是最具有特征的那個條件带射，我們稱為根節(jié)點同规。
中間節(jié)點。那個矩形總是要往下分窟社，并不是最終的結果券勺，它叫做中間節(jié)點（或內部節(jié)點）。
邊灿里。那些帶有文字的線段（一般使用有箭頭的有向線段）关炼，線的一端連的是中間節(jié)點、另一端連的是另一個中間節(jié)點或葉節(jié)點匣吊，然后線段上還有文字儒拂，它叫做邊寸潦。
葉節(jié)點。那個圓角矩形社痛，它就已經是最后的結果了见转，不再往下了，這一類東西呢蒜哀，在決策樹里叫做葉節(jié)點斩箫。
決策樹的一般流程
（1）收集數(shù)據：可以使用任何方法。
（2）準備數(shù)據：樹構造算法只適用于標稱型數(shù)據撵儿，因此數(shù)值型數(shù)據必須離散化校焦。
（3）分析數(shù)據：可以使用任何方法，構造樹完成后统倒，我們應該檢查圖形是否符合預期寨典。
（4）訓練算法：構造樹的數(shù)據結構。
（5）測試算法：使用經驗樹計算錯誤率房匆。
（6）使用算法：此步驟可以適用于任何機器學習算法耸成，而使用決策樹可以更好地理解數(shù)據的內在含義。
上面這種樸素的算法很容易想到浴鸿，但是太容易得到的它往往不夠美好井氢。如果自變量很多的時候，我們該選哪個作為根節(jié)點呢岳链？選定了根節(jié)點后花竞，樹再往下生長接下來的內部節(jié)點該怎么選呢？針對這些問題掸哑，衍生了很多決策樹算法约急，他們處理的根本問題是上面流程的第四步——訓練算法，實際上也就是劃分數(shù)據集方法苗分。我們來看看代表之一 ——ID3算法厌蔽。
信息增益
在劃分數(shù)據集之前之后信息發(fā)生的變化稱為信息增益，知道如何計算信息增益摔癣，我們就可以計算每個特征值劃分數(shù)據集獲得的信息增益奴饮，獲得信息增益最高的特征就是最好的選擇。
這里又引入了另一個概念——熵择浊。這里先不展開說了戴卜，我們記住他的概念：一個事情它的隨機性越大就越難預測。
具體來說這個概率p越小琢岩，最后熵就越大（也就是信息量越大）投剥，如果極端情況一件事情概率為1，它的熵就變成0了粘捎。
比如薇缅，你如果能預測一個彩票的中獎號碼就發(fā)達了危彩；但是，如果你能預測明天太陽從東邊升起來則毫無價值泳桦。這樣衡量一個信息價值的事汤徽，就可以由熵來表示。
聰明的你或許已經發(fā)現(xiàn)了灸撰，決策樹算法其實就是為了找到能夠迅速使熵變小谒府，直至熵為0的那條路徑，這就是信息增益的那條路浮毯。我們將對每個特征劃分數(shù)據集的結果計算一次信息熵完疫，然后判斷按照哪個特征劃分數(shù)據集是最好的劃分方式。
舉個容易理解的例子：
解決問題：預設4個自變量：天氣债蓝、溫度壳鹤、濕度、風速饰迹，預測學校會不會舉辦運動會芳誓？
步驟一：假設我們記錄了某個學校14屆校運會按時舉行或取消的記錄，舉行或者取消的概率分別為：9/14啊鸭、5/14锹淌，那么它的信息熵，這里也叫先驗熵赠制，為：
步驟二：我們同時記錄了當天的天氣情況赂摆，發(fā)現(xiàn)天氣好壞和校運會舉行還是取消有關。14天中钟些，5次晴天（2次舉行烟号、3次取消）、5次雨天（3次舉行厘唾、2次取消）褥符、4次陰天（4次舉行）。相對應的晴天抚垃、陰天、雨天的后驗熵趟大。
步驟三：我們計算知道天氣情況后的條件熵鹤树。
步驟四：我們計算在有沒有天氣情況這個條件前后的信息增益就是。
步驟五：我們依次計算在有沒有溫度逊朽、濕度罕伯、風速條件前后的信息增益。
步驟六：根據設置的閾值叽讳，若信息增益的值大于設置的閾值追他，選取為我們的特征值坟募，也就是我們上圖中的矩形節(jié)點。
步驟七：生成決策樹邑狸。選取信息增益最大的自變量作為根節(jié)點懈糯。其他的特征值依次選取為內部節(jié)點。
比如上面的例子是這樣的過程：
經過如上步驟单雾，我們得到決策樹赚哗。可以看到硅堆，最終們只選取了3個特征值作為內部節(jié)點屿储。
決策樹的應用
決策樹也是一種分類方法。它的分類是二元的渐逃，一個值經過相應節(jié)點的測驗够掠，要么進入真分支，要么進入假分支茄菊。所以一組值經過決策樹以后疯潭，就會形成從樹跟到結果節(jié)點的一條唯一路徑。所以它除了可以對輸入進行分類之外买羞，還能給出如此分類的解釋袁勺。因此決策樹常常被應用于專家系統(tǒng)，用于解釋回答人類專家才能回答的問題畜普。例如需要考慮多個變量時期丰，我們可以利用決策樹進行預測。
