av草草久久久久久久久久久,国产区av在线观看,色噜噜噜色噜噜噜色琪琪

99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

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

2016-03-22

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

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

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

ID3算法

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

信息熵的含義及分類

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

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

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

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

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

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

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

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

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

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

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

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

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

1.一元模型的熵

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

2.二元模型條件熵

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

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

同時我們也分別計算出了4種天氣情況下，不同取值時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é)點來構(gòu)建決策樹。

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

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

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

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

1.構(gòu)建分支節(jié)點

Outlook 節(jié)點Overcast分支

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

Outlook 節(jié)點Sunny分支

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

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

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

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

互信息

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

1.構(gòu)建分支決策節(jié)點(Humidity)

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

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

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

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

使用決策樹進行預(yù)測

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

決策樹預(yù)測

通過隨機森林提高準確率

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

來源 | 藍鯨的網(wǎng)站分析筆記

http://bluewhale.cc/2016-03-20/decision-tree.html

CDA數(shù)據(jù)分析師考試相關(guān)入口一覽（建議收藏）：

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