摘 要： 針對已有增量分類算法只是作用于小規(guī)模數(shù)據(jù)集或者在集中式環(huán)境下進(jìn)行的缺點(diǎn)，提出一種基于Hadoop云計(jì)算平臺的增量分類模型，以解決大規(guī)模數(shù)據(jù)集的增量分類。為了使云計(jì)算平臺可以自動地對增量的訓(xùn)練樣本進(jìn)行處理，基于模塊化集成學(xué)習(xí)思想，設(shè)計(jì)相應(yīng)Map函數(shù)對不同時刻的增量樣本塊進(jìn)行訓(xùn)練，Reduce函數(shù)對不同時刻訓(xùn)練得到的分類器進(jìn)行集成，以實(shí)現(xiàn)云計(jì)算平臺上的增量學(xué)習(xí)。仿真實(shí)驗(yàn)證明了該方法的正確性和可行性。
關(guān)鍵詞： 增量分類；Hadoop；云計(jì)算

隨著信息技術(shù)和生物技術(shù)突飛猛進(jìn)的發(fā)展，科學(xué)研究和實(shí)際應(yīng)用中產(chǎn)生了海量數(shù)據(jù)，并且這些數(shù)據(jù)每天都在增加，為了將每天產(chǎn)生的新數(shù)據(jù)納入到新的學(xué)習(xí)系統(tǒng)，需要利用增量學(xué)習(xí)。增量學(xué)習(xí)比較接近人類自身的學(xué)習(xí)方式，可以漸進(jìn)地進(jìn)行知識的更新，修正和加強(qiáng)以前的知識，使得更新后的知識能適應(yīng)更新后的數(shù)據(jù)，而不必重新學(xué)習(xí)全部數(shù)據(jù)，從而降低了對時間和空間的需求。模塊化是擴(kuò)展現(xiàn)有增量學(xué)習(xí)能力的有效方法之一[1]，而集成學(xué)習(xí)（Ensemble Learning）一直是機(jī)器學(xué)習(xí)領(lǐng)域的一個研究熱點(diǎn)[2-6]，許多模塊化增量分類算法[7-9]正是基于二者提出的。
云計(jì)算(Cloud Computing)這一新名詞從2007年第3季度誕生起就在學(xué)術(shù)界和產(chǎn)業(yè)界引起了轟動，Google、IBM、百度、Yahoo等公司都開始進(jìn)行“云計(jì)算”的部署工作。云計(jì)算是分布式計(jì)算(Distributed Computing)、并行計(jì)算(Parallel Computing)和網(wǎng)格計(jì)算(Grid Computing)的發(fā)展與延伸。在云計(jì)算環(huán)境下，互聯(lián)網(wǎng)用戶只需要一個終端就可以享用非本地或遠(yuǎn)程服務(wù)集群提供的各種服務(wù)（包括計(jì)算、存儲等），真正實(shí)現(xiàn)了按需計(jì)算，有效地提高了云端各種軟硬件資源的利用效率。隨著云計(jì)算技術(shù)的日益成熟，云計(jì)算也為解決海量數(shù)據(jù)挖掘所面臨的問題提供了很好的基礎(chǔ)[10]。雖然在機(jī)器學(xué)習(xí)領(lǐng)域，對增量學(xué)習(xí)進(jìn)行了較深入的研究，但是在云計(jì)算環(huán)境下，還沒有相關(guān)文獻(xiàn)討論利用增量分類提高云計(jì)算環(huán)境下海量數(shù)據(jù)挖掘的效率問題。本文基于模塊化的集成學(xué)習(xí)思想，研究在開源云計(jì)算平臺Hadoop[11]上的增量分類方法。
1 Hadoop云平臺的體系結(jié)構(gòu)
在現(xiàn)有的云計(jì)算技術(shù)中， Apache軟件基金會(Apache Software Foundation) 組織下的開源項(xiàng)目Hadoop是一個很容易支持開發(fā)和并行處理大規(guī)模數(shù)據(jù)的分布式云計(jì)算平臺，具有可擴(kuò)展、低成本、高效和可靠性等優(yōu)點(diǎn)。程序員可以使用Hadoop中的Streaming工具(Hadoop為簡化Map/Reduce的編寫，為讓不熟悉Java的程序員更容易在Hadoop上開發(fā)而提供的一個接口)使用任何語言編寫并運(yùn)行一個Map/Reduce作業(yè)。Hadoop項(xiàng)目包括多個子項(xiàng)目，但主要是由Hadoop分布式文件系統(tǒng)HDFS（Hadoop Distributed File System）和映射/化簡引擎（Map/Reduce Engine）兩個主要的子項(xiàng)目構(gòu)成。
1.1 分布式文件系統(tǒng)HDFS
Hadoop實(shí)現(xiàn)了一個分布式文件系統(tǒng)(Hadoop Distribu-
tedFile System)，簡稱HDFS。HDFS采用Master/Slave架構(gòu)，一個HDFS集群由一個NameNode節(jié)點(diǎn)和若干DataNode節(jié)點(diǎn)組成。NameNode節(jié)點(diǎn)存儲著文件系統(tǒng)的元數(shù)據(jù)，這些元數(shù)據(jù)包括文件系統(tǒng)的名字空間等，并負(fù)責(zé)管理文件的存儲等服務(wù)，程序使用的實(shí)際數(shù)據(jù)并存放在DataNode中，Client是獲取分布式文件系統(tǒng)HDFS文件的應(yīng)用程序。圖1是HDFS結(jié)構(gòu)圖。
圖1中，Master主要負(fù)責(zé)NameNode及JobTracker的工作，JobTracker的主要職責(zé)是啟動、跟蹤和調(diào)度各個Slave任務(wù)的執(zhí)行。還會有多臺Slave，每一臺Slave通常具有DataNode的功能并負(fù)責(zé)TaskTracker的工作。TaskTracker根據(jù)應(yīng)用要求來結(jié)合本地數(shù)據(jù)執(zhí)行Map任務(wù)以及Reduce任務(wù)。

1.2 Map/Reduce分布式并行編程模型
Hadoop框架中采用了Google提出的云計(jì)算核心計(jì)算模式Map/Reduce，它是一種分布式計(jì)算模型，也是簡化的分布式編程模式[12]。Map/Reduce把運(yùn)行在大規(guī)模集群上的并行計(jì)算過程抽象成兩個函數(shù)：Map和Reduce，其中，Map把任務(wù)分解成多個任務(wù)，Reduce把分解后的多個任務(wù)處理結(jié)果匯總起來，得到最終結(jié)果。圖2介紹了用Map/Reduce處理數(shù)據(jù)的過程。一個Map/Reduce操作分為兩個階段：映射和化簡。

在映射階段（Map階段），Map/Reduce框架將用戶輸入的數(shù)據(jù)分割為N個片段，對應(yīng)N個Map任務(wù)。每一個Map的輸入是數(shù)據(jù)片段中的鍵值對<K1，V1>集合，Map操作會調(diào)用用戶定義的Map函數(shù)，輸出一個中間態(tài)的鍵值對<K2，V2>。然后，按照中間態(tài)K2將輸出的數(shù)據(jù)進(jìn)行排序，形成<K2，list(V2)>元組，這樣可以使對應(yīng)于同一個鍵的所有值的數(shù)據(jù)都集合在一起。最后，按照K2的范圍將這些元組分割成M個片段，從而形成M個Rdeuce任務(wù)。
在化簡階段(Reduce階段)，每一個Reduce操作的輸入是Map階段的輸出，即<K2，list(V2)>片段，Reduce操作調(diào)用用戶定義的Reduce函數(shù)，生成用戶需要的結(jié)果<K3，V3>進(jìn)行輸出。
2 基于Map/Reduce的模塊化增量分類模型
基于Map/Reduce的增量分類模型，主要思想是Map函數(shù)對訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練，得到基于不同時刻增量塊的分類器，Reduce函數(shù)利用Map訓(xùn)練好的分類器對測試樣本進(jìn)行預(yù)測，并且將不同時刻訓(xùn)練得到的分類器進(jìn)行集成，得到最終的分類結(jié)果。基于Map/Reduce的增量分類模型如圖3所示。當(dāng)t1時刻有海量的訓(xùn)練樣本到達(dá)時，通過設(shè)置Map任務(wù)的個數(shù)使得云平臺自動地對到達(dá)的海量樣本進(jìn)行劃分，每個Map的任務(wù)就是對基于劃分所得的樣本子集進(jìn)行訓(xùn)練得到一個基分類器。同一時刻的不同Map之間可以并行訓(xùn)練，從而得到t1時刻的增量分類系統(tǒng)。當(dāng)tT時刻的訓(xùn)練樣本到達(dá)以后，采取相同的步驟，得到tT時刻的不同基分類器，然后將這些分類器加入到tT-1時刻的增量分類系統(tǒng)以構(gòu)成tT時刻的增量分類系統(tǒng)。再采用Reduce函數(shù)將當(dāng)前增量分類系統(tǒng)里所有分類器進(jìn)行集成，集成方法可以采用投票法Majority Voting(MV)進(jìn)行。
2.1 Map過程
Map函數(shù)的主要功能就是建立不同時刻的增量分類系統(tǒng)。當(dāng)某一時刻有新的訓(xùn)練樣本到達(dá)時，Map便從HDFS將其讀取。通過設(shè)置Map任務(wù)的個數(shù)使得云平臺自動地對大規(guī)模的訓(xùn)練樣本進(jìn)行劃分，每一個Map任務(wù)完成基于一個劃分塊的分類訓(xùn)練，劃分后的不同塊可以并行訓(xùn)練，從而得到基于該時刻增量樣本集的不同分類器，然后將這些分類器加入上一時刻的增量分類系統(tǒng)以構(gòu)成當(dāng)前時刻的增量分類系統(tǒng)。Map函數(shù)偽代碼如下：


3 仿真實(shí)驗(yàn)