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

更新時(shí)間:2021-09-16 來(lái)源:黑馬程序員瀏覽量:

IT培訓(xùn)班

信息增益：以某特征劃分?jǐn)?shù)據(jù)集前后的熵的差值。熵可以表示樣本集合的不確定性，熵越大，樣本的不確定性就越大。因此可以使用劃分前后集合熵的差值來(lái)衡量使用當(dāng)前特征對(duì)于樣本集合D劃分效果的好壞。
信息增益 = entroy(前) - entroy(后)
注：信息增益表示得知特征X的信息而使得類Y的信息熵減少的程度

定義與公式
假定離散屬性a有 V 個(gè)可能的取值:

假設(shè)離散屬性性別有2（男，女）個(gè)可能的取值

若使用a來(lái)對(duì)樣本集 D 進(jìn)行劃分，則會(huì)產(chǎn)生 V 個(gè)分支結(jié)點(diǎn),

其中第v個(gè)分支結(jié)點(diǎn)包含了 D 中所有在屬性a上取值為 $a^v$ 的樣本，記為 $D^v$ . 我們可根據(jù)前面給出的信息熵公式計(jì)算出 $D^v$ 的信息熵，再考慮到不同的分支結(jié)點(diǎn)所包含的樣本數(shù)不同，給分支結(jié)點(diǎn)賦予權(quán)重 $\frac{|D^v|}{|D|}$

即樣本數(shù)越多的分支結(jié)點(diǎn)的影響越大，于是可計(jì)算出用屬性a對(duì)樣本集 D 進(jìn)行劃分所獲得的"信息增益" (information gain)

其中：

特征a對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益Gain(D,a),定義為集合D的信息熵Ent(D)與給定特征a條件下D的信息條件熵 $Ent(D|a)$ 之差，即公式為：

公式的詳細(xì)解釋：

信息熵的計(jì)算：

條件熵的計(jì)算：

其中：

$D^v$ 表示a屬性中第v個(gè)分支節(jié)點(diǎn)包含的樣本數(shù)

$C^{kv}$ 表示a屬性中第v個(gè)分支節(jié)點(diǎn)包含的樣本數(shù)中，第k個(gè)類別下包含的樣本數(shù)

一般而言，信息增益越大，則意味著使用屬性 a 來(lái)進(jìn)行劃分所獲得的"純度提升"越大。因此，我們可用信息增益來(lái)進(jìn)行決策樹(shù)的劃分屬性選擇，著名的 ID3 決策樹(shù)學(xué)習(xí)算法 [Quinlan， 1986] 就是以信息增益為準(zhǔn)則來(lái)選擇劃分屬性。其中，ID3 名字中的 ID 是 Iterative Dichotomiser (迭代二分器)的簡(jiǎn)稱

案例：