潘 玉，陳曉紅+，李舜酩，李紀(jì)永

1.南京航空航天大學(xué) 理學(xué)院，南京211106

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

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

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

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

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

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

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

1 相關(guān)工作回顧

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

其中，C與C分別表示與的協(xié)方差矩陣，C表示與的互協(xié)方差矩陣，基于尺度不變性，CCA可轉(zhuǎn)化為等式約束的優(yōu)化問題：

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

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

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

2 塊增量典型相關(guān)分析

2.1 主投影方向的計算

受塊增量學(xué)習(xí)的啟發(fā)，本文提出塊增量典型相關(guān)分析（CICCA）算法，其主要思想是將樣本劃分為多個塊，每個塊內(nèi)的樣本數(shù)為，以每個數(shù)據(jù)塊為單位進(jìn)行投影向量的迭代更新。CICCA 數(shù)據(jù)排列示意圖如圖1 所示。

圖1 CICCA 數(shù)據(jù)排列示意圖Fig.1 Data arrangement diagram of CICCA

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

式（7）等號左側(cè)的求和運(yùn)算只保留最后一項(xiàng)，將前-1 項(xiàng)移到等號右側(cè)，可得：

進(jìn)而得到如下遞推公式：

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

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

當(dāng)CICCA 數(shù)據(jù)塊所含樣本的個數(shù)為1 時，式（11）轉(zhuǎn)化為式（4），因此ICCA 是CICCA 的特例。

2.2 其他投影方向的計算

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

塊增量典型相關(guān)分析（CICCA）

2.3 算法對比

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

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

2.4 算法復(fù)雜度

表1 算法的復(fù)雜度Table 1 Complexity of algorithm

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集的介紹

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

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

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

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

3.2 實(shí)驗(yàn)設(shè)置與結(jié)果分析

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

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

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

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

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

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

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

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

表8 Ads的分類準(zhǔn)確率（II）Table 8 Classification accuracy of Ads（II） %

綜合表2～表9 可知，在每個數(shù)據(jù)集上，CCA、ICCA 和CICCA 降維后視圖串行或并行融合的分類效果比直接進(jìn)行分類好，進(jìn)一步說明多視圖學(xué)習(xí)的性能優(yōu)于單視圖學(xué)習(xí)。

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

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

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

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

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

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

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

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

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

4 總結(jié)與展望

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