機器學習之整合學習
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

一、整合演算法(Ensemble Algorithms)綜述

嚴格意義上來說,這不算是一種機器學習演算法,而更像是一種優化手段或者策略,它通常是結合多個簡單的弱機器學習演算法,去做更可靠的決策。有人把它稱為機器學習中的“屠龍刀”,非常萬能且有效,整合模型是一種能在各種的機器學習任務上提高準確率的強有力技術,整合演算法往往是很多資料競賽關鍵的一步,能夠很好地提升演算法的效能。哲學思想為“三個臭皮匠賽過諸葛亮”。拿分類問題舉個例,直觀的理解,就是單個分類器的分類是可能出錯,不可靠的,但是如果多個分類器投票,那可靠度就會高很多。

現實生活中,我們經常會通過投票,開會等方式,以做出更加可靠的決策。整合學習就與此類似。整合學習就是有策略的生成一些基礎模型,然後有策略地把它們都結合起來以做出最終的決策。整合學習又叫多分類器系統。

整合方法是由多個較弱的模型整合模型組,一般的弱分類器可以是DT, SVM, NN, KNN等構成。其中的模型可以單獨進行訓練,並且它們的預測能以某種方式結合起來去做出一個總體預測。該演算法主要的問題是要找出哪些較弱的模型可以結合起來,以及如何結合的方法。這是一個非常強大的技術集,因此廣受歡迎。

整合演算法家族強大,思想多樣,但是好像沒有同一的術語,很多書本上寫得也不一樣, 不同的學者有不同的描述方式,最常見的一種就是依據整合思想的架構分為 Bagging ,Boosting, Stacking三種。國內,南京大學的周志華教授對整合學習有深入的研究,其在09年發表的一篇概述性論文《Ensemple Learning》(https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/springerEBR09.pdf)對這三種架構做出了明確的定義。

演算法鳥瞰

Bagging:基於資料隨機重抽樣的分類器構建方法。從訓練集從進行子抽樣組成每個基模型所需要的子訓練集,對所有基模型預測的結果進行綜合產生最終的預測結果。

這裡寫圖片描述

Boosting:訓練過程為階梯狀,基模型按次序一一進行訓練(實現上可以做到並行),基模型的訓練集按照某種策略每次都進行一定的轉化,每次都是提高前一次分錯了的資料集的權值,最後對所有基模型預測的結果進行線性組合產生最終的預測結果。

這裡寫圖片描述

Stacking:將訓練好的所有基模型對訓練基進行預測,第j個基模型對第i個訓練樣本的預測值將作為新的訓練集中第i個樣本的第j個特徵值,最後基於新的訓練集進行訓練。同理,預測的過程也要先經過所有基模型的預測形成新的測試集,最後再對測試集進行預測:
這裡寫圖片描述

Stacking演算法分為2層,第一層是用不同的演算法形成T個弱分類器,同時產生一個與原資料集大小相同的新資料集,利用這個新資料集和一個新演算法構成第二層的分類器。
以上圖片來自使用sklearn進行整合學習——理論@jasonfreak
http://www.cnblogs.com/jasonfreak/p/5657196.html

常用的模型融合增強方法

  • Bagging (Bootstrapped Aggregation)
  • Random Forest
  • Boosting
  • AdaBoost (Adaptive Boosting)
  • Gradient Boosting Machines (GBM)梯度推進機
  • Gradient Boosted Regression Trees (GBRT)梯度提升迴歸樹
  • Stacked Generalization (blending)層疊泛化

二、關於基礎分類器結果整合的主要方式

1. 對於迴歸預測(數值預測)

簡單平均(Simple Average),就是取各個分類器結果的平均值。

G(x)=1T∑t=1Tgt(x)” role=”presentation”>G(x)=1T∑t=1Tgt(x)G(x)=1T∑t=1Tgt(x)

G(x)=\frac{1}{T}\sum\limits{t=1}^{T}{{{g}{t}}}(x)

加權平均(Weighted Average)。

G(x)=1T∑t=1Tαt⋅gt(x),αt≥0″ role=”presentation”>G(x)=1T∑t=1Tαt⋅gt(x),αt≥0G(x)=1T∑t=1Tαt⋅gt(x),αt≥0

G(x)=\frac{1}{T}\sum\limits{t=1}^{T}{{{\alpha }{t}}}\cdot {{g}{t}}(x), {{\alpha }{t}}\ge 0

2. 對於分類(類別預測)

簡單投票(Majority Voting):就是每個分類器的權重大小一樣,少數服從多數,類別得票數超過一半的作為分類結果

G(x)=sign(∑t=1T1⋅gt(x))” role=”presentation”>G(x)=sign(∑t=1T1⋅gt(x))G(x)=sign(∑t=1T1⋅gt(x))

G(x)=sign\left( \sum\limits{t=1}^{T}{1}\cdot {{g}{t}}(x) \right)

加權投票(Weighted Majority Voting):每個分類器權重不一。

G(x)=sign(∑t=1Tαt⋅gt(x)),αt≥0″ role=”presentation”>G(x)=sign(∑t=1Tαt⋅gt(x)),αt≥0G(x)=sign(∑t=1Tαt⋅gt(x)),αt≥0

G(x)=sign\left( \sum\limits{t=1}^{T}{{{\alpha }{t}}}\cdot {{g}{t}}(x) \right),{{\alpha }{t}}\ge 0

概率投票(Soft vote):有的分類器的輸出是有概率資訊的,因此可用概率投票。

整合學習的關鍵有兩點:

  • 如何構建具有差異性的分類器;
  • 如何多這些分類器的結果進行整合。

基學習器之間的效能要有較大的差別,否則整合效果會很不好,也就是要保證多樣性(Diversity),基學習器可以是DT, SVM, NN, KNN等,也可以是訓練過程不同的同一種模型,例如不同的引數,不同的訓練集,或者不同的特徵選擇等。

3、Bootstrap演算法

Bootstrap方法是非常有用的一種統計學上的估計方法。 Bootstrap是一類非參Monte Carlo方法,其實質是對觀測資訊進行再抽樣,進而對總體的分佈特性進行統計推斷。首先,Bootstrap通過重抽樣,避免了Cross-Validation造成的樣本減少問題,其次,Bootstrap也可以創造資料的隨機性。Bootstrap是一種有放回的重複抽樣方法,抽樣策略就是簡單的隨機抽樣。

(1)、基於Bootstrap 的Bagging 演算法

Bagging(Bootstrapped Aggregation的簡稱)對於給定資料處理任務,採用不同的模型、引數、特徵訓練出多個模型,最後採用投票或者加權平均的方式輸出最終結果。基學習器可以是相同的模型,也可以是不同的,一般使用的是同一種基學習器,最常用的是DT決策樹。

Bagging通過對原資料集進行有放回的取樣構建出大小和原資料集D一樣的新資料集D1,D2,D3…..,然後用這些新的資料集訓練多個分類器g1,g2,g3….。因為是有放回的取樣,所以一些樣本可能會出現多次,而有些樣本會被忽略,理論上新的樣本會包含67%的原訓練資料。

Bagging通過降低基分類器的方差改善了泛化能力,因此Bagging的效能依賴於基分類器的穩定性,如果基分類器是不穩定的,Bagging有助於降低訓練資料的隨機擾動導致的誤差,但是如果基分類器是穩定的,即對資料變化不敏感,那麼bagging方法就得不到效能的提升。

演算法流程如下:
這裡寫圖片描述

(2)基於Bagging的Random Forest

隨機森林(Random Forest)是許多決策樹的平均,每個決策樹都用通過Bootstrap的方式獲得隨機樣本訓練。森林中的每個獨立的樹都比一個完整的決策樹弱,但是通過將它們結合,可以通過多樣性獲得更高的整體表現。

隨機森林會首先生成許多不同的決策樹,每棵樹變數的個數可以為K” role=”presentation”>K−−√K\sqrt{K}(K” role=”presentation”>KKK為可用變數的個數),這樣能夠顯著的加速模型的訓練速度。一般的基礎分類器的個數為500棵或者可以更多。

隨機森林具有Self-testing的特性,因為隨機森林是通過Bootstrap的方式取樣,理論上往往會有大約1/3的原始資料沒有被選中,我們叫做OOB(out of bag),而這部分資料剛好可以用來做測試,類似於Cross-Validation的作用。

隨機森林是當今機器學習中非常流行的演算法。它是一種“叢集智慧”,非常容易訓練(或構建),且它往往表現良好。

隨機森林具有很多的優點:

  • 所有的資料都能夠有效利用,而且不用人為的分出一部分資料來做cross-validation;
  • 隨機森林可以實現很高的精確度,但是隻有很少的引數,而且對於分類和迴歸都適用;
  • 不用擔心過擬合的問題;
  • 不需要事先做特徵選擇,每次只用隨機的選取幾個特徵來訓練樹。

它的缺點是:

  • 相比於其他演算法,其輸出預測可能較慢。

4、Boosting演算法

Boosting(Adaptive Boosting的簡稱),基於錯誤提升分類器效能,通過集中關注被已有分類器分類錯誤的樣本,構建新分類器並整合。其思想為模型每次迭代時通過調整錯誤樣本的損失權重,提升對資料樣本整體的處理精度。

Boosting與Bagging 相比來說最大的區別就是 Boosting是序列的,而Bagging中所有的分類器是可以同時生成的,之間沒有什麼關係,而Boosting中則必須先生成第一個分類器,然後根據第一個分類器的結果生成第二個分類器,依次往後進行。

這裡寫圖片描述

核心思想是通過改變訓練集進行有針對性的學習。通過每次迭代,增加錯誤樣本的權重,減小正確樣本的權重。知錯就改,越來越好。

這裡寫圖片描述

上圖(圖片來自prml p660)就是一個Boosting的過程,綠色的線表示目前取得的模型(模型是由前m次得到的模型合併得到的),虛線表示當前這次模型。每次分類的時候,會更關注分錯的資料,上圖中,紅色和藍色的點就是資料,點越大表示權重越高,看看右下角的圖片,當m=150的時候,獲取的模型已經幾乎能夠將紅色和藍色的點區分開了。

演算法流程如下:

這裡寫圖片描述
增加前邊學錯樣本的權重,減小已經判斷正確的樣本的權重,有點亡羊補牢,知錯就改的意思,進行有針對性的學習。

理論上,Boosting 可以生成任意精確的分類器,而基礎學習器則可以任意弱,只需要比瞎猜好一點就OK~

Bagging 減小方差(variance ),而Boosting減小偏差(bias),關於具體的細節,可以參考知乎網友的解答為什麼說bagging是減少variance,而boosting是減少bias?(https://www.zhihu.com/question/26760839

(1)、基於Boosting的AdaBoost

AdaBoost 是Boosting中最具代表性的演算法。AdaBoost 是一種Boosting方法,與Bagging不同的是,Adaboost中不同的子模型必須是序列訓練獲得,每個新的子模型是都根據已訓練出的模型效能來進行訓練的,而且Boosting演算法中基學習器為弱學習,可以理解為只比隨機猜測好一點,在二分類情況下,正確率略高於0.5即可。

AdaBoost中每個訓練樣本都有一個權重,初始值都為Wi=1/N。Adaboost中每次迭代生成新的子模型使用的訓練資料都相同,但是樣本的權重會不一樣。AdaBoost會根據當前的錯誤率,按照增大錯誤樣本權重,減小正確樣本權重的原則更新每個樣本的權重。不斷重複訓練和調整權重,直到訓練錯誤率或基學習器的個數滿足使用者指定的數目為止。Adaboost的最終結果為每個弱學習器加權的結果。

AdaBoost 優點:

  • 很容易實施
  • 幾乎沒有引數需要調整
  • 不用擔心過擬合

缺點:

  • 公式中的α是區域性最優解,不能保證是最優解
  • 對噪聲很敏感
    這裡寫圖片描述
    這裡寫圖片描述
    Gradient Boosting Machines (GBM)梯度推進機

梯度提升和隨機森林類似,都是由弱決策樹構成的。最大的區別是,在梯度提升中樹是被一個接一個相繼訓練的。每個隨後的樹主要用被先前樹錯誤識別的資料進行訓練。這使得梯度提升更少地集中在容易預測的情況並更多地集中在困難的情況。

Gradient Boost(https://en.wikipedia.org/wiki/Gradient_boosting)與傳統Boost的區別在於每個新的模型是為了使之前的模型的殘差往梯度方向減少。Gradient Boost與傳統的Boost的區別是,每一次的計算是為了減少上一次的殘差(residual),而為了消除殘差,我們可以在殘差減少的梯度(Gradient)方向上建立一個新的模型。所以說,在Gradient Boost中,每個新的模型的建立是為了使得之前模型的殘差往梯度方向減少,與傳統Boost對正確、錯誤的樣本進行加權有著很大的區別。

梯度提升訓練速度也很快且表現非常好。然而,訓練資料的小變化可以在模型中產生徹底的改變,因此它可能不會產生最可解釋的結果。

Gradient Boosted Regression Trees (GBRT)梯度提升迴歸樹

首先應該說明的一點是,這個演算法有很多名字,但其實是一樣的~

  • Gradient Tree Boosting
  • GBRT (Gradient BoostRegression Tree) 梯度提升迴歸樹
  • GBDT (Gradient BoostDecision Tree) 梯度提升決策樹
  • MART (MultipleAdditive Regression Tree) 多決策迴歸樹
  • Tree Net決策樹網路

GBRT也是一種Boosting方法,每個子模型是根據已訓練出的學習器的效能(殘差)訓練出來的,子模型是序列訓練獲得,不易並行化。GBRT基於殘差學習的算,沒有AdaBoost中的樣本權重的概念。GBRT結合了梯度迭代和迴歸樹,準確率非常高,但是也有過擬合的風險。GBRT中迭代的是殘差的梯度,殘差就是目前結合所有得到的訓練器預測的結果與實際值的差值。

GBRT使用非常廣泛的,能分類,能迴歸預測。GBRT是迴歸樹,不是分類樹。其核心就在於,每一棵樹是從之前所有樹的殘差中來學習的。GBRT不是分類樹而是迴歸樹。

決策樹分為迴歸樹和分類樹: 迴歸樹用於預測實數值,如溫度、使用者年齡等 分類樹用於分類標籤值,如天氣情況、使用者性別等。

模型組合 決策樹相關的演算法有兩種比較基本的形式 – 隨機森林與GBDT((Gradient Boost Decision Tree),其他的比較新的模型組合 決策樹的演算法都是來自這兩種演算法的延伸。

演算法流程如下:
這裡寫圖片描述
關於Bagging和Boosting架構下,整合演算法更多細節,包括演算法實現,可以參看Python官網機器學習包整合模組:sk-learn(http://scikit-learn.org/stable/modules/ensemble.html

5、Stacking

Wolpert在1992年的一篇論文(https://www.researchgate.net/publication/222467943_Stacked_Generalization)中對 stacked generalization進行了介紹 , stacked generalization背後的基本思想是使用大量基分類器,然後使用另一種分類器來融合它們的預測,旨在降低泛化誤差。

Stacking 主要分為兩大部分。第一層就是傳統的訓練,訓練出許多小分類器;第二層則是把這些小分類器的輸出重新組合成為一個新的訓練集,訓練出來一個更高層次的分類器,目的就是尋找相應的權重或者它們之間的組合方式。

在訓練第二層分類器時採用各基礎分類器的輸出作為輸入,第二層分類器的作用就是對基礎分類器的輸出進行整合。
這裡寫圖片描述
演算法流程如下:
這裡寫圖片描述

Stacking 就像是 Bagging的升級版,Bagging中的融合各個基礎分類器是相同權重,而Stacking中則不同,Stacking中第二層學習的過程就是為了尋找合適的權重或者合適的組合方式。
值得注意的是,在Stacking的架構下,有一些經常出現的說法如Stacking, Blending , Stacked Generalization 很多文章也沒有明確說明他們之間的關係。

如果不嚴格來區分的話,可以認為堆疊(Stacking),混合(Blending)和層疊泛化(Stacked Generalization)其實是同一種演算法的不同名字罷了。在傳統的整合學習中,我們有多個分類器試圖適應訓練集來近似目標函式。 由於每個分類器都有自己的輸出,我們需要找到一個組合結果的組合機制,可以通過投票(大多數勝利),加權投票(一些分類器具有比其他權力更多的權威),平均結果等。

在堆疊中,組合機制是分類器(0級分類器)的輸出將被用作另一個分類器(1級分類器)的訓練資料,以近似相同的目標函式。基本上,讓1級分類器找出合併機制。

Stacking, Blending and and Stacked Generalization are all the same thing with different names. It is a kind of ensemble learning. In traditional ensemble learning, we have multiple classifiers trying to fit to a training set to approximate the target function. Since each classifier will have its own output, we will need to find a combining mechanism to combine the results. This can be through voting (majority wins), weighted voting (some classifier has more authority than the others), averaging the results, etc.

關於Stacking與Blending更多的細節可以參考 KAGGLE ENSEMBLING GUIDE(https://mlwave.com/kaggle-ensembling-guide/),中文 kaggle比賽整合指南@qjgods(http://blog.csdn.net/a358463121/article/details/53054686

另眼觀世界
最後我們也可以按照林軒田老師課程中的講述來對機器學習整合演算法做一個歸納。整合模型主要分為兩條主線,一條Blending 線,一條 Learning線。Blending 假設我們已經得到了各個基礎分類器 ,learning 主要指我們面對的是一堆資料,需要一邊獲得基礎分類器 ,同時一邊學習融合它們的方法。
這裡寫圖片描述

Blending框架

這裡寫圖片描述

Learning框架
這裡寫圖片描述

當然還有更加複雜一點的,就是整合的整合。

這裡寫圖片描述

模型評價
評價模型優劣的準則有很多。
欠擬合和過擬合是經常出現的兩種情況,簡單的判定方法是比較訓練誤差和測試誤差的關係,當欠擬合時,可以設計更多特徵來提升模型訓練精度,當過擬合時,可以優化特徵量降低模型複雜度來提升模型測試精度。

過擬合與欠擬合
這裡寫圖片描述
這裡寫圖片描述

方差與偏差
機器學習模型的Bias和Variance分析,Understanding the Bias-Variance Tradeoff(http://scott.fortmann-roe.com/docs/BiasVariance.html)中的一副圖生動形象地為我們展示了偏差和方差的關係:


簡單來說,一個模型越複雜,對訓練樣本的擬合度會越高,其Bias會越小(訓練誤差小)。但是,由於對資料過於敏感,生成的模型的變化範圍可能比較大(Variance較大),可能導致在測試資料上效能的不確定性較高。

相關文章

程式語言 最新文章