基于MapReduce技術的并行集成分類算法*

琚春華，鄒江波，張 芮，魏建良

（1.浙江工商大學信息學院 杭州310018；2.浙江工商大學現代商貿研究中心 杭州310000）

1 引言

隨著信息技術在全球范圍內的普及，各行各業已經積累了大規模的行業數據，如電子商務行業中的用戶消費數據、瀏覽商品數據、商品評論數據，生產制造業中的生產數據，科學研究領域的實驗數據等，這些數據背后隱藏著許多有價值的信息和知識可被廣泛用于各種應用，如市場分析、欺詐檢測、顧客保有、產品控制和科學探索等[1]。

設計分類器是模式識別系統的核心，而基分類器的選擇和集成策略是集成分類算法的關鍵[2]。基分類器的選擇實質上是分類算法的選擇，選擇適合挖掘場景的算法是最終分類準確與否的決定因素之一，集成策略的好壞也會影響最終的分類結果，最常用的策略是對各分類器的分類結果進行加權組合，權重反映了各分類器對最終分類結果的影響。

[2]和[3]指出要設計高精度分類器并不容易，但設計出比隨機猜測略好的簡單分類器卻相對容易，因此可以將多個簡單分類器進行組合來提升分類精度，并從理論上證明了該假設的正確性。參考文獻[4]利用不同分類器模型之間的互補性,動態選擇出對目標有較高識別率的分類器組合,使參與集成的分類器數量能夠隨識別目標的復雜程度而自適應地變化,并根據可信度實現系統的循環集成。參考文獻[5]基于Stacking多分類器組合策略，構造了一個兩層的疊加式框架結構，融入可能的上下文信息作為情景特征向量輸入到各層的4種分類器中進行組合，并在中文組塊識別中取得了較好的效果。參考文獻[6]針對AdaBoost算法在迭代后期，訓練基分類器越來越集中于某一小區域樣本上，不能體現出不同區域分類特征的問題，利用待測樣本與各分類器的全信息相關度描述基分類器的局部分類性能，提出了基于全信息相關度的動態多分類器融合方法，根據各分類器對待測樣本的局部分類性能動態確定分類器組合和權重。上述研究在一定程度上通過改進集成分類的集成策略，提高了小數據集上分類算法的效率。

當面對數據流數據時，目前提出的集成分類算法都無法高效地進行分類，因此，運用并行集成分類方法是解決數據流挖掘問題的一個重要途徑。已有并行集成的方法僅在生產制造業研究中有所體現，但在數據挖掘領域還有待研究，參考文獻[7]和[8]基于已有并行知識約簡算法多任務并行的優點，利用屬性集的不可辨識性和MapReduce技術，設計了適合大規模數據集的差別矩陣知識約簡算法，并通過實驗說明了該約簡算法能夠高效地處理大量數據。參考文獻[9]基于模塊化集成學習的思想，設計了與云平臺相結合的增量分類方法，雖然沒有對云環境下的集成策略進行深入研究，但為本文并行集成處理數據流奠定了基礎。

針對已有集成分類算法只適合作用于小規模數據集的缺點，剖析了集成分類器的特性，采用基于聚合方式的集成分類器和云計算的MapReduce技術設計了處理大規模數據的集成分類算法（EMapReduce），并在Amazon計算集群上模擬實驗，實驗結果表明該算法具有一定的高效性和可行性。

2 相關理論研究

2.1 集成分類理論

集成分類器處理大規模數據的方式主要有3種：基于水平方式的集成分類器、基于垂直方式的集成分類器以及綜合兩者的基于聚合方式的集成分類器，如圖1～3所示。

集成分類器增量處理大規模數據集，將連續達到的數據緩存，再對緩存數據等量分塊得到數據塊{Di}+∞i=1，由于存儲空間的局限性，系統內存最多只能連續容納n個包含一定數量記錄的數據塊。

基于水平方式的集成分類器通過選擇學習算法L對緩存數據塊Di學習得到集成分類器中的基分類器fi，即fi=L(Di)，i=1,2,…,n。再對D1，D2，…,Dn已標記類別數據塊中學習的基分類器集成，達到對Dn+1數據塊分類的目的。基分類器fi對Dn+1中的每條記錄預測分類結果，最后采用類似專家投票的方式得出分類結果。基于水平方式的集成分類器可用謂詞邏輯表示，如式（1），時間復雜度為O(nlg(n))。

基于垂直方式的集成分類器通過選擇學習算法Lj（j=1,2,…,m）隨機選擇緩存中的某一數據塊Dn學習得到集成分類器中的基分類器fj，即fj=Lj(Dn)。如圖2所示，該方式與水平集成分類器不同的是，它隨機抽取一個數據塊并采用不同的挖掘算法進行學習得到集成分類器。不同算法的基分類器fj對Dn+1中的每條記錄分別預測分類結果，最后采用類似專家投票的方式得出分類結果。基于垂直方式的集成分類器可用謂詞邏輯表示，如式（2），時間復雜度為O(mnlg(n))。

綜合上述兩者的基于聚合方式的集成分類器[10]，如圖3所示，通過m種學習算法Li（i=1,2,…,m）對緩存中的數據塊Dj（j=1,2,…,n）學習得到集成分類器中的基分類器fij，即fij=Li(Dj)，其中i表示算法集中的第i種算法，j表示緩存中的第j個數據塊。基于聚合方式的集成分類器可用謂詞邏輯表示，如式（3），時間復雜度為O(mnlg(n))。學習的基分類器構成了一個m×n階的分類器矩陣（CM）。

聚合集成分類器克服了水平集成分類器僅用一種算法學習而導致的過度擬合問題以及垂直集成分類器僅隨機選擇數據學習造成的欠學習問題，其處理數據流的能力良好，如降低了噪聲數據對分類模型的干擾以及目標分類模型隨時間變化產生的概念漂移。

理論上基于聚合方式的集成分類器在大規模數據時具有良好的性質，其時間復雜度與基于垂直方式的集成分類器相同，在實際應用中如果每個數據塊Dj都用i種算法學習集成（i=1,2,…,m，j=1,2,…,n），由于計算機內存資源的限制，當m、n取值較小時，一臺計算機需要運行較長時間進行分類學習，但當選擇的算法較多，數據塊劃分較細時，僅用一臺機器運算聚合集成分類算法顯然是不合適的。

2.2 云計算技術

為了應對類似上述大規模數據計算的難題，MapReduce編程模型應運而生。該模型由Google公司提出，其良好的易用性和擴展性，得到了IT界和學術界的廣泛支持。Hadoop是MapReduce模型的開源實現，并且已經在Yahoo、Facebook、IBM、百度、中國移動等多家企業中成功應用。

MapReduce以函數方式提供了Map和Reduce兩種方式進行分布式計算。Map相對獨立且并行運行，對存儲系統中的文件按行處理，并產生鍵值（key，value）對。Reduce以Map的輸出作為輸入，相同key的記錄匯聚到同個Reduce，所有Reduce任務并歸處理輸出組成最終結果，其流程如圖4所示。

3 構建基于云計算的并行集成分類器

3.1 適用于MapReduce編程模式的并行集成分類模型

MapReduce編程模式彌補了集成分類器由于多基分類器在一臺計算機上并行學習造成內存資源不足的問題。本文提出的并行集成分類算法基于聚合方式的集成分類器，利用MapReduce模式實現基分類器并行計算，EMapReduce算法結構如圖5所示。

基于Hadoop將連續到達的數據{Di}切塊存儲到計算集群的分布式文件系統（HDFS）中，Hadoop負責管理切塊數據{di}，其key值為所屬數據塊Di。計算集群中的計算機Mi（i為計算集群數量）采用m種算法對本地存儲的相應切塊數據并行學習得到基分類器Ci，對同機器基分類器的分類結果Reduce（key值為機器號，value值為分類結果）得到該機器的分類結果，最后將所有集群的分類結果“投票”獲得集成分類器。

并行集成分類模型將數據切塊處理，降低了噪聲數據對學習的干擾，通過并行學習提高了計算效率，選擇多種學習算法，防止了分類結果過度擬合，采用集成的方法削弱了概念漂移對模型的影響。

3.2 并行集成分類器算法

在云計算環境下并行集成算法中，Map函數主要完成切塊數據的基分類器學習，而Reduce函數主要計算同機器中不同算法基分類器的分類結果。下面給出處理大規模數據的并行集成分類算法EMapReduce，分別設計1個Map函數（算法1），用于并行學習生成基分類器，2個Reduce函數（算法2，算法3），用于計算分類結果。

EMapReduce算法1主要用于并行學習產生基分類器，如下所示。

Input:The chunk id(Key),the labeled training instance(Value)

Initialize threshold use to create base classifier;

Vtrain←training instances in value from chunk i which have stored in HDFS;

Vtest←all test instances read from HDFS;

N←Number of test instances in Vtest;

Ci←algorism(Vtrain);//create a base classifier use algorism i

For j=1 to N

Accurate←Ci(Vtest(j));//verify the base classifier accurate through test data

End for

If base classifier accurate>accurate threshold

Save this classifier in the map which use to predict prediction data class label

EMapReduce算法2主要用于并行學習產生的基分類器對預測樣本進行分類，如下所示。

Input:The chunk which is except to predict class label,the key is chunk instance id,the unlabeled data is value

Output:key is the base classifier use for predict class label,value is list of the predict label

Vpredict←prediction data in HDFS;

N←Number of test instances in Vpredict;

For j=1 to N

List label←Ci(Vpredict j));//use trained base classifier to predict test instances class and return the list of predict class label

End for

key’←this base classifier id;

value’←List label;

EMapReduce算法3主要用于對預測分類進行加權統計得出最終分類結果，如下所示。

Input:the list of predict class label from every node base classifier

Output:final classification of this unlabeled chunk data

For each label in the list

If predict label is Li;

Li++;

End for

Final class label of this chunk data←max{Li}(i=1,2…k);

Return Final class label;

4 實驗驗證

本文沒有自行搭建實驗所需的云計算平臺，因為關于Hadoop節點、網絡的配置比較繁瑣，并且自行搭建的計算環境性相對不穩定，所以本文選擇在Amazon第三方云平臺上進行模擬實驗，因為它免除了搭建平臺的復雜操作，使研究重點放在MapReduce邏輯處理上，圖6為Amazon云計算平臺主界面。

本實驗所有的數據均來自UCI官網，主要選擇了兩大數據集，第一個是Amazon Commerce Reviews Set數據集，數據源來自客戶對亞馬遜電子商務網站商品的評論，數據實例由50名活躍用戶（數據集中用戶擁有唯一的姓名）對商品的評論構成，選擇了每個用戶的30條評論，共1 500條實例，本實驗選擇1 000條實例作為訓練數據，500條數據作為測試數據，雖然數據量較少，但是該數據集具有高維性，共10 000個屬性，具有如此高維度的原因是數據集將不同的單詞作為一個維度，如果用戶的評論中包含該單詞，則實例中用該單詞出現的次數表示，如果該單詞沒有出現則用0表示，最后實例類別為50名評論用戶的唯一姓名。第2個是Adult數據集，數據源來自美國人口普查數據，共計48 842條，其中包含訓練數據32 561條，測試數據16 281條，根據實例的性別、年齡、受教育水平、平均每周工作時間、工作性質等14個屬性，對實例的實際年薪是否達到50 000美元進行分類。表1是對實驗數據信息的匯總。

通過Amazon S3功能添加并行計算所需的實驗數據，如圖7所示，其中包含2個訓練數據文件、2個測試數據文件以及實現MapReduce接口的并行集成分類器算法jar包。

表1 實驗數據信息匯總

通過Amazon Elastic MapReduce功能達到配置程序的目的。用Create Job Flow配置數據源路徑、主程序路徑、結果輸出路徑，計算集群個數，當Job Flow建立完成以后，如圖8所示，有1臺Master主機和3臺Core主機，共4臺主機構成計算集群。

圖9為Amazon集群上對Adult Data Set數據集完成計算的截圖，可以看到在云平臺上僅用10 min便完成了對數據集分類的任務。

當MapReduce任務完成后云計算主機自動停止并在輸出目錄中輸出了此次計算的日志數據，如圖10所示。

圖11為計算完成后Master主機的資源使用情況，包括磁盤讀寫數、網絡輸入輸出數、CPU使用百分比等。通過該圖可以觀測云計算的資源使用情況。

最后在Amazon S3中查看輸出日志，選取混淆矩陣統計并行分類算法的分類準確率，混合矩陣的定義見表2，分類的平均準確率可由下式計算得出：

表2 混合矩陣

Amazon上并行集成分類算法對Amazon Commerce Reviews Set、Adult Data Set測試數據正負實例的分類結果，見表3和表4。

表3 EMapReduce在Amazon Commerce Reviews Set數據上分類準確率

表4 EMapReduce在Adult Data Set數據上分類準確率

本文將Amazon Commerce Reviews Set、Adult Data Set數據集在weka上進行實驗，但由于數據維度較高，實驗的運行時間較長，并沒有得到期望的實驗結果，相比較而言在云平臺上對大規模數據進行分類計算具有一定的可行性。

5 結束語

經典的集成分類算法在處理小數據集時，有較高的分類準確性，但面對大規模數據集時，會因為基分類器的不斷學習及其在內存中的數目不斷增多而導致機器分類效率降低，這顯然不適合處理如今的海量數據。針對已有集成分類算法只適合作用于小規模數據集的缺點，剖析了集成分類器的特性，采用基于聚合方式的集成分類器和云計算的MapReduce技術設計了集成分類算法（EMapReduce），達到并行處理大規模數據的目的。并在Amazon計算集群上模擬實驗，實驗結果表明該算法具有一定高效性和可行性。

參考文獻

1 韓家煒,坎伯.數據挖掘:概念與技術.北京：機械工業出版社，2001

2 付忠良.分類器線性組合的有效性和最佳組合問題的研究.計算機研究與發展，2009,46(7)：1 206～l 216

3 Valiant I G．A theory of the learnable．Communications of the ACM，1984，27(11)：1 134～1 142

4 郝紅衛,王志彬,殷緒成.分類器的動態選擇與循環集成方法.自動化學報，2011,37(11):1 291～1 295

5 李珩,朱靖波,姚天順.基于Stacking算法的組合分類器及其應用于中文組塊分析.計算機研究與發展，2005,42(5):844～848

6 張健沛,程麗麗,楊靜.基于全信息相關度的動態多分類器融合.計算機科學，2008,35(3):188～190

7 錢進,苗奪謙,張澤華.云計算環境下知識約簡算法.計算機學報，2011,34(12):2 333～2 343

8 錢進,苗奪謙,張澤華.云計算環境下差別矩陣知識約簡算法研究.計算機學報，2011,38(8):193～196

9 李曼.云計算平臺上的增量分類研究.微型機與應用，2011,30(18):65～68

10 Zhang Peng,Zhu Xingquan，Shi Yong.Robust ensemble learning for mining noisy data streams.Decision Support Systems，2011（50）:469～479

11 Dean J，Ghemawat S.MapReduce:simplified data processing on large clusters.Osdi,2004(34):137～150