改進(jìn)的二視圖隨機(jī)森林

夏笑秋，陳松燦,2+

1.南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，南京210016

2.南京航空航天大學(xué) 模式分析與機(jī)器智能工信部重點實驗室，南京210016

由Breiman 在2001 年首次提出的隨機(jī)森林（random forest，RF）已成為應(yīng)用最廣的集成學(xué)習(xí)算法之一。RF 通過利用隨機(jī)重采樣和結(jié)點隨機(jī)分裂策略構(gòu)建出多棵決策樹，進(jìn)而通過投票得到最終分類結(jié)果。由于其具有高精度、好的可解釋性、低的過擬合風(fēng)險及良好的容噪能力等優(yōu)點，已在包括計算機(jī)視覺和數(shù)據(jù)挖掘等眾多領(lǐng)域取得了極大成功，同時也激發(fā)眾多后繼者對RF 的廣泛研究，發(fā)展出了諸如動態(tài)RF、深度森林等RF 變體。

盡管如此，現(xiàn)有的RF 及其變體幾乎全聚焦于單視圖學(xué)習(xí)場景，針對二視圖或多視圖的RF 構(gòu)建卻很少。現(xiàn)實中很多分類問題本質(zhì)上是多視圖的，因為單視圖數(shù)據(jù)通常并不能描述出數(shù)據(jù)信息的全貌，數(shù)據(jù)特征往往需要從多個方面進(jìn)行刻畫，相互補(bǔ)充。例如一張圖片可由其紋理特征、形狀特征和顏色特征來共同表示，即形成了一組多視圖數(shù)據(jù)。充分利用來自不同視圖的互補(bǔ)信息可以帶來泛化性能的提高，并已推動了多視圖學(xué)習(xí)的廣泛展開。

然而，當(dāng)前結(jié)合RF 的二視圖或多視圖工作僅有兩個，其一是用于行人檢測的多視圖RF，另一個是研究放射性組的基于差異的多視圖RF。兩者提出的方法都是先為各個視圖生成各自的RF，然后在決策（或后程）階段才融合視圖信息。顯然，這些方法并未全程利用到?jīng)Q策樹/RF 的層次結(jié)構(gòu)，在各層次的各結(jié)點處進(jìn)行視圖間的信息交互，這無疑是對信息資源的一種浪費(fèi)。為了克服這一不足，本文在二視圖場景下，提出了一種改進(jìn)的二視圖RF（improved two-view random forest，ITVRF），考慮將視圖交互信息融入到?jīng)Q策樹的全程構(gòu)建階段，充分利用決策樹/RF 的層次特征逐層進(jìn)行特征交互，以實現(xiàn)視圖數(shù)據(jù)的全程融合。為此，需要解決以下兩個問題：

（1）如何在決策樹的構(gòu)建階段逐層融合二視圖數(shù)據(jù)？

（2）如何將融合后的數(shù)據(jù)用于分類？

針對第一個問題，可通過諸如經(jīng)典的典型相關(guān)分析（canonical correlation analysis，CCA）來解決。CCA 是研究視圖間相關(guān)性的一種有效方法。具體而言，對于一組給定的二視圖數(shù)據(jù)，CCA 旨在獲得一組基向量使視圖間的相關(guān)性最大。作為一類經(jīng)典的二視圖數(shù)據(jù)處理方法，CCA 自然也可用于信息融合。常見的特征融合方法分為并行和串行兩種。在決策樹的全程構(gòu)建階段進(jìn)行視圖融合是ITVRF 能夠取得優(yōu)越性能的關(guān)鍵。

針對第二個問題，ITVRF 考慮利用樣本的類信息來進(jìn)行分類。將數(shù)據(jù)投影到線性判別分析（linear discriminant analysis，LDA）對應(yīng)的判別向量上，使得類內(nèi)樣本盡可能緊湊，類間樣本盡可能分離。對于投影后的樣本，利用不純度測量方法計算出當(dāng)前最佳分割數(shù)據(jù)空間的超平面，在超平面創(chuàng)建的每個分區(qū)中生成一個子樹。依此遞歸進(jìn)行，最終得到一棵二視圖決策樹。對樣本判別信息的全程利用是導(dǎo)致ITVRF 產(chǎn)生良好分類效果的另一個原因。

值得一提的是，ITVRF 先利用CCA 融合視圖信息，再用LDA 進(jìn)行樣本投影，這要求先后計算一對CCA 向量和LDA 向量，增加了算法的復(fù)雜性，導(dǎo)致很大程度的低效性。幸運(yùn)的是，早期所提出的增強(qiáng)組合特征判別性的CCA（combined-feature-discriminability enhanced canonical correlation analysis，CECCA）提供了將兩步合為一步的辦法。CECCA 是一種監(jiān)督型降維方法，彌補(bǔ)了CCA 抽取出的特征未必具有良好判別性這一不足。通過直接將數(shù)據(jù)投影到一組兼顧視圖間相關(guān)性和判別性的向量上，CECCA 可以一步解決上述兩個問題，為ITVRF 提供了效率保證。

1 相關(guān)知識介紹

1.1 隨機(jī)森林

隨機(jī)森林（RF）是Breiman 提出的由一組決策樹{(,θ),=1,2,…,}組成的分類器，其中θ是相互獨立且同分布的隨機(jī)向量，表示RF 中決策樹的個數(shù)，RF 最終由所有決策樹投票決定輸入向量的最終分類結(jié)果。

RF 的生成步驟如下：

（1）利用bootstrap 重采樣法有放回地隨機(jī)抽取個自助樣本集，每個樣本集的容量都與原始訓(xùn)練集相同。

（2）設(shè)有個特征，在每棵決策樹的每個結(jié)點隨機(jī)抽取個特征（<）。通過不純度測量，在個特征中選擇最具分類能力的特征進(jìn)行結(jié)點分裂。

（3）在個樣本集上分別構(gòu)建決策樹，每棵樹都最大限度地自由生長，即不進(jìn)行剪枝處理。

（4）RF 的最終預(yù)測結(jié)果通過多數(shù)投票法得到。

1.2 典型相關(guān)分析

典型相關(guān)分析（CCA）是研究兩組變量相關(guān)關(guān)系的多元統(tǒng)計方法，在二視圖學(xué)習(xí)中，CCA 早已廣泛應(yīng)用于特征提取和信息融合。

給出一組二視圖數(shù)據(jù)集{(x,y)}∈R×R，其中x和y分別來自兩個不同的視圖。令

分別表示兩個視圖。CCA 旨在尋找一組投影方向w∈R和w∈R，使得樣本集和在投影空間的相關(guān)性最大。可以通過優(yōu)化如下函數(shù)獲得：

分別為樣本集的自協(xié)方差矩陣和互協(xié)方差矩陣。

CCA 尋找的投影向量w和w可以通過求解如下問題獲得：

在得到w和w后，對樣本對(,)進(jìn)行特征組合。常用的組合方法有兩種，并行組合

和串行組合

在進(jìn)行分類任務(wù)時，可利用上述信息融合方法得到組合屬性特征，再將該組合特征作為輸入用于預(yù)測。

1.3 線性判別分析

線性判別分析（LDA）是一種有監(jiān)督的降維技術(shù)，其目標(biāo)是尋找一個有效的投影方向，使得數(shù)據(jù)投影后類內(nèi)散度盡可能小，類間散度盡可能大。

假設(shè)有一組樣本集=[,,…,x]∈R，LDA的目標(biāo)函數(shù)定義為：

式中，μ為第類樣本的均值向量；為的類間散布矩陣；為類內(nèi)散布矩陣。

LDA 的解為：

2 改進(jìn)的二視圖隨機(jī)森林

如前分析，現(xiàn)有的針對二視圖場景的RF 構(gòu)建都是先為各個視圖生成對應(yīng)的RF，再通過各個RF 投票決定最終預(yù)測結(jié)果。這些方法的弊端是在后程的決策階段才利用了視圖間的互補(bǔ)信息。本文提出的ITVRF 方法彌補(bǔ)了這一不足。ITVRF 中的每棵決策樹都獨立生成，且在樹的構(gòu)建階段全程進(jìn)行了視圖間的信息交互。本章將詳細(xì)介紹ITVRF的實現(xiàn)過程。

2.1 融合視圖數(shù)據(jù)

假設(shè){(x,y)}∈R×R為一組二視圖樣本集，令數(shù)據(jù)矩陣

其中，C、C和C的定義同式（2），和分別表示并行組合樣本集[,]的類間散布矩陣和類內(nèi)散布矩陣。目標(biāo)向量可通過求解如下廣義特征值問題而獲得：

2.2 構(gòu)建二視圖決策樹

p可看作并行樣本對z在上的投影。而后排序所有p，形成-1 個s 分割點q=(p+ p)/2。經(jīng)過分割點q且與正交的超平面為當(dāng)前劃分?jǐn)?shù)據(jù)空間的候選超平面。每個超平面將當(dāng)前的數(shù)據(jù)空間劃分為和兩個分區(qū)：

其中，代表兩個分區(qū)中相對較純的一個。利用不純度測量方法（如信息增益準(zhǔn)則）選出所有中樣本信息最純的一個，將其對應(yīng)的分割點q記作。經(jīng)過的候選超平面是所求的最佳超平面。對每個分區(qū)重復(fù)上述操作生成子樹，直到滿足決策樹的停止生長條件為止。二視圖決策樹的生長過程詳見算法1。

生成二視圖決策樹

輸入：={(,),(,),…,(x,y)} 為一個二視圖數(shù)據(jù)集，_為葉子結(jié)點的最小樣本數(shù)。

輸出：二視圖決策樹。

2.3 構(gòu)建二視圖隨機(jī)森林

利用bootstrap 重采樣技術(shù)隨機(jī)抽取個自助樣本集，在每個樣本集上分別構(gòu)建決策樹，每棵決策樹不受限制自由生長。ITVRF 由按上述方法生成的棵決策樹組成。

在預(yù)測階段，輸入一個二視圖樣本對(,)，ITVRF的最終預(yù)測結(jié)果由森林中的所有決策樹投票共同決定：

其中，(?)為指示函數(shù)，h是ITVRF 中的單個決策樹分類器。

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集

表1 UCI數(shù)據(jù)集統(tǒng)計信息Table 1 Statistics for UCI datasets

此外，還在3 個真實多視圖數(shù)據(jù)集SPECTF、機(jī)器人執(zhí)行故障數(shù)據(jù)集和Microsoft Research Cambridge v1（MSRC-v1）上對ITVRF進(jìn)行了性能評估。SPECTF數(shù)據(jù)集包含兩組與不同受試者應(yīng)激狀態(tài)和靜息對應(yīng)的圖像特征，可被視為一組維度均為22 的二視圖。機(jī)器人執(zhí)行故障數(shù)據(jù)集描述了機(jī)器人在故障檢測后的力和扭矩對應(yīng)的兩組特征，維度均為45，可被視為一組二視圖數(shù)據(jù)。該數(shù)據(jù)集被劃分為5 個學(xué)習(xí)任務(wù)，具體信息見表2。MSRC-v1 數(shù)據(jù)集共有240 幅圖像，可分為8 類。本文選取了7 類作為實驗數(shù)據(jù)。這些類是樹、建筑、飛機(jī)、牛、臉、汽車和自行車，每個類有30 個圖像。從每幅圖像中提取4 個特征作為4 個視圖，即顏色矩、方向梯度直方圖、局部二進(jìn)制模式和中間特征。結(jié)合不同特征，可以得到兩個二視圖數(shù)據(jù)集，具體信息如表3 所示。

表2 機(jī)器人執(zhí)行故障數(shù)據(jù)集Table 2 Robot execution failures dataset

表3 從MSRC-v1 數(shù)據(jù)集中選擇的二視圖數(shù)據(jù)集信息Table 3 Two-view dataset information selected from MSRC-v1 datasets

3.2 實驗設(shè)計

為了對每個方法進(jìn)行公平比較，實驗中所有RF參數(shù)都設(shè)成相同，即RF 中決策樹個數(shù)均為10，每棵決策樹的最大深度均不設(shè)限制，即不進(jìn)行任何剪枝處理，葉子結(jié)點的最小樣本數(shù)_均為2，決策樹均選擇信息增益準(zhǔn)則作為不純度準(zhǔn)則。本實驗重復(fù)10 次，選取平均值來比較各個方法的性能。評價標(biāo)準(zhǔn)采用AUC。實驗仿真的參數(shù)詳見表4。

表4 實驗仿真參數(shù)Table 4 Experimental simulation parameters

引言部分提到，現(xiàn)有的TVRF 都是先為每個視圖生成對應(yīng)的RF，在決策階段再進(jìn)行融合，其中基于差異的TVRF將RF 作為生成差異矩陣的中間載體，再融合差異矩陣作為輸入生成新的RF，而ITVRF 也同樣可以計算出對應(yīng)的差異矩陣并進(jìn)行后續(xù)工作。本文著重研究的是最基本的RF 二視圖數(shù)據(jù)融合方法，而非對已有的二視圖RF 模型進(jìn)行改造，故此處不對ITVRF 和已有的TVRF 方法進(jìn)行基于差異矩陣處理后的比較。

為了全面比較和解釋ITVRF 的性能，本文也專門針對fisherRF 設(shè)計了一個拓展的二視圖fisher 隨機(jī)森林（TV_fisherRF）。TV_fisherRF 的實現(xiàn)思路是，針對每個視圖生成對應(yīng)的fisherRF，最終預(yù)測結(jié)果由每個fisherRF 分別投票決定，其中，fisherRF 是指由若干fisher 決策樹組成的RF。由于ITVRF 中的決策樹和fisher 決策樹都利用了樣本的判別信息進(jìn)行分類，TV_fisherRF 特別作為TVRF 和ITVRF 性能的中間比較方法。

3.3 實驗結(jié)果比較

表5 為ITVRF 與現(xiàn)有的二視圖RF 的比較結(jié)果，表6 為ITVRF 與現(xiàn)有多視圖算法MLRA 的比較結(jié)果。通過分析可得出如下結(jié)論：

表5 AUC 值和運(yùn)行時間Table 5 AUC value and running time

表6 ITVRF 與多視圖算法MLRA 的AUC 值Table 6 AUC values of ITVRF and multi-view method MLRA

（1）相較于TVRF 和TV_fisherRF，ITVRF 的AUC值獲得明顯的提高。這是因為TVRF 和TV_fisherRF均在決策階段才利用到了視圖數(shù)據(jù)間的互補(bǔ)信息，而ITVRF 是在整個決策樹的生成過程中都進(jìn)行了信息融合。對信息的充分利用是ITVRF 取得更優(yōu)性能的關(guān)鍵。

（2）TV_fisherRF的AUC值大多高于TVRF。TV_fisherRF 和TVRF 的不同之處在于TV_fisherRF 的基學(xué)習(xí)器是fisher 決策樹，而fisher 決策樹利用LDA 方法生成具有判別性的決策邊界。由此可見ITVRF 的性能能夠優(yōu)于已有的TVRF 的另一個原因是CECCA方法生成的決策邊界兼顧了樣本的相關(guān)性和判別性，使其更加適合分類。

（3）對于特征數(shù)較少的樣本集，如Iris、Banknote、Diabetes 等，ITVRF 的AUC 值顯著高于TVRF 和TV_fisherRF。這是因為對于人工分割的二視圖數(shù)據(jù)，視圖之間的信息本身是互補(bǔ)的，這在特征數(shù)較少的樣本中體現(xiàn)得尤為明顯?，F(xiàn)有的TVRF 在決策階段才進(jìn)行視圖間的數(shù)據(jù)交互，導(dǎo)致了信息的嚴(yán)重欠利用。

（4）ITVRF 性能略優(yōu)于多視圖算法MLRA 性能。值得一提的是，ITVRF 聚焦于二視圖RF 場景，主要關(guān)注的是如何實現(xiàn)在決策樹生長過程中通過視圖特征的逐層交互達(dá)到全程決策的融合，故ITVRF 更加關(guān)注與同類體系算法的比較。

3.4 參數(shù)分析

接下來研究ITVRF 中二視圖決策樹的個數(shù)、最大深度和葉子結(jié)點最小樣本數(shù)_對性能的影響。

圖1（a）和圖1（b）分別表示在決策樹個數(shù)取不同值時，部分手工分割二視圖數(shù)據(jù)集和真實數(shù)據(jù)集上的AUC 值，其中的取值范圍為{10，25，50，75，100}。從實驗結(jié)果可以看出，隨著決策樹個數(shù)的增多，ITVRF 性能越好。

圖1 不同K 值下的AUC 值Fig.1 AUC value with different values of K

圖2（a）和圖2（b）表示不同下ITVRF 在部分手工分割二視圖數(shù)據(jù)集和真實數(shù)據(jù)集上的AUC值。的取值范圍為{2，5，8，10，}，其中表示所有決策樹都生長到最大深度，即不進(jìn)行任何剪枝處理。分析實驗結(jié)果可以得到，隨著的增大，AUC 值會隨之增大。但若任ITVRF 完全自由生長，決策樹可能會出現(xiàn)過擬合進(jìn)而影響性能。

圖2 不同depth 值下的AUC 值Fig.2 AUC value with different values of depth

不同_下ITVRF 在部分手工分割二視圖數(shù)據(jù)集和真實數(shù)據(jù)集上的AUC值見圖3（a）和圖3（b）。_的取值范圍為{2，4，6，8，10}。從圖中可以看出，_值對ITVRF的性能無明顯影響。

圖3 不同min_obj 值下的AUC 值Fig.3 AUC value with different values of min_obj

3.5 算法復(fù)雜度分析

ITVRF 的運(yùn)行時間見表5?？梢钥闯鲈跇颖咎卣鲾?shù)較小時，TVRF 效率優(yōu)于ITVRF。這是因為ITVRF 算法的步驟6 需要計算投影向量，時間復(fù)雜度為((+)3)，其中和分別表示兩個視圖的特征數(shù)。

隨著特征數(shù)的增大，ITVRF 比TVRF 的運(yùn)行效率更高。因為TVRF 在結(jié)點分裂時需要在每個特征中依次搜索最優(yōu)分割點，這無疑消耗了大量時間。而ITVRF 雖然計算了投影向量，訓(xùn)練時間略有增加，但無需在每個屬性中搜索最優(yōu)分割點。

可以看出，ITVRF 與現(xiàn)有的TVRF 實際應(yīng)用成本相當(dāng)。

4 總結(jié)與展望

多視圖數(shù)據(jù)在現(xiàn)實世界中非常常見，從多視圖數(shù)據(jù)中往往能夠獲取比單視圖數(shù)據(jù)更有用的信息。然而RF 作為一類實現(xiàn)簡單、性能優(yōu)越的分類器，針對二視圖或多視圖的RF 構(gòu)建卻很少，且僅有的二視圖RF 均未利用到RF 的層次結(jié)構(gòu)。

本文在二視圖場景下提出了一種改進(jìn)的二視圖RF 方法，在決策樹生成過程中采用CCA 方法融合視圖數(shù)據(jù)，將視圖間的信息交互融入到?jīng)Q策樹的全程構(gòu)建之中，逐層實現(xiàn)視圖間的互補(bǔ)信息在整個RF 生成過程中的利用。對比已有的TVRF，ITVRF 既全程融合了視圖間的互補(bǔ)信息，又利用了數(shù)據(jù)的判別信息，分類準(zhǔn)確率得到了顯著的提高。

ITVRF 是在決策樹構(gòu)建階段全程進(jìn)行視圖交互的一次成功嘗試，因為使用了CCA 型設(shè)計，僅適合二視圖場景，到多視圖的推廣需要另行設(shè)計，如將多集合CCA（multiset CCA）拓展到與本文相似的場景，或采用層次式兩兩判別CCA 設(shè)計，由于其中都涉及到非平凡的改造，將作為下一步的工作。