決策樹的劃分依據(jù)之:信息增益率

在上面的介紹中，我們有意忽略了"編號"這一列.若把"編號"也作為一個候選劃分屬性，則根據(jù)信息增益公式可計算出它的信息增益為 0.9182，遠大于其他候選劃分屬性。

計算每個屬性的信息熵過程中,我們發(fā)現(xiàn),該屬性的值為0, 也就是其信息增益為0.9182. 但是很明顯這么分類,最后出現(xiàn)的結(jié)果不具有泛化效果.無法對新樣本進行有效預(yù)測.

實際上，信息增益準(zhǔn)則對可取值數(shù)目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，著名的 C4.5 決策樹算法 [Quinlan， 1993J 不直接使用信息增益，而是使用"增益率" (gain ratio) 來選擇最優(yōu)劃分屬性.

增益率：增益率是用前面的信息增益Gain(D, a)和屬性a對應(yīng)的"固有值"(intrinsic value) [Quinlan , 1993J的比值來共同定義的。

屬性 a 的可能取值數(shù)目越多(即 V 越大)，則 IV(a) 的值通常會越大.


案例一

a.計算類別信息熵

b.計算性別屬性的信息熵(性別、活躍度)

c.計算活躍度的信息增益(性別、活躍度)

d.計算屬性分裂信息度量

用分裂信息度量來考慮某種屬性進行分裂時分支的數(shù)量信息和尺寸信息，我們把這些信息稱為屬性的內(nèi)在信息(instrisic information)。信息增益率用信息增益/內(nèi)在信息，會導(dǎo)致屬性的重要性隨著內(nèi)在信息的增大而減小(也就是說，如果這個屬性本身不確定性就很大，那我就越不傾向于選取它)，這樣算是對單純用信息增益有所補償。

e.計算信息增益率

活躍度的信息增益率更高一些，所以在構(gòu)建決策樹的時候，優(yōu)先選擇

通過這種方式，在選取節(jié)點的過程中，我們可以降低取值較多的屬性的選取偏好。

案例二

如下圖，第一列為天氣，第二列為溫度，第三列為濕度，第四列為風(fēng)速，最后一列該活動是否進行。

我們要解決：根據(jù)下面表格數(shù)據(jù)，判斷在對應(yīng)天氣下，活動是否會進行?

該數(shù)據(jù)集有四個屬性，屬性集合A={ 天氣，溫度，濕度，風(fēng)速}， 類別標(biāo)簽有兩個，類別集合L={進行，取消}。

a.計算類別信息熵

類別信息熵表示的是所有樣本中各種類別出現(xiàn)的不確定性之和。根據(jù)熵的概念，熵越大，不確定性就越大，把事情搞清楚所需要的信息量就越多。

$Ent(D)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$

b.計算每個屬性的信息熵

每個屬性的信息熵相當(dāng)于一種條件熵。他表示的是在某種屬性的條件下，各種類別出現(xiàn)的不確定性之和。屬性的信息熵越大，表示這個屬性中擁有的樣本類別越不“純”。

c.計算信息增益

信息增益的 = 熵 - 條件熵，在這里就是 類別信息熵 - 屬性信息熵，它表示的是信息不確定性減少的程度。如果一個屬性的信息增益越大，就表示用這個屬性進行樣本劃分可以更好的減少劃分后樣本的不確定性，當(dāng)然，選擇該屬性就可以更快更好地完成我們的分類目標(biāo)。

信息增益就是ID3算法的特征選擇指標(biāo)。

e.計算信息增益率

天氣的信息增益率最高，選擇天氣為分裂屬性。發(fā)現(xiàn)分裂了之后，天氣是“陰”的條件下，類別是”純“的，所以把它定義為葉子節(jié)點，選擇不“純”的結(jié)點繼續(xù)分裂。

在子結(jié)點當(dāng)中重復(fù)過程1~5，直到所有的葉子結(jié)點足夠"純"。

現(xiàn)在我們來總結(jié)一下C4.5的算法流程

while(當(dāng)前節(jié)點"不純")：
    1.計算當(dāng)前節(jié)點的類別熵(以類別取值計算)
    2.計算當(dāng)前階段的屬性熵(按照屬性取值嚇得類別取值計算)
    3.計算信息增益
    4.計算各個屬性的分裂信息度量
    5.計算各個屬性的信息增益率
end while
當(dāng)前階段設(shè)置為葉子節(jié)點

猜你喜歡：

meanshift算法通俗講解【meanshift實例展示】

DRIVE AGX系列首先推出了一款新型Orin SoC

什么是KNN算法?

Numpy數(shù)組運算【黑馬程序員】

黑馬程序員ai人工智能開發(fā)課程