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

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

0 引言

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

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

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

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

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

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

1 基礎(chǔ)知識

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

1.1 隨機森林

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

算法1 隨機森林算法。

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

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

1.2 大數(shù)據(jù)處理平臺Hadoop與Spark

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

圖1 MapReduce處理大數(shù)據(jù)的流程Fig.1 Flowchart of big data processing by MapReduce

從程序設(shè)計語言的角度來看，Map 和Reduce 是兩個抽象的編程接口，由用戶編程實現(xiàn)，完成自己的應(yīng)用邏輯。

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

圖2 Spark處理大數(shù)據(jù)的流程Fig.2 Flowchart of big data processing by Spark

2 基于隨機森林的大數(shù)據(jù)投票樣例選擇算法

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

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

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

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

輸入 大數(shù)據(jù)集D；

輸出 選擇的樣例子集S。

2.1 隨機森林大數(shù)據(jù)投票樣例選擇算法的MapReduce實現(xiàn)

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

算法3 MR-RF-IS算法。

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

2.2 隨機森林大數(shù)據(jù)投票樣例選擇算法的Spark實現(xiàn)

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

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

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

分區(qū)統(tǒng)計 在Bin 數(shù)據(jù)進行單獨統(tǒng)計后，可以通過Reduce 階段進行數(shù)據(jù)的合并來得到總的Bin 數(shù)據(jù)，合并的數(shù)據(jù)為統(tǒng)計數(shù)據(jù)，不會帶來很大的網(wǎng)絡(luò)通信負載。

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

算法4 Spark-RF算法。

輸入 大數(shù)據(jù)集T；

輸出 數(shù)據(jù)子集S；

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

實驗所用到MapReduce和Spark大數(shù)據(jù)平臺，兩個平臺都為主從式結(jié)構(gòu)，設(shè)定1臺為主機為主節(jié)點和7臺主機作為從節(jié)點，7 臺計算機都在同一局域網(wǎng)內(nèi)，并通過端口速率為100 Mb/s 的H3C S5100 交換機連接。集群的操作系統(tǒng)均為CentOS 6.4，CPU 為Intel E5 2.20 GHz，實驗使用Hadoop 版本為2.7.1，Spark 版本為2.3.1?？蛻舳碎_發(fā)環(huán)境為Idea，JDK版本為jdk-1.8.0_144-windows-x64，表1為集群環(huán)境配置的詳細信息表，計算機型號均為Dell PowerEdge R820。

表1 大數(shù)據(jù)計算平臺節(jié)點規(guī)劃Tab.1 Node configuration of big data computing platform

3.2 實驗數(shù)據(jù)

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

表2 數(shù)據(jù)集基本信息Tab.2 Basic information of datasets

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

3.3 實驗分析

本節(jié)主要是對在MapReduce 和Spark 平臺上實現(xiàn)的基于隨機森林的大數(shù)據(jù)樣例選擇進行實驗對比。實驗指標為測試精度、選擇比、算法執(zhí)行時間。

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

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

運行時間 樣例選擇算法從開始到執(zhí)行結(jié)束所花費的時間。

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

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

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

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

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

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

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

3.4 與其他大數(shù)據(jù)樣例選擇算法對比

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

表5 3種算法在各數(shù)據(jù)集上的實驗結(jié)果Tab.5 Experimental results of three algorithms on different datasets

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

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

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

4 結(jié)語

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