快牛策略量化課程之決策樹(shù)分類(lèi)算法

1、快牛策略量化課程之決策樹(shù)分類(lèi)算法決策樹(shù)分類(lèi)算法1、概述決策樹(shù)(decisiontree)是一種被廣泛使用的分類(lèi)算法。相比貝葉斯算法，決策樹(shù)的優(yōu)勢(shì)在于構(gòu)造過(guò)程不需要任何領(lǐng)域知識(shí)或參數(shù)設(shè)置在實(shí)際應(yīng)用中，對(duì)于探測(cè)式的知識(shí)發(fā)現(xiàn)，決策樹(shù)更加適用。2、算法思想這個(gè)女孩的決策過(guò)程就是典型的分類(lèi)樹(shù)決策。實(shí)質(zhì)：通過(guò)年齡、長(zhǎng)相、收入和是否公務(wù)員對(duì)將男人分為兩個(gè)類(lèi)別：見(jiàn)和不見(jiàn)假設(shè)這個(gè)女孩對(duì)男人的要求是：30歲以下、長(zhǎng)相中等以上并且是高收入者或中等以上收入的公務(wù)員，那么這個(gè)可以用下圖表示女孩的決策邏輯JI11;橙色節(jié)點(diǎn)表示決策結(jié)果箭頭表示在一個(gè)判斷條件在不同情況下的決策路徑圖中紅色箭頭表示了上面例子中女孩的決策過(guò)程。

2、這幅圖基本可以算是一顆決策樹(shù)，說(shuō)它“基本可以算”是因?yàn)閳D中的判定條件沒(méi)有量化，如收入高中低等等，還不能算是嚴(yán)格意義上的決策樹(shù)，如果將所有條件量化，則就變成真正的決策樹(shù)了。決策樹(shù)分類(lèi)算法的關(guān)鍵就是根據(jù)“先驗(yàn)數(shù)據(jù)”構(gòu)造一棵最佳的決策樹(shù)，用以預(yù)測(cè)未知數(shù)據(jù)的類(lèi)別決策樹(shù)：是一個(gè)樹(shù)結(jié)構(gòu)（可以是二叉樹(shù)或非二叉樹(shù)）。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類(lèi)別。使用決策樹(shù)進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開(kāi)始，測(cè)試待分類(lèi)項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)存放的類(lèi)別作為決策結(jié)果。3、決策樹(shù)構(gòu)造假如有以下判斷蘋(píng)果好壞的數(shù)

3、據(jù)樣本：梯本江丈好蘋(píng)寶TOC o 1-5 h z01111112D10樣本中有2個(gè)屬性，A0表示是否紅蘋(píng)果。A1表示是否大蘋(píng)果。假如要根據(jù)這個(gè)數(shù)據(jù)樣本構(gòu)建一棵自動(dòng)判斷蘋(píng)果好壞的決策樹(shù)。由于本例中的數(shù)據(jù)只有2個(gè)屬性，因此，我們可以窮舉所有可能構(gòu)造出來(lái)的決策樹(shù)，就2棵，如下圖所示：顯然左邊先使用A0(紅色)做劃分依據(jù)的決策樹(shù)要優(yōu)于右邊用A1(大小)做劃分依據(jù)的決策樹(shù)。當(dāng)然這是直覺(jué)的認(rèn)知。而直覺(jué)顯然不適合轉(zhuǎn)化成程序的實(shí)現(xiàn)，所以需要有一種定量的考察來(lái)評(píng)價(jià)這兩棵樹(shù)的性能好壞。決策樹(shù)的評(píng)價(jià)所用的定量考察方法為計(jì)算每種劃分情況的信息熵增益：如果經(jīng)過(guò)某個(gè)選定的屬性進(jìn)行數(shù)據(jù)劃分后的信息熵下降最多，則這個(gè)劃分屬性

4、是最優(yōu)選擇屬性劃分選擇(即構(gòu)造決策樹(shù))的依據(jù)：簡(jiǎn)單來(lái)說(shuō)，熵就是“無(wú)序，混亂”的程度。通過(guò)計(jì)算來(lái)理解：1、原始樣本數(shù)據(jù)的熵：樣例總數(shù)：4好蘋(píng)果：2壞蘋(píng)果：2熵：-(1/2*log(1/2)+1/2*log(1/2)=1信息熵為1表示當(dāng)前處于最混亂，最無(wú)序的狀態(tài)。2、兩顆決策樹(shù)的劃分結(jié)果熵增益計(jì)算樹(shù)1先選A0作劃分，各子節(jié)點(diǎn)信息熵計(jì)算如下：0,1葉子節(jié)點(diǎn)有2個(gè)正例，0個(gè)負(fù)例。信息熵為：el=-(2/2*log(2/2)+0/2*log(0/2)=0。2,3葉子節(jié)點(diǎn)有0個(gè)正例，2個(gè)負(fù)例。信息熵為：e2=-(0/2*log(0/2)+2/2*log(2/2)=0。因此選擇A0劃分后的信息熵為每個(gè)子節(jié)點(diǎn)

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