本文關(guān)鍵詞：決策樹分類，由筆耕文化傳播整理發(fā)布。

決策樹分類和預(yù)測(cè)算法的原理及實(shí)現(xiàn)

作者：藍(lán)鯨

算法決策樹是一種通過對(duì)歷史數(shù)據(jù)進(jìn)行測(cè)算實(shí)現(xiàn)對(duì)新數(shù)據(jù)進(jìn)行分類和預(yù)測(cè)的算法。簡(jiǎn)單來說決策樹算法就是通過對(duì)已有明確結(jié)果的歷史數(shù)據(jù)進(jìn)行分析，尋找數(shù)據(jù)中的特征。并以此為依據(jù)對(duì)新產(chǎn)生的數(shù)據(jù)結(jié)果進(jìn)行預(yù)測(cè)。

決策樹由3個(gè)主要部分組成，分別為決策節(jié)點(diǎn)，分支，和葉子節(jié)點(diǎn)。其中決策樹最頂部的決策節(jié)點(diǎn)是根決策節(jié)點(diǎn)。每一個(gè)分支都有一個(gè)新的決策節(jié)點(diǎn)。決策節(jié)點(diǎn)下面是葉子節(jié)點(diǎn)。每個(gè)決策節(jié)點(diǎn)表示一個(gè)待分類的數(shù)據(jù)類別或?qū)傩裕總�(gè)葉子節(jié)點(diǎn)表示一種結(jié)果。整個(gè)決策的過程從根決策節(jié)點(diǎn)開始，從上到下。根據(jù)數(shù)據(jù)的分類在每個(gè)決策節(jié)點(diǎn)給出不同的結(jié)果。

構(gòu)造決策樹是一個(gè)復(fù)雜的工作。下面我們將介紹決策樹中的ID3算法和“信息熵”的概念。并手工創(chuàng)建一個(gè)簡(jiǎn)單的決策樹，用以說明整個(gè)構(gòu)建的過程和思路。

ID3算法

構(gòu)造決策樹的方法有很多種，ID3是其中的一種算法。ID3算法最早是由羅斯昆(J. Ross Quinlan)1975年在悉尼大學(xué)提出的一種分類預(yù)測(cè)算法，核心是“信息熵”。ID3算法認(rèn)為“互信息”高的屬性是好屬性，，通過計(jì)算歷史數(shù)據(jù)中每個(gè)類別或?qū)傩缘摹靶畔㈧亍鲍@得“互信息”，并選擇“互信息”最高的類別或?qū)傩宰鳛闆Q策樹中的決策節(jié)點(diǎn)，將類別或?qū)傩缘闹底鰹榉种Ю^續(xù)進(jìn)行分裂。不斷重復(fù)這個(gè)過程，直到生成一棵完整的決策樹。

信息熵的含義及分類

信息熵是信息論中的一個(gè)重要的指標(biāo)，是由香農(nóng)在1948年提出的。香農(nóng)借用了熱力學(xué)中熵的概念來描述信息的不確定性。因此信息學(xué)中的熵和熱力學(xué)的熵是有聯(lián)系的。根據(jù)Charles H. Bennett對(duì)Maxwell’s Demon的重新解釋，對(duì)信息的銷毀是一個(gè)不可逆過程，所以銷毀信息是符合熱力學(xué)第二定律的。而產(chǎn)生信息，則是為系統(tǒng)引入負(fù)(熱力學(xué))熵的過程。 所以信息熵的符號(hào)與熱力學(xué)熵應(yīng)該是相反的 。

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

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

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

在拋硬幣的例子中，我們借助一元模型自身的概率，也就是前100次的歷史數(shù)據(jù)來消除了判斷結(jié)果的不確定性。而對(duì)于很多現(xiàn)實(shí)生活中的問題，則無法僅僅通過自身概率來判斷。例如：對(duì)于天氣情況，我們無法像拋硬幣一樣通過晴天，雨天和霧霾在歷史數(shù)據(jù)中出現(xiàn)的概率來判斷明天的天氣，因?yàn)樘鞖獾姆N類很多，并且影響天氣的因素也有很多。同理，對(duì)于網(wǎng)站的用戶我們也無法通過他們的歷史購買頻率來判斷這個(gè)用戶在下一次訪問時(shí)是否會(huì)完成購買。因?yàn)橛脩羰堑馁徺I行為存在著不確定性，要消除這些不確定性需要更多的信息。例如用戶歷史行為中的廣告創(chuàng)意，促銷活動(dòng)，商品價(jià)格，配送時(shí)間等信息。因此這里我們不能只借助一元模型來進(jìn)行判斷和預(yù)測(cè)了，需要獲得更多的信息并通過二元模型或更高階的模型了解用戶的購買行為與其他因素間的關(guān)系來消除不確定性。衡量這種關(guān)系的指標(biāo)叫做條件熵。

條件熵是通過獲得更多的信息來消除一元模型中的不確定性。也就是通過二元或多元模型來降低一元模型的熵。我們知道的信息越多，信息的不確定性越小。例如，只使用一元模型時(shí)我們無法根據(jù)用戶歷史數(shù)據(jù)中的購買頻率來判斷這個(gè)用戶本次是否也會(huì)購買。因?yàn)椴淮_定性太大。在加入了促銷活動(dòng)，商品價(jià)格等信息后，在二元模型中我們可以發(fā)現(xiàn)用戶購買與促銷活動(dòng)，或者商品價(jià)格變化之間的聯(lián)系。并通過購買與促銷活動(dòng)一起出現(xiàn)的概率，和不同促銷活動(dòng)時(shí)購買出現(xiàn)的概率來降低不確定性。

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

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

熵，條件熵和互信息是構(gòu)建決策樹的三個(gè)關(guān)鍵的指標(biāo)。下面我們將通過一個(gè) 維基百科 中的實(shí)例說明創(chuàng)建決策樹的過程。

構(gòu)建決策樹實(shí)例

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

構(gòu)建根決策節(jié)點(diǎn)

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

一元模型的熵

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

二元模型條件熵

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

聯(lián)合概率

以上是經(jīng)過分別計(jì)算后4種天氣情況與Play Golf同時(shí)出現(xiàn)的聯(lián)合概率值。

條件概率

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

互信息

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

通過互信息的值可以發(fā)現(xiàn)，4種天氣中Outlook的值最大。說明Outlook與Play Golf的相關(guān)性最高。因此我們選擇Outlook作為決策樹的根節(jié)點(diǎn)來構(gòu)建決策樹。

構(gòu)建根節(jié)點(diǎn)

在整個(gè)決策樹中，Outlook因?yàn)榕cPlay Golf的相關(guān)性最高，所以作為決策樹的根節(jié)點(diǎn)。以O(shè)utlook作為根節(jié)點(diǎn)后，決策樹出現(xiàn)了三個(gè)分支，分別是Outlook的三個(gè)不同的取值Sunny，Overcast和Rainy。其中Overcast所對(duì)應(yīng)的Play Golf都是Yes，因此這個(gè)分支的葉子節(jié)點(diǎn)為Yes。(后面構(gòu)建分支決策節(jié)點(diǎn)時(shí)會(huì)看到)另外兩個(gè)分支我們將使用和前面一樣的方法，通過計(jì)算熵，條件熵和互信息來挑選下一個(gè)分支的決策節(jié)點(diǎn)。

構(gòu)建分支決策節(jié)點(diǎn)

下面我們繼續(xù)構(gòu)建Sunny，Overcast和Rainy這三個(gè)分支的決策節(jié)點(diǎn)，首先來看下Overcast節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)只有一種結(jié)果，因此無需在繼續(xù)分裂。

構(gòu)建分支節(jié)點(diǎn)

Outlook 節(jié)點(diǎn)Overcast分支

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

Outlook 節(jié)點(diǎn)Sunny分支

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

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

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

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

互信息

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

構(gòu)建分支決策節(jié)點(diǎn)(Windy)

在Outlook根節(jié)點(diǎn)的Sunny分支下，經(jīng)過計(jì)算互信息的值Wind與Play Golf相關(guān)性最高，因此Wind作為Sunny的決策節(jié)點(diǎn)。Wind有兩個(gè)分支，分別為FALSE和TRUE。當(dāng)Wind為FALSE時(shí)，Play Golf的結(jié)果為Yes。Wind為TRUE時(shí)結(jié)果為No。

Outlook 節(jié)點(diǎn)Rainy分支

Outlook根節(jié)點(diǎn)還有一個(gè)分支是Rainy。以下是Outlook下Rainy的分支數(shù)據(jù)表。我們從這個(gè)表中挑選出Rainy分支下的決策節(jié)點(diǎn)。由于Outlook以及作為決策樹的根節(jié)點(diǎn)，Wind成為了Sunny分支下的決策節(jié)點(diǎn)，因此我們需要考慮的天氣情況就只剩下兩種Temp和Humidity。

首先計(jì)算在Rainy分支下Play Golf的熵。從歷史數(shù)據(jù)看No和Yes的概率為60%和40%，熵為0.971，一元模型依靠自身概率的不確定性較高。加入兩個(gè)天氣情況的信息來計(jì)算條件熵。

通過計(jì)算兩種天氣情況與Play Golf的聯(lián)合概率和條件概率發(fā)現(xiàn)，情況與Sunny分支類似。Humidity應(yīng)該與Play Golf的相關(guān)性較高。

通過計(jì)算獲得Temp和Humidity與Play Golf的條件熵，其中Humidity與Play Golf的條件熵為0。

互信息

Play Golf熵減去兩種天氣與Play Golf的條件熵獲得互信息的值。Humidity值最大，說明相關(guān)性最高。因此Humidity被選為Rainy分支的決策節(jié)點(diǎn)。

構(gòu)建分支決策節(jié)點(diǎn)(Humidity)

在Outlook的Rainy分支下，Humidity作為決策節(jié)點(diǎn)有兩個(gè)分支，分別為High和Normal。所有High分支都對(duì)應(yīng)Play Golf的No，所有Normal分支都對(duì)應(yīng)了Play Golf的Yes。因此停止繼續(xù)分裂。

到此為止我們通過Play Golf與天氣情況的歷史數(shù)據(jù)構(gòu)建了決策樹。下面我們?cè)趶妮^高的維度來看下整個(gè)決策樹與歷史數(shù)據(jù)表間的關(guān)系。

數(shù)據(jù)表與決策樹

通過將決策樹中每個(gè)決策點(diǎn)還原為原始數(shù)據(jù)表可以發(fā)現(xiàn)，每一個(gè)決策點(diǎn)都對(duì)應(yīng)了一張數(shù)據(jù)表。從根決策節(jié)點(diǎn)開始，我們通過計(jì)算熵尋找與Play Golf最相關(guān)的天氣信息，來建立決策點(diǎn)及分支，并反復(fù)迭代這一過程。直到最終構(gòu)建完整的決策樹。

使用決策樹進(jìn)行預(yù)測(cè)

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

通過隨機(jī)森林提高準(zhǔn)確率

決策樹是建立在已知的歷史數(shù)據(jù)及概率上的，一課決策樹的預(yù)測(cè)可能會(huì)不太準(zhǔn)確，提高準(zhǔn)確率最好的方法是構(gòu)建隨機(jī)森林(Random Forest)。所謂隨機(jī)森林就是通過隨機(jī)抽樣的方式從歷史數(shù)據(jù)表中生成多張抽樣的歷史表，對(duì)每個(gè)抽樣的歷史表生成一棵決策樹。由于每次生成抽樣表后數(shù)據(jù)都會(huì)放回到總表中，因此每一棵決策樹之間都是獨(dú)立的沒有關(guān)聯(lián)。將多顆決策樹組成一個(gè)隨機(jī)森林。當(dāng)有一條新的數(shù)據(jù)產(chǎn)生時(shí)，讓森林里的每一顆決策樹分別進(jìn)行判斷，以投票最多的結(jié)果作為最終的判斷結(jié)果。以此來提高正確的概率。

via:tuicool

End.

轉(zhuǎn)載請(qǐng)注明來自36大數(shù)據(jù)（36dsj.com)：36大數(shù)據(jù) » 決策樹分類和預(yù)測(cè)算法的原理及實(shí)現(xiàn)

標(biāo)簽：

  除非特別注明，本站所有文章均不代表本站觀點(diǎn)。報(bào)道中出現(xiàn)的商標(biāo)屬于其合法持有人。請(qǐng)遵守理性，寬容，換位思考的原則。

猜你喜歡

評(píng)論 搶沙發(fā)

  本文關(guān)鍵詞：決策樹分類，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：146541