改進(jìn)隨機(jī)森林算法的圖像分類(lèi)應(yīng)用①

張志禹,吉元元,滿蔚仕

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院,西安 710048)

1 引言

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

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

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

圖1 Spark 生態(tài)系統(tǒng)

在本文中實(shí)現(xiàn)圖像分類(lèi)的步驟如下:

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

Step2.對(duì)圖像的特征向量進(jìn)行聚類(lèi)得到視覺(jué)單詞[11],計(jì)算每幅圖片到這些視覺(jué)單詞的距離,并將其映射到距離最近的視覺(jué)單詞,完成每幅圖像的詞頻表達(dá)[12];

Step3.利用改進(jìn)的自適應(yīng)節(jié)點(diǎn)分裂隨機(jī)森林算法(Self-Adaptive Node Split Random Forest,SANS-RF)進(jìn)行圖像分類(lèi)并利用包外圖像進(jìn)行驗(yàn)證,改進(jìn)算法及涉及到的理論會(huì)在后續(xù)段落重點(diǎn)介紹.

2 空間金字塔模型

2.1 詞袋模型

在場(chǎng)景圖像分類(lèi)的眾多算法中,BoW模型的最大優(yōu)點(diǎn)是將圖像表示為視覺(jué)詞匯,更容易識(shí)別并表示出圖像中感興趣的部分[13],即將圖像看作一個(gè)“文檔”,關(guān)鍵詞就是提取圖像的SURF特征,稱(chēng)為“視覺(jué)詞典”[12].

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

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

同時(shí)選用二階標(biāo)準(zhǔn)高斯函數(shù)作為濾波器,即在Hessian矩陣構(gòu)造前,需對(duì)其進(jìn)行高斯濾波:

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

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

具體公式推導(dǎo)可詳見(jiàn)文獻(xiàn)[14].

通過(guò)以上方法可以生成尺度空間,再通過(guò)精確定位特征點(diǎn),選取特征點(diǎn)主方向確定的步驟,就可以構(gòu)造SURF特征點(diǎn)描述算子,進(jìn)行圖像特征提取.

2.2 空間金字塔結(jié)構(gòu)

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

該模型首先對(duì)局部特征量化,然后在每個(gè)金字塔水平把圖像劃分為細(xì)網(wǎng)格序列[15],從每個(gè)金字塔水平的網(wǎng)格中提取特征,同時(shí)給每層網(wǎng)格分配一個(gè)權(quán)重,按權(quán)重把每層網(wǎng)格特征加權(quán)串聯(lián)在一起,如圖2所示.

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

所以一幅圖像的最終加權(quán)空間金字塔表現(xiàn)方法為:

以上公式可以將需要分類(lèi)的圖像更好表示.

3 隨機(jī)森林算法

3.1 算法簡(jiǎn)介

隨機(jī)森林是一種組合分類(lèi)器,它利用Boostrap重抽樣方法從原始樣本中抽取多個(gè)樣本[16]構(gòu)造子數(shù)據(jù)集,利用子數(shù)據(jù)集形成基決策樹(shù)并對(duì)其進(jìn)行訓(xùn)練,RF在決策樹(shù)的訓(xùn)練中引入了隨機(jī)屬性選擇,即對(duì)基決策樹(shù)的每個(gè)節(jié)點(diǎn),先從該節(jié)點(diǎn)的屬性集合中隨機(jī)選擇一個(gè)包含k個(gè)屬性的子集,然后再?gòu)倪@些子集中選擇一個(gè)最優(yōu)屬性用于節(jié)點(diǎn)分裂,這樣可以使每棵決策樹(shù)彼此不同,提升系統(tǒng)的多樣性,然后將這些決策樹(shù)組合在一起,利用Boostrap中未抽取到的樣本作為包外數(shù)據(jù)集進(jìn)行驗(yàn)證,并通過(guò)投票法得到分類(lèi)結(jié)果,從而提升分類(lèi)性能,算法流程圖如圖3所示.

圖3 隨機(jī)森林算法

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

3.2 改進(jìn)隨機(jī)森林算法

大量研究都證明了隨機(jī)森林算法具有較高的分類(lèi)準(zhǔn)確率,對(duì)異常值和噪聲有很好的容忍度,而且不易出現(xiàn)過(guò)擬合.本文提出的SANS-RF算法,通過(guò)參數(shù)的自適應(yīng)選擇過(guò)程,來(lái)優(yōu)化算法中決策樹(shù)的節(jié)點(diǎn)分裂算法,達(dá)到提高算法分類(lèi)精度的目的.

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

其中Dv表示第v個(gè)分支節(jié)點(diǎn)包含的D中所有在屬性a上取值為av的樣本:

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

表1 節(jié)點(diǎn)分裂算法對(duì)比

結(jié)合表1內(nèi)容,節(jié)點(diǎn)分裂準(zhǔn)則應(yīng)以劃分后數(shù)據(jù)集純度更高為目標(biāo),因此組合節(jié)點(diǎn)分裂公式為:

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

實(shí)驗(yàn)中采用分類(lèi)錯(cuò)誤率與準(zhǔn)確率進(jìn)行性能度量,對(duì)于樣本D,分類(lèi)錯(cuò)誤率定義為:

準(zhǔn)確率則定義為:

具體實(shí)驗(yàn)效果在下節(jié)進(jìn)行對(duì)比驗(yàn)證.

4 實(shí)驗(yàn)過(guò)程及結(jié)果

4.1 空間金字塔模型

本節(jié)通過(guò)對(duì)比實(shí)驗(yàn)來(lái)驗(yàn)證詞袋模型與空間金字塔模型的分類(lèi)效果,實(shí)驗(yàn)設(shè)置為對(duì)Caltech101,256_ObjectCategories,SUN2012三種數(shù)據(jù)集中如圖4所示,對(duì)這些圖像提取特征并聚類(lèi),最后利用包外數(shù)據(jù)進(jìn)行測(cè)試得到分類(lèi)錯(cuò)誤率testErr,每組實(shí)驗(yàn)進(jìn)行多次取平均值作為最終實(shí)驗(yàn)數(shù)據(jù),實(shí)驗(yàn)結(jié)果如圖5所示.

圖4 數(shù)據(jù)集樣本

從圖5中數(shù)據(jù)可以看出對(duì)這三種數(shù)據(jù)集,在詞袋模型的基礎(chǔ)上引入空間金字塔模型可以有效的提高分類(lèi)準(zhǔn)確度,降低錯(cuò)誤率,因此在后續(xù)算法改進(jìn)中會(huì)以此模型為基礎(chǔ)繼續(xù)進(jìn)行.

圖5 空間金字塔與詞袋模型對(duì)比結(jié)果

4.2 分布式vs單機(jī)版

圖像分類(lèi)算法的計(jì)算時(shí)間會(huì)隨著圖片數(shù)量增加而急劇增加,但是在大數(shù)據(jù)平臺(tái)下,可以利用分布式處理來(lái)縮短程序的運(yùn)行時(shí)間,該平臺(tái)有三個(gè)節(jié)點(diǎn)分別為master,slave1,slave2,其內(nèi)存為 8 GB,4 線程運(yùn)行,同時(shí)將圖片的視覺(jué)特征文件存放在Hadoop HDFS分布式系統(tǒng)中,Spark單機(jī)版與分布式系統(tǒng)運(yùn)行對(duì)比結(jié)果見(jiàn)表2,運(yùn)行時(shí)間以分鐘為單位.

表2 單機(jī)與分布式運(yùn)行時(shí)間對(duì)比

加速比是指同一個(gè)任務(wù)在單機(jī)系統(tǒng)和分布式系統(tǒng)中運(yùn)行所用時(shí)間的比率,用來(lái)衡量分布式算法的效率,其計(jì)算公式為Sp=T1/T2,T1是單節(jié)點(diǎn)下運(yùn)行時(shí)間,T2是分布式運(yùn)行時(shí)間,結(jié)果如圖6所示.

4.3 改進(jìn)隨機(jī)森林算法的結(jié)果

根據(jù)上一節(jié)中SANS-RF算法的改進(jìn)公式可知,線性組合算法的系數(shù)值對(duì)分類(lèi)結(jié)果會(huì)有重要的影響,因此本節(jié)中首先用不同圖像集中的1000幅圖片進(jìn)行測(cè)試,人為給定參數(shù)值,并以包外數(shù)據(jù)的分類(lèi)錯(cuò)誤率testErr作為指標(biāo)進(jìn)行驗(yàn)證,實(shí)驗(yàn)結(jié)果如表3所示.

由表3可知對(duì)不同圖像集參數(shù)的最優(yōu)組合是不能固定的,因此引入?yún)?shù)的自適應(yīng)選擇來(lái)得到最優(yōu)的分類(lèi)結(jié)果是合理的.

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

圖6 Spark 平臺(tái)加速比結(jié)果圖

表3 SANS-RF 算法參數(shù)驗(yàn)證表

圖7 圖像集 1(Caltech-101)中算法分類(lèi)準(zhǔn)確率對(duì)比

通過(guò)這幾種算法的對(duì)比,實(shí)驗(yàn)結(jié)果表明,本文中提出的SANS-RF算法有著很好的分類(lèi)準(zhǔn)確率,遠(yuǎn)遠(yuǎn)高于基礎(chǔ)RF算法與支持向量機(jī)分類(lèi)效果,并且比IMRF算法更加穩(wěn)定,更適用于海量圖像的分布式應(yīng)用.因此,本文提出的基于Spark mllib隨機(jī)森林的組合節(jié)點(diǎn)分裂算法是令人滿意的.

5 結(jié)束語(yǔ)

本文在Spark平臺(tái)下實(shí)現(xiàn)了不同場(chǎng)景圖像的準(zhǔn)確分類(lèi),首先在簡(jiǎn)單的詞袋模型的基礎(chǔ)上驗(yàn)證了空間金字塔模型的有效性;其次針對(duì)隨機(jī)森林的節(jié)點(diǎn)分裂算法進(jìn)行改進(jìn)并實(shí)驗(yàn),通過(guò)對(duì)比,驗(yàn)證該算法的有效性與準(zhǔn)確性.Spark平臺(tái)可以有效提高算法運(yùn)行效率的同時(shí),又保證了分類(lèi)準(zhǔn)確率,適合海量圖像的分類(lèi)研究.

圖8 圖像集 2(256-ObjectCategories)中算法分類(lèi)準(zhǔn)確率對(duì)比

圖9 圖像集 3(SUN2012)中算法分類(lèi)準(zhǔn)確率對(duì)比

同時(shí)可以在增加分類(lèi)圖片數(shù)量和融合更成熟有效的節(jié)點(diǎn)分裂算法上進(jìn)一步研究,以體現(xiàn)Spark平臺(tái)在處理速度上的優(yōu)勢(shì),并提高分類(lèi)準(zhǔn)確率.