|
作者：藍鯨 算法決策樹是一種通過對歷史數(shù)據(jù)進行測算實現(xiàn)對新數(shù)據(jù)進行分類和預測的算法。簡單來說決策樹算法就是通過對已有明確結果的歷史數(shù)據(jù)進行分析，尋找數(shù)據(jù)中的特征。并以此為依據(jù)對新產生的數(shù)據(jù)結果進行預測。 決策樹由3個主要部分組成，分別為決策節(jié)點，分支，和葉子節(jié)點。其中決策樹最頂部的決策節(jié)點是根決策節(jié)點。每一個分支都有一個新的決策節(jié)點。決策節(jié)點下面是葉子節(jié)點。每個決策節(jié)點表示一個待分類的數(shù)據(jù)類別或屬性，每個葉子節(jié)點表示一種結果。整個決策的過程從根決策節(jié)點開始，從上到下。根據(jù)數(shù)據(jù)的分類在每個決策節(jié)點給出不同的結果。 
ID3算法構造決策樹的方法有很多種，ID3是其中的一種算法。ID3算法最早是由羅斯昆(J. Ross Quinlan)1975年在悉尼大學提出的一種分類預測算法，核心是“信息熵”。ID3算法認為“互信息”高的屬性是好屬性，通過計算歷史數(shù)據(jù)中每個類別或屬性的“信息熵”獲得“互信息”，并選擇“互信息”最高的類別或屬性作為決策樹中的決策節(jié)點，將類別或屬性的值做為分支繼續(xù)進行分裂。不斷重復這個過程，直到生成一棵完整的決策樹。 信息熵的含義及分類 信息熵是信息論中的一個重要的指標，是由香農在1948年提出的。香農借用了熱力學中熵的概念來描述信息的不確定性。因此信息學中的熵和熱力學的熵是有聯(lián)系的。根據(jù)Charles H. Bennett對Maxwell’s Demon的重新解釋，對信息的銷毀是一個不可逆過程，所以銷毀信息是符合熱力學第二定律的。而產生信息，則是為系統(tǒng)引入負(熱力學)熵的過程。 所以信息熵的符號與熱力學熵應該是相反的 。 簡單的說信息熵是衡量信息的指標，更確切的說是衡量信息的不確定性或混亂程度的指標。信息的不確定性越大，熵越大。決定信息的不確定性或者說復雜程度主要因素是概率。決策樹中使用的與熵有關的概念有三個：信息熵，條件熵和互信息。下面分別來介紹這三個概念的含義和計算方法。 信息熵是用來衡量一元模型中信息不確定性的指標。信息的不確定性越大，熵的值也就越大。而影響熵值的主要因素是概率。這里所說的一元模型就是指單一事件，而不確定性是一個事件出現(xiàn)不同結果的可能性。例如拋硬幣，可能出現(xiàn)的結果有兩個，分別是正面和反面。而每次拋硬幣的結果是一個非常不確定的信息。因為根據(jù)我們的經驗或者歷史數(shù)據(jù)來看，一個均勻的硬幣出現(xiàn)正面和反面的概率相等，都是50%。因此很難判斷下一次出現(xiàn)的是正面還是反面。這時拋硬幣這個事件的熵值也很高。而如果歷史數(shù)據(jù)告訴我們這枚硬幣在過去的100次試驗中99次都是正面，也就是說這枚硬幣的質量不均勻，出現(xiàn)正面結果的概率很高。那么我們就很容易判斷下一次的結果了。這時的熵值很低，只有0.08。 
條件熵是通過獲得更多的信息來消除一元模型中的不確定性。也就是通過二元或多元模型來降低一元模型的熵。我們知道的信息越多，信息的不確定性越小。例如，只使用一元模型時我們無法根據(jù)用戶歷史數(shù)據(jù)中的購買頻率來判斷這個用戶本次是否也會購買。因為不確定性太大。在加入了促銷活動，商品價格等信息后，在二元模型中我們可以發(fā)現(xiàn)用戶購買與促銷活動，或者商品價格變化之間的聯(lián)系。并通過購買與促銷活動一起出現(xiàn)的概率，和不同促銷活動時購買出現(xiàn)的概率來降低不確定性。 
構建決策樹實例這是一家高爾夫球俱樂部的歷史數(shù)據(jù)，里面記錄了不同天氣狀況用戶來打高爾夫球的歷史記錄。我們要做的是通過構建決策樹來預測用戶是否會來打高爾夫球。這里用戶是否來打球是一個一元模型，具有不確定性，熵值很高。我們無法僅通過Yes和No的頻率來判斷用戶明天是否會來。因此，需要借助天氣的信息來減少不確定性。下面分別記錄到了4種天氣情況，我們通過計算條件熵和互信息來開始構建決策樹的第一步：構建根決策點。 
構建根決策節(jié)點構建根決策點的方法就是尋找4種天氣情況中與打高爾夫球相關性最高的一個。首先我們來看Play Golf這個一元模型的熵，來看看這件事的不確定性有多高. 一元模型的熵在一元模型中，僅通過歷史數(shù)據(jù)的概率來看預測Play Golf是一件非常不確定的事情，在14條歷史數(shù)據(jù)中，打球的概率為64%，不打球的概率為36%。熵值達到了0.940。這與之前拋硬幣的例子很像。在無法改變歷史數(shù)據(jù)的概率時，我們需要借助更多的信息來降低不確定性。也就是計算條件熵。 
二元模型條件熵計算二元模型的條件熵需要知道Play Golf與4種天氣情況一起出現(xiàn)的聯(lián)合概率，以及在不同天氣情況下Play Golf出現(xiàn)的條件概率。下面我們分別來計算這兩類概率。 聯(lián)合概率 
條件概率 
互信息在已知Play Golf的一元模型熵和不同天氣條件下的二元模型熵后。我們就可以通過互信息來度量哪種天氣與Play Golf的相關性最高了。
構建根節(jié)點在整個決策樹中，Outlook因為與Play Golf的相關性最高，所以作為決策樹的根節(jié)點。以Outlook作為根節(jié)點后，決策樹出現(xiàn)了三個分支，分別是Outlook的三個不同的取值Sunny，Overcast和Rainy。其中Overcast所對應的Play Golf都是Yes，因此這個分支的葉子節(jié)點為Yes。(后面構建分支決策節(jié)點時會看到)另外兩個分支我們將使用和前面一樣的方法，通過計算熵，條件熵和互信息來挑選下一個分支的決策節(jié)點。
構建分支決策節(jié)點下面我們繼續(xù)構建Sunny，Overcast和Rainy這三個分支的決策節(jié)點，首先來看下Overcast節(jié)點，這個節(jié)點只有一種結果，因此無需在繼續(xù)分裂。 構建分支節(jié)點 Outlook 節(jié)點Overcast分支 在Outlook根節(jié)點下的Overcast分支中，Play Golf只有一種結果Yes，因此Overcast分支停止分裂。葉子節(jié)點的值為Yes。
在Outlook根節(jié)點下的Sunny分支中，單獨形成了另一個表。此時由于Outlook以及作為決策樹的根節(jié)點了，因此所需考慮的天氣情況為3種，我們繼續(xù)對這個表確定決策節(jié)點。從3種天氣情況中找出Sunny分支下的決策節(jié)點。方法及步驟和前面一致，計算熵，條件熵和互信息，并以互信息最大的作為Sunny分支的決策節(jié)點進行分裂。
互信息計算三種天氣情況與Play Golf的互信息值，也就是相關性。值越大相關性越高。三種天氣中Wind的互信息值最高，為0.971。說明Sunny分支下Wind和Play Golf的相關性最高。因此選擇Wind作為Sunny分支的決策節(jié)點。
在Outlook根節(jié)點的Sunny分支下，經過計算互信息的值Wind與Play Golf相關性最高，因此Wind作為Sunny的決策節(jié)點。Wind有兩個分支，分別為FALSE和TRUE。當Wind為FALSE時，Play Golf的結果為Yes。Wind為TRUE時結果為No。
Outlook根節(jié)點還有一個分支是Rainy。以下是Outlook下Rainy的分支數(shù)據(jù)表。我們從這個表中挑選出Rainy分支下的決策節(jié)點。由于Outlook以及作為決策樹的根節(jié)點，Wind成為了Sunny分支下的決策節(jié)點，因此我們需要考慮的天氣情況就只剩下兩種Temp和Humidity。
互信息Play Golf熵減去兩種天氣與Play Golf的條件熵獲得互信息的值。Humidity值最大，說明相關性最高。因此Humidity被選為Rainy分支的決策節(jié)點。
構建分支決策節(jié)點(Humidity)在Outlook的Rainy分支下，Humidity作為決策節(jié)點有兩個分支，分別為High和Normal。所有High分支都對應Play Golf的No，所有Normal分支都對應了Play Golf的Yes。因此停止繼續(xù)分裂。
數(shù)據(jù)表與決策樹通過將決策樹中每個決策點還原為原始數(shù)據(jù)表可以發(fā)現(xiàn)，每一個決策點都對應了一張數(shù)據(jù)表。從根決策節(jié)點開始，我們通過計算熵尋找與Play Golf最相關的天氣信息，來建立決策點及分支，并反復迭代這一過程。直到最終構建完整的決策樹。
使用決策樹進行預測文章開始的時候我們說過，決策樹是用來進行分類和預測的。具體過程如下。當我們構建好決策樹后，當有新的信息發(fā)送時，我們利用已有的決策樹邏輯對新的信息結構進行判斷。當信息的內容與決策樹一致時，就進入下一分支進行判斷，并通過葉子節(jié)點獲得分類的結果。例如，當新的一天開始時，我們就可以通過4個天氣特征來判斷用戶是否會來打高爾夫球。以下是具體預測流程的示意圖，首先尋找新信息中的根決策節(jié)點Outlook，根據(jù)Outlook的取值進入到Sunny分支，在Sunny分支中繼續(xù)判斷下一決策點Windy的取值，新的信息中Windy的取值為FALSE，根據(jù)決策樹中的邏輯返回Yes。因此在新信息中通過對天氣情況的判斷預測用戶會來打高爾夫球。
via:tuicool End. 轉載請注明來自36大數(shù)據(jù)（)：36大數(shù)據(jù) ? 決策樹分類和預測算法的原理及實現(xiàn) |
|
|
