典型關(guān)聯(lián)分析(CCA)原理總結(jié)（轉(zhuǎn)自劉建平Pinard）

典型關(guān)聯(lián)分析(Canonical Correlation Analysis，以下簡(jiǎn)稱CCA)是最常用的挖掘數(shù)據(jù)關(guān)聯(lián)關(guān)系的算法之一。比如我們拿到兩組數(shù)據(jù)，第一組是人身高和體重的數(shù)據(jù)，第二組是對(duì)應(yīng)的跑步能力和跳遠(yuǎn)能力的數(shù)據(jù)。那么我們能不能說(shuō)這兩組數(shù)據(jù)是相關(guān)的呢？CCA可以幫助我們分析這個(gè)問(wèn)題。

1. CCA概述

在數(shù)理統(tǒng)計(jì)里面，我們都知道相關(guān)系數(shù)這個(gè)概念。假設(shè)有兩組一維的數(shù)據(jù)集X和Y，則相關(guān)系數(shù)ρ的定義為:

其中cov(X,Y)是X和Y的協(xié)方差，而D(X),D(Y)分別是X和Y的方差。相關(guān)系數(shù)ρ的取值為[-1,1],ρ的絕對(duì)值越接近于1，則X和Y的線性相關(guān)性越高。越接近于0，則X和Y的線性相關(guān)性越低。

雖然相關(guān)系數(shù)可以很好的幫我們分析一維數(shù)據(jù)的相關(guān)性，但是對(duì)于高維數(shù)據(jù)就不能直接使用了。拿上面我們提到的，如果X是包括人身高和體重兩個(gè)維度的數(shù)據(jù)，而Y是包括跑步能力和跳遠(yuǎn)能力兩個(gè)維度的數(shù)據(jù)，就不能直接使用相關(guān)系數(shù)的方法。那我們能不能變通一下呢？CCA給了我們變通的方法。

CCA使用的方法是將多維的X和Y都用線性變換為1維的X'和Y'，然后再使用相關(guān)系數(shù)來(lái)看X'和Y'的相關(guān)性。將數(shù)據(jù)從多維變到1位，也可以理解為CCA是在進(jìn)行降維，將高維數(shù)據(jù)降到1維，然后再用相關(guān)系數(shù)進(jìn)行相關(guān)性的分析。下面我們看看CCA的算法思想。

2. CCA的算法思想

上面我們提到CCA是將高維的兩組數(shù)據(jù)分別降維到1維，然后用相關(guān)系數(shù)分析相關(guān)性。但是有一個(gè)問(wèn)題是，降維的標(biāo)準(zhǔn)是如何選擇的呢？回想下主成分分析PCA，降維的原則是投影方差最大；再回想下線性判別分析LDA，降維的原則是同類的投影方差小，異類間的投影方差大。對(duì)于我們的CCA，它選擇的投影標(biāo)準(zhǔn)是降維到1維后，兩組數(shù)據(jù)的相關(guān)系數(shù)最大。

現(xiàn)在我們具體來(lái)討論下CCA的算法思想。假設(shè)我們的數(shù)據(jù)集是X和Y，X為n1×m的樣本矩陣。Y為n2×m的樣本矩陣.其中m為樣本個(gè)數(shù)，而n1,n2分別為X和Y的特征維度。

對(duì)于X矩陣，我們將其投影到1維，或者說(shuō)進(jìn)行線性表示，對(duì)應(yīng)的投影向量或者說(shuō)線性系數(shù)向量為a, 對(duì)于Y矩陣，我們將其投影到1維，或者說(shuō)進(jìn)行線性表示，對(duì)應(yīng)的投影向量或者說(shuō)線性系數(shù)向量為b, 這樣X ,Y投影后得到的一維向量分別為X',Y'。我們有

我們CCA的優(yōu)化目標(biāo)是最大化ρ(X′,Y′)得到對(duì)應(yīng)的投影向量a,b，即

在投影前，我們一般會(huì)把原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，得到均值為0而方差為1的數(shù)據(jù)X和Y。這樣我們有：

E是期望，D(X)=cov(X,X)。
由于我們的X，Y的均值均為0，則

令S_{XY} =cov(X,Y)，則優(yōu)化目標(biāo)可以轉(zhuǎn)化為：

由于分子分母增大相同的倍數(shù)，優(yōu)化目標(biāo)結(jié)果不變，我們可以采用和SVM類似的優(yōu)化方法，固定分母，優(yōu)化分子，具體的轉(zhuǎn)化為：

也就是說(shuō)，我們的CCA算法的目標(biāo)最終轉(zhuǎn)化為一個(gè)凸優(yōu)化過(guò)程，只要我們求出了這個(gè)優(yōu)化目標(biāo)的最大值，就是我們前面提到的多維X和Y的相關(guān)性度量，而對(duì)應(yīng)的a,b則為降維時(shí)的投影向量，或者說(shuō)線性系數(shù)。

這個(gè)函數(shù)優(yōu)化一般有兩種方法，第一種是奇異值分解SVD，第二種是特征分解，兩者得到的結(jié)果一樣，下面我們分別講解。

3. CCA算法的SVD求解

對(duì)于上面的優(yōu)化目標(biāo)，我們可以做一次矩陣標(biāo)準(zhǔn)化，就可以用SVD來(lái)求解了。
首先，我們令a=S_{XX}^{-1/2}u, b=S_{YY}^{-1/2}v,這樣我們有：

a^TS_{XX}a =1 \Rightarrow u^TS_{XX}^{-1/2}S_{XX}S_{XX}^{-1/2}u =1 \Rightarrow u^Tu=1
b^TS_{YY}b =1 \Rightarrow v^TS_{YY}^{-1/2}S_{YY}S_{YY}^{-1/2}v=1 \Rightarrow v^Tv=1
a^TS_{XY}b = u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v

也就是說(shuō)，我們的優(yōu)化目標(biāo)變成下式：
\underbrace{arg\;max}_{u,v}u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v
s.t. u^Tu =1,\; v^Tv =1

仔細(xì)一看，如果將u和v看做矩陣M=S_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}的某一個(gè)奇異值對(duì)應(yīng)的左右奇異向量。那么利用奇異值分解，我們可以得到M=U\Sigma V^T,其中U,V分別為M的左奇異向量和右奇異向量組成的矩陣，而Σ為M的奇異值組成的對(duì)角矩陣。由于U,V所有的列都為標(biāo)準(zhǔn)正交基，則u^TU和V^Tv得到一個(gè)只有一個(gè)標(biāo)量值為1，其余標(biāo)量值為0的向量。此時(shí)我們有
u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v = u^TU\Sigma V^Tv = \sigma_{uv}

也就是說(shuō)我們最大化u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v,其實(shí)對(duì)應(yīng)的最大值就是某一組左右奇異向量所對(duì)應(yīng)的奇異值的最大值。也就是將M做了奇異值分解后，最大的奇異值就是我們優(yōu)化目標(biāo)的最大值，或者說(shuō)我們的X和Y之間的最大相關(guān)系數(shù)。利用對(duì)應(yīng)的左右奇異向量u,v我們也可以求出我們?cè)嫉腦和Y的線性系數(shù)a=S_{XX}^{-1/2}u, b=S_{YY}^{-1/2}v。

可以看出，SVD的求解方式非常簡(jiǎn)潔方便。但是如果你不熟悉SVD的話，我們也可以用傳統(tǒng)的拉格朗日函數(shù)加上特征分解來(lái)完成這個(gè)函數(shù)的優(yōu)化。

4. CCA算法的特征分解求解

特征分解方式就比較傳統(tǒng)了，利用拉格朗日函數(shù)，優(yōu)化目標(biāo)轉(zhuǎn)化為最大化下式：
J(a,b) = a^TS_{XY}b -\frac{\lambda}{2}(a^TS_{XX}a-1)-\frac{\theta}{2}(b^TS_{YY}b-1)

分別對(duì)a,b求導(dǎo)并令結(jié)果為0，我們得到：

S_{XY}b-\lambda S_{XX}a=0
S_{YX}a-\theta S_{YY}b=0

將上面第一個(gè)式子左乘a^T,第二個(gè)式子左乘b^T，并利用a^TS_{XX}a =1,\; b^TS_{YY}b =1我們得到

\lambda = \theta = a^TS_{XY}b

其實(shí)也就是說(shuō)我們的拉格朗日系數(shù)就是我們要優(yōu)化的目標(biāo)。我們繼續(xù)將上面的兩個(gè)式子做整理，第一個(gè)式子左乘S_{XX}^{-1},第二個(gè)式子左乘S_{YY}^{-1}我們得到

S_{XX}^{-1}S_{XY}b=\lambda a
S_{YY}^{-1}S_{YX}a = \lambda b

將上面第二個(gè)式子帶入第一個(gè)式子，我們得到

S_{XX}^{-1}S_{XY}S_{YY}^{-1}S_{YX}a=\lambda^2a
這個(gè)式子我們就熟悉了，這不就是特征分解嗎！要求最大的相關(guān)系數(shù)λ,我們只需要對(duì)矩陣N=S_{XX}^{-1}S_{XY}S_{YY}^{-1}S_{YX}做特征分解，找出最大的特征值取平方根即可，此時(shí)最大特征值對(duì)應(yīng)的特征向量即為X的線性系數(shù)a。

同樣的辦法，我們將上面第一個(gè)式子帶入第二個(gè)式子，我們得到

S_{YY}^{-1}S_{YX}S_{XX}^{-1}S_{XY}b=\lambda^2b

我們只需要對(duì)矩陣N’=S_{YY}^{-1}S_{YX}S_{XX}^{-1}S_{XY}做特征分解，找出最大的特征值取平方根即可，此時(shí)最大特征值對(duì)應(yīng)的特征向量即為Y的線性系數(shù)b。

可以看出特征分解的方法要比SVD復(fù)雜，但是兩者求得的結(jié)果其實(shí)是等價(jià)的，只要利用SVD和特征分解之間的關(guān)系就很容易發(fā)現(xiàn)兩者最后的結(jié)果相同。

5. CCA算法流程

這里我們對(duì)CCA的算法流程做一個(gè)總結(jié)，以SVD方法為準(zhǔn)。

輸入：各為m個(gè)的樣本X和Y，X和Y的維度都大于1

輸出：X,Y的相關(guān)系數(shù)ρ,X和Y的線性系數(shù)向量a和b

1）計(jì)算X的方差S_{XX}，Y的方差S_{YY}，X和Y的協(xié)方差S_{XY}, Y和X的協(xié)方差S_{YX}=S_{XY}^T

  1. 計(jì)算矩陣M=S_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}

3）對(duì)矩陣M進(jìn)行奇異值分解，得到最大的奇異值ρ，和最大奇異值對(duì)應(yīng)的左右奇異向量u,v

  1. 計(jì)算X和Y的線性系數(shù)向量a和b,a=S_{XX}^{-1/2}u, b=S_{YY}^{-1/2}v

6. CCA算法小結(jié)

CCA算法廣泛的應(yīng)用于數(shù)據(jù)相關(guān)度的分析，同時(shí)還是偏最小二乘法的基礎(chǔ)。但是由于它依賴于數(shù)據(jù)的線性表示，當(dāng)我們的數(shù)據(jù)無(wú)法線性表示時(shí)，CCA就無(wú)法使用，此時(shí)我們可以利用核函數(shù)的思想，將數(shù)據(jù)映射到高維后，再利用CCA的思想降維到1維，求對(duì)應(yīng)的相關(guān)系數(shù)和線性關(guān)系，這個(gè)算法一般稱為KCCA。

但是選用核方法也有其自身的問(wèn)題，主要在于核選取的不可知性，還有計(jì)算量比較大。此時(shí)我們可以利用神經(jīng)網(wǎng)絡(luò)解決非線性問(wèn)題。Deep CCA就是先用深度神經(jīng)網(wǎng)絡(luò)分別求出兩個(gè)視圖的經(jīng)過(guò)線性化的向量，然后求出兩個(gè)投影向量的最大相關(guān)性，最后求出新的投影向量。用這個(gè)投影向量加入到機(jī)器學(xué)習(xí)算法進(jìn)行分類，聚類回歸。

此外，我們?cè)谒惴ɡ镏徽伊讼嚓P(guān)度最大的奇異值或者特征值，作為數(shù)據(jù)的相關(guān)系數(shù)，實(shí)際上我們也可以像PCA一樣找出第二大奇異值，第三大奇異值，。。。得到第二相關(guān)系數(shù)和第三相關(guān)系數(shù)。然后對(duì)數(shù)據(jù)做進(jìn)一步的相關(guān)性分析。但是一般的應(yīng)用來(lái)說(shuō)，找出第一相關(guān)系數(shù)就可以了

有時(shí)候我們的矩陣S_{XX}，S_{YY}不可逆，此時(shí)我們得不到對(duì)應(yīng)的逆矩陣，一般遇到這種情況可以對(duì)S_{XX}，S_{YY}進(jìn)行正則化，將S_{XX}，S_{YY}變化為S_{XX}+\gamma I,S_{YY}+\gamma I,然后繼續(xù)求逆。其中\gamma 為正則化系數(shù)。

參考鏈接：
基于典型相關(guān)性分析(CCA)的多視圖學(xué)習(xí)方法綜述
Analysis (CCA) Based Multi-View Learning: An Overview-- Neural Computing and Applications 2019
關(guān)于方差、協(xié)方差的兩個(gè)公式
深度學(xué)習(xí)解決多視圖非線性數(shù)據(jù)特征融合問(wèn)題

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容