決策樹與隨機森林學習筆記-1.信息熵

05-14

信息熵

熵（entropy）是表示隨機變數不確定性的度量。設有隨機變數X，則：

$P(X=x_i)=p_i i=1,2...,n$

則隨機變數X的熵定義為：

$H(X)=-sum_{i=1}^{n}{p_ilog(p_i)}$

熵只依賴X的分布，而與X的取值無關，所以也可將X的熵記為H(X)。

當隨機變數X只取（0,1）即服從Bernoulli Distribution 則X的分布為:

$P(X=1)=p quad P(X=0)=1-p$

熵為：

$H(X)=-p log_2p-(1-p)log_2p$

設有隨機變數（X,Y）聯合分布概率為

$P(X=x_i,Y=y_i)=p_{i j}quad i=1,2...n j=1,2,...m$

條件熵

條件熵H（Y|X）表示在已知隨機變數X的條件下，隨機變數Y的不確定性，隨機變數X給定的條件下隨機變數Y 的條件熵（conditional entropy）H（Y|X），定義為X給定條件下Y的條件概率分布的熵對X的數學期望：

$H(Y|X)=sum_{i=1}^{n}p_i H(Y|X=x_i ) quad p_i=P(X=x_i), i=1,2,..n$

當熵和條件熵中的概率由數據估計（特別是極大似然估計）得到時，所對應的熵與條件熵分別稱為經驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）。此時如果有0概率，令 $0log0=0$ 。

信息增益

信息增益（information gain）表示得知特徵X的信息而使得類Y的信息不確定性減少的程度，特徵A對訓練數據集D的信息增益定義為集合D的經驗熵與特徵A給定條件下D的經驗條件熵之差，即：

$g(D,A)=H(D)-H(D|A)$

一般地，熵H(Y)與條件熵H(Y|X)之差稱為互信息（mutual information）,決策樹學習中的信息增益等價於訓練數據集中類與特徵的互信息。

設訓練數據集為D，|D|表示其樣本容量，即樣本個數，設有K個類 $C_k, k=1,2,...K$ ,

$|C_k|$ 為屬於 $C_k$ 的樣本個數, $sum_{k=1}^{K}|C_k|=|D|$ 。設特徵A有n個不同的取值， $left{ a_1,a_2 ,a_3,...,a_n ight}$ ，根據特徵A的取值將D劃分為n個子集， $D_1，D_2,...,D_n,|D_i|表示Di的樣本數， sum_{i=1}^{n}|D_i|=|D|$ 。記子集Di中屬於類Ck的樣本的集合為 $D_{ik}=D_icap C_k$ ，於是信息增益的演算法如下：

計算數據集D 的經驗熵 $H(D)=-sum_{k=1}^{K}frac{|C_k|}{|D|}log_{2}frac{|C_k|}{|D|}$
計算特徵A對數據集D的經驗條件熵 $H(D|A)=sum_{i=1}^{n}frac{|D_i|}{|D|}H(D_i)=-sum_{i=1}^{K}frac{|D_{ik}|}{|D_i|}log_2frac{|D_{ik}|}{|D_i|}$
計算信息增益 $g(D,A)=H(D)-H(D|A)$

信息增益比

信息增益比: 以信息增益作為劃分訓練數據集的特徵，存在偏向於選擇取值較多的特徵問題。使用信息增益比（information gain ration）可以對這一問題進行校正。這是特徵選擇的另一種準則。特徵A對訓練數據集D的信息增益比 $g_R(D, A)$ 定義為其信息增益 $g(D,A)$ 與訓練數據集D關於特徵A的值的熵 $H_A(D)$ 之比。

$g_R(D,A)=frac {g(D,A)}{H_A(D)} quad H_A(D)=-sum_{i=1} ^n{frac {|D_i|}{D}log_2frac{|D_i|}{D}} n是特徵A取值的個數$

基尼係數

基尼係數：分類問題中，假設有K個類，樣本點屬於第k類的概率為 $p_k$ ,則概率分布的基尼指數定義為：

$Gini(p)=sum_{k=1}^{K}p_k(1-p_k)=1-sum_{k=1}^K p_k^2$

對於二分類問題，若樣本點屬於第1個類的概率是p，則概率分布的基尼指數為：

$Gini(p)=2p(1-p)$

對於給定的樣本集合D，其基尼指數為：

$Gini(D)=1-sum_{k=1}^K(frac{|C_k|}{|D|})^2$

這裡， $C_k$ 是D中屬於第k類的樣本子集，K是類的個數。

表中為一個由15個樣本組成的貸款申請訓練數據，數據包括貸款申請人申請訓練數據，數據包括貸款申請人的4個特徵：第一個特徵是年齡：青年，中年，中年；第二個特徵是有工作，是2個可能值：是，否；第三個特徵是有自己的房子，有2個可能值：是，否；第四個特徵是信貸情況，有3個可能值：非常好，好，一般。表的最後一類是類別（結局），是否同意貸款，取2個值：是，否。

希望通過所給的訓練數據學習一個貸款申請的決策樹，用以對未來的貸款申請進行分類，即當新的客戶提出貸款申請時，根據申請人的特徵利用決策樹決定是否批准貸款申請。

根據表中數據分別計算四個特徵的信息增益，信息增益率。代入計算公式，得到：

統計學習方法-李航