[ML] Random Forest

終於來到我最喜歡的演算法 - Random Forest

會喜歡的原因是, 他簡單, 直觀, 當然前提是你要知道甚麼是 Tree

在看 Random Forest 之前最好先去了解一下 Tree, Link: Decision Tree, Link: CART

假設你已經知道甚麼是 Tree, 那你也差不多沒幾步就可以完成 Random Forest 了!!

在這之前先聽個故事...

ptt 最喜歡惡搞的一個故事就是, 父親給兒子筷子, 然後一根很容易折斷

兩根很容易折斷, 三根也很容易折斷...嗯...這兒子力量好強!!

這應該叫他 SVM, 因為超強的XDDD

如果今天變成是, 給到第三跟筷子兒子折不斷, 那這時候就要跟他講團結的力量大XD

其實 Random Forest 就是團結的力量 !!

用一句話描述 Random Forest:

Random Forest 基本概念就是先 build 多棵 Decision Tree, 然後集合這些 Tree 的力量為一個 Forest, 再來做預測

打完收工~~大~家~可~以~回~家~了!!

當然...事情永遠不會那麼單純XD

Random Forest

事實上, 跟前述的東西差不多, Random Forest 的確就差不多這些東西構成的

只是有些東西要來細部的探討一下

首先是來歷: 由 Leo Breiman and Adele Cutler 在 2001 年發表在 Machine Learning Journal !!

官網: http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm

原始 paper: http://oz.berkeley.edu/~breiman/randomforest2001.pdf

如果英文不錯的其實官網就已經教學得很清楚了, 我只是用我自己的理解重新描述

因為 Random Forest 我從來沒有在 ML 課學過, 完全是自學的

那來把最上述的一句話我稍微展開一點:

在 training data 中, 從中取出一些 feature & 部份 data 產生出 Tree (通常是CART)

並且重複這步驟多次, 會產生出多棵 Tree 來

最後利用 Ensemble (Majority Vote) 的方法, 結合所有 Tree, 就完成了 Random Forest

首先故事是這樣的 Random Forest 其實是靠底下的 Tree 建立而成的

而這些 Tree 的差異就是在組成所用的 data 跟 feature 都有點不一樣

所以我們先從準備 training data 開始

Bootstrap

首先要建立一棵 Tree, 不會用全部的 training data 去 training 一棵 Tree

我們為甚麼不用全部的 training data 餵進去就好?

如果全部都餵的話, 那我不管建立幾棵 Tree, 結果都是一樣的, 那我乾脆就只要一棵就好了~

所以為了讓每棵有所不同, 主要就是 training data 的採樣結果都會不太一樣

這邊採樣的方式就是 Bagging

---

Bagging

一種採樣方式, 假設全體 training data 有N筆, 你要採集部分資料, 

但是又不想要採集到全體的資料 (那就不叫採集了), 要如何做?

一般常見的方式為: 從 N 筆 data 挑資料, 一次挑一筆, 挑出的會再放回去, 最後計算的時候重複的會不算(with replacement), 假設最後為y, N > y

那 y 就是一次標準的 bagging sampling 樣本數, 當然也有人不 replacement, 但是較少人使用

wiki: http://www.wikipedia.com/wiki/Bootstrap_aggregating

---

那因為是用 bagging on data, 所以每棵 Tree 在建立的時候, 都會是用不一樣的 data 去建立的

除了 data 之外, 還有 feature, Random Forest 另外一個特點, 不只是 data 用 bagging

甚至是 feature 也是bagging 的方式, 也就是連使用哪些 feature 去建立 Tree, 都是不固定的
(所以感覺到那股 Random 了沒有阿~~~)

等於說, Random Forest 所建立的每棵 Tree, 在 data 跟 feature 上, 都有一定程度上的不同

那其實這樣的結果會有一個狀況, 假設建立出 10 棵 Tree,

有的 Tree 很多 Node, 有的 Tree 很少, 有的很 skew, 有的很 wide

在 '08 年有一篇 paper, 探討 feature 的數量到底要如何決定, 不然差異太大, 可能結果會不甚良好

Link: http://hal.archives-ouvertes.fr/docs/00/43/63/67/PDF/icic08.pdf

那我個人實驗目前比較採用的方式是:

設定最少要 bagging 出 (k / 2) + 1 的 feature, 才比較有顯著結果, K 為原本的 feature 數量

或者另外一個常見設定是 square(k)

當然, feature 太少的當然就不太適合這樣做, square 的方式則是最好有夠多的 feature

Build Tree

這邊, 就沒什麼好說的了, 只要將前述的 data & feature 準備好, 餵入 CART 就可以了

唯一要注意的事情, Random Forest 不須要讓任何的 Tree 做 prune

Ensemble

最後一個步驟, 假設你 training 了 50 棵 Tree, 最後就是合體

團結的力量是吧, 使用方式當然也就很單純, 給我一筆 data

我會讓這 50 棵 Tree 分別去預估可能的 class, 最後全體投票, 多數決決定

如果今天是用 Regression 的 RF, 則是加總起來除以總棵數, 就是預估的答案

Out Of Bag

那要如何衡量可能的錯誤率? 可以這麼做

因為重複採樣的關係, 平均來講, 每棵大約會有 1/3 training data 採樣不到

所以收集這些 data, 最後等到 Forest 建立完成之後, 將這些 data 餵進去判斷, 最後得出錯誤率

這方式稱為 Out-Of-Bag (OOB)

其實 Random Forest 是一個很 heuristic 的演算法

他還有很多需要被決定的參數, 像是, 我到底要用幾棵樹

well, 笨一點的方式就是從 1棵, 2棵...到 n 棵, 棵一路建立上去

然後計算他相對的 OOB, 要是發現 OOB 沒在下降, 那就差不多了

不過不保證好用XD

那有 paper 探討幾棵 Tree 比較實用, 可以參考下列這篇

How Many Trees in a Random Forest?

http://link.springer.com/chapter/10.1007%2F978-3-642-31537-4_13

可惜這要錢, 有學術網路的人可以參考這篇

---

那其實 Random Forest 在近代真的是很好用的演算法

當然他變形也相當多, 有一個比 Random Forest 還要更 Random 的演算法為底下的 Tree 是用Extremely randomized trees 來建構

或者是'09 年有一篇很紅的 paper: Online Random Forest

Link: http://www.vision.ee.ethz.ch/~cleistne/papers/2009-OnlineRandomForests.pdf

這篇我有特別去實作, 效果棒, 不過參數需要選擇的更多, 而且會變成有需要做 prune

有空的話再介紹這篇 Online Random Forest

有時候寫 Blog 我會寫的掉東掉西的, 有錯請多多包涵, 有發現會馬上改正