本文關鍵詞：決策樹模型，由筆耕文化傳播整理發(fā)布。

決策樹模型組合之（在線）隨機森林與GBDT

前言：

決策樹這種算法有著很多良好的特性，比如說訓練時間復雜度較低，預測的過程比較快速，模型容易展示（容易將得到的決策樹做成圖片展示出來）等。但是同時， 單決策樹又有一些不好的地方，比如說容易over-fitting，雖然有一些方法，如剪枝可以減少這種情況，但是還是不夠的。

模型組合（比如說有Boosting，Bagging等）與決策樹相關的算法比較多，這些算法最終的結果是生成N(可能會有幾百棵以上）棵樹，這樣可以大 大的減少單決策樹帶來的毛病，有點類似于三個臭皮匠等于一個諸葛亮的做法，雖然這幾百棵決策樹中的每一棵都很簡單（相對于C4.5這種單決策樹來說），但 是他們組合起來確是很強大。

基礎內容：

這里只是準備簡單談談基礎的內容，主要參考一下別人的文章，對于隨機森林與GBDT，有兩個地方比較重要，首先是information gain，其次是決策樹。這里特別推薦Andrew Moore大牛的Decision Trees Tutorial，與Information Gain Tutorial。Moore的Data Mining Tutorial系列非常贊，看懂了上面說的兩個內容之后的文章才能繼續(xù)讀下去。

決策樹實際上是將空間用超平面進行劃分的一種方法，每次分割的時候，都將當前的空間一分為二，比如說下面的決策樹：

就是將空間劃分成下面的樣子：

這樣使得每一個葉子節(jié)點都是在空間中的一個不相交的區(qū)域，在進行決策的時候，會根據輸入樣本每一維feature的值，一步一步往下，最后使得樣本落入N個區(qū)域中的一個（假設有N個葉子節(jié)點）

隨機森林(Random Forest):

隨機森林是一個最近比較火的算法，它有很多的優(yōu)點：

隨機森林顧名思義，是用隨機的方式建立一個森林，森林里面有很多的決策樹組成，隨機森林的每一棵決策樹之間是沒有關聯(lián)的。在得到森林之后，當有一個新的輸 入樣本進入的時候，就讓森林中的每一棵決策樹分別進行一下判斷，看看這個樣本應該屬于哪一類（對于分類算法），，然后看看哪一類被選擇最多，就預測這個樣本 為那一類。

在建立每一棵決策樹的過程中，有兩點需要注意 - 采樣與完全分裂。首先是兩個隨機采樣的過程，random forest對輸入的數據要進行行、列的采樣。對于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復的樣本。假設輸入樣本為N個，那 么采樣的樣本也為N個。這樣使得在訓練的時候，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現(xiàn)over-fitting。然后進行列采樣，從M 個feature中，選擇m個(m << M)。之后就是對采樣之后的數據使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節(jié)點要么是無法繼續(xù)分裂的，要么里面的所有樣本的都是指向的同一 個分類。一般很多的決策樹算法都一個重要的步驟 - 剪枝，但是這里不這樣干，由于之前的兩個隨機采樣的過程保證了隨機性，所以就算不剪枝，也不會出現(xiàn)over-fitting。

按這種算法得到的隨機森林中的每一棵都是很弱的，但是大家組合起來就很厲害了。我覺得可以這樣比喻隨機森林算法：每一棵決策樹就是一個精通于某一個窄領域 的專家（因為我們從M個feature中選擇m讓每一棵決策樹進行學習），這樣在隨機森林中就有了很多個精通不同領域的專家，對一個新的問題（新的輸入數 據），可以用不同的角度去看待它，最終由各個專家，投票得到結果。

隨機森林的過程請參考Mahout的random forest 。這個頁面上寫的比較清楚了，其中可能不明白的就是Information Gain，可以看看之前推薦過的Moore的頁面。

Gradient Boost Decision Tree:

GBDT是一個應用很廣泛的算法，可以用來做分類、回歸。在很多的數據上都有不錯的效果。GBDT這個算法還有一些其他的名字，比如說MART(Multiple Additive Regression Tree)，GBRT(Gradient Boost Regression Tree)，Tree Net等，其實它們都是一個東西（參考自wikipedia – Gradient Boosting)，發(fā)明者是Friedman

Gradient Boost其實是一個框架，里面可以套入很多不同的算法，可以參考一下機器學習與數學(3)中的講解。Boost是"提升"的意思，一般Boosting算法都是一個迭代的過程，每一次新的訓練都是為了改進上一次的結果。

原始的Boost算法是在算法開始的時候，為每一個樣本賦上一個權重值，初始的時候，大家都是一樣重要的。在每一步訓練中得到的模型，會使得數據點的估計 有對有錯，我們就在每一步結束后，增加分錯的點的權重，減少分對的點的權重，這樣使得某些點如果老是被分錯，那么就會被“嚴重關注”，也就被賦上一個很高 的權重。然后等進行了N次迭代（由用戶指定），將會得到N個簡單的分類器（basic learner），然后我們將它們組合起來（比如說可以對它們進行加權、或者讓它們進行投票等），得到一個最終的模型。

而Gradient Boost與傳統(tǒng)的Boost的區(qū)別是，每一次的計算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度(Gradient)方向上建立一個新的模型。所以說，在Gradient Boost中，每個新的模型的簡歷是為了使得之前模型的殘差往梯度方向減少，與傳統(tǒng)Boost對正確、錯誤的樣本進行加權有著很大的區(qū)別。

在分類問題中，有一個很重要的內容叫做Multi-Class Logistic，也就是多分類的Logistic問題，它適用于那些類別數>2的問題，并且在分類結果中，樣本x不是一定只屬于某一個類可以得到 樣本x分別屬于多個類的概率（也可以說樣本x的估計y符合某一個幾何分布），這實際上是屬于Generalized Linear Model中討論的內容，這里就先不談了，以后有機會再用一個專門的章節(jié)去做吧。這里就用一個結論：如果一個分類問題符合幾何分布，那么就可以用Logistic變換來進行之后的運算。

假設對于一個樣本x，它可能屬于K個分類，其估計值分別為F1(x)…FK(x)，Logistic變換如下，logistic變換是一個平滑且將數據規(guī)范化（使得向量的長度為1）的過程，結果為屬于類別k的概率pk(x)，

對于Logistic變換后的結果，損失函數為：

其中，yk為輸入的樣本數據的估計值，當一個樣本x屬于類別k時，yk = 1，否則yk = 0。

將Logistic變換的式子帶入損失函數，并且對其求導，可以得到損失函數的梯度：

上面說的比較抽象，下面舉個例子：

假設輸入數據x可能屬于5個分類（分別為1,2,3,4,5），訓練數據中，x屬于類別3，則y = (0, 0, 1, 0, 0)，假設模型估計得到的F(x) = (0, 0.3, 0.6, 0, 0)，則經過Logistic變換后的數據p(x) = (0.16,0.21,0.29,0.16,0.16)，y - p得到梯度g：(-0.16, -0.21, 0.71, -0.16, -0.16)。觀察這里可以得到一個比較有意思的結論：

假設gk為樣本當某一維（某一個分類）上的梯度:

gk>0時，越大表示其在這一維上的概率p(x)越應該提高，比如說上面的第三維的概率為0.29，就應該提高，屬于應該往“正確的方向”前進

越小表示這個估計越“準確”

gk<0時，越小，負得越多表示在這一維上的概率應該降低，比如說第二維0.21就應該得到降低。屬于應該朝著“錯誤的反方向”前進

越大，負得越少表示這個估計越“不錯誤 ”

總的來說，對于一個樣本，最理想的梯度是越接近0的梯度。所以，我們要能夠讓函數的估計值能夠使得梯度往反方向移動（>0的維度上，往負方向移動，<0的維度上，往正方向移動）最終使得梯度盡量=0），并且該算法在會嚴重關注那些梯度比較大的樣本，跟Boost的意思類似。

得到梯度之后，就是如何讓梯度減少了。這里是用的一個迭代+決策樹的方法，當初始化的時候，隨便給出一個估計函數F(x)（可以讓F(x)是一個隨機的值，也可以讓F(x)=0），然后之后每迭代一步就根據當前每一個樣本的梯度的情況，建立一棵決策樹。就讓函數往梯度的反方向前進，最終使得迭代N步后，梯度越小。

這里建立的決策樹和普通的決策樹不太一樣，首先，這個決策樹是一個葉子節(jié)點數J固定的，當生成了J個節(jié)點后，就不再生成新的節(jié)點了。

算法的流程如下:（參考自treeBoost論文）

0. 表示給定一個初始值

1. 表示建立M棵決策樹（迭代M次）

2. 表示對函數估計值F(x)進行Logistic變換

3. 表示對于K個分類進行下面的操作（其實這個for循環(huán)也可以理解為向量的操作，每一個樣本點xi都對應了K種可能的分類yi，所以yi, F(xi), p(xi)都是一個K維的向量，這樣或許容易理解一點）

4. 表示求得殘差減少的梯度方向

5. 表示根據每一個樣本點x，與其殘差減少的梯度方向，得到一棵由J個葉子節(jié)點組成的決策樹

6. 為當決策樹建立完成后，通過這個公式，可以得到每一個葉子節(jié)點的增益（這個增益在預測的時候用的）

每個增益的組成其實也是一個K維的向量，表示如果在決策樹預測的過程中，如果某一個樣本點掉入了這個葉子節(jié)點，則其對應的K個分類的值是多少。比如 說，GBDT得到了三棵決策樹，一個樣本點在預測的時候，也會掉入3個葉子節(jié)點上，其增益分別為（假設為3分類的問題）：

(0.5, 0.8, 0.1),  (0.2, 0.6, 0.3),  (0.4, 0.3, 0.3)，那么這樣最終得到的分類為第二個，因為選擇分類2的決策樹是最多的。

7. 的意思為，將當前得到的決策樹與之前的那些決策樹合并起來，作為新的一個模型(跟6中所舉的例子差不多)

GBDT的算法大概就講到這里了，希望能夠彌補一下上一篇文章中沒有說清楚的部分：）

實現(xiàn)：

看明白了算法，就需要去實現(xiàn)一下，或者看看別人實現(xiàn)的代碼，這里推薦一下wikipedia中的gradient boosting頁面，下面就有一些開源軟件中的一些實現(xiàn)，比如說下面這個：

參考資料：

除了文章中的引用的內容（已經給出了鏈接）外，主要還是參考Friedman大牛的文章：Greedy function approximation : A Gradient Boosting Machine

本文由LeftNotEasy發(fā)布于, 本文可以被全部的轉載或者部分使用，但請注明出處，如果有問題，請聯(lián)系wheeleast@gmail.com

=========================================

cvchina上的《online random forest》

一直忽悠cvchina，心有歉意。第一次發(fā)文，簡單寫點online learning的東西。

傳統(tǒng)的SVM和adaboost都是batch mode learning. 所謂的batch mode learning， 簡單說，就是所有的訓練數據都是available的（或則說所有訓練數據都已經在內存中）。這種方法主要有2個缺點：

1）  有時候數據量太大，在內存中放不下，處理起來不方便

2）  由于應用環(huán)境限制，有時候無法在訓練之前得到所有訓練數據

而Online learning， 他的數據是come in sequence，也就是說traning sample 是一個一個來，或則是幾個幾個來，然后classifer 根據新來的samples進行更新。Online learning是比較困難的，主要原因是你無法知道將來的訓練數據是如何的。顯然adaboost和svm是行不通的。最近幾年也有一些人做 online learning的研究，主要方法還是集中在online boosting這一塊。推薦2篇不錯的文章：

1）  online adaboost [1], 并把他用在object tracking等方面。這篇文章發(fā)表于CVPR2006引用率蠻高。這幾年的cvpr上的幾篇做tracking的文章以這個idea為基礎。 tracking的方法是用最近比較流行的tracking-by-detection的方法。簡答的說就是在tracking的時 候，observation model這一塊是用一個在線訓練的分類器。tracking的過程如下圖所示（圖中還有一步是用跟蹤的結果作為訓練器的新的輸入）：

這篇文章online 訓練的時候，用tracking 的結果作為online classifier的positive samples。顯然這種數據是有噪聲的，最后tracking會drift掉。而且需要指出的是，這種方法沒有嚴格證明，只是模仿batch mode adaboost. 我把這個算法用在uci的訓練數據上，效果不是很好。作者的主頁是：~hegrabne/. 這個是他用online learning 做tracking的項目主頁：。 有現(xiàn)成代碼和demo。

2）  去年的一篇論文是關于online random forest[2]。網上有現(xiàn)成的代碼。我跑了一下，挺牛逼的，效果沒比offline mode差不多。如果你需要做online learning的話十分推薦。

[1].On-line Boosting and Vision. 06CVPR.

[2]. Online random forest. 09ICCV workshop on online machine learning.

PS：code的原始鏈接失效了，我傳了一份到mediafire。丕子發(fā)現(xiàn)mediafirm也被墻了，NND，所以自己上傳了一份弄到微盤里面了：

分享代碼，難得下到的。Online random forest. 09ICCV workshop on online machine learning.通過@微盤 分享文件"OnlineForest-0.11.tar.gz" 

posted on

  本文關鍵詞：決策樹模型，由筆耕文化傳播整理發(fā)布。