高維數(shù)據(jù)降維中SVD與CUR分解對比分析

, , , ,

(解放軍信息工程大學(xué), 鄭州 450000)

在高維空間中，由于“維數(shù)災(zāi)難”的存在，作為數(shù)據(jù)之間相似性度量的Lp距離會失去意義。高維數(shù)據(jù)包含許多冗余，其實(shí)際的維度比原始的數(shù)據(jù)維度小得多，因此高維數(shù)據(jù)可以通過降維手段轉(zhuǎn)換到低維空間進(jìn)行處理。高維數(shù)據(jù)的處理方法有很多種，常用的方法有SVD分解和CUR分解。SVD分解是大數(shù)據(jù)分析和處理常用的降維方法。但是，由于它線性綜合了全局的信息，因此生成的數(shù)據(jù)往往過于稠密且難以解釋。針對SVD分解的缺點(diǎn)，有人提出了CUR分解的方法[1]。CUR分解是一種從原始數(shù)據(jù)矩陣中依概率選取部分行和列構(gòu)造矩陣的分解方法。CUR分解得到的矩陣由原始數(shù)據(jù)構(gòu)造而來，其得到的矩陣稀疏且物理意義明確。同時(shí)，CUR分解的算法較為簡單，避免了對高維矩陣進(jìn)行特征值求解，因此其效率也較高。本文主要對這兩種降維方法進(jìn)行對比分析。

1 矩陣的SVD分解

1.1 SVD分解的一般形式

A=UΣVT

(1)

其中,Σ=diag(σ1,…,σρ);Σ∈Rm×n;ρ=min(m,n)，σ1≥σ2≥…≥σp≥0，矩陣U稱為A的左奇異矩陣，矩陣VT稱為A的右奇異矩陣，(σ1,σ2,…,σp)稱為A的奇異值。因?yàn)榫仃嘦和V均為正交矩陣，式(1)還可以寫為UTAV=Σ。

1.2 SVD分解的存在性

下面討論矩陣A的SVD分解的存在性[2]，假設(shè)對于矩陣A∈Rm×n成立，則

(2)

當(dāng)m>n時(shí)，

(3)

當(dāng)m=n時(shí)，

(4)

當(dāng)m

(5)

如果式(1)成立，由式(3)、(4)和(5)得：

A=UFVT,AT=VFTUT

(6)

由上式得：

ATA=VΣ2VT,VT(ATA)V=Σ2

(7)

下面構(gòu)造正交矩陣U、V。

(8)

構(gòu)造V={v1,v2,…,vn}，V∈Rn×n為正交陣，令

(9)

AV=UF或UTAV=F

(10)

式(10)說明矩陣A的SVD分解是存在的，且對任意的矩陣總能找到這樣的分解式。

(11)

盡管SVD分解的應(yīng)用非常廣泛，但是從原始矩陣的列來看，特征向量ui和vi往往缺乏合理的解釋。例如，個(gè)人信息矩陣經(jīng)過SVD分解后，可能得到的特征向量會包括很多極小值和負(fù)值。這對于SVD分解來說是正常的，因?yàn)镾VD分解是一個(gè)數(shù)學(xué)方法，可以適用于任何矩陣。而在實(shí)際應(yīng)用中，有著明確物理意義的數(shù)據(jù)經(jīng)過SVD分解會得到負(fù)值,這樣的結(jié)果就很難給出合理的解釋。

2 矩陣的CUR分解

2.1 相關(guān)研究

Stewart G W在線性代數(shù)領(lǐng)域提出了Quasi-Gram-Schmidt方法,這種方法應(yīng)用到矩陣中得到了CUR分解[3-4]。Goreinov S A等提出了CUR分解(pseudoskeleton近似)，并討論了怎樣選取行和列滿足最大不相關(guān)理論[5-6]。Frieze A等提出依據(jù)矩陣中列的Euclidean范數(shù)的概率分布隨機(jī)選擇矩陣A中的列[7]。Mahoney M W等結(jié)合上述方法的優(yōu)點(diǎn)，提出效果較好的CUR分解方法[1]。本文主要分析CUR分解過程，并與SVD分解進(jìn)行對比。

2.2 CUR分解的一般方法

CUR分解的實(shí)質(zhì)是從原始矩陣中直接選取部分行和列，并以此構(gòu)造3個(gè)矩陣C、U和R。給定矩陣A，為了構(gòu)造矩陣C(矩陣R的構(gòu)造類似)，需要對A中每列計(jì)算一個(gè)重要程度值，重要程度值越大的列在構(gòu)造過程中被選取的概率越大。按照這種規(guī)則進(jìn)行選擇，就能保證CUR是原始矩陣A的一個(gè)近似。

原始矩陣A的第j列表示為

(12)

(13)

再對前k個(gè)右奇異向量計(jì)算正則化杠桿效應(yīng)值：

(14)

(1)計(jì)算并正則化矩陣A的前k個(gè)右奇異向量的杠桿效應(yīng)值；

矩陣R的構(gòu)造與之類似，對AT按相同步驟處理后可得矩陣R。

定義矩陣W為矩陣C和矩陣R相交元素構(gòu)成的一個(gè)k×k矩陣，對矩陣W進(jìn)行如下操作：

(1)計(jì)算矩陣W的SVD分解，W=XΣYT；

(2)計(jì)算Σ的廣義逆矩陣(Moore-Penrose pseudoinverse)Σ+；

(3)令U=Y(Σ+)2XT；

這樣就得到了CUR分解的3個(gè)矩陣。

3 SVD與CUR分解對比

3.1 SVD與CUR分解異同

對SVD與CUR分解得到的3個(gè)矩陣進(jìn)行對比，可以發(fā)現(xiàn)其相似之處：SVD分解得到的矩陣U和V是嚴(yán)格正交的，這是由求解過程和特征向量性質(zhì)決定的。CUR分解中構(gòu)造的矩陣C和R是近似正交的，這是因?yàn)樵诟呔S矩陣中存在著“維數(shù)災(zāi)難”現(xiàn)象，在高維矩陣中，任意兩個(gè)向量之間都是近似正交的。由于相似性，對矩陣U和V的一些處理方法在矩陣C和R上也是適用的。如果矩陣的維數(shù)較小，矩陣C和R沒有近似正交，其應(yīng)用會受到限制。

與SVD分解相比，CUR分解還有以下優(yōu)點(diǎn)：

(1)CUR分解非常直觀，矩陣C和R都是直接從原始矩陣中按照概率直接選取的，不會產(chǎn)生難以解釋的數(shù)據(jù),如負(fù)值等；

(2)CUR分解中矩陣C和R有著明確的物理意義，且與SVD分解的應(yīng)用方法相同；

(3)CUR分解的效率極高，SVD分解需要分別對矩陣ATA和AAT求特征值，在矩陣A的維數(shù)較高時(shí)計(jì)算量是非常大的。CUR分解只需要對一個(gè)低維的矩陣W進(jìn)行SVD分解，其他兩個(gè)矩陣計(jì)算量都比較小。

3.2 CUR與SVD分解實(shí)際效果比較

利用一個(gè)具體的實(shí)例對CUR分解及SVD分解進(jìn)行比較[8]。圖1是用戶——電影矩陣，矩陣中列代表用戶，行代表電影，矩陣中的元素表示用戶對電影的評分。

圖1 用戶——電影矩陣

對這個(gè)電影矩陣進(jìn)行SVD分解，由式(1)可以得到：

(15)

(16)

(17)

(18)

如果采用截?cái)嗥娈愔捣纸夥?TSVD)，保留最大的兩個(gè)奇異值，可以得到如下式子：

U′ΣVT′=A′

(19)

(20)

(21)

(22)

(23)

可以看到，將TSVD分解得到的矩陣相乘所得的矩陣是原始矩陣的一個(gè)近似。

利用TSVD分解的結(jié)果可以做一個(gè)簡單的推薦系統(tǒng)，例如某用戶只看過電影Matrix，對其評分為4。將該用戶評分表示成向量形式：

(24)

上式表明該用戶可能傾向于科幻類的電影。

(qV)VT=(1.13 1.13 1.13 -0.13 -0.13)

(25)

上式表明該用戶可能對電影Alien和Star Wars也感興趣。

經(jīng)過SVD分解得到的矩陣包括許多負(fù)值，這在現(xiàn)實(shí)意義上難以解釋。雖然還原后的矩陣與原始矩陣近似，但原始矩陣是非常稀疏的，而還原矩陣包含了許多極小值，非常稠密，不便處理。

對原始矩陣進(jìn)行CUR分解，取k=2。

CUR=A′

(26)

(27)

(28)

(29)

(30)

CUR分解得到的矩陣也是原始矩陣的一個(gè)近似。

利用CUR分解同樣可以實(shí)現(xiàn)一個(gè)推薦系統(tǒng)，先對矩陣R進(jìn)行正則化，然后按照與TSVD類似的方法進(jìn)行處理：

(qRT)R=(1.35 1.35 1.35 0 0)

(31)

其結(jié)果與利用TSVD分解得到的結(jié)果是非常近似的。

再對CUR分解得到的矩陣進(jìn)行觀察，發(fā)現(xiàn)其能夠克服TSVD分解的缺點(diǎn)。首先CUR分解中矩陣的構(gòu)造來自原始矩陣，沒有出現(xiàn)類似負(fù)值這樣的異常值；其次，CUR分解得到的矩陣非常稀疏，還原后的矩陣也非常稀疏，這對于高維數(shù)據(jù)的處理是非常有利的。

4 結(jié) 語

SVD分解是一種傳統(tǒng)的矩陣分解方法，生成的矩陣中包含很多極小值和負(fù)值，這在工程實(shí)際中是不好解釋的。TSVD方法在SVD分解的基礎(chǔ)之上，通過保留若干個(gè)較大的奇異值及對應(yīng)的奇異向量實(shí)現(xiàn)降維，既在一定程度上保留了矩陣的全局信息，也去掉了大量難以解釋和處理的極小值。CUR分解直接從原始矩陣中依概率選取行和列構(gòu)造矩陣，物理意義明確，處理過程簡單，效率較高，而實(shí)際用法與效果與SVD分解類似，優(yōu)勢非常明顯。但是CUR依賴高維矩陣中任意兩個(gè)向量正交的性質(zhì)，選取行列容易受一些異常數(shù)據(jù)的干擾。

在一般情況下，SVD分解的準(zhǔn)確性較好，CUR分解穩(wěn)定性較差。在高維數(shù)據(jù)的應(yīng)用場景中，對準(zhǔn)確性并沒有嚴(yán)格的要求，SVD分解生成的矩陣過于稠密且效率低下，而CUR分解構(gòu)造的矩陣稀疏，效率較高。

參考文獻(xiàn):

[1] Mahoney M W, Drineas P.CUR Matrix Decompositions for Improved Data Analysis[J].Proceedings of the National Academy of Sciences, 2009, 106(3): 697-702.

[2] 馬良榮, 張德澄.矩陣 SVD 分解法在工程數(shù)據(jù)計(jì)算中的應(yīng)用[J].寧夏大學(xué)學(xué)報(bào)(自然科學(xué)版), 1998, 19(2): 125-127.

[3] Stewart G W.Four Algorithms for the Efficient Computation of Truncated Pivoted QR Approximations to a Sparse Matrix[J].Numerische Mathematik, 1999, 83(2): 313-323.

[4] Berry M W, Pulatova S A, Stewart G W.Algorithm 844: Computing Sparse Reduced-rank Approximations to Sparse Matrices[J].ACM Transactions on Mathematical Software (TOMS), 2005, 31(2): 252-269.

[5] Goreinov S A, Tyrtyshnikov E E, Zamarashkin N L.A theory of Pseudoskeleton Approximations[J].Linear Algebra and Its Applications, 1997, 261(1): 1-21.

[6] Goreinov S A, Tyrtyshnikov E E.The Maximum-volume Concept in Approximation by Low-rank Matrices[J].Contemp.Math., 2001, 280:47-51.

[7] Frieze A, Kannan R, Vempala S.Fast Monte-carlo Algorithms for Finding Low-rank Approximations[J].Journal of the ACM, 2004, 51(6): 1025-1041.

[8] Rajaraman A, Ullman J D.Mining of Massive Datasets[M].Cambridge: Cambridge University Press, 2012.