集成學習演算法
Ⅰ 常見的分類方法
主要分類方法介紹解決分類問題的方法很多[40-42] ，單一的分類方法主要包括：決策樹、貝葉斯、人工神經網路、K-近鄰、支持向量機和基於關聯規則的分類等；另外還有用於組合單一分類方法的集成學習演算法，如Bagging和Boosting等。
（1）決策樹
決策樹是用於分類和預測的主要技術之一，決策樹學習是以實例為基礎的歸納學習演算法，它著眼於從一組無次序、無規則的實例中推理出以決策樹表示的分類規則。構造決策樹的目的是找出屬性和類別間的關系，用它來預測將來未知類別的記錄的類別。它採用自頂向下的遞歸方式，在決策樹的內部節點進行屬性的比較，並根據不同屬性值判斷從該節點向下的分支，在決策樹的葉節點得到結論。
主要的決策樹演算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT演算法等。它們在選擇測試屬性採用的技術、生成的決策樹的結構、剪枝的方法以及時刻，能否處理大數據集等方面都有各自的不同之處。
（2）貝葉斯
貝葉斯（Bayes）分類演算法是一類利用概率統計知識進行分類的演算法，如樸素貝葉斯（Naive
Bayes）演算法。這些演算法主要利用Bayes定理來預測一個未知類別的樣本屬於各個類別的可能性，選擇其中可能性最大的一個類別作為該樣本的最終類別。由於貝葉斯定理的成立本身需要一個很強的條件獨立性假設前提，而此假設在實際情況中經常是不成立的，因而其分類准確性就會下降。為此就出現了許多降低獨立性假設的貝葉斯分類演算法，如TAN（Tree
Augmented Na?ve Bayes)演算法，它是在貝葉斯網路結構的基礎上增加屬性對之間的關聯來實現的。
（3）人工神經網路
人工神經網路（Artificial
Neural
Networks，ANN）是一種應用類似於大腦神經突觸聯接的結構進行信息處理的數學模型。在這種模型中，大量的節點（或稱」神經元」，或」單元」）之間相互聯接構成網路，即」神經網路」，以達到處理信息的目的。神經網路通常需要進行訓練，訓練的過程就是網路進行學習的過程。訓練改變了網路節點的連接權的值使其具有分類的功能，經過訓練的網路就可用於對象的識別。
目前，神經網路已有上百種不同的模型，常見的有BP網路、徑向基RBF網路、Hopfield網路、隨機神經網路（Boltzmann機）、競爭神經網路（Hamming網路，自組織映射網路）等。但是當前的神經網路仍普遍存在收斂速度慢、計算量大、訓練時間長和不可解釋等缺點。
（4）k-近鄰
k-近鄰(kNN，k-Nearest
Neighbors)演算法是一種基於實例的分類方法。該方法就是找出與未知樣本x距離最近的k個訓練樣本，看這k個樣本中多數屬於哪一類，就把x歸為那一類。k-近鄰方法是一種懶惰學習方法，它存放樣本，直到需要分類時才進行分類，如果樣本集比較復雜，可能會導致很大的計算開銷，因此無法應用到實時性很強的場合。
（5）支持向量機
支持向量機（SVM，Support
Vector Machine）是Vapnik根據統計學習理論提出的一種新的學習方法[43]
，它的最大特點是根據結構風險最小化准則，以最大化分類間隔構造最優分類超平面來提高學習機的泛化能力，較好地解決了非線性、高維數、局部極小點等問題。對於分類問題，支持向量機演算法根據區域中的樣本計算該區域的決策曲面，由此確定該區域中未知樣本的類別。
（6）基於關聯規則的分類
關聯規則挖掘是數據挖掘中一個重要的研究領域。近年來，對於如何將關聯規則挖掘用於分類問題，學者們進行了廣泛的研究。關聯分類方法挖掘形如condset→C的規則，其中condset是項(或屬性-值對)的集合，而C是類標號，這種形式的規則稱為類關聯規則（class
association
rules，CARS）。關聯分類方法一般由兩步組成：第一步用關聯規則挖掘演算法從訓練數據集中挖掘出所有滿足指定支持度和置信度的類關聯規則；第二步使用啟發式方法從挖掘出的類關聯規則中挑選出一組高質量的規則用於分類。屬於關聯分類的演算法主要包括CBA[44]
，ADT[45] ，CMAR[46] 等。
（7）集成學習（Ensemble Learning）
實際應用的復雜性和數據的多樣性往往使得單一的分類方法不夠有效。因此，學者們對多種分類方法的融合即集成學習進行了廣泛的研究。集成學習已成為國際機器學習界的研究熱點，並被稱為當前機器學習四個主要研究方向之一。
集成學習是一種機器學習範式，它試圖通過連續調用單個的學習演算法，獲得不同的基學習器，然後根據規則組合這些學習器來解決同一個問題，可以顯著的提高學習系統的泛化能力。組合多個基學習器主要採用（加權）投票的方法，常見的演算法有裝袋[47]
（Bagging），提升/推進[48, 49] （Boosting）等。
有關分類器的集成學習見圖2-5。集成學習由於採用了投票平均的方法組合多個分類器，所以有可能減少單個分類器的誤差，獲得對問題空間模型更加准確的表示，從而提高分類器的分類准確度。
圖2-5：分類器的集成學習
以上簡單介紹了各種主要的分類方法，應該說其都有各自不同的特點及優缺點。對於資料庫負載的自動識別，應該選擇哪種方法呢？用來比較和評估分類方法的標准[50]
主要有：（1）預測的准確率。模型正確地預測新樣本的類標號的能力；（2）計算速度。包括構造模型以及使用模型進行分類的時間；（3）強壯性。模型對雜訊數據或空缺值數據正確預測的能力；（4）可伸縮性。對於數據量很大的數據集，有效構造模型的能力；（5）模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈容易理解，則愈受歡迎。
Ⅱ 經典機器學習系列之【集成學習】
塌歷老中國有句老古話，叫「 三個臭皮匠頂個諸葛亮 」，說的是人多力量大，可也有句成語叫「 烏合之眾 」。在機器學習中也有一類演算法，將這兩種思想融合起來，取其精華，它就是 集成學習 ，演算法將不同的學習器融合在一起。
在集成學習中，演算法不要求每個學習器性能最好，但是期望它們對問題具有不同的看法，Good But Different (好而不同)。
如果在分類問題上描述的話，所表示的就是具有不同的劃分能力，對於一些樣本學習器 能劃分，對於另外一些樣本，學習器 能劃分。並不要求單個學習器對所有樣本都具備劃分能力。
用專業一點的屬於來說的話，就是不同的學習器具有不同的偏好模型，但是每一個都是弱監督模型，集成學習將多個弱監督模型組合，得到一個好的強監督模型。其思想是，不同的學習器之間相互地錯誤糾正，以達到最終准確率的提升。
集成學習，其英文名稱叫做( ensemble learning )，它通過將多個學習器集成在一起來達到學習的目的。主要是將有限的模型相互組合，其名稱有時也會有不同的叫法，有時也會被稱為多分類器系統( multi-classifier system )、委員會學習( committee learning )、Molar systems、classifier fusion、combination、aggregation等。這些概念相互之間互相聯系，又有些許區別，對於概念的定義業界還沒有達成共識。整個演算法所表現出來的性能非常地強悍，許多高水平的競賽(Knowledge Discovery and Data Mining、Kaggle)中都是首選。
在機器學習，滿足訓練集的假設不一定在實際應用中有同樣好的表現，這樣學習演算法選擇哪個假設進行輸出的時候就面臨著一定的風險，把多個假設集成起來能夠降低這種風險（這可以理解為通過集成使得各個假設和目標假設之間的誤差得到一定程度的抵消）。
在周志華西瓜書中通過Hoeffding不等式證明了， 隨著集成中個體分類器數目的增大 ， 集成的錯誤率將指數級下降 ， 最終趨於零 。
集成學習先產生一組「個體學習器」( indivial learner )，再通過某種策略將其結合起來。依據每個個體學習器所採用的學習演算法是否相同，可以分為 同質集成 和 異質集成 。
集成學習器性能要好於單個個體學習器需要滿足 好而不同 的兩點要求：
第一個條件相對來說比較容易實現，在當前問題下訓練一個模型，結果比瞎猜的結果好就行了。 第二個條件是集成學習研究的核心問題 。每個個體學習器學習的都是同一個問題，所以個體學習器不可能做到完全相互獨立。想想小時候，老師讓你發爛歲表不同的觀點，想想寫論文的時候找創新點，人都很難做到這樣一件事情，何況它只是一個小小的學習演算法。
想要在個體學習器足夠好的前提下，增強其多樣性，我們可以直觀上來想像一下。整個的演算法學習過程是從數據到模型再到輸出。
首先考慮輸入 。如果每個學習器學習不同的樣本，那麼可以學習出相對來說不同的個體學習器。那麼現在的問題就是怎麼劃分訓練樣本，你可以隨機抽取，或者利用不同的屬性子集訓練出不同的個體學習器。
其次考慮模型 ，如果基學習器的模型不一樣，也能訓練出不同的個體學習器。
最後考慮輸出 ，如果我們依據標簽的特性來進團升行劃分，也能得到不同的個體學習器。
依據上述三點概念，主要有以下5種方法：
從原始訓練樣本中產生不同的樣本子集，然後利用不同的樣本子集訓練不同的個體學習器。如 Bagging 中使用的 自助采樣 ， Boosting 中使用的 序列采樣 。
這種訓練樣本擾動的方法簡單高效，但 只對不穩定的基學習器有效 ，像 決策樹 、 神經網路 等；對於穩定的基學習器，如線性學習器、支持向量機、樸素貝葉斯、K-NN等，就效果不明顯，產生這個問題的原因就是因為穩定的基學習器，「變通能力」並不是很強。
說到Bagging和Boosting，這里詳細介紹一下這兩種經典的方法：集成學習分為個體學習其之間存在強以來關系、必須 串列生成的序列化方法-Boosting 和不存在強依賴關系， 可同時生成並行化方法-Bagging 。
具體的實現方法是：首先給每一個訓練 樣例賦予相同的權重 ，然後訓練第一個基本分類器並用它來對訓練集進行測試， 對於那些分類錯誤的測試樣例提高其權重 （實際演算法中是降低分類正確的樣例的權重）， 然後用調整後的帶權訓練集訓練第二個基本分類器 ，然後重復這個過程直到最後得到一個足夠好的學習器。
Boosting中最著名演算法是1997年Yoav Freund所提出的AdaBoost（Adaptive Boosting）方法。下圖是AdaBoost論文Bing學術搜索結果：
本文以周志華西瓜書推導過程為例，以「 加性模型 」（additive model）進行解析：
將基學習器 線性組合，則基學習器的線性組合表示為如下 形式：
定義整個學習器的損失函數為指數損失函數( exponential loss function )，期望指數損失函數最小化：
其中 是真實函數， ， 表示樣本的權值分布(對於錯誤的樣本權重要高一點，正確的樣本權重要低一點，所有的樣本組合起來就相當於有一個分布)。
若基學習器的線性組合 能夠使得指數損失函數最小化，一般的做法就是求偏導數，令其等於零，求解。由於 取值只有兩種，所以其求偏導數之後的結果如下所示：
令其偏導數為0，解得：
有：
這意味著若指數損失函數最小化，則分類錯誤率也將最小化。說明指數損失函數是原任務的替代函數，但由於其連續可微，所以用它替代 0/1 損失函數作為優化目標。上面這么多就是說接下來用這個連續的指數損失函數做進一步的處理。
在AdaBoost演算法中，第一個基分類器 通過直接將基學習演算法用於初始數據分布而得到；之後的 和 是通過迭代生成得到的。當基分類器 基於分布 產生之後，基分類器的權重 應該使得 最小化指數損失函數，只有 在判斷錯誤的基分類器給予較小權值，判斷正確的基分類器給予較大權值，才能使得 具有較准確的判斷，從而最小化指數損失函數
其中 ，其實就是誤判率。為了求得基分類器的權重，對其求導：
再令導數為0，可得：
到這里相當於自適應做完了，在這里，AdaBoost自適應的思想採取的是加權多數表決的方法，上述公式體現出來的就是加大分類器誤差率小的弱分類器的權值，使其在表決中起較大作用。誤差率較大的則相反。
現在要回到Boost的原理中對樣本的處理，在改變這個樣本的權值，或者說概率分布的時候，我們要實現的直觀想法是： 提高那些被前一輪弱分類器錯誤分類樣本的權值 ， 降低那些被正確分類的樣本的權值 。接下來我們去把這個公式證出來：
這里通過基學習器開始證明，看基學習器在什麼樣本分布下能夠學出來最小化分類誤差。
AdaBoost 在得到 之後，調整樣本分布，使得 能學出來之前的基學習器無法學習到的東西，能糾正 的一些錯誤，那這個 就能夠最小化：
注意到 ，上式可使用 的泰勒展開式近似為如下公式：
於是理想的基學習器：
注意到 是一個常數。令 表示一個分布：
依據數學期望的定義，等價於令:
由 ， ， ，有：
則理想的基學習器：
由此可見，理想的 將在分布 下最小化分類誤差。 和 的關系有：
上述公式就是下圖AdaBoost的第7步更新公式，整個的AdaBoost演算法如下圖所示：
AdaBoost 演算法第五行檢查當前基分類器是否比隨機猜測好，一旦不滿足條件，當前基學習器即被拋棄，且學習過程停止。在這個請款下就有可能導致集成中包含基學習器數量過少，導致整體性能不佳。採用「重采樣法」（re-sampling）來處理，即在每一輪學習中，根據樣本分布對訓練集重新采樣，再用重采樣而得到的樣本集對基學習器進行訓練，則可獲得重啟動。
是並行式集成學習方法著名代表，基於自助采樣法( bootstrap sampling )，給定包含 個樣本的數據集，有放回隨機采樣，經過 次得到含有 個樣本的采樣集，這樣的采樣，初始訓練集中約有 的樣本出現在采樣集中。
照這樣采樣出 個含 個訓練樣本的采樣集，然後基於每個采樣集訓練一個基學習器，再將這些基學習器進行結合。在預測輸出時，Bagging通常對分類任務使用 簡單投票法 。對回歸任務使用 簡單平均法 。
上圖中 表示自助采樣產生的樣本分布。
輸入屬性擾動通常是從初始屬性集中抽取出若干個屬性子集，然後利用不同的屬性子集訓練出不同的個體學習器。比如有：
RF 在以 決策樹 為基學習器構建Bagging集成的基礎上，進一步在決策樹的訓練過程中引入隨機屬性。傳統決策樹在選擇劃分屬性時是在當前結點的屬性集合中選擇一個最優屬性；而在RF中，對基決策樹的每個結點， 先從該結點的屬性集合中隨機選擇一個包含 個屬性的子集 ， 然後再從這個子集中選擇一個最優屬性用於劃分 。
隨機森林中基學習器多樣性不僅來自樣本擾動，還來自屬性擾動，使得最終集成的泛化性能可通過個體學習器之間差異度的增加而進一步提升。
但這類輸入屬性擾動的方法只對大量冗餘屬性的數據集有效，但若數據集只包含少量屬性，或者冗餘屬性很少，則不宜使用。隨機森林由於起始引入了屬性擾動，性能會比Bagging差一點，但隨著個體數量增多，隨機森林通常會收斂到更低的泛化誤差。
演算法參數擾動指的是通過隨機設置不同的參數來訓練差別較大的個體學習器。如下圖所示的神經網路的隱層神經元數、初始連接權值等不同。
此類方法對參數較多的演算法有效，對參數較少的演算法，可通過將其學習過程中某些環節用其他類似方法代替？從而達到擾動的目的。這可能也是發論文的一個點吧，自己以後可能也不咋用這個演算法，就不去做演算法調研了。
輸出標記擾動是對訓練樣本的類別標記稍作變動，將原來的多分類問題隨機轉化 多個二分類問題 來訓練基學習器。經典的一個演算法就是糾錯輸出編碼法（Error-Correcting Output Codes，ECOC）
將每個類別對應一個長度為n的二進制位串（稱為碼字），共形成m個碼字，這些碼字的同一位描述了一個二值函數。學習結束後獲得n個二分器，在分類階段，每個二分器對輸入樣本產生的輸出形成輸出向量，然後由決策規則判定輸入樣本的類別。
這類方法對類數足夠多的數據集有效，但若數據集包含的類數較少，則不宜使用。
混合擾動在同一個集成演算法中同時使用上述多種擾動方法。比如隨機森林就同時使用了訓練樣本擾動和輸入屬性擾動。
上文五點討論的是如何產生好而不同的個體學習器。那產生了好而不同的個體學習器之後，我們如何結合這些策略？主要有 平均法 和常見的 投票法 (voting)，具體包括：
簡單地將輸出結果平均一下
乘以權值系數將其加起來。
即若某標記得票過半數，則分類為該標記，否則拒絕分類。
分類為得票最多的標記，若同時有多個標記獲最高票，則從中隨機選取一個。
給每個個體學習器預測的類標記賦一個權值，分類為權值最大的標記。這里的權值通常為該個體學習器的分類置信度（類成員概率）。
Ⅲ 集成演算法名詞解釋
集成演算法(Emseble Learning)是構建多個學習器，然後通過一定策略結合把它們來完成學習任務的，常常可以獲得比單一學習顯著優越的學習器。
Ⅳ 集成演算法
集成學習包括Bagging方法和Boosting方法，下面詳細分析這兩種方法。
下面是決策樹與這些演算法框架進行結合所得到的新的演算法：
1） Bagging + 決策樹 = 隨機森林
2）AdaBoost + 決策樹 = 提升樹
3）Gradient Boosting + 決策樹 = GBDT
Bagging法假設訓練樣本集服從均勻分布，即1/N。
（1） 從訓練樣本集中 隨機可放回抽樣（Bootstrapping )N次 ，得到與訓練集相同大小的訓練集，重復抽樣K次， 得到K個訓練集 。
（2） 每個訓練集得到一個最優模型， K個訓練集得到K個最優廳彎模型。
（3） 分類問題：對K個模型採用 投票的方式得到分類結果 ；回歸問題：對K個模型的值 求平均得到分 類結果。
每一個樣本數據是有權重的，每一個學習器是有先後順序的。在PAC（概率近似正確）的學習框架下，一定可以將弱分類器組裝成一個強分類器。
（1）每一輪如何改變訓練數據的權值和概率分布？
（2）通過什麼方式來組合弱學習器？
其尺氏中，學習器性能越好，對應的權值也越大。樣本權值1初始化為1/N，即初始樣本集服從均勻分布，後面隨著前一個學習器的結果更新樣本權值。
集成學習得到多個學習器後，結合策略得到最終的結果。通常用到最多的是平均法，投票法和學習法。
適用范圍：
規模大的集成，學習的權重較多 ， 加權平均法易導致過擬合
個體學習器性能相差較大時宜使用加權平均法，相近用簡單平均法 。
絕對多數投票法：某標記 超過半數 ，也就是我們常說的要票過半數，否則就當會拒絕預測；
相對多數投票法：預測為得票 最多 的標記，若同時有多個標記的票最高，則從中隨機選取一個，也就是所謂的「少數服從多數」。
加權投票法：提供了預測結果，與加權平均法類似。
對於學習法，代表方法是stacking，當使用stacking的結合策略時， 我們不是對弱學習器的結果做簡單的邏輯處理，而是再加上一層學習器，也就是說，我們 將訓練集弱學習器的學習結果作為輸入， 將訓練集的輸出作為輸出，重新訓練一個學習器來得到最終結果。
在這種情況下，我們將弱學習器稱為初級學習器，將用於結合的學習器稱為次級學習器。對於測試集，我們首先用初級學習器預測一次，得到次級學習器的輸入樣本，再用次級學習器預測一次，得到最終的預測結果。
1）訓練樣本集
Bagging：訓練集是有放回抽樣，從原始集中選出的K組訓練集是相互獨立的。
Boosting：每一次迭代的訓練集不變。
2）訓練樣本權扮困悶重
Bagging：每個訓練樣本的權重相等，即1/N。
Boosting：根據學習器的錯誤率不斷調整樣例的權值，錯誤率越大，權值越大。
3）預測函數的權重：
Bagging：K組學習器的權重相等，即1/K。
Boosting：學習器性能好的分配較大的權重，學習器性能差的分配較小的權重。
4）並行計算
Bagging：K組學習器模型可以並行生成。
Boosting：K組學習器只能順序生成，因為後一個模型的樣本權值需要前一個學習器模型的結果。
Bagging和Boosting方法都是把若干個學習器整合為一個學習器的方法，Bagging方法可以降低模型的方差，Boosting方法可以降低模型的偏差，在實際工作中，因情況需要選擇集成方法。