?

目錄：

1.矩陣分解

? ? 1.1 矩陣分解的產(chǎn)生原因

? ? 1.2?矩陣分解作用

? ? 1.3?矩陣分解的方法

? ? 1.4?推薦學(xué)習(xí)的經(jīng)典矩陣分解算法

2. 特征值分解(EVD)

3. 奇異值分解(SVD)

4.?SVD++

5.SVD/SVD++在協(xié)同過濾中的應(yīng)用

?

1. 矩陣分解

1.1 矩陣分解的產(chǎn)生原因

在介紹矩陣分解之前，先讓我們明確下推薦系統(tǒng)的場景以及矩陣分解的原理。對于推薦系統(tǒng)來說存在兩大場景即評分預(yù)測（rating prediction）與Top-N推薦（item recommendation，item ranking）。

評分預(yù)測場景主要用于評價(jià)網(wǎng)站，比如用戶給自己看過的電影評多少分（MovieLens），或者用戶給自己看過的書籍評價(jià)多少分。其中矩陣分解技術(shù)主要應(yīng)用于該場景。

Top-N推薦場景主要用于購物網(wǎng)站或者一般拿不到顯式評分信息的網(wǎng)站，即通過用戶的隱式反饋信息來給用戶推薦一個(gè)可能感興趣的列表以供其參考。其中該場景為排序任務(wù)，因此需要排序模型來對其建模。因此，我們接下來更關(guān)心評分預(yù)測任務(wù)。

對于評分預(yù)測任務(wù)來說，我們通常將用戶和物品表示為二維矩陣的形式，其中矩陣中的某個(gè)元素表示對應(yīng)用戶對于相應(yīng)項(xiàng)目的評分，1-5分表示喜歡的程度逐漸增加，？表示沒有過評分記錄。推薦系統(tǒng)評分預(yù)測任務(wù)可看做是一個(gè)矩陣補(bǔ)全（Matrix Completion）的任務(wù)，即基于矩陣中已有的數(shù)據(jù)（observed data）來填補(bǔ)矩陣中沒有產(chǎn)生過記錄的元素（unobserved data）。值得注意的是，這個(gè)矩陣是非常稀疏的（Sparse）,?稀疏度一般能達(dá)到90%以上，因此如何根據(jù)極少的觀測數(shù)據(jù)來較準(zhǔn)確的預(yù)測未觀測數(shù)據(jù)一直以來都是推薦系統(tǒng)領(lǐng)域的關(guān)鍵問題。

其中，推薦系統(tǒng)的評分預(yù)測場景可看做是一個(gè)矩陣補(bǔ)全的游戲，矩陣補(bǔ)全是推薦系統(tǒng)的任務(wù)，矩陣分解是其達(dá)到目的的手段。因此，矩陣分解是為了更好的完成矩陣補(bǔ)全任務(wù)（欲其補(bǔ)全，先其分解之）。之所以可以利用矩陣分解來完成矩陣補(bǔ)全的操作，那是因?yàn)榛谶@樣的假設(shè)：假設(shè)UI矩陣是低秩的，即在大千世界中，總會存在相似的人或物，即物以類聚，人以群分，然后我們可以利用兩個(gè)小矩陣相乘來還原它。

1.2?矩陣分解作用

• 矩陣填充(通過矩陣分解來填充原有矩陣，例如協(xié)同過濾的ALS算法就是填充原有矩陣)
• 清理異常值與離群點(diǎn)
• 降維、壓縮
• 個(gè)性化推薦
• 間接的特征組合(計(jì)算特征間相似度)

1.3?矩陣分解的方法

• 特征值分解。

• PCA(Principal Component Analysis)主成分分析，分解，作用：降維、壓縮。

• SVD(Singular Value Decomposition)分解，也叫奇異值分解。

• LSI(Latent Semantic Indexing)或者叫LSA(Latent Semantic Analysis)，隱語義分析分解。

• PLSA(Probabilistic Latent Semantic Analysis)，概率潛在語義分析。PLSA和LDA都是主題模型，PLSA是判別式模型。

• NMF(Non-negative Matrix Factorization)，非負(fù)矩陣分解。非負(fù)矩陣分解能夠廣泛應(yīng)用于圖像分析、文本挖掘和語言處理等領(lǐng)域。

• LDA(Latent Dirichlet Allocation)模型，潛在狄利克雷分配模型。LDA是一種主題模型，將文檔集中每篇文檔的主題以概率的形式給出，可以用于主題聚類或者文本分類，是生成式模型。LDA作為主題模型可以應(yīng)用到很多領(lǐng)域，比如：文本情感分析、文本分類、個(gè)性化推薦、社交網(wǎng)絡(luò)、廣告預(yù)測等方面。

• MF(Matrix Factorization)模型，矩陣分解模型。矩陣分解其實(shí)可以分為很多種：

• 基本矩陣分解(Basic Matrix Factorization)，basic MF分解。

• 正則化矩陣分解(Regularized Matrix Factorization)。

• 概率矩陣分解(Probabilistic Matrix Factorization)，PMF。

• 非負(fù)矩陣分解(Non-negative Matrix Factorization)，NMF。

• 正交非負(fù)矩陣分解(Orthogonal Non-negative Matrix Factorization)。

• PMF(Probabilistic Matrix Factorization)，概率矩陣分解。

• SVD++

關(guān)于矩陣分解的方法大概就是上面這些。矩陣分解的主要應(yīng)用是：降維、聚類分析、數(shù)據(jù)預(yù)處理、低維度特征學(xué)習(xí)、特征學(xué)習(xí)、推薦系統(tǒng)、大數(shù)據(jù)分析等。上面把主要的矩陣分解方法給列出來了，比較混亂，再給大家擺上一張矩陣分解發(fā)展的歷史：

圖1：矩陣分解發(fā)展歷史

?

1.3 推薦學(xué)習(xí)的經(jīng)典矩陣分解算法

矩陣分解的算法這么多，給大家推薦幾個(gè)經(jīng)典的算法來學(xué)習(xí)：

1) 經(jīng)典的主成分分析(PCA)、奇異值分解(SVD)是機(jī)器學(xué)習(xí)入門必學(xué)算法。

2)2003年提出的主題模型(LDA)，在當(dāng)年提出的時(shí)候，也是大紅大紫，現(xiàn)在也在廣泛的應(yīng)用，可以學(xué)習(xí)一下。

3)概率矩陣分解(PMF)，主要應(yīng)用到推薦系統(tǒng)中，在大規(guī)模的稀疏不平衡Netflix數(shù)據(jù)集上取得了較好的結(jié)果。

4)非負(fù)矩陣分解(NMF)，也很重要。非負(fù)矩陣分解及其改進(jìn)版本應(yīng)用到很多領(lǐng)域中。

2.特征值分解(EVD)-理論推導(dǎo)

特征值分解和奇異值分解在機(jī)器學(xué)習(xí)中都是很常見的矩陣分解算法。兩者有著很緊密的關(guān)系，特征值分解和奇異值分解的目的都是一樣，就是提取出一個(gè)矩陣最重要的特征。

1）特征值、特征向量

如果一個(gè)向量v是矩陣A的特征向量，將一定可以表示成下面的形式：

其中，λ是特征向量v對應(yīng)的特征值，一個(gè)矩陣的一組特征向量是一組正交向量。

思考：為什么一個(gè)向量和一個(gè)數(shù)相乘的效果與一個(gè)矩陣和一個(gè)向量相乘的效果是一樣的呢？

答案：矩陣A與向量v相乘，本質(zhì)上是對向量v進(jìn)行了一次線性變換（旋轉(zhuǎn)或拉伸），而該變換的效果為常數(shù)λ乘以向量v。當(dāng)我們求特征值與特征向量的時(shí)候，就是為了求矩陣A能使哪些向量（特征向量）只發(fā)生伸縮變換，而變換的程度可以用特征值λ表示。矩陣變換遵循：左乘是進(jìn)行初等行變換，右乘是進(jìn)行初等列變換。Ref：初等矩陣左乘右乘 影響矩陣行列變換

2）特征值與特征向量的幾何意義

一個(gè)矩陣其實(shí)就是一個(gè)線性變換，因?yàn)橐粋€(gè)矩陣乘以一個(gè)向量后得到的向量，其實(shí)就相當(dāng)于將這個(gè)向量進(jìn)行了線性變換。比如說下面的這個(gè)矩陣：

它其實(shí)對應(yīng)的線性變換是圖2的形式：

圖2：矩陣M的線性變換

因?yàn)檫@個(gè)矩陣M乘以一個(gè)向量（x，y）的結(jié)果是：

上面的矩陣是對稱的，所以這個(gè)變換是一個(gè)對x、y軸的方向一個(gè)拉伸變換（每一個(gè)對角線上的元素將會對一個(gè)維度進(jìn)行拉伸變換，當(dāng)值大于1時(shí)是拉伸，當(dāng)值小于1時(shí)是縮短），如圖2所示。當(dāng)矩陣不是對稱的時(shí)候，假如說矩陣是下面的樣子：

它所描述的變換是下面的樣子：

圖3：M是非對稱矩陣變換

這其實(shí)是在平面上對一個(gè)軸進(jìn)行的拉伸變換，如圖3藍(lán)色的箭頭所示，藍(lán)色的箭頭是一個(gè)最主要的變換方向（變換的方向可能不止一個(gè)）。如果想要描述好一個(gè)變換，那我們就需要描述好這個(gè)變換主要的變化方向。

3）特征值分解

對于矩陣A，有一組特征向量v，將這組向量進(jìn)行正交化單位化，就能得到一組正交單位向量。特征值分解，就是將矩陣A分解為如下式：

其中，Q是矩陣A的特征向量組成的矩陣，則是一個(gè)對角陣，對角線上的元素就是特征值。我們來分析一下特征值分解的式子，分解得到的Σ矩陣是一個(gè)對角矩陣，里面的特征值是由大到小排列的，這些特征值所對應(yīng)的特征向量就是描述這個(gè)矩陣變換方向（從主要的變化到次要的變化排列）。

當(dāng)矩陣是高維的情況下，那么這個(gè)矩陣就是高維空間下的一個(gè)線性變換，這個(gè)線性變換可能沒法通過圖片來表示，但是可以想象，這個(gè)變換也同樣有很多的變化方向，我們通過特征值分解得到的前N個(gè)特征向量，就對應(yīng)了這個(gè)矩陣最主要的N個(gè)變化方向。我們利用這前N個(gè)變化方向，就可以近似這個(gè)矩陣變換。也就是之前說的：提取這個(gè)矩陣最重要的特征。

總結(jié)：特征值分解可以得到特征值與特征向量，特征值表示的是這個(gè)特征到底有多么重要，而特征向量表示這個(gè)特征是什么，可以將每一個(gè)特征向量理解為一個(gè)線性的子空間，我們可以利用這些線性的子空間干很多事情。不過，特征值分解也有很多的局限，比如說變換的矩陣必須是方陣。

4)特征值分解的例子

這里我們用一個(gè)簡單的方陣來說明特征值分解的步驟。我們的方陣A定義為：

首先，由方陣A的特征方程，求出特征值。

特征值為（重?cái)?shù)是2）。

然后，把每個(gè)特征值λ帶入線性方程組，求出特征向量。

當(dāng)λ=2時(shí)，解線性方程組?。

解得。特征向量為：。

當(dāng)λ=1時(shí)，解線性方程組?

。特征向量為：。

最后，方陣A的特征值分解為：

特征值特征向量的求解還可以參考求解矩陣特征值及特征向量

3. 奇異值分解(SVD)-理論推導(dǎo)

1)特征值分解矩陣的缺點(diǎn): 只能針對方陣，但是我們要分解的大部分都不是方陣

我們前面講了很多特征值、特征向量和特征值分解，而且基于我們以前學(xué)習(xí)的線性代數(shù)知識，利用特征值分解提取特征矩陣是一個(gè)容易理解且便于實(shí)現(xiàn)的方法。但是為什么還存在奇異值分解呢？特征值分解最大的問題是只能針對方陣，即n*n的矩陣。而在實(shí)際的應(yīng)用中，我們分解的大部分都不是方陣。

舉個(gè)例子：

關(guān)系型數(shù)據(jù)庫中的某一張表的數(shù)據(jù)存儲結(jié)構(gòu)就類似于一個(gè)二維矩陣，假設(shè)這個(gè)表有m行，有n個(gè)字段，那么這個(gè)表數(shù)據(jù)矩陣規(guī)模就是m*n。很明顯，在絕大部分情況下，m與n是不相等的。如果這個(gè)時(shí)候要對這個(gè)矩陣進(jìn)行特征提取，特征值分解的方法明顯就不行了。此時(shí)，就可以用SVD對非方陣矩陣進(jìn)行分解。

2)奇異值分解

奇異值分解是一個(gè)能適用于任意矩陣的一種分解的方法，對于任意矩陣A總是存在一個(gè)奇異值分解：

假設(shè)A是一個(gè)m*n的矩陣，那么得到的U是一個(gè)m*m的方陣，U里面的正交向量被稱為左奇異向量。Σ是一個(gè)m*n的矩陣，Σ除了對角線其它元素都為0，對角線上的元素稱為奇異值。是V的轉(zhuǎn)置矩陣，是一個(gè)n*n的矩陣，它里面的正交向量被稱為右奇異值向量。而且一般來講，我們會將Σ上的值按從大到小的順序排列。上面矩陣的維度變化可以參照圖4所示。

圖4：奇異值分解中各個(gè)矩陣維度變化

思考：雖說上面奇異值分解等式成立，但是如何求得左奇異向量、右奇異向量和奇異值呢？

答案：由上面的奇異值分解等式，我們是不知道如何拆分矩陣A的。我們可以把奇異值和特征值聯(lián)系起來。

首先，我們將A和A的轉(zhuǎn)置做矩陣的乘法，得到一個(gè)方陣，用這樣的方陣進(jìn)行特征分解，得到的特征和特征向量滿足下面的等式：

這里的?就是左奇異向量。

其次，我們用矩陣A的轉(zhuǎn)置乘以A，得到一個(gè)方陣，用這樣的方陣進(jìn)行特征分解，得到的特征值和特征向量滿足下面的等式：

這里的就是我們要求的右奇異向量。

思考：上面我們說的特征向量組成的就是我們SVD中的U矩陣?，而的特征向量組成的矩陣就是我們SVD中的V矩陣，這有什么根據(jù)么?我們來證明一下，以V矩陣的證明為例。

上式證明中使用了。與特征值分解??對比可以看出的特征向量組成的矩陣就是我們SVD中的V矩陣，?的特征向量組成的就是我們SVD中的U矩陣。

補(bǔ)充定義：

此外，我們還可以得到奇異值，奇異值求法有兩種：

a) 第一種：

b)第二種：

通過上面公式的證明，我們還可以看出，特征值矩陣等于奇異值矩陣的平方，也就是說特征值和奇異值滿足如下關(guān)系：

這里的就是奇異值，奇異值跟特征值類似，在矩陣Σ中也是從大到小排列。

思考：我們已經(jīng)知道如何用奇異值分解任何矩陣了，那么問題又來了，一個(gè)m*n的矩陣A，你把它分解成m*m的矩陣U、m*n的矩陣Σ和n*n的矩陣。這三個(gè)矩陣中任何一個(gè)的維度似乎一點(diǎn)也不比A的維度小，而且還要做兩次矩陣的乘法，這不是沒事找事干嘛！把簡單的事情搞復(fù)雜了么！并且我們知道矩陣乘法的時(shí)間復(fù)雜度為。那奇異值分解到底要怎么做呢？

補(bǔ)充：兩個(gè)矩陣A:m*n，B:n*p相乘，時(shí)間復(fù)雜度（O(nmp)）。分析偽代碼如下：

input:int A[m,n],B[n,p] Let C be a new matrix of the appropriate sizefor i in 1 to m ? ?for j in 1 to pLet sum = 0 ?for k in 1 to n ? ?sum += A[i,k]*B[k,j] ?Set Cij = sum

所以兩個(gè)矩陣相乘的時(shí)間復(fù)雜度是。

答案：在奇異值分解矩陣中Σ里面的奇異值按從大到小的順序排列，奇異值從大到小的順序減小的特別快。在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上。也就是說，剩下的90%甚至99%的奇異值幾乎沒有什么作用。因此，我們可以用前面r個(gè)大的奇異值來近似描述矩陣，于是奇異值分解公式可以寫成如下：

其中r是一個(gè)遠(yuǎn)遠(yuǎn)小于m和n的數(shù)，右邊的三個(gè)矩陣相乘的結(jié)果將會使一個(gè)接近A的矩陣。如果r越接近于n，則相乘的結(jié)果越接近于A。如果r的取值遠(yuǎn)遠(yuǎn)小于n，從計(jì)算機(jī)內(nèi)存的角度來說，右邊三個(gè)矩陣的存儲內(nèi)存要遠(yuǎn)遠(yuǎn)小于矩陣A的。所以在奇異值分解中r的取值很重要，就是在計(jì)算精度和時(shí)間空間之間做選擇。

3)SVD計(jì)算舉例

這里我們用一個(gè)簡單的矩陣來說明奇異值分解的步驟。我們的矩陣A定義為：

3.3 SVD分解的應(yīng)用

異值分解的應(yīng)用有很多，比如：用SVD解PCA、潛在語言索引也依賴于SVD算法。可以說，SVD是矩陣分解、降維、壓縮、特征學(xué)習(xí)的一個(gè)基礎(chǔ)的工具，所以SVD在機(jī)器學(xué)習(xí)領(lǐng)域相當(dāng)?shù)闹匾?/p>

1)降維。

通過奇異值分解的公式，我們可以很容易看出來，原來矩陣A的特征有n維。經(jīng)過SVD分解后，可以用前r個(gè)非零奇異值對應(yīng)的奇異向量表示矩陣A的主要特征，這樣就把矩陣A進(jìn)行了降維。

2)壓縮。

通過奇異值分解的公式，我們可以看出來，矩陣A經(jīng)過SVD分解后，要表示原來的大矩陣A，我們只需要存儲U、Σ、V三個(gè)較小的矩陣即可。而這三個(gè)較小規(guī)模的矩陣占用內(nèi)存上也是遠(yuǎn)遠(yuǎn)小于原有矩陣A的，這樣SVD分解就起到了壓縮的作用。

?

4.SVD/SVD++ 應(yīng)用于協(xié)同過濾（附Python實(shí)現(xiàn)）

上面第二、三節(jié)完成了SVD、SVD++的理論推導(dǎo)，證明了要預(yù)測用戶對電影的評分，也就是補(bǔ)全稀疏U-I矩陣中的缺省值，但是這個(gè)矩陣稀疏度一般能達(dá)到90%，很難通過極少的觀測數(shù)據(jù)來預(yù)測缺省值，要完成矩陣補(bǔ)全可以通過將m*n維的U-I矩陣進(jìn)行SVD/SVD++矩陣分解得到矩陣、，用這兩個(gè)小矩陣相乘來還原他，這兩個(gè)小矩陣都是稠密矩陣，可以通過訓(xùn)練得到。因此接下來我們要討論的就是怎么根據(jù)訓(xùn)練樣本得到、。

4.1?奇異值分解(SVD)?

考慮CF中最為常見的用戶給電影評分的場景，我們需要一個(gè)數(shù)學(xué)模型來模擬用戶給電影打分的場景，比如對評分進(jìn)行預(yù)測。

將評分矩陣U看作是兩個(gè)矩陣的乘積：

其中，uxy?可以看作是user x對電影的隱藏特質(zhì)y的熱衷程度，而iyz可以看作是特質(zhì) y 在電影 z中的體現(xiàn)程度。那么上述模型的評分預(yù)測公式為：

q 和 p 分別對應(yīng)了電影和用戶在各個(gè)隱藏特質(zhì)上的特征向量。

以上的模型中，用戶和電影都體現(xiàn)得無差別，例如某些用戶非常挑剔，總是給予很低的評分；或是某部電影拍得奇爛，惡評如潮。為了模擬以上的情況，需要引入 baseline predictor.

其中 μ 為所有評分基準(zhǔn)，bi 為電影 i 的評分均值相對μ的偏移，bu 類似。注意，這些均為參數(shù)，需要通過訓(xùn)練得到具體數(shù)值，不過可以用相應(yīng)的均值作為初始化時(shí)的估計(jì)。

模型參數(shù)bi,bu,qi,pu通過最優(yōu)化下面這個(gè)目標(biāo)函數(shù)獲得：

可以用梯度下降方法或迭代的最小二乘算法求解。在迭代最小二乘算法中，首先固定pu優(yōu)化qi，然后固定qi優(yōu)化pu，交替更新。梯度下降方法中參數(shù)的更新式子如下（為了簡便，把目標(biāo)函數(shù)中的μ+bi+bu+q?ipu整體替換為r^ui）：

其中α是更新步長。

具體代碼請參考：SVD --應(yīng)用于協(xié)同過濾（附Python實(shí)現(xiàn)）

4.2?SVD++：

某個(gè)用戶對某個(gè)電影進(jìn)行了評分，那么說明他看過這部電影，那么這樣的行為事實(shí)上蘊(yùn)含了一定的信息，因此我們可以這樣來理解問題：評分的行為從側(cè)面反映了用戶的喜好，可以將這樣的反映通過隱式參數(shù)的形式體現(xiàn)在模型中，從而得到一個(gè)更為精細(xì)的模型，便是 SVD++.

其中 I(u) 為該用戶所評價(jià)過的所有電影的集合，yj為隱藏的“評價(jià)了電影 j”反映出的個(gè)人喜好偏置。收縮因子取集合大小的根號是一個(gè)經(jīng)驗(yàn)公式，并沒有理論依據(jù)。

模型參數(shù)bi,bu,qi,pu,yj通過最優(yōu)化下面這個(gè)目標(biāo)函數(shù)獲得：

與SVD方法類似，可以通過梯度下降算法進(jìn)行求解。

具體代碼請參考：SVD應(yīng)用于協(xié)同過濾改良版之SVD++（附Python實(shí)現(xiàn)）

具體訓(xùn)練步驟：

1.首先根據(jù)統(tǒng)計(jì)數(shù)據(jù)對矩陣U、V，bi，bu，y進(jìn)行初始化

2.根據(jù)已知參數(shù)計(jì)算評分預(yù)測值p

3.根據(jù)誤差，利用隨機(jī)梯度下降法 對參數(shù)進(jìn)行更新。

?

Ref：

SVD與SVD++??https://www.cnblogs.com/nolonely/p/7337619.html

SVD應(yīng)用于協(xié)同過濾改良版之SVD++（附Python實(shí)現(xiàn)）??https://zhuanlan.zhihu.com/p/42269534

推薦系統(tǒng)之矩陣分解家族?https://zhuanlan.zhihu.com/p/35262187

機(jī)器學(xué)習(xí)中SVD總結(jié)??https://mp.weixin.qq.com/s/Dv51K8JETakIKe5dPBAPVg

?

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的矩阵分解之: 特征值分解(EVD)、奇异值分解(SVD)、SVD++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。