基于隨機森林和投票機制的大數據樣例選擇算法

周 翔，翟俊海*，黃雅婕，申瑞彩，侯瓔真

（1.河北大學數學與信息科學學院，河北保定 071002；2.河北省機器學習與計算智能重點實驗室（河北大學），河北保定 071002）

0 引言

在信息技術飛速發展的時代，不僅技術在快速發展，數據也在呈指數型上升。隨著數據規模不斷擴大，數據已經充斥了生活中的方方面面，如何從海量數據中去除冗余的和不重要的數據，或從大數據中選擇重要的子集具有重要的研究價值。

樣例選擇是解決大數據問題的一種有效的方法，它從大數據集中選擇一個子集，用選擇出的子集代替大數據集進行學習，目標是在學習性能受很小影響的前提下，提高學習效率。歷史上，第一個樣例選擇算法是Hart［1］于1968 年提出壓縮最近鄰（Condensed Nearest Neighbor，CNN）算法，研究人員提出的諸多樣例選擇算法根據樣例選擇過程可分為兩類：增量算法和減量算法。

增量算法從原始數據集T中按照特定的選擇規則，不斷地選擇重要的樣例放入初始化為空集的子集S中，增量算法從T中選擇樣例的方法具有隨機性，這種隨機性對最終結果影響較大。CNN 就是一種增量樣例選擇算法。Carbonera 和Abel［2-3］提出了兩種基于密度的樣例選擇算法：LDIS（Local Density Instance Selection）和CDIS（Central Density Instance Selection）。LDIS 算法選擇樣例的標準是在每個類中選擇具有最高密度值的樣例，而不是在整個數據集中進行全局搜索，這樣保證了LDIS 算法具有較低的計算時間復雜度。CDIS 算法采用與LDIS 算法相同策略，不同之處在于給有K個最近鄰的樣例賦予一個更高的密度值。在這一框架下，Malhat 等［4］也提出了兩種基于密度的樣例選擇算法：基于全局密度的樣例選擇和基于全局密度的增強樣例選擇算法。Arnaiz-González 等［5］提出了民主樣例選擇算法，并在Hadoop 平臺上，用MapReduce編程實現了該算法。De Haro-Garcíada等［6］提出了一種基于遺傳算法的樣例選擇算法。Guo 等［7］提出了一種基于Bagging 集成策略的關鍵樣例選擇算法，提出的方法比Bagging 方法更準確，比Boosting 方法更可靠。上面算法都是針對分類任務提出的，而Kordos 等［8］提出了一種針對回歸任務的進化樣例選擇算法。

減量型算法初始化數據集S為原始數據集T，再使用某種啟發式從S中刪除不重要或冗余的樣例，與增量型算法相比，減量型算法具有更高的時間復雜度，但是會提高分類器在子集上的測試精度。在CNN 算法的基礎上，Gates［9］提出了約簡最近鄰（Reduced Nearest Neighbor，RNN）算法，RNN能從CNN選出的子集中進一步刪除冗余的樣例，但是需更多的處理時間。為了解決CNN 和RNN 都可能無法得到最小一致子集的缺點，Ritter 等［10］提出了SNN（Selective Nearest Neighbour）算法，SNN 將原數據集中每個樣例與一致子集中最近同類別樣例之間的距離設定為小于該樣例到原數據集中的最近非同類樣例之間的距離，選出更小距離的一致子集。Liao 等［11］提出一種去除文本文件中噪聲樣例選擇的算法，通過計算文本文件的類別屬性得分，來區分每一類中噪聲樣例和正常樣例。受交叉驗證思想的啟發，Zhai 等［12］提出了一種交叉樣例選擇算法，該算法使用極限學習機算法構建由分類器組成的委員會，以投票熵作為評價樣例重要性的準則進行樣例選擇。Abbasi 等［13］提出了一種基于ReliefF 的樣例選擇算法，該算法利用ReliefF 計算最近鄰集合中每個樣例的權重，選擇出權重大的樣例。Cavalcanti 等［14］提出了一種基于排名的樣例選擇，該算法根據每個樣例與訓練集中所有其他樣例的關系來計算每個樣例的得分，根據得分排名選擇樣例。Yang 等［15］提出了一種基于粗糙集的樣例選擇算法。Pang 等［16］提出了基于K-近鄰的加權多類孿生支持向量機的樣例選擇算法，它通過刪除已分類的樣例子集中冗余的樣例來得到有代表性的數據子集。Jiang 等［17］提出了基于深度學習的樣例選擇方法，根據本地數據集的重要性進行篩選，將篩選出的樣例集合進行網絡上傳，來減小網絡負載和訓練時長，提高數據集的性能。

隨機森林（Random Forest，RF）由決策樹算法歸納總結得出，決策樹的并行化問題是先由Kufrin［18］提出的。Breiman［19］提出了應用非常廣泛的隨機森林算法。Yildiz 等［20］提出了并行化回歸樹算法。Wu 等［21］在Hadoop 平臺上用MapReduce 編程實現了C4.5 決策樹算法。Robnik-Sikonja［22］提出了改進的隨機森林算法，使用邊際權重加權投票代替普通投票選擇子樹。Del Rio 等［23］使用隨機森林算法對大數據進行過采樣、欠采樣和成本敏感學習，并用在MapReduce 編程實現了提出的算法。Xu 等［24］提出了一種基于Fayyad 邊界點原理的改進隨機森林算法，以解決經典隨機森林算法在連續屬性離散化過程中的信息丟失問題。

綜上所述，目前的參考文獻中基于大數據的樣例選擇問題還比較少，本文擬在這一問題領域使用隨機森林算法解決大數據樣例選擇問題。解決問題的思路是，在MapReduce［25］和Spark［26］框架上，將大數據集劃分為若干個數據子集，將這些數據子集分發到不同的大數據計算平臺的不同節點上，在各個節點上，通過隨機森林算法進行分類處理，將其中被錯誤分類的樣例子集S1選擇出來。重復p次，得到p個樣例子集S1，S2，…，Sp。最后用這p個樣例子集進行投票，得到最終樣例子集。

1 基礎知識

本章簡要介紹將要用到的基礎知識，包括隨機森林、開源的大數據處理平臺Hadoop和Spark。

1.1 隨機森林

隨機森林［19］是一種由若干棵決策樹構成的集成分類算法，其基礎是決策樹算法，其核心是如何用隨機化的思想構建組成隨機森林的多棵決策樹。對于給定的包含n個樣例的訓練集T={(xi，yi)|xi∈Rd，yi∈Y}，假設隨機森林的規模為l，隨機森林算法中的隨機性體現在兩個方面：一是按一定比例從訓練集T中隨機地抽取樣例，得到T的一個樣例子集，重復l次，得到l個樣例子集；二是按一定比例從d個屬性中隨機地抽取一個屬性子集來劃分樣例。隨機森林算法的偽代碼如算法1所示。

算法1 隨機森林算法。

輸入 訓練集T={(xi，yi)|xi∈Rd，yi∈Y}，1 ≤i≤n；隨機森林的規模l，隨機抽取的屬性子集的大小m，測試樣例x；

輸出 測試樣例x的類別標簽y∈Y。

1.2 大數據處理平臺Hadoop與Spark

Hadoop［25］是Apache 軟件基金會負責管理維護的一個開源的分布式大數據處理平臺，用于大數據的高可靠、可擴展的分布式計算。HDFS（Hadoop Distributed File System）和MapReduce 是Hadoop 的兩個核心組件，HDFS 負責大數據的組織、存儲和管理，MapReduce 用于實現用戶對大數據的不同應用邏輯。實際上，MapReduce 是一個并行編程框架，這一框架可方便用戶編寫處理大數據的應用程序，封裝了許多底層處理細節，如節點之間的通信、任務同步、負載均衡、失效檢查與恢復等，都由MapRecuce 自動完成，不需要用戶干預。MapRecuce 采用分而治之的思想處理大數據，將數據處理分成Map、Shuffle 和Reduce 三個階段，與HDFS 配合共同完成大數據處理，MapReduce處理大數據的流程如圖1所示。

圖1 MapReduce處理大數據的流程Fig.1 Flowchart of big data processing by MapReduce

從程序設計語言的角度來看，Map 和Reduce 是兩個抽象的編程接口，由用戶編程實現，完成自己的應用邏輯。

Spark［26］是一個基于內存的大數據處理平臺，2009年誕生于加州大學伯克利分校AMPLab（Algorithms，Machine，and People Lab），早期屬于伯克利大學的研究性開發項目，采用Scala 編程語言開發，于2010 年正式開源，2013 年6 月成為Apeche 孵化項目，2014 年2 月成為Apache 頂級項目，現在Spark 已經成為一個功能完善的生態系統。其中，Spark Core是Spark的核心組件，具有任務調度、存儲管理、錯誤恢復等功能。Spark 的主要操作對象為彈性分布式數據集（Resilient Distributed Dataset，RDD），RDD是一種抽象的數據模塊結構。Spark 使用RDD 實現基于內存的計算，在計算過程中會優先考慮將數據緩存在內存中，如果內存容量不足的話，Spark 才會考慮將數據或部分數據緩存到磁盤上。Spark 為RDD 提供了一系列算子，以對RDD 進行有效的操作。實際上，Spark 對大數據的處理就是通過對RDD的處理實現的，將一種RDD經算子操作變換成另一種RDD 來實現數據的計算。Spark 對大數據的處理流程如圖2所示。

圖2 Spark處理大數據的流程Fig.2 Flowchart of big data processing by Spark

2 基于隨機森林的大數據投票樣例選擇算法

本章首先介紹基于隨機森林的大數據樣例選擇算法，簡記為RF-IS（Random Forest Instance Selection），然后分別介紹在MapReduce 平臺和Spark 平臺上實現基于隨機森林的大數據選擇算法的具體思路。

本文提出的基于隨機森林的大數據投票樣例選擇算法，其基本思路是將大數據集分為訓練集D1和測試集D2，在D1上用隨機森林算法訓練出隨機森林分類器，在D2上使用訓練出的隨機森林分類器進行分類，把錯誤分類的樣例選擇出來記為S1，重復p次，得到p個子集S1，S2，…，Sp，對得到的p個子集進行投票選擇，得到最終的樣例子集S。提出的算法的基本思想如圖3所示，算法的偽代碼如算法2所示。

圖3 所提算法的基本思想Fig.3 Basic idea of the proposed algorithm

算法2 基于隨機森林的大數據投票樣例選擇算法。

輸入 大數據集D；

輸出 選擇的樣例子集S。

2.1 隨機森林大數據投票樣例選擇算法的MapReduce實現

根據對隨機森林算法的分析，由于需要處理的數據集為大數據集，故將算法在MapReduce 計算框架中實現，將數據集并行地在大數據計算平臺進行建樹和分類的操作，不僅提高了建模的效率，還提升了容錯率。數據集中樣例數的增多，可以通過增加MapReduce 的計算節點，來縮短運算的處理時間，將大數據集劃分成多個數據子集，對每個數據子集進行樣例選擇，提高了算法的可擴展性。算法3 是基于MapReduce的隨機森林大數據投票樣例選擇算法，簡記為MR-RF-IS（MapReduce Random Forest Instance Selection）。

算法3 MR-RF-IS算法。

在MapReduce 計算平臺中，Mahout 庫也提供了隨機森林算法實現的方法，分為三部分組成。首先生成描述性文件，不僅要了解數據特征屬性的數據格式是離散還是連續的，還要知道訓練集中每條的輸入輸出記錄在哪個屬性列；然后生成隨機森林模型，包括建立一棵決策樹，把建立好的決策樹轉換成為隨機森林模型和把隨機森林模型存入文件系統；最后評估隨機森林模型，主要是對隨機森林模型的分類正確率進行評估。

2.2 隨機森林大數據投票樣例選擇算法的Spark實現

基于隨機森林的大數據樣例選擇算法是運用集成學習（bagging）的思想，將多棵樹集成的一種算法，所以在MR-RFIS 的基礎上，在Spark 大數據計算平臺上對其進行實現。在Spark 平臺上實現隨機森林算法，簡記為Spark-RF-IS（Spark Random Forest Instance Selection）。Spark 隨機森林算法采用了多種優化處理：

切分點抽樣式統計 在local 模式中決策樹對連續值進行劃分點（split）進行分裂時，都是通過對特征進行排序，然后取相鄰的兩個數據間作為數據的劃分點。假如在standalone模式中，進行相同的操作會帶來大量的網絡通信操作，當數據量巨大時，算法的效率將極為低下。為了避免排序操作，MLlib庫中的隨機森林在建樹的過程中，通過對各個分區進行一定的子特征抽樣策略，生成每個分區的統計數據來獲取劃分點，此策略雖然犧牲了部分的精度，但對模型的整體影響不大。

特征裝箱（Binning） 根據抽樣策略得到劃分點后，將特征進行裝箱操作將計算出最優的劃分點，劃分出來的區域（Bin）由相鄰的數據劃分點構成，Bin的個數很小，一般采用30個左右，通過計算每個Bin 中不同類型的比例，可以快速計算出最優的劃分點

分區統計 在Bin 數據進行單獨統計后，可以通過Reduce 階段進行數據的合并來得到總的Bin 數據，合并的數據為統計數據，不會帶來很大的網絡通信負載。

逐層訓練（level-wise training） 在local 模式中建樹的過程使用深度優先的遞歸調用策略，需要移動數據，將相同節點的數據匯總到一起，但是在分布式處理系統中無法有效地執行此操作，同時數據過大也會導致操作無法存儲在一起，所以需要分布式存儲。MLlib 采用的是廣度優先的逐層構建樹節點的策略，遍歷所有數據的次數等于決策樹的最大層數，每次遍歷只需要計算每個節點上特征的Binning統計參數，遍歷完成后，根據節點的Binning統計數，決定是否切分和如何切分。Spark-RF-IS算法的偽代碼如算法4所示。

算法4 Spark-RF算法。

輸入 大數據集T；

輸出 數據子集S；

3 實驗結果與分析

3.1 實驗環境

實驗所用到MapReduce和Spark大數據平臺，兩個平臺都為主從式結構，設定1臺為主機為主節點和7臺主機作為從節點，7 臺計算機都在同一局域網內，并通過端口速率為100 Mb/s 的H3C S5100 交換機連接。集群的操作系統均為CentOS 6.4，CPU 為Intel E5 2.20 GHz，實驗使用Hadoop 版本為2.7.1，Spark 版本為2.3.1。客戶端開發環境為Idea，JDK版本為jdk-1.8.0_144-windows-x64，表1為集群環境配置的詳細信息表，計算機型號均為Dell PowerEdge R820。

表1 大數據計算平臺節點規劃Tab.1 Node configuration of big data computing platform

3.2 實驗數據

實驗采用3 個人工大數據集和3 個UCI 大數據集進行實驗，所使用的數據集的基本信息見表2，每個數據集都被隨機分成了兩部分，數據集的80%作為訓練集，20%作為測試集，將由下面描述的實驗指標，將MR-RF-IS 和Spark-RF-IS 進行比對分析，三個Gaussian人工數據集的具體參數見表3。

表2 數據集基本信息Tab.2 Basic information of datasets

表3 三個人工數據集服從的概率分布Tab.3 Probability distributions followed by three synthetic datasets

3.3 實驗分析

本節主要是對在MapReduce 和Spark 平臺上實現的基于隨機森林的大數據樣例選擇進行實驗對比。實驗指標為測試精度、選擇比、算法執行時間。

測試精度 將原數據集分為測試集和訓練集，將訓練集經過樣例選擇的數據子集進行訓練為分類器，用測試集對該分類器的測試精度進行測試，測試精度越高，代表樣例選擇的算法越好。

選擇比 選擇比是所選擇的樣例數與原始數據集的比值，選擇比的值越低，證明選擇出的子集更有代表性，說明樣例選擇的性能好。

運行時間 樣例選擇算法從開始到執行結束所花費的時間。

實驗結果如表4。由表4實驗結果發現，在人工數據集和UCI 數據集上，MR-RF-IS 和Spark-RF-IS 算法在測試精度和選擇比上數值近似相同，是因為MR-RF-IS和Spark-RF-IS在算法結構和運行邏輯上基本秉承同種思想，算法在執行樣例選擇時所選擇的樣例子集也是大致相同的，選擇出的樣例子集重要程度也近乎相似；但兩種算法的在不同的平臺上所運行的時間有著很大的差距，造成這種差距的主要原因是在MapReduce 和Spark大數據處理平臺上對數據的處理采取截然不同的策略。基于隨機森林的大數據樣例選擇在大數據計算平臺上算法主要在I/O 操作和中間數據傳輸上消耗過多時間，其運行時間T可以分為文件讀取時間Tread、中間數據傳輸時間Ttran、中間數據排序時間Tsort和文件輸出時間Twrite；其中，文件讀取時間Tread受文件讀取速度和文件的影響，文件輸出時間Twrite受文件輸出速度和文件數量的影響。在MapReduce和Spark平臺上，文件的輸入輸出速度和數據的數量的差異主要是受到不同平臺的運行機制和讀寫方法影響，所以只對中間數據傳輸時間Ttran和中間數據排序時間Tsort造成的影響進行分析。

表4 在6個數據集上實驗指標的對比Tab.4 Comparison of experimental indexes on 6 datasets

中間數據傳輸時間Ttran指的是將Map 執行的任務輸出到Reduce 階段作為輸入所消耗的時間，主要由Map 階段輸出的文件大小和I/O 傳輸速度所決定，MapReduce 在處理大數據集時，首先將數據集在HDFS 進行存儲，然后在Map 階段對放在HDFS 中的數據集進行處理后再將中間數據輸出到HDFS 等待Reduce階段的處理，在Reduce階段會根據數據的鍵值對數據集進行計算。而Spark作為基于內存的大數據處理平臺，將Spark計算中的中間數據直接在內存中儲存，只有在中間數據溢出時才會把HDFS 作為備倉庫進行儲存，這樣會大幅度減少網絡I/O操作，導致因此基于MapReduce的中間數據傳輸時間遠大于基于Spark的中間數據傳輸時間。

中間數據排序時間Tsort主要是針對MapReduce平臺，為了保證每一個Map 任務都對應一個有序的中間數據，Shuffle 過程會對中間數據進行排序和歸并操作，當有m個Map任務時，每個Map 任務有n條數據，則在MapReduce 上對中間數據的傳輸時間為O(m· logn)。而在Spark 大數據處理平臺上，不需要中間數據有序排列，所以其排序時間為0。所以從不論中間數據排序時間Tsort和中間數據傳輸時間Ttran，Spark的算法運行時間都優于MapReduce算法處理時間。

對于文件數目來講，算法運行過程產生的中間數據會以文件形式存儲，過多的數據既帶來大量的I/O操作也會占用內存的存儲空間，也會導致算法的運行時間增加。在MapReduce 在執行操作時，Shuffle 過程會將每個Map 節點所產生的文件都進行排序和歸并操作來使數據能存儲在一個文件中，但在Spark中，不需要對中間數據進行排序和歸并操作，只是對數據進行合理分區，雖然會產生比MapReduce 更多的文件，但是從一定程度上減少了運行時間。

對于同步次數來說，MapReduce 是典型的同步模型，只有當所有的Map 任務完成后才可以進行Reduce 任務，而Spark是異步模型，多個節點可以單獨地執行計算，這使得算法的執行效率得到了很大的提升。

綜上所述，雖然在MR-RF-IS 和Spark-RF-IS 算法的程序設計上思想相同，但兩個平臺的計算邏輯相差較大，Spark 上雖對數據進行分區操作導致Spark 所產生的文件數遠遠多于MapReduce 的文件數，但在數據的傳輸調度上，Spark 采用導管式傳輸，大幅減少了同步的次數，隨著迭代次數的增加在中間數據傳輸上優于MapReduce，所以Spark 在算法運行時間上有更好的表現。

3.4 與其他大數據樣例選擇算法對比

表5 是本文算法與CNN 算法和RNN 算法對相同的大數據集進行樣例選擇的實驗結果。

表5 3種算法在各數據集上的實驗結果Tab.5 Experimental results of three algorithms on different datasets

從測試精度上來看，本文提出的算法在測試精度上在大部分數據集上都能夠超越CNN 和RNN 經典算法。因為隨機森林分類器是集成的強學習器，有良好的泛化能力，且自身精度比其他單個算法更高，但計算開銷很小，所以本文使用的隨機森林分類器較KNN（KNearest Neighbor）分類器性能更好，在處理大規模數據時有很大優勢。

從運算時間上來看，CNN 算法作為經典算法在規模較小的數據集的時間復雜度有一定的優勢，但是在處理規模較大的數據集時，所花費的時間較多；而RNN 算法在隨著數據規模的擴大，時間復雜度也隨之大幅增長，當數據集到達一定規模后就無法對其進行處理；而本文提出的RF-IS 算法在規模較小的數據集中算法在運行時間上表現穩定，當數據達到一定規模后，也能在保證選擇比足夠小的情況下，可以花費比較少的時間處理大規模的數據集。

綜上所述，本文提出的RF-IS 算法在保證測試精度和一定選擇比的情況下，RF-IS算法對規模更大的數據集表現穩定并且算法運行時間更短，代表RF-IS 算法在大數據樣例選擇性能上更加出色，表現更加穩定。

4 結語

本文提出了基于隨機森林的大數據投票樣例選擇算法，并分別在MapReduce和Spark大數據處理平臺上進行了實現，在此基礎上不僅對兩個大數據處理平臺進行了實驗比較，而且還與經典樣例選擇算法CNN 和RNN 進行了實驗比較。從對兩個大數據平臺的實驗對比來看，因為平臺差異，在算法運行時間上有較為明顯的差異，在其余的實驗指標上均近似相同。從提出的算法與CNN和RNN的實驗比較的結果來看，在保證測試精度和一定的選擇比的情況下，本文提出的算法對規模更大的數據集進行計算時，表現更加穩定且具有更低的計算時間復雜度，RF-IS算法在大數據樣例選擇上性能更加穩定，表現更加出色。綜上所述，本文提出的算法是行之有效的。