《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 決策森林研究綜述
決策森林研究綜述
2016年電子技術(shù)應(yīng)用第12期
黃海新1,吳 迪2,,文 峰1
1.沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院,,遼寧 沈陽110159,;2.沈陽理工大學(xué) 自動(dòng)化與電氣工程學(xué)院,,遼寧 沈陽110159
摘要: 隨著經(jīng)濟(jì)與社會(huì)的發(fā)展,,數(shù)據(jù)挖掘技術(shù)廣泛應(yīng)用到各個(gè)領(lǐng)域,,其中分類算法中的決策森林(Decision Forest)成為一個(gè)研究熱點(diǎn),。決策森林算法是一種包含多個(gè)決策樹分類器的統(tǒng)計(jì)學(xué)習(xí)理論,,能較好地處理噪聲且避免發(fā)生過擬合,。針對(duì)幾種典型的決策森林算法,闡述了其原理和算法的特點(diǎn),,并從決策森林的構(gòu)建過程出發(fā),,系統(tǒng)地分析和總結(jié)了國(guó)內(nèi)外現(xiàn)有的決策森林算法。在此基礎(chǔ)上,詳細(xì)說明了在面對(duì)大數(shù)據(jù)時(shí)應(yīng)用決策森林進(jìn)行分布式計(jì)算的處理過程,。通過比較,,總結(jié)出了各種決策森林算法的適用范圍。
中圖分類號(hào): TP301
文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2016.12.001
中文引用格式: 黃海新,,吳迪,,文峰. 決策森林研究綜述[J].電子技術(shù)應(yīng)用,2016,,42(12):5-9.
英文引用格式: Huang Haixin,,Wu Di,Wen Feng. Review of decision forest[J].Application of Electronic Technique,,2016,,42(12):5-9.
Review of decision forest
Huang Haixin1,Wu Di2,,Wen Feng1
1.Shenyang Ligong University,,College of Information Science and Engineering,Shenyang 110159,,China,; 2.Shenyang Ligong University,Automation and Electrical Engineering,,Shenyang 110159,,China
Abstract: With the development of economy and society, the Data Mining Technology runs through all areas widely. In which the forest decision of the classification algorithm has become a hot topic.Decision forest algorithm is statistics theory that combins the set of decision tree classification, can deal with noise and avoid over fitting surpassingly. This article mainly introduced the several classic methods of decision forest algorithm and their characteristics. Researching algorithms in domestic and overseas were analyzed and summarized systematically from the process of the construction of the decision forest. In the face of big data is described in detail application decision forest distributed computing process. By comparison,this article summarizes the applicable scope of various decision forest algorithm.
Key words : data mining technology;sampling,;decision forest,;classification;distributed computing,;decision tree

0 引言

    隨著日常生活和諸多領(lǐng)域中人們對(duì)數(shù)據(jù)處理需求的提高,,海量數(shù)據(jù)分類已經(jīng)成為現(xiàn)實(shí)生活中一個(gè)常見的問題。分類算法作為機(jī)器學(xué)習(xí)的主要算法之一,,是通過對(duì)已知類別的訓(xùn)練集進(jìn)行分析,,得到分類規(guī)則并用此規(guī)則來判斷新數(shù)據(jù)的類別,現(xiàn)已被醫(yī)療生物學(xué),、統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)等方面的學(xué)者提出,。同時(shí),近幾年大數(shù)據(jù)時(shí)代的到來,,傳統(tǒng)的分類算法如SVM,、貝葉斯算法、神經(jīng)網(wǎng)絡(luò),、決策樹等,,在實(shí)際應(yīng)用中難以解決高維數(shù)據(jù)和數(shù)量級(jí)別的數(shù)據(jù),。而決策森林在處理類似問題時(shí)會(huì)有較高的正確率及面對(duì)高維數(shù)據(jù)分類問題時(shí)的可擴(kuò)展性和并行性。Fernandez-Delgado[1]等人通過在121種數(shù)據(jù)集上比較了14種決策森林歸納算法的預(yù)測(cè)效果,,8種改進(jìn)隨機(jī)森林算法,,20種改進(jìn)更新權(quán)重抽樣算法,24種改進(jìn)無更新權(quán)重抽樣算法和11種其他的集成算法,,得出結(jié)論:隨機(jī)森林中的決策樹比其他的學(xué)習(xí)算法效果好很多,。目前,決策森林已在人工智能如AlphaGo,、推薦系統(tǒng),、圖像和視頻檢索中使用。

    本文基于的隨機(jī)森林算法分析其他幾種典型決策森林的特性及不同,,進(jìn)而說明了不同決策森林算法的適用范圍,。通過比較算法,根據(jù)使用者選取能解決問題的最適合的決策森林算法,。介紹了面向大數(shù)據(jù)時(shí),,基于決策森林的并行處理數(shù)據(jù)的方法。

1 決策樹

    決策樹算法是一種基于實(shí)例的算法,,常應(yīng)用于分類和預(yù)測(cè),。決策樹的構(gòu)建是一種自上而下的歸納過程,,用樣本的屬性作為節(jié)點(diǎn),,屬性的取值作為分支的樹形結(jié)構(gòu)。因此,,每棵決策樹對(duì)應(yīng)著從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一組規(guī)則,。決策樹的基本思想如圖1所示。

zs1-t1.gif

    決策樹的可視結(jié)構(gòu)是一棵倒置的樹狀,,它利用樹的結(jié)構(gòu)將數(shù)據(jù)進(jìn)行二分類,。其中樹的結(jié)構(gòu)中包含三種節(jié)點(diǎn),分別為:葉子節(jié)點(diǎn),、中間結(jié)點(diǎn),、根節(jié)點(diǎn)。

    對(duì)決策樹而言問題主要集中在剪枝和訓(xùn)練樣本的處理,。相對(duì)而言,,決策森林在提高了分類精度的同時(shí)解決了決策樹面臨的問題。決策森林由幾種決策樹的預(yù)測(cè)組合成一個(gè)最終的預(yù)測(cè),,其原理為應(yīng)用集成思想提高決策樹準(zhǔn)確率,。通過構(gòu)建森林,一棵決策樹的錯(cuò)誤可以由森林中的其他決策樹彌補(bǔ),。

2 決策森林構(gòu)建方法

2.1 Bootstrap aggregating

    Bagging(bootstrap aggregating)無權(quán)重抽樣通常用于產(chǎn)生全體模型,,尤其是在決策森林中,,是一種簡(jiǎn)單而有效的方法。森林中的每一棵決策樹從原始訓(xùn)練集中篩選出的數(shù)據(jù)作為訓(xùn)練集,。所有的樹都使用相同的學(xué)習(xí)算法進(jìn)行訓(xùn)練,,最后的預(yù)測(cè)結(jié)果由每棵樹的預(yù)測(cè)結(jié)果投票決定。由于有放回抽樣被使用,,一些原始數(shù)據(jù)可能出現(xiàn)不止一次而有些數(shù)據(jù)沒有被抽到,。為了確保在每個(gè)訓(xùn)練實(shí)例中有足夠數(shù)量的訓(xùn)練樣本,通常會(huì)設(shè)置每個(gè)樣本的原始訓(xùn)練集的大小,。無權(quán)重抽樣的一個(gè)最主要的優(yōu)點(diǎn)是在并行模式下容易執(zhí)行通過訓(xùn)練不同的處理程序的集成分類器,。

    通常情況下,bagging無權(quán)重抽樣產(chǎn)生一個(gè)組合模型,,這個(gè)模型比使用單一原始數(shù)據(jù)的模型效果好很多,。

    Breiman[2]指出無權(quán)重抽樣決策樹作為隨機(jī)森林算法中的特定實(shí)例,而隨機(jī)森林算法將會(huì)在下一節(jié)介紹,。

2.2 Adaptive boosting

    更新權(quán)重抽樣是一種提高弱學(xué)習(xí)機(jī)性能的方法,,這種算法通過反復(fù)地迭代不同分布的訓(xùn)練數(shù)據(jù)中的決策樹歸納算法。這些決策樹組合成為強(qiáng)集成森林,。該算法將預(yù)測(cè)精度較低的弱學(xué)習(xí)器提升為預(yù)測(cè)精度較高的強(qiáng)學(xué)習(xí)器,。與自舉法(bootstrapping)相同的是,更新權(quán)重抽樣方法同樣利用重采樣原理,,然而在每次迭代時(shí)卻不是隨機(jī)的選取樣本,,更新權(quán)重抽樣修改了樣本目的是想在每個(gè)連續(xù)的迭代中提高最有用的樣本。

    AdaBoost[3](Adaptive Boosting)是最受歡迎的更新權(quán)值抽樣算法,。AdaBoost是Boosting算法的一種,,它能夠自適應(yīng)地調(diào)節(jié)訓(xùn)練樣本權(quán)重分布,這個(gè)算法的主要思想是給在上一次迭代中錯(cuò)分的樹有較高的權(quán)值,。特別地,,這些錯(cuò)分的樹的權(quán)值越來越大而正確分類的那些樹的權(quán)值越來越小,這個(gè)迭代過程生成了一連串相互補(bǔ)充的決策樹,。

3 國(guó)內(nèi)外研究現(xiàn)狀

3.1 隨機(jī)森林(Random forest)

    隨機(jī)森林是最普通的決策森林,,這個(gè)算法在二十世紀(jì)90年代中期被提出,后來被Breiman[2]完善和推廣,。文獻(xiàn)[2]截至2016年4月的谷歌學(xué)術(shù)已經(jīng)被引用超過20 800次,,而這篇論文的受歡迎程度每年都增加的主要原因一方面是因?yàn)殡S機(jī)森林算法的簡(jiǎn)單,另一方面是因?yàn)樗念A(yù)測(cè)能力強(qiáng),。

    隨機(jī)森林算法中有大量的沒有修剪的隨機(jī)決策樹,,而這些決策樹的輸出是使用的一種無權(quán)重的多數(shù)投票。為了保證隨機(jī)森林的準(zhǔn)確性,,在決策樹歸納算法的建立過程中有2個(gè)隨機(jī)的過程:     

    (1)從訓(xùn)練集中無放回的挑選樣本,。雖然樣本都是從原始數(shù)據(jù)集中產(chǎn)生,,但每棵樹的訓(xùn)練數(shù)據(jù)集是不同的。

    (2)不是從所有的特征中選取最佳分裂點(diǎn),,而是隨機(jī)地從特征子集中取樣,,從中選取最佳分裂點(diǎn)。子集大小n是根據(jù)式(1)得出:

    zs1-gs1.gif

其中N是特征的數(shù)量,,近似得到,。

    最初隨機(jī)森林算法僅由決策樹組成。隨機(jī)森林是在樹的每個(gè)節(jié)點(diǎn)從不同屬性的子集中選擇一個(gè)特征,,其主要思想是替換更廣泛的“隨機(jī)子空間方法”[4],,此方法可以應(yīng)用于許多其他的算法例如支持向量機(jī)。盡管最近對(duì)于決策樹的隨機(jī)森林和隨機(jī)子空間的比較已經(jīng)表明在精確度方面前者要優(yōu)于后者[1],。

    尤其涉及到數(shù)字特征時(shí),,也存在將隨機(jī)性添加到?jīng)Q策樹歸納算法中的其他方法。例如代替使用所有的實(shí)例去決定為每個(gè)數(shù)字特性和使用實(shí)例的子樣本[5]的最佳分裂點(diǎn),,這些子樣本的特征是各不相同的,。使用這些特征和分裂點(diǎn)評(píng)價(jià)最優(yōu)化的分裂標(biāo)準(zhǔn),而評(píng)價(jià)標(biāo)準(zhǔn)是每個(gè)節(jié)點(diǎn)決策選擇的,。由于在每個(gè)節(jié)點(diǎn)分裂的樣本選取是不同的,,這項(xiàng)技術(shù)結(jié)果是由不同的樹組合成的集合體。另一種決策樹的隨機(jī)化方法是使用直方圖[6],。使用直方圖一直被認(rèn)為是使特征離散化的方法,,然而這樣對(duì)處理非常大的數(shù)據(jù)時(shí)能夠減少很多時(shí)間。作為代表性的是,,為每個(gè)特征創(chuàng)建直方圖,,每個(gè)直方圖的邊界被看作可能的分裂點(diǎn),。在這個(gè)過程中,,隨機(jī)化是在直方圖的邊界的一個(gè)區(qū)間內(nèi)隨機(jī)選取分裂點(diǎn)。

    由于隨機(jī)森林的流行,,隨機(jī)森林能被多種軟件語言實(shí)現(xiàn),,例如:Python、R語言,、Matlab和C語言,。

3.2 極端隨機(jī)森林(Extremely randomized forest)

    隨機(jī)森林選取最佳分裂屬性,而極端隨機(jī)森林[7]的最佳切割點(diǎn)是在隨機(jī)的特征子集中,。比較起來,,極端隨機(jī)森林的隨機(jī)性既在分裂的特征中又在它相應(yīng)的切割點(diǎn)中。為了選取分裂特征,,該算法隨機(jī)性表現(xiàn)為在被判斷為最好的特征中選取確定數(shù)目的特征,。除了數(shù)字特征以外,,該算法還在特征值域中統(tǒng)一地繪制隨機(jī)切點(diǎn),即切點(diǎn)選取那些完全隨機(jī)獨(dú)立的目標(biāo)屬性,。在極端情況下,,此算法在每個(gè)節(jié)點(diǎn)上隨機(jī)選取單屬性點(diǎn)和切割點(diǎn),因此一棵完全隨機(jī)化樹建立完成,。

    Geurts等人[7]指出獨(dú)立極端隨機(jī)樹往往有高偏差和方差的元素,,然而這些高方差元素能通過組合森林中大量的樹來相互抵消。

3.3 概率校正隨機(jī)森林

    一般地,,決策樹中的每個(gè)節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)是使用熵或者基尼指數(shù)進(jìn)行判斷,,這些判斷標(biāo)準(zhǔn)描述了相應(yīng)的節(jié)點(diǎn)分裂而沒有考慮節(jié)點(diǎn)的特性。概率校正隨機(jī)森林(Calibrated probabilities for random forest)[8]算法通過引入一個(gè)考慮分裂可能性的第二條件,,來提出一個(gè)提高隨機(jī)森林分類算法的分裂標(biāo)準(zhǔn),。提出的方法被直接應(yīng)用到離線學(xué)習(xí)的過程,因此分類階段保留了快速計(jì)算決策樹特征屬性取值的算法特征,。算法的改進(jìn)是直接在生成決策樹的過程中,,它沒有增加分類的計(jì)算時(shí)間。

    為了得到一個(gè)有識(shí)別力的可靠的分裂指標(biāo),,通過使用普拉特縮放(Platt Scaling)方法將Sigmoid函數(shù)引入特征空間,。因此,選取最佳分裂點(diǎn)不再只根據(jù)單一的標(biāo)準(zhǔn),,而是一種可靠的必須滿足更新最好分裂點(diǎn)的指標(biāo),。此外,這個(gè)指標(biāo)可以把隨機(jī)森林分類器更好地應(yīng)用到不同閾值的任務(wù)和數(shù)據(jù)集中,。

    該算法是用交通標(biāo)志識(shí)別的GTSRB數(shù)據(jù)集,、手寫數(shù)字識(shí)別的MNIST數(shù)據(jù)集和著名機(jī)器學(xué)習(xí)數(shù)據(jù)集(美國(guó)郵政總局?jǐn)?shù)據(jù)集、信件數(shù)據(jù)集和g50c數(shù)據(jù)集)進(jìn)行評(píng)估,。研究結(jié)果表明,本文提出的方法優(yōu)于標(biāo)準(zhǔn)隨機(jī)森林分類器,,尤其適用少量數(shù)目的樹。概率校正隨機(jī)森林基本流程圖如2所示,。

zs1-t2.gif

3.4 梯度提升決策樹

    梯度提升決策樹(Gradient boosted decision trees,,GBDT)[9]是更新權(quán)重抽樣算法的一種,最初用來解決回歸任務(wù),。與其他更新權(quán)重算法相同的是該算法計(jì)算一系列的回歸樹,,但卻以階段式方法構(gòu)建森林。特別地,,該算法計(jì)算一系列的回歸樹,,而回歸樹中的每一棵后續(xù)樹的主要目的是使預(yù)測(cè)偽殘差表現(xiàn)好的樹有任意可微的損失函數(shù)。樹中的每一片葉子在相應(yīng)區(qū)間最小化損失函數(shù),。通過使用適當(dāng)?shù)膿p失函數(shù),,傳統(tǒng)的更新權(quán)重抽樣的決策樹可也進(jìn)行分類任務(wù),。

    為了避免過擬合,在梯度更新權(quán)重抽樣森林中選擇適當(dāng)數(shù)量的樹(也就是迭代的次數(shù))是非常重要的,。迭代次數(shù)設(shè)置過高會(huì)導(dǎo)致過擬合,,而設(shè)置過低會(huì)導(dǎo)致欠擬合。選取最佳值的方法是嘗試在不同的數(shù)據(jù)集中比較不同森林大小的效果,。

    通過使用隨機(jī)梯度更新權(quán)重抽樣方法可以避免過擬合,。大體的思路是分別從訓(xùn)練集中選取隨機(jī)樣本并連續(xù)地訓(xùn)練樹。由于森林中的每棵樹是使用不同的樣本子集所建立的,,所以造成過擬合的概率將會(huì)降低,。

3.5 旋轉(zhuǎn)森林

    旋轉(zhuǎn)森林(Rotating forest)[10]是在3.1的基礎(chǔ)上進(jìn)行改進(jìn),添加了數(shù)據(jù)軸的一種算法,。旋轉(zhuǎn)森林中樹的多樣性是通過訓(xùn)練整個(gè)數(shù)據(jù)集中旋轉(zhuǎn)特征空間的每棵樹得到,。在運(yùn)行樹歸納算法之前旋轉(zhuǎn)數(shù)據(jù)軸將會(huì)建立完全不同的分類樹。除此之外在確保樹的多樣性同時(shí),,被旋轉(zhuǎn)的樹能降低對(duì)單變量樹的約束,,這些單變量樹能夠分解輸入空間到平行于原始特征軸的超平面。

    更具體的說,,是為森林中的每一棵樹使用特征提取的方法建立完整特征集,。首先隨機(jī)分離特征集到K個(gè)相互獨(dú)立的區(qū)間,之后分別在每個(gè)特征區(qū)間使用主成分分析法[11](Principal Component Analysis,,PCA),。PCA算法的思想是正交變換任何可能相關(guān)的特征到一個(gè)線性無關(guān)的特征集中。每個(gè)元素是原始數(shù)據(jù)線性組合,。且要保證第一主要元素具有最大方差,。其他的元素與原來的元素正交的條件下也具有較高方差。

    原始的數(shù)據(jù)集被線性轉(zhuǎn)變?yōu)樾碌挠?xùn)練集,,這些主要元素構(gòu)建一個(gè)新的特征集,。新的訓(xùn)練集是由新的特征空間所構(gòu)建的,被應(yīng)用到訓(xùn)練分類樹的樹歸納算法中,。值得注意的是,,不同的特征區(qū)間將會(huì)導(dǎo)致不同的變換特征集,因此建立了不同的分類樹,。這個(gè)旋轉(zhuǎn)森林算法已經(jīng)被應(yīng)用到MATLAB編碼的Weka工具。

    通過對(duì)旋轉(zhuǎn)森林的實(shí)驗(yàn)研究發(fā)現(xiàn)旋轉(zhuǎn)森林要比普通的隨機(jī)森林算法精度高,。然而旋轉(zhuǎn)森林有兩個(gè)缺點(diǎn),。第一,由于使用PCA算法旋轉(zhuǎn)隨機(jī)森林比普通隨機(jī)森林計(jì)算復(fù)雜度高,。另一個(gè)缺點(diǎn)是在新建立的樹中節(jié)點(diǎn)是變換后的特征而不是原始特征,。這令用戶更難理解樹,,因?yàn)闃渲械拿總€(gè)節(jié)點(diǎn)不是審查單一特征,用戶需要審查的是樹中每個(gè)節(jié)點(diǎn)上特征的一個(gè)線性組合,。

3.6 Safe-BayesianRandom Forest

    Novi Quadrianto 和Zoubin Ghahramani[12]提議利用從訓(xùn)練集中隨機(jī)選取的幾個(gè)樹的平均值進(jìn)行預(yù)測(cè),。從一個(gè)先驗(yàn)分布中隨機(jī)選取決策樹,對(duì)這些選取的樹進(jìn)行加權(quán)產(chǎn)生一個(gè)加權(quán)集合,。與其他的基于貝葉斯模型的決策樹不一樣的是,,需要用馬爾可夫鏈蒙特卡羅算法對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理。這個(gè)算法的框架利用數(shù)據(jù)中相互獨(dú)立的樹的先驗(yàn)性促進(jìn)線下決策樹的生成,。該算法的先驗(yàn)性在查看整體的數(shù)據(jù)之前從決策樹的集合中抽樣,。此外對(duì)于使用冪的可能性,這種算法通過集合的決策樹能夠計(jì)算距離間隔,。在無限大的數(shù)據(jù)的限制下給每一棵獨(dú)立的決策樹賦予一個(gè)權(quán)值,,這與基于貝葉斯的決策樹形成對(duì)比。

3.7 Switching classes

    Breiman[13]提出的一種決策森林,,該算法中的每棵決策樹使用帶有隨機(jī)分類標(biāo)簽的原始訓(xùn)練集,,每個(gè)訓(xùn)練樣本的類標(biāo)簽是根據(jù)過渡矩陣改變的。過渡矩陣確定了類被類替代的概率,,被選擇的改變概率是為了保持原始訓(xùn)練集的類分布,。

    Martínez-Munz和Suárez[14]指出當(dāng)森林是非常大的時(shí)候改變類的方法能使結(jié)果特別精確,而使用多類轉(zhuǎn)變建立的森林是不需要保持原始類的分布的,。在不平衡數(shù)據(jù)集中,,原始類分布松弛約束對(duì)于使用轉(zhuǎn)變類方法是非常重要的。每次迭代中原始數(shù)據(jù)集中隨機(jī)選取一個(gè)固定的部分,,這些選定實(shí)例的類是隨機(jī)切換的,。決策森林算法改進(jìn)過程如圖3所示。

zs1-t3.gif

4 決策森林算法比較

    參考文獻(xiàn)中嘗試了比較幾種不同的決策森林算法,。Dietterich[15]針對(duì)構(gòu)建C4.5決策森林比較了3種算法,,分別是隨機(jī)抽樣、無權(quán)重抽樣和更新權(quán)重抽樣,。實(shí)驗(yàn)表明當(dāng)數(shù)據(jù)中有少量噪聲時(shí),,更新權(quán)重抽樣預(yù)測(cè)效果最好,無權(quán)重抽樣和隨機(jī)抽樣有相同的效果,。

    另一個(gè)文獻(xiàn)比較了以更新權(quán)重抽樣為基礎(chǔ)的決策樹和以無更新權(quán)重為基礎(chǔ)的決策樹[16],。研究表明無更新權(quán)重抽樣減少了非穩(wěn)態(tài)法樣本的方差,而更新權(quán)重抽樣方法減小了非穩(wěn)態(tài)法樣本的方差和偏差但增加了穩(wěn)態(tài)法樣本的方差,。

    Villalba Santiago等人[17]為決策森林中建立決策樹的根節(jié)點(diǎn)對(duì)比了7種不同的更新權(quán)值抽樣算法,。他們得出結(jié)論,對(duì)于二項(xiàng)分類任務(wù)來說,大家眾所周知的AdaBoost算法(通過迭代弱分類器而產(chǎn)生最終的強(qiáng)分類器的算法)的效果更好,。然而對(duì)于多分類任務(wù)來說如GentleAdaBoost算法效果更好,。

    Banfield[18]等人用實(shí)驗(yàn)評(píng)估無更新權(quán)重抽樣和其他7種以隨機(jī)化為基礎(chǔ)的決策森林的算法。根據(jù)統(tǒng)計(jì)測(cè)試從57個(gè)公開的數(shù)據(jù)集獲得實(shí)驗(yàn)結(jié)果,。統(tǒng)計(jì)顯著性用交叉驗(yàn)證進(jìn)行對(duì)比,,得出57個(gè)數(shù)據(jù)集中只有8個(gè)比無更新權(quán)重抽樣精確,或在整組數(shù)據(jù)集上檢查算法的平均等級(jí),。Banfield等人總結(jié)出在更新權(quán)重抽樣算法的隨機(jī)森林中,,樹的數(shù)量是1 000棵時(shí)效果最好。

    除了預(yù)測(cè)效果也有其他的標(biāo)準(zhǔn),。根據(jù)使用者選取能解決問題的,、最適合的決策森林算法:

    (1)處理數(shù)據(jù)時(shí)適當(dāng)?shù)貙?duì)算法進(jìn)行設(shè)置:在處理具體的學(xué)習(xí)情況時(shí),不同的決策森林方法有不同的適用范圍,,例如不平衡的高維的多元的分類情況和噪聲數(shù)據(jù)集,。使用者首先需要的是描述學(xué)習(xí)任務(wù)的特征并相應(yīng)地選擇算法。

    (2)計(jì)算復(fù)雜度:生成決策森林的復(fù)雜成本以及實(shí)時(shí)性,,并且對(duì)新數(shù)據(jù)預(yù)測(cè)的時(shí)間要求,。通常梯度更新權(quán)重抽樣的迭代法會(huì)有較高的計(jì)算效率。

    (3)可擴(kuò)展性:決策森林算法對(duì)大數(shù)據(jù)有縮放的能力,。因此,,隨機(jī)森林和梯度更新權(quán)值抽樣樹有較好的可擴(kuò)展性。

    (4)軟件的有效性:現(xiàn)成的軟件數(shù)據(jù)包的數(shù)量,。這些數(shù)據(jù)包能提供決策森林的實(shí)現(xiàn)方法,,高度的有效性意味著使用者可以從一個(gè)軟件移動(dòng)到另一個(gè)軟件,不需要更換決策森林算法,。

    (5)可用性:提供一組控制參數(shù),,這些參數(shù)是廣泛性且易調(diào)節(jié)的。

5 決策森林應(yīng)用

    隨著通信信息系統(tǒng)收集到的數(shù)據(jù)數(shù)量的增長(zhǎng),,這些大規(guī)模數(shù)據(jù)集使得決策森林算法要提高其預(yù)測(cè)標(biāo)準(zhǔn),。然而對(duì)于任何數(shù)據(jù)學(xué)家,這些大規(guī)模數(shù)據(jù)的有效性是至關(guān)重要的,,因?yàn)檫@對(duì)學(xué)習(xí)算法的時(shí)間和存儲(chǔ)器提出了挑戰(zhàn),。大數(shù)據(jù)是近幾年被創(chuàng)造的專業(yè)術(shù)語,指的是使用現(xiàn)有算法難以處理的巨量資料集,。

    對(duì)于中小型數(shù)據(jù)集,,決策樹歸納算法計(jì)算復(fù)雜度是相對(duì)較低的。然而在大數(shù)據(jù)上訓(xùn)練密集森林仍有困難,??蓴U(kuò)展性指的是算法訓(xùn)練大數(shù)量數(shù)據(jù)能力的效率。

    近幾年來,,可擴(kuò)展性主要集中在像MapReduce和MPI的并行技術(shù)中,。MapReduce是數(shù)據(jù)挖掘技術(shù)中最普遍的并行編程框架算法之一,由谷歌開創(chuàng)并推廣的開源Apache Hadoop項(xiàng)目,。Map把一組鍵值對(duì)映射成一組新的鍵值對(duì),,處理鍵值對(duì)來生成過度鍵值對(duì)。指定并行Reduce函數(shù),,確保所有映射的鍵值對(duì)有相同的鍵組,。對(duì)于其他的并行編程架構(gòu)(例如CUDA和MPI),MapReduce已經(jīng)成為產(chǎn)業(yè)標(biāo)準(zhǔn),。已經(jīng)應(yīng)用于云計(jì)算服務(wù),,如亞馬遜的EC2和各類型公司的Cloudera服務(wù),它所提供的服務(wù)能緩解Hadoop壓力,。

    SMRF[19]是一種基于隨機(jī)森林算法改進(jìn)的,、可伸縮的、減少模型映射的算法,。這種算法使得數(shù)據(jù)在計(jì)算機(jī)集群或云計(jì)算的環(huán)境下,,能優(yōu)化多個(gè)參與計(jì)算數(shù)據(jù)的子集節(jié)點(diǎn)。SMRF算法是在基于MapReduce的隨機(jī)森林算法模型基礎(chǔ)上進(jìn)行改進(jìn),。SMRF在傳統(tǒng)的隨機(jī)森林相同準(zhǔn)確率的基礎(chǔ)上,,能處理分布計(jì)算環(huán)境來設(shè)置樹規(guī)模的大小。因此MRF比傳統(tǒng)的隨機(jī)森林算法更適合處理大規(guī)模數(shù)據(jù),。

    PLANET[20]是應(yīng)用于MapReduce框架的決策森林算法,。PLANET的基本思想是反復(fù)地生成決策樹,一次一層直到數(shù)據(jù)區(qū)間足夠小并能夠適合主內(nèi)存,,剩下的子樹可以在單個(gè)機(jī)器上局部地生長(zhǎng),。對(duì)于較高層次,PLANET的主要思想是分裂方法,。在一個(gè)不需要整個(gè)數(shù)據(jù)集的特定節(jié)點(diǎn),需要一個(gè)緊湊的充分統(tǒng)計(jì)數(shù)據(jù)結(jié)構(gòu),,這些數(shù)據(jù)結(jié)構(gòu)在大多數(shù)情況下可以適合內(nèi)存。

    Palit和Reddy[32]利用MapReduce框架開發(fā)出兩種并行更新權(quán)重抽樣算法:AdaBoost.PL和LogitBoost.PL,。根據(jù)預(yù)測(cè)結(jié)果,,這兩種算法與它們相應(yīng)的算法效果差不多。這些算法只需要一次循環(huán)MapReduce算法,,在它們自己的數(shù)據(jù)子集上的每個(gè)映射分別運(yùn)行AdaBoost算法以產(chǎn)生弱集合模型,。之后這些基本的模型隨著他們權(quán)重的減小被排序和傳遞,被減小的平均權(quán)值推導(dǎo)出整體最后的權(quán)值,。

    Del Río等人[21]提出用MapReduce來實(shí)現(xiàn)各種各樣的常規(guī)算法,。這些算法用隨機(jī)森林來處理不平衡的分類任務(wù)。結(jié)果表明,多數(shù)情況下映射數(shù)量的增加會(huì)使執(zhí)行時(shí)間減少,,而太多的映射會(huì)導(dǎo)致更糟糕的結(jié)果,。

    各種分布的隨機(jī)森林是可以實(shí)現(xiàn)的,尤其在Mahout中,,這只是一個(gè)Apache項(xiàng)目,。Apache項(xiàng)目是可以提供免費(fèi)的可擴(kuò)展的機(jī)器學(xué)習(xí)算法程序包,包括在Hadoop框架下實(shí)現(xiàn)隨機(jī)森林的包,。MLLib一個(gè)分布式機(jī)器學(xué)習(xí)框架,,提供了在Spark框架下實(shí)現(xiàn)隨機(jī)森林和梯度提升樹的包。

6 結(jié)論

    決策森林主要目的是通過訓(xùn)練多個(gè)決策樹來改善單一決策樹的預(yù)測(cè)性能,。當(dāng)前決策森林的研究趨勢(shì)是:解決大數(shù)據(jù)而實(shí)現(xiàn)分布式開發(fā),;改進(jìn)現(xiàn)有的分類和回歸的決策森林算法來處理各種各樣的任務(wù)和數(shù)據(jù)集。

    目前國(guó)內(nèi)對(duì)于決策森林的研究很多是針對(duì)隨機(jī)森林的,,但卻對(duì)決策森林的其他算法研究得比較少,。

參考文獻(xiàn)

[1] Fernández-Delgado M,Cernadas E,,Barro S,,et al.Do we need hundreds of classifiers to solve real world classification problems?[J].J Mach.Learn.Res.2014,15(1):3133-3181.

[2] BREIMAN L.Random forests[J].Machine Learning,,2001,,45(1):5-32.

[3] 錢志明,徐丹.一種Adaboost快速訓(xùn)練算法[J].計(jì)算機(jī)工程,,2009,,35(20):187-188.

[4] HO T K.The random subspace method for constructing decision forests[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1998,,20(8):832-844.

[5] KAMATH C,,CANTU-PAZ E.Creating ensembles of decision trees through sampling: US, US 6938049 B2[P].2005.

[6] KAMATH C,Cantú-Paz E,,LITTAU D.Approximate splitting for ensembles of trees using histograms[C]//Proc.siam Int’l Conf.data Mining,,2002.

[7] GEURTS P,ERNST D,,WEHENKEL L.Extremely randomized trees[J].Mach.Learn.2006,,63(1):3-42.

[8] BAUMANN F,CHEN J,,VOGT K,,et al.Improved threshold selection by using calibrated probabilities for random forest classifiers[C].Computer and Robot Vision(CRV),2015 12th Conference on.IEEE,,2015:155-160.

[9] FRIEDMAN J H.Greedy function approximation:a gradient boosting machine[J].Annals of Statistics,,2000,,29(5):1189-1232.

[10] Rodríguez J J,Kuncheva L I,,Alonso C J.Rotation forest:A new classifier ensemble method[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,,2006,28(10):1619-1630.

[11] 王景中,,李萌.基于輪廓PCA的字母手勢(shì)識(shí)別算法研究[J].電子技術(shù)應(yīng)用,,2014,,40(11):126-128.

[12] NOVI Q,,ZOUBIN G.A very simple safe-bayesian random forest[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2015,,37(6):1297-1303.

[13] BREIMAN L.Randomizing outputs to increase prediction accuracy[J].Machine Learning,,2000,40(3):229-242.

14-21略

此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載,。