典型关联分析(CCA)原理

典型关联分析(Canonical Correlation Analysis，以下简称CCA)是最常用的挖掘数据关联关系的算法之一。比如我们拿到两组数据，第一组是人身高和体重的数据，第二组是对应的跑步能力和跳远能力的数据。那么我们能不能说这两组数据是相关的呢？CCA可以帮助我们分析这个问题。

1. CCA概述

在数理统计里面，我们都知道相关系数这个概念。假设有两组一维的数据集X和Y，则相关系数$\rho$的定义为: $\rho(X,Y) = \frac{cov(X,Y)}{\sqrt{D(X)}\sqrt{D(Y)}}$ 其中$cov(X,Y)$是X和Y的协方差，而D(X), D(Y)分别是X和Y的方差。相关系数$\rho$的取值为[-1,1],　$\rho$的绝对值越接近于1，则X和Y的线性相关性越高。越接近于0，则X和Y的线性相关性越低。

虽然相关系数可以很好的帮我们分析一维数据的相关性，但是对于高维数据就不能直接使用了。拿上面我们提到的，如果X是包括人身高和体重两个维度的数据，而Y是包括跑步能力和跳远能力两个维度的数据，就不能直接使用相关系数的方法。那我们能不能变通一下呢？CCA给了我们变通的方法。

CCA使用的方法是将多维的X和Y都用线性变换为1维的X'和Y'，然后再使用相关系数来看X'和Y'的相关性。将数据从多维变到1位，也可以理解为CCA是在进行降维，将高维数据降到1维，然后再用相关系数进行相关性的分析。下面我们看看CCA的算法思想。

2. CCA的算法思想

上面我们提到CCA是将高维的两组数据分别降维到1维，然后用相关系数分析相关性。但是有一个问题是，降维的标准是如何选择的呢？回想下主成分分析PCA，降维的原则是投影方差最大；再回想下线性判别分析LDA，降维的原则是同类的投影方差小，异类间的投影方差大。对于我们的CCA，它选择的投影标准是降维到1维后，两组数据的相关系数最大。

现在我们具体来讨论下CCA的算法思想。假设我们的数据集是X和Y，X为$n_1 \times m$的样本矩阵。Y为$n_2 \times m$的样本矩阵.其中m为样本个数，而$n_1,n_2$分别为X和Y的特征维度。

对于X矩阵，我们将其投影到1维，或者说进行线性表示，对应的投影向量或者说线性系数向量为a, 对于Y矩阵，我们将其投影到1维，或者说进行线性表示，对应的投影向量或者说线性系数向量为b, 这样X ,Y投影后得到的一维向量分别为X',Y'。我们有 $X' = a^TX, Y'=b^TY$ 我们CCA的优化目标是最大化$\rho(X',Y')$得到对应的投影向量a,b，即$arg\;max(a,b)\;\;\frac{cov(X',Y')}{\sqrt{D(X')}\sqrt{D(Y')}}$

在投影前，我们一般会把原始数据进行标准化，得到均值为0而方差为1的数据X和Y。这样我们有：$cov(X',Y') = cov(X',Y') = cov(a^TX, b^TY) = E(<a^TX, b^TY>) = E((a^TX)(b^TY)^T) = a^TE(XY^T)b$

$x = y$

$D(Y') = D(b^TY) = b^TE(YY^T)b$

由于我们的X，Y的均值均为0，则 $D(X) = cov(X,X) = E(XX^T), D(Y)= cov(Y,Y) = E(YY^T)$

$cov(X,Y) = E(XY^T), cov(Y,X) = E(YX^T)$ 令$S_{XY} =cov(X,Y)$，则优化目标可以转化为：$arg\;max(a,b)\;\;\frac{a^TS_{XY}b}{\sqrt{ a^TS_{XX}a}\sqrt{b^TS_{YY}b}}$

由于分子分母增大相同的倍数，优化目标结果不变，我们可以采用和SVM类似的优化方法，固定分母，优化分子，具体的转化为：$arg\;max(a,b)\;\;{a^TS_{XY}b}$ $s.t. a^TS_{XX}a =1,\; b^TS_{YY}b =1$

也就是说，我们的CCA算法的目标最终转化为一个凸优化过程，只要我们求出了这个优化目标的最大值，就是我们前面提到的多维X和Y的相关性度量，而对应的a,b则为降维时的投影向量，或者说线性系数。

这个函数优化一般有两种方法，第一种是奇异值分解SVD，第二种是特征分解，两者得到的结果一样，下面我们分别讲解。

3. CCA算法的SVD求解

对于上面的优化目标，我们可以做一次矩阵标准化，就可以用SVD来求解了。

首先，我们令$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$

$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$

也就是说，我们的优化目标变成下式：

$arg\;max(u,v)\;\;u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v$

$s.t. u^Tu =1,\; v^Tv =1$

仔细一看，如果将u和v看做矩阵$M=S_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}$的某一个奇异值对应的左右奇异向量。那么利用奇异值分解，我们可以得到$M=U\Sigma V^T$,其中U,V分别为M的左奇异向量和右奇异向量组成的矩阵，而$\Sigma$为M的奇异值组成的对角矩阵。由于U,V所有的列都为标准正交基，则$u^TU$和$V^Tv$得到一个只有一个标量值为1，其余标量值为0的向量。此时我们有$u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v = u^TU\Sigma V^Tv = \sigma_{uv}$

也就是说我们最大化$u^TS_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}v$,其实对应的最大值就是某一组左右奇异向量所对应的奇异值的最大值。也就是将M做了奇异值分解后，最大的奇异值就是我们优化目标的最大值，或者说我们的X和Y之间的最大相关系数。利用对应的左右奇异向量u,v我们也可以求出我们原始的X和Y的线性系数$a=S_{XX}^{-1/2}u, b=S_{YY}^{-1/2}v$。

可以看出，SVD的求解方式非常简洁方便。但是如果你不熟悉SVD的话，我们也可以用传统的拉格朗日函数加上特征分解来完成这个函数的优化。

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

特征分解方式就比较传统了，利用拉格朗日函数，优化目标转化为最大化下式：$J(a,b) = a^TS_{XY}b -\frac{\lambda}{2}(a^TS_{XX}a-1)-\frac{\theta}{2}(b^TS_{YY}b-1)$

分别对a,b求导并令结果为0，我们得到：$S_{XY}b-\lambda S_{XX}a=0S_{YX}a-\lambda S_{YY}b=0$

将上面第一个式子左乘$a^T$,第二个式子左乘$b^T$，并利用$a^TS_{XX}a =1,\; b^TS_{YY}b =1$，我们得到$\lambda = \theta = a^TS_{XY}b$

其实也就是说我们的拉格朗日系数就是我们要优化的目标。我们继续将上面的两个式子做整理，第一个式子左乘$S_{XX}^{-1}$,第二个式子左乘$S_{YY}^{-1}$，我们得到：$S_{XX}^{-1}S_{XY}b=\lambda aS_{YY}^{-1}S_{YX}a = \lambda b$

将上面第二个式子带入第一个式子，我们得到$S_{XX}^{-1}S_{XY}S_{YY}^{-1}S_{YX}a=\lambda^2a$

这个式子我们就熟悉了，这不就是特征分解吗！要求最大的相关系数$\lambda$,我们只需要对矩阵$N=S_{XX}^{-1}S_{XY}S_{YY}^{-1}S_{YX}$做特征分解，找出最大的特征值取平方根即可，此时最大特征值对应的特征向量即为X的线性系数a。

同样的办法，我们将上面第一个式子带入第二个式子，我们得到$S_{YY}^{-1}S_{YX}S_{XX}^{-1}S_{XY}b=\lambda^2b$, 我们只需要对矩阵$N^{'}=S_{YY}^{-1}S_{YX}S_{XX}^{-1}S_{XY}$做特征分解，找出最大的特征值取平方根即可，此时最大特征值对应的特征向量即为Y的线性系数b。

可以看出特征分解的方法要比SVD复杂，但是两者求得的结果其实是等价的，只要利用SVD和特征分解之间的关系就很容易发现两者最后的结果相同。

5. CCA算法流程

这里我们对CCA的算法流程做一个总结，以SVD方法为准。

输入：各为m个的样本X和Y，X和Y的维度都大于1

输出：X,Y的相关系数\rho,X和Y的线性系数向量a和b

1）计算X的方差$S_{XX}$, Y的方差$S_{YY}$，X和Y的协方差$S_{XY}$, Y和X的协方差$S_{YX}=S_{XY}^T$

2) 计算矩阵M=$S_{XX}^{-1/2}S_{XY}S_{YY}^{-1/2}$

3）对矩阵M进行奇异值分解，得到最大的奇异值$\rho$，和最大奇异值对应的左右奇异向量u,v

4) 计算X和Y的线性系数向量a和b,$a=S_{XX}^{-1/2}u, b=S_{YY}^{-1/2}v$

可见算法流程并不复杂，但是要理解这个算法需要了解一些背景知识。

6. CCA算法小结

CCA算法广泛的应用于数据相关度的分析，同时还是偏最小二乘法的基础。但是由于它依赖于数据的线性表示，当我们的数据无法线性表示时，CCA就无法使用，此时我们可以利用核函数的思想，将数据映射到高维后，再利用CCA的思想降维到1维，求对应的相关系数和线性关系，这个算法一般称为KCCA。

此外，我们在算法里只找了相关度最大的奇异值或者特征值，作为数据的相关系数，实际上我们也可以像PCA一样找出第二大奇异值，第三大奇异值，。。。得到第二相关系数和第三相关系数。然后对数据做进一步的相关性分析。但是一般的应用来说，找出第一相关系数就可以了。

有时候我们的矩阵$S_{XX},S_{YY}$不可逆，此时我们得不到对应的逆矩阵，一般遇到这种情况可以对$S_{XX},S_{YY}$进行正则化，将$S_{XX},S_{YY}$变化为$S_{XX}+\gamma I,S_{YY}+\gamma I$,然后继续求逆。其中$\gamma$为正则化系数。