0 引言

    隨著日常生活和諸多領(lǐng)域中人們對數(shù)據(jù)處理需求的提高，海量數(shù)據(jù)分類已經(jīng)成為現(xiàn)實(shí)生活中一個(gè)常見的問題。分類算法作為機(jī)器學(xué)習(xí)的主要算法之一，是通過對已知類別的訓(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ì)有較高的正確率及面對高維數(shù)據(jù)分類問題時(shí)的可擴(kuò)展性和并行性。Fernandez-Delgado^[1]等人通過在121種數(shù)據(jù)集上比較了14種決策森林歸納算法的預(yù)測效果，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ù)測。決策樹的構(gòu)建是一種自上而下的歸納過程，用樣本的屬性作為節(jié)點(diǎn)，屬性的取值作為分支的樹形結(jié)構(gòu)。因此，每棵決策樹對應(yīng)著從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一組規(guī)則。決策樹的基本思想如圖1所示。

    決策樹的可視結(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)。

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

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

2.1 Bootstrap aggregating

    Bagging(bootstrap aggregating)無權(quán)重抽樣通常用于產(chǎn)生全體模型，尤其是在決策森林中，是一種簡單而有效的方法。森林中的每一棵決策樹從原始訓(xùn)練集中篩選出的數(shù)據(jù)作為訓(xùn)練集。所有的樹都使用相同的學(xué)習(xí)算法進(jìn)行訓(xùn)練，最后的預(yù)測結(jié)果由每棵樹的預(yù)測結(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ù)測精度較低的弱學(xué)習(xí)器提升為預(yù)測精度較高的強(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 國內(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ī)森林算法的簡單，另一方面是因?yàn)樗念A(yù)測能力強(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)得出：

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

    最初隨機(jī)森林算法僅由決策樹組成。隨機(jī)森林是在樹的每個(gè)節(jié)點(diǎn)從不同屬性的子集中選擇一個(gè)特征，其主要思想是替換更廣泛的“隨機(jī)子空間方法”^[4]，此方法可以應(yīng)用于許多其他的算法例如支持向量機(jī)。盡管最近對于決策樹的隨機(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)為是使特征離散化的方法，然而這樣對處理非常大的數(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ù)集（美國郵政總局?jǐn)?shù)據(jù)集、信件數(shù)據(jù)集和g50c數(shù)據(jù)集）進(jìn)行評(píng)估。研究結(jié)果表明,本文提出的方法優(yōu)于標(biāo)準(zhǔn)隨機(jī)森林分類器，尤其適用少量數(shù)目的樹。概率校正隨機(jī)森林基本流程圖如2所示。

3.4 梯度提升決策樹

    梯度提升決策樹(Gradient boosted decision trees，GBDT)^[9]是更新權(quán)重抽樣算法的一種，最初用來解決回歸任務(wù)。與其他更新權(quán)重算法相同的是該算法計(jì)算一系列的回歸樹，但卻以階段式方法構(gòu)建森林。特別地，該算法計(jì)算一系列的回歸樹，而回歸樹中的每一棵后續(xù)樹的主要目的是使預(yù)測偽殘差表現(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)的樹能降低對單變量樹的約束，這些單變量樹能夠分解輸入空間到平行于原始特征軸的超平面。

    更具體的說，是為森林中的每一棵樹使用特征提取的方法建立完整特征集。首先隨機(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工具。

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

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ù)集中，原始類分布松弛約束對于使用轉(zhuǎn)變類方法是非常重要的。每次迭代中原始數(shù)據(jù)集中隨機(jī)選取一個(gè)固定的部分，這些選定實(shí)例的類是隨機(jī)切換的。決策森林算法改進(jìn)過程如圖3所示。

4 決策森林算法比較

    參考文獻(xiàn)中嘗試了比較幾種不同的決策森林算法。Dietterich^[15]針對構(gòu)建C4.5決策森林比較了3種算法，分別是隨機(jī)抽樣、無權(quán)重抽樣和更新權(quán)重抽樣。實(shí)驗(yàn)表明當(dāng)數(shù)據(jù)中有少量噪聲時(shí)，更新權(quán)重抽樣預(yù)測效果最好，無權(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)對比了7種不同的更新權(quán)值抽樣算法。他們得出結(jié)論，對于二項(xiàng)分類任務(wù)來說，大家眾所周知的AdaBoost算法（通過迭代弱分類器而產(chǎn)生最終的強(qiáng)分類器的算法)的效果更好。然而對于多分類任務(wù)來說如GentleAdaBoost算法效果更好。

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

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

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

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

    (3)可擴(kuò)展性：決策森林算法對大數(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ù)量的增長，這些大規(guī)模數(shù)據(jù)集使得決策森林算法要提高其預(yù)測標(biāo)準(zhǔn)。然而對于任何數(shù)據(jù)學(xué)家，這些大規(guī)模數(shù)據(jù)的有效性是至關(guān)重要的，因?yàn)檫@對學(xué)習(xí)算法的時(shí)間和存儲(chǔ)器提出了挑戰(zhàn)。大數(shù)據(jù)是近幾年被創(chuàng)造的專業(yè)術(shù)語，指的是使用現(xiàn)有算法難以處理的巨量資料集。

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

    近幾年來，可擴(kuò)展性主要集中在像MapReduce和MPI的并行技術(shù)中。MapReduce是數(shù)據(jù)挖掘技術(shù)中最普遍的并行編程框架算法之一，由谷歌開創(chuàng)并推廣的開源Apache Hadoop項(xiàng)目。Map把一組鍵值對映射成一組新的鍵值對，處理鍵值對來生成過度鍵值對。指定并行Reduce函數(shù)，確保所有映射的鍵值對有相同的鍵組。對于其他的并行編程架構(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ī)器上局部地生長。對于較高層次，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ù)測結(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ù)測性能。當(dāng)前決策森林的研究趨勢是：解決大數(shù)據(jù)而實(shí)現(xiàn)分布式開發(fā)；改進(jìn)現(xiàn)有的分類和回歸的決策森林算法來處理各種各樣的任務(wù)和數(shù)據(jù)集。

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

參考文獻(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í)別算法研究[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略