679
【BABY夜談大數據】決策樹
前言
最近好忙好忙的說，連更新都慢了一周呢，收到豆瓣的催稿好就趕緊開始碼字了，哭。
最近阿法狗好火，所以就特地講下決策樹。如果你喜歡本書或者想要支持我，可以直接在豆瓣購買哦！https://read.douban.com/column/3346397/
決策樹就像是真的一棵樹，它從一個主幹逐漸分支，構成一個完整的決策樹。
決策樹（Decision Tree）是一種簡單但是廣泛使用的分類器。通過訓練數據構建決策樹，可以高效的對未知的數據進行分類。決策數有兩大優點：
決策樹模型可以讀性好，具有描述性，有助於人工分析。
效率高，決策樹隻需要一次構建，反複使用，每一次預測的最大計算次數不超過決策樹的深度。
機器學習中，決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關係。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經曆的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。數據挖掘中決策樹是一種經常要用到的技術，可以用於分析數據，同樣也可以用來作預測。
比如我現在我同事在我旁邊，我問他“如果你找個女朋友喜歡什麼樣的？”
他回答“長得好看，身高不要太矮，170左右、開朗、善良、孝順、脾氣好”。
同事的回答可以整理成上述的決策樹圖，簡單來說決策樹就是根據多個條件將某個事物歸於某個類別。
隻要遇到個女生，想要直到是否是同事喜歡的隻需要代入已經構建好的決策樹模型中便可以輕鬆得知到底是喜歡還是不喜歡。
決策樹可以按照如下步驟構建：
設立開始節點，所有的記錄從這裏出發。
決定哪些條件合適作為節點。
將節點繼續分為兩個子節點。
對子節點重複上麵三個步驟。
決策樹的變量可以有兩種：
數字型：變量類型是整數或浮點數。用“>=”，“>”,“<”或“<=”作為分割條件（排序後，利用已有的分割情況，可以優化分割算法的時間複雜度）。
名稱型：類似編程語言中的枚舉類型，變量隻能重有限的選項中選取，比如前麵例子中的“婚姻情況”，隻能是“單身”，“已婚”或“離婚”。使用“=”來分割。
雖然在選擇節點的時候，很多人喜歡用數學的角度去分析哪些條件更適合，在對待一些涉及到人、情感等問題上，往往是人的主觀意識更為重要。所以這裏個人建議在涉及到人的主觀意識類的問題不妨從純粹的主觀角度出發去思考。
在大數據領域有時候使用決策樹並不能有很好的效果，因為決策樹的模型是在得到數據之前就建立好的，如果數據繁多的話會浪費很多數據，決策樹也可以看作是一種貪心算法，如果某一個節點有失誤那麼之後的決策就會出錯。
注：貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。
不妨在初期建立的決策樹的決策條件放寬鬆點，經過長期大量的數據訓練、完善後再將決策樹的模型作為分析的核心。
當然也有人提倡說用隨機森林，隨機森林是一個包含多個決策樹的分類器， 並且其輸出的類別是由個別樹輸出的類別的眾數（出現最多的結果）而定。
在利用決策樹分類的時候，如果樣本數據缺失一些變量，但決策樹的決策過程中並未用到這些變量，那麼就可以將這些樣本作為完整的樣本。當決策用到了缺失的變量，不妨試試隨機森林或者在當前節點做多數投票來預測這個缺失的變量是什麼。
或者可以參照其它完整的樣本的結果來進行預測。比如我們最開始的舉的例子，如果不知道B喜歡男的女的，但是知道其它條件，那麼可以用其它條件與其它完整的樣本及其結果進行比較，預測下B喜歡男的女的。
可能講到這裏會有人問說什麼樣的特征適合作為變量呢？
一般是通過卡方檢驗、信息增益、相關係數等等算法來對不同的樣本進行觀測，看看哪些特征更適合作為變量。
個人建議是這些特征一般都有決定性作用並且不會出現歧義的情況就不妨拿來做變量試試。
講到決策樹就會講到熵，玻爾茲曼認為，任何粒子的常態都是隨機運動，也就是"無序運動"，如果讓粒子呈現"有序化"，必須耗費能量。所以，能量可以被看作"有序化"的一種度量。熱力學第二定律實際上是說，當一種形式的"有序化"轉化為另一種形式的"有序化"，必然伴隨產生某種"無序化"。一旦能量以"無序化"的形式存在，就無法再利用了，除非從外界輸入新的能量，讓無序狀態重新變成有序狀態。
"熵"就是"無序化"的度量。考慮到"無序化"代表著混亂（實質是隨機運動）。
熵是無序性（或不確定性）的度量指標。假如事件A的全概率劃分是（A1,A2,...,An），每部分發生的概率是(p1,p2,...,pn)，那信息熵定義為：
熵代表一個係統的雜亂程度，熵越大，係統越雜亂。對一個數據集中數據的分類就是使得該數據集熵減小的過程。
決策樹算法就是一個劃分數據集的過程。劃分數據集的原則就是：將無序的數據變得更加有序。
在決策樹中最出名的莫過於ID3，ID3算法（Iterative Dichotomiser 3 迭代二叉樹3代）是一個由Ross Quinlan發明的用於決策樹的算法。
這個算法是建立在奧卡姆剃刀的基礎上：越是小型的決策樹越優於大的決策樹。
通過ID3可以選擇到最適合的節點，我們接下來來做個簡單的推導。（這裏就使用我在網上找到的一個例子，感覺這個例子不錯，我才不是懶得寫表格呢(～ o ～)~zZ ,例子來源zhangchaoyang）
我們現在從別的地方扒來了一個表格，表格中統計了14天的氣象數據(指標包括outlook，temperature，humidity，windy)，並已知這些天氣是否打球(play)。如果給出新一天的氣象指標數據:sunny,cool,high,TRUE，請親愛的們判斷一下會不會去打球。
構造樹的基本想法是隨著樹深度的增加，節點的熵迅速地降低。熵降低的速度越快越好，這樣我們有望得到一棵高度最矮的決策樹。
在沒有給定任何天氣信息時，根據曆史數據，我們隻知道新的一天打球的概率是9/14，不打的概率是5/14。此時的熵為：
屬性有4個：outlook，temperature，humidity，windy。我們首先要決定哪個屬性作樹的根節點。
對每項指標分別統計：在不同的取值下打球和不打球的次數。
下麵我們計算當已知變量outlook的值時，信息熵為多少。
outlook=sunny時，2/5的概率打球，3/5的概率不打球。entropy=0.971
outlook=overcast時，entropy=0
outlook=rainy時，entropy=0.971
而根據曆史統計數據，outlook取值為sunny、overcast、rainy的概率分別是5/14、4/14、5/14，所以當已知變量outlook的值時，信息熵為：5/14 × 0.971 + 4/14 × 0 + 5/14 × 0.971 = 0.693
這樣的話係統熵就從0.940下降到了0.693，信息增溢gain(outlook)為0.940-0.693=0.247
同樣可以計算出gain(temperature)=0.029，gain(humidity)=0.152，gain(windy)=0.048。
gain(outlook)最大（即outlook在第一步使係統的信息熵下降得最快），所以決策樹的根節點就取outlook。
接下來要確定N1取temperature、humidity還是windy?在已知outlook=sunny的情況，根據曆史數據，我們作出類似table 2的一張表，分別計算gain(temperature)、gain(humidity)和gain(windy)，選最大者為N1。
依此類推，構造決策樹。當係統的信息熵降為0時，就沒有必要再往下構造決策樹了，此時葉子節點都是純的--這是理想情況。最壞的情況下，決策樹的高度為屬性（決策變量）的個數，葉子節點不純（這意味著我們要以一定的概率來作出決策）。
最後更新：2017-07-13 18:02:32