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

（1.浙江工商大學信息學院 杭州310018；2.浙江工商大學現(xiàn)代商貿(mào)研究中心 杭州310000）

1 引言

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

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

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

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

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

2 相關理論研究

2.1 集成分類理論

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

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

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

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

綜合上述兩者的基于聚合方式的集成分類器[10]，如圖3所示，通過m種學習算法Li（i=1,2,…,m）對緩存中的數(shù)據(jù)塊Dj（j=1,2,…,n）學習得到集成分類器中的基分類器fij，即fij=Li(Dj)，其中i表示算法集中的第i種算法，j表示緩存中的第j個數(shù)據(jù)塊?；诰酆戏绞降募煞诸惼骺捎弥^詞邏輯表示，如式（3），時間復雜度為O(mnlg(n))。學習的基分類器構成了一個m×n階的分類器矩陣（CM）。

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

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

2.2 云計算技術

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

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

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

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

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

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

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

3.2 并行集成分類器算法

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

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

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主要用于并行學習產(chǎn)生的基分類器對預測樣本進行分類，如下所示。

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主要用于對預測分類進行加權統(tǒng)計得出最終分類結果，如下所示。

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節(jié)點、網(wǎng)絡的配置比較繁瑣，并且自行搭建的計算環(huán)境性相對不穩(wěn)定，所以本文選擇在Amazon第三方云平臺上進行模擬實驗，因為它免除了搭建平臺的復雜操作，使研究重點放在MapReduce邏輯處理上，圖6為Amazon云計算平臺主界面。

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

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

表1 實驗數(shù)據(jù)信息匯總

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

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

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

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

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

表2 混合矩陣

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

表3 EMapReduce在Amazon Commerce Reviews Set數(shù)據(jù)上分類準確率

表4 EMapReduce在Adult Data Set數(shù)據(jù)上分類準確率

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

5 結束語

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

參考文獻

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

2 付忠良.分類器線性組合的有效性和最佳組合問題的研究.計算機研究與發(fā)展，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 郝紅衛(wèi),王志彬,殷緒成.分類器的動態(tài)選擇與循環(huán)集成方法.自動化學報，2011,37(11):1 291～1 295

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

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

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

8 錢進,苗奪謙,張澤華.云計算環(huán)境下差別矩陣知識約簡算法研究.計算機學報，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