改進的二視圖隨機森林

夏笑秋，陳松燦,2+

1.南京航空航天大學 計算機科學與技術學院，南京210016

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

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

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

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

（1）如何在決策樹的構建階段逐層融合二視圖數據？

（2）如何將融合后的數據用于分類？

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

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

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

1 相關知識介紹

1.1 隨機森林

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

RF 的生成步驟如下：

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

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

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

（4）RF 的最終預測結果通過多數投票法得到。

1.2 典型相關分析

典型相關分析（CCA）是研究兩組變量相關關系的多元統計方法，在二視圖學習中，CCA 早已廣泛應用于特征提取和信息融合。

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

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

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

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

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

和串行組合

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

1.3 線性判別分析

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

假設有一組樣本集=[,,…,x]∈R，LDA的目標函數定義為：

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

LDA 的解為：

2 改進的二視圖隨機森林

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

2.1 融合視圖數據

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

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

2.2 構建二視圖決策樹

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

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

生成二視圖決策樹

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

輸出：二視圖決策樹。

2.3 構建二視圖隨機森林

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

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

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

3 實驗與結果分析

3.1 數據集

表1 UCI數據集統計信息Table 1 Statistics for UCI datasets

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

表2 機器人執行故障數據集Table 2 Robot execution failures dataset

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

3.2 實驗設計

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

表4 實驗仿真參數Table 4 Experimental simulation parameters

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

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

3.3 實驗結果比較

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

表5 AUC 值和運行時間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均在決策階段才利用到了視圖數據間的互補信息，而ITVRF 是在整個決策樹的生成過程中都進行了信息融合。對信息的充分利用是ITVRF 取得更優性能的關鍵。

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

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

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

3.4 參數分析

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

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

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

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

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

不同_下ITVRF 在部分手工分割二視圖數據集和真實數據集上的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 算法復雜度分析

ITVRF 的運行時間見表5。可以看出在樣本特征數較小時，TVRF 效率優于ITVRF。這是因為ITVRF 算法的步驟6 需要計算投影向量，時間復雜度為((+)3)，其中和分別表示兩個視圖的特征數。

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

可以看出，ITVRF 與現有的TVRF 實際應用成本相當。

4 總結與展望

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

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

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