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

1、概述

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

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

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

2、算法思想

通俗來說，決策樹分類的思想類似于找對象?，F(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

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

      母親：26。

      女兒：長的帥不帥？

      母親：挺帥的。

      女兒：收入高不？

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

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

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

      女兒：那好，我去見見。 

這個女孩的決策過程就是典型的分類樹決策。

實(shí)質(zhì)：通過年齡、長相、收入和是否公務(wù)員對將男人分為兩個類別：見和不見

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

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

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

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

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

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

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

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

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

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

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

樣本    紅     大      好蘋果

0         1      1         1

1         1      0         1

2         0      1         0

3         0      0         0

樣本中有2個屬性，A0表示是否紅蘋果。A1表示是否大蘋果。假如要根據(jù)這個數(shù)據(jù)樣本構(gòu)建一棵自動判斷蘋果好壞的決策樹。

由于本例中的數(shù)據(jù)只有2個屬性，因此，我們可以窮舉所有可能構(gòu)造出來的決策樹，就2棵，如下圖所示：

顯然左邊先使用A0（紅色）做劃分依據(jù)的決策樹要優(yōu)于右邊用A1（大?。┳鰟澐忠罁?jù)的決策樹。

當(dāng)然這是直覺的認(rèn)知。而直覺顯然不適合轉(zhuǎn)化成程序的實(shí)現(xiàn)，所以需要有一種定量的考察來評價這兩棵樹的性能好壞。

決策樹的評價所用的定量考察方法為計算每種劃分情況的信息熵增益：

如果經(jīng)過某個選定的屬性進(jìn)行數(shù)據(jù)劃分后的信息熵下降最多，則這個劃分屬性是最優(yōu)選擇 

屬性劃分選擇（即構(gòu)造決策樹）的依據(jù)：

簡單來說，熵就是“無序，混亂”的程度。

通過計算來理解：

1、原始樣本數(shù)據(jù)的熵：

樣例總數(shù)：4

好蘋果：2

壞蘋果：2

熵： -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1

信息熵為1表示當(dāng)前處于最混亂，最無序的狀態(tài)。

2、兩顆決策樹的劃分結(jié)果熵增益計算

樹1先選A0作劃分，各子節(jié)點(diǎn)信息熵計算如下：

0，1葉子節(jié)點(diǎn)有2個正例，0個負(fù)例。信息熵為：e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。

2，3葉子節(jié)點(diǎn)有0個正例，2個負(fù)例。信息熵為：e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

因此選擇A0劃分后的信息熵為每個子節(jié)點(diǎn)的信息熵所占比重的加權(quán)和：E = e1*2/4 + e2*2/4 = 0。

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

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

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

0，2子節(jié)點(diǎn)有1個正例，1個負(fù)例。信息熵為：e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

1，3子節(jié)點(diǎn)有1個正例，1個負(fù)例。信息熵為：e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

因此選擇A1劃分后的信息熵為每個子節(jié)點(diǎn)的信息熵所占比重的加權(quán)和：E = e1*2/4 + e2*2/4 = 1。也就是說分了跟沒分一樣！

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

因此，每次劃分之前，我們只需要計算出信息熵增益最大的那種劃分即可。

先做A0劃分時的信息熵增益為1>先做A1劃分時的信息熵增益，所以先做A0劃分是最優(yōu)選擇?。?！

4、算法指導(dǎo)思想

經(jīng)過決策屬性的劃分后，數(shù)據(jù)的無序度越來越低，也就是信息熵越來越小 

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

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

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

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

最新評論