轉(zhuǎn)載請(qǐng)聲明出處http://blog.csdn.net/zhongkejingwang/article/details/43083603

? ? 前面文章SVD原理及推導(dǎo)已經(jīng)把SVD的過(guò)程講的很清楚了，本文介紹如何將SVD應(yīng)用于推薦系統(tǒng)中的評(píng)分預(yù)測(cè)問(wèn)題。其實(shí)也就是復(fù)現(xiàn)Koren在NetFlix大賽中的使用到的SVD算法以及其擴(kuò)展出的RSVD、SVD++。

? ?記得剛接觸SVD是在大二，那會(huì)兒跟師兄在做項(xiàng)目的時(shí)候就用到這個(gè)東西，然后到大三下學(xué)期剛好百度舉辦了一個(gè)電影推薦算法大賽，躍躍欲試地參加了，當(dāng)時(shí)就用的SVD而且只會(huì)用這個(gè)，后來(lái)覺(jué)得效果還不錯(cuò)，接著就又找來(lái)了Koren的論文，看了一下把SVD++也實(shí)現(xiàn)了，把兩者結(jié)果融合得到不少的提升。下面是最終比賽結(jié)果：

? ? ? ? ? ? ? ? ? ? ? ??

其實(shí)這個(gè)最終結(jié)果是和第11名組隊(duì)后融合了他的結(jié)果，所以成績(jī)是一樣的。但是單純地使用SVD、SVD++融合得到的結(jié)果最好的也能到0.606左右，這個(gè)結(jié)果已經(jīng)很牛逼了，記得當(dāng)時(shí)0.6111在榜上維持了兩個(gè)多星期的No.1。當(dāng)時(shí)的遺憾就是沒(méi)能實(shí)現(xiàn)更多的SVD擴(kuò)展算法，導(dǎo)致融合的結(jié)果沒(méi)法再提升，代碼也由于時(shí)間倉(cāng)促寫(xiě)的很臃腫，前段時(shí)間有空把算法重寫(xiě)了一下并實(shí)現(xiàn)了更多的擴(kuò)展算法，已經(jīng)共享到github上了，有興趣的可以看看：https://github.com/jingchenUSTC/SVDRecommenderSystem

? ? 下面開(kāi)始介紹SVD算法，假設(shè)存在以下user和item的數(shù)據(jù)矩陣：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

這是一個(gè)極其稀疏的矩陣，這里把這個(gè)評(píng)分矩陣記為R，其中的元素表示user對(duì)item的打分，“？”表示未知的，也就是要你去預(yù)測(cè)的，現(xiàn)在問(wèn)題來(lái)了：如何去預(yù)測(cè)未知的評(píng)分值呢？上一篇文章用SVD證明了對(duì)任意一個(gè)矩陣A，都有它的滿秩分解：

? ? ? ? ? ? ?

? ?那么剛才的評(píng)分矩陣R也存在這樣一個(gè)分解，所以可以用兩個(gè)矩陣P和Q的乘積來(lái)表示評(píng)分矩陣R：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

上圖中的U表示用戶數(shù)，I表示商品數(shù)。然后就是利用R中的已知評(píng)分訓(xùn)練P和Q使得P和Q相乘的結(jié)果最好地?cái)M合已知的評(píng)分，那么未知的評(píng)分也就可以用P的某一行乘上Q的某一列得到了：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

這是預(yù)測(cè)用戶u對(duì)商品i的評(píng)分，它等于P矩陣的第u行乘上Q矩陣的第i列。這個(gè)是最基本的SVD算法，那么如何通過(guò)已知評(píng)分訓(xùn)練得到P和Q的具體數(shù)值呢？

假設(shè)已知的評(píng)分為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

則真實(shí)值與預(yù)測(cè)值的誤差為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

繼而可以計(jì)算出總的誤差平方和：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

只要通過(guò)訓(xùn)練把SSE降到最小那么P、Q就能最好地?cái)M合R了。那又如何使SSE降到最小呢？下面介紹一個(gè)常用的局部?jī)?yōu)化算法。

梯度下降法

? ?為了說(shuō)明梯度下降法，我找了一張PPT：

也就是說(shuō)如果要最小化目標(biāo)函數(shù)，必須往其負(fù)梯度方向搜索。這就是梯度下降法，注意它是一個(gè)局部?jī)?yōu)化算法，也就是說(shuō)有可能落到局部最優(yōu)解而不是全局最優(yōu)解。

Basic SVD

利用梯度下降法可以求得SSE在Puk變量（也就是P矩陣的第u行第k列的值）處的梯度：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

利用求導(dǎo)鏈?zhǔn)椒▌t，e^2先對(duì)e求導(dǎo)再乘以e對(duì)Puk的求導(dǎo)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

由于

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

所以

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

上式中括號(hào)里的那一坨式子如果展開(kāi)來(lái)看的話，其與Puk有關(guān)的項(xiàng)只有PukQki，其他的無(wú)關(guān)項(xiàng)對(duì)Puk的求導(dǎo)均等于0

所以求導(dǎo)結(jié)果為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

所以

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

為了讓式子更簡(jiǎn)潔，令

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

這樣做對(duì)結(jié)果沒(méi)有影響，只是為了把求導(dǎo)結(jié)果前的2去掉，更好看點(diǎn)。得到

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

現(xiàn)在得到了目標(biāo)函數(shù)在Puk處的梯度了，那么按照梯度下降法，將Puk往負(fù)梯度方向變化：

令更新的步長(zhǎng)（也就是學(xué)習(xí)速率）為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

則Puk的更新式為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

同樣的方式可得到Qik的更新式為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

得到了更新的式子，現(xiàn)在開(kāi)始來(lái)討論這個(gè)更新要怎么進(jìn)行。有兩種選擇：1、計(jì)算完所有已知評(píng)分的預(yù)測(cè)誤差后再對(duì)P、Q進(jìn)行更新。2、每計(jì)算完一個(gè)eui后立即對(duì)Pu和qi進(jìn)行更新。這兩種方式都有名稱，分別叫：1、批梯度下降。2、隨機(jī)梯度下降。兩者的區(qū)別就是批梯度下降在下一輪迭代才能使用本次迭代的更新值，隨機(jī)梯度下降本次迭代中當(dāng)前樣本使用的值可能就是上一個(gè)樣本更新的值。由于隨機(jī)性可以帶來(lái)很多好處，比如有利于避免局部最優(yōu)解，所以現(xiàn)在大多傾向于使用隨機(jī)梯度下降進(jìn)行更新。

RSVD

? ?上面就是基本的SVD算法，但是，問(wèn)題來(lái)了，上面的訓(xùn)練是針對(duì)已知評(píng)分?jǐn)?shù)據(jù)的，過(guò)分地?cái)M合這部分?jǐn)?shù)據(jù)有可能導(dǎo)致模型的測(cè)試效果很差，在測(cè)試集上面表現(xiàn)很糟糕。這就是過(guò)擬合問(wèn)題，關(guān)于過(guò)擬合與欠擬合可以看一下這張圖

第一個(gè)是欠擬合，第二個(gè)剛好，第三個(gè)過(guò)擬合。那么如何避免過(guò)擬合呢？那就是在目標(biāo)函數(shù)中加入正則化參數(shù)（加入懲罰項(xiàng)），對(duì)于目標(biāo)函數(shù)來(lái)說(shuō)，P矩陣和Q矩陣中的所有值都是變量，這些變量在不知道哪個(gè)變量會(huì)帶來(lái)過(guò)擬合的情況下，對(duì)所有變量都進(jìn)行懲罰：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

這時(shí)候目標(biāo)函數(shù)對(duì)Puk的導(dǎo)數(shù)就發(fā)生變化了，現(xiàn)在就來(lái)求加入懲罰項(xiàng)后的導(dǎo)數(shù)。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

括號(hào)里第一項(xiàng)對(duì)Puk的求導(dǎo)前面已經(jīng)求過(guò)了，第二項(xiàng)對(duì)Puk的求導(dǎo)很容易求得，第三項(xiàng)與Puk無(wú)關(guān)，導(dǎo)數(shù)為0，所以

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

同理可得SSE對(duì)qik的導(dǎo)數(shù)為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

將這兩個(gè)變量往負(fù)梯度方向變化，則更新式為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

這就是正則化后的SVD，也叫RSVD。

加入偏置的SVD、RSVD

? ?關(guān)于SVD算法的變種太多了，叫法也不統(tǒng)一，在預(yù)測(cè)式子上加點(diǎn)參數(shù)又會(huì)出來(lái)一個(gè)名稱。由于用戶對(duì)商品的打分不僅取決于用戶和商品間的某種關(guān)系，還取決于用戶和商品獨(dú)有的性質(zhì)，Koren將SVD的預(yù)測(cè)公式改成這樣

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

第一項(xiàng)為總的平均分，bu為用戶u的屬性值，bi為商品i的屬性值，加入的這兩個(gè)變量在SSE式子中同樣需要懲罰，那么SSE就變成了下面這樣：

? ??

由上式可以看出SSE對(duì)Puk和qik的導(dǎo)數(shù)都沒(méi)有變化，但此時(shí)多了bu和bi變量，同樣要求出其更新式。首先求SSE對(duì)bu的導(dǎo)數(shù)，只有第一項(xiàng)和第四項(xiàng)和bu有關(guān)，第一項(xiàng)對(duì)bu的求導(dǎo)和之前的求導(dǎo)類似，用鏈?zhǔn)椒▌t即可求得，第四項(xiàng)直接求導(dǎo)即可，最后可得偏導(dǎo)數(shù)為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

同理可得對(duì)bi的導(dǎo)數(shù)為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

所以往其負(fù)梯度方向變化得到其更新式為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

這就是修改后的SVD（RSVD）。

ASVD

? ? 全稱叫Asymmetric-SVD，即非對(duì)稱SVD，其預(yù)測(cè)式子為

R(u)表示用戶u評(píng)過(guò)分的商品集合，N(u)表示用戶u瀏覽過(guò)但沒(méi)有評(píng)過(guò)分的商品集合，Xj和Yj是商品的屬性。這個(gè)模型很有意思，看預(yù)測(cè)式子，用戶矩陣P已經(jīng)被去掉了，取而代之的是利用用戶評(píng)過(guò)分的商品和用戶瀏覽過(guò)尚未評(píng)分的商品屬性來(lái)表示用戶屬性，這有一定的合理性，因?yàn)橛脩舻男袨橛涗洷旧砭湍芊磻?yīng)用戶的喜好。而且，這個(gè)模型可以帶來(lái)一個(gè)很大的好處，一個(gè)商場(chǎng)或者網(wǎng)站的用戶數(shù)成千上萬(wàn)甚至過(guò)億，存儲(chǔ)用戶屬性的二維矩陣會(huì)占用巨大的存儲(chǔ)空間，而商品數(shù)卻沒(méi)有那么多，所以這個(gè)模型的好處顯而易見(jiàn)。但是它有個(gè)缺點(diǎn)，就是迭代時(shí)間太長(zhǎng)了，這是可以預(yù)見(jiàn)的，以時(shí)間換空間嘛。

同樣的，需要計(jì)算其各個(gè)參數(shù)的偏導(dǎo)數(shù)，求出更新式，顯然，bu和bi的更新式和剛才求出的一樣

其中的向量z等于下面這坨

? ? ? ? ? ? ? ? ? ? ? ?

現(xiàn)在要求qik、x和y的更新式，在這里如果把z看成Pu則根據(jù)前面求得的更新式可得qik的更新式：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

求Xj的導(dǎo)數(shù)需要有點(diǎn)耐心，SSE的第二項(xiàng)對(duì)Xj的導(dǎo)數(shù)很容易得到，現(xiàn)在來(lái)求第一項(xiàng)對(duì)Xj的導(dǎo)數(shù)：

???

上式求和符中的i,j都是屬于R(u)的，可以看到Zm只有當(dāng)m==k時(shí)才與Xjk有關(guān)，所以

? ? ??

因?yàn)?/p>

? ? ? ??

所以

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

所以得到SSE對(duì)Xjk的導(dǎo)數(shù)為

??????????????????

同理可得SSE對(duì)Yjk的導(dǎo)數(shù)為

?????????????????????????????????

所以得到Xjk和Yjk的更新方程

??????????????

?????????????????????????

這就叫ASVD。。。。。。

SVDPP

? ? 最后這個(gè)模型也是Koren文章中提到的，SVDPlusPlus（SVD++），它的預(yù)測(cè)式子為

? ? ? ? ? ? ? ? ? ? ? ? ? ?

這里的N(u)表示用戶u行為記錄（包括瀏覽的和評(píng)過(guò)分的商品集合）。看了ASVD的更新式推導(dǎo)過(guò)程再來(lái)看這個(gè)應(yīng)該很簡(jiǎn)單，Puk和qik的更新式子不變，Yjk的更新式子和ASVD的更新式一樣：

??????????????????????????????????

? ? 這些就是Koren在NetFlix大賽中用到的SVD算法，最后，還有一個(gè)需要提的：

對(duì)偶算法

? ? 將前面預(yù)測(cè)公式中的u和i調(diào)換位置得到其對(duì)偶算法，對(duì)于RSVD而言，u和i的位置是等價(jià)的、對(duì)稱的，所以其對(duì)偶算法和其本身沒(méi)有區(qū)別，但對(duì)于ASVD和SVD++則不同，有時(shí)候?qū)ε妓惴ǖ玫降慕Y(jié)果更加精確，并且，如果將對(duì)偶算法和原始算法的預(yù)測(cè)結(jié)果融合在一起的話，效果的提升會(huì)讓你吃驚！

對(duì)偶的ASVD預(yù)測(cè)公式：

這里R(i)表示評(píng)論過(guò)商品i的用戶集合，N(i)表示瀏覽過(guò)商品i但沒(méi)有評(píng)論的用戶集合。由于用戶數(shù)量龐大，所以對(duì)偶的ASVD會(huì)占用很大空間，這里需要做取舍了。

對(duì)偶的SVD++預(yù)測(cè)公式：

? ? ??

這里N(i)表示對(duì)商品i有過(guò)行為（瀏覽或評(píng)分）的用戶集合。

實(shí)現(xiàn)這一對(duì)偶的操作其實(shí)很簡(jiǎn)單，只要讀取數(shù)據(jù)的時(shí)候把用戶id和商品id對(duì)調(diào)位置即可，也就是將R矩陣轉(zhuǎn)置后再訓(xùn)練。

? ? 暫時(shí)實(shí)現(xiàn)的算法就這些，代碼都在github上了，有興趣的可以看看，地址：https://github.com/jingchenUSTC/SVDRecommenderSystem

總結(jié)

以上是生活随笔為你收集整理的SVD在推荐系统中的应用详解以及算法推导的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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