文档章节

典型关联分析(CCA)原理总结

o
 osc_zoa3moe9
发布于 2019/12/07 16:10
字数 2770
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

原文地址:https://www.cnblogs.com/pinard/p/6288716.html

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

1. CCA概述

    在数理统计里面,我们都知道相关系数这个概念。假设有两组一维的数据集X和Y,则相关系数ρρ 的定义为:

ρ(X,Y)=cov(X,Y)D(X)−−−−−√D(Y)−−−−−√ρ(X,Y)=cov(X,Y)D(X)D(Y)

 

    其中cov(X,Y)cov(X,Y) 是X和Y的协方差,而D(X),D(Y)D(X),D(Y) 分别是X和Y的方差。相关系数ρρ 的取值为[-1,1], ρρ 的绝对值越接近于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为n1×mn1×m 的样本矩阵。Y为n2×mn2×m 的样本矩阵.其中m为样本个数,而n1,n2n1,n2 分别为X和Y的特征维度。

    对于X矩阵,我们将其投影到1维,或者说进行线性表示,对应的投影向量或者说线性系数向量为aa , 对于Y矩阵,我们将其投影到1维,或者说进行线性表示,对应的投影向量或者说线性系数向量为bb , 这样X ,Y投影后得到的一维向量分别为X',Y'。我们有

X=aTX,Y=bTYX′=aTX,Y′=bTY

 

    我们CCA的优化目标是最大化ρ(X,Y)ρ(X′,Y′) 得到对应的投影向量a,ba,b ,即

argmaxa,bcov(X,Y)D(X)−−−−−√D(Y)−−−−−√argmax⏟a,bcov(X′,Y′)D(X′)D(Y′)

 

     在投影前,我们一般会把原始数据进行标准化,得到均值为0而方差为1的数据X和Y。这样我们有:

cov(X,Y)=cov(aTX,bTY)=E(<aTX,bTY>)=E((aTX)(bTY)T)=aTE(XYT)bcov(X′,Y′)=cov(aTX,bTY)=E(<aTX,bTY>)=E((aTX)(bTY)T)=aTE(XYT)b

D(X)=D(aTX)=aTE(XXT)aD(X′)=D(aTX)=aTE(XXT)a

D(Y)=D(bTY)=bTE(YYT)bD(Y′)=D(bTY)=bTE(YYT)b

 

    由于我们的X,Y的均值均为0,则

D(X)=cov(X,X)=E(XXT),D(Y)=cov(Y,Y)=E(YYT)D(X)=cov(X,X)=E(XXT),D(Y)=cov(Y,Y)=E(YYT)

cov(X,Y)=E(XYT),cov(Y,X)=E(YXT)cov(X,Y)=E(XYT),cov(Y,X)=E(YXT)

 

    令SXY=cov(X,Y)SXY=cov(X,Y) ,则优化目标可以转化为:

argmaxa,baTSXYbaTSXXa−−−−−−−√bTSYYb−−−−−−√argmax⏟a,baTSXYbaTSXXabTSYYb

 

    由于分子分母增大相同的倍数,优化目标结果不变,我们可以采用和SVM类似的优化方法,固定分母,优化分子,具体的转化为:

argmaxa,baTSXYbargmax⏟a,baTSXYb

s.t.aTSXXa=1,bTSYYb=1s.t.aTSXXa=1,bTSYYb=1

 

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

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

3. CCA算法的SVD求解

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

    首先,我们令a=S1/2XXu,b=S1/2YYva=SXX−1/2u,b=SYY−1/2v ,这样我们有:

aTSXXa=1uTS1/2XXSXXS1/2XXu=1uTu=1aTSXXa=1⇒uTSXX−1/2SXXSXX−1/2u=1⇒uTu=1

bTSYYb=1vTS1/2YYSYYS1/2YYv=1vTv=1bTSYYb=1⇒vTSYY−1/2SYYSYY−1/2v=1⇒vTv=1

aTSXYb=uTS1/2XXSXYS1/2YYvaTSXYb=uTSXX−1/2SXYSYY−1/2v

 

 

    也就是说,我们的优化目标变成下式:

argmaxu,vuTS1/2XXSXYS1/2YYvargmax⏟u,vuTSXX−1/2SXYSYY−1/2v

s.t.uTu=1,vTv=1s.t.uTu=1,vTv=1

   

 

    仔细一看,如果将u和v看做矩阵M=S1/2XXSXYS1/2YYM=SXX−1/2SXYSYY−1/2 的某一个奇异值对应的左右奇异向量。那么利用奇异值分解,我们可以得到M=UΣVTM=UΣVT ,其中U,VU,V 分别为M的左奇异向量和右奇异向量组成的矩阵,而ΣΣ 为M的奇异值组成的对角矩阵。由于U,VU,V 所有的列都为标准正交基,则uTUuTU 和VTvVTv 得到一个只有一个标量值为1,其余标量值为0的向量。此时我们有

uTS1/2XXSXYS1/2YYv=uTUΣVTv=σuvuTSXX−1/2SXYSYY−1/2v=uTUΣVTv=σuv

 

    也就是说我们最大化uTS1/2XXSXYS1/2YYvuTSXX−1/2SXYSYY−1/2v ,其实对应的最大值就是某一组左右奇异向量所对应的奇异值的最大值。也就是将M做了奇异值分解后,最大的奇异值就是我们优化目标的最大值,或者说我们的X和Y之间的最大相关系数。利用对应的左右奇异向量u,vu,v 我们也可以求出我们原始的X和Y的线性系数a=S1/2XXu,b=S1/2YYva=SXX−1/2u,b=SYY−1/2v 。

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

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

    特征分解方式就比较传统了,利用拉格朗日函数,优化目标转化为最大化下式:

J(a,b)=aTSXYbλ2(aTSXXa1)θ2(bTSYYb1)J(a,b)=aTSXYb−λ2(aTSXXa−1)−θ2(bTSYYb−1)

 

    分别对a,ba,b 求导并令结果为0,我们得到:

SXYbλSXXa=0SXYb−λSXXa=0

SYXaθSYYb=0SYXa−θSYYb=0

 

    将上面第一个式子左乘aTaT ,第二个式子左乘bTbT ,并利用aTSXXa=1,bTSYYb=1aTSXXa=1,bTSYYb=1 ,我们得到

λ=θ=aTSXYbλ=θ=aTSXYb

 

    其实也就是说我们的拉格朗日系数就是我们要优化的目标。我们继续将上面的两个式子做整理,第一个式子左乘S1XXSXX−1 ,第二个式子左乘S1YYSYY−1 ,我们得到:

S1XXSXYb=λaSXX−1SXYb=λa

S1YYSYXa=λbSYY−1SYXa=λb

 

    将上面第二个式子带入第一个式子,我们得到

S1XXSXYS1YYSYXa=λ2aSXX−1SXYSYY−1SYXa=λ2a

 

    这个式子我们就熟悉了,这不就是特征分解吗!要求最大的相关系数λλ ,我们只需要对矩阵N=S1XXSXYS1YYSYXN=SXX−1SXYSYY−1SYX 做特征分解,找出最大的特征值取平方根即可,此时最大特征值对应的特征向量即为X的线性系数aa 。

    同样的办法,我们将上面第一个式子带入第二个式子,我们得到

S1YYSYXS1XXSXYb=λ2bSYY−1SYXSXX−1SXYb=λ2b

, 我们只需要对矩阵N=S1YYSYXS1XXSXYN′=SYY−1SYXSXX−1SXY 做特征分解,找出最大的特征值取平方根即可,此时最大特征值对应的特征向量即为Y的线性系数bb 。

 

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

5. CCA算法流程

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

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

    输出:X,Y的相关系数ρρ ,X和Y的线性系数向量a和b

    1)计算X的方差SXXSXX , Y的方差SYYSYY ,X和Y的协方差SXYSXY , Y和X的协方差SYX=STXYSYX=SXYT

    2)  计算矩阵M=S1/2XXSXYS1/2YYM=SXX−1/2SXYSYY−1/2

    3)对矩阵MM 进行奇异值分解,得到最大的奇异值ρρ ,和最大奇异值对应的左右奇异向量u,vu,v

    4) 计算X和Y的线性系数向量a和b, a=S1/2XXu,b=S1/2YYva=SXX−1/2u,b=SYY−1/2v

    

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

6. CCA算法小结

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

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

    有时候我们的矩阵SXX,SYYSXX,SYY 不可逆,此时我们得不到对应的逆矩阵,一般遇到这种情况可以对SXX,SYYSXX,SYY 进行正则化,将SXX,SYYSXX,SYY 变化为SXX+γI,SYY+γISXX+γI,SYY+γI ,然后继续求逆。其中γγ 为正则化系数。

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
CCA典型关联分析原理与Python案例

本文分享自微信公众号 - 脑机接口社区(BrainComputer)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

脑机接口社区
07/02
0
0
机器学习(32)之典型相关性分析(CCA)详解 【文末有福利......】

微信公众号 关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 人工智能与Python公开课 限时免费 文末领取 前言 典型关联...

mbx8x9u
2017/12/17
0
0
ICML 2019 | Hinton等人新研究:如何更好地测量神经网络表示相似性

作者:Simon Kornblith、Mohammad Norouzi、Honglak Lee、Geoffrey Hinton 参与:可可、路 近期很多研究试图通过对比神经网络表示来理解神经网络的行为。谷歌大脑 Simon Kornblith、Geoffre...

zhuiqiuk
06/22
0
0
如何更好地测量神经网络表示相似性

近期很多研究试图通过对比神经网络表示来理解神经网络的行为。谷歌大脑 Simon Kornblith、Geoffrey Hinton 等人的一项新研究引入了 centered kernel alignment (CKA) 作为相似性指数,并分析...

osc_bq1qsg6s
2019/05/21
1
0
Hinton等人新研究:如何更好地测量神经网络表示相似性

Hinton等人新研究:如何更好地测量神经网络表示相似性 2019年05月22日 08:39:15 喜欢打酱油的老鸟 阅读数 177更多 分类专栏: 人工智能 https://www.toutiao.com/a6692998683081835012/ 近期...

osc_p0ka0957
2019/09/07
1
0

没有更多内容

加载失败,请刷新页面

加载更多

使用命名管道承载gRPC

最近GRPC很火,感觉整RPC不用GRPC都快跟不上时髦了。 gRPC设计 gRPC是一种与语言无关的高性能远程过程调用 (RPC) 框架。刚好需要使用一个的RPC应用系统,自然而然就盯上了它,但是它真能够解...

osc_nq69o22c
22分钟前
16
0
06-敏捷开发框架-apis 脚本库 引用位置无关性设计

动态引入技术的设计,对我们来说非常重要。 同时也说明动态语言的使用对我们来说也是非常重要。 没有动态语言的支撑,有些想法可能不容易实现,或者有替代方案,可能会花更大的代价。 前端开...

osc_5zg9z6t1
23分钟前
21
0
(三)学习了解OrchardCore笔记——灵魂中间件ModularTenantContainerMiddleware的第一行①的模块部分

  了解到了OrchardCore主要由两个中间件(ModularTenantContainerMiddleware和ModularTenantRouterMiddleware)构成,下面开始了解ModularTenantContainerMiddleware中间件第一行代码。   ...

osc_kdarxvx0
25分钟前
15
0
50Mn18Cr4V锻锻环件

电机无磁护环怎么锻性能才能《高高》?50Mn18Cr4V高锰无磁钢在变形温度为900~1 100℃、应变速率为0.1 ~10s-1条件下的热变形行为. 结果,VC第二相的应变诱导析出对50Mn18Cr4V的热变形行为产生...

无磁钢
25分钟前
16
0
【遇见offer】一汽-大众实习生专场来啦!成长+学习+福利,一个也不能少~

在上次一汽-大众的社招直播之后,实习生的专场招聘也终于来啦! 针对2020年暑期,我们提供了非常多的实习岗位给大家选择。 如果你想得到大厂实习的宝贵经验,如果你想得到更快速的成长,如果...

osc_b88oux8w
27分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部