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

1(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071000)

2(河北大學(xué) 河北省機器學(xué)習(xí)與計算智能重點實驗室，河北 保定 071000)

1 引 言

目前，云計算、物聯(lián)網(wǎng)和人工智能等技術(shù)的不斷進(jìn)步，不僅使技術(shù)飛躍式地發(fā)展，數(shù)據(jù)的維度也呈指數(shù)型上升，導(dǎo)致大數(shù)據(jù)問題變得越發(fā)突出，但大數(shù)據(jù)除了帶來巨大的價值，其中還存在大量不相關(guān)、不完整和有噪聲的數(shù)據(jù)影響計算的性能和模型的魯棒性，導(dǎo)致計算機存儲量巨大和計算復(fù)雜度高等問題.為了解決高維數(shù)據(jù)的問題，特征選擇算法已逐漸成為數(shù)據(jù)挖掘領(lǐng)域中至關(guān)重要的組成部分[1].特征選擇算法是檢測和挑選相關(guān)特征并丟棄不相關(guān)特征的過程，從高維數(shù)據(jù)集中挑選出具有代表性的特征子集來代替原始數(shù)據(jù)集進(jìn)行計算和存儲，使學(xué)習(xí)者在學(xué)習(xí)效率、概括能力和便捷歸納模型方面得到巨大改進(jìn)，以到達(dá)數(shù)據(jù)降維和減少計算復(fù)雜度的目的.關(guān)于特征選擇算法和用于推斷模型的歸納學(xué)習(xí)方法之間的關(guān)系，可以區(qū)分為4種主要方法：過濾式[2]、封裝式[3]、嵌入式[4]和混合式[5].

過濾式方法基于性能度量選擇特征，不考慮數(shù)據(jù)建模算法，先對原始數(shù)據(jù)集進(jìn)行特征選擇，再訓(xùn)練數(shù)據(jù)模型.過濾式方法可以對單個特征進(jìn)行排序或評估整個特征子集.目前，已提出的過濾式方法的度量方法大致可分為：信息、距離、一致性、相似性和統(tǒng)計度量.過濾式方法主要依賴于訓(xùn)練數(shù)據(jù)的特征進(jìn)行選擇，并且特征選擇過程為預(yù)處理步驟獨立于歸納算法.過濾式方法對比封裝式方法具有更低的計算成本，更快的計算速度和更好的泛化能力，但其主要缺點是缺少與數(shù)據(jù)模型的交互.例如，Hoque等人[6]提出了一種基于互信息的貪婪特征選擇方法，將特征互信息和特征類互信息結(jié)合起來，最大限度地提高特征之間的相關(guān)性，尋找特征的最優(yōu)子集.Sikonja和Kononenko[7]提出一種屬性估計方法稱為消除(Relief)算法，Relief算法能夠檢測屬性之間的條件依賴關(guān)系，通過回歸和分類的訓(xùn)練，將數(shù)據(jù)統(tǒng)一映射到視圖來進(jìn)行特征選擇.Dash和Ong[8]為了克服Relief中存在大量不相關(guān)特征和大量噪聲的問題，對Relief進(jìn)行了改進(jìn)，將Relief進(jìn)行聚類組成Relief-C(Relief-Clustering)來選擇相關(guān)的特征以解決此問題.Yu和Liu[9]提出了一種引入了優(yōu)勢相關(guān)概念的快速過濾式方法，無需對特征進(jìn)行成對的相關(guān)分析，就可以識別相關(guān)特征和消除相關(guān)特征之間的冗余.Witten和Tibshirani[10]提出了一種稀疏聚類方法將自適應(yīng)選擇的特征子集進(jìn)行聚類，并使用套索機制來選擇特征.

封裝式方法是將數(shù)據(jù)模型作為選擇過程中的一部分，使用訓(xùn)練模型來選擇特征子集，其創(chuàng)建的模型被視為黑盒評估器.封裝式方法具有與分類器交互和捕獲功能相關(guān)性的特點，但是計算成本高，且有過擬合的風(fēng)險，計算效率也主要取決于數(shù)據(jù)模型的選擇.從模型處理性能來說，封裝式方法比過濾式方法效果更好，缺點是通常使用迭代計算，計算花銷較大，并且只能使用較為簡單的模型才能選擇出最優(yōu)的特征子集.對于分類任務(wù)，封裝器基于分類器評估特征子集，例如樸素貝葉斯[11]或極限分類機[12].而對于聚類任務(wù)，封裝器基于聚類算法評估子集，例如，Kim等人[13]使用K均值聚類算法來選擇特征.特征子集的生成依賴于搜索策略，封裝式特征選擇的每次迭代都會基于所用的搜索策略，例如前向搜索[14]、后向搜索[15]和啟發(fā)式搜索策略[16].實際上，封裝器不只適用于貪婪搜索策略和快速建模算法，搜索策略和建模算法的任何組合都可以組成封裝器.Cortizo和Giraldez[17]提出了一種使用依賴性信息作為指導(dǎo)的搜索最優(yōu)特征子集的封裝器，并選用NaiveBayes分類器作為模型.Liu等人[18]提出了一種用于故障診斷的全局幾何相似特征選擇算法(GGSS)，利用線性支持向量機和回歸神經(jīng)網(wǎng)絡(luò)(GRNN)建立的分類器進(jìn)行選擇特征.Benot等人[19]使用極限分類器選擇出合適的特征子集.劉兆賡等人[20]提出基于森林優(yōu)化算法的增強特征選擇方法(EFSFOA)，高效地處理高維數(shù)據(jù).

嵌入式方法在訓(xùn)練模型的同時執(zhí)行特征選擇，即將特征選擇過程和數(shù)據(jù)模型訓(xùn)練過程結(jié)合在一起，使特征選擇和數(shù)據(jù)模型在一個訓(xùn)練過程中完成，通常嵌入式方法都基于特定的學(xué)習(xí)模型，所以其性能主要取決于所選的歸納算法.嵌入式方法具有與模型交互、低計算成本和可捕獲相關(guān)性功能的優(yōu)點，故嵌入式方法執(zhí)行效率比封裝式方法更高，但是其計算效率主要取決于數(shù)據(jù)模型.例如，Shuangge等人[21]提出了一種發(fā)展式的懲罰特征選擇算法，用于高維輸入的生物信息學(xué)的研究.Zou和Hastie[22]提出了一種使用彈性計算的網(wǎng)絡(luò)正則化算法(LARS-EN)，將彈性計算與線性分類器一起工作，將對模型沒有貢獻(xiàn)的特征進(jìn)行剔除.

混合式方法是結(jié)合了過濾式方法和封裝式方法的優(yōu)點所構(gòu)成的特征選擇方法.首先，為了減少特征維度空間，使用過濾式方法獲得幾個候選子集，然后，使用封裝式方法來尋找最佳候選子集，故混合式方法通常同時具有封裝式方法的高精度和過濾式方法的高效率.例如，Cadenas等人[23]提出了一種以模糊隨機森林為基礎(chǔ)的特征選擇方法，通過將過濾和封裝方法集成到一個序列搜索過程來處理低質(zhì)量的數(shù)據(jù)，提高了算法的分類精度.Seok等人[24]提出了一種用于特征選擇的混合式遺傳算法.Ali和Shahzad[25]提出了一種基于條件互信息和蟻群優(yōu)化的特征子集選擇算法.Sarafrazi和Nezamabadi-Pour[26]將引力搜索算法(GSA)與支持向量機(SVM)相結(jié)合，提出了一種混合式重力搜索特征選擇算法(GSA-SVM).

隨著大數(shù)據(jù)時代的來臨，將傳統(tǒng)的特征選擇算法擴展到大數(shù)據(jù)環(huán)境變得至關(guān)重要.近幾年，余征等人[27]提出針對海量人像小圖片的特征提取方法.Fan等人[28]提出了一種基于不相關(guān)回歸和自適應(yīng)譜圖的多標(biāo)簽特征選擇方法.Rashid等人[29]提出了基于隨機特征分組的協(xié)同進(jìn)化特征選擇算法(CCFSRFG)對大數(shù)據(jù)集進(jìn)行動態(tài)分解，提高了相交互的特征分到同一元組中的概率.Long等人[30]提出了一種K均值聚類算法，將特征選擇和K-means聚類結(jié)合在一個統(tǒng)一的框架中，選擇細(xì)化后的特征，提高計算性能.趙宇海等人[31]提出一種面向大規(guī)模序列數(shù)據(jù)的交互特征并行挖掘算法，提高了針對序列數(shù)據(jù)進(jìn)行特征選擇的有效性和執(zhí)行效率.張文杰和蔣烈輝[32]提出一種基于遺傳算法優(yōu)化的大數(shù)據(jù)特征選擇方法，該方法用特征權(quán)重引導(dǎo)遺傳算法的搜索，提升算法的搜索能力和獲取特征的準(zhǔn)確性.胡晶[33]對云計算海量高維大數(shù)據(jù)特征選擇算法進(jìn)行了研究，針對云計算大數(shù)據(jù)的高動態(tài)與高維度特征，提出了基于競爭熵加權(quán)結(jié)合稀疏原理的在線學(xué)習(xí)特征選擇算法.

2 基礎(chǔ)知識

本節(jié)將對本文所涉及的基礎(chǔ)知識進(jìn)行簡要介紹，包括決策樹算法，MapReduce編程框架模型和Spark編程框架模型.

2.1 決策樹

決策樹是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)中強大、高效和流行的方法，用于探索大型和復(fù)雜的數(shù)據(jù)集以找到有用的模式.因為決策樹支持從大量數(shù)據(jù)中提取知識和建模，在保證低成本的同時，建模過程更容易，準(zhǔn)確和有效，所以決策樹算法在包括數(shù)據(jù)挖掘、機器學(xué)習(xí)、信息抽取、文本挖掘和模式識別在內(nèi)的各個學(xué)科中都是非常有效的工具.

決策樹[36]是為監(jiān)督數(shù)據(jù)挖掘設(shè)計，并以樹狀方式分析數(shù)據(jù)的預(yù)測模型，其中每個內(nèi)部節(jié)點代表一個特征的測試，每個分枝代表特征測試的結(jié)果，每個葉節(jié)點代表類標(biāo)簽.最初，所有數(shù)據(jù)元祖都在根節(jié)點，此時，根節(jié)點的入度為零，這意味著沒有引入邊.決策樹通過分割樹的分枝來實現(xiàn)分類，其中每個分割點代表對數(shù)據(jù)屬性的測試，以根節(jié)點為起點依據(jù)每個數(shù)據(jù)集的屬性值劃分子節(jié)點，在孩子節(jié)點上根據(jù)數(shù)據(jù)集的屬性值優(yōu)劣遞歸劃分新的葉節(jié)點，這種分割一直持續(xù)到終端層，最終一個節(jié)點上的所有數(shù)據(jù)元組都由一個類的樣本組成.構(gòu)建決策樹一般采用啟發(fā)式的方法，即在每次對屬性進(jìn)行分裂時，都自動將滿足條件的最優(yōu)特征作為劃分的標(biāo)準(zhǔn)，為的是將選定的數(shù)據(jù)集進(jìn)行歸納分類，組成可視化模型.圖1為決策樹的算法流程圖.

圖1 決策樹算法流程圖

信息熵(entropy)是衡量樣本信息的純度和不確定性的度量，信息熵由公式(1)定義.

(1)

H(D)的值越小，提取D的精確度越高.

信息增益(gain)是衡量特征能為該分類帶來信息量的度量，利用屬性值A(chǔ)來劃分?jǐn)?shù)據(jù)集D時所用的信息增益由公式(2)定義.

(2)

g(D，A)越大，就意味著屬性A劃分的精確度越高.

信息增益率gR(D，A)是由信息增益和分裂信息熵比值決定的信息度量.算法2中使用信息增益率對劃分屬性進(jìn)行選擇.信息增益率公式(3)定義.

(3)

分裂信息熵Sp(A)是衡量當(dāng)前分裂的純度和不確定性的度量，由公式(4)定義.

(4)

信息增益率越高，該屬性的純度越高，即代表該屬性具有更高的代表性.

2.2 ID3算法和C4.5算法

ID3(Iterative Dichotomiser 3)算法是Ross Quinlan發(fā)明的一種決策樹算法，采用自頂向下的貪婪搜索策略，遍歷所有可能的決策空間.主要基礎(chǔ)為奧卡姆剃刀原理，即用較少的計算代價做更多的事，越是小型的決策樹越優(yōu)于大型的決策樹.核心思想就是以信息增益來度量屬性的劃分，選擇分裂后信息增益最大的屬性繼續(xù)進(jìn)行分裂，直到滿足終止條件.算法1為ID3算法偽代碼.

算法1.ID3算法

輸入：訓(xùn)練樣本S；

輸出：一棵決策樹Ti.

1.初始化閾值；

2.判斷該樣本的類別，若為同一類Di，則標(biāo)記類別為D，并返回單節(jié)點樹T，否則執(zhí)行下一個樣本；

3.判斷屬性，若為空則返回T，并標(biāo)記該類為樣本中輸出類別D中樣例最多的類，否則執(zhí)行下一個樣本；

4.根據(jù)當(dāng)前劃分，計算S中各個屬性對D的信息增益，選擇出其中信息增益最大的屬性AMax；

5.若AMax的信息增益小于閾值，返回T；否則，按AMax的不同值A(chǔ)Maxi將對應(yīng)的D劃分為其他類別，每類產(chǎn)生一個子節(jié)點，對應(yīng)屬性值為AMaxi，增加T；

6.D=Di，A=AMax，在所有子節(jié)點遞歸調(diào)用2-5步；

7.得到子樹Ti并返回.

本文使用的C4.5算法也是由Ross Quinlan開發(fā)的用于產(chǎn)生決策樹的算法，該算法是對ID3算法的一個改進(jìn)，將ID3使用的信息增益改為更有說服力的信息增益率來建樹，使C4.5算法產(chǎn)生的決策樹產(chǎn)生的分類更易于理解，準(zhǔn)確率更高.算法2為C4.5算法偽代碼.

算法2.C4.5算法

輸入：訓(xùn)練樣本S；

輸出：一棵決策樹Ti.

1.設(shè)置根節(jié)點N；

2.若S屬于同一類，則返回N為葉節(jié)點，標(biāo)記為類C；

3.Ifattributes=null或S中剩余的樣例數(shù)少于闕值，返回N為葉節(jié)點，標(biāo)記N為S中出現(xiàn)最多的類；

4.For eachattributes

5.計算信息增益率，找出attributes中信息增益率最高的屬性；

6.End for

7.For新的葉子節(jié)點

8.若該葉子節(jié)點樣本子集S′空，則分裂此葉子節(jié)點生成新葉節(jié)點，并標(biāo)記為S中出現(xiàn)最多的類；

9.Else

10. 在該葉子節(jié)點上繼續(xù)分裂；

11.End for

12.后剪枝.

13.得到子樹Ti并返回；

2.3 MapReduce和Spark基礎(chǔ)介紹

Hadoop是一個由Apache基金會所開發(fā)的開源分布式計算平臺，目前已成為工業(yè)界和學(xué)術(shù)界進(jìn)行云計算應(yīng)用和研究的標(biāo)準(zhǔn)平臺.Hadoop最先受到Google Lab開發(fā)的GFS和MapReduce的啟發(fā)，后逐漸發(fā)展到現(xiàn)如今的規(guī)模.Hadoop的核心組件為HDFS和MapReduce，HDFS(Hadoop Distributed File System)是Hadoop的高性能、高容錯和可擴展的分布式文件存儲系統(tǒng)，為海量的數(shù)據(jù)提供了多種的存儲方式和巨大的可用空間，MapReduce是并行處理大規(guī)模數(shù)據(jù)的分布式運行框架，為用戶提供了計算.在Hadoop框架上，可以將成百上千個節(jié)點組成的大規(guī)模計算機集群規(guī)范整理為大數(shù)據(jù)開源平臺，用戶基于此平臺可編寫處理大規(guī)模數(shù)據(jù)的并行分布式程序.Hadoop具有高可靠性、高擴展性、高效性、高容錯性、低成本等優(yōu)點，現(xiàn)已被全球幾大IT公司用作其“云計算”環(huán)境中的重要基礎(chǔ)軟件.

Spark是一種用來實現(xiàn)快速和通用計算的集群數(shù)據(jù)平臺，最初于2009年在加州大學(xué)伯克利分校AMP實驗室誕生，到現(xiàn)在，Spark已經(jīng)成為一個功能完善的生態(tài)系統(tǒng).Spark擴展了MapReduce計算模型，可以高效地支持更多的計算模式，包括流的處理、交互查詢和迭代計算.Spark在滿足簡單和低能耗的前提下將各種處理流程整合為一套流程，使其在統(tǒng)一的框架下支持不同的計算模式，大大減少了原先需要對各種平臺和信息分別處理的問題.

3 大數(shù)據(jù)環(huán)境下的投票特征選擇算法介紹

本節(jié)首先介紹大數(shù)據(jù)環(huán)境下的投票特征選擇，然后分別介紹在MapReduce平臺和Spark平臺上實現(xiàn)大數(shù)據(jù)投票特征選擇算法的具體實現(xiàn)思路.圖2為大數(shù)據(jù)投票特征選擇流程圖.

圖2 大數(shù)據(jù)環(huán)境下的投票特征選擇算法流程圖

其中，使用決策樹算法的目標(biāo)就是從訓(xùn)練數(shù)據(jù)集上歸納出一組分類規(guī)則，決策樹分類器通常分為3個步驟：選擇最優(yōu)特征、決策樹生成和決策樹剪枝.選擇最優(yōu)特征的標(biāo)準(zhǔn)就是判斷一個特征對于當(dāng)前數(shù)據(jù)集的分類效果，在當(dāng)前節(jié)點根據(jù)信息增益率作為判斷進(jìn)行切分，按照切分后節(jié)點數(shù)據(jù)集合中的分區(qū)有序程度找到局部最優(yōu)的特征，然后將不同分類的數(shù)據(jù)盡可能分開.劃分后的分區(qū)數(shù)據(jù)越純，證明當(dāng)前劃分規(guī)則就越合適.生成決策樹模型后，對決策樹進(jìn)行剪枝操作，即后剪枝，將決策樹模型中的冗余子樹用葉節(jié)點來代替，防止過擬合，提高決策樹計算精度和泛化能力.

算法3.大數(shù)據(jù)環(huán)境下的投票特征選擇算法

輸入：數(shù)據(jù)集U；

輸出：數(shù)據(jù)子集U*.

1.初始化空集U*用于儲存特征選擇的集合；

2.將特征選擇的數(shù)據(jù)集進(jìn)行預(yù)處理；

3.其中將U隨機分成L份部署到L個節(jié)點上；

4.對數(shù)據(jù)子集UL使用決策樹算法進(jìn)行分類，訓(xùn)練出決策樹分類器DT；

8.ReturnU*.

3.1 MapReduce環(huán)境下的投票特征選擇算法的實現(xiàn)過程

本文主要解決大數(shù)據(jù)中高維數(shù)據(jù)處理的問題，結(jié)合對決策樹分類算法和大數(shù)據(jù)平臺的分析，將本算法在MapReduce并行計算框架下進(jìn)行實現(xiàn)，可以有效地對高維數(shù)據(jù)執(zhí)行特征選擇.同時，將高維數(shù)據(jù)集在MapReduce框架中進(jìn)行建樹分類的操作，既提高了算法的容錯率，減少了算法的時間復(fù)雜度，實現(xiàn)了算法的可擴展性，還可根據(jù)算法的實際處理效率對MapReduce框架進(jìn)行計算空間擴展.算法4是在MapReduce框架上的投票特征選擇(記為MR-VT-FS)的計算流程，MapReduce分為Mapper和Reducer階段.

算法4.MR-VT-IS算法

Mapper階段

1. 數(shù)據(jù)預(yù)處理；

2. 初始化空集F，存放選擇出的特征子集；

3.DecisionTreetree=newDecisionTree(numFeatures)；

4.List>features=getFeatures(trainData)；

5.tree.train(trainData，features)；

6. 計算特征的對于tree分類器的信息增益率，選擇出大于闕值的特征

Reducer階段

1.tree=train(v2)；

2.vote=Tree(features)；

3.context.write(features，vote)；

4.ReturnU*.

3.2 Spark中的投票特征選擇的實現(xiàn)過程

在Spark并行計算框架下，決策樹分類首先查找可能劃分的分裂點(split)和桶(bin)，然后針對每次劃分split，計算每個樣本應(yīng)該所屬的bin，通過聚合每個bin的屬性信息計算每次split的信息增益率，并選擇信息增益率最大進(jìn)行劃分split，按照該劃分split對當(dāng)前節(jié)點進(jìn)行分割，直到滿足終止條件.為了防止過擬合，采用后剪枝，即在構(gòu)造決策樹完成后進(jìn)行剪枝，作為終止條件，本文設(shè)定闕值來停止創(chuàng)建分枝.算法5為Spark中的投票特征選擇算法(記為Spark-VT-FS).

算法5.Spark-VT-FS算法

輸入：訓(xùn)練集T；

輸出：被選出的特征集合U*.

1.對訓(xùn)練集中的樣本進(jìn)行預(yù)處理；

2.將數(shù)據(jù)廣播到L節(jié)點；

3.在L個子節(jié)點訓(xùn)練出L個DecisionTree分類器；

4.TREERDD=dataRDD_.mapPartitions()；

5.計算特征的信息增益率，選擇出大于闕值的特征

6.vote=DecisionTree(features)；

7.//投票篩選數(shù)據(jù)集合U*.

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

4.1 實驗環(huán)境

實驗所用到MapReduce和Spark大數(shù)據(jù)平臺，設(shè)置如下，由1個主節(jié)點和7個從節(jié)點結(jié)構(gòu)，用千兆以太網(wǎng)交換機H3C S5100連接，平臺操作系統(tǒng)為CentOS 6.4，CPU為Intel E5 2.20GHz，Hadoop版本是2.7.1，Spark版本是2.3.1.客戶端開發(fā)環(huán)境為Idea，JDK版本為jdk-1.8.0_144-windows-x64，表1為集群環(huán)境配置的詳細(xì)信息表.

表1 平臺各節(jié)點配置詳情

4.2 實驗指標(biāo)

本實驗的評價指標(biāo)為選擇出的特征數(shù)、測試精度和運算執(zhí)行時間.

選擇出的特征數(shù)：進(jìn)行特征選擇后選擇出的特征數(shù)，特征數(shù)越少，越能驗證大數(shù)據(jù)環(huán)境下的投票特征選擇算法選擇特征的有效性.

測試精度：數(shù)據(jù)集劃分為訓(xùn)練集和測試集，訓(xùn)練集訓(xùn)練出的分類器，用測試集對分類進(jìn)行測試，測試結(jié)果為測試精度，測試精度越高，證明特征選擇算法的性能越好.

運算執(zhí)行時間：從開始到完成大數(shù)據(jù)環(huán)境下的投票特征選擇所花費的時間.

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

本實驗采用UCI數(shù)據(jù)集進(jìn)行訓(xùn)練，將數(shù)據(jù)進(jìn)行歸一化處理提高計算的精度.所選的數(shù)據(jù)集均為含有類標(biāo)的高維數(shù)據(jù)集，其中含有一定的噪音，比較適合驗證特征選擇的實驗結(jié)果.Hadoop與Spark平臺的實驗數(shù)據(jù)信息如表2所示.

表2 數(shù)據(jù)集基本信息

4.4 MapReduce和Spark平臺上的實驗對比與分析

本小節(jié)主要是對在MapReduce和Spark平臺實現(xiàn)的大數(shù)據(jù)投票特征選擇算法進(jìn)行實驗對比，實驗比較的結(jié)果列于表3中.

由表3實驗結(jié)果可知，對于不同的數(shù)據(jù)集，在測試精度數(shù)值方面MR-VT-FS和Spark-VT-FS算法近乎相似，由MapReduce和Spark運行邏輯和本文算法結(jié)構(gòu)可知，MapReduce和Spark都采用分布式處理，并且執(zhí)行相同運算邏輯的算法，選擇出的特征也基本相同，故在測試精度相仿，但兩種算法的在不同的平臺上所運行的時間有著很大的差距，主要原因是在MapReduce和Spark大數(shù)據(jù)處理平臺上在數(shù)據(jù)處理方面采用完全不同的兩種策略，在Spark平臺上對數(shù)據(jù)進(jìn)行分區(qū)操作時雖然會產(chǎn)生比MapReduce更多的中間文件，但是在數(shù)據(jù)傳輸方面采用導(dǎo)管式傳輸，很大程度地減少了中間數(shù)據(jù)傳輸時間.在同步方式上，MapReduce采用同步式執(zhí)行方式，當(dāng)所有Map端的任務(wù)完成后，才會繼續(xù)執(zhí)行Reduce端的任務(wù)，而Spark采用異步式執(zhí)行方式，各個節(jié)點獨立地執(zhí)行計算，加快了運算效率，節(jié)省了中間數(shù)據(jù)排序時間，所以在運行時間上Spark會比MapReduce上節(jié)約更多時間.但也不意味著MapReduce對比Spark平臺沒有優(yōu)勢可言，在穩(wěn)定性方面MapReduce更加具有優(yōu)勢，在處理中間數(shù)據(jù)時，MapReduce會等待中間數(shù)據(jù)全部保存后再進(jìn)行后續(xù)計算，使性能方面的要求減弱，保證算法運行更為穩(wěn)定，適合長期后臺運行.當(dāng)處理需要長期存儲的數(shù)據(jù)時MapReduce中的HDFS可以提供多種存儲方式和巨大的存儲空間，此外，MapReduce還具有安全功能和控制權(quán)限功能，所以MapReduce在穩(wěn)定性上更具有優(yōu)勢.

表3 MapReduce和Spark上各數(shù)據(jù)集實驗的比對

綜上所述，雖然在MR-VT-FS和Spark-VT-FS算法的程序運行思想和算法邏輯相同，但在兩個平臺采用了兩種不同的執(zhí)行方式，導(dǎo)致在算法執(zhí)行效率上差異較大，在數(shù)據(jù)的傳輸調(diào)度方面，MapReduce會對數(shù)據(jù)進(jìn)行暫存，當(dāng)滿足執(zhí)行下一步的條件，才會對數(shù)據(jù)進(jìn)行處理，而Spark采用導(dǎo)管式傳輸，將數(shù)據(jù)直接進(jìn)行處理，大幅減少了同步的次數(shù)和傳輸時間，所以Spark在算法運行時間上有更好的表現(xiàn).但在穩(wěn)定性方面，MapReduce提供了相對簡單的運行框架、豐富的存儲資源和諸多安全保障功能，使MapReduce在計算穩(wěn)定性上表現(xiàn)更佳.

4.5 與其他算法的實驗對比與分析

表4是本文算法與單變量特征選擇算法和基于遺傳算法的特征選擇算法對相同的高維數(shù)據(jù)集進(jìn)行特征選擇的實驗結(jié)果.

表4 在不同數(shù)據(jù)集上特征選擇實驗結(jié)果

單變量特征選擇算法(Univariate feature selection)是一種常用的特征選擇方法，該方法思路簡單，具有通用性，采用卡方檢驗來對數(shù)據(jù)集的每個特征進(jìn)行評價，從而衡量每個特征對分類的貢獻(xiàn)大小，選擇出對分類貢獻(xiàn)最大的若干個特征.遺傳算法(GA)是一種模擬進(jìn)化算法，通過數(shù)學(xué)方式模擬生物界中的進(jìn)化過程，借助群體搜索來搜尋最優(yōu)個體，找到問題的最優(yōu)解.GA算法其中每個個體由一串0-1碼表示，1表示選取該個體，0表示不選該個體，通過模擬交叉、變異、選擇來模擬生物界中生物進(jìn)化的過程，通過選擇適應(yīng)度最優(yōu)的個體來完成特征選擇.

在搜索策略方面，本文算法和遺傳算法都屬于群體搜索，單變量特征選擇屬于逐個搜索，通過不同的搜索方式，便于比較算法的性能優(yōu)劣.在算法邏輯方面，本文算法和遺傳算法都屬于迭代算法，但不同的是遺傳算法計算的是最優(yōu)生存率，決策樹算法計算的是當(dāng)前特征的最優(yōu)適應(yīng)程度.為了便于與本文算法進(jìn)行比較，將選出的特征的參數(shù)設(shè)置為與本文選出的特征數(shù)相同.

從表4可以看出，在較小的數(shù)據(jù)集中，本文算法和Univariate-FS、GA算法的測試精度近似相同，但是隨著數(shù)據(jù)規(guī)模的增大和維度的提升，本文提出的方法具有更高的測試精度，代表具有更優(yōu)的計算性能.而從選擇出的特征數(shù)上來看，本文算法選擇出的特征集，在維度較低的數(shù)據(jù)上選出的特征數(shù)幾乎相同，但在高維度的數(shù)據(jù)集上選擇出了更少的特征，證明本文算法提出的大數(shù)據(jù)環(huán)境下的投票特征選擇算法，可以有效地從高維數(shù)據(jù)集中選擇出更具代表性的特征子集，降低高維數(shù)據(jù)集的維度.通過極限學(xué)習(xí)機(ELM)[37]對原始數(shù)據(jù)集和選擇出的特征子集進(jìn)行比對驗證，發(fā)現(xiàn)選擇出的特征子集可以有效地代替原數(shù)據(jù)集進(jìn)行計算，達(dá)到了數(shù)據(jù)降維和降低計算復(fù)雜度目的.

5 結(jié) 論

本文提出了大數(shù)據(jù)環(huán)境下的投票特征選擇，在MapReduce和Spark大數(shù)據(jù)處理平臺上都進(jìn)行了算法實現(xiàn)，并基于提出的算法在對MapReduce和Spark大數(shù)據(jù)處理平臺進(jìn)行了比較.此外，提出的算法還和單變量特征選擇算法與基于遺傳算法的特征選擇算法進(jìn)行了實驗比較.從MapReduce和Spark大數(shù)據(jù)平臺的實驗對比來看，因兩平臺對文件執(zhí)行方式和傳輸方式的不同，導(dǎo)致本算法在兩個大數(shù)據(jù)平臺上的適用程度有所不同，實驗指標(biāo)中，測試精度和選擇出的特征數(shù)相近，而在算法執(zhí)行時間上有較大差異，而差異主要在于MapReduce平臺提供的是更好的穩(wěn)定性和容錯性，而Spark平臺上保證的是算法具有更高的執(zhí)行效率.從本文提出的算法與單變量特征選擇算法和遺傳算法的實驗結(jié)果比較發(fā)現(xiàn)，本文提出的算法對高維數(shù)據(jù)集進(jìn)行特征選擇時，具有更高的計算精度，選擇出的特征子集更加精煉，證明本文提出的大數(shù)據(jù)環(huán)境下的投票特征選擇算法在高維數(shù)據(jù)特征選擇上具有更優(yōu)的執(zhí)行效率，并且能選出更具代表性的特征子集，降低數(shù)據(jù)維度.綜上所述，本文提出的算法是行之有效的.