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

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

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

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


3 仿真實驗