iT邦幫忙

DAY 15
0

Data Mining 學習路:概念、技術與工具系列 第 15

將資料化為資訊:Divide and Conquer - Decision Trees(2/2)

# information entropy 要怎麼算?

基本的公式在此:

ps.1 Pn 表示 個別分類結果的占總數量有多少
ps.2 通常 log 以 2 為底

ex. info([2,3,4]) = entropy(2/9, 3/9, 4/9) = -2/9 x log(2/9) - 3/9 x log(3/9) - 4/9 x log(4/9)
關於這個的原理什麼的,自己去 Google 吧(數學苦手表示難過 Orz)

而計算分支總 info = 個別 info 乘上個別所占的比例(有點像期望值 :o)
info([2,3], [4,0], [3,2]) = (5/14) x info([2,3]) + (4/14) x info([4,0]) + (5/14) x info([3,2])

information entropy 的計算上有三個性質:

  1. 如果有分類結果為 0 的,info 值就會是 0。例如上面的 info([4,0]) = 0 bits
  2. 分類結果數量相等時,info 會有最大值
  3. multistage property

前面兩個應該很好懂,至於什麼是 multistage property 勒?
簡單來說就是,分類這回事其實是可以層層進行的。
例如我們有個分類結果為 [2,3,4],被分成三個類別,當我們在分類的時候其實可以看成兩個步驟
第一次分類 [2,7]
第二次分類 [2,3,4]
於是我們計算 info([2,3,4]) 時,事實上是在做這個運算:
info([2,3,4]) = info(2,7) + (7/9) x info([3,4])
為什麼會這樣??改天再說吧......

真的在計算的時候拿 log 那個公式做就好了 :p

當樹的分支太細碎時:Gain Ratio

information entropy 提供了我們一個客觀的標準來決定決策樹的分支屬性,然而他有一個缺點,就是在分支的屬性造成太多分支時,我們會得到一個合理但卻讓決策樹的分類產生問題的結果。
假設我們拿上面資料的 Day ID 作為節點分支的依據,會產生高達 14 個分支,我們計算個別分支的總 info 值時,會得到 0:

info([0,1]) + info([0,1]) + info([1,0]) + ... + info([0,1]) = 0

這時的 gain(Day ID) 就會等於 info([9,5]) = 0.940 bits
( gain(root) = info(root) - info(branches) and info(branches) is 0 now )

gain(Day ID) 非常大,遠大過於先前計算的四個屬性的 gain 值,這樣的話我們是不是應該拿 Day ID 作為節點的分類依據呢?很明顯如果我們拿了 Day ID 作為分類的依據,當有一個未知的新資料要做分類時,就會造成分類上的問題。

這時我們就會需要 gain ratio 的概念,簡單來說就是把分支的數量也加入考慮,使我們在選取分類依據時能更加的準確客觀。
以 Day ID 做依據時,總共會產生 14 個分支,每個分支下僅有一個分類,則這個分支的 info 值為
info([1,1,1,1,...,1]) = -1/14 x log(1/14) x 14 = 3.807 bits
因為分支的數量相當多,所以他的 info 值也相當的大。

接著我們就可以求出 gain ratio ,直接把原本的 info 值除以分支數量的 info 值:
0.940 / 3.807 = 0.247

試著計算 outlook 分支數量的 info:
info([5,4,5]) = 1.577 (分支數量為 5,4,5)
這時可得 outlook 的 gain ratio
0.247 / 1.577 = 0.156

在這個範例中,Day ID 的 gain ratio 仍然高於其他四個屬性的 gain ratio,但他們的差距已經小很多,在實際的應用上我們可以透過隨機測試 (ad hoc test,請參考下方連結)來剔除那些沒用的屬性,換句話說就是要多多嘗試啦,不要相信單一的結果...

決策樹相關研究

John Ross Quinlan 是一位在決策樹的演算法上有相當成果的一位科學家,他發明了一些很有名的算法像是 ID3, C4.5 等,有興趣的人可以自己去查查看 ...
附上 C4.5 algorithm 的聯結
http://en.wikipedia.org/wiki/C4.5\_algorithm

References

[資訊的度量 - Information Entropy](http://blog.xuite.net/metafun/life/69851478-%E8%B3%87%E8%A8%8A%E7%9A%84%E5%BA%A6%E9%87%8F-+Information+Entropy)
[Entropy](http://episte.math.ntu.edu.tw/articles/mm/mm\_13\_3\_01/)
[information entropy 在 wiki 上的介紹](http://en.wikipedia.org/wiki/Entropy\_%28information\_theory%29)
[ad hoc test](http://blog.csdn.net/wayne\_ran/article/details/2030915)


上一篇
將資料化為資訊:Divide and Conquer - Decision Trees (1/2)
下一篇
將資料化為資訊:Statistical Modelling - Naïve Bayes Classifier(1/3)
系列文
Data Mining 學習路:概念、技術與工具16

尚未有邦友留言

立即登入留言