【正文】 ..., )id i m? 為預(yù)測類。下面詳細(xì)介紹隨機(jī)決策樹的深度選擇和數(shù)目的選擇及其分類。 (1)選擇樹的深度。使用多個(gè)隨機(jī)樹的主要特色是多樣性導(dǎo)致較高的分類準(zhǔn)確率 ,多樣性不與深度成正比關(guān)系。研究表明 ,當(dāng) i=k/2 時(shí)得到最大路徑數(shù) ,隨機(jī)決策上海大學(xué)碩士學(xué)位論文 2022 年 5 月 10 樹有最佳的效果。 (2)選擇隨機(jī)決策樹的個(gè)數(shù)。樹的個(gè)數(shù) N=10 時(shí)有較低的分類錯(cuò)誤率 ,且可信度大于 %。 (3)葉子 結(jié)點(diǎn)的更新。在樹的結(jié)構(gòu)建好后對樹結(jié)點(diǎn)更新 ,其中葉子結(jié)點(diǎn)記錄事例被分類為某一預(yù)定類別的個(gè)數(shù) 。非葉子結(jié)點(diǎn)不記錄經(jīng)過分支的事例數(shù)目 ,葉子中信息形式如 : 1 1 2 2{ ( , ) , ( , ) , ..., ( , ) }mmd s d s d s。其中 ,si 表示預(yù)測為 di 類的事例數(shù) , ( 1, 2,..., )id i m? 表示決策屬性類別。 12 ... mS s s s? 表示某一葉子結(jié)點(diǎn)記錄的總事例數(shù)。 (4) 分類。當(dāng)對事例進(jìn)行分類時(shí) , 預(yù)測為預(yù)定類別 di 的概率11( 1 , 2 , . . . )NijjP i m PN ??? ?。其中 ,N 表示隨機(jī)決策樹的數(shù)目 。 /jiP s S? 為每棵隨機(jī)決策樹輸出的后驗(yàn)概率 。S 為從根結(jié)點(diǎn)開始搜索到合適葉子結(jié)點(diǎn)處的事例個(gè)數(shù) 。Si 為該葉子結(jié)點(diǎn)處訓(xùn)練數(shù)據(jù)集中標(biāo)記為 di 類的數(shù)目。在后驗(yàn)概率 Pi 中找出最大的一個(gè) m ax( )( 1,..., )iP i m? ,其所對應(yīng)的預(yù)定類別即為隨機(jī)決策樹最終的輸出結(jié)果。 由于完全隨機(jī)的選擇屬性 ,因而可能會出現(xiàn)某些屬性在整個(gè)決策樹構(gòu)造過程中沒有或很少被選取為分裂屬性 ,特別是當(dāng)該屬性對分類結(jié)果有較大貢獻(xiàn)時(shí) ,這種缺少將導(dǎo)致分類正確率的不穩(wěn)定 ,當(dāng)屬性 數(shù)較少時(shí) ,這種不穩(wěn)定性將更為明顯。 隨機(jī)森林算法 [43] 在決策樹算法中 ,一般用選擇分裂屬性和剪枝來控制樹的生成 ,但是當(dāng)數(shù)據(jù)中噪聲或分裂屬性過多時(shí) ,它們也解決不了樹不平衡 。最新的研究表明 [6],構(gòu)造多分類器的集成 ,這樣可以提高分類精度 .隨機(jī)森林就是許多決策樹的集成 . 為了構(gòu)造 k 棵樹 ,我們得先產(chǎn)生 k 個(gè)隨機(jī)向量 12, ,..., k? ? ? ，這些隨機(jī)向量 i? 是相互獨(dú)立并且是同分布。隨機(jī)向量 i? 可構(gòu)造決策分類樹 ( , )ihX? ，簡化為 ()hX 。 給定 k 個(gè)分類器 12( ), ( ), ...., ( )kh x h x h x和隨機(jī)向量 x、 y,定義邊緣函數(shù) ( , ) ( ( ) ) m a x ( ( ) )k k k kjym g x y a v I h x y a v I h x j?? ? ? ? () 其中 ()I? 是示性函數(shù)。該邊緣函數(shù)刻畫了對向量 X 正確分類 y 的平均得票數(shù)上海大學(xué)碩士學(xué)位論文 2022 年 5 月 11 超過其它任何類平均得票數(shù)的程度。可以看出 ,邊際越大分類的置信度就越高。于是， 分類器的泛化誤差 * , ( ( , ) 0)xyP E P m g x y?? () 其中下標(biāo) X,Y 代表的是該誤差是在 X,Y 空間下的。 將上面的結(jié)論推廣到隨機(jī)森林 , ( ) ( , )kkh X h X ?? 。如果森林中的樹的數(shù)目較大，隨著樹的數(shù)目增加 ,對所有隨機(jī)向量 *,...,PE? 趨向于 , ( ( ( , ) ) m a x ( ( , ) ) 0 )xy jyP p h x y p h x j?????? ? ? ? () 這是隨機(jī)森林的一個(gè)重要特點(diǎn) ， 并且隨著樹的增加 ， 泛化誤差 *PE 將趨向一上界 ， 這表明隨機(jī)森林對未知的實(shí)例有很好的擴(kuò)展 。 隨機(jī)森林的泛化誤差上界的定義為 _* 2 2(1 ) /P E s s??? () 其中 _? 是相關(guān)系數(shù)的均值 ,s 是樹的分類強(qiáng)度 。隨機(jī)森林的泛化誤差上界可以根據(jù)兩個(gè)參數(shù)推導(dǎo)出來：森林中每棵決策樹的分類精度即樹的強(qiáng)度 S,和這些樹之間的相互依賴程度 _? 。當(dāng)隨機(jī)森林中各個(gè)分類器的相關(guān)程度 _? 增大時(shí)，泛化誤差*PE 上界就增大；當(dāng)各個(gè)分類器的分類強(qiáng)度增大時(shí)，泛化誤差 *PE 上界就增大。正確理解這兩者之間的相互影響是我們理解隨機(jī)森林工作原理的基礎(chǔ) . . 集成學(xué)習(xí) 算法 集成學(xué)習(xí) (Ensemble Learning)是一種新的機(jī)器學(xué)習(xí)范式，它使用多個(gè) (通常是同質(zhì)的 )學(xué)習(xí)器來解決同一個(gè)問題。由于集成學(xué)習(xí)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)。 集成學(xué)習(xí)算法概述 在機(jī)器學(xué)習(xí)領(lǐng)域，最早的集成學(xué)習(xí)方法是 Bayesian Averaging。在此之后，集成學(xué)習(xí)的研究才逐漸引起了人們的關(guān)注。 和 [44]使用一組神經(jīng)網(wǎng)絡(luò)來解決問題，除了按常規(guī)的做法選擇出最好的神經(jīng)網(wǎng)絡(luò)之外，他們還嘗試上海大學(xué)碩士學(xué)位論文 2022 年 5 月 12 通過投票法將所有的神經(jīng)網(wǎng)絡(luò)結(jié)合起來求解。他們的實(shí)驗(yàn)結(jié)果表明，這一組神經(jīng)網(wǎng)絡(luò)形成的集成，比最好的個(gè)體神經(jīng)網(wǎng)絡(luò)的性能還好。正是這一超乎人們直覺的結(jié)果，使得集成學(xué)習(xí)引起了很多學(xué)者的重視。 1990 年， Schapire[45]通過一個(gè)構(gòu)造性方法對弱 學(xué)習(xí)算法與強(qiáng)學(xué)習(xí)算法是否等價(jià)的問題作了肯定的證明，證明多個(gè)弱分類器可以集成為一個(gè)強(qiáng)分類器，他的工作奠定了集成學(xué)習(xí)的理論基礎(chǔ)。這個(gè)構(gòu)造性方法就是 Boosting 算法的雛形。但是這個(gè)算法存在著一個(gè)重大的缺陷，就是必須知道學(xué)習(xí)算法正確率的下限，這在實(shí)際中很難做到。在 1995 年， Freund和 Schapire[46]做了進(jìn)一步工作，提出了 AdBaoost 算法，該算法不再要求事先知道泛化下界，可以非常容易的應(yīng)用到實(shí)際的問題中去。 1996 年， Breiman[46]提出了與 Boosting 相似的技術(shù) Bagging，進(jìn)一步 促進(jìn)了集成學(xué)習(xí)的發(fā)展。 狹義地說，集成學(xué)習(xí)是指利用多個(gè)同質(zhì)的學(xué)習(xí)器來對同一個(gè)問題進(jìn)行學(xué)習(xí)，這里的“同質(zhì)”是指所使用的學(xué)習(xí)器屬于同一種類型，例如所有的學(xué)習(xí)器都是決策樹、都是神經(jīng)網(wǎng)絡(luò)等等。廣義地來說，只要是使用多個(gè)學(xué)習(xí)器來解決問題，就是集成學(xué)習(xí) [47,48]。在集成學(xué)習(xí)的早期研究中，狹義定義采用得比較多，而隨著該領(lǐng)域的發(fā)展，越來越多的學(xué)者傾向于接受廣義定義。所以在廣義的情況下，集成學(xué)習(xí)已經(jīng)成為了一個(gè)包含內(nèi)容相當(dāng)多的、比較大的研究領(lǐng)域。 大致上來說，集成學(xué)習(xí)的構(gòu)成方法可以分為四種 : 1. 輸入變量集重構(gòu)法。這種構(gòu)成 方法，用于集成的每個(gè)算法的輸入變量是原變量集的一個(gè)子集。這種方法比較適用于輸入變量集高度冗余的時(shí)候，否則的話，選取一個(gè)屬性子集，會影響單個(gè)算法的性能，最終影響集成的結(jié)果。 2. 輸出變量集重構(gòu)法。這種構(gòu)成方法，主要是通過改變輸出變量集，將多分類問題轉(zhuǎn)換為二分類問題來解決。 3. 樣本集重新抽樣法。在這種構(gòu)成方法中，用于集成的每個(gè)算法所對應(yīng)的訓(xùn)練數(shù)據(jù)都是原來訓(xùn)練數(shù)據(jù)的一個(gè)子集。目前的大部分研究主要集中在使用這種構(gòu)成方法來集成學(xué)習(xí)，如 Bagging， Boosting 等等。樣本集重新抽樣法對于不穩(wěn)定的算法來說，能夠取得很好的 效果。不穩(wěn)定的算法指的是當(dāng)訓(xùn)練數(shù)據(jù)發(fā)生很小變化的時(shí)候，結(jié)果就能產(chǎn)生很大變化的算法。如神經(jīng)網(wǎng)絡(luò)、決策樹。但是對于穩(wěn)定的算法來說，效果不是很好。 上海大學(xué)碩士學(xué)位論文 2022 年 5 月 13 4. 參數(shù)選擇法。對于許多算法如神經(jīng)網(wǎng)絡(luò)、遺傳算法來說，在算法應(yīng)用的開始首先要解決的就是要選擇算法參數(shù)。而且，由于這些算法操作過程的解釋性很差，對于算法參數(shù)的選擇沒有確定的規(guī)則可依。在實(shí)際應(yīng)用中，就需要操作者根據(jù)自己的經(jīng)驗(yàn)進(jìn)行選擇。在這樣的情況下，不同的參數(shù)選擇，最終的結(jié)果可能會有很大的區(qū)別，具有很大的不穩(wěn)定性。 集成算法的作用主要體現(xiàn)在如下四個(gè)方面： 1. 提高預(yù)測結(jié)果的準(zhǔn)確性 。機(jī)器學(xué)習(xí)的一個(gè)重要目標(biāo)就是對新的測試樣本盡可能給出最精確的估計(jì)。構(gòu)造單個(gè)高精度的學(xué)習(xí)器是一件相當(dāng)困難的事情，然而產(chǎn)生若干個(gè)只比隨機(jī)猜想略好的學(xué)勻器卻很容易。研究者們在應(yīng)用研究中發(fā)現(xiàn)，將多個(gè)學(xué)習(xí)器進(jìn)行集成后得到的預(yù)測精度明顯高于單個(gè)學(xué)習(xí)器的精度，甚至比單個(gè)最好的學(xué)習(xí)器的精度更高。 2. 提高預(yù)測結(jié)果的穩(wěn)定性。有些學(xué)習(xí)算法單一的預(yù)測結(jié)果時(shí)好時(shí)壞，不具有穩(wěn)定性，不能一直保持高精度的預(yù)測。通過模型的集成，可以在多種數(shù)據(jù)集中以較高的概率普遍取得很好的結(jié)果。 3. 解決過擬合問題。在對己知的數(shù)據(jù)集合進(jìn)行學(xué)習(xí)的時(shí)候，我們常常選擇擬 合度值最好的一個(gè)模型作為最后的結(jié)果。也許我們選擇的模型能夠很好的解釋訓(xùn)練數(shù)據(jù)集合，但是卻不能很好的解釋測試數(shù)據(jù)或者 其它數(shù)據(jù)，也就是說這個(gè)模型過于精細(xì)的刻畫了訓(xùn)練數(shù)據(jù)，對于測試數(shù)據(jù)或者 其它 新的數(shù)據(jù)泛化能力不強(qiáng)，這種現(xiàn)象就稱為過擬合。為了解決過擬合問題，按照集成學(xué)習(xí)的思想，可以選擇多個(gè)模型作為結(jié)果，對于每個(gè)模型賦予相應(yīng)的權(quán)重，從而集合生成合適的結(jié)果，提高預(yù)測精度。 4. 改進(jìn)參數(shù)選擇。對于一些算法而言，如神經(jīng)網(wǎng)絡(luò)、遺傳算法，在解決實(shí)際問題的時(shí)候，需要選擇操作參數(shù)。但是這些操作參數(shù)的選取沒有確定性的規(guī)則可以依據(jù)，只能憑 借經(jīng)驗(yàn)來選取，對于非專業(yè)的一般操作人員會有一定的難度。而且參數(shù)選擇不同，結(jié)果會有很大的差異。通過建立多個(gè)不同操作參數(shù)的模型，可以解決選取參數(shù)的難題，同時(shí)將不同模型的結(jié)果按照一定的方式集成就可以生成我們想要的結(jié)果。 集成學(xué)習(xí)經(jīng)過了十幾年的不斷發(fā)展，各種不同的集成學(xué)習(xí)算法不斷被提了出來，其中以 Boosting 和 Bagging 的影響最大。這兩種算法也是被研究得最多上海大學(xué)碩士學(xué)位論文 2022 年 5 月 14 的，它們都是通過改造訓(xùn)練樣本集來構(gòu)造集成學(xué)習(xí)算法。在下面的章節(jié)中對這兩種算法進(jìn)行了詳細(xì)的介紹。 AdaBoost 算法 Kearns 和 Valiant 指出 [48]，在 PCA 學(xué)習(xí)模型中，若存在一個(gè)多項(xiàng)式級學(xué)習(xí)算法來識別一組概念，并且識別正確率很高，那么這組概念是強(qiáng)可學(xué)習(xí)的；而如果學(xué)習(xí)算法識別一組概念的正確率僅比隨機(jī)猜測略好，那么這組概念是弱可學(xué)習(xí)的。 Kaerns 和 valiant 提出了弱學(xué)習(xí)算法與強(qiáng)學(xué)習(xí)算法的等價(jià)性問題，即是否可以將弱學(xué)習(xí)算法提升成強(qiáng)學(xué)習(xí)算法的問題。如果兩者等價(jià)，那么在學(xué)習(xí)概念時(shí)，只要找到一個(gè)比隨機(jī)猜測略好的弱學(xué)習(xí)算法，就可以將其提升為強(qiáng)學(xué)習(xí)算法，而不必直接去找通常情況下很難獲得的強(qiáng)學(xué)習(xí)算法。 1990 年， schapire[49] 通過 一個(gè)構(gòu)造性方法對該問題做出了肯定的證明，其構(gòu)造過程稱為 Boosting。 1995 年Freund[50]對其進(jìn)行了改進(jìn)。在 Freund 的方法中通過 Boosting 產(chǎn)生一系列神經(jīng)網(wǎng)絡(luò)，各網(wǎng)絡(luò)的訓(xùn)練集決定于在其之前產(chǎn)生的網(wǎng)絡(luò)的表現(xiàn)，被已有網(wǎng)絡(luò)錯(cuò)誤判斷的示例將以較大的概率出現(xiàn)在新網(wǎng)絡(luò)的訓(xùn)練集中。這樣，新網(wǎng)絡(luò)將能夠很好地處理對己有網(wǎng)絡(luò)來說很困難的示例。另一方面，雖然 Boosting 方法能夠增強(qiáng)神經(jīng)網(wǎng)絡(luò)集成的泛化能力，但是同時(shí)也有可能使集成過分偏向于某幾個(gè)特別困難的示例。因此，該方法不太穩(wěn)定，有時(shí)能起到很好的作用，有時(shí) 卻沒有效果。 1995年， Freund 和 schapire 提出了 AdaBoost (Adaptive Boosting)算法 [46]， 該算法的效率與 Freund[9]算法很接近，而且 可以很容易地應(yīng)用到實(shí)際問題中，因此，該算法已成為目前最流行的 Boosting 算法。 Boosting 算法介紹 Boosting[49]方法總的思想是學(xué)習(xí)一系列分類器，在這個(gè)系列中每一個(gè)分類器對它前一個(gè)分類器導(dǎo)致的錯(cuò)誤分類例子給予更大的重視。尤其是在學(xué)習(xí)完分類器之后，增加由之導(dǎo)致分類錯(cuò)誤的訓(xùn)練示例的權(quán)值，并通過重新對 訓(xùn)練示例計(jì)算權(quán)值，再學(xué)習(xí)下一個(gè)分類器。這個(gè)訓(xùn)練過程重復(fù)了次。最終的分類器從這一系列的分類器中綜合得出。在這個(gè)過程中，每個(gè)訓(xùn)練示例被賦予一個(gè)相應(yīng)的權(quán)值，如果一個(gè)訓(xùn)練示例被分類器錯(cuò)誤分類，那么就相應(yīng)增加該例子的權(quán)值，使得在下一次上海大學(xué)碩士學(xué)位論文 2022 年 5 月 15 學(xué)習(xí)中，分類器對該樣本示例代表的情況更加重視。 Boosting 是一種將弱分類器通過某種方式結(jié)合起來得到一個(gè)分類性能大大提高的強(qiáng)分類器的分類方法。這種方法將一些粗略的經(jīng)驗(yàn)規(guī)則轉(zhuǎn)變?yōu)楦叨葴?zhǔn)確的預(yù)測法則。強(qiáng)分類器對數(shù)據(jù)進(jìn)行分類，是通過弱分類器的多數(shù)投票機(jī)制進(jìn)行的。已經(jīng)有理論證明任何弱分類算法都能夠被有效地轉(zhuǎn)變或者提升為強(qiáng)學(xué)習(xí)分類算法。該算法其實(shí)是一個(gè)簡單的弱分類算法提升過程，這個(gè)過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能力。整個(gè)過程如下所示 : ? 先通過對 N 個(gè)訓(xùn)練數(shù)據(jù)的學(xué)習(xí)得到第一個(gè)弱分類器 h1。 ? 將 h1分錯(cuò)的數(shù)據(jù)和 其它 的新數(shù)據(jù)一起構(gòu)成一個(gè)新的有 N個(gè)訓(xùn)練數(shù)據(jù)的樣本，通過對這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器 h2。 ? 將 h1 和 h2 都分錯(cuò)了的數(shù)據(jù)加上 其它 的新數(shù)據(jù)構(gòu)成另一個(gè)新的有 N 個(gè)訓(xùn)練數(shù)據(jù)的樣本，通過對這個(gè)樣本的學(xué)習(xí)得到第三個(gè)弱分類器 h3。 ? 最終經(jīng)過提升的強(qiáng)分類器 1 2 3( , , )finalh M a jor it y V o te h h h? ? ?。即某個(gè)數(shù)據(jù)被分為哪一類要通過 1 2 3,h h h 的多數(shù)表決。 Adaboost 算法描述 對于 Boosting 算法，存在兩個(gè)問題 : 1. 如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練弱分類器得以進(jìn)行。 2. 如何將訓(xùn)練得到的各個(gè)弱分類器聯(lián)合起來