【文章內(nèi)容簡介】 字符識別、醫(yī)學(xué)診斷和語音識別等廣闊領(lǐng)域[36,37]。決策樹分類算法使用訓(xùn)練樣本集合構(gòu)造出一棵決策樹，從而實現(xiàn)了對樣本空間的劃分。當(dāng)使用決策樹對未知樣本進(jìn)行分類時，由根結(jié)點開始對該樣本的屬性逐漸測試其值，并且順著分枝向下走，直到到達(dá)某個葉結(jié)點，此葉結(jié)點代表的類即為該樣本的類。例如，它將整個樣本空間分為三類。如果一個樣本屬性A的取值為a2,屬性B的取值為b2，屬性C的取值為c1那么它屬于類1[38]。 一顆決策樹實例為了避免過度擬和現(xiàn)象的出現(xiàn)，在決策樹的生成階段要對決策樹進(jìn)行必要修剪。常用的修剪技術(shù)有預(yù)修剪(prepruning)和后修剪(postpruning)兩種。決策樹的質(zhì)量更加依靠好的停止規(guī)則而不是劃分規(guī)則。[39]獲取大小合適的樹常用的方法是后剪枝。后剪枝法主要有①訓(xùn)練和驗證集法，②使用統(tǒng)計的方法，③最小描述長度準(zhǔn)則。其它的剪枝方法有：①限制最小結(jié)點規(guī)模，②兩階段研究，③不純度的閥值，④將樹轉(zhuǎn)變?yōu)橐?guī)則，⑤Tree reduction。沒有一種剪枝方法明顯優(yōu)于其它方法。尋找一棵最優(yōu)決策樹主要解決以下三個最優(yōu)化問題:①生成最少數(shù)目的葉子，②生成的每個葉子的深度最小，③生成的決策樹葉子最少且每個葉子的深度最小。以上三個問題均已被證明為NP難題，所以,決策樹算法一般只能找到一棵近似最優(yōu)決策樹[40]。常用的決策樹算法由CART，ID3，隨機樹算法，在下面，對本文中用到的決策樹算法進(jìn)行了詳細(xì)介紹。 [41]設(shè)S為訓(xùn)練集樣本總數(shù)，共有m類樣本，Si為類Ci中的樣本數(shù)，計算公式為： () 其中，其中pi是任意樣本屬于Ci的概率，可用Si/S來估計。 設(shè)屬性X具有v個值，它將S分成v個子集，其中Sj包含S中這樣的一些樣本，它們在屬性X上具有值。以屬性X為分類所需的期望熵（條件熵）是： ()其中sij是子集Sj中屬于類Ci的樣本數(shù)， ，是sj中的樣本屬于Ci的概率。屬性X的信息增益函數(shù)為： ()信息增益函數(shù)對于那些可能產(chǎn)生多分枝的測試傾向于生產(chǎn)大的函數(shù)值，但是輸出分枝多，并不表示該測試對末知的對象具有更好的預(yù)測效果，信息增益率函數(shù)可以彌補這個缺陷“信息增益率”是為了去除多分枝屬性的影響而對信息增益的一種改進(jìn)。使用“信息增益率函數(shù)”，它同時考慮了每一次劃分所產(chǎn)生的子結(jié)點的個數(shù)和每個子結(jié)點的大?。ò臄?shù)據(jù)實例的個數(shù)），考慮的對象主要是一個個地劃分，而不再考慮分類所蘊涵的信息量，屬性X的信息增益函數(shù)為： ()其中v為該節(jié)點的分枝數(shù)，si為第i個分枝下的記錄個數(shù)。依次計算每個屬性的信息增益Gain(X)以及信息增益率A(X)，選取信息增益率最大的，但同時獲取的信息增益又不低于所有屬性平均值的屬性作為測試屬性，以該屬性作為結(jié)點，屬性的每一個分布引出一個分枝，據(jù)此劃分樣本。要是節(jié)點中所有樣本都在同一個類，則該節(jié)點成為樹葉，以該客戶類別標(biāo)記該樹葉。如此類推，直到子集中的數(shù)據(jù)記錄在主屬性上取值都相同，或沒有屬性可再供劃分使用，遞歸地形成初始決策樹。另外，在節(jié)點處記下符合條件的統(tǒng)計數(shù)據(jù)：該分枝總數(shù)、有效數(shù)、中止數(shù)和失效數(shù)。之所以選取信息增益率大而信息增益不低于平均值的屬性，是因為高信息增益率保證了高分枝屬性不會被選取，從而決策樹的樹型不會因某節(jié)點分枝太多而過于松散。過多的分枝會使得決策樹過分地依賴某一屬性，而信息增益不低于平均值保證了該屬性的信息量，使得有利于分類的屬性更早地出現(xiàn)。得到了完全生長的初始決策樹后，為了除去噪聲數(shù)據(jù)和孤立點引起的分枝異常，可采用后剪枝算法對生成的初始決策樹進(jìn)行剪枝，并在剪枝過程中使用一種悲觀估計來補償樹生成時的樂觀偏差。對決策樹上的每個非葉子結(jié)點，計算該分枝節(jié)點上的子樹被剪枝可能出現(xiàn)的期望錯誤率。然后，使用每個分枝的錯誤率，結(jié)合沿每個分枝觀察的權(quán)重評估，計算不對該節(jié)點剪枝的期望錯誤率。如果剪去該節(jié)點導(dǎo)致較高的期望錯誤率，則保留該子樹；否則剪去該子樹，最后得到具有最小期望錯誤率的決策樹。 隨機決策樹算法[42] 設(shè)屬性集為建樹提供結(jié)構(gòu)，其中是非決策屬性，決策屬性是一列有效的類別。表示記錄x的屬性Fi的值,具體結(jié)構(gòu)描述如下：樹中的每個結(jié)點表示一個問題。每個分支對應(yīng)結(jié)點分裂屬性Fi的可能取值。隨機決策樹的構(gòu)造過程:對根結(jié)點和分支結(jié)點隨機的從屬性集合中選擇分裂屬性,在一條分支路徑上離散屬性僅出現(xiàn)一次,連續(xù)屬性可以出現(xiàn)多次。且在以下3種情況下停止樹的構(gòu)造：樹的高度滿足預(yù)先設(shè)定的閾值。分支結(jié)點的事例數(shù)太小以至于不能給出一個有統(tǒng)計意義的測試。其它任何一個屬性測試都不能更好地分類。在后2種情況下,分類結(jié)果標(biāo)記為訓(xùn)練數(shù)據(jù)集中最普通的類,或是出現(xiàn)概率最高的類。當(dāng)對事例X進(jìn)行分類時,以各隨機樹輸出的后驗概率均值最大的類為預(yù)測類。下面詳細(xì)介紹隨機決策樹的深度選擇和數(shù)目的選擇及其分類。(1)選擇樹的深度。使用多個隨機樹的主要特色是多樣性導(dǎo)致較高的分類準(zhǔn)確率,多樣性不與深度成正比關(guān)系。研究表明,當(dāng)i=k/2時得到最大路徑數(shù),隨機決策樹有最佳的效果。(2)選擇隨機決策樹的個數(shù)。樹的個數(shù)N=10時有較低的分類錯誤率,%。 (3)葉子結(jié)點的更新。在樹的結(jié)構(gòu)建好后對樹結(jié)點更新,其中葉子結(jié)點記錄事例被分類為某一預(yù)定類別的個數(shù)。非葉子結(jié)點不記錄經(jīng)過分支的事例數(shù)目,葉子中信息形式如:。其中,si表示預(yù)測為di類的事例數(shù), 表示決策屬性類別。表示某一葉子結(jié)點記錄的總事例數(shù)。 (4)分類。當(dāng)對事例進(jìn)行分類時,預(yù)測為預(yù)定類別di的概率。其中,N表示隨機決策樹的數(shù)目。為每棵隨機決策樹輸出的后驗概率。S為從根結(jié)點開始搜索到合適葉子結(jié)點處的事例個數(shù)。Si為該葉子結(jié)點處訓(xùn)練數(shù)據(jù)集中標(biāo)記為di類的數(shù)目。在后驗概率Pi中找出最大的一個,其所對應(yīng)的預(yù)定類別即為隨機決策樹最終的輸出結(jié)果。由于完全隨機的選擇屬性,因而可能會出現(xiàn)某些屬性在整個決策樹構(gòu)造過程中沒有或很少被選取為分裂屬性,特別是當(dāng)該屬性對分類結(jié)果有較大貢獻(xiàn)時,這種缺少將導(dǎo)致分類正確率的不穩(wěn)定,當(dāng)屬性數(shù)較少時,這種不穩(wěn)定性將更為明顯。 隨機森林算法[43] 在決策樹算法中,一般用選擇分裂屬性和剪枝來控制樹的生成,但是當(dāng)數(shù)據(jù)中噪聲或分裂屬性過多時,它們也解決不了樹不平衡。最新的研究表明[6],構(gòu)造多分類器的集成,. 為了構(gòu)造k棵樹,我們得先產(chǎn)生k個隨機向量，這些隨機向量是相互獨立并且是同分布。隨機向量可構(gòu)造決策分類樹，簡化為。給定k個分類器和隨機向量x、y,定義邊緣函數(shù) ()其中是示性函數(shù)。該邊緣函數(shù)刻畫了對向量X正確分類y的平均得票數(shù)超過其它任何類平均得票數(shù)的程度。可以看出,邊際越大分類的置信度就越高。于是，分類器的泛化誤差 ()其中下標(biāo)X,Y代表的是該誤差是在X,Y空間下的。將上面的結(jié)論推廣到隨機森林,。如果森林中的樹的數(shù)目較大，隨著樹的數(shù)目增加,對所有隨機向量趨向于 ()這是隨機森林的一個重要特點，并且隨著樹的增加，泛化誤差將趨向一上界，這表明隨機森林對未知的實例有很好的擴展。隨機森林的泛化誤差上界的定義為 ()其中是相關(guān)系數(shù)的均值,s是樹的分類強度。隨機森林的泛化誤差上界可以根據(jù)兩個參數(shù)推導(dǎo)出來：森林中每棵決策樹的分類精度即樹的強度S,和這些樹之間的相互依賴程度。當(dāng)隨機森林中各個分類器的相關(guān)程度增大時，泛化誤差上界就增大；當(dāng)各個分類器的分類強度增大時，泛化誤差上界就增大。正確理解這兩者之間的相互影響是我們理解隨機森林工作原理的基礎(chǔ).. 集成學(xué)習(xí)算法 集成學(xué)習(xí)(Ensemble Learning)是一種新的機器學(xué)習(xí)范式，它使用多個(通常是同質(zhì)的)學(xué)習(xí)器來解決同一個問題。由于集成學(xué)習(xí)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國際機器學(xué)習(xí)界的研究熱點。 集成學(xué)習(xí)算法概述 在機器學(xué)習(xí)領(lǐng)域，最早的集成學(xué)習(xí)方法是Bayesian Averaging。在此之后，集成學(xué)習(xí)的研究才逐漸引起了人們的關(guān)注。[44]使用一組神經(jīng)網(wǎng)絡(luò)來解決問題，除了按常規(guī)的做法選擇出最好的神經(jīng)網(wǎng)絡(luò)之外，他們還嘗試通過投票法將所有的神經(jīng)網(wǎng)絡(luò)結(jié)合起來求解。他們的實驗結(jié)果表明，這一組神經(jīng)網(wǎng)絡(luò)形成的集成，比最好的個體神經(jīng)網(wǎng)絡(luò)的性能還好。正是這一超乎人們直覺的結(jié)果，使得集成學(xué)習(xí)引起了很多學(xué)者的重視。1990年，Schapire[45]通過一個構(gòu)造性方法對弱學(xué)習(xí)算法與強學(xué)習(xí)算法是否等價的問題作了肯定的證明，證明多個弱分類器可以集成為一個強分類器，他的工作奠定了集成學(xué)習(xí)的理論基礎(chǔ)。這個構(gòu)造性方法就是Boosting算法的雛形。但是這個算法存在著一個重大的缺陷，就是必須知道學(xué)習(xí)算法正確率的下限，這在實際中很難做到。在1995年，F(xiàn)reund和Schapire[46]做了進(jìn)一步工作，提出了AdBaoost算法，該算法不再要求事先知道泛化下界，可以非常容易的應(yīng)用到實際的問題中去。1996年，Breiman[46]提出了與Boosting相似的技術(shù)Bagging，進(jìn)一步促進(jìn)了集成學(xué)習(xí)的發(fā)展。 狹義地說，集成學(xué)習(xí)是指利用多個同質(zhì)的學(xué)習(xí)器來對同一個問題進(jìn)行學(xué)習(xí)，這里的“同質(zhì)”是指所使用的學(xué)習(xí)器屬于同一種類型，例如所有的學(xué)習(xí)器都是決策樹、都是神經(jīng)網(wǎng)絡(luò)等等。廣義地來說，只要是使用多個學(xué)習(xí)器來解決問題，就是集成學(xué)習(xí)[47,48]。在集成學(xué)習(xí)的早期研究中，狹義定義采用得比較多，而隨著該領(lǐng)域的發(fā)展，越來越多的學(xué)者傾向于接受廣義定義。所以在廣義的情況下，集成學(xué)習(xí)已經(jīng)成為了一個包含內(nèi)容相當(dāng)多的、比較大的研究領(lǐng)域。 大致上來說，集成學(xué)習(xí)的構(gòu)成方法可以分為四種:1. 輸入變量集重構(gòu)法。這種構(gòu)成方法，用于集成的每個算法的輸入變量是原變量集的一個子集。這種方法比較適用于輸入變量集高度冗余的時候，否則的話，選取一個屬性子集，會影響單個算法的性能，最終影響集成的結(jié)果。2. 輸出變量集重構(gòu)法。這種構(gòu)成方法，主要是通過改變輸出變量集，將多分類問題轉(zhuǎn)換為二分類問題來解決。3. 樣本集重新抽樣法。在這種構(gòu)成方法中，用于集成的每個算法所對應(yīng)的訓(xùn)練數(shù)據(jù)都是原來訓(xùn)練數(shù)據(jù)的一個子集。目前的大部分研究主要集中在使用這種構(gòu)成方法來集成學(xué)習(xí)，如Bagging，Boosting等等。樣本集重新抽樣法對于不穩(wěn)定的算法來說，能夠取得很好的效果。不穩(wěn)定的算法指的是當(dāng)訓(xùn)練數(shù)據(jù)發(fā)生很小變化的時候，結(jié)果就能產(chǎn)生很大變化的算法。如神經(jīng)網(wǎng)絡(luò)、決策樹。但是對于穩(wěn)定的算法來說，效果不是很好。4. 參數(shù)選擇法。對于許多算法如神經(jīng)網(wǎng)絡(luò)、遺傳算法來說，在算法應(yīng)用的開始首先要解決的就是要選擇算法參數(shù)。而且，由于這些算法操作過程的解釋性很差，對于算法參數(shù)的選擇沒有確定的規(guī)則可依。在實際應(yīng)用中，就需要操作者根據(jù)自己的經(jīng)驗進(jìn)行選擇。在這樣的情況下，不同的參數(shù)選擇，最終的結(jié)果可能會有很大的區(qū)別，具有很大的不穩(wěn)定性。集成算法的作用主要體現(xiàn)在如下四個方面：1. 提高預(yù)測結(jié)果的準(zhǔn)確性。機器學(xué)習(xí)的一個重要目標(biāo)就是對新的測試樣本盡可能給出最精確的估計。構(gòu)造單個高精度的學(xué)習(xí)器是一件相當(dāng)困難的事情，然而產(chǎn)生若干個只比隨機猜想略好的學(xué)勻器卻很容易。研究者們在應(yīng)用研究中發(fā)現(xiàn)，將多個學(xué)習(xí)器進(jìn)行集成后得到的預(yù)測精度明顯高于單個學(xué)習(xí)器的精度，甚至比單個最好的學(xué)習(xí)器的精度更高。2. 提高預(yù)測結(jié)果的穩(wěn)定性。有些學(xué)習(xí)算法單一的預(yù)測結(jié)果時好時壞，不具有穩(wěn)定性，不能一直保持高精度的預(yù)測。通過模型的集成，可以在多種數(shù)據(jù)集中以較高的概率普遍取得很好的結(jié)果。3. 解決過擬合問題。在對己知的數(shù)據(jù)集合進(jìn)行學(xué)習(xí)的時候，我們常常選擇擬合度值最好的一個模型作為最后的結(jié)果。也許我們選擇的模型能夠很好的解釋訓(xùn)練數(shù)據(jù)集合，但是卻不能很好的解釋測試數(shù)據(jù)或者其它數(shù)據(jù)，也就是說這個模型過于精細(xì)的刻畫了訓(xùn)練數(shù)據(jù)，對于測試數(shù)據(jù)或者其它新的數(shù)據(jù)泛化能力不強，這種現(xiàn)象就稱為過擬合。為了解決過擬合問題，按照集成學(xué)習(xí)的思想，可以選擇多個模型作為結(jié)果，對于每個模型賦予相應(yīng)的權(quán)重，從而集合生成合適的結(jié)果，提高預(yù)測精度。4. 改進(jìn)參數(shù)選擇。對于一些算法而言，如神經(jīng)網(wǎng)絡(luò)、遺傳算法，在解決實際問題的時候，需要選擇操作參數(shù)。但是這些操作參數(shù)的選取沒有確定性的規(guī)則可以依據(jù)，只能憑借經(jīng)驗來選取，對于非專業(yè)的一般操作人員會有一定的難度。而且參數(shù)選擇不同，結(jié)果會有很大的差異。通過建立多個不同操作參數(shù)的模型，可以解決選取參數(shù)的難題，同時將不同模型的結(jié)果按照一定的方式集成就可以生成我們想要的結(jié)果。集成學(xué)習(xí)經(jīng)過了十幾年的不斷發(fā)展，各種不同的集成學(xué)習(xí)算法不斷被提了出來，其中以Boosting和Bagging的影響最大。這兩種算法也是被研究得最多的，它們都是通過改造訓(xùn)練樣本集來構(gòu)造集成學(xué)習(xí)算法。在下面的章節(jié)中對這兩種算法進(jìn)行了詳細(xì)的介紹。 AdaBoost算法 Kearns和Valiant指出[48]，在PCA學(xué)習(xí)模型中，若存在一個多項式級學(xué)習(xí)算法來識別一組概念，并且識別正確率很高，那么這組概念是強可學(xué)習(xí)的；而如果學(xué)習(xí)算法識別一組概念的正確率僅比隨機猜測略好，那么這組概念是弱可學(xué)習(xí)的。Kaerns和valiant提出了弱學(xué)習(xí)算法與強學(xué)習(xí)算法的等價性問題，即是否可以將弱學(xué)習(xí)算法提升成強學(xué)習(xí)算法的問題。如果兩者等價，那么在學(xué)習(xí)概念時，只要找到一個比隨機猜測略好的弱學(xué)習(xí)算法，就可以將其提升為強學(xué)習(xí)算法，而不必直接去找通常情況下很難獲得的強學(xué)習(xí)算法。1990年，schapire[49] 通過一個構(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ò)錯誤判斷的示例將以較大的概率出現(xiàn)在新網(wǎng)絡(luò)的訓(xùn)練集中。這樣，新網(wǎng)絡(luò)將能夠很好地處理對己有網(wǎng)絡(luò)來說很困難的示例。另一方面，雖然Boosting方法能夠增強神經(jīng)網(wǎng)絡(luò)集成的泛化能力，但是同時也有可能使集成過分偏向于某幾個特別困難的示例。因此，該方法不太穩(wěn)定，有時能起到很好的作用，有時卻沒有效果。1995年，F(xiàn)reund和schapire提出了AdaBoost (Adaptive Boosting)算法[46]，該算法的效率與Freund[9]算法很接近，而且可以很容易地應(yīng)用到實際問題中，因此，該算法已成為目前最流行的Boosting算法。 Boosting算法介紹 Boosting[49]方法總的思想是學(xué)