大數據環境下的投票特征選擇算法

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

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

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

1 引 言

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

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

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

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

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

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

2 基礎知識

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

2.1 決策樹

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

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

圖1 決策樹算法流程圖

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

(1)

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

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

(2)

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

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

(3)

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

(4)

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

2.2 ID3算法和C4.5算法

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

算法1.ID3算法

輸入：訓練樣本S；

輸出：一棵決策樹Ti.

1.初始化閾值；

2.判斷該樣本的類別，若為同一類Di，則標記類別為D，并返回單節點樹T，否則執行下一個樣本；

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

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

5.若AMax的信息增益小于閾值，返回T；否則，按AMax的不同值AMaxi將對應的D劃分為其他類別，每類產生一個子節點，對應屬性值為AMaxi，增加T；

6.D=Di，A=AMax，在所有子節點遞歸調用2-5步；

7.得到子樹Ti并返回.

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

算法2.C4.5算法

輸入：訓練樣本S；

輸出：一棵決策樹Ti.

1.設置根節點N；

2.若S屬于同一類，則返回N為葉節點，標記為類C；

3.Ifattributes=null或S中剩余的樣例數少于闕值，返回N為葉節點，標記N為S中出現最多的類；

4.For eachattributes

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

6.End for

7.For新的葉子節點

8.若該葉子節點樣本子集S′空，則分裂此葉子節點生成新葉節點，并標記為S中出現最多的類；

9.Else

10. 在該葉子節點上繼續分裂；

11.End for

12.后剪枝.

13.得到子樹Ti并返回；

2.3 MapReduce和Spark基礎介紹

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

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

3 大數據環境下的投票特征選擇算法介紹

本節首先介紹大數據環境下的投票特征選擇，然后分別介紹在MapReduce平臺和Spark平臺上實現大數據投票特征選擇算法的具體實現思路.圖2為大數據投票特征選擇流程圖.

圖2 大數據環境下的投票特征選擇算法流程圖

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

算法3.大數據環境下的投票特征選擇算法

輸入：數據集U；

輸出：數據子集U*.

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

2.將特征選擇的數據集進行預處理；

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

4.對數據子集UL使用決策樹算法進行分類，訓練出決策樹分類器DT；

8.ReturnU*.

3.1 MapReduce環境下的投票特征選擇算法的實現過程

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

算法4.MR-VT-IS算法

Mapper階段

1. 數據預處理；

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中的投票特征選擇的實現過程

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

算法5.Spark-VT-FS算法

輸入：訓練集T；

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

1.對訓練集中的樣本進行預處理；

2.將數據廣播到L節點；

3.在L個子節點訓練出L個DecisionTree分類器；

4.TREERDD=dataRDD_.mapPartitions()；

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

6.vote=DecisionTree(features)；

7.//投票篩選數據集合U*.

4 實驗結果與分析

4.1 實驗環境

實驗所用到MapReduce和Spark大數據平臺，設置如下，由1個主節點和7個從節點結構，用千兆以太網交換機H3C S5100連接，平臺操作系統為CentOS 6.4，CPU為Intel E5 2.20GHz，Hadoop版本是2.7.1，Spark版本是2.3.1.客戶端開發環境為Idea，JDK版本為jdk-1.8.0_144-windows-x64，表1為集群環境配置的詳細信息表.

表1 平臺各節點配置詳情

4.2 實驗指標

本實驗的評價指標為選擇出的特征數、測試精度和運算執行時間.

選擇出的特征數：進行特征選擇后選擇出的特征數，特征數越少，越能驗證大數據環境下的投票特征選擇算法選擇特征的有效性.

測試精度：數據集劃分為訓練集和測試集，訓練集訓練出的分類器，用測試集對分類進行測試，測試結果為測試精度，測試精度越高，證明特征選擇算法的性能越好.

運算執行時間：從開始到完成大數據環境下的投票特征選擇所花費的時間.

4.3 實驗數據

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

表2 數據集基本信息

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

本小節主要是對在MapReduce和Spark平臺實現的大數據投票特征選擇算法進行實驗對比，實驗比較的結果列于表3中.

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

表3 MapReduce和Spark上各數據集實驗的比對

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

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

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

表4 在不同數據集上特征選擇實驗結果

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

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

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

5 結 論

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