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

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

0 引言

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

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

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

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

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

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

1 基礎(chǔ)知識(shí)

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

1.1 隨機(jī)森林

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

算法1 隨機(jī)森林算法。

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

輸出 測(cè)試樣例x的類別標(biāo)簽y∈Y。

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

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

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

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

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

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

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

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

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

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

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

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

輸出 選擇的樣例子集S。

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

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

算法3 MR-RF-IS算法。

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

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

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

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

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

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

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

算法4 Spark-RF算法。

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

3.3 實(shí)驗(yàn)分析

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

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

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

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

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

表4 在6個(gè)數(shù)據(jù)集上實(shí)驗(yàn)指標(biāo)的對(duì)比Tab.4 Comparison of experimental indexes on 6 datasets

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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