Hadoop 下多模式并行分類算法及其應用研究

李玉丹,鄭曉薇

(遼寧師范大學計算機與信息技術學院,遼寧 大連 116081)

1 概述

BP 神經網絡(Back Propagation Neural Network,BPNN)具有高度的非線性映射能力,通過構建合適的網絡,可以以任意精度逼近任何非線性映射函數,因而在眾多領域得到廣泛應用,如文獻[1]使用BP 神經網絡來識別復雜背景下的各種手勢；文獻[2]利用BP 神經網絡對醫學圖像進行分類；文獻[3-4]分別將BP 神經網絡應用于泥石流和電力價格的預測系統中。傳統的BP 神經網絡訓練方法,是將搜集到的全部資料樣本作為一個整體訓練集,在單機上串行處理。然而,在圖像檢索等應用領域中,此方法針對大規模雜亂無序的圖像樣本的多語義分類問題,往往表現出2 個方面的不足：(1)由于不同語義模式的樣本特征值存在明顯的差異性,這些特征值作為BP 神經網絡的輸入數據會使輸入層的輸入值發生較大跳躍,使BP 網絡很難學習到樣本數據的內在特征和規律,導致網絡迭代時間長、訓練精度低；(2)隨著樣本規模的不斷增大,算法的串行訓練方式內存開銷成為瓶頸問題,通信耗時增長、系統效率低。

為解決上述問題,本文提出一種SOM-MBP(Selforganizing Mapping Multi-back Propagation Neural Network)多模式并行分類算法。該算法將自組織映射(Self-organizing Mapping,SOM)網絡和多個并行BP 網絡相結合,由自組織網絡對全部樣本進行初期自動聚類,再用不同的BP 網絡訓練不同的聚類樣本集,改善了數據多樣性的樣本訓練對BP 性能的影響。基于云計算平臺Hadoop 中MapReduce 編程模型設計了多作業并行處理機制,實現SOM-MBP 神經網絡自身及多個BP 神經網絡間的并行處理,并縮短了訓練時間。

2 SOM-MBP 多模式并行分類算法

2.1 自組織映射網絡

自組織映射網絡是一種無監督神經網絡,它模擬了生物神經網絡中神經元之間的興奮、抑制與競爭機制,即一個神經元興奮后,通過它的分支會對周圍其他神經元產生抑制,實現優勝劣汰的選擇過程[5],其結構如圖1 所示,由輸入層和競爭層兩部分組成。假如輸入層有n個神經元,競爭層有m個神經元,每個樣本對應于輸入層第i個神經元的輸入值表示為Xi,競爭層第j個神經元的輸出值表示為Yj；輸入層與競爭層之間的連接權值表示為Wij,依據式(1)所示的學習規則,求得該輸入樣本的輸出值Yj,規定Yj中最大值所在的神經元為獲勝神經元。

圖1 SOM 網絡結構

SOM 網絡只能實現單種模式的歸類判別,當樣本數據由輸入層進入SOM 網絡模型,通過一定的學習規則,競爭層僅有一個神經元為獲勝者,將僅與獲勝神經元相聯系的各連接權值朝著有利于競爭的方向調整,其他權值保持不變。獲勝神經元代表已定義的樣本數據模式中的一種,使用式(2)調整網絡權值。SOM 網絡不是以一個神經元的狀態矢量反映分類結果,而是以若干神經元同時反映分類結果,因此其存在需要高度訓練的缺點。

其中,η∈(0,1]為學習率為權值Wij所對應的權值增量；t為迭代次數。

2.2 MBP 并行神經網絡

BP 網絡與SOM 網絡不同,它需要期望信號,是一種有監督的神經網絡。其結構與SOM 類似,不同的是在輸入層和輸出層中間存在一或多個隱藏層[6]。BP 神經網絡的主要思想是：首先輸入樣本數據,根據給定的學習規則從輸入層至輸出層,正向計算網絡的實際輸出,學習規則如式(3)所示。神經網絡中各神經元的激發函數表示為f(x),第k層第j個神經元的實際輸出值表示為然后將實際輸出與期望信號進行比較,得到的誤差從輸出層至輸入層反向傳播,對網絡權值沿著使誤差縮小的方向進行修改,權值調整見式(4)：

其中,η為學習率,一般介于0～1 之間；t為迭代次數。

BP 神經網絡學習的目的是修改網絡的權值,當學習結束時,該權值反映了同種模式輸入樣本的共同特征；對預測的樣本數據,通過學習規則實現一種或多種模式分類。在實際應用中,要達到較好的分類效果,BP 神經網絡需要進行大量的樣本訓練,這就需要預先獲取有代表性的訓練樣本集。此外,由于網絡的所有輸出神經元的誤差均影響各層之間的權值調整量,在多模式分類的情況下,不同的輸出誤差將產生不同的權值調整方向,會對調整效果產生不利影響。

本文設計的MBP 并行神經網絡,采用多個BP網絡并行集成方法,可有效地避免權值的調整效果被相互抵消的問題。在本系統中,每個并行的BP 神經網絡各自訓練一種語義模式,這樣每個BP 網絡就可最大限度地逼近其所代表的語義模式函數,充分學習各語義模式間的細微差別,提高訓練精度。

2.3 SOM-MBP 多模式并行分類模型

SOM-MBP 多模式并行分類模型結構如圖2 所示。本文實驗選用圖像樣本做分類,首先對樣本進行特征值提取的預處理,得到能夠代表樣本的特征數據,然后利用SOM 網絡對樣本數據進行自組織聚類,將具有相似特征和規律的樣本劃分為N個樣本集。該N個樣本集作為BP 神經網絡的訓練樣本,這樣既為BP 神經網絡提供了有代表性的含有期望信號的樣本數據集,同時由于同一樣本集內的樣本數據具有相似性,克服了因輸入值跳躍造成的BP 神經網絡學習效果差的問題。依據SOM 樣本聚類集的個數,在N個單輸出的并行BP 神經網絡中,每個BP 網絡獨立訓練一個樣本集。在多語義類綜合判斷階段,匯總N個BP 網絡的結果,依據規定的閾值判斷所屬的多個模式,這樣就彌補了SOM 單模式歸類的不足,方便地實現多種語義模式的分類。

圖2 SOM-MBP 模型結構

3 MapReduce 并行的SOM-MBP 多模式分類

目前,云計算是處理大規模數據的主流平臺,Hadoop 是開源云計算平臺的典型代表,Hadoop 平臺下采用的并行化技術主要是MapReduce 模型[7],該模型根據分而治之的思想,將并行計算簡化為Map和Reduce 過程,同時隱藏很多繁瑣的細節[8],如自動并行化、負載均衡和災備管理等[9-10]。Map(映射)函數用來把一組鍵值對映射成一組新的鍵值對；Reduce(化簡)函數用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

在圖像分類檢索的應用中,由于人工神經網絡在樣本學習過程中,對每一個樣本均要遍歷迭代所有神經元,因此當圖像樣本個數較多、每個樣本的特征數據維數較大時,往往會出現內存開銷大、通信耗時長、分類效率低的現象。本文在Hadoop 平臺下將SOM-MBP 多模式并行分類模型通過MapReduce 編程模型予以并行化設計,采用Map 函數和Reduce 函數實現SOM-MBP 神經網絡內部的自動并行化,同時利用MapReduce 提供的多作業并行處理機制實現多個BP 神經網絡間的并行執行。此設計能大大縮短SOM-MBP 算法的樣本聚類和訓練時間,提高訓練的精度。

3.1 SOM 子模型的MapReduce 并行方法

自組織映射網絡算法由網絡權值修改量的精度控制迭代次數,在每次迭代過程中,需要對所有樣本數據判斷其獲勝神經元的位置,并修改與獲勝神經元連接的權值。在MapReduce 并行中針對每一次迭代,Map 階段判定獲勝神經元,計算其相應的權值修改量。Reduce 階段對相同的獲勝神經元,統計與其連接的每個權值的總體更新量,然后對權值更新。算法如下：

(1) Map 階段

1) 輸入鍵值對＜key,value ＞,其中,key 表示樣本序號；value 表示樣本的特征值集合；每個＜key,value ＞對代表一個樣本記錄。

2) 根據學習規則計算競爭層的輸出值。

3) 判定獲勝神經元,將其輸出狀態設為1,其他所有神經元狀態設為0。設定獲勝標志flag 為獲勝神經元在競爭層的位置。

4) 計算與獲勝神經元相連接的各權值更新量,其他權值保持不變。

5) 輸出鍵值對＜key,value ＞,其中,key 表示flag 獲勝標志；value 表示與獲勝神經元相連接的各權值更新量。

(2) Reduce 階段

1) 接收Map 階段的結果作為輸入鍵值對＜key,value ＞,其中,key 表示flag 獲勝標志；value表示list ＜與獲勝神經元相連接的各權值更新量＞,即具有相同獲勝標值的權值更新列表作為value 值。

2) 累計每個權值的總體更新量,求得平均更新量。

3) 調整相應的網絡權值。

4) 輸出鍵值對＜key,value ＞,其中,key 表示權值更新狀態；value 表示更新后的網絡權值。

5) 更新全局文件,使文件中對該網絡的權值為reduce 的輸出值。

重復以上MapReduce 過程,直到各權值的調整量趨近于規定的精度值。

3.2 MBP 子模型的MapReduce 多作業并行方法

本文中SOM-MBP 網絡模型的BP 神經網絡部分是將多個單輸出的BP 并列集成,在Hadoop 云計算平臺下,將每個BP 神經網絡加載為一個獨立的作業,由MapReduce 框架提供的submit()方法并行提交作業,實現多個BP 神經網絡作業的并行執行。同時,每個BP 神經網絡由Map 函數和Reduce 函數實現其自身內部的并行處理。Map 階段計算每個樣本數據其對應的所有權值變化量。Reduce 階段統計整個網絡中每個權值的總體更新量,然后對權值進行更新,寫入Hadoop 文件系統,供下一次迭代使用。

(1) MBP 子模型的Map 階段

首先將SOM 算法的聚類結果,即樣本的特征值集合+類別信號,作為BP 神經網絡輸入鍵值對＜key,value ＞的value 值,樣本序號作為key 值,輸入到網絡中。根據式(3)的學習規則向前逐層計算網絡的輸出值。與SOM 不同,在網絡輸出層無需判定獲勝神經元,而是將輸出層的實際輸出值與期望的類別信號比較,逐層計算學習誤差。然后根據學習誤差計算網絡中每個權值的更新量。將每個樣本所對應的所有權值更新量作為Map 輸出鍵值對＜key,value ＞的value 值,輸出給Reduce 階段使用。

(2) MBP 子模型的Reduce 階段

接收來自Map 階段的輸出結果,即每個樣本所對應的所有權值更新量。然后累計所有樣本相同權值的總體更新量,得到每個權值的總體平均更新量并更新網絡中的各權值。將更新后的網絡權值作為Reduce 階段的輸出寫入到HDFS 上指定的權值文件中,以供下一次迭代使用。

重復以上Map-Reduce 過程,直到誤差達到定義的精度或達到最大迭代次數。

4 實驗結果與分析

為驗證SOM-MBP 多模式并行分類算法在Hadoop 云計算平臺下對大量數據集的分類效率,對自然風景圖像進行了多種語義模式分類的測試實驗。

4.1 實驗環境及數據

硬件配置：Hadoop 集群平臺由55 個節點機構成,各節點機均為Intel(R) Core(TM) i3-3240 CPU @3.40 GHz,4.00 GB 內存,64 位操作系統。

軟件：Linux 操作系統Ubuntu13.04；編程環境為MapReduce 類庫和Eclipse 編譯器；程序設計語言為Java 語言。

實驗數據：實驗數據選自互聯網百度圖像庫。選取涵蓋日光、河海、高山、樹木、花朵5 種類別的自然圖像,圖像總數多達30 000 000 幅,圖像分辨率是300 ×210 像素。

模型結構：由于本文實驗是對自然風景圖像進行5 種語義模式的多語義分類,因此自組織映射網絡的競爭層神經元個數為5 個,相應地,構建5 個單輸出的BP 神經網絡。圖像樣本預處理階段,在OpenCV 環境下對每幅圖像樣本從顏色、紋理、形狀3 個方面進行底層特征的提取,其中,顏色特征64 維、紋理特征48 維、形狀特征7 維,即每幅圖像特征向量共計119 維,因此,對SOM 和每個單獨的BP神經網絡而言,依據所提取的圖像樣本底層特征數量,輸入層節點個數Ni取119,每個單獨的BP 神經網絡其輸出層節點個數No為1,隱藏層節點個數依據經驗公式,經過反復實驗取15 效果較好。

4.2 實驗結果

實驗結果具體如下：

(1) 文獻[11]采用單BP 多個輸出的網絡模型對自然圖像進行多種語義的分類,本文將該分類算法引用到本文實驗環境中并通過Java 予以實現,選取5 000 幅作為測試樣本,30 000 幅為訓練樣本,將其分類測試結果與本文提出的SOM-MBP多模式并行分類算法測試結果進行對比,如表1所示。

表1 不同分類算法測試結果對比 %

由表1 數據可計算出,文獻[11]單BP 多輸出分類算法的總體平均查全率為79.1%,平均準確率為81.0% ；SOM-MBP 多模式分類算法的總體平均查全率為88.2%,平均準確率為87.6% 。

(2) 單BP 多輸出神經網絡分類算法、SOM-MBP順序串行與MapReduce 并行的SOM-MBP 多模式分類算法,在圖像樣本總數從3 000 幅～30 000 000幅數據量下的運行時間對比如表2 所示。

表2 算法運行時間對比 s

(3) 為檢測并行優化的結果,對程序運行的并行加速比進行對比,加速比的定義如下[12]：

其中,Ts為單個處理器上求解問題所花的時間；Tp為p個相同處理器并行計算機求解同一問題所花時間；Tcomp為計算時間；Tcomm為通信時間。

Hadoop 下并行SOM-MBP 多模式分類算法的加速比隨節點個數、樣本數量變化趨勢如圖3 所示。

圖3 Hadoop 下并行SOM-MBP 多模式分類算法的加速比

4.3 結果分析

從表1 的實驗結果可知,由于SOM 階段將具有相似特征和規律的圖像劃分為一個樣本集,每個BP神經網絡訓練一個樣本集時能夠充分學習該類圖像間的細微特征差別,因而與文獻[11]提出的單BP多輸出分類算法相比,本文的SOM-MBP 多模式并行分類算法表現出了更高的查全率和準確率,表明了采用MapReduce 并行的SOM-MBP 多模式分類算法在自然圖像多模式分類中的高效性。

由表2、圖3 可見,MapReduce 并行的SOM-MBP多模式分類算法在樣本數為3 000 時,由于Hadoop 自身系統開銷等原因的影響,并行處理速度并不如串行SOM-MBP 算法,但當樣本個數達到30 000以上后,由于采用并行化及Hadoop 分布式文件存儲,降低了數據網絡傳輸的開銷和內存開銷,并行效率開始顯現,隨著數據量的增大并行處理速度逐漸提高、加速比逐漸增長；當樣本個數達到300 000后,加速比增長趨勢更明顯,這充分體現了該Hadoop 下并行SOM-MBP多模式分類算法在處理大規模數據時的優越性,說明了該算法是有效可行的。

5 結束語

在模式識別及樣本分類中,由于同種模式內的樣本特征值存在相似性,異種模式間的樣本特征值差異性較大,因此對復雜無序的樣本進行多種語義模式的分類時,BP 神經網絡通常很難學習到樣本數據的內在特征和規律,同時隨著數據規模的不斷擴大,在對大數據的存儲和處理過程中會產生內存溢出、數據解析時間長、磁盤與內存之間傳輸過大等問題,導致BP 網絡很難達到較好的分類效率。本文根據人工神經網絡自組織和高度并行的特點,提出一種云計算環境下MapReduce 并行的SOM-MBP 多模式分類算法,并在Hadoop 集群上進行了應用測試。實驗結果表明,該算法相比傳統單BP 多輸出算法訓練速度更快、分類精度更高,驗證了該算法的有效性和可行性,為神經網絡在多模式分類中的應用提供了借鑒。

[1]王先軍,白國振,楊勇明,等.復雜背景下BP 神經網絡的手勢識別方法[J].計算機應用與軟件,2013,30(3)：247-249,267.

[2]孫君頂,李 琳.基于BP 神經網絡的醫學圖像分類[J].計算機系統應用,2012,21(3)：160-162,212.

[3]Chang Tung-Chueng,Chao Ru-Jen.Application of Backpropagation Networks in Debris Flow Prediction[J].Engineering Geology,2006,85(3/4)：270-280.

[4]Meng K,Dong Z Y,Wong K P.Self-adaptive Radial Basis Function Neural Network for Short-term Electricity Price Forecasting[J].IET Generation,Transmission &Distribution,2009,3(4)：325-335.

[5]肖 婧,鄭更生,方 勇,等.基于自組織神經網絡的分簇成鏈協議[J].計算機工程,2013,39(7)：148-151.

[6]肖會敏,郭 鵬.基于主成分分析與BP 神經網絡的供應商選擇模型[J].計算技術與自動化,2013,32(1)：130-133.

[7]賈瑞玉,劉范范,潘雯雯,等.基于MapReduce 模型的并行量子進化算法[J].計算機工程,2012,38(8)：180-182,188.

[8]Jeffrey D,Sanjay G.MapReduce：Simplified Data Processing on Large Clusters[J].Communications of the ACM,2008,51(1)：107-113.

[9]李建江,崔 健,王 聃,等.MapReduce 并行編程模型研究綜述[J].電子學報,2011,39(11)：2635-2642.

[10]劉 義,景 寧,陳 犖,等.MapReduce 框架下基于R-樹的k-近鄰連接算法[J].軟件學報,2013,24(8)：1836-1851.

[11]謝文蘭,石躍祥,肖 平,等.應用BP 神經網絡對自然圖像分類[J].計算機工程與應用,2010,46(2)：163-166.

[12]陳國良.并行計算：結構,算法,編程[M].北京：高等教育出版社,1999.