熱線電話：13121318867

登錄
首頁精彩閱讀決策樹分類和預測算法的原理及實現
決策樹分類和預測算法的原理及實現
2016-03-22
收藏
算法決策樹是一種通過對歷史數據進行測算實現對新數據進行分類和預測的算法。簡單來說決策樹算法就是通過對已有明確結果的歷史數據進行分析，尋找數據中的特征。并以此為依據對新產生的數據結果進行預測。

決策樹由3個主要部分組成，分別為決策節點，分支，和葉子節點。其中決策樹最頂部的決策節點是根決策節點。每一個分支都有一個新的決策節點。決策節點下面是葉子節點。每個決策節點表示一個待分類的數據類別或屬性，每個葉子節點表示一種結果。整個決策的過程從根決策節點開始，從上到下。根據數據的分類在每個決策節點給出不同的結果。



構造決策樹是一個復雜的工作。下面我們將介紹決策樹中的ID3算法和“信息熵”的概念。并手工創建一個簡單的決策樹，用以說明整個構建的過程和思路。

ID3算法

構造決策樹的方法有很多種，ID3是其中的一種算法。ID3算法最早是由羅斯昆(J. Ross Quinlan)1975年在悉尼大學提出的一種分類預測算法，核心是“信息熵”。ID3算法認為“互信息”高的屬性是好屬性，通過計算歷史數據中每個類別或屬性的“信息熵”獲得“互信息”，并選擇“互信息”最高的類別或屬性作為決策樹中的決策節點，將類別或屬性的值做為分支繼續進行分裂。不斷重復這個過程，直到生成一棵完整的決策樹。

信息熵的含義及分類

信息熵是信息論中的一個重要的指標，是由香農在1948年提出的。香農借用了熱力學中熵的概念來描述信息的不確定性。因此信息學中的熵和熱力學的熵是有聯系的。根據Charles H. Bennett對Maxwell’s Demon的重新解釋，對信息的銷毀是一個不可逆過程，所以銷毀信息是符合熱力學第二定律的。而產生信息，則是為系統引入負(熱力學)熵的過程。 所以信息熵的符號與熱力學熵應該是相反的 。

簡單的說信息熵是衡量信息的指標，更確切的說是衡量信息的不確定性或混亂程度的指標。信息的不確定性越大，熵越大。決定信息的不確定性或者說復雜程度主要因素是概率。決策樹中使用的與熵有關的概念有三個：信息熵，條件熵和互信息。下面分別來介紹這三個概念的含義和計算方法。

信息熵是用來衡量一元模型中信息不確定性的指標。信息的不確定性越大，熵的值也就越大。而影響熵值的主要因素是概率。這里所說的一元模型就是指單一事件，而不確定性是一個事件出現不同結果的可能性。例如拋硬幣，可能出現的結果有兩個，分別是正面和反面。而每次拋硬幣的結果是一個非常不確定的信息。因為根據我們的經驗或者歷史數據來看，一個均勻的硬幣出現正面和反面的概率相等，都是50%。因此很難判斷下一次出現的是正面還是反面。這時拋硬幣這個事件的熵值也很高。而如果歷史數據告訴我們這枚硬幣在過去的100次試驗中99次都是正面，也就是說這枚硬幣的質量不均勻，出現正面結果的概率很高。那么我們就很容易判斷下一次的結果了。這時的熵值很低，只有0.08。



我們把拋硬幣這個事件看做一個隨機變量S，它可能的取值有2種，分別是正面x1和反面x2。每一種取值的概率分別為P1和P2。 我們要獲得隨機變量S的取值結果至少要進行1次試驗，試驗次數與隨機變量S可能的取值數量(2種)的對數函數Log有聯系。Log2=1(以2為底)。因此熵的計算公式是：



在拋硬幣的例子中，我們借助一元模型自身的概率，也就是前100次的歷史數據來消除了判斷結果的不確定性。而對于很多現實生活中的問題，則無法僅僅通過自身概率來判斷。例如：對于天氣情況，我們無法像拋硬幣一樣通過晴天，雨天和霧霾在歷史數據中出現的概率來判斷明天的天氣，因為天氣的種類很多，并且影響天氣的因素也有很多。同理，對于網站的用戶我們也無法通過他們的歷史購買頻率來判斷這個用戶在下一次訪問時是否會完成購買。因為用戶是的購買行為存在著不確定性，要消除這些不確定性需要更多的信息。例如用戶歷史行為中的廣告創意，促銷活動，商品價格，配送時間等信息。因此這里我們不能只借助一元模型來進行判斷和預測了，需要獲得更多的信息并通過二元模型或更高階的模型了解用戶的購買行為與其他因素間的關系來消除不確定性。衡量這種關系的指標叫做條件熵。

條件熵是通過獲得更多的信息來消除一元模型中的不確定性。也就是通過二元或多元模型來降低一元模型的熵。我們知道的信息越多，信息的不確定性越小。例如，只使用一元模型時我們無法根據用戶歷史數據中的購買頻率來判斷這個用戶本次是否也會購買。因為不確定性太大。在加入了促銷活動，商品價格等信息后，在二元模型中我們可以發現用戶購買與促銷活動，或者商品價格變化之間的聯系。并通過購買與促銷活動一起出現的概率，和不同促銷活動時購買出現的概率來降低不確定性。



計算條件熵時使用到了兩種概率，分別是購買與促銷活動的聯合概率P(c)，和不同促銷活動出現時購買也出現的條件概率E(c)。以下是條件熵E(T，X)的計算公式。條件熵的值越低說明二元模型的不確定性越小。



互信息是用來衡量信息之間相關性的指標。當兩個信息完全相關時，互信息為1，不相關時為0。在前面的例子中用戶購買與促銷活動這兩個信息間的相關性究竟有多高，我們可以通過互信息這個指標來度量。具體的計算方法就熵與條件熵之間的差。用戶購買的熵E(T)減去促銷活動出現時用戶購買的熵E(T，X)。以下為計算公式：



熵，條件熵和互信息是構建決策樹的三個關鍵的指標。下面我們將通過一個 維基百科 中的實例說明創建決策樹的過程。

構建決策樹實例

這是一家高爾夫球俱樂部的歷史數據，里面記錄了不同天氣狀況用戶來打高爾夫球的歷史記錄。我們要做的是通過構建決策樹來預測用戶是否會來打高爾夫球。這里用戶是否來打球是一個一元模型，具有不確定性，熵值很高。我們無法僅通過Yes和No的頻率來判斷用戶明天是否會來。因此，需要借助天氣的信息來減少不確定性。下面分別記錄到了4種天氣情況，我們通過計算條件熵和互信息來開始構建決策樹的第一步：構建根決策點。



構建根決策節點

構建根決策點的方法就是尋找4種天氣情況中與打高爾夫球相關性最高的一個。首先我們來看Play Golf這個一元模型的熵，來看看這件事的不確定性有多高.

1.一元模型的熵

在一元模型中，僅通過歷史數據的概率來看預測Play Golf是一件非常不確定的事情，在14條歷史數據中，打球的概率為64%，不打球的概率為36%。熵值達到了0.940。這與之前拋硬幣的例子很像。在無法改變歷史數據的概率時，我們需要借助更多的信息來降低不確定性。也就是計算條件熵。



2.二元模型條件熵

計算二元模型的條件熵需要知道Play Golf與4種天氣情況一起出現的聯合概率，以及在不同天氣情況下Play Golf出現的條件概率。下面我們分別來計算這兩類概率。



以上是經過分別計算后4種天氣情況與Play Golf同時出現的聯合概率值。



同時我們也分別計算出了4種天氣情況下，不同取值時Play Golf的條件概率值。并通過聯合概率與條件概率求得4種天氣情況與Play Golf間的條件熵。



互信息

在已知Play Golf的一元模型熵和不同天氣條件下的二元模型熵后。我們就可以通過互信息來度量哪種天氣與Play Golf的相關性最高了。



通過互信息的值可以發現，4種天氣中Outlook的值最大。說明Outlook與Play Golf的相關性最高。因此我們選擇Outlook作為決策樹的根節點來構建決策樹。



構建根節點

在整個決策樹中，Outlook因為與Play Golf的相關性最高，所以作為決策樹的根節點。以Outlook作為根節點后，決策樹出現了三個分支，分別是Outlook的三個不同的取值Sunny，Overcast和Rainy。其中Overcast所對應的Play Golf都是Yes，因此這個分支的葉子節點為Yes。(后面構建分支決策節點時會看到)另外兩個分支我們將使用和前面一樣的方法，通過計算熵，條件熵和互信息來挑選下一個分支的決策節點。


構建分支決策節點

下面我們繼續構建Sunny，Overcast和Rainy這三個分支的決策節點，首先來看下Overcast節點，這個節點只有一種結果，因此無需在繼續分裂。

1.構建分支節點

Outlook 節點Overcast分支

在Outlook根節點下的Overcast分支中，Play Golf只有一種結果Yes，因此Overcast分支停止分裂。葉子節點的值為Yes。



Outlook 節點Sunny分支

在Outlook根節點下的Sunny分支中，單獨形成了另一個表。此時由于Outlook以及作為決策樹的根節點了，因此所需考慮的天氣情況為3種，我們繼續對這個表確定決策節點。從3種天氣情況中找出Sunny分支下的決策節點。方法及步驟和前面一致，計算熵，條件熵和互信息，并以互信息最大的作為Sunny分支的決策節點進行分裂。



首先計算Play Golf的一元模型熵，可以看到在Sunny這一分支中根據Play Golf自身的歷史數據 No和Yes的概率分布為40%和60%，熵值為0.971。具有極高的不確定性。因此我們繼續計算條件熵。



以下是三種天氣情況分別與Play Golf的聯合概率和條件概率計算結果。這里可以看到Wind有些與眾不同，Wind為FALSE時都為Play Golf的值都為Yes。



通過計算獲得三種天氣情況與Play Golf的條件概率，其中Wind的值為0。



互信息

計算三種天氣情況與Play Golf的互信息值，也就是相關性。值越大相關性越高。三種天氣中Wind的互信息值最高，為0.971。說明Sunny分支下Wind和Play Golf的相關性最高。因此選擇Wind作為Sunny分支的決策節點。


1.構建分支決策節點(Humidity)

在Outlook的Rainy分支下，Humidity作為決策節點有兩個分支，分別為High和Normal。所有High分支都對應Play Golf的No，所有Normal分支都對應了Play Golf的Yes。因此停止繼續分裂。



到此為止我們通過Play Golf與天氣情況的歷史數據構建了決策樹。下面我們在從較高的維度來看下整個決策樹與歷史數據表間的關系。

數據表與決策樹

通過將決策樹中每個決策點還原為原始數據表可以發現，每一個決策點都對應了一張數據表。從根決策節點開始，我們通過計算熵尋找與Play Golf最相關的天氣信息，來建立決策點及分支，并反復迭代這一過程。直到最終構建完整的決策樹。



使用決策樹進行預測

文章開始的時候我們說過，決策樹是用來進行分類和預測的。具體過程如下。當我們構建好決策樹后，當有新的信息發送時，我們利用已有的決策樹邏輯對新的信息結構進行判斷。當信息的內容與決策樹一致時，就進入下一分支進行判斷，并通過葉子節點獲得分類的結果。例如，當新的一天開始時，我們就可以通過4個天氣特征來判斷用戶是否會來打高爾夫球。以下是具體預測流程的示意圖，首先尋找新信息中的根決策節點Outlook，根據Outlook的取值進入到Sunny分支，在Sunny分支中繼續判斷下一決策點Windy的取值，新的信息中Windy的取值為FALSE，根據決策樹中的邏輯返回Yes。因此在新信息中通過對天氣情況的判斷預測用戶會來打高爾夫球。

決策樹預測



通過隨機森林提高準確率




決策樹是建立在已知的歷史數據及概率上的，一課決策樹的預測可能會不太準確，提高準確率最好的方法是構建隨機森林(Random Forest)。所謂隨機森林就是通過隨機抽樣的方式從歷史數據表中生成多張抽樣的歷史表，對每個抽樣的歷史表生成一棵決策樹。由于每次生成抽樣表后數據都會放回到總表中，因此每一棵決策樹之間都是獨立的沒有關聯。將多顆決策樹組成一個隨機森林。當有一條新的數據產生時，讓森林里的每一顆決策樹分別進行判斷，以投票最多的結果作為最終的判斷結果。以此來提高正確的概率。
來源 | 藍鯨的網站分析筆記
http://bluewhale.cc/2016-03-20/decision-tree.html


CDA數據分析師考試相關入口一覽（建議收藏）：

? 想報名CDA認證考試，點擊>>>   “CDA報名” 了解CDA考試詳情；

? 想學習CDA考試教材，點擊>>> “CDA教材” 了解CDA考試詳情；

? 想加入CDA考試題庫，點擊>>> “CDA題庫” 了解CDA考試詳情；

? 想了解CDA考試含金量，點擊>>> “CDA含金量” 了解CDA考試詳情；

決策樹 D3 隨機森林 特征

數據分析咨詢請掃描二維碼

若不方便掃碼，搜微信號：CDAshujufenxi

上一篇圖論在大數據分析中的作用！
下一篇CDA認證再升一檔！與國家共同推進大數據人才培養標準教育事業！
數據分析師考試動態
CDA報考指南
數據分析學習
數據分析師資訊
更多

CDA教育閉環

常見問題

關于我們

CDA數據分析師公眾號

  • CDA數據分析師公眾號

CDA考試中心小程序

  • CDA考試中心服務號

CDA數據分析師App下載

  • CDA數據分析師App下載
Copyright © 2015-2021, www.ruiqisteel.com All Rights Reserved. CDA數據分析師(北京國富如荷網絡科技有限公司) 版權所有 京ICP備11001960號-9 京公網安備 11010802034615號 經營許可證編號：京B2-20210330
聯系電話：13321103290 (微信同號)

OK
客服在線
立即咨詢
日韩人妻系列无码专区视频,先锋高清无码,无码免费视欧非,国精产品一区一区三区无码
客服在線
立即咨詢