矩陣分解是最近幾年比較火的算法，經過kddcup和netflix比賽的多人多次檢驗，矩陣分解可以帶來更好的結果，而且可以充分地考慮各種因素的影響，有非常好的擴展性，因為要考慮多種因素的綜合作用，往往需要構造cost function來將矩陣分解問題轉化為優化問題，根據要考慮的因素為優化問題添加constraints，然后通過迭代的方法進行矩陣分解，原來評分矩陣中的missing vlaue可以通過分解后得到的矩陣求的。
本文將簡單介紹下最近學習到的矩陣分解方法。
（1）PureSvd
怎么評價這種方法呢？開始覺得這種方法很神奇很數學，而且在實際使用的時候也非常好用。
但最近讀了Yehuda大神的paper之后，覺得這種方法比較猥瑣。
其實，矩陣分解的核心是將一個非常稀疏的評分矩陣分解為兩個矩陣，一個表示user的特性，一個表示item的特性，將兩個矩陣中各取一行和一列向量做內積就可以得到對應評分。
那么如何將一個矩陣分解為兩個矩陣就是唯一的問題了。
說到這里大家就可能想起了在線代和數值分析中學到的各種矩陣分解方法，QR，Jordan，三角分解，SVD。。。
這里說說svd分解。
svd是將一個任意實矩陣分解為三個矩陣U,S,V，其中，U,V是兩個正交矩陣，稱為左右奇異矩陣，S是個對角陣，稱為奇異值矩陣。
其實svd分解的問題可以化解為特征值分解的問題。
評分矩陣A(m*n)=U(m*k)*S(k*k)*V'(k*n)
令B(m*m)=A(m*n)*A'(n*m)
B矩陣就是一個方陣，可以利用各種簡單的方法將B進行特征值分解：
Bv=av，
v是方陣B的特征向量，a是特征向量v對應的特征值。
所以奇異值s=sqrt(a)，
左奇異向量u=A*v/s
同樣的方法可以求得右奇異向量。
這樣我們就得到了svd分解后的三個矩陣。（你可以自己寫個c程序計算，當然也可以用matlab算算得到）
分解后的三個矩陣都有著各自的意義，
U：每一行表示一個user的特征。
V：每一列表示一個item的特征。
S：表示對應的user和item的相關性。
所以可以考慮用U和V將S吸收進來，形成兩個矩陣分別表示user的矩陣和item的矩陣。
得到這個以后后面的事情就好辦了。
為什么說這個方法猥瑣呢？
因為我覺得，這種方法有著矩陣分解算法的表，卻可以非常簡單地完成矩陣的分解，然后填充稀疏的評分矩陣。
但它考慮的因素太少了，不過對于簡單的推薦系統，這種方法還是非常有意義的，容易實現，而且結果也不會太差。
（2）Latent Factor Model
這是真正的矩陣分解算法，經過實踐檢驗，具有非常高的準確性和易擴展性。
正如上面提到的，實現推薦系統結果的目標是將那個稀疏的評分矩陣分解成兩個矩陣，一個表示user的feature，一個表示item的feature，然后做內積得到預測。
當然要實現滿足一定約束條件的矩陣分解，可不像上面的PureSVD那樣容易，需要構造一個優化問題，用一些復雜的算法求解優化問題。而這些優化問題往往是NP問題，只有局部最優解。
首先構造一個優化目標函數，
考慮到最后的評價指標是預測分值和實際分值之間的誤差的平方（RMSE），所以構造的目標函數也是誤差的平方的函數。
為什么這樣的算法可以得到更優的結果呢？因為算法可以很容易地擴展很多的feature進來，更加出色地考慮了多種影響推薦效果的實實在在的因素。
?
因為有的用戶總是會打出比別人高的分，或者說有的用戶他的評價尺度比較寬松；同樣有的item總是被打高分。這是一個普遍存在的問題，所以在構造目標函數的時候需要增加幾項：所有評分的平均值miu，user的偏見分數bu，item的偏見分數bi。
比如：求用戶x對電影y的打分，
所有評分電影的評分的平均分是miu=3.5，
電影y比所有評分電影平均分高bi=0.5
但是用戶x是個比較嚴格的用戶，評分總是相對偏低，所以bu=-0.3
所以用戶x對電影y的打分為3.7
用戶在使用web應用的時候，會產生大量的行為，充分挖掘這部分的價值，將會很好地提升推薦的效果。
利用用戶的隱式反饋，相當于充分的利用了評分矩陣中的missing value的價值，用戶在頁面的停留時間，檢索，瀏覽，點擊等等各種行為都可以建模，內含到目標函數中。
這里，可以將簡單地用一個Boolean來描述一種行為有還是沒有。
不過在使用的時候，需要進行歸一化處理。
- User-associated attributes
基于用戶的社會化屬性進行推薦也是一種很基本的推薦，當然也可以考慮到目標函數中。
用戶的興趣包括長期和短期，動態地考慮一段時間內用戶的興趣是很有必要的。
上面的幾個因素中隨著時間變化的有，user的bias項bu=bu(t)，item的bias項bi=bi(t)，以及user的factor向量pu=pu(t)，這里可以忽略item的factor向量的變化，因為item是比較穩定的。
因為在處理上述的因素的時候，很多都是比較主觀的，所以需要給每個因素添加一個置信權重，以平衡整個結果。
通過構造出這個目標函數，然后添加相應的約束條件，接下來的問題就是求解這個優化問題。
通常比較好的方法是Stochastic gradient desent。
PS：這種方法是現在學術界的主流方法，大家可以參閱Yehuda的神作（http://research.yahoo.com/Yehuda_Koren）以及上海交大在今年kddcup獲獎方法的paper以及他們的開源系統（http://apex.sjtu.edu.cn/apex_wiki/svdfeature）
?
?
?
（3）NMF（非負矩陣分解）
很多人用這種方法是因為他們覺得只有一個非負的值對于實際的例子才會有意義。
考慮到svd或者latent factor model會得到負的值，所以這種方法的物理意義比較明確。
同樣的道理，NMF也是將評分矩陣的轉置矩陣分解成兩個矩陣。
不同的是這兩個矩陣有著和上面的矩陣不同的物理意義。
其中一個是基矩陣W，另一個是投影矩陣H，即R'(n*m)=W(n*r)*H(r*m)
W：每一列包含一個基向量，這組基向量構成一個r維的空間。
H：每一列則近似為原始數據對應的列向量在該r維空間的投影。
做這個分解的方法也是構造一個目標函數和一些約束條件，然后用梯度下降的算法來計算得到一個局部最優解。
這種方法的思路大概是這樣的：
?
- 將評分矩陣轉置然后分解成兩個矩陣W和H。
- 根據基矩陣W，可以計算得到目標用戶評分向量a對基矩陣W的投影向量h。
- 計算投影向量h與投影矩陣H各行之間的歐式距離，將其中距離最小的前k個用戶組成目標用戶a的最近鄰集合。
- 然后用皮爾遜相關法將最近鄰集合中的數據進行加權計算，然后排序進行推薦。
可以看出來，這種方法的思路和上面的兩種還是很不相同的，主要還是在計算目標用戶的最近鄰集合，主要思想還是knn，只是在中間用了矩陣分解的方法降維降低了計算的時間復雜度。
矩陣分解在學習的時候感覺既沒用又麻煩，尤其是線代里面做矩陣的分解計算，無聊的很。
現在看來，矩陣分解非常有意義。
續：
最近研究了下Yehuda大神的paper，學習了下矩陣分解方法在推薦系統中如何用。
本文中提到的矩陣分解是一般的分解，即R=M*N的形式。
1、矩陣分解方法的來源
CF里的矩陣分解思想是來自于IR領域的Latent Semantic Analysis(LSA)。google黑板報的《數學之美》中很清楚地講了SVD分解在IR中的應用。（http://www.google.com.hk/ggblog/googlechinablog/2006/12/blog-post_8935.html）
2、矩陣分解的優劣
優點是：
?
- 比較容易編程實現
- 比較低的時間和空間復雜度
- 預測的精度比較高
- 非常好的擴展性
缺點是：推薦的結果不具有很好的可解釋性。因為把ratings matrix分解成user-factor matrix和item-factor matrix，這里的factor很難用實際意義的概念來解釋。不過，矩陣分解的過程相當于一個軟聚類的過程，得到的每一個factor相當于每一個聚類后的分組，只是我們沒有一個通用的方法來為這些分組命名。
但是在實際的應用中，我們可以提取這些分組中最突出的特點來給這些factor命名。比如，拿新聞資訊類的推薦系統來說，做好分解之后，每個factor都可以看成是一類資訊，可以從這些資訊中提取一些特征來給這個factor命名。
3、矩陣分解的模型（Latent Factor Model）
矩陣分解的思路是把評分矩陣通過分解，用一個低秩的矩陣來逼近原來的評分矩陣，逼近的目標就是讓預測的矩陣和原來的矩陣之間的誤差平方最小。（矩陣分解一般不用數學上直接分解的辦法，盡管分解出來的精度很高，但是效率實在太低！矩陣分解往往會轉化為一個優化問題，通過迭代求局部最優解。）
但是有個問題是，原來的評分矩陣的稀疏度太大，分解很容易產生overfitting（過度擬合，意思就是為了遷就一些錯誤的偏僻的值導致整個模型錯誤）的問題。所以現在的方法是在目標函數中增加一項regularization(正則化)，來避免overfitting問題。
所以一般的矩陣分解的目標函數（或者稱為loss function）是：
前一項是預測后的矩陣和現有的評分矩陣的誤差，這里計算只針對評分矩陣中已經評分的項。
后一項就是正則化項，用來解決過度擬合的問題。
這個優化問題求解的就是分解之后的user-factor，item-factor矩陣的factor向量。（qi是item的factor向量，pu是user的factor向量）
求解這個優化問題常用兩種方法，一種是alternative least squares（交叉最小二乘法），另一種是stochastic gradient descent（隨機梯度下降法）。
前一種方法會涉及到矩陣的求逆問題，所以計算起來會比較麻煩。
后一種方法，只需要求梯度，就可以迭代計算了，因此會簡單很多。
迭代方程如下：
其中，gamma是學習速率，lamda是正則化系數，是兩個可選的參數，而且對于最后的結果非常重要。
這里，gamma的大小不僅會影響到訓練時間，還會影響到結果的收斂性。gamma太大的話會導致結果發散，一般都會把gamma取得很小，不同的數據集取得值不同，但大概是0.001這個量級。這樣的話訓練的時間會長一些，但結果會比較好。
lamda的值一般也比較小，大概取0.01這個量級就好了。
迭代開始前，需要對user和item的特征向量賦初值，這個初值很重要，會嚴重地影響到計算速度。一般的做法是在所有已評分的平均分附近產生一些隨機數作為初值。
迭代結束的條件一般是loss function開始增加了，或者loss function的值小于了某一個閾值。
當我們拿到計算出來的user，item的factor向量后，最后預測結果時有兩種選擇，一種是保留計算出來的小數rating，一種是將這些小數rating四舍五入并裁減到[1，5]這個區間內。
對于實際的推薦系統來說，結果是小數還是整數，沒有所謂，因為我們并不會把預測的分數給用戶看，而只是返回一個推薦列表。
但對于線下訓練參數或者做論文的童鞋來說，不同的處理方法得到的RMSE或者MAE的值可不相同。
我用這個的算法對movielens 100k的小數據做了測試，用很短的時間就可以計算好，不過那些參數的選擇需要不斷地用RMSE 來計算得出。在其他的信息都沒有利用的情況下，也可以得到0.90這個量級的RMSE。
4、增加一些擴展項
上面的模型中只簡單的用了已知的評分數據，很多的信息都沒有考慮進來。
（1）增加biases信息
因為有的user總是趨向于打一個很高的分，而有的user比較嚴格，總是打一個很低的分，有的item總是被打一個很高的分，而有的item總是被低估。所以我們需要給模型增加biases項，loss function如下：
迭代方程變成了：
同樣的方法，只是多了對bu和bi的賦初值。
同樣，我用movielens的100k數據計算，得到的RMSE值也在0.90這個量級，但整體要比沒有考慮biases結果好。
（2）增加implicit feedback信息
評分是一個顯性的反饋方式，然而在很多時候顯性的反饋很少很少，而user的很多行為都可以反映出他們對item的態度，所以利用implicit feedback是非常必要的。給模型增加implicit feedback項，預測模型如下：
迭代方程如下：
implicit feedback信息對于商城來說，可能是購買，瀏覽等等行為，對于Netflix這樣的網站來說，可能是瀏覽，租賃等等。
（3）考慮temporal信息
因為用戶的興趣或者對某一個item的態度是和時間有關的，比如說，可能我今年不太喜歡西服這個東西，因為我用不著，所以我不會購買，但可能若干年后我不得不穿西服的時候，我一定會去買，也就是說我給推薦系統留下我喜歡西服這個東西的印象。（即使我真的不喜歡西服。）
動態地考慮user的興趣或者需求是非常必要的。
矩陣分解是當下非常流行的算法，可以考慮將這種算法和傳統的KNN結合在一起來做推薦，相信效果會很不錯。
