一種基于多圖的集成直推分類方法

余國先 張國基 韋 佳 任亞洲

①(華南理工大學計算機科學與工程學院 廣州 510006)

②(華南理工大學理學院 廣州 510640)

1 引言

隨著信息技術的發展，積累的數據與日俱增，如網絡文本和圖像等。這些數據通常只有少量類別屬性已知，并具有很高的維度。高的維度意味著分類器需要更多的訓練樣本來獲得一個理想的分類器，而僅利用稀少的有標記樣本并不能保證分類器具有好的泛化性能。半監督學習[1]通過平衡利用有標記樣本和無標記樣本獲取一個性能較好的學習器，受到越來越多的關注?；趫D的直推分類[1]是半監督學習的一個重要分支，它把所有參與訓練的樣本(包括有標記和無標記樣本)均作為圖上的頂點，并利用圖上的邊權重描述樣本之間的相似度信息，再在圖上利用有標記樣本預測這些無標記樣本。如高斯隨機場與和諧函數(GFHF)[2]，局部與全局一致性學習(LGC)[3]，線性鄰域標簽傳播(LNP)[4]，魯棒多類直推方法(RMGT)[5]等都是具有代表性的直推分類器。大部分基于圖的直推分類方法都可以看作是有標記樣本的標簽信息在圖上的傳播過程[1]，定義一個結構良好的圖是決定這些方法有效性的關鍵[1,4?6]。由于高維數據通常包含噪聲和冗余特征，常用的距離度量(如歐氏距離，余弦距離等)并不能很好地描述這類數據之間的近鄰結構信息[7]，直推分類器性能因此下降。GFHF, LGC和LNP等在低維數據上均可獲得較高的分類正確率，但在高維數據上的分類效果并不顯著。因而，很有必要在低的維度上構造圖再進行直推分類。

集成學習可以推進半監督學習器的性能[8]。本文先期實驗表明，類似決策森林方法[9]，在隨機子空間上訓練多個直推分類器，再通過投票獲得的集成分類器性能并不顯著，因為這些隨機子空間上基礎分類器的準確率較低?；A分類器的準確率和它們之間的差異性是決定集成分類器性能的兩個重要指標[10]，高準確率要求基礎分類器在預測樣本時一致性較高，而差異性意味著基礎分類器對同一樣本的分類結果不一致。構造既有較高準確率也有較高差異性的基礎分類器是提高集成分類器性能的關鍵[10]。鑒于此，本文提出一種基于多圖的集成直推分類方法(Multi Graphs based Transductive Ensemble Classification, MGTEC)。MGTEC首先生成多個隨機子空間，其次在子空間上進行半監督判別分析空間(SDA)[11]，再在每個判別的子空間上構造一個近鄰圖并訓練一個直推分類器，最后投票融合這些分類器。在人臉圖像上的實驗表明，MGTEC的基礎分類器具有較高的精度和差異度；對比其它直推分類方法，MGTEC不僅表現出更好的分類效果，對參數的選取也較魯棒。MGTEC的多圖構建策略非常顯式直觀，可直接應用到其他基于圖的半監督學習算法中。

2 拉普拉斯譜圖

基于圖的直推分類方法如 GFHF, LGC, LNP等和基于圖的譜嵌入如 SDA, LPP[12], MFA[13]等都同Laplace譜圖有著緊密的聯系。令X={x1,x2,… ,其中前l個樣本的標簽已知，其余u個未知，D為樣本維度。圖Laplace矩陣[12]定義如下：

其中D為對角矩陣，定義如下：

W通常定義為簡單的0-1相似度：

或高斯熱核相似度[12]：

其中xi∈kNN(xj)表示xi是xj的k個最近鄰之一，d(xi,xj)為某種距離度量，如歐幾里得距離，馬氏距離等，σ為高斯熱核寬度。

從式(1)-式(4)可以看出，L和W最終都依賴于k近鄰圖結構。然而隨著樣本維數的增多，常用的距離度量并不能反映樣本之間的近鄰結構信息[7]，定義的近鄰圖不足以刻畫樣本的分布信息，基于圖的譜嵌入和直推分類器的性能因此下降。

3 基于多圖的集成直推分類

基于多圖的集成直推分類分為兩步：基于隨機子空間的半監督判別分析(Random Subspace based Semi-supervised Discriminate Analysis, RSSDA)和MGTEC。

3.1 RSSDA

SDA通過在k近鄰圖上定義一個Laplace矩陣L來描述樣本之間的流形結構信息，再結合線性判別分析(LDA)[14]獲得一個C?1維的判別子空間，其中C為樣本類別數。如同絕大多數基于圖的降維方法，該方法的有效性也依賴于定義一個結構良好的近鄰圖[13]。由于高維數據通常包含噪聲和大量冗余特征，定義一個結構良好的近鄰圖比較困難。為此，本文在低維的隨機子空間上構造圖，進而提出RSSDA, RSSDA具體流程如表1所示。

表1 RSSDA算法

不同于 SDA, RSSDA目標方程中的tL在隨機子空間上構造，隨機子空間的大小p遠小于D，它較少受噪聲和冗余特征的影響，定義的近鄰圖能較好地反映子空間的分布信息。RSSDA的廣義特征向量在隨機子空間上求解，其時間復雜度為O(p3)，而SDA在原始空間上求解，其時間復雜度為O(D3)。為改善圖嵌入結果，LGSSDR[15]定義一個獎勵圖和一個懲罰圖，再在圖上構造 Laplace矩陣進行基于圖的半監督降維。EGGLE[16]利用測地線距離和廣義高斯函數構造多個圖，再在每個圖上進行譜嵌入，最后在這些嵌入結果上集成分類。SSDA[17]利用流形距離來刻畫樣本之間的距離，再進行半監督判別分析。這3種方法都是基于原始空間上的近鄰圖進行優化，此時近鄰圖易受冗余和噪聲特征的影響，并不能保證得到優化的圖，另外，特征向量求解的時間復雜度均為O(D3)。

3.2 MGTEC

基于圖的直推分類方法依賴于圖結構。盡管LGC, GFHF和LNP擁有不同的優化目標方程，但是它們的有效性更多依賴于近鄰圖及其上定義的邊權重[1,4?6]。實驗表明，類似決策森林[9]的方法構造的集成直推分類器精度并不高。通過在 RSSDA的判別子空間上訓練的基礎直推分類器不僅具有較高的精度，由于判別子空間之間的差異性，這些基礎分類器之間還具有一定的差異性，從而保證了MGTEC具有更高的精度。下文以GFHF為例，論述如何在判別子空間上訓練基礎直推分類器并通過投票策略集成它們。GFHF的目標方程如下[2]：

其中yi為第i(1≤i≤l)個樣本的已知標簽，fj為第j個樣本的預測標簽，Wij的定義同式(4)。令其中fl為l個有標記樣本的標簽值，fu為GFHF在u個未標記樣本上的預測標簽值。根據文獻[2]，

其中

D為對角矩陣，其分塊同W一樣。從式(10)可以看出fu也依賴于一個有效的相似性度量W。在RSSDA的基礎上，本文提出MGTEC，其流程如表2所示。

通過在判別分析后的子空間上構建圖，再在圖上訓練直推分類器，可有效降低噪聲和冗余特征對分類器的影響。另外，由于這些判別的子空間具有較好的區分能力和差異性，因而易于在這些子空間上獲得具有高準確率和較好差異性的基礎分類器，這正是MGTEC的有效性的基礎。事實上，MGTEC可以看做是降維和直推分類結合的一種混合方法。本文中的 SDA也可以用其它的降維方法代替，如LGSSDR；同樣，式(14)也可以采用LGC, LNP等方法的目標方程替換。LapRLSC[18]在核主成分分析(KPCA)后的低維嵌入上定義一個近鄰圖，再在近鄰圖上定義一個 Laplace矩陣，并把它作為一個正則項引入到半監督分類中，但該方法需要選擇合適的核寬度和主成分個數。RASCO[19]通過在隨機子空間上訓練協同訓練所需的子分類器再集成分類，但它對子空間的依耐性較高且子分類器的精度也較低?；谧涌臻g的集成方法也被應用到人臉識別中，Semi-RS[10]首先把人臉圖像分割為多個子模塊，其次在這些子模塊上進行主成分分析(PCA)[14]，再在這些PCA子空間上產生多個隨機子空間，最后在這些子空間上訓練分類器進行投票集成，但它需要選擇合適的子模塊大小和較多的基礎分類器。RLDA[20]先把圖像投影到N?1維(N為樣本數量)的PCA子空間，再選取前N0個最大主成分對應的特征，再從剩余的N?N0?1個特征中多次隨機選擇N1個特征，構成大小為N0+N1的子空間，最后在這些子空間上訓練LDA分類器并集成，但它較難選擇合適的N0和N1。不同于 Semi-RS和 RLDA, MGTEC不需PCA進行預處理，而且比較易于選擇合適大小的隨機子空間和核寬度。

4 實驗及分析

本節通過在兩個標準人臉數據集上的分類實驗來驗證 MGTEC的有效性。參與比對的算法有GFHF, LGC, LNP, RMGT, SDAGFHF(先在原始空間上 SDA，再在判別子空間上訓練 GFHF)和RSGFHF(先在每個隨機子空間上訓練一個基礎分類器GFHF，再通過投票集成它們)，前5個比對算法都是在單圖上的直推分類，最后1個對比算法也是基于多圖的集成直推分類。RSGFHF與MGTEC的主要區別是MGTEC在經過判別分析后的子空間上訓練基礎分類器，而RSGFHF則在隨機子空間上訓練基礎分類器。實驗采用的兩個數據集為 AR[21]和擴展的yaleB[22]。在AR的實驗中，共選取2600張(50名男性，50名女性)圖像作為實驗數據集，其中每個實例26張圖像，在實驗前，先對這些圖像進行配準，再剪裁到大小為 42×30的灰度圖像。在yaleB的實驗中，選擇其正面圖像子集，共計2414張，共 38個實例，并配準再剪裁到大小為 32×32的灰度圖像。為了便于分析，做如下符號約定，Lp:每類有標記樣本數量，C:樣本的類別數，D:樣本的原始維度，p: 隨機子空間大小，EnsK: 隨機子空間的個數，N:訓練樣本數量，k:近鄰大小。實驗中，式(8)中參數α,β均取0.1,σ取為訓練樣本間歐幾里得距離的均值，k取為5。算法的評價指標為算法在測試樣本上的分類正確率，測試樣本為訓練樣本中的未知標記樣本。為避免隨機性，報告的實驗結果為20次獨立運行結果的平均值。

4.1 不同數量標記樣本下的分類性能

為了分析算法在不同數量有標記樣本下的分類精度，本文分別在AR和yaleB上執行實驗。在這兩個實驗中，EnsK為20,p為類別數的2倍。圖1和圖2給出了各比對算法在不同Lp下的分類精度變化情況。

圖1 AR上不同Lp下的分類準確率

圖2 yaleB上不同Lp下的分類準確率

從圖1和圖2可以看出，相對于其他算法，MGTEC通常可以獲得更高的分類正確率。這是由于MGTEC在判別嵌入的子空間上構造的圖較少受噪聲和冗余特征的影響，從而更好的描述了子空間的分布信息。SDAGFHF獲得了僅次于MGTEC的性能，這說明有效的降維可以提高分類器的性能。LNP通過利用線性鄰域傳播來優化近鄰圖邊權重，獲得了比GFHF, LGC更高的精度，這說明對圖進行優化可以提高直推分類器的精度。RMGT利用非參數學習方法改進近鄰圖邊權重，但它沒有利用同類樣本之間的相似度信息，在迭代優化過程中需要較多的矩陣運算損失了運算精度，分類正確率因此下降，在yaleB上甚至低于GFHF和LGC。RSGFHF在Lp增加時分類精度不斷提高，但其精度低于SDAGFHF和MGTEC，同GFHF也沒有顯著的區別，這正好驗證了在隨機子空間上訓練多個分類器再集成，并不能保證得到一個準確率較高的集成分類器，而在判別嵌入的子空間上訓練基礎分類器，可以得到一個準確率較高的集成分類器(LGC作為基礎分類器也有同樣結論，限于篇幅沒有報告)。

4.2 參數敏感性分析

本節通過在AR上進行實驗來分析MGTEC的參數敏感性。在實驗中，如未作特別說明，Lp設置為10,p=2C, EnsK為20。

實驗1 高斯熱核相似度對熱核寬度σ較敏感，為了研究各種算法在不同σ時的性能，在AR上執行一個實驗。在實驗中，σ的取值為1, 10, 100, 1000,10000, 100000, 1000000, 10000000, 100000000，對應的實驗結果如圖3。

圖3 不同σ下的分類正確率

從圖3可以看出，依賴于高斯熱核相似度的直推分類方法，都需要選擇一個合適的σ。LNP不需要設定σ，故沒有報告其結果。當σ過小時，所有的Wij趨近或等于0，此時的σ一般不選取。無論選擇哪個指標下的σ, LGC, GFHF均沒有獲得顯著的分類性能，而MGTEC可以在絕大多數指標下保持穩定，這說明MGTEC對參數選取的魯棒性比這些對比方法要好。SDAGFHF由于運用了判別分析，獲得的性能也較穩定，這說明降維不僅可以提高分類正確率，在一定程度上還可以穩定分類器性能。

實驗 2 基于隨機子空間的集成分類方法對p依賴性較高。為了分析不同的p對MGTEC的影響，本文在AR上執行一個實驗。在本實驗中，p從20增大到 300，圖4為不同p時分類器的性能變化情況。

圖4 不同p下的分類正確率

從圖4可以看出，無論何種p下，RSGFHF的性能都沒有大的變化，這說明通過直接在隨機子空間上訓練基于圖的直推分類并不能保證獲得一個穩定且性能較好的分類器。由于SDA的判別子空間大小為C?1，因而通常p≥C。當p≥2C時，MGTEC,RSGFHF的性能均有所下降，原因是隨著p的增大，噪聲和冗余特征也隨之增多。在2C≥p≥C時，MGTEC均表現出較高和穩定的正確率，這表明MGTEC可在一定的原則下選擇合適的p，可選擇的p也較多。

實驗3 基礎分類器的個數(此處等同于EnsK)影響著基于隨機子空間的集成分類器性能。為此本文繼續在AR上執行一個實驗，在實驗中，EnsK從1增加到50，圖5為不同EnsK時的分類結果。

圖5 不同EnsK下的分類正確率

從圖5可以看出，盡管RSGFHF的基礎分類器不斷增多，但其性能并沒有顯著變化，而MGTEC可以在較少的基礎分類器時達到較高且穩定的精度。在只有1個基礎分類器時，MGTEC的分類器精度可以達到0.8，而RSGFHF接近0.3，這說明在隨機子空間上訓練的分類器精度并不高，通過投票得到的集成分類器性能也不顯著。本實驗還表明基礎分類器的精度對集成分類器的精度起著關鍵作用，僅增加基礎分類器的個數并不能很好的提高集成分類器的性能。

實驗4 為了證明MGTEC的基礎分類器不僅具有較高的精度還有較好的差異度。圖6給出了MGTEC和RSGFHF的20個基礎分類器各自的分類正確率及其集成后的分類正確率。

圖6 基礎分類器及其集成后的分類正確率

圖6中 RSGFHF(I)和 MGTEC(I)分別為RSGFHF和MGTEC的基礎分類器。從圖6可以發現，通過投票策略獲得的集成分類器均獲得了較基礎分類器更好的性能，這不僅表明基于投票的集成策略是有效的，而且說明這些基礎分類器之間具有較大的差異性。由于隨機子空間較少受噪聲和冗余特征的影響，通過SDA獲得的判別子空間能把在子空間中的不同類樣本區分開來，從而使得在這些子空間上訓練的基礎分類器擁有較高的精度。同時，隨機子空間之間的差異性在判別分析后得以保留，使得判別子空間上的分類器之間也具有較大的差異性。因此，MGTEC具有比 RSGFHF更好的分類性能。

5 結論

針對在高維數據上構造的圖易受噪聲和冗余特征影響，而基于圖的直推分類器的性能依賴于圖結構的難題，本文提出一種基于多圖的集成直推分類方法MGTEC。MGTEC首先在隨機子空間上進行半監督判別分析，再在這些判別嵌入后的子空間上訓練基礎分類器，最后通過投票策略集成這些分類器。實驗表明，通過這種方式構造的基礎分類器具有較高的精度，它們之間還有較好的差異性，獲得的集成分類器具有更高的精度，對參數的選取也較魯棒。本文提出的多圖構建策略直觀，可應用到絕大多數基于圖的半監督學習方法中。

[1] Zhu X J. Semi-supervised learning literature [R]. Technical Report 1530, Department of Computer Sciences, University of Wisconsin-Madison, 2008.

[2] Zhu X J, Ghahramani Z, and Lafferty J. Semi-supervised learning using Gaussian fields and harmonic functions [C].Proceedings of the 20th International Conference on Machine Learning (ICML), Washington, DC, USA, 2003: 912-919.

[3] Zhou D Y, Bousquet O, Lal T N,et al.. Learning with local and global consistency [C]. Advances in Neural Information Processing Systems (NIPS), Vancouver and Whistler, British Columbia, Canada, 2003: 257-264.

[4] Wang J D, Wang F, Zhang C S,et al.. Linear neighborhood propagation and its applications [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(9):1600-1615.

[5] Liu W and Chang S F. Robust multi-class transductive learning with graphs [C]. Proceedings of IEEE 22th Computer Vision and Pattern Recognition (CVPR), Miami,Florida, USA, 2009: 381-388.

[6] Jebara T, Wang J, and Chang S F. Graph construction and b-matching for semi-supervised learning [C]. Proceedings of the 26th International Conference on Machine Learning(ICML), Montreal, Quebec, Canada, 2009: 441-448.

[7] Parsons L, Haque E, and Liu H. Subspace clustering for high dimensional data: a review [J].ACM SIGKDD Explorations Newsletter, 2004, 6(1): 90-105.

[8] Zhou Z H. When semi-supervised learning meets ensemble learning [C]. Proceedings of 8th International Workshop on Multiple Classifier System (MCS), Reykjavik, Iceland, 2009:529-538.

[9] Ho T K. The random subspace method for constructing decision forests [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(8): 832-844.

[10] Zhu Y L, Liu J, and Chen S C. Semi-random subspace method for face recognition [J].Image and Vision Computing,2009, 27(9): 1358-1370.

[11] Cai D, He X F, and Han J W. Semi-supervised discriminate analysis [C]. Proceedings of IEEE 11th International Conference on Computer Vision (ICCV), Rio de Janeiro,Brazil, 2007: 1-7.

[12] He X F and Niyogi P. Locality preserving projections [C].Advances in Neural Information Processing Systems (NIPS),Vancouver and Whistler, British Columbia, Canada, 2003:153-160.

[13] Yan S C, Xu D, Zhang B Y,et al.. Graph embedding and extensions: a general framework for dimensionality reduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(1): 40-51.

[14] Martinez A M and Kak A. PCA versus LDA [J].IEEETransactions on Pattern Analysis and Machine Intelligence,2002, 23(2): 228-233.

[15] 韋佳, 彭宏. 一種基于局部與全局保持的半監督維數約減方法[J]. 軟件學報, 2008, 19(11): 2833-2842.Wei Jia and Peng Hong. Local and global preserving based semi-supervised dimensionality reduction method [J].Journal of Software, 2008, 19(11): 2833-2842.

[16] 曾憲華, 羅四維, 王嬌, 等. 基于測地線距離的廣義高斯型Laplacian特征映射[J]. 軟件學報, 2009, 20(4): 815-824.Zeng Xian-hua, Luo Si-wei, Wang Jiao,et al.. Geodesic distance-based generalized Gaussian laplacian eigenmap[J].Journal of Software, 2009, 20(4): 815-824.

[17] 魏萊, 王守覺. 基于流形距離的半監督判別分析[J]. 軟件學報,2010, 21(10): 2445-2453.Wei Lai and Wang Shou-jue. Semi-supervised discriminate analysis based on manifold distance [J].Journal of Software,2010, 21(10): 2445-2453.

[18] 張向榮, 陽春, 焦李成. 基于 Laplacian 正則化最小二乘的半監督SAR目標識別[J]. 軟件學報, 2010, 21(4): 586-596.Zhang Xiang-rong, Yang Chun, and Jiao Li-cheng. Semisupervised SAR target recognition based on laplacian regularized least squares classification [J].Journal of Software,2010, 21(4): 586-596.

[19] 王嬌, 羅四維, 曾憲華. 基于隨機子空間的半監督協同訓練算法[J]. 電子學報, 2008, 36(12A): 60-65.Wang Jiao, Luo Si-wei, and Zeng Xian-hua. A random subspace method for co-training [J].Acta Electronic Sinica,2008, 36(12A): 60-65.

[20] Wang X G and Tang X O. Random sampling for subspace face recognition [J].International Journal of Computer Vision, 2006, 70(1): 91-104.

[21] Martinez M and Benavente R. The AR face database [R].CVC Technical Report 24, 1998.

[22] Georghiades S, Belhumeur P N, and Kriegman D J. From few to many: illumination cone models for face recognition under variable lighting and pose [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(6): 643-660.