改進隨機森林算法的圖像分類應用①

張志禹,吉元元,滿蔚仕

(西安理工大學 自動化與信息工程學院,西安 710048)

1 引言

隨著互聯網技術、多媒體應用和計算機視覺的不斷發展,對于海量場景圖像的分類處理成為不容小覷的問題.近年來,主要以詞袋模型(Bag of Word,BoW)、卷積神經網絡等圖像分類算法的有效分類性能吸引了更多的關注.圖像分類己成為管理應用圖像數據的關鍵技術,由于圖像的多樣性和復雜性以及類內的差異性,如何更加準確全面地表示圖像是一個問題.早期的圖像分類是通過提取圖像的底層特征,如顏色、紋理等特征.但是,這些算法對應的是全局信息從而確定目標的整體結構不能變,且會因為圖像缺失或者光線或遮擋問題而受到影響,這樣在處理復雜圖像時效果并不理想.Avila[1]在圖像分類中用到了詞袋模型,并且引入了基于密度函數的池策略.這種方法能夠更好地代表詞典的碼字并描述圖像.將該方法用在視頻和圖像分類上,都有不錯的分類效果.Li等人[2]將視覺詞匯與空間金字塔匹配模型結合,提出了一種仿射傳播聚類算法用于高分辨率遙感圖像分類,實驗結果表明該算法分類性能優于傳統聚類算法.

隨機森林算法在處理非平衡數據集、連續變量與決策樹節點分裂算法[3]問題等方面提出和發展了許多新方法.對場景圖像進行特征提取后的后續分類,本文擬采用隨機森林(Random Forest,RF)算法做進一步的研究.文獻[4]中提出一種新的特征加權方法和決策樹選擇方法(Improved Random Forest,IMRF),結合協同服務,使隨機森林算法適用于多類大量圖像數據的分類.利用該方法,在不增加誤差界的前提下,有效地減少子空間的大小,提高分類性能.Archana Chaudhary 等人[5]由隨機森林機器學習算法、屬性評估方法和實例過濾方法組成一種新的隨機森林分類器方法,并用于多類別花生病害分類問題,并極大提高分類精度.但是,這些方法在海量數據的分類效率與分布式計算問題上還存在一定的制約,同時分類精度也有待進一步提高,難以適應信息量的爆炸式增長,因此相關問題上還有待進一步學習研究.

Apache Spark集群計算平臺[6,7](如圖1)是一個基于內存計算的開源運算系統,在運算速度上可以滿足人們的需要;Spark啟用了內存分布數據集[8],除了能夠提供交互式查詢外,它還可以優化迭代工作負載,具有很好的容錯機制[9],該機制可以維護 “血統”,可以記錄特定數據轉換操作行為的過程.同時Spark可以很好的兼容Hadoop生態系統,這使得其應用發展都有了很好的基礎.因此本文中,有關于場景圖像分類的若干步驟將在該平臺下進行,有利于對大數據量問題的研究與分布式計算的實現.

圖1 Spark 生態系統

在本文中實現圖像分類的步驟如下:

Step1.利用SURF特征進行圖像特征采樣[10],再利用局部特征描述子形成對這些向量的表達;

Step2.對圖像的特征向量進行聚類得到視覺單詞[11],計算每幅圖片到這些視覺單詞的距離,并將其映射到距離最近的視覺單詞,完成每幅圖像的詞頻表達[12];

Step3.利用改進的自適應節點分裂隨機森林算法(Self-Adaptive Node Split Random Forest,SANS-RF)進行圖像分類并利用包外圖像進行驗證,改進算法及涉及到的理論會在后續段落重點介紹.

2 空間金字塔模型

2.1 詞袋模型

在場景圖像分類的眾多算法中,BoW模型的最大優點是將圖像表示為視覺詞匯,更容易識別并表示出圖像中感興趣的部分[13],即將圖像看作一個“文檔”,關鍵詞就是提取圖像的SURF特征,稱為“視覺詞典”[12].

為了在特征點檢測與匹配實現尺度不變性,SURF算法首先用Hessian矩陣確定候選點,然后進行非極大抑制,會使計算復雜度降低許多.Hessian矩陣是SURF算法的核心,即根據圖像中每一個像素點的Hessian矩陣,如式(1),得到 Hessian 判別式,如式(2),其值即是Hessian矩陣的特征值,可以用該式的結果對像素點進行分類:

在SURF算法中,通常利用圖像像素I(x,y)代替原始的f(x,y),通過特定核間的卷積計算二階偏導數,可以得到Hessian矩陣的三個元素Lxx,Lyy,Lxy,因此Hessian矩陣如下所示:

同時選用二階標準高斯函數作為濾波器,即在Hessian矩陣構造前,需對其進行高斯濾波:

其中L(x,t)代表一幅圖像在不同解析度下的表示,G(t)代表高斯核,公式如下:

以上計算可以判別特征點,為此 Herbert Bay[14]提出用近似值代替L(x,t),為減小準確值與近似值之間的誤差引入權值,權值隨尺度變化,則Hessian矩陣的判別式表示為:

具體公式推導可詳見文獻[14].

通過以上方法可以生成尺度空間,再通過精確定位特征點,選取特征點主方向確定的步驟,就可以構造SURF特征點描述算子,進行圖像特征提取.

2.2 空間金字塔結構

利用上一小節提到的詞袋模型表示圖像可以得到一個不錯的分類效果,但是該模型沒有考慮圖像的空間位置信息,得到的是圖像的一個無序集合.因此在這一步驟中引入了空間金字塔模型,以達到充分利用圖像空間信息的要求.

該模型首先對局部特征量化,然后在每個金字塔水平把圖像劃分為細網格序列[15],從每個金字塔水平的網格中提取特征,同時給每層網格分配一個權重,按權重把每層網格特征加權串聯在一起,如圖2所示.

圖2 空間金字塔模型示意圖

所以一幅圖像的最終加權空間金字塔表現方法為:

以上公式可以將需要分類的圖像更好表示.

3 隨機森林算法

3.1 算法簡介

隨機森林是一種組合分類器,它利用Boostrap重抽樣方法從原始樣本中抽取多個樣本[16]構造子數據集,利用子數據集形成基決策樹并對其進行訓練,RF在決策樹的訓練中引入了隨機屬性選擇,即對基決策樹的每個節點,先從該節點的屬性集合中隨機選擇一個包含k個屬性的子集,然后再從這些子集中選擇一個最優屬性用于節點分裂,這樣可以使每棵決策樹彼此不同,提升系統的多樣性,然后將這些決策樹組合在一起,利用Boostrap中未抽取到的樣本作為包外數據集進行驗證,并通過投票法得到分類結果,從而提升分類性能,算法流程圖如圖3所示.

圖3 隨機森林算法

節點分裂是RF算法的核心步驟,通過節點分裂才能產生一顆完整的決策樹[17].每棵樹分支的生成,都是按照某種分裂規則選擇屬性,這些規則主要包括信息增益最大、信息增益率最大和Gini指數最小等原則,然后選擇某個屬性作為分裂屬性,并按照其劃分實現決策樹分支生長.隨著劃分過程的進行,節點的純度越來越高,即該節點所包含的樣本盡可能的屬于同一類別.

3.2 改進隨機森林算法

大量研究都證明了隨機森林算法具有較高的分類準確率,對異常值和噪聲有很好的容忍度,而且不易出現過擬合.本文提出的SANS-RF算法,通過參數的自適應選擇過程,來優化算法中決策樹的節點分裂算法,達到提高算法分類精度的目的.

對同一個數據集,選擇不同的節點分裂算法,也會因選擇的屬性不相同而得到不同的決策樹,得出隨機森林的分類精度會有差異.因此提出在生成決策樹時,選擇最優的屬性進行節點分裂,即將節點分裂算法進行線性組合,形成新的分裂規則,應用于節點屬性的選擇劃分.由于Spark mllib的隨機森林算法中集成的節點分裂算法只有ID3和CART,因此節點分裂優化的考慮暫定這兩種算法上,其節點分裂公式表示用屬性對 樣本集進行劃分所獲得的信息增益與基尼指數分別如下:

其中Dv表示第v個分支節點包含的D中所有在屬性a上取值為av的樣本:

式(12)和式(13)分別表示數據集D的信息熵與基尼值.

表1 節點分裂算法對比

結合表1內容,節點分裂準則應以劃分后數據集純度更高為目標,因此組合節點分裂公式為:

由于不同圖像集中圖像的特征是不同的,所以SANS-RF算法中的參數選擇也難以固定,因此采用自適應參數選擇過程,得出最優的組合參數,對于參數α,β應滿足上式中的約束條件.

實驗中采用分類錯誤率與準確率進行性能度量,對于樣本D,分類錯誤率定義為:

準確率則定義為:

具體實驗效果在下節進行對比驗證.

4 實驗過程及結果

4.1 空間金字塔模型

本節通過對比實驗來驗證詞袋模型與空間金字塔模型的分類效果,實驗設置為對Caltech101,256_ObjectCategories,SUN2012三種數據集中如圖4所示,對這些圖像提取特征并聚類,最后利用包外數據進行測試得到分類錯誤率testErr,每組實驗進行多次取平均值作為最終實驗數據,實驗結果如圖5所示.

圖4 數據集樣本

從圖5中數據可以看出對這三種數據集,在詞袋模型的基礎上引入空間金字塔模型可以有效的提高分類準確度,降低錯誤率,因此在后續算法改進中會以此模型為基礎繼續進行.

圖5 空間金字塔與詞袋模型對比結果

4.2 分布式vs單機版

圖像分類算法的計算時間會隨著圖片數量增加而急劇增加,但是在大數據平臺下,可以利用分布式處理來縮短程序的運行時間,該平臺有三個節點分別為master,slave1,slave2,其內存為 8 GB,4 線程運行,同時將圖片的視覺特征文件存放在Hadoop HDFS分布式系統中,Spark單機版與分布式系統運行對比結果見表2,運行時間以分鐘為單位.

表2 單機與分布式運行時間對比

加速比是指同一個任務在單機系統和分布式系統中運行所用時間的比率,用來衡量分布式算法的效率,其計算公式為Sp=T1/T2,T1是單節點下運行時間,T2是分布式運行時間,結果如圖6所示.

4.3 改進隨機森林算法的結果

根據上一節中SANS-RF算法的改進公式可知,線性組合算法的系數值對分類結果會有重要的影響,因此本節中首先用不同圖像集中的1000幅圖片進行測試,人為給定參數值,并以包外數據的分類錯誤率testErr作為指標進行驗證,實驗結果如表3所示.

由表3可知對不同圖像集參數的最優組合是不能固定的,因此引入參數的自適應選擇來得到最優的分類結果是合理的.

SANS-RF算法的在三種不同圖像集上的分類結果如圖 7 至圖 9 所示,其中,SVM(Support Vector Machine)是通常情況下圖像分類會選擇的算法,原始RF指Spark平臺上未改進的隨機森林方法,IMRF為文獻[4]中提出的利用權重與決策樹選擇的隨機森林改進算法.

圖6 Spark 平臺加速比結果圖

表3 SANS-RF 算法參數驗證表

圖7 圖像集 1(Caltech-101)中算法分類準確率對比

通過這幾種算法的對比,實驗結果表明,本文中提出的SANS-RF算法有著很好的分類準確率,遠遠高于基礎RF算法與支持向量機分類效果,并且比IMRF算法更加穩定,更適用于海量圖像的分布式應用.因此,本文提出的基于Spark mllib隨機森林的組合節點分裂算法是令人滿意的.

5 結束語

本文在Spark平臺下實現了不同場景圖像的準確分類,首先在簡單的詞袋模型的基礎上驗證了空間金字塔模型的有效性;其次針對隨機森林的節點分裂算法進行改進并實驗,通過對比,驗證該算法的有效性與準確性.Spark平臺可以有效提高算法運行效率的同時,又保證了分類準確率,適合海量圖像的分類研究.

圖8 圖像集 2(256-ObjectCategories)中算法分類準確率對比

圖9 圖像集 3(SUN2012)中算法分類準確率對比

同時可以在增加分類圖片數量和融合更成熟有效的節點分裂算法上進一步研究,以體現Spark平臺在處理速度上的優勢,并提高分類準確率.