在介紹熵之前，先從另一個概念說起：信息量
世界杯決賽的兩支球隊中，哪支球隊獲得了冠軍？在對球隊實力沒有任何了解的情況下，每支球隊奪冠的概率都是1/2，所以誰獲得冠軍這條信息的信息量是 - log2 1/2 = 1 bit。如果信息是四強中的球隊誰獲得了冠軍，它的信息量是 - log2 1/4 = 2 bit。
其實這正好對應了計算機對數字的表示，如果用二進制表示，每一位出現0和1的概率都是1/2，所以每一位的信息量是1bit。如果用十六進制表示，每一位出現任意一個符號的概率是1/16，所以每一位能表示 - log2 1/16 = 4 bit。所以1位十六進制的信息量，和4位二進制信息量是相同的。
這樣就比較好理解另一個經典的例子，英文有26個字母，假設每個字母出現的概率是一樣的，每個字母的信息量就是 - log2 1/26 = 4.7；常用的漢字有2500個，每個漢字的信息量是 - log2 1/2500 = 11.3。所以在信息量相同的情況下，使用的漢字要比英文字母要少——這其實就是十六進制和二進制的區別，在這個例子中，apple成了5位26進制的數值，信息量4.7 * 5 = 23.5；而蘋果成為2位2500進制的數值，信息量11.3 * 2 = 22.6。雖然表示的方式不同，但信息量差不多（這是一個很巧合的例子，僅用于說明信息量的含義，大多數詞語都不會這么接近）。
在實際的情況中，每種可能情況出現的概率并不是相同的，所以熵（entropy）就用來衡量整個系統的平均信息量，其計算公式如下

熵是平均信息量，也可以理解為不確定性。例如進行決賽的巴西和南非，假設根據經驗判斷，巴西奪冠的幾率是80%，南非奪冠的幾率是20%，則誰能獲得冠軍的信息量就變為 - 0.8 * log2 0.8 - 0.2 * log2 0.2 = 0.257 + 0.464 = 0.721，小于1 bit了。經驗減少了判斷所需的信息量，消除了不確定性。
而且通過計算可以發現，巴西奪冠的幾率越高，計算出的熵就越小，即越是確定的情況，不確定性越小，信息量越少。如果巴西100%奪冠，那么熵是0，相當于沒有任何信息。當兩隊幾率都是50%最難判斷，所熵達到最大值1。其實之前的?- log2 1/2 = 1 bit 是簡化了的計算過程，其結果也是通過熵的公式來計算的?- 0.5 * log2 0.5 - 0.5 * log2 0.5 = 1 bit，計算信息量要綜合考慮每種結果的可能性。
另一個會迷惑的問題是熵會大于1嗎？答案當然是肯定的，剛剛計算的最大值為1bit，是因為最終的結果只有兩種情況。在有四支球隊的時候，其最大值就是 - 0.25 * log2 0.25?- 0.25 * log2 0.25?- 0.25 * log2 0.25?- 0.25 * log2 0.25 = 2 bit，當四支球隊奪冠概率不等的時候，熵會小于2 bit。
數據挖掘分類問題中構建決策樹的算法ID3和C4.5，就是對熵的一個典型的應用。 以經典的根據天氣判斷是否打高爾夫球的例子來說明

@relation weather.symbolic@attribute outlook {sunny, overcast, rainy} @attribute temperature {hot, mild, cool} @attribute humidity {high, normal} @attribute windy {TRUE, FALSE} @attribute play {yes, no}@data sunny,hot,high,FALSE,no sunny,hot,high,TRUE,no overcast,hot,high,FALSE,yes rainy,mild,high,FALSE,yes rainy,cool,normal,FALSE,yes rainy,cool,normal,TRUE,no overcast,cool,normal,TRUE,yes sunny,mild,high,FALSE,no sunny,cool,normal,FALSE,yes rainy,mild,normal,FALSE,yes sunny,mild,normal,TRUE,yes overcast,mild,high,TRUE,yes overcast,hot,normal,FALSE,yes rainy,mild,high,TRUE,no

因為最終的結果只有yes和no兩種，判斷是否打高爾夫球所需的信息量（熵、不確定性）是1 bit。構建決策樹的過程就是通過各種天氣特征，來消除不確定性（使熵減少）。
在選擇分裂屬性之前會計算一個初始的熵，但這個值卻不是剛才提到的1。因為在只知道Class Label的情況下，是有一些經驗上的信息的。如訓練集中，有9個yes和5個no，這就好比我們知道在兩隊的交手記錄中巴西獲勝過幾次，所以由此可以推算出現yes的概率是9/14，出現no的概率是5/14。所以初始的熵為 H-init = ?- 9/14 * log2 9/14 - 5/14 * log2 5/14 = 0.94。
屬性是如何使熵減少的呢？假設我們選取的是outlook，則通過這個屬性可以將訓練集劃分成3個集合

sunny,hot,high,FALSE,no sunny,hot,high,TRUE,no sunny,mild,high,FALSE,no sunny,cool,normal,FALSE,yes sunny,mild,normal,TRUE,yesovercast,hot,high,FALSE,yes overcast,cool,normal,TRUE,yes overcast,mild,high,TRUE,yes overcast,hot,normal,FALSE,yesrainy,mild,high,FALSE,yes rainy,cool,normal,FALSE,yes rainy,cool,normal,TRUE,no rainy,mild,normal,FALSE,yes rainy,mild,high,TRUE,no

某些子集在分割后變得更加純凈了，如當 outlook = overcast 的時候，全部為yes，該子集的熵為0，使得總體的熵（各個子集熵的平均值）減少。 H-sunny = - 0.4 * log2 0.4 - 0.6 * log2 0.6 = 0.971 H-overcast = - 1 * log2 1 - 0 = 0 H-rainy =?- 0.6 * log2 0.6?- 0.4 * log2 0.4 = 0.971 H-average = 0.971 * 5 / 14 + 0 * 4 / 14 + 0.971 * 5 / 14 = 0.694
初始熵與分割后的總體熵的差值，就是信息增益 InfoGain = H-init - H-average = 0.94 - 0.694 = 0.246 相當于獲得了有用的信息，使判斷出結果所需的信息量減少了。所以ID3算法在每次分割時，都選取信息增益最大的屬性，這樣使用最少的分支判斷就可以得到最終的結果。
熵表示不確定性，可以衡量混亂程度或純凈度，因此也用作分類或聚類結果的評價標準。類似地，在得到了所劃分的n個集合后，分別計算每個集合的熵，公式中的n為集合中類別的個數，pi為第i個類別在該集合中出現的概率。如集合中有4個元素，分別屬于4個類別，那么這個集合的熵就是2。之后計算各個集合熵的加權平均值，即是整個劃分結果的熵。同理，熵越低表示劃分得越準確。

參考文章：http://gaofeihang.blog.163.com/blog/static/8450828520128139648199/

關于決策樹算法的詳細介紹，推薦：http://www.cnblogs.com/leoo2sk/archive/2010/09/19/1831151.html?

感謝吳軍老師所著的《數學之美》對我的啟發

總結

以上是生活随笔為你收集整理的信息熵与分类算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。