數(shù)據(jù)挖據(jù)技術(shù)集成學(xué)習(xí)方法ensemblelearnig

1、 數(shù)據(jù)挖據(jù)技術(shù)集成學(xué)習(xí)方法(ensemble learnig)王磊 （副教授）12第六章： 集成學(xué)習(xí)方法基本概念baggingboosting隨機(jī)森林選擇性集成方法2在機(jī)器學(xué)習(xí)中，直接建立一個(gè)高性能的分類器是很困難的。但是，如果能找到一系列性能較差的分類器（弱分類器），并把它們集成起來(lái)的話，也許就能得到更好的分類器。日常生活中，“三個(gè)臭皮匠，勝過諸葛亮”，便是體現(xiàn)了這種思想。集成學(xué)習(xí)的基本概念3Classifier ensembleihi(x)hn(x)h2(x)h1(x)Input vectorClassifier 1Classifier 2Classifier NCombine Class

2、ifiersOutputx集成學(xué)習(xí)：圖示4我們一般選定加權(quán)平均的方法來(lái)構(gòu)造集成學(xué)習(xí)的最終學(xué)習(xí)器。但是里面的每一個(gè) 弱分類器（i）怎樣構(gòu)造呢？有一些研究，是針對(duì)每個(gè)學(xué)習(xí)器都不同構(gòu)的情況，比如識(shí)別一個(gè)人，一個(gè)學(xué)習(xí)器考慮臉，另一個(gè)考慮步態(tài)，另一個(gè)考慮指紋。這種研究通常稱為Information Fusion，不在我們今天討論的范疇。狹義的集成學(xué)習(xí)（ensemble learning），是用同樣類型的學(xué)習(xí)算法來(lái)構(gòu)造不同的弱學(xué)習(xí)器的方法。集成學(xué)習(xí)：如何構(gòu)造？5辦法就是改變訓(xùn)練集。通常的學(xué)習(xí)算法，根據(jù)訓(xùn)練集的不同，會(huì)給出不同的學(xué)習(xí)器。這時(shí)就可以通過改變訓(xùn)練集來(lái)構(gòu)造不同的學(xué)習(xí)器。然后再把它們集成起來(lái)。集成學(xué)

3、習(xí)：如何構(gòu)造？6在原來(lái)的訓(xùn)練集上隨機(jī)采樣，可以得到新的訓(xùn)練集?！倦S機(jī)采樣】7 集成學(xué)習(xí)（Ensemble Learning）是一種機(jī)器學(xué)習(xí)方法，它使用多個(gè)（通常是同質(zhì)的）學(xué)習(xí)器來(lái)解決同一個(gè)問題 問題 . . 問題 集成學(xué)習(xí)中使用的多個(gè)學(xué)習(xí)器稱為個(gè)體學(xué)習(xí)器當(dāng)個(gè)體學(xué)習(xí)器均為決策樹時(shí)，稱為“決策樹集成”當(dāng)個(gè)體學(xué)習(xí)器均為神經(jīng)網(wǎng)絡(luò)時(shí)，稱為“神經(jīng)網(wǎng)絡(luò)集成” 集成學(xué)習(xí)的定義8由于集成學(xué)習(xí)技術(shù)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國(guó)際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)，并被國(guó)際權(quán)威 T.G. Dietterich 稱為當(dāng)前機(jī)器學(xué)習(xí)四大研究方向之首T.G. Dietterich, AIMag97問題：對(duì)20維超立方體空

4、間中的區(qū)域分類左圖中縱軸為錯(cuò)誤率從上到下的四條線分別表示：平均神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率最好神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率兩種神經(jīng)網(wǎng)絡(luò)集成的錯(cuò)誤率令人驚奇的是，集成的錯(cuò)誤率比最好的個(gè)體還低 L.K. Hansen & P. Salamon, TPAMI90【集成學(xué)習(xí)的重要性】9集成學(xué)習(xí)技術(shù)已經(jīng)在行星探測(cè)、地震波分析、Web信息過濾、生物特征識(shí)別、計(jì)算機(jī)輔助醫(yī)療診斷等眾多領(lǐng)域得到了廣泛的應(yīng)用只要能用到機(jī)器學(xué)習(xí)的地方，就能用到集成學(xué)習(xí)【集成學(xué)習(xí)的應(yīng)用】10期望結(jié)果個(gè)體1 (精度33.3%)個(gè)體2 (精度33.3%)個(gè)體3 (精度33.3%)集成(精度33.3%)投票個(gè)體必須有差異期望結(jié)果個(gè)體1 (精度33.3%)個(gè)體2 (精

5、度33.3%)個(gè)體3 (精度33.3%)集成 (精度0%)投票個(gè)體精度不能太低個(gè)體學(xué)習(xí)器越精確、差異越大，集成越好A. Krogh & J. Vedelsby, NIPS94【如何構(gòu)建好的集成】11既然多個(gè)個(gè)體的集成比單個(gè)個(gè)體更好，那么是不是個(gè)體越多越好?更多的個(gè)體意味著： 在預(yù)測(cè)時(shí)需要更大的計(jì)算開銷，因?yàn)橐?jì)算更多的個(gè)體預(yù)測(cè) 更大的存儲(chǔ)開銷，因?yàn)橛懈嗟膫€(gè)體需要保存?zhèn)€體的增加將使得個(gè)體間的差異越來(lái)越難以獲得【個(gè)體越多越好嗎？】12集成策略有多種策略可以將q個(gè)弱分類器組合成集成分類器。 13集成策略14從大小為n的原始數(shù)據(jù)集D中獨(dú)立隨機(jī)地抽取n個(gè)數(shù)據(jù)(n=n)，形成一個(gè)自助數(shù)據(jù)集；重復(fù)上述過程

6、，產(chǎn)生出多個(gè)獨(dú)立的自助數(shù)據(jù)集；利用每個(gè)自助數(shù)據(jù)集訓(xùn)練出一個(gè)“分量分類器”；最終的分類結(jié)果由這些“分量分類器”各自的判別結(jié)果投票決定。基本思想：對(duì)訓(xùn)練集有放回地抽取訓(xùn)練樣例，從而為每一個(gè)基本分類器都構(gòu)造出一個(gè)跟訓(xùn)練集相當(dāng)大小但各不相同的訓(xùn)練集，從而訓(xùn)練出不同的基本分類器；該算法是基于對(duì)訓(xùn)練集進(jìn)行處理的集成方法中最簡(jiǎn)單、最直觀的一種。 【Bagging算法】15【Bagging算法】16【Boosting算法】17Boosting流程描述Step1: 原始訓(xùn)練集輸入Step2: 計(jì)算訓(xùn)練集中各樣本的權(quán)重Step3: 采用已知算法訓(xùn)練弱學(xué)習(xí)機(jī)，并對(duì)每個(gè)樣本進(jìn)行判別Step4: 計(jì)算對(duì)此次的弱學(xué)習(xí)機(jī)的

7、權(quán)重Step5: 轉(zhuǎn)到Step2, 直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求Step6: 將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī)18核心思想樣本的權(quán)重沒有先驗(yàn)知識(shí)的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有N個(gè)樣本，每個(gè)樣本的分布概率為1/N每次循環(huán)一后提高錯(cuò)誤樣本的分布概率，分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大， 使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷。弱學(xué)習(xí)機(jī)的權(quán)重準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高循環(huán)控制：損失函數(shù)達(dá)到最小在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)加權(quán)的弱學(xué)習(xí)機(jī)，使準(zhǔn)確率提高，損失函數(shù)值減小。19簡(jiǎn)單問題演示（Boosting訓(xùn)練過程）20算法boosting數(shù)學(xué)

8、描述訓(xùn)練集 (x1,y1), (x2,y2), (xN,yN) xi Rm, yi -1,+1Dt 為第t次循環(huán)時(shí)的訓(xùn)練樣本分布（每個(gè)樣本在訓(xùn)練集中所占的概率， Dt總和應(yīng)該為1）ht:X-1,+1 為第t次循環(huán)時(shí)的Weak learner，對(duì)每個(gè)樣本給出相應(yīng)的假設(shè)，應(yīng)該滿足強(qiáng)于隨機(jī)猜測(cè)：wt為ht的權(quán)重 為t次循環(huán)得到的Strong learner21樣本權(quán)重思想：提高分錯(cuò)樣本的權(quán)重 反映了strong learner對(duì)樣本的假設(shè)是否正確采用什么樣的函數(shù)形式？22弱學(xué)習(xí)機(jī)權(quán)重思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大 為學(xué)習(xí)機(jī)的錯(cuò)誤概率采用什么樣的函數(shù)形式？ 和指數(shù)函數(shù)遙相呼應(yīng)：23AdaBo

9、ost算法24Adaboost 訓(xùn)練過程25Adaboost 訓(xùn)練過程26Adaboost 訓(xùn)練過程27Adaboost的缺點(diǎn)28隨機(jī)森林算法隨機(jī)森林算法是Leo Breiman于2001年提出的一種新型分類和預(yù)測(cè)模型，它具有需要調(diào)整的參數(shù)少，不容易過度擬合，分類速度快，能高效處理大樣本數(shù)據(jù)等特點(diǎn)。Bagging和AdaBoost等方法只是通過改變樣本的權(quán)重來(lái)獲得不同的弱分類器。隨機(jī)森林（RF）則通過同時(shí)改變樣本和特征子集來(lái)獲得不同的弱分類器。29隨機(jī)森林算法隨機(jī)森林是采用隨機(jī)的方式建立一個(gè)森林，森林有很多決策樹組成，每棵決策樹之間沒有關(guān)聯(lián)。對(duì)于新的測(cè)試樣本，讓森林中的每一棵決策樹分布分別進(jìn)行

10、一下判斷，依據(jù)多數(shù)者投票方法決定樣本的類別。3031完全分裂的方式32隨機(jī)特征選取當(dāng)特征個(gè)數(shù)M較多時(shí)，隨機(jī)選擇m個(gè)用于訓(xùn)練決策樹。m越小，樹的相關(guān)性越小，且訓(xùn)練速度越快。當(dāng)特征個(gè)數(shù)M較少時(shí)，可以由M個(gè)特征進(jìn)行隨機(jī)線性組合來(lái)產(chǎn)生M 個(gè)擴(kuò)展特征，然后，在（M+M）上隨機(jī)選擇m個(gè)特征，構(gòu)建決策樹。其中，每一個(gè)擴(kuò)展特征的構(gòu)造如下： 從現(xiàn)有M特征中隨機(jī)抽取L個(gè)，它們的權(quán)重系數(shù)是-1,+1區(qū)間的均勻隨機(jī)數(shù)。然后，由L個(gè)已有特征線性組合出擴(kuò)展特征。33隨機(jī)特征數(shù)的確定34選擇性集成算法一方面，使用更多的學(xué)習(xí)器將導(dǎo)致更大的計(jì)算和存儲(chǔ)開銷，另一方面，當(dāng)個(gè)體學(xué)習(xí)器數(shù)目增加之后，學(xué)習(xí)器之間的差異將越來(lái)越難以獲得。因此，提出問題：為了達(dá)到更好的性能，是否必須使用更多的個(gè)體學(xué)習(xí)器？35選擇性集成的理論分析36選擇性集成的理論分析37選擇性集成的理論分析38選擇性集成的理論分析39問題求解40問題求解41GASEN算法42論文講解基于約束投影的支持向量機(jī)選擇性集成 ，200943研