王 燕，曹建芳,，李艷飛

(1.忻州師范學院 計算機系，山西 忻州 034000；2.太原科技大學 計算機科學與技術學院，山西 太原 030024)

0 引 言

隨著圖像獲取設備的普及和計算機網(wǎng)絡技術、多媒體技術的快速發(fā)展，各類圖像數(shù)據(jù)正在迅速增長[1]。作為最為常見的一類圖像數(shù)據(jù)，場景圖像的數(shù)量更是呈現(xiàn)指數(shù)級增長趨勢。人工智能和機器學習的創(chuàng)新發(fā)展使得利用計算機自動提取場景圖像特征并對其分類成為人工智能和計算機視覺領域的重要研究課題之一[2]。在機器學習領域，常見的分類算法有K最近鄰(KNN)[3]、貝葉斯(Bayes)[4]、神經(jīng)網(wǎng)絡[5]、決策樹[6]和支持向量機[7]。然而，上述算法都在不同層面存在一定的缺陷。KNN算法本身的時間復雜度和空間復雜度都很高；Bayes分類算法需要計算事件的先驗概率，而且對輸入數(shù)據(jù)的表達形式非常敏感；神經(jīng)網(wǎng)絡算法收斂速度慢并且易陷入局部最優(yōu)；決策樹對信息缺失的處理較為困難，易有過擬合的現(xiàn)象發(fā)生；而SVM因其廣義屬性，能夠提供較高的分類精度，是一種應用廣泛的分類算法[8]。但隨著研究的不斷深入，研究者們發(fā)現(xiàn)，由于受存儲能力和計算能力的約束，傳統(tǒng)的單節(jié)點架構的SVM算法在處理海量數(shù)據(jù)時，在內(nèi)存需求和計算時間方面會產(chǎn)生“瓶頸”，分析處理效率會急劇下降。

2004年，Google公司推出了一個處理海量數(shù)據(jù)的并行編程模型MapReduce[9]，因其具有良好的接口和運行支持庫，并隱藏了實現(xiàn)的復雜細節(jié)，支持并行執(zhí)行大規(guī)模的計算任務，從而在眾多領域得到了廣泛應用。在醫(yī)療領域，高漢松等[10]設計了一個對海量醫(yī)療數(shù)據(jù)進行挖掘和分析的醫(yī)療大數(shù)據(jù)挖掘平臺；在生物領域，涂金金等[11]在Hadoop平臺下應用MapReduce模型分析基因的表達數(shù)據(jù)；在通信領域，中國移動為了解決大流量數(shù)據(jù)業(yè)務快速、廉價處理的問題，提出了“大云”數(shù)據(jù)挖掘系統(tǒng)的構想[12]。MapReduce并行編程模型在各個領域的應用愈來愈多。

因此，針對上述單機平臺下SVM算法在處理大規(guī)模數(shù)據(jù)時面臨的“瓶頸”，為進一步提高分類準確率，基于混合優(yōu)化組合的思想，文中提出一種新的集群環(huán)境下的場景圖像分類方法：P-Adaboost-(ABC-PSO-SVM)模型。該模型首先應用人工蜂群(ABC)和粒子群(PSO)算法對SVM的參數(shù)進行混合優(yōu)化，以得到最優(yōu)的SVM參數(shù)對；然后使用Adaboost算法加強多個SVM分類器的結果，進一步提高分類準確率；最后利用MapReduce并行編程模型對算法進行并行化設計，以更好地改進該算法在處理海量數(shù)據(jù)時的時間性能。通過在場景圖像庫SUN Database上進行實驗，并與傳統(tǒng)單節(jié)點架構的SVM分類模型和集群環(huán)境下的并行SVM分類模型進行對比，驗證了P-Adaboost-(ABC-PSO-SVM)模型對海量場景圖像的分類效果。

1 P-Adaboost-(ABC-PSO-SVM)分類算法

1.1 ABC-PSO混合優(yōu)化SVM參數(shù)

1.1.1 SVM參數(shù)優(yōu)化分析

SVM算法以結構風險最小化原則為基礎，使用核函數(shù)將低維的線性不可分問題映射到高維空間，轉(zhuǎn)換成線性可分問題進行處理。核函數(shù)的構造對SVM算法的性能起著關鍵性作用[13]。局部核函數(shù)和全局核函數(shù)這兩類核函數(shù)是SVM最常使用的核函數(shù)，局部核函數(shù)的優(yōu)點是學習能力強，但存在的問題是泛化能力弱；全局核函數(shù)雖然泛化能力強，但學習能力卻很弱。為了兼顧兩者的學習能力和泛化能力，研究者們提出了將局部核函數(shù)和全局核函數(shù)相結合構造混合核函數(shù)的思想，最常見的是將徑向基函數(shù)(RBF)和多項式核函數(shù)進行線性組合，構造出滿足Mercer條件的混合核函數(shù)。

Kmix=λKpoly+(1+λ)Krbf

(1)

其中，λ∈(0,1)；Kploy=[(x·xi)+1]q為多項式核函數(shù)；Krbf=-γ‖x-xi‖2為RBF核函數(shù)。

SVM分類性能的優(yōu)劣與SVM參數(shù)有很大關系，因此有必要對SVM的參數(shù)做優(yōu)化調(diào)整。文中需要優(yōu)化的參數(shù)是：懲罰因子C、核參數(shù)γ和調(diào)節(jié)因子λ。懲罰因子C用于決定SVM重視離群點帶來損失的程度，核參數(shù)γ決定支持向量之間存在的關聯(lián)程度，調(diào)節(jié)因子λ的經(jīng)驗值尋優(yōu)范圍一般取值在0.50～0.99之間。

1.1.2 ABC-PSO-SVM算法

PSO算法[14]是一種群體智能進化算法，其思想源于鳥群覓食行為，優(yōu)點是實現(xiàn)容易、精度高、收斂快，但存在局部尋優(yōu)能力差、易產(chǎn)生早熟收斂等問題。ABC算法[15]是一種全局群智能優(yōu)化算法，其思想源于蜂群采蜜行為，應用的主要優(yōu)勢體現(xiàn)在不需要了解實際問題的特殊信息，只需要對問題進行優(yōu)劣的比較，通過各人工蜂個體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來，收斂速度較快。如果能充分利用PSO算法和ABC算法的優(yōu)勢，將兩者結合起來進行混合優(yōu)化，就會很好地克服PSO算法的缺陷，增強優(yōu)化算法的魯棒性。基于此，文中采用ABC-PSO算法對SVM的參數(shù)實行混合優(yōu)化，以形成最優(yōu)的SVM分類模型。優(yōu)化算法步驟為：

Step1：初始化PSO和ABC算法的參數(shù)。主要包括：種群規(guī)模、最大迭代次數(shù)、PSO算法的速度、ABC算法的食物源數(shù)量和控制參數(shù)、ABC和PSO算法的初始(C,γ,λ)。

Step2：將(C,γ,λ)作為SVM的參數(shù)，對SVM進行訓練和測試。

Step3：計算和更新適應度值。如果滿足最大迭代次數(shù)，即可得到SVM的最優(yōu)參數(shù)(C,γ,λ)，算法停止；否則，執(zhí)行Step4。

Step4：返回Step2執(zhí)行，繼續(xù)迭代尋優(yōu)。

1.2 Adaboost算法組合參數(shù)優(yōu)化的SVM

Adaboost算法是對同一問題集成多個弱分類器的結果共同決策的一種機器學習技術，通過執(zhí)行基本的分類算法，獲得多個不同的弱分類器，訓練過程中自適應改變樣本權重，錯分的樣本被賦予較大的權重，反復迭代，最后使用加權投票的方法獲得最終的判決結果[16]。文中使用Adaboost算法對ABC-PSO算法優(yōu)化后的SVM分類器進行加強，提出Adaboost-(ABC-PSO-SVM)算法，將ABC-PSO-SVM分類器作為弱分類器提供給Adaboost集成學習，在訓練過程中不斷改變輸入樣本的權重以重構少數(shù)類別樣本，加強對錯分樣本的訓練，最終構建強分類器。算法步驟為：

Step1：數(shù)值初始化。輸入訓練樣本集D={(x1,y1),(x2,y2),…,(xm,ym)}和訓練迭代次數(shù)T，優(yōu)化的SVM參數(shù)(C,γ,λ)，并將訓練樣本集權值分布Dt(i)設置為1/N。

Step2：訓練弱分類器ABC-PSO-SVM。

Step2.1：根據(jù)權值分布D1(i)得到第t次弱分類器Ht=L(D,Dt)。

Step2.2：計算Ht的錯誤率εt。

(2)

Step2.3：根據(jù)εt的值判斷是否更新樣本權重。

如果0<εt≤0.5，先根據(jù)式3計算權重值αt，然后根據(jù)式4更新樣本權重，繼續(xù)執(zhí)行Step2.1；否則執(zhí)行Step3。

(3)

(4)

Step3：線性組合T輪訓練后得到的T組弱分類器為Ht(x)，得到強分類器H(x)。

(5)

1.3 Adaboost-(ABC-PSO-SVM)算法的并行化設計

1.3.1 MapReduce并行編程模型

Hadoop是一個用于分布式處理海量各類型數(shù)據(jù)的軟件框架，其中HDFS和MapReduce是Hadoop平臺的兩個核心設計。HDFS是采用主/從模式體系結構的分布式文件系統(tǒng)，將大量數(shù)據(jù)分布存儲于多臺相關聯(lián)的計算機上，以實現(xiàn)對大規(guī)模數(shù)據(jù)集的流式訪問；MapReduce是一種并行編程模型，能夠?qū)⒂嬎闳蝿蘸蛿?shù)據(jù)分配到Hadoop集群的各個節(jié)點上，讓各節(jié)點并行執(zhí)行任務，得到中間結果后進行匯總并再次向各節(jié)點分配計算，以獲得最終結果。MapReduce在執(zhí)行任務的過程中，借助函數(shù)式編程方法，將計算分為Map和Reduce兩個任務，每個任務的處理均以鍵值對的形式進行輸入和輸出，通過定義Mapper()和Reducer()函數(shù)實現(xiàn)一個鍵值對到另一個鍵值對的映射[17-18]。Mapper()函數(shù)將大數(shù)據(jù)集分割成小數(shù)據(jù)集分配給各節(jié)點進行并行處理，Reducer()函數(shù)匯總各節(jié)點的處理結果，實現(xiàn)了分布式并行處理。

1.3.2 P-Adaboost-(ABC-PSO-SVM)算法

文中利用MapReduce并行編程模型在Hadoop集群環(huán)境中對提出的Adaboost-(ABC-PSO-SVM)算法進行并行化設計，即P-Adaboost-(ABC-PSO-SVM)算法，以解決單機平臺下的Adaboost-(ABC-PSO-SVM)算法在處理大規(guī)模場景圖像時硬件開銷大、運行耗時長，尤其是訓練時間急劇增加的問題。算法主要包括對Adaboost-(ABC-PSO-SVM)算法并行化的Map和Reduce兩個階段，另外，考慮到如果在Reduce階段直接對Map階段產(chǎn)生的中間結果進行匯總，集群環(huán)境各節(jié)點之間會產(chǎn)生很大的通信開銷。因此，文中在Reduce階段之前設計了一個Combine()函數(shù)，對Map階段產(chǎn)生的結果在一定程度上進行了本地處理，以減小節(jié)點之間的通信開銷。算法偽代碼描述如下：

Adaboost-(ABC-PSO-SVM)-Mapper()

Input：<弱分類器ID，樣本特征值>

Output：<弱分類器ID，預測誤差εt>

{

//對每個弱分類器

ABC-PSO優(yōu)化SVM參數(shù)(C,γ,λ)；

訓練弱分類器：

{

計算預測誤差εt；

if(0<εt≤0.5)

更新樣本權重αt；

}

獲取弱分類器預測函數(shù)Ht(x)和更新的εt；

輸出<弱分類器ID，預測誤差εt>；

}

Adaboost-(ABC-PSO-SVM)-Combine()

Input：<弱分類器ID，預測誤差εt>

Output：<弱分類器ID，弱分類器Ht(x)>

{

count←0；//統(tǒng)計訓練弱分類器數(shù)

//對每個弱分類器

解析處理εt坐標值；

count←count+1；

在本地歸約處理ID相同的鍵值對，更新εt，獲得弱分類器Ht(x)的輸出；

輸出<弱分類器ID，弱分類器Ht(x)>；

}；

Adaboost-(ABC-PSO-SVM)-Reducer( )

Input：<弱分類器ID，弱分類器Ht(x)>

Output：<預測誤差εt，強分類器H(x)>

{

對各節(jié)點ID相同的鍵值對再次進行合并處理；

對弱分類器Ht(x)進行線性組合，更新εt，得到強分類器H(x)；

輸出<預測誤差εt，強分類器H(x)>；

}

2 大規(guī)模場景圖像分類實現(xiàn)

2.1 特征提取

尺度不變特征變化(scale-invariant feature transform，SIFT)是David G.提出的基于尺度空間的特征描述算子，是一種通過檢測多尺度圖像金字塔極值點提取圖像的位置、尺度、旋轉(zhuǎn)等關鍵點的計算方法[19]。由于SIFT特征不受圖像大小、旋轉(zhuǎn)、光線等變換的影響，區(qū)分力強，具有很好的魯棒性，現(xiàn)已成為應用廣泛的圖像特征提取算法。文中選取場景圖像的SIFT特征作為分類器的輸入特征參數(shù)，在Hadoop平臺下對SIFT特征的提取進行并行化設計，算法步驟為：

Step1：將不同類別的場景圖像設置為Map任務的輸入，其中key為圖像名稱，value為場景圖像。

Step2：Map階段，利用OpenCV函數(shù)庫中的Dense SIFT算法提取場景圖像的SIFT特征，輸出形如<圖像名稱，128維特征向量>的鍵值對，建立多個文件夾，每個文件夾保存一幅場景圖像的SIFT特征向量。

由于SIFT特征提取過程較為簡單，考慮到節(jié)約時間和通信開銷，在并行提取場景圖像SIFT特征時未設置Reduce任務。

2.2 分類模型構建及實現(xiàn)

文中設計的海量場景圖像分類模型框架如圖1所示。

圖1 海量場景圖像分類模型框架

分類模型基于Hadoop大數(shù)據(jù)平臺架構，在提取場景圖像的SIFT特征后，將其作為分類器的輸入?yún)?shù)，然后使用提出的Adaboost-(ABC-PSO-SVM)算法建模，并利用MapReduce并行編程模型對SIFT特征提取和Adaboost-(ABC-PSO-SVM)算法進行并行化設計，對大規(guī)模場景圖像進行類別預測，將得到的分類結果反饋給用戶。具體步驟為：

Step1：并行提取場景圖像的SIFT特征，生成特征矩陣。

Step2：確定Adaboost-(ABC-PSO-SVM)分類器的結構。

Step3：搭建Hadoop集群，并行訓練Adaboost-(ABC-PSO-SVM)分類器，不斷更新樣本權重，組合輸出結果。

Step4：使用訓練好的分類器，對大規(guī)模場景圖像進行分類識別，并將結果反饋給用戶。

3 實驗結果及分析

3.1 實驗環(huán)境和數(shù)據(jù)來源

實驗環(huán)境：采用局域網(wǎng)內(nèi)5臺計算機搭建了Hadoop集群環(huán)境，其中1臺作為主(master)節(jié)點，其余4臺作為從(slave)節(jié)點。所有節(jié)點計算機硬件配置都采用酷睿i7四核八線程4.2 G處理器，8 G內(nèi)存，4 T硬盤空間的基本配置；軟件配置：操作系統(tǒng)是64位的Ubuntu 14.04，Java環(huán)境為jdk1.7.0_79，Hadoop為Hadoop-2.5.1(64位編譯)。

數(shù)據(jù)來源：實驗數(shù)據(jù)來源于SUN Database場景圖像庫，包含131 067幅、908個類別的場景圖像。該圖像庫是供研究者們免費使用的，其規(guī)模不斷擴大。為便于處理，文中實驗用的圖像都被預處理成200×200像素的大小。

3.2 實驗對比分析

為驗證該算法的有效性，在SUN Database圖像庫中隨機選取50 000張場景圖像，構造了不同規(guī)模的數(shù)據(jù)集，從最優(yōu)參數(shù)組合及進化迭代次數(shù)、分類準確率和分類器訓練耗時等幾個方面進行了實驗對比分析。

3.2.1 SVM參數(shù)優(yōu)化對比

ABC算法和PSO算法同時對SVM參數(shù)進行混合優(yōu)化，不需要遍歷所有的參數(shù)點就能很快找到全局最優(yōu)解。在SUN Database圖像庫中隨機選取了10個類別，共5 000張場景圖像，對ABC-PSO算法參數(shù)優(yōu)化與PSO算法參數(shù)尋優(yōu)及進化代數(shù)做了對比，如表1所示。

表1的數(shù)據(jù)表明，數(shù)據(jù)類別不同，數(shù)據(jù)的復雜性也不同，兩種算法在不同數(shù)據(jù)類別下的進化速度會有快有慢，得到的參數(shù)組合也不一樣。但無論針對哪種數(shù)據(jù)類別，ABC-PSO-SVM算法的進化速度都比PSO-SVM算法的進化速度快得多，而且ABC-PSO-SVM算法能找到優(yōu)于PSO-SVM算法的參數(shù)組合，充分說明了ABC算法和PSO算法進行混合優(yōu)化的優(yōu)越性。

表1 最優(yōu)參數(shù)組合及進化代數(shù)對比

3.2.2 分類準確率比較

為驗證文中算法的分類性能，使用3.2.1中的10個數(shù)據(jù)類別，采用復制的方法構造了包含10 000張場景圖像的數(shù)據(jù)集，將其中30%的圖像作為測試數(shù)據(jù)集，對不同數(shù)據(jù)類別的測試準確率如圖2所示。

圖2 不同類別圖像測試準確率對比

圖中A—Airport terminal，B—Beach，C—Bedroom，D—Conference room，E—Forest path，F(xiàn)—Highway，G—Kitchen，H—Mountain snowy，I—Playground，J—Vegetable garden。

從圖2可以看出，文中算法的分類準確率明顯高于其他單機平臺上的SVM、PSO-SVM和ABC-PSO-SVM算法。這主要是因為：一方面是基于組合優(yōu)化的思想使用Adaboost算法對混合優(yōu)化參數(shù)后的SVM分類器進行了加強，構建強分類器提高了分類精度；另一方面采用MapReduce并行編程模型對算法進行了并行化設計，增強了計算能力，訓練的分類模型更優(yōu)，進一步提高了分類準確率。

另外，為進一步驗證文中算法的有效性，又構造了不同規(guī)模的數(shù)據(jù)集，使用不同的算法做了分類對比實驗(訓練樣本:測試樣本=7∶3)，如表2所示。

表2 不同數(shù)據(jù)規(guī)模下的分類性能對比

從表2中的數(shù)據(jù)可以看到，在不同規(guī)模的數(shù)據(jù)集下，P-Adaboost-(ABC-PSO-SVM)算法的訓練準確率和測試準確率都要高于其他3種單機平臺架構下的算法；而且，隨著場景圖像數(shù)據(jù)規(guī)模的不斷增大，雖然各種算法的分類準確率都在下降，但文中算法的下降趨勢較為平緩，而其他3種算法的下降趨勢很明顯，尤其是當場景圖像規(guī)模超過10 000時；另外，對于不同的數(shù)據(jù)規(guī)模，文中算法的測試準確率和訓練準確率非常接近。這都充分說明了MapReduce并行編程模型和Hadoop平臺分布式處理的計算能力的強大，在這種集群環(huán)境下訓練得到了最優(yōu)的SVM分類模型，使得分類精度不會隨著數(shù)據(jù)集的增大而急劇下降，同時測試準確率接近于訓練準確率。

3.2.3 訓練耗時對比

為驗證文中算法在處理大規(guī)模數(shù)據(jù)集時的時間性能，對不同分類器的訓練時間進行了實驗比較，如表3所示。

表3 不同算法在不同規(guī)模數(shù)據(jù)集下的訓練時間對比

表3的數(shù)據(jù)明顯表明，集群環(huán)境下設計的并行算法訓練時間要比單機平臺下的算法訓練時間少得多；而且，隨著圖像規(guī)模的不斷增大，單機平臺下的算法訓練時間會急劇增加，而文中算法基于集群環(huán)境設計，能夠進行分布式并行處理，因此訓練時間不會增加太多，實現(xiàn)了短時間內(nèi)對海量數(shù)據(jù)的處理。

4 結束語

對集群環(huán)境下融合混合優(yōu)化和組合思想的大規(guī)模場景圖像分類算法做了深入探討。對使用ABC算法和PSO算法混合優(yōu)化SVM的參數(shù)進行了研究，將Adaboost算法組合SVM的分類結果構建強分類器，并利用Hadoop平臺下的MapReduce并行編程模型對提出的算法進行了并行化設計，將其應用于大規(guī)模場景圖像的分類問題。在SUN Database場景圖像庫上的對比實驗結果表明，該算法能快速優(yōu)化SVM的參數(shù)，分類準確率高，訓練耗時少，構建的Hadoop集群環(huán)境能充分利用各節(jié)點計算機的資源，發(fā)揮其計算能力，提高分類器的訓練和預測的速度和精度，獲得最優(yōu)的分類模型。相對于單機平臺下的傳統(tǒng)算法，系統(tǒng)性能良好，很好地體現(xiàn)了分布式并行處理集群環(huán)境的強大運算能力，拓寬了大數(shù)據(jù)技術在數(shù)字圖像理解領域的應用。