典型相关分析（CCA）

CCA是数据挖掘中重要的算法，可以挖掘出数据间的关联关系的算法。

基础知识

如何衡量两个变量之间的相关性呢？我们有相关系数，如下所示：

ρ(X,Y)=cov(X,Y)DX√DY√ ρ ( X , Y ) = c o v ( X , Y ) D X D Y $\rho(X, Y) = \frac{cov(X,Y)}{\sqrt{DX}\sqrt{DY}}$

值 ρ(X,Y) ρ ( X , Y ) $\rho(X, Y)$的绝对值越接近1，说明X与Y的线性相关性越高

值 ρ(X,Y) ρ ( X , Y ) $\rho(X, Y)$的绝对值越接近0，说明X与Y的线性相关性越低

算法思想

CCA将多维数据 X,Y X , Y $X,Y$利用线性变换投影为1维的数据 X′,Y′ X ′ , Y ′ $X',Y'$，然后计算 X′,Y′ X ′ , Y ′ $X',Y'$的相关系数，进而得到二者的相关性。

那么我们的投影标准就是：

投影后，两组数据的相关系数最大。（这样我们就能挖掘出最相关的特征了。）

算法推导

假设投影向量分别为 a,b a , b $a,b$, 则投影后的数据为：

X′=aTX,Y′=bTY X ′ = a T X , Y ′ = b T Y $X' = a^TX ,Y' = b^TY$

则：

arga,bmaxρ(X′,Y′)=arga,bmaxcov(x′,Y′)DX′√DY′√ a r g a , b m a x ρ ( X ′ , Y ′ ) = a r g a , b m a x c o v ( x ′ , Y ′ ) D X ′ D Y ′ $arg_{a,b} max \rho (X',Y') = arg_{a,b} max \frac{cov(x', Y')}{\sqrt{DX'}\sqrt{DY'}}$

假设我们的原始数据是标准化的，即均值为0，方差为1，则：

cov(X′,Y′)=cov(aTX,bTY)=aTE(XYT)b c o v ( X ′ , Y ′ ) = c o v ( a T X , b T Y ) = a T E ( X Y T ) b $cov(X',Y') = cov(a^TX,b^TY) = a^TE(XY^T)b$

DX′=D(aTX)=aTDXa=aTE(XXT)a D X ′ = D ( a T X ) = a T D X a = a T E ( X X T ) a $DX' = D(a^TX) = a^TDXa = a^TE(XX^T)a$

DY′=D(aTY)=aTDYa=aTE(YYT)a D Y ′ = D ( a T Y ) = a T D Y a = a T E ( Y Y T ) a $DY' = D(a^TY) = a^TDYa = a^TE(YY^T)a$

因为均值为0，有：

DX=E(XXT),DY=E(YYT) D X = E ( X X T ) , D Y = E ( Y Y T ) $DX = E(XX^T) , DY = E(YY^T)$

cov(X,Y)=E(XYT),cov(Y,X)=E(YXT) c o v ( X , Y ) = E ( X Y T ) , c o v ( Y , X ) = E ( Y X T ) $cov(X,Y) = E(XY^T) , cov(Y,X) = E(YX^T)$

令 SXY=cov(X,Y) S X Y = c o v ( X , Y ) $S_{XY} = cov(X,Y)$

我们的问题就转化为：

arga,bmaxρ(X′,Y′)=arga,bmaxaTSXYbaTSXXa√bTSYYb√ a r g a , b m a x ρ ( X ′ , Y ′ ) = a r g a , b m a x a T S X Y b a T S X X a b T S Y Y b $arg_{a,b} max \rho (X',Y') = arg_{a,b} max \frac{a^TS_{XY}b}{\sqrt{a^TS_{XX}a}\sqrt{b^TS_{YY}b}}$

问题转化为：

arga,bmaxρ(X′,Y′)=arga,bmax aTSXYb a r g a , b m a x ρ ( X ′ , Y ′ ) = a r g a , b m a x   a T S X Y b $arg_{a,b} max \rho (X',Y') = arg_{a,b} max \ a^TS_{XY}b$

s.t.aTSXXa=1,bTSYYb=1 s . t . a T S X X a = 1 , b T S Y Y b = 1 $s.t. a^TS_{XX}a=1 , b^TS_{YY}b =1$

则根据拉格朗日乘子法，有：

J(a,b)=aTSXYb−λ0(aTSXXa−1)−λ1(bTSYYb−1) J ( a , b ) = a T S X Y b − λ 0 ( a T S X X a − 1 ) − λ 1 ( b T S Y Y b − 1 ) $J(a,b) = a^TS_{XY}b - \lambda_0(a^TS_{XX}a - 1) - \lambda_1(b^TS_{YY}b - 1)$

求导有：

SXYb=λ0SXXa S X Y b = λ 0 S X X a $S_{XY}b = \lambda_0 S_{XX}a$

SYXa=λ1SYYb S Y X a = λ 1 S Y Y b $S_{YX}a = \lambda_1 S_{YY}b$

所以有：

aTSXYb=λ0aTSXXa=λ0 a T S X Y b = λ 0 a T S X X a = λ 0 $a^TS_{XY}b = \lambda_0 a^TS_{XX}a = \lambda_0$

bTSYXa=λ1bTSYYb=λ1 b T S Y X a = λ 1 b T S Y Y b = λ 1 $b^TS_{YX}a = \lambda_1 b^TS_{YY}b = \lambda_1$

所以有：

λ0=λT1=λ1=aTSXYb=λ λ 0 = λ 1 T = λ 1 = a T S X Y b = λ $\lambda_0 = \lambda_1^T = \lambda_1 = a^TS_{XY}b = \lambda$

可以推出：

S−1XXSXYb=λa S X X − 1 S X Y b = λ a $S_{XX}^{-1}S_{XY}b = \lambda a$

S−1YYSYXa=λb S Y Y − 1 S Y X a = λ b $S_{YY}^{-1}S_{YX}a = \lambda b$

因此有：

S−1XXSXYS−1YYSYXa=λ2a S X X − 1 S X Y S Y Y − 1 S Y X a = λ 2 a $S_{XX}^{-1}S_{XY}S_{YY}^{-1}S_{YX}a = \lambda^2 a$

对上面的式子进行特征值分解，那么特征值的平方根的最大值的特征向量就是我们求得的向量a

同理可以求得向量b

S−1YYSYXS−1XXSXYb=λ2b S Y Y − 1 S Y X S X X − 1 S X Y b = λ 2 b $S_{YY}^{-1}S_{YX}S_{XX}^{-1}S_{XY}b = \lambda^2 b$

基于SVD的推导

其实算法也可以通过svd分解的算法求得，如下所示：

arga,bmaxρ(X′,Y′)=arga,bmax aTSXYb a r g a , b m a x ρ ( X ′ , Y ′ ) = a r g a , b m a x   a T S X Y b $arg_{a,b} max \rho (X',Y') = arg_{a,b} max \ a^TS_{XY}b$

s.t.aTSXXa=1,bTSYYb=1 s . t . a T S X X a = 1 , b T S Y Y b = 1 $s.t. a^TS_{XX}a=1 , b^TS_{YY}b =1$

令：

a=S−12XXμ,b=S−12YYv a = S X X − 1 2 μ , b = S Y Y − 1 2 v $a=S_{XX}^{-\frac{1}{2}} \mu, b=S_{YY}^{-\frac{1}{2}} v$

则问题转化为：

arga,bmaxρ(X′,Y′)=arga,bmax μTS−12XXSXYTS−12YYv a r g a , b m a x ρ ( X ′ , Y ′ ) = a r g a , b m a x   μ T S X X − 1 2 S X Y T S Y Y − 1 2 v $arg_{a,b} max \rho (X',Y') = arg_{a,b} max \ \mu^TS_{XX}^{-\frac{1}{2}} S_{XY}TS_{YY}^{-\frac{1}{2}}v$

s.t. μTμ=1,vTv=1 s . t .   μ T μ = 1 , v T v = 1 $s.t. \ \mu^T \mu=1 , v^Tv =1$

这里 μ,v μ , v $\mu, v$都是单位正交基。

令：

M=S−12XXSXYTS−12YY M = S X X − 1 2 S X Y T S Y Y − 1 2 $M = S_{XX}^{-\frac{1}{2}} S_{XY}TS_{YY}^{-\frac{1}{2}}$

对M进行奇异值分解,有：

M=UΣVT M = U Σ V T $M =U \Sigma V^T$

因此有：

μTMv=μTUΣVTv=σμv μ T M v = μ T U Σ V T v = σ μ v $\mu^TMv = \mu^T U \Sigma V^T v = \sigma_{\mu v}$

因为 U,V U , V $U, V$都是单位正交基矩阵， 且 μ,v μ , v $\mu, v$都是单位正交基。

所以有 μTU,VTv μ T U , V T v $\mu^TU, V^Tv$是只有一个标量值为1，其他值为0的向量。

所以 σμv σ μ v $\sigma_{\mu v}$只要是最大的奇异值即可。

因此问题转换为对 M=S−12XXSXYTS−12YY M = S X X − 1 2 S X Y T S Y Y − 1 2 $M = S_{XX}^{-\frac{1}{2}} S_{XY}TS_{YY}^{-\frac{1}{2}}$做奇异值分解，得到 U,V U , V $U, V$，进而得到 μ,v μ , v $\mu, v$

进而得到：

a=S−12XXμ a = S X X − 1 2 μ $a=S_{XX}^{-\frac{1}{2}} \mu$

b=S−12YYv b = S Y Y − 1 2 v $b=S_{YY}^{-\frac{1}{2}} v$

后记

我们看到CCA可以用作分析向量的相关性，一定意义上，也可以用作降维。

但是CCA最重要的一个应用还是特征融合，即根据两组特征找到相关性最大的特征，这样可以利用较好的特征来从较差的特征中进行进一步的特征抽取，提高分类效果。