高维数据降维中SVD与CUR分解对比分析
曾琦;李国盛;郭云鹏;曾圆;张凤娟
【摘 要】在大数据分析和处理中有许多常用的降维方法,在线性降维中典型的方法有SVD分解和CUR分解,但是对这两种方法的使用条件和实际效果研究甚少.基于此,通过对SVD与CUR分解原理和实验结果的探讨,分析了这两种降维方法的使用条件和实际效果.
【期刊名称】《中原工学院学报》
【年(卷),期】2014(025)006
【总页数】5页(P80-84)
【关键词】SVD分解;TSVD;CUR分解;降维
【作 者】曾琦;李国盛;郭云鹏;曾圆;张凤娟
【作者单位】解放军信息工程大学,郑州450000;解放军信息工程大学,郑州450000;解放军信息工程大学,郑州450000;解放军信息工程大学,郑州450000;解放军信息工程大学,郑州450000
【正文语种】中 文
【中图分类】G354
在高维空间中，由于“维数灾难”的存在，作为数据之间相似性度量的Lp距离会失去意义。高维数据包含许多冗余，其实际的维度比原始的数据维度小得多，因此高维数据可以通过降维手段转换到低维空间进行处理。高维数据的处理方法有很多种，常用的方法有SVD分解和CUR分解。SVD分解是大数据分析和处理常用的降维方法。但是，由于它线性综合了全局的信息，因此生成的数据往往过于稠密且难以解释。针对SVD分解的缺点，有人提出了CUR分解的方法[1]。CUR分解是一种从原始数据矩阵中依概率选取部分行和列构造矩阵的分解方法。CUR分解得到的矩阵由原始数据构造而来，其得到的矩阵稀疏且物理意义明确。同时，CUR分解的算法较为简单，避免了对高维矩阵进行特征值求解，因此其效率也较高。本文主要对这两种降维方法进行对比分析。
1 矩阵的SVD分解
1.1 SVD分解的一般形式
给定一个m×n的矩阵A，那么就一定存在正交矩阵U={u1,u2,…,um}∈Rm×m和V={v1,v2,…,vn}∈Rn×n，其中则一定有：
A=UΣVT
(1)
其中,Σ=diag(σ1,…,σρ);Σ∈Rm×n;ρ=min(m,n)，σ1≥σ2≥…≥σp≥0，矩阵U称为A的左奇异矩阵，矩阵VT称为A的右奇异矩阵，(σ1,σ2,…,σp)称为A的奇异值。因为矩阵U和V均为正交矩阵，式(1)还可以写为UTAV=Σ。
1.2 SVD分解的存在性
下面讨论矩阵A的SVD分解的存在性[2]，假设对于矩阵A∈Rm×n成立，则
(2)
当m>n时，
(3)
当m=n时，
(4)
当m<n时，
(5)
如果式(1)成立，由式(3)、(4)和(5)得：
A=UFVT,AT=VFTUT
(6)
由上式得：
ATA=VΣ2VT,VT(ATA)V=Σ 2
(7)
式(7)中V的所有列向量为ATA的特征向量，且均为规范化正交组，在式(3)、(4)和(5)中，为ATA的特征值。U的所有列向量为对称阵AAT的特征向量。
下面构造正交矩阵U、V。
设是ATA的特征值，且ATA存在规范化正交特征向量组{v1,v2,…,vn}，即
(8)
构造V={v1,v2,…,vn}，V∈Rn×n为正交阵，令
(9)
显然，{u1,u2,…,ur}为AAT的特征值所对应的特征向量，且满足(ui,uj)=δij(i,j=1,2,…,r)，在Rm中补充向量(ur+1,…,um),使{u1,u2,…,um}为Rm中的一个规范正交基，再令U={u1,u2,…,um}∈Rm×m为正交阵，则由式(8)和式(9)得：
AV=UF或UTAV=F
(10)
式(10)说明矩阵A的SVD分解是存在的，且对任意的矩阵总能到这样的分解式。
SVD分解在大数据分析中有着广泛的应用。利用SVD降维的更常见的方法是先对矩阵进行奇异值分解，然后根据需要截取Σ矩阵中最大的k个元素，以及相应的U矩阵和V矩阵中的特征向量，这种方法称作截断奇异值分解(TSVD)。如果k≤r=rank(A)，定义，则有：
(11)
这里用Frobenius范数·F来衡量矩阵Ak和原始矩阵A之间的距离，可以证明矩阵Ak是原始矩阵A的近似。
尽管SVD分解的应用非常广泛，但是从原始矩阵的列来看，特征向量ui和vi往往缺乏合理的解释。例如，个人信息矩阵经过SVD分解后，可能得到的特征向量会包括很多极小值和负值。这对于SVD分解来说是正常的，因为SVD分解是一个数学方法，可以适用于任何矩阵。而在实际应用中，有着明确物理意义的数据经过SVD分解会得到负值,这样的结果就很难给出合理的解释。
2 矩阵的CUR分解
2.1 相关研究
Stewart G W在线性代数领域提出了Quasi-Gram-Schmidt方法,这种方法应用到矩阵中得到了CUR分解[3-4]。Goreinov S A等提出了CUR分解(pseudoskeleton近似)，并讨论了怎样选取行和列满足最大不相关理论[5-6]。Frieze A等提出依据矩阵中列的Euclidean范数的概率分布随机选择矩阵A中的列[7]。Mahoney M W等结合上述方法的优点，提出效果较好的CUR分解方法[1]。本文主要分析CUR分解过程，并与SVD分解进行对比。
2.2 CUR分解的一般方法
CUR分解的实质是从原始矩阵中直接选取部分行和列，并以此构造3个矩阵C、U和R。给定矩阵A，为了构造矩阵C(矩阵R的构造类似)，需要对A中每列计算一个重要程度值，重要程度值越大的列在构造过程中被选取的概率越大。按照这种规则进行选择，就能保证CUR是原始矩阵A的一个近似。
正则化一个5 5随机矩阵
原始矩阵A的第j列表示为
(12)
其中；vξj是Aj对应的第ξ个右奇异向量。式(12)表明原始矩阵A中的第j列是所有左奇异向量和奇异值的线性组合，而右奇异矩阵第j行的元素是它们的系数。因此，与TSVD方法类似，有如下近似：
(13)
再对前k个右奇异向量计算正则化杠杆效应值：
(14)
经过正则化之后，有πj≥0且形成了一个在n列上的概率分布。然后按照下面的步骤操作：
(1)计算并正则化矩阵A的前k个右奇异向量的杠杆效应值；
(2)依概率pj=min{1,cπj}选择矩阵A中的第j列，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。