決策樹的劃分依據之：信息增益

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

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

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

若使用a來對樣本集 D 進行劃分，則會產生 V 個分支結點,

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

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

其中：

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

公式的詳細解釋：

信息熵的計算：

條件熵的計算：

其中：

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

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

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


案例：

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

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

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

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

可得到三個熵：

a.計算類別信息熵

整體熵：

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

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

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

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

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

猜你喜歡：

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

DeepLab系列各有什么特點？

什么是KNN算法?

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

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