1、17機器學習-決策樹分類算法原理1. 概述決策樹(decisiontree)是一種被廣泛使用的分類算法。相比貝葉斯算法，決策樹的優(yōu)勢在于構造過程不需要任何領域知識或參數(shù)設置在實際應用中，對于探測式的知識發(fā)現(xiàn)，決策樹更加適用2. 算法思想通俗來說，決策樹分類的思想類似于找對象。現(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話:女兒多大年紀了？母親26。女兒長的帥不帥？母親挺帥的。女兒收入高不？母親不算很高，中等情況。女兒是公務員不？母親是，在稅務局上班呢。女兒那好，我去見見。這個女孩的決策過程就是典型的分類樹決策。實質(zhì)：通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見

2、上圖完整表達了這個女孩決定是否見去約會的策略，其中:假設這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務員，那么這個可以用下圖表示女孩的決策邏輯:30帥或中等綠色節(jié)點表示判斷條件橙色節(jié)點表示決策結果箭頭表示在一個判斷條件在不同情況下的決策路徑圖中紅色箭頭表示了上面例子中女孩的決策過程。這幅圖基本可以算是一顆決策樹，說它“基本可以算”是因為圖中的判定條件沒有量化，如收入高中低等等，還不能算是嚴格意義上的決策樹，如果將所有條件量化，則就變成真正的決策樹了。決策樹分類算法的關鍵就是根據(jù)“先驗數(shù)據(jù)”構造一棵最佳的決策樹，用以預測未知數(shù)據(jù)的類別。決策樹：是一個樹結構（可

3、以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結果。3. 決策樹構造3.1決策樹構造樣例假如有以下判斷蘋果好壞的數(shù)據(jù)樣本：樣本中有2個屬性，A0表示是否紅蘋果。A1表示是否大蘋果。假如要根據(jù)這個數(shù)據(jù)樣本構建一棵自動判斷蘋果好壞的決策樹。由于本例中的數(shù)據(jù)只有2個屬性，因此，我們可以窮舉所有可能構造出來的決策樹，就2棵，如下圖所示：當然這是直覺的認知。而直覺顯然不適合轉化

4、成程序的實現(xiàn)，所以需要有一種定量的考察來評價這兩棵樹的性能好壞。決策樹的評價所用的定量考察方法為計算每種劃分情況的信息熵增益：如果經(jīng)過某個選定的屬性進行數(shù)據(jù)劃分后的信息熵下降最多，則這個劃分屬性是最優(yōu)選擇2屬性劃分選擇(即構造決策樹)的依據(jù)熵：信息論的奠基人香農(nóng)定義的用來信息量的單位。簡單來說，熵就是“無序，混亂”的程度。通過計算來理解：2.1原始樣本數(shù)據(jù)的熵樣例總數(shù)：4好蘋果：2壞蘋果：2熵：-(1/2*log(1/2)+1/2*log(1/2)=1信息熵為1表示當前處于最混亂，最無序的狀態(tài)。2.2兩顆決策樹的劃分結果熵增益計算樹1先選A0作劃分，各子節(jié)點信息熵計算如下:0,1葉子節(jié)點有2個

5、正例，0個負例。信息熵為：el=-(2/2*log(2/2)+0/2*log(0/2)=0。2,3葉子節(jié)點有0個正例，2個負例。信息熵為：e2=-(0/2*log(0/2)+2/2*log(2/2)=0。因此選擇A0劃分后的信息熵為每個子節(jié)點的信息熵所占比重的加權和：E=e1*2/4+e2*2/4=0。選擇A0做劃分的信息熵增益G(S,A0)=S-E=1-0=1.事實上，決策樹葉子節(jié)點表示已經(jīng)都屬于相同類別，因此信息熵一定為0。樹2先選A1作劃分，各子節(jié)點信息熵計算如下:0,2子節(jié)點有1個正例，1個負例。信息熵為：el=-(1/2*log(1/2)+1/2*log(1/2)=1。1,3子節(jié)點有1個正例，1個負例。信息熵為：e2=-(1/2*log(1/2)+1/2*log(1/2)=1。因此選擇A1劃分后的信息熵為每個子節(jié)點的信息熵所占比重的加權和：E=e1*2/4+e2*2/4=1。也就是說分了跟沒分一樣！選擇A1做劃分的信息熵增益G(S,A1)=S-E=1-1=0.因此，每次劃分之前，我們只需要計算出信息熵增益最大的那種劃分即可。4. 算法要點4.1指導思想經(jīng)過決策屬性的劃分后，數(shù)據(jù)的無序度越來越低，也就