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

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

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

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

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

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


案例一

a.計(jì)算類別信息熵

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

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

d.計(jì)算屬性分裂信息度量

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

e.計(jì)算信息增益率

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

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

案例二

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

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

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

a.計(jì)算類別信息熵

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

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

b.計(jì)算每個(gè)屬性的信息熵

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

c.計(jì)算信息增益

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

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

e.計(jì)算信息增益率

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

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

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

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

猜你喜歡：

meanshift算法通俗講解【meanshift實(shí)例展示】

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

什么是KNN算法?

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

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