云計算平臺上的增量分類研究*

李 曼

(南京郵電大學 計算機學院，江蘇 南京210003)

隨著信息技術和生物技術突飛猛進的發展，科學研究和實際應用中產生了海量數據，并且這些數據每天都在增加，為了將每天產生的新數據納入到新的學習系統，需要利用增量學習。增量學習比較接近人類自身的學習方式，可以漸進地進行知識的更新，修正和加強以前的知識，使得更新后的知識能適應更新后的數據，而不必重新學習全部數據，從而降低了對時間和空間的需求。模塊化是擴展現有增量學習能力的有效方法之一[1]，而集成學習（Ensemble Learning）一直是機器學習領域的一個研究熱點[2-6]，許多模塊化增量分類算法[7-9]正是基于二者提出的。

云計算(Cloud Computing)這一新名詞從2007年第3季度誕生起就在學術界和產業界引起了轟動，Google、IBM、百度、Yahoo等公司都開始進行“云計算”的部署工作。云計算是分布式計算(Distributed Computing)、并行計算(Parallel Computing)和網格計算(Grid Computing)的發展與延伸。在云計算環境下，互聯網用戶只需要一個終端就可以享用非本地或遠程服務集群提供的各種服務（包括計算、存儲等），真正實現了按需計算，有效地提高了云端各種軟硬件資源的利用效率。隨著云計算技術的日益成熟，云計算也為解決海量數據挖掘所面臨的問題提供了很好的基礎[10]。雖然在機器學習領域，對增量學習進行了較深入的研究，但是在云計算環境下，還沒有相關文獻討論利用增量分類提高云計算環境下海量數據挖掘的效率問題。本文基于模塊化的集成學習思想，研究在開源云計算平臺Hadoop[11]上的增量分類方法。

1 Hadoop云平臺的體系結構

在現有的云計算技術中，Apache軟件基金會(A-pache Software Foundation)組織下的開源項目Hadoop是一個很容易支持開發和并行處理大規模數據的分布式云計算平臺，具有可擴展、低成本、高效和可靠性等優點。程序員可以使用Hadoop中的Streaming工具(Hadoop為簡化Map/Reduce的編寫，為讓不熟悉Java的程序員更容易在Hadoop上開發而提供的一個接口)使用任何語言編寫并運行一個Map/Reduce作業。Hadoop項目包括多個子項目，但主要是由Hadoop分布式文件系統HDFS（Hadoop Distributed File System）和映射/化簡引擎（Map/Reduce Engine）兩個主要的子項目構成。

1.1 分布式文件系統HDFS

Hadoop實現了一個分布式文件系統(Hadoop DistributedFile System)，簡稱HDFS。HDFS采用Master/Slave架構，一個HDFS集群由一個NameNode節點和若干DataNode節點組成。NameNode節點存儲著文件系統的元數據，這些元數據包括文件系統的名字空間等，并負責管理文件的存儲等服務，程序使用的實際數據并存放在DataNode中，Client是獲取分布式文件系統HDFS文件的應用程序。圖1是HDFS結構圖。

圖1中，Master主要負責NameNode及JobTracker的工作，JobTracker的主要職責是啟動、跟蹤和調度各個Slave任務的執行。還會有多臺Slave，每一臺Slave通常具有DataNode的功能并負責TaskTracker的工作。Task-Tracker根據應用要求來結合本地數據執行Map任務以及Reduce任務。

1.2 Map/Reduce分布式并行編程模型

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

在映射階段（Map階段），Map/Reduce框架將用戶輸入的數據分割為N個片段，對應N個Map任務。每一個Map的輸入是數據片段中的鍵值對＜K1，V1＞集合，Map操作會調用用戶定義的Map函數，輸出一個中間態的鍵值對＜K2，V2＞。然后，按照中間態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時刻的增量分類系統。當tT時刻的訓練樣本到達以后，采取相同的步驟，得到tT時刻的不同基分類器，然后將這些分類器加入到tT-1時刻的增量分類系統以構成tT時刻的增量分類系統。再采用Reduce函數將當前增量分類系統里所有分類器進行集成，集成方法可以采用投票法Majority Voting(MV)進行。

2.1 Map過程

Map函數的主要功能就是建立不同時刻的增量分類系統。當某一時刻有新的訓練樣本到達時，Map便從HDFS將其讀取。通過設置Map任務的個數使得云平臺自動地對大規模的訓練樣本進行劃分，每一個Map任務完成基于一個劃分塊的分類訓練，劃分后的不同塊可以并行訓練，從而得到基于該時刻增量樣本集的不同分類器，然后將這些分類器加入上一時刻的增量分類系統以構成當前時刻的增量分類系統。Map函數偽代碼如下：

(1)初始化：訓練分類算法相關參數；初始訓練數據集：

TR1={{Xi，yi}|Xi∈RD，yi∈{1，2， …，c}，1≤i≤N1}，Xi表示樣本，yi表示樣本類別，{1，2，…，c}表示類別標志集合，N1表示初始訓練樣本數，D表示樣本特征空間維數。

(2)設置Map任務給n個數，將TR1自動劃分成n塊，使得：TR1={TR11，TR12，…，TR1n}

(3)FOR m=1，2，…，n

①基于TR1m訓練得到分類器C1m

②將分類器C1m加入初始時刻的增量分類系統

END

(4)FOR j=2，3，…，T

①將在tj時刻采集的訓練集增量塊TRj劃分，使得：TRj={TRj1，TRj2，…，TRjn}；

②FOR m=1，2，…，n

（a）用 TRjm訓練得到基分類器 Cjm；

（b）將分類器Cjm加入tj-1時刻的增量分類系統，以構成tj時刻的增量學習系統；

END

END

}

2.2 Reduce過程

Reduce函數的主要功能是對當前時刻增量分類系統的分類器進行集成。集成策略可以采用簡單的投票法Majority Voting(MV)。也就是將tj時刻增量分類系統中各個基分類器的分類結果進行多數投票，得到票數多的類別作為測試樣本的類別。如果出現票數相等的情形，則進行隨機猜測。Reduce函數的偽代碼如下：

(1)初始化：當前增量數據采集時刻數 T；測試樣本 Xtest

(2)FOR j=1,2,…,T

(3)若所有 Cjm(Xtest)（j=1,2,…,T，m=1,2,…,n）均相同，則得到Xtest的類別Cjm(Xtest)，否則則根據多數投票的分類器組合策略輸出Xtest的類別。

}

3 仿真實驗

本文用三臺PC搭建了Hadoop云計算平臺，三臺PC的硬件配置均為2GRAM和AMD雙核CPU，各節點的操作系統為 Linux Centos 5.4，Hadoop版本為 0.19.2，JDK版本為1.6.0_12。實驗中一臺PC既部署NameNode和 JobTrack，也部署 DataNode和 TaskTrack，另兩臺 PC均部署 DataNode和 TaskTrack。

實驗對兩個數據集進行了仿真，第一個數據集是來自UCI的Adult[13]數據集,第二個是來自UCI的Mushrooms(每個實名屬性都被分解成若干個二進制屬性，初始的12號屬性由于丟失未使用)數據集。分類器采用SVM[14]。為了證明該方法的正確性，每個實驗分別在集中式和云平臺兩種環境下進行。兩種環境都將訓練樣本集隨機劃分為五等份以構成5個增量訓練子集，也就是按照時間順序進行了5次增量訓練。由于現實中采集的增量訓練樣本的規模可能很大，所以在云平臺環境中，通過設置Map的個數對樣本進行分解。本次實驗中Map的個數設為2，這樣每個增量訓練子集都會被云平臺自動劃分成兩塊，各塊之間可以進行并行訓練。為了與云平臺環境進行對比，在集中式環境中將每個子集手動均分成兩塊，每塊用來訓練一個分類器。每個實驗均采用了式（1）和式（2）兩種核函數。

其中，相關參數 γ=0.008，β0=0.009，β1=0，懲罰因子 C=1。實驗所用的兩個數據集的數據分布如表1所示。

表1 兩個數據集的數據特性

兩個增量分類系統在不同數據集上的分類性能如圖4所示。通過比較可知，集中式增量分類的準確率和Hadoop云平臺上增量分類準確率較為接近，證明了本文所提出的在Hadoop云平臺上實現增量分類方法的可行性和正確性。由于MV方法本身具有較大的波動性，故集中式和Hadoop云平臺環境中隨著訓練樣本的增加，增量分類系統的學習能力是曲折上升的。

本文提出了一種基于Hadoop云平臺的增量分類方法，仿真實驗表明，基于Hadoop云平臺的增量分類是可行的。與其他增量分類方法相比，該模型簡單，易于實現。通過設置平臺中Map任務的個數讓云平臺自動地對海量訓練樣本進行劃分，劃分后的各個任務相互獨立，可以進行并行訓練。這提高了海量數據的處理速度，基本實現了實時的增量分類。

[1]羅四維，溫津偉.神經場整體性和增殖性研究與分析[J].計算機研究與發展，2003，40(5)：668-674.

[2]周志華，陳世福.神經網絡集成[J].計算機學報，2002，25(1)：1-8.

[3]王玨，石純一.機器學習研究[J].廣西師范大學學報，2003，21(2)：1-15.

[4]LU B L，ITO M.Task decomposition and module combination based on class relations:a modular neural networks for pattern classification[J].IEEE Trans.Neural Networks，1999，10(5)：1244-1256.

[5]HUANG Y S，SUEN C Y.A method of combining multiple experts for the recognition of unconstrained handwritten numerals[J].IEEE Trans.Pattern Analysis and Machine Intelligence,1995,17(1):90-94.

[6]WOODS K,KEGELMEYER W P，BOWYER K.Combination of multiple classifiers using local accuracy estimates[J].IEEE Trans.Pattern Analysis and Machine Intelligence,1997,19(4)：405-410.

[7]POLIKAR R，UDPA L，UDPA S S，et al.Learn++:an incremental learning algorithm for supervised neural networks[J].IEEE Trans.System,Man,and Cybernetic,2001,31(4)：497-508.

[8]LU B L，ICHIKAWA M.Emergent online learning in minmax modular neural networks[J].In:Proc.of Inter’l Conference on Neural Network(IJCNN’01),Washington,DC,USA,2001：2650-2655.

[9]文益民，楊旸，呂寶糧.集成學習算法在增量學習中的應用研究[J].計算機研究與發展,2005,42(增刊):222-227.

[10]COPPOCK H W，FREUND J E.All-or-none versus incremental learning of errorless shock escapes by the rat[J].Science,1962,135(3500)：318-319.

[11]Hadoop.[EB/OL].2008-12-16.http://hadoop.apache.org/core/.

[12]DEAN J，GHEMAWAT S.MapReduce:simplified data processingon large clusters[J].Communications of the ACM,2008,51(1):107-113.

[13]PLATT J C.Fast training of support vector machines using sequential minimal optimization[D].SCHOLKOPF B,BURGES C J C,SMOLA A J,editors.Advances in kernel methods-support vector learning.Cambridge,MA,MIT Press，1998.

[14]鄧乃揚，田英杰.數據挖掘中的新方法:支持向量機[D].北京：科學出版社,2004.