塊增量典型相關分析

潘 玉，陳曉紅+，李舜酩，李紀永

1.南京航空航天大學 理學院，南京211106

2.南京航空航天大學 能源與動力學院，南京211106

3.四川航天中天動力裝備有限責任公司，成都610100

數據降維是高維數據的一種預處理技術，將樣本映射到低維空間，從而揭示數據的低維本質結構。常用的降維算法有主成分分析（principal component analysis，PCA）、線性判別分析（linear discriminant analysis，LDA）、偏最小二乘法（partial least square，PLS）、典型相關分析（canonical correlation analysis，CCA）等。這些方法需要將所有的訓練樣本全部加載到內存中后再進行特征提取，但是實際應用中常遇到數據流問題，訓練數據并不能一次性全部獲得，而是分期分批地到達。此時，原有的降維方法無法有效工作。

為了解決這個問題，有研究者提出了增量學習方法。增量學習是指每當新樣本加入時，不需要重新學習全部樣本，而是保留上一步學習過的舊知識，僅利用新增樣本引起的變化進行修正更新，從而構成連續的學習過程。例如，對傳統的主成分分析引入增量學習，得到增量主成分分析算法，許多研究小組提出了各種不同版本的改進算法，這些方法大致可分為兩類：第一類是無協方差增量主成分分析（candid covariance-free incremental principal component analysis，CCIPCA），CCIPCA 無需估計樣本協方差矩陣，而是根據數據流信息逐步計算樣本序列主成分，利用前-1 個樣本獲得的投影向量v與第個樣本的信息得到v，并運用特征向量彼此間的相互正交性找到前個特征向量，進而實現對數據的降維處理。第二類是增量主成分分析（incremental principal component analysis，IPCA），IPCA 通過殘差向量來判斷新增樣本是否能夠增加特征空間的維數，若新樣本包含特征空間的所有信息，則協方差矩陣保持不變；若新樣本在互補特征空間包含一定信息，則更新協方差矩陣。

進一步，Chu 等人將增量學習與線性判別分析相結合，提出了增量線性判別分析（incremental linear discriminant analysis，ILDA）算法。該算法中的類內散度矩陣和類間散度矩陣是根據數據的更新不斷調整，進而得出新的投影向量。Zeng 等人提出的增量偏最小二乘（incremental partial least squares,IPLS）改進了傳統的偏最小二乘算法，IPLS 分為在線和離線兩個階段：在線階段，利用新增樣本迭代更新主投影方向；離線階段，利用PLS的特征空間與克雷洛夫序列特征空間的等價性來計算其他投影方向。牟昭曦等人提出的增量典型相關分析（incremental canonical correlation analysis，ICCA）算法，利用第對樣本來迭代更新由前-1 對樣本所獲得的主投影向量，進而利用特征向量的正交性來估算其他投影向量。

由上述分析可見，每增加一個訓練樣本，增量式降維算法均需更新特征向量，當樣本數量龐大的時候，該方法的訓練時間過長。在實際應用中，數據流往往成批出現，這時候對數據進行批處理，不但減少了計算量，大大地節省系統的運行時間，而且更新投影向量同時使用多個樣本的信息，可提高算法的性能。Ozawa 等人基于IPCA 提出了塊增量主成分分析（chunk incremental principal component analysis，CIPCA），當新增一批樣本數據時，為了防止數據有效信息丟失，CIPCA 將殘差向量的累加比作為特征軸增加的衡量標準，進而更新協方差矩陣，計算新的投影向量。Pang等人基于ILDA 提出了塊增量線性判別分析（chunk incremental linear discriminant analysis，CILDA），用批處理的方式將新增數據融入類內散度矩陣和類間散度矩陣，進而更新投影向量。曾雪強等人則基于IPLS 提出了塊增量偏最小二乘算法（chunk incremental partial least squares，CIPLS），CIPLS將樣本劃分為多個塊，每次迭代均使用一塊樣本對算法進行更新，從而減少特征向量更新的次數，降低訓練時間，提高了算法的性能。

基于上述思想，本文對ICCA 算法進行改進，提出塊增量典型相關分析（chunk incremental canonical correlation analysis，CICCA），每次以批樣本為單位迭代更新投影向量，克服ICCA 使用單對樣本的局限性和耗時的缺點，提高了算法的學習效率，并在人工數據集和多個真實數據集上驗證CICCA 的有效性。

1 相關工作回顧

1.1 典型相關分析

其中，C與C分別表示與的協方差矩陣，C表示與的互協方差矩陣，基于尺度不變性，CCA可轉化為等式約束的優化問題：

利用拉格朗日乘子法，CCA 的求解可表示如下：

1.2 增量典型相關分析

給定樣本數據流=[,,…,x,x,…]，=[,,…,y,y,…]。當獲得第對樣本時，投影向量()的迭代公式為：

2 塊增量典型相關分析

2.1 主投影方向的計算

受塊增量學習的啟發，本文提出塊增量典型相關分析（CICCA）算法，其主要思想是將樣本劃分為多個塊，每個塊內的樣本數為，以每個數據塊為單位進行投影向量的迭代更新。CICCA 數據排列示意圖如圖1 所示。

圖1 CICCA 數據排列示意圖Fig.1 Data arrangement diagram of CICCA

將上式右側的()用(-1)代替，式（6）可寫為：

式（7）等號左側的求和運算只保留最后一項，將前-1 項移到等號右側，可得：

進而得到如下遞推公式：

將式（9）等號左側的()拆成(1-)()+()，等號兩邊同時乘以1/，移項可得：

把前-1 步的迭代信息加入式（10），即得：

當CICCA 數據塊所含樣本的個數為1 時，式（11）轉化為式（4），因此ICCA 是CICCA 的特例。

2.2 其他投影方向的計算

上述工作得到的主投影向量只能將高維數據降至一維，往往會導致數據信息丟失過多。為了盡可能多地保留數據信息，數據通常要降至多維。由于CCA 投影向量彼此之間具有正交性，因此可在投影向量的正交補空間中計算其他投影向量。首先回顧ICCA 其他投影向量的計算方法：

塊增量典型相關分析（CICCA）

2.3 算法對比

典型相關分析（CCA）、增量典型相關分析（ICCA）以及本文在這兩者基礎上提出的塊增量典型相關分析（CICCA），這三種均是多視圖降維算法。ICCA 和CICCA 是增量式算法，可以處理數據流問題，其中ICCA 將樣本一對對處理，每次只利用單對樣本迭代更新投影向量，且每新增一對樣本均需更新一次投影向量；而CICCA 將樣本一批批處理，每次利用一批樣本迭代更新投影向量，可以有效地縮短訓練時間，并且充分利用批樣本信息提高算法的性能。

另外，式（4）中ICCA 投影向量的迭代公式存在秩為2 的奇異矩陣，解決辦法是加入正則項；式（11）中CICCA 投影向量的迭代公式中需要求矩陣的逆，但當矩陣行滿秩時，矩陣是可逆的，因此一定程度上可以緩解矩陣不可逆帶來的負面影響。

2.4 算法復雜度

表1 算法的復雜度Table 1 Complexity of algorithm

3 實驗與分析

3.1 數據集的介紹

（1）人工數據集有X=[,]和Y=[,]兩個視圖，其中X、Y表示、視圖的第(=1,2)類樣本，每類有5 000 個樣本，具體參數見文獻[20]。

（2）Ads（http://archive.ics.uci.edu/ml/datasets/Internet+Advertments）數據集共收集5 個視圖的網頁數據(cap、alt、url、orig 和ancurl)，每個視圖有3 279 個樣本，均為0-1 的稀疏向量。

（3）WebKB（http://www.cs.cmu.edu/afs/cs/project/theo-11/www/wwkb）數據集包含1 051 個樣本的雙視圖網站數據，其中課程類網頁230 個樣本，非課程類網頁821 個樣本。

（4）MFD（http://archive.ics.uci.edu/ml/datasets/Multiple+Features）數據集將手寫數字提取不同的特征組成6 個視圖(fac、fou、kar、mor、pix 和zer)，每個視圖有2 000 個樣本。

3.2 實驗設置與結果分析

由表2 和表3 可知，在人工數據集和WebKB 數據集上，每種算法串行和并行兩種特征融合方式對分類的結果影響不大。由表4 可知，在Ads 數據集上，CICCA 在維數比較相近的視圖組合中，分類率會明顯提高，可達到93%以上。由表5 可知，在MFD 數據集上，三種算法串行組合的分類率要略優于并行組合，且串行組合分類率達到90%以上。但總體來說，CCA、ICCA 和CICCA 三種算法在每個數據集的分類性能相當。

表2 人工數據集的分類準確率（I）Table 2 Classification accuracy of synthetic dataset(I) %

表3 WebKB 的分類準確率（I）Table 3 Classification accuracy of WebKB(I) %

表4 Ads的分類準確率（I）Table 4 Classification accuracy of Ads(I) %

表5 MFD 的分類準確率（I）Table 5 Classification accuracy of MFD(I) %

對比表6～表9可知，總體上CCA、ICCA和CICCA的分類性能要優于CCIPCA，CICCA 在人工數據集上和視圖的分類率均可達92%；在WebKB 數據集上視圖的分類率為82%；在Ads 數據集上視圖的分類率高達89%；在MFD 數據集上兩種視圖的分類率均達89%以上。同時由表6 和表7 可知，CCA、ICCA 和CICCA 三種算法的分類率相差甚??；由表8和表9 可知，三種算法的平均分類準確率相差甚小，再次說明CCA、ICCA 和CICCA 的分類性能相當。

表6 人工數據集的分類準確率（II）Table 6 Classification accuracy of synthetic dataset(II) %

表7 WebKB 的分類準確率（II）Table 7 Classification accuracy of WebKB(II) %

表8 Ads的分類準確率（II）Table 8 Classification accuracy of Ads（II） %

綜合表2～表9 可知，在每個數據集上，CCA、ICCA 和CICCA 降維后視圖串行或并行融合的分類效果比直接進行分類好，進一步說明多視圖學習的性能優于單視圖學習。

表9 MFD 的分類準確率（II）Table 9 Classification accuracy of MFD(II) %

數據塊所含樣本個數是塊增量式降維模型的重要參數。該部分進一步測試數據塊所含樣本個數對CICCA 算法的性能影響，將設置為10、20、30 至100，繪制數據塊所含樣本個數對分類率的變化曲線以及數據塊所含樣本個數對時間的變化曲線。實驗以串行組合為例進行分類（下同），在Ads 數據集上，選取url 和orig 兩個視圖進行研究；在MFD 數據集上，選取fou 和kar 兩個視圖進行研究。由于不同數據集的計算時間差異比較大，為了更好地反映數據塊所含樣本個數對計算時間的影響，對數據集的計算時間進行了歸一化，實驗結果如圖2 和圖3 所示。

從圖2 可以看出，在Ads 和WebKB 數據集上，CICCA 分類率的上升和下降變化量不超過0.02；在MFD 數據集上，CICCA 分類率上升和下降的變化量不超過0.01。因此可以認為，CICCA 分類率幾乎不受數據塊所含樣本個數的影響。從圖3 可以看出，數據塊所含樣本個數越大，CICCA 的訓練時間就越短，的增大能夠減少特征向量的更新次數，從而進一步縮短訓練時間。隨著的增大，模型的訓練時間逐漸趨于平穩。同時的大小受數據環境和系統內存的限制，因此CICCA 算法需要權衡限制因素和算法性能，選取合適的值以獲得最高的時間效率。

圖2 數據塊所含樣本個數對分類率的影響Fig.2 Effect of sample number in chunk data on accuracy

圖3 數據塊所含樣本個數對時間的影響Fig.3 Effect of sample number in chunk data on time

對于許多降維算法，樣本數量是非常關鍵的參數。在給定數量的樣本下，比較CCA、ICCA 和CICCA 的分類率和訓練時間。實驗隨機抽取數據的10%、20%至100%，在抽取的數據中分別進行分類精度的實驗，具體實驗設置同3.2 節。在真實數據集上，分類率隨樣本數量變化的結果如圖4 所示，時間隨樣本數量變化的結果如圖5 所示。

圖4 樣本數量對分類率的影響Fig.4 Effect of sample number on accuracy

圖5 樣本數量對時間的影響Fig.5 Effect of sample number on time

從圖4 可以看出，CCA、ICCA 和CICCA 的分類率很大程度上受到樣本數量的影響。樣本數量的增大能夠提高算法的分類性能，但當樣本數量增大到一定程度后，分類性能基本保持穩定。從圖5 可以看出，在Ads 和WebKB 數據集上，CCA 和ICCA 的時間隨樣本數量增加呈指數變化；在MFD 數據集上，CCA和ICCA 算法的時間隨樣本數量增加呈線性變化；而CICCA 在三個數據集的用時最短且時間增長不明顯。因此，在上述真實數據集上表明，相比于CCA 和ICCA 算法，CICCA 算法用時最少，且樣本數量越多，優勢越明顯。

4 總結與展望

面對規模日益增長的海量數據問題，增量降維方法不僅可以處理維度高的數據，還可以處理個數龐大的數據，是一種適用于大規模數據流的技術。因此，本文以數據降維為背景，結合塊增量學習的思想提出了塊增量典型相關分析（CICCA）算法。CICCA可以有效地降低模型的訓練時間，并充分利用批樣本豐富的信息，提高算法的性能。經過比較分析，未來的研究方向可以從以下兩個方面進行：（1）非線性化。利用數據在低維空間線性不可分轉化為高維空間線性可分的思想，提出塊增量核典型相關分析算法。（2）不完全配對學習。CCA、ICCA、CICCA 算法要求每個視圖的數據是完全配對的，而在一般分類中，數據多數是不完全配對的，因此可對不完全配對多視圖數據進行分析研究，提出不完全配對塊增量典型相關分析算法。