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

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

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

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

若使用a來對樣本集 D 進行劃分，則會產(chǎn)生 V 個分支結(jié)點,

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

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

其中：

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

公式的詳細解釋：

信息熵的計算：

條件熵的計算：

其中：

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

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

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


案例：

如下圖，第一列為論壇號碼，第二列為性別，第三列為活躍度，最后一列用戶是否流失。

我們要解決一個問題：性別和活躍度兩個特征，哪個對用戶流失影響更大?

通過計算信息增益可以解決這個問題，統(tǒng)計上右表信息

其中Positive為正樣本（已流失），Negative為負樣本（未流失），下面的數(shù)值為不同劃分下對應(yīng)的人數(shù)。

可得到三個熵：

a.計算類別信息熵

整體熵：

b.計算性別屬性的信息熵(a="性別")

c.計算性別的信息增益(a="性別")

b.計算活躍度屬性的信息熵(a="活躍度")

c.計算活躍度的信息增益(a="活躍度")

活躍度的信息增益比性別的信息增益大，也就是說，活躍度對用戶流失的影響比性別大。在做特征選擇或者數(shù)據(jù)分析的時候，我們應(yīng)該重點考察活躍度這個指標(biāo)。

猜你喜歡：

SIFT算法原理：SIFT算法詳細介紹

DeepLab系列各有什么特點？

什么是KNN算法?

如何成為頂級開源項目的貢獻者

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