本文實(shí)例為大家分享了python實(shí)現(xiàn)決策樹(shù)分類算法的具體代碼，供大家參考，具體內(nèi)容如下

1、概述

決策樹(shù)（decision tree）——是一種被廣泛使用的分類算法。

相比貝葉斯算法，決策樹(shù)的優(yōu)勢(shì)在于構(gòu)造過(guò)程不需要任何領(lǐng)域知識(shí)或參數(shù)設(shè)置

在實(shí)際應(yīng)用中，對(duì)于探測(cè)式的知識(shí)發(fā)現(xiàn)，決策樹(shù)更加適用。

2、算法思想

通俗來(lái)說(shuō)，決策樹(shù)分類的思想類似于找對(duì)象。現(xiàn)想象一個(gè)女孩的母親要給這個(gè)女孩介紹男朋友，于是有了下面的對(duì)話：

      女兒：多大年紀(jì)了？

      母親：26。

      女兒：長(zhǎng)的帥不帥？

      母親：挺帥的。

      女兒：收入高不？

      母親：不算很高，中等情況。

      女兒：是公務(wù)員不？

      母親：是，在稅務(wù)局上班呢。

      女兒：那好，我去見(jiàn)見(jiàn)。 

這個(gè)女孩的決策過(guò)程就是典型的分類樹(shù)決策。

實(shí)質(zhì)：通過(guò)年齡、長(zhǎng)相、收入和是否公務(wù)員對(duì)將男人分為兩個(gè)類別：見(jiàn)和不見(jiàn)

假設(shè)這個(gè)女孩對(duì)男人的要求是：30歲以下、長(zhǎng)相中等以上并且是高收入者或中等以上收入的公務(wù)員，那么這個(gè)可以用下圖表示女孩的決策邏輯

上圖完整表達(dá)了這個(gè)女孩決定是否見(jiàn)一個(gè)約會(huì)對(duì)象的策略，其中：

◊綠色節(jié)點(diǎn)表示判斷條件

◊橙色節(jié)點(diǎn)表示決策結(jié)果

◊箭頭表示在一個(gè)判斷條件在不同情況下的決策路徑

圖中紅色箭頭表示了上面例子中女孩的決策過(guò)程。 

這幅圖基本可以算是一顆決策樹(shù)，說(shuō)它“基本可以算”是因?yàn)閳D中的判定條件沒(méi)有量化，如收入高中低等等，還不能算是嚴(yán)格意義上的決策樹(shù)，如果將所有條件量化，則就變成真正的決策樹(shù)了。 

決策樹(shù)分類算法的關(guān)鍵就是根據(jù)“先驗(yàn)數(shù)據(jù)”構(gòu)造一棵最佳的決策樹(shù)，用以預(yù)測(cè)未知數(shù)據(jù)的類別 

決策樹(shù)：是一個(gè)樹(shù)結(jié)構(gòu)（可以是二叉樹(shù)或非二叉樹(shù)）。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試，每個(gè)分支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹(shù)進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開(kāi)始，測(cè)試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果。

3、決策樹(shù)構(gòu)造

假如有以下判斷蘋(píng)果好壞的數(shù)據(jù)樣本：

樣本    紅     大      好蘋(píng)果

0         1      1         1

1         1      0         1

2         0      1         0

3         0      0         0

樣本中有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è)劃分屬性是最優(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ù)例。信息熵為：e1 = -(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)的信息熵所占比重的加權(quán)和：E = e1*2/4 + e2*2/4 = 0。

選擇A0做劃分的信息熵增益G（S, A0）=S - E = 1 - 0 = 1.

事實(shí)上，決策樹(shù)葉子節(jié)點(diǎn)表示已經(jīng)都屬于相同類別，因此信息熵一定為0。 

樹(shù)2先選A1作劃分，各子節(jié)點(diǎn)信息熵計(jì)算如下：

0，2子節(jié)點(diǎn)有1個(gè)正例，1個(gè)負(fù)例。信息熵為：e1 = -(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 = e1*2/4 + e2*2/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)越低，也就是信息熵越來(lái)越小 

5、算法實(shí)現(xiàn)

梳理出數(shù)據(jù)中的屬性

比較按照某特定屬性劃分后的數(shù)據(jù)的信息熵增益，選擇信息熵增益最大的那個(gè)屬性作為第一劃分依據(jù)，然后繼續(xù)選擇第二屬性，以此類推

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論