0 引言

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

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

1 決策樹

    決策樹算法是一種基于實例的算法，常應用于分類和預測。決策樹的構建是一種自上而下的歸納過程，用樣本的屬性作為節點，屬性的取值作為分支的樹形結構。因此，每棵決策樹對應著從根節點到葉節點的一組規則。決策樹的基本思想如圖1所示。

    決策樹的可視結構是一棵倒置的樹狀，它利用樹的結構將數據進行二分類。其中樹的結構中包含三種節點，分別為：葉子節點、中間結點、根節點。

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

2 決策森林構建方法

2.1 Bootstrap aggregating

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

    通常情況下，bagging無權重抽樣產生一個組合模型，這個模型比使用單一原始數據的模型效果好很多。

    Breiman^[2]指出無權重抽樣決策樹作為隨機森林算法中的特定實例，而隨機森林算法將會在下一節介紹。

2.2 Adaptive boosting

    更新權重抽樣是一種提高弱學習機性能的方法，這種算法通過反復地迭代不同分布的訓練數據中的決策樹歸納算法。這些決策樹組合成為強集成森林。該算法將預測精度較低的弱學習器提升為預測精度較高的強學習器。與自舉法（bootstrapping）相同的是，更新權重抽樣方法同樣利用重采樣原理，然而在每次迭代時卻不是隨機的選取樣本，更新權重抽樣修改了樣本目的是想在每個連續的迭代中提高最有用的樣本。

    AdaBoost^[3](Adaptive Boosting)是最受歡迎的更新權值抽樣算法。AdaBoost是Boosting算法的一種，它能夠自適應地調節訓練樣本權重分布，這個算法的主要思想是給在上一次迭代中錯分的樹有較高的權值。特別地，這些錯分的樹的權值越來越大而正確分類的那些樹的權值越來越小，這個迭代過程生成了一連串相互補充的決策樹。

3 國內外研究現狀

3.1 隨機森林(Random forest)

    隨機森林是最普通的決策森林，這個算法在二十世紀90年代中期被提出，后來被Breiman^[2]完善和推廣。文獻[2]截至2016年4月的谷歌學術已經被引用超過20 800次，而這篇論文的受歡迎程度每年都增加的主要原因一方面是因為隨機森林算法的簡單，另一方面是因為它的預測能力強。

    隨機森林算法中有大量的沒有修剪的隨機決策樹，而這些決策樹的輸出是使用的一種無權重的多數投票。為了保證隨機森林的準確性，在決策樹歸納算法的建立過程中有2個隨機的過程：     

    (1)從訓練集中無放回的挑選樣本。雖然樣本都是從原始數據集中產生，但每棵樹的訓練數據集是不同的。

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

其中N是特征的數量，近似得到。

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

    尤其涉及到數字特征時，也存在將隨機性添加到決策樹歸納算法中的其他方法。例如代替使用所有的實例去決定為每個數字特性和使用實例的子樣本^[5]的最佳分裂點，這些子樣本的特征是各不相同的。使用這些特征和分裂點評價最優化的分裂標準，而評價標準是每個節點決策選擇的。由于在每個節點分裂的樣本選取是不同的，這項技術結果是由不同的樹組合成的集合體。另一種決策樹的隨機化方法是使用直方圖^[6]。使用直方圖一直被認為是使特征離散化的方法，然而這樣對處理非常大的數據時能夠減少很多時間。作為代表性的是，為每個特征創建直方圖，每個直方圖的邊界被看作可能的分裂點。在這個過程中，隨機化是在直方圖的邊界的一個區間內隨機選取分裂點。

    由于隨機森林的流行，隨機森林能被多種軟件語言實現，例如：Python、R語言、Matlab和C語言。

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

    隨機森林選取最佳分裂屬性，而極端隨機森林^[7]的最佳切割點是在隨機的特征子集中。比較起來，極端隨機森林的隨機性既在分裂的特征中又在它相應的切割點中。為了選取分裂特征，該算法隨機性表現為在被判斷為最好的特征中選取確定數目的特征。除了數字特征以外，該算法還在特征值域中統一地繪制隨機切點，即切點選取那些完全隨機獨立的目標屬性。在極端情況下，此算法在每個節點上隨機選取單屬性點和切割點，因此一棵完全隨機化樹建立完成。

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

3.3 概率校正隨機森林

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

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

    該算法是用交通標志識別的GTSRB數據集、手寫數字識別的MNIST數據集和著名機器學習數據集（美國郵政總局數據集、信件數據集和g50c數據集）進行評估。研究結果表明,本文提出的方法優于標準隨機森林分類器，尤其適用少量數目的樹。概率校正隨機森林基本流程圖如2所示。

3.4 梯度提升決策樹

    梯度提升決策樹(Gradient boosted decision trees，GBDT)^[9]是更新權重抽樣算法的一種，最初用來解決回歸任務。與其他更新權重算法相同的是該算法計算一系列的回歸樹，但卻以階段式方法構建森林。特別地，該算法計算一系列的回歸樹，而回歸樹中的每一棵后續樹的主要目的是使預測偽殘差表現好的樹有任意可微的損失函數。樹中的每一片葉子在相應區間最小化損失函數。通過使用適當的損失函數，傳統的更新權重抽樣的決策樹可也進行分類任務。

    為了避免過擬合，在梯度更新權重抽樣森林中選擇適當數量的樹（也就是迭代的次數）是非常重要的。迭代次數設置過高會導致過擬合，而設置過低會導致欠擬合。選取最佳值的方法是嘗試在不同的數據集中比較不同森林大小的效果。

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

3.5 旋轉森林

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

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

    原始的數據集被線性轉變為新的訓練集，這些主要元素構建一個新的特征集。新的訓練集是由新的特征空間所構建的，被應用到訓練分類樹的樹歸納算法中。值得注意的是，不同的特征區間將會導致不同的變換特征集，因此建立了不同的分類樹。這個旋轉森林算法已經被應用到MATLAB編碼的Weka工具。

    通過對旋轉森林的實驗研究發現旋轉森林要比普通的隨機森林算法精度高。然而旋轉森林有兩個缺點。第一，由于使用PCA算法旋轉隨機森林比普通隨機森林計算復雜度高。另一個缺點是在新建立的樹中節點是變換后的特征而不是原始特征。這令用戶更難理解樹，因為樹中的每個節點不是審查單一特征，用戶需要審查的是樹中每個節點上特征的一個線性組合。

3.6 Safe-BayesianRandom Forest

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

3.7 Switching classes

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

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

4 決策森林算法比較

    參考文獻中嘗試了比較幾種不同的決策森林算法。Dietterich^[15]針對構建C4.5決策森林比較了3種算法，分別是隨機抽樣、無權重抽樣和更新權重抽樣。實驗表明當數據中有少量噪聲時，更新權重抽樣預測效果最好，無權重抽樣和隨機抽樣有相同的效果。

    另一個文獻比較了以更新權重抽樣為基礎的決策樹和以無更新權重為基礎的決策樹^[16]。研究表明無更新權重抽樣減少了非穩態法樣本的方差，而更新權重抽樣方法減小了非穩態法樣本的方差和偏差但增加了穩態法樣本的方差。

    Villalba Santiago等人^[17]為決策森林中建立決策樹的根節點對比了7種不同的更新權值抽樣算法。他們得出結論，對于二項分類任務來說，大家眾所周知的AdaBoost算法（通過迭代弱分類器而產生最終的強分類器的算法)的效果更好。然而對于多分類任務來說如GentleAdaBoost算法效果更好。

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

    除了預測效果也有其他的標準。根據使用者選取能解決問題的、最適合的決策森林算法：

    (1)處理數據時適當地對算法進行設置：在處理具體的學習情況時，不同的決策森林方法有不同的適用范圍，例如不平衡的高維的多元的分類情況和噪聲數據集。使用者首先需要的是描述學習任務的特征并相應地選擇算法。

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

    (3)可擴展性：決策森林算法對大數據有縮放的能力。因此，隨機森林和梯度更新權值抽樣樹有較好的可擴展性。

    (4)軟件的有效性：現成的軟件數據包的數量。這些數據包能提供決策森林的實現方法，高度的有效性意味著使用者可以從一個軟件移動到另一個軟件，不需要更換決策森林算法。

    (5)可用性：提供一組控制參數，這些參數是廣泛性且易調節的。

5 決策森林應用

    隨著通信信息系統收集到的數據數量的增長，這些大規模數據集使得決策森林算法要提高其預測標準。然而對于任何數據學家，這些大規模數據的有效性是至關重要的，因為這對學習算法的時間和存儲器提出了挑戰。大數據是近幾年被創造的專業術語，指的是使用現有算法難以處理的巨量資料集。

    對于中小型數據集，決策樹歸納算法計算復雜度是相對較低的。然而在大數據上訓練密集森林仍有困難?？蓴U展性指的是算法訓練大數量數據能力的效率。

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

    SMRF^[19]是一種基于隨機森林算法改進的、可伸縮的、減少模型映射的算法。這種算法使得數據在計算機集群或云計算的環境下，能優化多個參與計算數據的子集節點。SMRF算法是在基于MapReduce的隨機森林算法模型基礎上進行改進。SMRF在傳統的隨機森林相同準確率的基礎上，能處理分布計算環境來設置樹規模的大小。因此MRF比傳統的隨機森林算法更適合處理大規模數據。

    PLANET^[20]是應用于MapReduce框架的決策森林算法。PLANET的基本思想是反復地生成決策樹，一次一層直到數據區間足夠小并能夠適合主內存，剩下的子樹可以在單個機器上局部地生長。對于較高層次，PLANET的主要思想是分裂方法。在一個不需要整個數據集的特定節點,需要一個緊湊的充分統計數據結構，這些數據結構在大多數情況下可以適合內存。

    Palit和Reddy^[32]利用MapReduce框架開發出兩種并行更新權重抽樣算法：AdaBoost.PL和LogitBoost.PL。根據預測結果，這兩種算法與它們相應的算法效果差不多。這些算法只需要一次循環MapReduce算法，在它們自己的數據子集上的每個映射分別運行AdaBoost算法以產生弱集合模型。之后這些基本的模型隨著他們權重的減小被排序和傳遞，被減小的平均權值推導出整體最后的權值。

    Del Río等人^[21]提出用MapReduce來實現各種各樣的常規算法。這些算法用隨機森林來處理不平衡的分類任務。結果表明，多數情況下映射數量的增加會使執行時間減少，而太多的映射會導致更糟糕的結果。

    各種分布的隨機森林是可以實現的，尤其在Mahout中，這只是一個Apache項目。Apache項目是可以提供免費的可擴展的機器學習算法程序包，包括在Hadoop框架下實現隨機森林的包。MLLib一個分布式機器學習框架，提供了在Spark框架下實現隨機森林和梯度提升樹的包。

6 結論

    決策森林主要目的是通過訓練多個決策樹來改善單一決策樹的預測性能。當前決策森林的研究趨勢是：解決大數據而實現分布式開發；改進現有的分類和回歸的決策森林算法來處理各種各樣的任務和數據集。

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

參考文獻

[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快速訓練算法[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的字母手勢識別算法研究[J].電子技術應用，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略