前言
最近好忙好忙的說，連更新都慢了一周呢，收到豆瓣的催稿好就趕緊開始碼字了，哭。
決策樹就像是真的一棵樹，它從一個主幹逐漸分支，構成一個完整的決策樹。
決策樹（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時，就沒有必要再往下構造決策樹了，此時葉子節點都是純的--這是理想情況。最壞的情況下，決策樹的高度為屬性（決策變量）的個數，葉子節點不純（這意味着我們要以一定的機率來作出決策）。