一種基于S_Dbw的可變特征算子的改進(jìn)隨機(jī)森林算法

簡琤峰，陳嘉誠，張美玉

(浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，杭州 310023)

1 引 言

隨機(jī)森林算法從被提出至今一直備受關(guān)注.它在處理高維數(shù)據(jù)時(shí)的精度和效率不輸于神經(jīng)網(wǎng)絡(luò)和SVM算法[1].對(duì)于隨機(jī)森林的各種改進(jìn)方式不斷被提出.這些方式主要針對(duì)三個(gè)方面，分別是數(shù)據(jù)預(yù)處理優(yōu)化、算法自身構(gòu)建過程優(yōu)化和決策樹輸出組合方式優(yōu)化.數(shù)據(jù)預(yù)處理在模型訓(xùn)練之前，包括原始樣本的特征獲取，如文獻(xiàn)[2]的基于HOG的多特征融合算法，以及數(shù)據(jù)集平衡性處理，如常用的過采樣法.算法自身構(gòu)建過程優(yōu)化一般指對(duì)節(jié)點(diǎn)的分裂方式進(jìn)行優(yōu)化，經(jīng)典算法有閾值法、二分k-means等.而決策樹輸出組合方式改進(jìn)有霍夫森林、隨機(jī)組合等方式.

上述改進(jìn)方式確實(shí)從各自角度較大程度地提高了隨機(jī)森林的判別能力，然而它們都忽略了一個(gè)重要的事實(shí).由于決策樹自上而下使用一致的特征算子，數(shù)據(jù)集在經(jīng)過若干次分裂之后，子集中的數(shù)據(jù)會(huì)趨向于相似.此時(shí)，森林的判別能力不再隨著樹的深度增加而增加，使得后續(xù)分裂產(chǎn)生的節(jié)點(diǎn)之間具有較大的相似性，也是所謂的過早收斂.本文從文獻(xiàn)[3]中根據(jù)新聞話題演化對(duì)特征進(jìn)行演化的算法獲得啟發(fā)，根據(jù)數(shù)據(jù)集的不斷劃分，提出允許使用上下不一致特征的可變特征隨機(jī)森林.簡言之，將獲取原始樣本的數(shù)據(jù)特征這一過程，從算法訓(xùn)練前的數(shù)據(jù)預(yù)處理階段遷移到模型構(gòu)建階段，根據(jù)聚類評(píng)估指標(biāo)，使用不同的特征算子進(jìn)行二分聚類，從而維持節(jié)點(diǎn)分裂的可靠性和判別性.本文將使用S_Dbw算法[4]作為聚類評(píng)估指標(biāo)，它不需要引入外部數(shù)據(jù)，且在2010年Liu Y等人的單調(diào)性、噪聲、密度、組和偏態(tài)分布這五個(gè)方面測(cè)試中都非?？煽縖5].

隨機(jī)森林被廣泛應(yīng)用于各個(gè)領(lǐng)域，如圖像中的對(duì)象檢測(cè).2015年，Xiaolong Zhu等人提出使用結(jié)構(gòu)化隨機(jī)森林進(jìn)行手部檢測(cè)[6].該算法將隨機(jī)森林的輸出形式變?yōu)槎嫡谡郑行У睦昧四繕?biāo)對(duì)象像素之間的結(jié)構(gòu)關(guān)系，能夠以較高精度進(jìn)行手部檢測(cè).本文采用與Xiaolong Zhu等人相同的圖像數(shù)據(jù)集和結(jié)構(gòu)化方式，使用基于S_Dbw的可變特征隨機(jī)森林進(jìn)行手部檢測(cè)，并與Xiaolong Zhu等人的算法進(jìn)行比較.

2 可變特征隨機(jī)森林

隨機(jī)森林算法發(fā)展至今有多種改進(jìn)方式，但其大體的訓(xùn)練過程是相似的.對(duì)于原始數(shù)據(jù)集S，采用特征算子F：S→P，得到P表示S的特征集.令P對(duì)應(yīng)決策樹的根節(jié)點(diǎn)，使用劃分算法φ：P→P1，P2，則P1和P2對(duì)應(yīng)兩個(gè)子節(jié)點(diǎn).重復(fù)分裂過程，直至滿足葉子條件.顯然的，當(dāng)劃分算法采用某一確定的算法時(shí)，選擇不同的特征算子來進(jìn)行數(shù)據(jù)初始化，模型最終會(huì)得到不同的判別效果.一般來說，會(huì)選擇能使數(shù)據(jù)集具有盡可能大的離散度的算子.

然而，即使當(dāng)前數(shù)據(jù)集具有較大的離散程度，在經(jīng)過若干次劃分后，其生成的子集內(nèi)部數(shù)據(jù)的總體差異性會(huì)逐漸降低.這樣，后續(xù)的數(shù)據(jù)劃分很難具有合理性.另外，對(duì)于圖像數(shù)據(jù)而言，即使不進(jìn)行數(shù)據(jù)集的劃分，在使用不同的特征算子時(shí)同樣會(huì)使得數(shù)據(jù)呈現(xiàn)不同的離散程度.Li C等人[7]對(duì)于同一組圖像分別使用兩種不同特征算子，再使用t-SNE算法可視化對(duì)比兩種情況下數(shù)據(jù)的離散程度.而在圖1中，原始數(shù)據(jù)集包含4組圖像，分別為r1有噪聲(范圍在±25之間)，r2無噪聲，b1有噪聲，b2無噪聲.若只采用梯度特征，可以將數(shù)據(jù)集分為{r1，b1}和{r2，b2}.若只采用色彩特征，可以將數(shù)據(jù)分為{r1，r2}和{b1，b2}.若先采用梯度，再采用色彩，則決策樹可以“良好”生長到兩層.

圖1 使用不同特征時(shí)的劃分方式Fig.1 Two criterions for image set split

2.1 可變特征隨機(jī)森林的本質(zhì)

在進(jìn)行決策樹訓(xùn)練的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次劃分.那么如果每一次劃分都使用當(dāng)前最佳的特征算子從原始數(shù)據(jù)集中獲取特征，那么最終獲得的決策樹也可以具有更強(qiáng)的判別能力.這也是本文算法的本質(zhì).

對(duì)于集合F={fi}，其元素fi為特征算子.對(duì)于數(shù)據(jù)集S，disc(f，S)表示特征f在S中的判別能力，那么對(duì)于在第k次分裂時(shí)，使用特征fk=arg maxf∈Fdisc(f，S).同理，在第k+1次分裂時(shí)使用的特征為fk+1.本文的不定特征就是允許fk≠fk+1.

傳統(tǒng)隨機(jī)森林在進(jìn)行節(jié)點(diǎn)分裂時(shí)，有時(shí)會(huì)隨機(jī)或按照某些條件挑選當(dāng)前特征數(shù)據(jù)集的若干屬性作為分裂的數(shù)據(jù)參考.這一過程事實(shí)上也可以看做重新從原始數(shù)據(jù)中以新的特征算子獲取數(shù)據(jù)特征.所以，它也是可變特征這個(gè)概念的一個(gè)子集.

2.2 可變特征的易擴(kuò)展性

可變特征具有易擴(kuò)展的特點(diǎn).在很多研究工作中，多特征被視為增強(qiáng)算法效果的重要方法.但對(duì)多特征的使用方式通常有簡單線性加權(quán)組合[8-11]、自適應(yīng)加權(quán)[12]等.其中與本文算法最為相似的是自適應(yīng)加權(quán)組合特征.然而，當(dāng)參與組合的特征種類較多時(shí)，組合特征會(huì)難以避免的出現(xiàn)維數(shù)過大的問題.而可變特征只需擴(kuò)展備選特征算子庫，并從中選擇當(dāng)前最優(yōu)，對(duì)于維數(shù)產(chǎn)生的影響并不會(huì)過大.

3 本文算法

本文算法對(duì)于隨機(jī)森林進(jìn)行改進(jìn)的著重點(diǎn)在于使用上下不一致的特征，即可變特征.那么，如何從備選特征算子庫中選取當(dāng)前最佳算子，是應(yīng)用可變特征的關(guān)鍵.在傳統(tǒng)的改進(jìn)隨機(jī)隨機(jī)森林算法中，部分經(jīng)典算法使用二分聚類的方式進(jìn)行數(shù)據(jù)集的劃分.據(jù)此，本文算法使用二分k-means進(jìn)行節(jié)點(diǎn)分裂，并使用S_Dbw算法對(duì)每次二分k-means的結(jié)果進(jìn)行評(píng)估，從而選取最佳算子.S_Dbw的計(jì)算公式[4]如下：

S_Dbw(c)=Scat(c)+Dens_bw(c)

(1)

(2)

(3)

在本文算法中，隨機(jī)森林中的每棵決策樹的訓(xùn)練過程并無差異，所以將以一棵決策樹的訓(xùn)練過程代表整個(gè)隨機(jī)森林的訓(xùn)練過程.本文算法的訓(xùn)練步驟如下：

輸入： 原始樣本數(shù)據(jù)集S，特征算子庫F={fi}，非葉節(jié)點(diǎn)數(shù)據(jù)集最小尺寸Gmin.

輸出： 決策樹Tree={Branchi，Leafi}，Branchi表示非葉節(jié)點(diǎn)，Leafi表示葉節(jié)點(diǎn).

Step1.若S的尺寸小于Gmin，則生成一個(gè)葉節(jié)點(diǎn)Leaf，加入Tree，不進(jìn)入其它步驟; 否則，生成一個(gè)非葉結(jié)點(diǎn)Branch;

Step2.使用F對(duì)S進(jìn)行處理，即F(S)={Pi}，集合Pi表示fi(S);

Step3.使用二分k-means算法對(duì)Pi進(jìn)行劃分，得到子集Pi1和Pi2;

Step4.根據(jù)公式(1)(2)(3)評(píng)估Setp3中得到的每對(duì)子集，選擇最優(yōu)劃分，即

f*=arg maxfigetS_Dbw(Pi1，Pi2);

Step5.分別以f*(S)對(duì)應(yīng)的S1和S2為輸入，進(jìn)入Step1，生成當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn);

4 隨機(jī)森林在圖像檢測(cè)中的結(jié)構(gòu)化方式

傳統(tǒng)隨機(jī)森林用于圖像中對(duì)象檢測(cè)和分割的本質(zhì)，是建立從單個(gè)像素p到單個(gè)類別標(biāo)簽yp∈{0，1}的映射關(guān)系.它

圖2 隨機(jī)森林結(jié)構(gòu)化方式Fig.2 Structured forest

的輸入形式是一個(gè)特征向量，通常從以像素p為中心的鄰域圖塊中計(jì)算得到.它的輸出形式為類別標(biāo)簽的概率分布P(y|xp)，其中y∈{0，1}.

而在結(jié)構(gòu)化隨機(jī)森林中，輸出形式被變?yōu)镻(x，y|xp)，表示圖塊xp中坐標(biāo)為(x，y)的像素屬于目標(biāo)對(duì)象的概率.其本質(zhì)是建立從圖塊到二值圖像的映射關(guān)系.圖2(出自文獻(xiàn)[6])很好展示了兩者之間的差別.

5 實(shí) 驗(yàn)

本文將在圖像數(shù)據(jù)集中，對(duì)基于S_Dbw的可變特征隨機(jī)森林算法的結(jié)構(gòu)化形式進(jìn)行測(cè)試，并將結(jié)果與Xiaolong Zhu等人的結(jié)構(gòu)化隨機(jī)森林算法進(jìn)行比較.本文使用的數(shù)據(jù)集為GTEA(Geogia Tech Ego-centric Activity dataset)和EDSH1數(shù)據(jù)集.前者有Coffee、Tea和Peanut這三個(gè)子集，幾乎不包含攝像頭自身運(yùn)動(dòng).而后者有EDSH1和EDSH2兩個(gè)子集，存在較多光照條件的改變和攝像頭自身的運(yùn)動(dòng).對(duì)于實(shí)驗(yàn)的結(jié)果，根據(jù)不同的閾值，求對(duì)應(yīng)的精度(P)和召回率(R)，并求得相應(yīng)的F值.最終取F值的最大值.F值的計(jì)算公式如下：

圖3 實(shí)驗(yàn)樣例Fig.3 Samples of experiments

(4)

5.1 實(shí)驗(yàn)1

使用GTEA數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，即以Coffee數(shù)據(jù)作為訓(xùn)練樣本集，以Tea和Peanut數(shù)據(jù)作為測(cè)試樣本集.首先將全部樣本降采樣為180×320的圖像，再設(shè)置圖塊尺寸為16×16.再文獻(xiàn)[6]中，當(dāng)算法只使用Color和Gradient組合特征時(shí)，檢測(cè)效果明顯弱于使用Color、Gradient和Texture(指像素差異)三者組合成的特征.而在表1所示的實(shí)驗(yàn)結(jié)果中，在同樣包含16棵決策樹的情況下，三中情況的檢測(cè)結(jié)果不相上下.在本文算法只使用Color和Gradient特征的情況下，與文獻(xiàn)[6]使用Color、Gradient和Texture組合特征相比，甚至有微弱的優(yōu)勢(shì).這證明了本文算法確實(shí)可以在每一次分裂只使用單一特征的情況下，達(dá)到甚至超過組合特征的效果.在圖3中給出了實(shí)驗(yàn)中若干個(gè)樣本及相應(yīng)的檢測(cè)結(jié)果.

表1 在GTEA上進(jìn)行對(duì)比Table 1 Comparcomparation in GTEA dataset

5.2 實(shí)驗(yàn)2

使用EDSH數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，即以EDSH1作為訓(xùn)練樣本集，以EDSH2作為測(cè)試樣本集.同樣將全部樣本降采樣為180×320的圖像，設(shè)置圖塊尺寸為16×16.實(shí)驗(yàn)結(jié)果如表2所示，b項(xiàng)仍然略優(yōu)于a項(xiàng)，這證明在樣本存在光照條件變化的情況下，本文算法可以降低特征對(duì)于光照變化的敏感度.

表2 在EDSH上進(jìn)行對(duì)比Table 2 Comparation in EDSH dataset

6 結(jié) 語

本文提出在隨機(jī)森林中允許上下使用不一樣的特征算子，而不僅僅只從統(tǒng)一特征向量中提取不同屬性進(jìn)行節(jié)點(diǎn)分裂.此外，本文使用本文算法的結(jié)構(gòu)化形式，并進(jìn)行了手部檢測(cè)的實(shí)驗(yàn).實(shí)驗(yàn)證明算法是有效的.但在訓(xùn)練過程中，對(duì)于當(dāng)前最佳特征算子的選取需要耗費(fèi)較多的時(shí)間.這一問題在算子庫規(guī)模較大時(shí)會(huì)變得更加明顯，不能很好的滿足可變特征的易于擴(kuò)展的特點(diǎn).后續(xù)研究將圍繞如何以更高效的方式選取最佳特征算子展開.

[1] Caruana R，Karampatziakis N，Yessenalina A.An empirical evalu-ation of supervised learning in high dimensions[C].International Conference on Machine Learning，ACM，San Diego，California，USA，2008：96-103.

[2] Guo Jin-xin，Chen Wei.Face recognition based on HOG multi-feature fusion and random forest[J].Computer Science，2013，40(10)：279-282.

[3] Zhao Xu-jian，Yang Chun-ming，Li Bo，et al.A topic evolution mining algorithm of news text based on feature evolving[J].Chinese Journal of Computers，2014，37(4)：819-832.

[4] Halkidi M，Vazirgiannis M.Clustering validity assessment： finding the optimal partitioning of a data set[C].Proceedings of Institute of Electrical and Electronics Engineers International Conference on Data Mining，San Jose，California，USA，2001：187-194.

[5] Liu Y，Li Z，Xiong H，et al.Understanding of internal clustering validation measures[C].Proceedings of Institute of Electrical and Electronics Engineers International Conference on Data Mining，IEEE，Sydney，Australia，2010：911-916.

[6] Zhu X，Jia X，Wong K Y K.Structured forests for pixel-level hand detection and hand part labelling[J].Computer Vision & Image Understanding，2015，141(C)：95-107.

[7] Li C，Kitani K M.Pixel-level hand detection in ego-centric videos[C].Proceedings of Institute of Electrical and Electronics Engineers Conference on Computer Vision and Pattern Recognition，Portland，Oregon，USA，2013：3570-3577.

[8] Yang Jian，Yang Jing-yu，Wang Zheng-qun，et al.A novel feature extraction method based on feature integration[J].Chinese Journal of Computers，2002，25(6)：570-575.

[9] Mei K，Xu L，Li B，et al.A real-time hand detection system based on multi-feature[J].Neurocomputing，2015，158(C)：184-193.

[10] Wan Yuan，Li Huan-huan，Wu Ke-feng，et al.Fusion with layered features of LBP and HOG for face recognition[J].Journal of Computer-Aided Design & Computer Graphics，2015，27(4)：640-650.

[11] Zhu Yu-lian，Chen Song-can.Sub-image method based on feature sampling and feature fusion for face recognition[J].Journal of Software，2012，23(12)：3209-3220.

[12] Xiang Ru-xi，Li Jian-wei.Particle filter tracking method of multiple features based adaptive fusion[J].Journal of Computer-Aided Design & Computer Graphics，2012，24(1)：97-103.

附中文參考文獻(xiàn)：

[2] 郭金鑫，陳 瑋.基于HOG多特征融合與隨機(jī)森林的人臉識(shí)別[J].計(jì)算機(jī)科學(xué)，2013，40(10)：279-282.

[3] 趙旭劍，楊春明，李 波，等.一種基于特征演變的新聞話題演化挖掘方法[J].計(jì)算機(jī)學(xué)報(bào)，2014，37(4)：819-832.

[8] 楊 健，楊靜宇，王正群，等.一種組合特征抽取的新方法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25(6)：570-575.

[10] 萬 源，李歡歡，吳克風(fēng)，等.LBP和HOG的分層特征融合的人臉識(shí)別[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015，27(4)：640-650.

[11] 朱玉蓮，陳松燦.特征采樣和特征融合的子圖像人臉識(shí)別方法[J].軟件學(xué)報(bào)，2012，23(12)：3209-3220.

[12] 相入喜，李見為.多特征自適應(yīng)融合的例子濾波跟蹤算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24(1)：97-103.

1http：//www.cs.cmu.edu