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

1、數(shù)據(jù)挖據(jù)技術(shù)集成學(xué)習(xí)方法(ensemble learnig),王磊 （副教授） 經(jīng)濟(jì)信息工程學(xué)院,1,2,2,第六章： 集成學(xué)習(xí)方法,基本概念 bagging boosting 隨機(jī)森林 選擇性集成方法,Data Mining: Concepts and Techniques,10/19/2020,在機(jī)器學(xué)習(xí)中，直接建立一個(gè)高性能的分類器是很困難的。 但是，如果能找到一系列性能較差的分類器（弱分類器），并把它們集成起來(lái)的話，也許就能得到更好的分類器。 日常生活中，“三個(gè)臭皮匠，勝過(guò)諸葛亮”，便是體現(xiàn)了這種思想。,集成學(xué)習(xí)的基本概念,3,Data Mining: Concepts and Tec

2、hniques,10/19/2020,集成學(xué)習(xí)：圖示,4,Data Mining: Concepts and Techniques,10/19/2020,我們一般選定加權(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,Data Mining

3、: Concepts and Techniques,10/19/2020,辦法就是改變訓(xùn)練集。 通常的學(xué)習(xí)算法，根據(jù)訓(xùn)練集的不同，會(huì)給出不同的學(xué)習(xí)器。這時(shí)就可以通過(guò)改變訓(xùn)練集來(lái)構(gòu)造不同的學(xué)習(xí)器。然后再把它們集成起來(lái)。,集成學(xué)習(xí)：如何構(gòu)造？,6,Data Mining: Concepts and Techniques,10/19/2020,在原來(lái)的訓(xùn)練集上隨機(jī)采樣，可以得到新的訓(xùn)練集。,【隨機(jī)采樣】,7,Data Mining: Concepts and Techniques,10/19/2020,集成學(xué)習(xí)（Ensemble Learning）是一種機(jī)器學(xué)習(xí)方法，它使用多個(gè)（通常是同質(zhì)的）學(xué)習(xí)器

4、來(lái)解決同一個(gè)問(wèn)題,集成學(xué)習(xí)中使用的多個(gè)學(xué)習(xí)器稱為個(gè)體學(xué)習(xí)器 當(dāng)個(gè)體學(xué)習(xí)器均為決策樹(shù)時(shí)，稱為“決策樹(shù)集成” 當(dāng)個(gè)體學(xué)習(xí)器均為神經(jīng)網(wǎng)絡(luò)時(shí)，稱為“神經(jīng)網(wǎng)絡(luò)集成” ,集成學(xué)習(xí)的定義,8,Data Mining: Concepts and Techniques,10/19/2020,由于集成學(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,問(wèn)題：對(duì)20維超立方體空間中的區(qū)域分類 左圖中縱軸為錯(cuò)誤率 從上到下的四條線分別表示： 平均神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率 最好

5、神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率 兩種神經(jīng)網(wǎng)絡(luò)集成的錯(cuò)誤率 令人驚奇的是，集成的錯(cuò)誤率比最好的個(gè)體還低,L.K. Hansen & P. Salamon, TPAMI90,【集成學(xué)習(xí)的重要性】,9,Data Mining: Concepts and Techniques,10/19/2020,集成學(xué)習(xí)技術(shù)已經(jīng)在行星探測(cè)、地震波分析、Web信息過(guò)濾、生物特征識(shí)別、計(jì)算機(jī)輔助醫(yī)療診斷等眾多領(lǐng)域得到了廣泛的應(yīng)用,只要能用到機(jī)器學(xué)習(xí)的地方，就能用到集成學(xué)習(xí),【集成學(xué)習(xí)的應(yīng)用】,10,Data Mining: Concepts and Techniques,10/19/2020,【如何構(gòu)建好的集成】,11,Data Mi

6、ning: Concepts and Techniques,10/19/2020,既然多個(gè)個(gè)體的集成比單個(gè)個(gè)體更好，那么是不是個(gè)體越多越好?,更多的個(gè)體意味著： 在預(yù)測(cè)時(shí)需要更大的計(jì)算開(kāi)銷，因?yàn)橐?jì)算更多的個(gè)體預(yù)測(cè) 更大的存儲(chǔ)開(kāi)銷，因?yàn)橛懈嗟膫€(gè)體需要保存,個(gè)體的增加將使得個(gè)體間的差異越來(lái)越難以獲得,【個(gè)體越多越好嗎？】,12,Data Mining: Concepts and Techniques,10/19/2020,集成策略,有多種策略可以將q個(gè)弱分類器組合成集成分類器。,13,Data Mining: Concepts and Techniques,10/19/2020,集成策略,14

7、,Data Mining: Concepts and Techniques,10/19/2020,從大小為n的原始數(shù)據(jù)集D中獨(dú)立隨機(jī)地抽取n個(gè)數(shù)據(jù)(n=n)，形成一個(gè)自助數(shù)據(jù)集； 重復(fù)上述過(guò)程，產(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,Data Mining: Concep

8、ts and Techniques,10/19/2020,【Bagging算法】,16,Data Mining: Concepts and Techniques,10/19/2020,【Boosting算法】,17,Data Mining: Concepts and Techniques,10/19/2020,Boosting流程描述,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ī)的權(quán)重 Step5: 轉(zhuǎn)到Step2, 直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求 Step6:

9、 將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī),18,Data Mining: Concepts and Techniques,10/19/2020,核心思想,樣本的權(quán)重 沒(méi)有先驗(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,Data Mining: Concept

10、s and Techniques,10/19/2020,簡(jiǎn)單問(wèn)題演示（Boosting訓(xùn)練過(guò)程）,20,Data Mining: Concepts and Techniques,10/19/2020,算法boosting數(shù)學(xué)描述,訓(xùn)練集 (x1,y1), (x2,y2), (xN,yN) xi Rm, yi -1,+1 Dt 為第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 learner,21,Data

11、 Mining: Concepts and Techniques,10/19/2020,樣本權(quán)重,思想：提高分錯(cuò)樣本的權(quán)重 反映了strong learner對(duì)樣本的假設(shè)是否正確 采用什么樣的函數(shù)形式？,22,Data Mining: Concepts and Techniques,10/19/2020,弱學(xué)習(xí)機(jī)權(quán)重,思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大 為學(xué)習(xí)機(jī)的錯(cuò)誤概率 采用什么樣的函數(shù)形式？ 和指數(shù)函數(shù)遙相呼應(yīng)：,23,Data Mining: Concepts and Techniques,10/19/2020,AdaBoost算法,24,Data Mining: Concepts

12、 and Techniques,10/19/2020,25,Adaboost 訓(xùn)練過(guò)程,D,2,26,Adaboost 訓(xùn)練過(guò)程,D,2,27,Adaboost 訓(xùn)練過(guò)程,D,2,Adaboost的缺點(diǎn),28,Data Mining: Concepts and Techniques,10/19/2020,隨機(jī)森林算法,隨機(jī)森林算法是Leo Breiman于2001年提出的一種新型分類和預(yù)測(cè)模型，它具有需要調(diào)整的參數(shù)少，不容易過(guò)度擬合，分類速度快，能高效處理大樣本數(shù)據(jù)等特點(diǎn)。 Bagging和AdaBoost等方法只是通過(guò)改變樣本的權(quán)重來(lái)獲得不同的弱分類器。隨機(jī)森林（RF）則通過(guò)同時(shí)改變樣本和特

13、征子集來(lái)獲得不同的弱分類器。,29,Data Mining: Concepts and Techniques,10/19/2020,隨機(jī)森林算法,隨機(jī)森林是采用隨機(jī)的方式建立一個(gè)森林，森林有很多決策樹(shù)組成，每棵決策樹(shù)之間沒(méi)有關(guān)聯(lián)。對(duì)于新的測(cè)試樣本，讓森林中的每一棵決策樹(shù)分布分別進(jìn)行一下判斷，依據(jù)多數(shù)者投票方法決定樣本的類別。,30,Data Mining: Concepts and Techniques,10/19/2020,31,Data Mining: Concepts and Techniques,10/19/2020,完全分裂的方式,32,Data Mining: Concepts a

14、nd Techniques,10/19/2020,隨機(jī)特征選取,當(dāng)特征個(gè)數(shù)M較多時(shí)，隨機(jī)選擇m個(gè)用于訓(xùn)練決策樹(shù)。m越小，樹(shù)的相關(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)建決策樹(shù)。 其中，每一個(gè)擴(kuò)展特征的構(gòu)造如下： 從現(xiàn)有M特征中隨機(jī)抽取L個(gè)，它們的權(quán)重系數(shù)是-1,+1區(qū)間的均勻隨機(jī)數(shù)。然后，由L個(gè)已有特征線性組合出擴(kuò)展特征。,33,Data Mining: Concepts and Techniques,10/19/2020,隨機(jī)特征數(shù)的確定,34,Data Mining: Concepts an

15、d Techniques,10/19/2020,選擇性集成算法,一方面，使用更多的學(xué)習(xí)器將導(dǎo)致更大的計(jì)算和存儲(chǔ)開(kāi)銷，另一方面，當(dāng)個(gè)體學(xué)習(xí)器數(shù)目增加之后，學(xué)習(xí)器之間的差異將越來(lái)越難以獲得。 因此，提出問(wèn)題：為了達(dá)到更好的性能，是否必須使用更多的個(gè)體學(xué)習(xí)器？,35,Data Mining: Concepts and Techniques,10/19/2020,選擇性集成的理論分析,36,Data Mining: Concepts and Techniques,10/19/2020,選擇性集成的理論分析,37,Data Mining: Concepts and Techniques,10/19/20

16、20,選擇性集成的理論分析,38,Data Mining: Concepts and Techniques,10/19/2020,選擇性集成的理論分析,39,Data Mining: Concepts and Techniques,10/19/2020,問(wèn)題求解,40,Data Mining: Concepts and Techniques,10/19/2020,問(wèn)題求解,41,Data Mining: Concepts and Techniques,10/19/2020,GASEN算法,42,Data Mining: Concepts and Techniques,10/19/2020,論文講解,基于約束投影的支持向量機(jī)選擇性集成 ，2009,43,Data Mining