矩陣分解推薦演算法

A. ab與ba的特徵值相同嗎

如果A，B都是方陣。則AB與BA的特徵值相同。

矩陣分解的含義：

矩陣分解演算法將m×n維的矩陣R分解為m×k的用戶矩陣P和k×n維的物品矩陣Q相乘的形式。其中m為用戶的數量，n為物品的數量，k為隱向量（Latent Factor）的維度。k的大小決定了隱向量表達能力的強弱，實際應用中，其取值要經過多次的實驗來確定。

在得到了用戶矩陣和物品矩陣Q後，將兩個矩陣相乘，就可以得到一個滿秩的矩陣。那麼，我們就對未被評價過的物品，有了一個預測評分。接下來，可以將評分進行排序，推薦給用戶。這就是矩陣分解對於推薦系統最基本的用途。

B. 推薦系統中——矩陣分解

在推薦系統中，我們經常會拿到一種數據是user—item的表格，然後對應的是每位user對每個item的評分，如下圖：

對於這個問題我們通常會選擇矩陣分解的方法來解決。

我們常見的推薦系統矩陣分解有BPR、SVD（funkSVD）、ALS、NMF、WRMF。

接下來就來看看推薦系統中常用的幾種矩陣分解的區別，主要通過公式、特點和適合哪種數據這幾個方面來講。

對於 矩陣 進行SVD分解，把矩陣 分解為：

其中 是矩陣 中較大的部分奇異值的個數，一般會遠遠的小於用戶數和物品數。如果我們要預測第 個用戶對第 個物品的評分 ,則只需要計算 即可。通過這種方法，我們可以將評分表裡面所有沒有評分的位置得到一個預測評分。通過找到最高的若干個評分對應的物品推薦給用戶。

可以看出這種方法簡單直接。但是有一個很大的問題我們忽略了，就是SVD分解要求矩陣是稠密的，也就是說矩陣的所有位置不能有空白。所以傳統的SVD實際上在推薦系統中還是比較難用的。

前面說到，傳統的SVD要求的矩陣是稠密的。那麼我們現在要解決的問題就是避開矩陣稀疏的問題。

FunkSVD是將矩陣 分解為兩個矩陣 ，這里採用了線性回歸的思想。我們的目標是讓用戶的評分和用矩陣乘積得到的評分殘差盡可能的小，也就是說，可以用均方差作為損失函數，來尋找最終的 。

對於某一個用戶評分 ，用FunkSVD分解，則對應的表示為 ，採用均方差做為損失函數，則我們期望均方差盡可能小：

在實際應用中，我們為了防止過擬合，會加入一個L2的正則化項，因此正式的FunkSVD的優化目標函數 ：

其中 為正則化稀疏，需要調參。對於這個優化問題，我們一般通過梯度下降法來進行優化得到結果。

將上式分別對 求導，然後利用梯度下降法迭代， 的迭代公式如下：

還有許多基於FunkSVD的方法進行改進的，例如BiasSVD、SVD++等，這里就不細說了。

在很多推薦場景中，我們都是 基於現有的用戶和商品之間的一些數據，得到用戶對所有商品的評分，選擇高分的商品推薦給用戶 ，funkSVD演算法的做法最基本的做法，使用起來十分有效，而且模型的可擴展性也非常優秀，其基本思想也能廣泛運用於各種場景中。並且對於相似度計算方法的選擇，有多種相似度計算方法，每種都有對應優缺點，可針對不同場景使用最適合的相似度計算方法。由於funkSVD時間復雜度高，訓練速度較慢，可以使用梯度下降等機器學習相關方法來進行近似計算，以減少時間消耗。

參考： https://www.cnblogs.com/pinard/p/6351319.html

https://zhuanlan.hu.com/p/34497989

https://blog.csdn.net/syani/article/details/52297093

在有些推薦場景中，我們是為了在千萬級別的商品中推薦個位數的商品給用戶，此時，我們更關心的是用戶來說，哪些極少數商品在用戶心中有更高的優先順序，也就是排序更靠前。也就是說，我們需要一個排序演算法，這個演算法可以把每個用戶對應的所有商品按喜好排序。BPR就是這樣的一個我們需要的 排序演算法 。

在BPR演算法中，我們將任意用戶 對應的物品進行標記，如果用戶 在同時有物品 和 的時候點擊了 ，那麼我們就得到了一個三元組 ，它表示對用戶 來說， 的排序要比 靠前

BPR是基於矩陣分解的一種排序演算法，但是和funkSVD之類的演算法比，它不是做全局的評分優化，而是 針對每一個用戶自己的商品喜好分貝做排序優化 。因此在迭代優化的思路上完全不同。同時對於訓練集的要求也是不一樣的， funkSVD只需要用戶物品對應評分數據二元組做訓練集，而BPR則需要用戶對商品的喜好排序三元組做訓練集 。

參考： https://www.cnblogs.com/pinard/p/9128682.html

ALS是交替最小二乘的簡稱。在機器學習中，ALS特指使用交替最小二乘求解的一個協同推薦演算法。如：將用戶（user）對商品（item）的評分矩陣分解成2個矩陣：user對item 潛在因素的偏好矩陣(latent factor vector)，item潛在因素的偏好矩陣。

假設有m個user和n個item，所以評分矩陣為R。ALS(alternating least squares)希望找到2個比較低緯度的矩陣（X和Y）來逼近這個評分矩陣R。

ALS的核心就是這樣一個假設：打分矩陣是近似低秩的。換句話說，就是一個 的打分矩陣可以由分解的兩個小矩陣 和 的乘積來近似。這就是ALS的矩陣分解方法。

為了讓X和Y相乘能逼近R，因此我們需要最小化損失函數(loss function)，因此需要最小化損失函數，在此定義為平方誤差和(Mean square error, MSE)。

一般損失函數都會需要加入正則化項(Regularization item)來避免過擬合的問題，通常是用L2，所以目標函數會被修改為：

上面介紹了「最小二乘（最小平方誤差）」，但是還沒有講清楚「交替」是怎麼回事。因為X和Y都是未知的參數矩陣，因此我們需要用「交替固定參數」來對另一個參數求解。

先固定Y, 將loss function對X求偏導，使其導數等於0：

再固定X, 將loss function對Y求偏導，使其導數等於0：

然後進行迭代。

在實際應用中，由於待分解的矩陣常常是非常稀疏的，與SVD相比， ALS能有效的解決過擬合問題 。基於ALS的矩陣分解的協同過濾演算法的可擴展性也優於SVD。與隨機梯度下降的求解方式相比，一般情況下隨機梯度下降比ALS速度快；但有兩種情況ALS更優於隨機梯度下降：（1）當系統能夠並行化時，ALS的擴展性優於隨機梯度下降法。（2）ALS-WR能夠有效的處理用戶對商品的隱式反饋的數據。

但是ALS演算法是無法准確評估新加入的用戶或商品。這個問題也被稱為冷啟動問題。

參考： https://flashgene.com/archives/46364.html

https://flashgene.com/archives/52522.html

https://lumingdong.cn/recommendation-algorithm-based-on-matrix-decomposition.html#ALS

非負矩陣分解(Non-negative Matrix Factorization，NMF)演算法，即NMF是在矩陣中所有元素均為非負數約束條件之下的矩陣分解方法。NMF中要求原始的矩陣V的所有元素的均是非負的，並且矩陣V可以分解出的兩個小矩陣也是非負的，

給定一個打分矩陣R，NMF的目標是求解兩個非負秩矩陣  最小化目標函數如下：

計算 的梯度如下：

其中：

採用梯度下降的參數優化方式, 可得W以及H的更新迭代方式見下式：

在矩陣分解基礎上，加入了隱向量的非負限制。然後使用非負矩陣分解的優化演算法求解。

要用NMF做矩陣分解有一個很大的前提—— 用戶item之間的評分矩陣要求是非負並且分解出的小矩陣也要滿足非負約束 。NMF分解是對原矩陣的近似還原分解，其存在的問題和ALS相像，對於未知的評分預測相當不準確。

參考： https://flashgene.com/archives/52522.html

http://tripleday.cn/2017/01/12/sparse-nmf/

在有些場景下，雖然 沒有得到用戶具體的評分，但是能夠得到一些類似於「置信度」的信息（也稱為隱式反饋信息） ，例如用戶的游戲時長、觀看時長等數據。雖然時長信息不能直接體現用戶的喜好，但是能夠說明用戶喜歡的概率更大。在此場景下，用戶-物品記錄可以表示為一個置信度 和一個0-1指示量 （用戶-物品是否有交互），如果用戶-物品沒有交互，那麼置信度就為0。

「帶權」就是根據置信度計算每條記錄對應損失的權重，優化的目標函數如下：

權重通過置信度計算得到，可以使用 。由於未發生的交互也存在於損失函數中，因此慣用的隨機梯度下降存在性能問題，為此採用ALS來優化模型，因此訓練過程如下：

（1）更新每個用戶的向量：

（2）更新每個物品的向量：

前面除了BPR以外，我們講的演算法都是針對顯式反饋的評分矩陣的，因此當數據集只有隱式反饋時，應用上述矩陣分解直接建模會存在問題。而WRMF就可以解決隱式反饋的問題。

參考： https://sine-x.com/gorse-2/

https://flashgene.com/archives/52522.html

基於現有的用戶和商品之間的一些數據，得到用戶對所有商品的評分，選擇高分的商品推薦給用戶，可以根據以往的評分矩陣做全局的評分優化。有多種從SVD的改進演算法可選擇，如：表示biasSVD、SVD++、TimesSVD等

funkSVD可以解決矩陣稀疏的問題，但是其時間復雜度高，訓練速度較慢，可以使用梯度下降等機器學習相關方法來進行近似計算，以減少時間消耗。

ALS演算法和SVD的使用場景相似，也是基於用戶——商品評分數據得到全局用戶對商品的評分。

ALS能有效的解決過擬合問題，但是ALS演算法是無法准確評估新加入的用戶或商品。這個問題也被稱為冷啟動問題。

要用NMF做矩陣分解有一個很大的前提—— 用戶item之間的評分矩陣要求是非負並且分解出的小矩陣也要滿足非負約束 。NMF分解是對原矩陣的近似還原分解，NMF用法和SVD、ALS相似。

NMF存在的問題和ALS相像，對於未知的評分預測相當不準確。

BPR是基於矩陣分解的一種排序演算法，但是，它不是做全局的評分優化，而是 針對每一個用戶自己的商品喜好分貝做排序優化 。因此在迭代優化的思路上完全不同。 BPR需要用戶對商品的喜好排序三元組做訓練集 。

當 沒有得到用戶具體的評分，但是能夠得到一些類似於隱式反饋信息時，就可使用WRMF進行矩陣分解。

C. 矩陣分解演算法

矩陣分解演算法主要用於解決協同過濾演算法泛化能力弱的問題。

在現實中人和商品可以進行分類，比如將人分為偏好刺激的、偏好自然的，將電影分為恐怖的、溫馨的。當我們以這樣信息對人和物進行標定後就可以根據他們直接的距離來判斷他們的相似程度。

一般協同過濾的思路通過物品找到相似的人，在給用戶1推薦和他相似的用戶喜歡的物品。

對用戶和物品在映射到低維度下計算他們之間的距離。

原有的 大小的共現矩陣 ，我們的目標是將它分解為 , 表示降維後的用戶矩陣， 表示降維後的物品矩陣, 表示降溫的程度一般 是遠小於 。

如何進行矩陣分解？接下來介紹幾種策略

在推薦模型中出現矩陣分解思路時自然想到了SVD（奇異值分解），SVD可以將一個矩陣 分解為 的形式，D中主對角線上是從到到小排序的奇異值，我們選擇前幾個奇異值和對應U和V的向量這樣實現了降讓行茄維。

降維後的 可以作為用戶矩陣,降維後的 可以作為物品矩陣。接著使用 , 公式對所有的用戶產品組合進行評分，這樣我們就把原共現矩陣中用戶沒有評分的物品也打上分了，利用這些評分就可以完成推薦。

問題就這樣完美解決了？並不是。

矩陣 要進行SVD分解它就不能存在空的數據，而我們待分解的矩陣由於用戶操作的低頻特點，肯定會有空的位置出現，並且如果已經有了一個填滿數據的共現矩陣，那就不用進行分解直接用就可以了。針對空數據可以採用填0、填平均值等方式暴力補全數據，但是這樣的操作會影響准確度而且對越稀疏的矩陣影響越大，同時存放一個暴力填滿的矩陣要求更多的存儲空間，還有SVD的時間復雜度 也很可觀。坦察

這個模型感覺和SVD關系不大了，他的目標是得到矩陣 和 ，這兩個矩陣可以很好的反應已知的用戶數據，根據以上目標構造待優化的目標函數

這里 表示用戶評分樣本集合。為了避免過擬合引入正則項後目標函數變為

接著利用梯度下降求解 和 。

Funk-SVD模式解決了SVD模型中空數據需要保留填寫、SVD分解耗時、佔用空間多的問題。同時考慮一些偏置。

用戶偏置 ：一些用戶喜歡打帶知高分、一些用戶喜歡打低分

物品偏置 ：一些電影普遍得分高

整體偏置 ：數據整體的平均得分

這樣可以消除偏置，讓預測更合理。

該模型依然存在利用信息有限的缺點。

深度學習推薦系統 王喆

推薦系統之矩陣分解家族

推薦系統實踐 項亮

D. 推薦演算法簡介

寫在最前面：本文內容主要來自於書籍《推薦系統實踐》和《推薦系統與深度學習》。

推薦系統是目前互聯網世界最常見的智能產品形式。從電子商務、音樂視頻網站，到作為互聯網經濟支柱的在線廣告和新穎的在線應用推薦，到處都有推薦系統的身影。推薦演算法是推薦系統的核心，其本質是通過一定的方式將用戶和物品聯系起來，而不同的推薦系統利用了不同的方式。

推薦系統的主要功能是以個性化的方式幫助用戶從極大的搜索空間中快速找到感興趣的對象。因此，目前所用的推薦系統多為個性化推薦系統。個性化推薦的成功應用需要兩個條件：

在推薦系統的眾多演算法中，基於協同的推薦和基於內容的推薦在實踐中得到了最廣泛的應用。本文也將從這兩種演算法開始，結合時間、地點上下文環境以及社交環境，對常見的推薦演算法做一個簡單的介紹。

基於內容的演算法的本質是對物品內容進行分析，從中提取特徵，然後基於用戶對何種特徵感興趣來推薦含有用戶感興趣特徵的物品。因此，基於內容的推薦演算法有兩個最基本的要求：

下面我們以一個簡單的電影推薦來介紹基於內容的推薦演算法。

現在有兩個用戶A、B和他們看過的電影以及打分情況如下：

其中問好（?）表示用戶未看過。用戶A對《銀河護衛隊 》《變形金剛》《星際迷航》三部科幻電影都有評分，平均分為 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；對《三生三世》《美人魚》《北京遇上西雅圖》三部愛情電影評分平均分為 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。現在需要給A推薦電影，很明顯A更傾向於科幻電影，因此推薦系統會給A推薦獨立日。而對於用戶B，通過簡單的計算我們可以知道更喜歡愛情電影，因此給其推薦《三生三世》。當然，在實際推薦系統中，預測打分比這更加復雜些，但是其原理是一樣的。

現在，我們可以將基於內容的推薦歸納為以下四個步驟：

通過上面四步就能快速構建一個簡單的推薦系統。基於內容的推薦系統通常簡單有效，可解釋性好，沒有物品冷啟動問題。但他也有兩個明顯的缺點：

最後，順便提一下特徵提取方法：對於某些特徵較為明確的物品，一般可以直接對其打標簽，如電影類別。而對於文本類別的特徵，則主要是其主題情感等，則些可以通過tf-idf或LDA等方法得到。

基於協同的演算法在很多地方也叫基於鄰域的演算法，主要可分為兩種：基於用戶的協同演算法和基於物品的協同演算法。

啤酒和尿布的故事在數據挖掘領域十分有名，該故事講述了美國沃爾瑪超市統計發現啤酒和尿布一起被購買的次數非常多，因此將啤酒和尿布擺在了一起，最後啤酒和尿布的銷量雙雙增加了。這便是一個典型的物品協同過濾的例子。

基於物品的協同過濾指基於物品的行為相似度（如啤酒尿布被同時購買）來進行物品推薦。該演算法認為，物品A和物品B具有很大相似度是因為喜歡物品A的用戶大都也喜歡物品B。

基於物品的協同過濾演算法主要分為兩步：

基於物品的協同過濾演算法中計算物品相似度的方法有以下幾種：
（1）基於共同喜歡物品的用戶列表計算。

此外，John S. Breese再其論文中還提及了IUF（Inverse User Frequence，逆用戶活躍度）的參數，其認為活躍用戶對物品相似度的貢獻應該小於不活躍的用戶，應該增加IUF參數來修正物品相似度的公式：

上面的公式只是對活躍用戶做了一種軟性的懲罰， 但對於很多過於活躍的用戶， 比如某位買了當當網80%圖書的用戶， 為了避免相似度矩陣過於稠密， 我們在實際計算中一般直接忽略他的興趣列表， 而不將其納入到相似度計算的數據集中。

（2）基於餘弦相似度計算。

（3）熱門物品的懲罰。
從上面（1）的相似度計算公式中，我們可以發現當物品 i 被更多人購買時，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都會增長。對於熱門物品，分子 N(i) ∩ N(j) 的增長速度往往高於 N(i)，這就會使得物品 i 和很多其他的物品相似度都偏高，這就是 ItemCF 中的物品熱門問題。推薦結果過於熱門，會使得個性化感知下降。以歌曲相似度為例，大部分用戶都會收藏《小蘋果》這些熱門歌曲，從而導致《小蘋果》出現在很多的相似歌曲中。為了解決這個問題，我們對於物品 i 進行懲罰，例如下式， 當α∈(0, 0.5) 時，N(i) 越小，懲罰得越厲害，從而使熱門物品相關性分數下降（ 博主註：這部分未充分理解 ）：

此外，Kary pis在研究中發現如果將ItemCF的相似度矩陣按最大值歸一化， 可以提高推薦的准確率。 其研究表明， 如果已經得到了物品相似度矩陣w， 那麼可以用如下公式得到歸一化之後的相似度矩陣w'：

歸一化的好處不僅僅在於增加推薦的准確度，它還可以提高推薦的覆蓋率和多樣性。一般來說，物品總是屬於很多不同的類，每一類中的物品聯系比較緊密。假設物品分為兩類——A和B， A類物品之間的相似度為0.5， B類物品之間的相似度為0.6， 而A類物品和B類物品之間的相似度是0.2。 在這種情況下， 如果一個用戶喜歡了5個A類物品和5個B類物品， 用ItemCF給他進行推薦， 推薦的就都是B類物品， 因為B類物品之間的相似度大。 但如果歸一化之後， A類物品之間的相似度變成了1， B類物品之間的相似度也是1， 那麼這種情況下， 用戶如果喜歡5個A類物品和5個B類物品， 那麼他的推薦列表中A類物品和B類物品的數目也應該是大致相等的。 從這個例子可以看出， 相似度的歸一化可以提高推薦的多樣性。

那麼，對於兩個不同的類，什麼樣的類其類內物品之間的相似度高，什麼樣的類其類內物品相似度低呢？一般來說，熱門的類其類內物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類裡面的物品，而這些物品也是比較熱門的。因此，推薦的覆蓋率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統的覆蓋率。

最後，利用物品相似度矩陣和用戶打過分的物品記錄就可以對一個用戶進行推薦評分：

基於用戶的協同演算法與基於物品的協同演算法原理類似，只不過基於物品的協同是用戶U購買了A物品，會計算經常有哪些物品與A一起購買（也即相似度），然後推薦給用戶U這些與A相似的物品。而基於用戶的協同則是先計算用戶的相似性（通過計算這些用戶購買過的相同的物品），然後將這些相似用戶購買過的物品推薦給用戶U。

基於用戶的協同過濾演算法主要包括兩個步驟：

步驟（1）的關鍵是計算用戶的興趣相似度，主要是利用用戶的行為相似度計算用戶相似度。給定用戶 u 和 v，N(u) 表示用戶u曾經有過正反饋（譬如購買）的物品集合，N(v) 表示用戶 v 曾經有過正反饋的物品集合。那麼我們可以通過如下的 Jaccard 公式簡單的計算 u 和 v 的相似度：

或通過餘弦相似度：

得到用戶之間的相似度之後，UserCF演算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。如下的公式度量了UserCF演算法中用戶 u 對物品 i 的感興趣程度：

首先回顧一下UserCF演算法和ItemCF演算法的推薦原理：UserCF給用戶推薦那些和他有共同興趣愛好的用戶喜歡的物品， 而ItemCF給用戶推薦那些和他之前喜歡的物品具有類似行為的物品。

（1）從推薦場景考慮
首先從場景來看，如果用戶數量遠遠超過物品數量，如購物網站淘寶，那麼可以考慮ItemCF，因為維護一個非常大的用戶關系網是不容易的。其次，物品數據一般較為穩定，因此物品相似度矩陣不必頻繁更新，維護代價較小。

UserCF的推薦結果著重於反應和用戶興趣相似的小群體的熱點，而ItemCF的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反應了用戶所在小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反應了用戶自己的個性傳承。因此UserCF更適合新聞、微博或微內容的推薦，而且新聞內容更新頻率非常高，想要維護這樣一個非常大而且更新頻繁的表無疑是非常難的。

在新聞類網站中，用戶的興趣愛好往往比較粗粒度，很少會有用戶說只看某個話題的新聞，而且往往某個話題也不是每天都會有新聞。 個性化新聞推薦更強調新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，個性化是補充，所以 UserCF 給用戶推薦和他有相同興趣愛好的人關注的新聞，這樣在保證了熱點和時效性的同時，兼顧了個性化。

（2）從系統多樣性（也稱覆蓋率，指一個推薦系統能否給用戶提供多種選擇）方面來看，ItemCF的多樣性要遠遠好於UserCF，因為UserCF更傾向於推薦熱門物品。而ItemCF具有較好的新穎性，能夠發現長尾物品。所以大多數情況下，ItemCF在精度上較小於UserCF，但其在覆蓋率和新穎性上面卻比UserCF要好很多。

在介紹本節基於矩陣分解的隱語義模型之前，讓我們先來回顧一下傳統的矩陣分解方法SVD在推薦系統的應用吧。

基於SVD矩陣分解在推薦中的應用可分為如下幾步：

SVD在計算前會先把評分矩陣 A 缺失值補全，補全之後稀疏矩陣 A 表示成稠密矩陣，然後將分解成 A' = U∑V T 。但是這種方法有兩個缺點：（1）補成稠密矩陣後需要耗費巨大的儲存空間，對這樣巨大的稠密矩陣進行儲存是不現實的；（2）SVD的計算復雜度很高，對這樣大的稠密矩陣中進行計算式不現實的。因此，隱語義模型就被發明了出來。

更詳細的SVD在推薦系統的應用可參考 奇異值分解SVD簡介及其在推薦系統中的簡單應用 。

隱語義模型（Latent Factor Model）最早在文本挖掘領域被提出，用於找到文本的隱含語義。相關的演算法有LSI，pLSA，LDA和Topic Model。本節將對隱語義模型在Top-N推薦中的應用進行詳細介紹，並通過實際的數據評測該模型。

隱語義模型的核心思想是通過隱含特徵聯系用戶興趣和物品。讓我們通過一個例子來理解一下這個模型。

現有兩個用戶，用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書，而用戶B的興趣比較集中在數學和機器學習方面。那麼如何給A和B推薦圖書呢？

我們可以對書和物品的興趣進行分類。對於某個用戶，首先得到他的興趣分類，然後從分類中挑選他可能喜歡的物品。簡言之，這個基於興趣分類的方法大概需要解決3個問題：

對於第一個問題的簡單解決方案是找相關專業人員給物品分類。以圖書為例，每本書出版時，編輯都會給出一個分類。但是，即使有很系統的分類體系，編輯給出的分類仍然具有以下缺點：（1）編輯的意見不能代表各種用戶的意見；（2）編輯很難控制分類的細粒度；（3）編輯很難給一個物品多個分類；（4）編輯很難給一個物品多個分類；（5）編輯很難給出多個維度的分類；（6）編輯很難決定一個物品在某一個類別中的權重。

為了解決上述問題，研究員提出可以從數據出發，自動找到那些分類，然後進行個性化推薦。隱語義模型由於採用基於用戶行為統計的自動聚類，較好地解決了上面提出的5個問題。

LFM將矩陣分解成2個而不是3個：

推薦系統中用戶和物品的交互數據分為顯性反饋和隱性反饋數據。隱式模型中多了一個置信參數，具體涉及到ALS（交替最小二乘法，Alternating Least Squares）中對於隱式反饋模型的處理方式——有的文章稱為「加權的正則化矩陣分解」：

一個小細節：在隱性反饋數據集中，只有正樣本（正反饋）沒有負反饋（負樣本），因此如何給用戶生成負樣本來進行訓練是一個重要的問題。Rong Pan在其文章中對此進行了探討，對比了如下幾種方法：

用戶行為很容易用二分圖表示，因此很多圖演算法都可以應用到推薦系統中。基於圖的模型（graph-based model）是推薦系統中的重要內容。很多研究人員把基於領域的模型也稱為基於圖的模型，因為可以把基於領域的模型看作基於圖的模型的簡單形式。

在研究基於圖的模型之前，需要將用戶行為數據表示成圖的形式。本節的數據是由一系列用戶物品二元組 (u, i) 組成的，其中 u 表示用戶對物品 i 產生過行為。

令 G(V, E) 表示用戶物品二分圖，其中 V=V U UV I 由用戶頂點 V U 和物品節點 V I 組成。對於數據集中每一個二元組 (u, i) ，圖中都有一套對應的邊 e(v u , v i )，其中 v u ∈V U 是用戶對應的頂點，v i ∈V I 是物品i對應的頂點。如下圖是一個簡單的物品二分圖，其中圓形節點代表用戶，方形節點代表物品，用戶物品的直接連線代表用戶對物品產生過行為。比如下圖中的用戶A對物品a、b、d產生過行為。

度量圖中兩個頂點之間相關性的方法很多，但一般來說圖中頂點的相關性主要取決於下面3個因素：

而相關性高的一對頂點一般具有如下特徵：

舉個例子，如下圖，用戶A和物品c、e沒有邊直連，但A可通過一條長度為3的路徑到達c，而Ae之間有兩條長度為3的路徑。那麼A和e的相關性要高於頂點A和c，因而物品e在用戶A的推薦列表中應該排在物品c之前，因為Ae之間有兩條路徑。其中，（A,b,C,e）路徑經過的頂點的出度為（3，2，2，2），而 (A,d,D,e) 路徑經過了一個出度比較大的頂點D，所以 (A,d,D,e) 對頂點A與e之間相關性的貢獻要小於（A,b,C,e）。

基於上面3個主要因素，研究人員設計了很多計算圖中頂點相關性的方法，本節將介紹一種基於隨機遊走的PersonalRank演算法。

假設要給用戶u進行個性化推薦，可以從用戶u對應的節點 v u 開始在用戶物品二分圖上進行隨機遊走。遊走到任一節點時，首先按照概率α決定是繼續遊走還是停止這次遊走並從 v u 節點重新開始遊走。若決定繼續遊走，則從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為遊走下次經過的節點。這樣，經過很多次隨機遊走後，每個物品被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。

上述演算法可以表示成下面的公式：

雖然通過隨機遊走可以很好地在理論上解釋PersonalRank演算法，但是該演算法在時間復雜度上有明顯的缺點。因為在為每個用戶進行推薦時，都需要在整個用戶物品二分圖上進行迭代，知道所有頂點的PR值都收斂。這一過程的時間復雜度非常高，不僅無法在線進行實時推薦，離線計算也是非常耗時的。

有兩種方法可以解決上面PersonalRank時間復雜度高的問題：
（1）減少迭代次數，在收斂之前停止迭代。但是這樣會影響最終的精度。

（2）從矩陣論出發，重新涉及演算法。另M為用戶物品二分圖的轉移概率矩陣，即：

網路社交是當今社會非常重要甚至可以說是必不可少的社交方式，用戶在互聯網上的時間有相當大的一部分都用在了社交網路上。

當前國外最著名的社交網站是Facebook和Twitter，國內的代表則是微信/QQ和微博。這些社交網站可以分為兩類：

需要指出的是，任何一個社交網站都不是單純的社交圖譜或興趣圖譜。如QQ上有些興趣愛好群可以認識不同的陌生人，而微博中的好友也可以是現實中認識的。

社交網路定義了用戶之間的聯系，因此可以用圖定義社交網路。我們用圖 G(V,E,w) 定義一個社交網路，其中V是頂點集合，每個頂點代表一個用戶，E是邊集合，如果用戶va和vb有社交網路關系，那麼就有一條邊 e(v a , v b ) 連接這兩個用戶，而 w(v a , v b )定義了邊的權重。一般來說，有三種不同的社交網路數據：

和一般購物網站中的用戶活躍度分布和物品流行度分布類似，社交網路中用戶的入度（in degree，表示有多少人關注）和出度（out degree，表示關注多少人）的分布也是滿足長尾分布的。即大部分人關注的人都很少，被關注很多的人也很少。

給定一個社交網路和一份用戶行為數據集。其中社交網路定義了用戶之間的好友關系，而用戶行為數據集定義了不同用戶的歷史行為和興趣數據。那麼最簡單的演算法就是給用戶推薦好友喜歡的物品集合。即用戶u對物品i的興趣 p ui 可以通過如下公式計算。

用戶u和用戶v的熟悉程度描述了用戶u和用戶在現實社會中的熟悉程度。一般來說，用戶更加相信自己熟悉的好友的推薦，因此我們需要考慮用戶之間的熟悉度。下面介紹3中衡量用戶熟悉程度的方法。

（1）對於用戶u和用戶v，可以使用共同好友比例來計算他們的相似度：

上式中 out(u) 可以理解為用戶u關注的用戶合集，因此 out(u) ∩ out(v) 定義了用戶u、v共同關注的用戶集合。

（2）使用被關注的用戶數量來計算用戶之間的相似度，只要將公式中的 out(u) 修改為 in(u)：

in(u) 是指關注用戶u的集合。在無向社交網路中，in(u)和out(u)是相同的，而在微博這種有向社交網路中，這兩個集合的含義就不痛了。一般來說，本方法適合用來計算微博大V之間的相似度，因為大v往往被關注的人數比較多；而方法（1）適用於計算普通用戶之間的相似度，因為普通用戶往往關注行為比較豐富。

（3）除此之外，還可以定義第三種有向的相似度：這個相似度的含義是用戶u關注的用戶中，有多大比例也關注了用戶v：

這個相似度有一個缺點，就是在該相似度下所有人都和大v有很大的相似度，這是因為公式中的分母並沒有考慮 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，來降低大v與其他用戶的相似度：

上面介紹了3種計算用戶之間相似度（或稱熟悉度）的計算方法。除了熟悉程度，還需要考慮用戶之間的興趣相似度。我們和父母很熟悉，但很多時候我們和父母的興趣確不相似，因此也不會喜歡他們喜歡的物品。因此，在度量用戶相似度時，還需要考慮興趣相似度，而興趣相似度可以通過和UserCF類似的方法度量，即如果兩個用戶喜歡的物品集合重合度很高，兩個用戶的興趣相似度很高。

最後，我們可以通過加權的形式將兩種權重合並起來，便得到了各個好有用戶的權重了。

有了權重，我們便可以針對用戶u挑選k個最相似的用戶，把他們購買過的物品中，u未購買過的物品推薦給用戶u即可。打分公式如下：

其中 w' 是合並後的權重，score是用戶v對物品的打分。

node2vec的整體思路分為兩個步驟：第一個步驟是隨機遊走（random walk），即通過一定規則隨機抽取一些點的序列；第二個步驟是將點的序列輸入至word2vec模型從而得到每個點的embedding向量。

隨機遊走在前面基於圖的模型中已經介紹過，其主要分為兩步：（1）選擇起始節點；（2）選擇下一節點。起始節點選擇有兩種方法：按一定規則抽取一定量的節點或者以圖中所有節點作為起始節點。一般來說會選擇後一種方法以保證所有節點都會被選取到。

在選擇下一節點方法上，最簡單的是按邊的權重來選擇，但在實際應用中需要通過廣度優先還是深度優先的方法來控制遊走范圍。一般來說，深度優先發現能力更強，廣度優先更能使社區內（較相似）的節點出現在一個路徑里。

斯坦福大學Jure Leskovec教授給出了一種可以控制廣度優先或者深度優先的方法。

以上圖為例，假設第一步是從t隨機遊走到v，這時候我們要確定下一步的鄰接節點。本例中，作者定義了p和q兩個參數變數來調節遊走，首先計算其鄰居節點與上一節點t的距離d，根據下面的公式得到α：

一般從每個節點開始遊走5~10次，步長則根據點的數量N遊走根號N步。如此便可通過random walk生成點的序列樣本。

得到序列之後，便可以通過word2vec的方式訓練得到各個用戶的特徵向量，通過餘弦相似度便可以計算各個用戶的相似度了。有了相似度，便可以使用基於用戶的推薦演算法了。

推薦系統需要根據用戶的歷史行為和興趣預測用戶未來的行為和興趣，因此大量的用戶行為數據就成為推薦系統的重要組成部分和先決條件。如何在沒有大量用戶數據的情況下設計個性化推薦系統並且讓用戶對推薦結果滿意從而願意使用推薦系統，就是冷啟動問題。

冷啟動問題主要分為三類：

針對用戶冷啟動，下面給出一些簡要的方案：
（1）有效利用賬戶信息。利用用戶注冊時提供的年齡、性別等數據做粗粒度的個性化；
（2）利用用戶的社交網路賬號登錄（需要用戶授權），導入用戶在社交網站上的好友信息，然後給用戶推薦其好友喜歡的物品；
（3）要求用戶在登錄時對一些物品進行反饋，手機用戶對這些物品的興趣信息，然後給用推薦那些和這些物品相似的物品；
（4）提供非個性化推薦。非個性化推薦的最簡單例子就是熱門排行榜，我們可以給用戶推薦熱門排行榜，然後等到用戶數據收集到一定的時候，在切換為個性化推薦。

對於物品冷啟動，可以利用新加入物品的內容信息，將它們推薦給喜歡過和他們相似的物品的用戶。

對於系統冷啟動，可以引入專家知識，通過一定高效的方式快速建立起物品的相關度表。

在上面介紹了一些推薦系統的基礎演算法知識，這些演算法大都是比較經典且現在還在使用的。但是需要注意的是，在實踐中，任何一種推薦演算法都不是單獨使用的，而是將多種推薦演算法結合起來，也就是混合推薦系統，但是在這里並不準備介紹，感興趣的可以查閱《推薦系統》或《推薦系統與深度學習》等書籍。此外，在推薦中非常重要的點擊率模型以及基於矩陣的一些排序演算法在這里並沒有提及，感興趣的也可自行學習。

雖然現在用的很多演算法都是基於深度學習的，但是這些經典演算法能夠讓我們對推薦系統的發展有一個比較好的理解，同時，更重要的一點——「推陳出新」，只有掌握了這些經典的演算法，才能提出或理解現在的一些更好地演算法。

E. 正定矩陣因子分解法（PMF）

3.2.4.1 方法建立

就全國范圍而言，我國地下水質量總體較好，根據國家《地下水質量標准》（GB/T 14848—93），我國63%的地區地下水可直接飲用，17%經適當處理後可供飲用，12%不宜飲用，剩餘8%為天然的鹹水和鹽水，由此可見，不宜飲用的地下水和天然鹹水、鹽水佔到了20%，對於這些地下水型水源地飲用水指標並不一定受到污染而存在超標現象，其水質可能受到地下水形成演化影響更為明顯，因此，考慮選擇反映地下水形成、演化的地下水水化學類型常規指標，進行影響因素解析。地下水水質指標在取樣與分析過程中，由於取樣和樣品處理、試劑和水純度、儀器量度和儀器潔凈、採用的分析方法、測定過程以及數據處理等過程均會產生測量誤差（系統誤差，隨機誤差，過失誤差）。從取樣到分析結果計算誤差都絕對存在，雖然在各個過程中進行質量控制，但無法完全消除不確定性的影響，為確保分析結果的可靠性，採用PMF法對地下水水質指標考慮一定的不確定性誤差，使分析數據能夠准確地反映實際情況。

PMF（Positive Matrix Factorization）與主成分分析（PCA）、因子分析（FA）都是利用矩陣分解來解決實際問題的分析方法，在這些方法中，原始的大矩陣被近似分解為低秩的V＝WH形式。但PMF與PCA和FA不同，PCA、FA方法中因子W和H中的元素可為正或負，即使輸入的初始矩陣元素全是正的，傳統的秩削減演算法也不能保證原始數據的非負性。在數學上，從計算的觀點看，分解結果中存在負值是正確的，但負值元素在實際問題中往往是沒有意義的。PMF是在矩陣中所有元素均為非負數約束條件之下的矩陣分解方法，在求解過程中對因子載荷和因子得分均做非負約束，避免矩陣分解的結果中出現負值，使得因子載荷和因子得分具有可解釋性和明確的物理意義。PMF使用最小二乘方法進行迭代運算，能夠同時確定污染源譜和貢獻，不需要轉換就可以直接與原始數據矩陣作比較，分解矩陣中元素非負，使得分析的結果明確而易於解釋，可以利用不確定性對數據質量進行優化，是美國國家環保局（EPA）推薦的源解析工具。

3.2.4.2 技術原理

PMF：模型是一種基於因子分析的方法，具有不需要測量源指紋譜、分解矩陣中元素非負、可以利用數據標准偏差來進行優化等優點。目前PMF模型此方法成功用於大氣氣溶膠、土壤和沉積物中持久性有毒物質的源解析，已有成熟的應用模型 PMF1.1，PMF2.0，PMF3.0等。PMF模型基本方程為：

X_nm＝G_npF_pm+E （3.7）

式中：n——取樣點數；

m——各取樣點測試的成分數量；

p——污染源個數；

X_nm——取樣點各成分含量；

G_np——主要源的貢獻率；

F_pm——源指紋圖譜。

基本計算過程如下：

1）樣品數據無量綱化，無量綱化後的樣品數據矩陣用D表示。

2）協方差矩陣求解，為計算特徵值和特徵向量，可先求得樣品數據的協方差矩陣，用D′為D的轉置，演算法為：

Z＝DD′ （3.8）

3）特徵值及特徵向量求解，用雅各布方法可求得協方差矩陣Z的特徵值矩陣E和特徵向量矩陣Q，Q′表示Q的轉置。這時，協方差矩陣可表示為：

Z＝QEQ′ （3.9）

4）主要污染源數求解，為使高維變數空間降維後能盡可能保留原來指標信息，利用累計方差貢獻率提取顯著性因子，判斷條件為：

地下水型飲用水水源地保護與管理：以吳忠市金積水源地為例

式中：n——顯著性因子個數；

m——污染物個數；

λ——特徵值。

5）因子載荷矩陣求解，提取顯著性因子後，利用求解得到的特徵值矩陣E和特徵向量矩陣Q進一步求得因子載荷矩陣S和因子得分矩陣C，這時，因子載荷矩陣可表示為：

S＝QE^1/2 （3.11）

因子得分矩陣可表示為：

C＝（S′S）^-1S′D （3.12）

6）非負約束旋轉，由步驟5求得的因子載荷矩陣S和因子得分矩陣C分別對應主要污染源指紋圖譜和主要污染源貢獻，為解決其值可能為負的現象，需要做非負約束的旋轉。

7）首先利用轉換矩陣T₁對步驟5求得的因子載荷矩陣S和因子得分矩陣C按下式進行旋轉：

地下水型飲用水水源地保護與管理：以吳忠市金積水源地為例

C₁＝T₁C （3.14）

式中：S₁——旋轉後的因子載荷矩陣；

C₁——旋轉後的因子得分矩陣；

T₁——轉換矩陣，且T₁＝（C^∗C′）（C^∗C′）^-1（其中：C^∗為把C中的負值替換為零後的因子得分矩陣）。

8）利用步驟7中旋轉得到的因子載荷矩陣S₁構建轉換矩陣T₂對步驟5中旋轉得到的因子載荷矩陣S₁和因子得分矩陣C₁繼續旋轉：

S₂＝S₁T₂ （3.15）

地下水型飲用水水源地保護與管理：以吳忠市金積水源地為例

式中：S₂——二次旋轉後的因子載荷矩陣；

C₂——二次旋轉後的因子得分矩陣；

T₂——二次轉換矩陣，且T₂＝（S′₁+S₁）^-1（S′₁+

）（其中：

為S₁中的負值換為零後的因子載荷矩陣）。

9）：重復步驟7、8，直到因子載荷中負值的平方和小於某一設定的誤差精度e而終止，最終得到符合要求的因子載荷矩陣S，即主要污染源指紋圖譜。

3.2.4.3 方法流程

針對受體采樣數據直接進行矩陣分解，得到各污染源組分及其貢獻率的統計方法（圖3.5）。

圖3.5 方法流程圖

（1）缺失值處理

正定矩陣因子分析是基於多元統計的分析方法，對數據有效性具有一定的要求，因此在進行分析之前首先對數據進行預處理。根據已有數據的特徵結合實際情況主要有以下5種處理方法。

1）采樣數據量充足的情況下直接丟棄含缺失數據的記錄。

2）存在部分缺失值情況下用全局變數或屬性的平均值來代替所有缺失數據。把全局變數或是平均值看作屬性的一個新值。

3）先根據歐式距離或相關分析來確定距離具有缺失數據樣本最近的K個樣本，將這K個值加權平均來估計該樣本的缺失數據。

4）採用預測模型來預測每一個缺失數據。用已有數據作為訓練樣本來建立預測模型，如神經網路模型預測缺失數據。該方法最大限度地利用已知的相關數據，是比較流行的缺失數據處理技術。

5）對低於數據檢測限的數據可用數據檢測限值或1/2檢測限以及更小比例檢測限值代替。

（2）不確定性處理

計算數據不確定性。

地下水型飲用水水源地保護與管理：以吳忠市金積水源地為例

式中：s——誤差百分數；

c——指標濃度值；

l——因子數據檢出限。

（3）數據合理性分析

本研究所用數據在放入模型前以信噪比S/N（Signal to Noise）作為標准進行篩選，信噪比S/N為：

地下水型飲用水水源地保護與管理：以吳忠市金積水源地為例

式中：x_ij——第i采樣點第j個樣品的濃度；

s_ij——第i采樣點第j個樣品的標准偏差。

信噪比小，說明樣品的雜訊大，信噪比越大則表示樣品檢出的可能性越大，越適合模型。

（4）數據輸入及因子分析

與其他因子分析方法一樣，PMF不能直接確定因子數目。確定因子數目的一般方法是嘗試多次運行軟體，根據分析結果和誤差，Q值以及改變因子數目時Q值的相對變化等來確定合理的因子數目。

3.2.4.4 適用范圍

PMF對污染源和貢獻施加了非負限制，並考慮了原始數據的不確定性，對數據偏差進行了校正，使結果更具有科學的解釋。PMF使用最小二乘方法，得到的污染源不需要轉換就可以直接與原始數據矩陣作比較，PMF方法能夠同時確定污染源和貢獻，而不需要事先知道源成分譜。適用於水文地質條件簡單，觀測數據量較大，污染源和污染種類相對較少的地區，運用簡便，可應用分析軟體進行計算。

3.2.4.5 NMF 源解析

NMF在實現上較PMF演算法簡單易行，非負矩陣分解根據目的的不同大致可以分為兩種：一是在保證數據某些性質的基礎上，將高維空間的樣本點映射到某個低維空間上，除去一些不重要的細節，獲得原數據的本質信息；二是在從復雜混亂的系統中得到混合前的獨立信息的種類和強度。因此，基於非負矩陣分解過程應用領域的不同，分解過程所受的約束和需要保留的性質都不相同。本書嘗試性地將NMF演算法應用於水質影響因素的分離計算中（表3.2）。

表3.2 RMF矩陣分解權值表

依照非負矩陣分解理論的數學模型，尋找到一個分解過程V≈WH，使WH和V無限逼近，即盡可能縮小二者的誤差。在確保逼近的效果，定義一個相應的衡量標准，這個衡量標准就叫作目標函數。目標函數一般採用歐氏距離和散度偏差來表示。在迭代過程中，採用不同的方法對矩陣W和H進行初始化，得到的結果也會不同，演算法的性能主要取決於如何對矩陣W和H進行初始化。傳統的非負矩陣演算法在對矩陣W和H賦初值時採用隨機方法，這樣做雖然簡單並且容易實現，但實驗的可重復性以及演算法的收斂速度是無法用隨機初始化的方法來控制的，所以這種方法並不理想。許多學者提出改進W和H的初始化方法，並發展出專用性比較強的形式眾多的矩陣分解演算法，主要有以下幾種：局部非負矩陣分解（Local Non-negative Matrix Factorization，LNMF）、加權非負矩陣分解（Weighted Non-negative Matrix Factorization，WNMF）、Fisher非負矩陣分解（Fisher Non-negative Matrix Factorization，FNMF）、稀疏非負矩陣分解（Sparse Non-negative Matrix Factorization，SNMF）、受限非負矩陣分解（Constrained Non-negative Matrix Factorization，CNMF）、非平滑非負矩陣分解（Non-smooth Non-negative Matrix Factorization，NSNMF）、稀疏受限非負矩陣分解（Nonnegative Matrix Factorization with Sparseness Constraints，NMF-SC）等理論方法，這些方法針對某一具體應用領域對NMF演算法進行了改進。

本書嘗試應用MATLAB工具箱中NNMF程序與改進的稀疏非負矩陣分解（SNMF）對研究區11項指標（同PMF數據）進行分解，得到各元素在綜合成分中的得分H，初始W₀，H₀採用隨機法取初值。r為分解的基向量個數，合適的r取值主要根據試演算法確定，改變r值觀察誤差值變化情況，本書利用SMNF演算法計算時，r分別取2，3，4，採用均方誤差對迭代結果效果進行評價，結果顯示當r取2，4時誤差值為0.034，取3時誤差值為0.016，因此r＝3是較合理的基向量個數。採用NNMF演算法進行計算時，利用MATLAB工具箱提供的兩種計演算法分別進行計算，乘性法則（Multiplicative Update Algorithm）計算結果誤差項比最小二乘法（Alternating Least-squares Algorithm）計算誤差值小且穩定，但總體NNMF計算誤差較大，改變初始W₀，H₀取值和增加迭代次數誤差均未明顯減小，調整r取值，隨著r值的增大誤差逐漸減小。

對比SNMF和NNMF演算法所得權值結果，兩種方法所得權值趨勢一致，但得分值有所不同，由於SNMF演算法對矩陣進行了稀疏性約束，計算結果中較小的權值更趨近於0，兩次結果中在三個基向量上總體權值較大的元素項為T-Hard、

、Mg²⁺、Ca²⁺、

，從盲源分離的角度來看該幾種元素對地下水具有較大的影響，但從地下水水質影響因素來看，該方法對數據的分析偏重於突出局部數據的特徵，在各因素相關性較大但含量不高的情況下，容易忽略了關鍵的影響因素。從權值得分來看，SNMF法解析的第一個基向量上的元素包括EC、T-Hard、NH₄—N、

、

、TDS；第二基向量主要有Na⁺、Mg²⁺、Cl^-；第三個基向量

、Ca²⁺，從結果可以看出該方法進行矩陣分解並未得到可合理解釋的源項結果，方法有待進一步研究及驗證。

F. 【轉】矩陣分解之SVD和SVD++

前面的內容是關於近鄰推薦的相關知識，來看下另外一種推薦方法：矩陣分解。

協同過濾可以解決我們關注的很多問題，但是仍然有一些問題存在，比如：

上述兩個問題，在矩陣分解中可以得到解決。原始的矩陣分解只適用於評分預測問題，這里所討論的也只是針對於評分預測問題。常用的分解演算法有SVD和SVD++。

矩陣分解，簡單來說，就是把原來的大矩陣，近似分解成兩個小矩陣的乘積，在實際推薦計算時不再使用大矩陣，而是使用分解得到的兩個小矩陣。

具體來說，假設用戶物品評分矩陣為 R，形狀為 mxn，即 m 個用戶， n 個物品。我們選擇一個很小的數 k，k 比 m 和 n 都小很多，然後通過演算法生成兩個矩陣 P 和 Q，這兩個矩陣的要求如下：P 的形狀是 mxk，Q 的形狀是 nxk， P 和 Q 的轉置相乘結果為 R。也就是說分解得到的矩陣P和Q可以還原成原始的矩陣R。

用公式來描述就是：

其中 R 表示真實的用戶評分矩陣，一般有很多缺失值（缺失值表示用戶沒有對該物品評分），帶尖帽的 R 表示使用分解矩陣預測的用戶評分矩陣，它補全了所有的缺失值。

從另一個角度來看，矩陣分解就是把用戶和物品都映射到一個 k 維空間中（這里映射後的結果用戶用矩陣P表示，物品用矩陣Q表示），這個 k 維空間不是我們直接看得到的，也不一定具有非常好的可解釋性，每一個維度也沒有名字，所以常常叫做隱因子。用戶向量代表了用戶的興趣，物品向量代表了物品的鋒帆特點，且每一個維度相互對應，兩個向量的內積表示用戶對該物品的喜好程度。

SVD 全程奇異值分解，原本是是線性代數中的一個知識，在推薦演算法中用到的 SVD 並非正統的奇異值分解。

前面已經知道通過矩陣分解，可以得到用戶矩陣和物品矩陣。針對每個用戶和物品，假設分解後得到的用戶 u 的向量為 p_u，物品 i 的向量為 q_i，那麼用戶 u 對物品 i 的評分為：

其中，K 表示隱因子個數。

問題關鍵來了，如何為每個用戶和物品生成k維向量呢？這個問題可以轉化成桐瞎機器學習問題，要解決機器學習問題，就需要尋找損失函數以及優化演算法。

這里單個用戶對單個物品的真實評分與預測評分之間的差值記為 e{ui}。

將所有用戶對物品的真實評分與預測評分之間的差值的平方之和作為損失函數，即

其中，R 表示所有的用戶對所有物品的評分集合，K 表示隱因子個數。

我們要做的就是求出用戶向量 p_u 和物品向量 q_i ，來保證損失函數結果最小。

求解損失函數優化演算法常用的選擇有兩個，一個是梯度下降（GD），另一個是交替最小二乘（ALS） 。這里以梯度下降為例。

梯度下降演算法的一個關鍵點在於計算損失函數對於每個參數的梯度。

在實際應用中，會存在以下情況：相比於其他用戶，有些用戶給分就是偏高或偏低。相比於其他物品，有些物品就是能得到偏高的評分。所以使用 pu*qi^T 來定義評分是有失偏頗的。我們可以認為 評分 = 興趣 + 偏見。

其局基空中，μ表示全局均值， bu表示用戶偏見，bi表示物品偏見。

舉例來說，一個電影網站全局評分為 3.5 分，你評分電影時比較嚴格，一般打分比平均分都要低 0.5，《肖申克的救贖》的平均分比全局平均分要高 1 分。這里 u=3.5，bu=-0.5，bi=1分。

實際生產中，用戶評分數據很稀少，也就是說顯式數據比隱式數據少很多，這些隱式數據能否加入模型呢？

SVD++ 就是在 SVD 模型中融入用戶對物品的隱式行為。我們可以認為 評分=顯式興趣 + 隱式興趣 + 偏見。

那麼隱式興趣如何加入到模型中呢？首先，隱式興趣對應的向量也是 k 維，它由用戶有過評分的物品生成。

其中，|N(u)|表示用戶u的行為物品集，yj表示物品j所表達的隱式反饋。

介紹了在評分數據中非常受歡迎 SVD 演算法以及改進。比如加入偏置信息，考慮隱式反饋等。

推薦系統百問百答

參考：

G. 矩陣分解的一點總結

------------------------------------------------------------------------------------------------------------------------------------------------

對於推薦系統來說存在兩大場景即評分預測（rating prediction）與Top-N推薦（item recommendation，item ranking）。矩陣分解主要應用於評分預測場景。

推薦系統的評分預測場景可看做是一個矩陣補全的游戲，矩陣補全是推薦系統的任務，矩陣分解是其達到目的的手段。因此，矩陣分解是為了更好的完成矩陣補全任務（欲其補全，先其分解之）。之所以可以利用矩陣分解來完成矩陣補全的操作，那是因為基於這樣的假設：假設UI矩陣是低秩的，即在大千世界中，總會存在相似的人或物，即物以類聚，人以群分，然後我們可以利用兩個小矩陣相乘來還原它。

矩陣分解就是把原來的大矩陣，近似的分解成小矩陣的乘積，在實際推薦計算時不再使用大矩陣，而是使用分解得到的兩個小矩陣。

具體來說就是，假設用戶物品的評分矩陣A是m乘n維，即一共有m個用戶，n個物品.通過一套演算法轉化為兩個矩陣U和V,矩陣U的維度是m乘k，矩陣V的維度是n乘k。

這兩個矩陣的要求就是通過下面這個公式可以復原矩陣A:

說起矩陣分解，我們第一個想起的就是SVD。

SVD分解的形式為3個矩陣相乘，左右兩個矩陣分別表示用戶/項目隱含橘巧因子矩陣，中間矩陣為奇異值矩陣並且是對角矩陣，每個元素滿足非負性，並且逐漸減小。因此我們可以只需要前個K因子來表示它。

但SVD分解要求矩陣是稠密的，也就是說矩陣的所有位置不能有空白。有空白時我們的M是沒法直接去SVD分解的。大家會說，如果這個矩陣是稠密的，那不就是說我們都已經找到所有用戶物品的評分了嘛，那還要SVD幹嘛! 的確，這是一個問題，傳統SVD採用的方法是對評分矩陣中的缺失值進行簡單的補全，比如用全局平均值或者用用戶物品平均值補全，得到補全後的矩陣。接著可以用SVD分解並降燃伍逗維。

雖然有了上面的補全策略，我們的傳統SVD在推薦演算法上還是較難使用。因為我們的用戶數和物品一般都是超級大，隨便就成千上萬了。這么大一個矩陣做SVD分解是非常耗時的。那麼有沒有簡化版的矩陣分解可以用呢？我們下面來看看實際可以用於推薦系統的矩陣分解。

FunkSVD是在傳統SVD面臨計算效率問題時提出來的，既然將一個矩陣皮賣做SVD分解成3個矩陣很耗時，同時還面臨稀疏的問題，那麼我們能不能避開稀疏問題，同時只分解成兩個矩陣呢？也就是說，現在期望我們的矩陣M這樣進行分解：

SVD分解已經很成熟了，但是FunkSVD如何將矩陣M分解為P和Q呢？這里採用了線性回歸的思想。目標是讓用戶的評分和用矩陣乘積得到的評分殘差盡可能的小，也就是說，可以用均方差作為損失函數，來尋找最終的P和Q。

在實際應用中，為了防止過擬合，會加入一個L2的正則化項。加入了正則化系數，需要調參。對於這個優化問題，一般通過梯度下降法來進行優化得到結果。

在FunkSVD演算法火爆之後，出現了很多FunkSVD的改進版演算法。其中BiasSVD算是改進的比較成功的一種演算法。BiasSVD假設評分系統包括三部分的偏置因素：一些和用戶物品無關的評分因素，用戶有一些和物品無關的評分因素，稱為用戶偏置項。而物品也有一些和用戶無關的評分因素，稱為物品偏置項。這其實很好理解。比如一個垃圾山寨貨評分不可能高，自帶這種爛屬性的物品由於這個因素會直接導致用戶評分低，與用戶無關。

一個用戶給一個物品的評分會由四部分相加：

從左到右分別代表：全局平均分、物品的評分偏置、用戶的評分偏置、用戶和物品之間的興趣偏好

BiasSVD增加了一些額外因素的考慮，因此在某些場景會比FunkSVD表現好。

SVD++演算法在BiasSVD演算法上進一步做了增強，這里它增加考慮用戶的隱式反饋。它是基於這樣的假設：用戶除了對於項目的顯式歷史評分記錄外，瀏覽記錄或者收藏列表等隱反饋信息同樣可以從側面一定程度上反映用戶的偏好，比如用戶對某個項目進行了收藏，可以從側面反映他對於這個項目感興趣，具體反映到預測公式為：

學習演算法依然不變，只是要學習的參數多了兩個向量：x和y。一個是隱式反饋的物品向量，另一個是用戶屬性的向量，這樣在用戶沒有評分時，也可以用他的隱式反饋和屬性做出一定的預測。

它是基於這樣的假設：用戶的興趣或者偏好不是一成不變的，而是隨著時間而動態演化。於是提出了timeSVD，其中用戶的和物品的偏置隨著時間而變化，同時用戶的隱含因子也隨著時間而動態改變，在此物品的隱含表示並未隨時間而變化（假設物品的屬性不會隨著時間而改變）。

其中，t為時間因子，表示不同的時間狀態。

通過之前構建目標函數之後，就要用到優化演算法找到能使它最小的參數。優化方法常用的選擇有兩個，一個是隨機梯度下降(SGD)，另一個是交替最小二乘(ALS),在實際應用中，交替最小二乘更常用一些，這也是推薦系統中選擇的主要矩陣分解方法。
找到兩個矩陣P和Q，讓它們相乘後約等於原矩陣R:

P和Q兩個都是未知的，如果知道其中一個的話，就可以按照代數標准解法求得，比如知道Q，那麼P就可以這樣算：

也就是R矩陣乘Q矩陣的逆矩陣就得到了結果，反之，知道了P 再求Q 也一樣，交替最小二乘通過迭代的方式解決這個雞生蛋蛋生雞的難題：
1)、初始化隨機矩陣Q裡面的元素值

2)、把Q矩陣當做已知的，直接用線性代數的方法求得矩陣P

3)、得到了矩陣P後，把P當做已知的，故技重施，回去求解矩陣Q

4)、 上面兩個過程交替進行，一直到誤差可以接受為止

使用交替最小二乘好處：
1.在交替的其中一步，也就是假設已知其中一個矩陣求解另一個時，要優化的參數是很容易並行的；
2.在不是很稀疏的數據集合上，交替最小二乘通常比隨機梯度下降要更快的得到結果。

在很多推薦場景中，我們都是基於現有的用戶和商品之間的一些數據，得到用戶對所有商品的評分，選擇高分的商品推薦給用戶，這是funkSVD之類演算法的做法，使用起來也很有效。但是在有些推薦場景中，我們是為了在千萬級別的商品中推薦個位數的商品給用戶，此時，我們更關心的是用戶來說，哪些極少數商品在用戶心中有更高的優先順序，也就是排序更靠前。也就是說，我們需要一個排序演算法，這個演算法可以把每個用戶對應的所有商品按喜好排序。BPR就是這樣的一個我們需要的排序演算法。

BPR根據像交替最小二乘那樣完成矩陣分解，先假裝矩陣分解結果已經有了，於是就計算出用戶對於每個物品的推薦分數，只不過這個推薦分數可能並不滿足均方根誤差最小，而是滿足物品相對排序最佳

得到了用戶和物品的推薦分數後，就可以計算四元組的樣本中，物品1和物品2的分數差，這個分數可能是正數，也可能是負數，也可能是0。如果物品1和物品2相對順序為1，那麼希望兩者分數之差是個正數，而且越大越好；如果物品1和物品2的相對順序是0，則希望分數之差是負數，且越小越好。
目標函數：

把這個目標函數化簡和變形後，和把AUC當成目標函數是非常相似的，也正是因為如此，BPR模型宣稱該模型是為AUC而生的。

SVDFeature 是由上海交大Apex Data & Knowledge Management Lab(APEX)開發的一個推薦系統工具包。他們提出了一種基於feature 的矩陣分解的框架。

它的目的是有效地解決基於特徵的矩陣分解。新的模型可以只通過定義新的特徵來實現。

這種基於特徵的設置允許我們把很多信息包含在模型中，使得模型更加與時俱進。使用此工具包，可以很容易的把其他信息整合進模型，比如時間動態，領域關系和分層信息。除了評分預測，還可以實現pairwise ranking任務。

SVDFeature的模型定義如下：

輸入包含三種特徵<α，β，γ>，分別是用戶特徵，物品特徵和全局特徵。

SVD ：要求矩陣是稠密的，時間復雜度高。不推薦使用。
FunkSVD ：不在將矩陣分解為3個矩陣，而是分解為2個低秩的用戶項目矩陣，同時降低了時間復雜度。
BiasSVD ：考慮偏置項時使用，也就是用戶的愛好。
SVD++ ：考慮用戶的隱式反饋時使用。主動點評電影或者美食的用戶是少數，也就是說顯示反饋比隱式反饋少，這個時候就可以根據用戶的隱式反饋推薦。
timeSVD ：考慮時間因素時使用。人是善變的，隨著時間的流逝，興趣也會發生變化。
ALS ：考慮建模時間時使用。強烈推薦使用，這也是社交巨頭 Facebook 在他們的推薦系統中選擇的主要矩陣分解演算法。
BPR ：考慮排序結果時使用。
SVDFeature ：當我們有多個特徵時，可以使用。SVDFeature的目的就是解決基於特徵的矩陣分解。

矩陣分解演算法的缺點 ：都沒有解決冷啟動問題

准確率表示預測正確的樣本數占總樣本數的比例。

TP（true positive）：表示樣本的真實類別為正，最後預測得到的結果也為正；
FP（false positive）：表示樣本的真實類別為負，最後預測得到的結果卻為正；
FN（false negative）：表示樣本的真實類別為正，最後預測得到的結果卻為負；
TN（true negative）：表示樣本的真實類別為負，最後預測得到的結果也為負.

精確率表示預測為正樣本的樣本中，正確預測為正樣本的概率。

召回率表示正確預測出正樣本占實際正樣本的概率。

折中了召回率與精確率。

對於評分預測任務，一般都是根據原有的評分數據，利用矩陣分解等方法去擬合原評分，使得優化後的模型可以去預測新的評分，這里就要衡量你預測的評分和實際評分的差異了，指標也很簡單，分為RMSE和MSE。
MSE 是指參數估計值與參數真值之差平方的期望值;
MSE可以評價數據的變化程度，MSE的值越小，說明預測模型描述實驗數據具有更好的精確度。
RMSE ：RMSE是MSE的算術平方根。

AUC 這個值在數學上等價於：模型把關心的那一類樣本排在其他樣本前面的概率。最大是 1，完美結果，而 0.5 就是隨機排列，0 就是完美地全部排錯。
這個非常適合用來評價模型的排序效果，很適合作為BPR的評價指標。得到一個推薦模型後，按照它計算的分數，可以把用戶想要的物品排在最前面。

具體的計算過程可看我的另一篇 文章

其中Rel表示與用戶 u 相關的商品集（測試集）， Rec表示推薦給用戶的前K個列表，二者的交集除以Rec的集合元素個數（其實就是K），得到Precision@K。一般是算出每個用戶的Precision@K，然後取平均值。

其中Rel表示與用戶u相關的商品集（測試集），Rec表示推薦給用戶的前K個列表，二者的交集除以Rec的集合元素個數（也就是測試集中用戶u評過分的商品數），得到Recall@K。一般是算出每個用戶的Recall@K，然後取平均值。

MAP(Mean Average Precision)：單個主題的平均准確率是每篇相關文檔檢索出後的准確率的平均值。

主集合的平均准確率(MAP)是每個主題的平均准確率的平均值。

MAP 是反映系統在全部相關文檔上性能的單值指標。

系統檢索出來的相關文檔越靠前(rank 越高)，MAP就可能越高。如果系統沒有返回相關文檔，則准確率默認為0。
例如：

假設有兩個主題，主題1有4個相關網頁，主題2有5個相關網頁。

某系統對於主題1檢索出4個相關網頁，其rank分別為1, 2, 4, 7；

對於主題2檢索出3個相關網頁，其rank分別為1,3,5。

對於主題1，平均准確率為(1/1+2/2+3/4+4/7)/4=0.83。對於主題2，平均准確率為(1/1+2/3+3/5+0+0)/5=0.45。

則MAP= (0.83+0.45)/2=0.64。

正確檢索結果值在檢索結果中的排名來評估檢索系統的性能。

其中Q是用戶的個數，rank是對於第i個用戶，推薦列表中第一個在ground-truth結果中的item所在的排列位置。

舉個例子：假如檢索三次的結果如下，需要的結果（cat，torus，virus）分別排在3,2,1的話，此系統地MRR為（1/3 + 1/2 + 1)/3 = 11/18

比較復雜，可參考這篇 文章

參考文章：
https://blog.csdn.net/qq_40006058/article/details/89432773
https://blog.csdn.net/weixin_41362649/article/details/82848132
https://blog.csdn.net/qq_19446965/article/details/82079367
https://www.cnblogs.com/pinard/p/9128682.html
https://time.geekbang.org/column/article/5055

H. 個性化推薦演算法

演算法評估

1.個性化召回

用戶行為在個性化推薦系統中一般分兩種——顯性反饋行悔磨為（explicit feedback）和隱性反饋行為（implicit feedback）
隱性反饋行為指的是那些不能明確反應用戶喜好的行為。最具代表性的隱性反饋行為就是頁面瀏覽行為。

按照反饋的明確性分，用戶行為數據可以分為顯性反饋和隱性反饋，但按照反饋的方向分，
又可以分為正反饋和負反饋。正反饋指用戶的行為傾向於指用戶喜歡該物品，而負反饋指用戶的
行為傾向於指用戶不喜歡該物中帆品。在顯性反饋中，很容易區分一個用戶行為是正反饋還賣前雹是負反饋，
而在隱性反饋行為中，就相對比較難以確定。

P55

1 .1 LFM (latent factor model )
協同演算法
矩陣分解演算法的一種
LFM 應用

正則化防止過擬合

CF？？？演算法

I. 矩陣分解的奇異值分解法

奇異值分解 (singular value decomposition,SVD) 是另一種正交矩陣分解法；SVD是最可靠的分解法，但是它比QR 分解法要花上近十倍的計算時間。[U,S,V]=svd(A)，其中U和V分別代表兩個正交矩陣，而S代表一對角矩陣。 和QR分解法相同， 原矩陣A不必為正方矩陣。使用SVD分解法的用途是解最小平方誤差法和數據壓縮。
MATLAB以svd函數來執行svd分解法， 其語法為[S,V,D]=svd(A)。

J. 矩陣分解在協同過濾推薦演算法中的應用

矩陣分解在協同過濾推薦演算法中的應用
推薦系統是當下越來越熱的一個研究問題，無論在學術界還是在工業界都有很多優秀的人才參與其中。近幾年舉辦的推薦系統比賽更是一次又一次地把推薦系統的研究推向了高潮，比如幾年前的Neflix百萬大獎賽，KDD CUP 2011的音樂推薦比賽，去年的網路電影推薦競賽，還有最近的阿里巴巴大數據競賽。這些比賽對推薦系統的發展都起到了很大的推動作用，使我們有機會接觸到真實的工業界數據。我們利用這些數據可以更好地學習掌握推薦系統，這些數據網上很多，大家可以到網上下載。
推薦系統在工業領域中取得了巨大的成功，尤其是在電子商務中。很多電子商務網站利用推薦系統來提高銷售收入，推薦系統為Amazon網站每年帶來30%的銷售收入。推薦系統在不同網站上應用的方式不同，這個不是本文的重點，如果感興趣可以閱讀《推薦系統實踐》（人民郵電出版社，項亮）第一章內容。下面進入主題。
為了方便介紹，假設推薦系統中有用戶集合有6個用戶，即U={u1,u2,u3,u4,u5,u6}，項目（物品）集合有7個項目，即V={v1,v2,v3,v4,v5,v6,v7}，用戶對項目的評分結合為R，用戶對項目的評分范圍是[0, 5]。R具體表示如下：

推薦系統的目標就是預測出符號「？」對應位置的分值。推薦系統基於這樣一個假設：用戶對項目的打分越高，表明用戶越喜歡。因此，預測出用戶對未評分項目的評分後，根據分值大小排序，把分值高的項目推薦給用戶。怎麼預測這些評分呢，方法大體上可以分為基於內容的推薦、協同過濾推薦和混合推薦三類，協同過濾演算法進一步劃分又可分為基於基於內存的推薦（memory-based）和基於模型的推薦（model-based），本文介紹的矩陣分解演算法屬於基於模型的推薦。
矩陣分解演算法的數學理論基礎是矩陣的行列變換。在《線性代數》中，我們知道矩陣A進行行變換相當於A左乘一個矩陣，矩陣A進行列變換等價於矩陣A右乘一個矩陣，因此矩陣A可以表示為A=PEQ=PQ（E是標准陣）。
矩陣分解目標就是把用戶-項目評分矩陣R分解成用戶因子矩陣和項目因子矩陣乘的形式，即R=UV，這里R是n×m， n =6， m =7，U是n×k，V是k×m。直觀地表示如下：

高維的用戶-項目評分矩陣分解成為兩個低維的用戶因子矩陣和項目因子矩陣，因此矩陣分解和PCA不同，不是為了降維。用戶i對項目j的評分r_ij =innerproct(u_i, v_j)，更一般的情況是r_ij =f(U_i, V_j)，這里為了介紹方便就是用u_i和v_j內積的形式。下面介紹評估低維矩陣乘積擬合評分矩陣的方法。
首先假設，用戶對項目的真實評分和預測評分之間的差服從高斯分布，基於這一假設，可推導出目標函數如下：

最後得到矩陣分解的目標函數如下：

從最終得到得目標函數可以直觀地理解，預測的分值就是盡量逼近真實的已知評分值。有了目標函數之後，下面就開始談優化方法了，通常的優化方法分為兩種：交叉最小二乘法（alternative least squares）和隨機梯度下降法（stochastic gradient descent）。
首先介紹交叉最小二乘法，之所以交叉最小二乘法能夠應用到這個目標函數主要是因為L對U和V都是凸函數。首先分別對用戶因子向量和項目因子向量求偏導，令偏導等於0求駐點，具體解法如下：

上面就是用戶因子向量和項目因子向量的更新公式，迭代更新公式即可找到可接受的局部最優解。迭代終止的條件下面會講到。
接下來講解隨機梯度下降法，這個方法應用的最多。大致思想是讓變數沿著目標函數負梯度的方向移動，直到移動到極小值點。直觀的表示如下：

其實負梯度的負方向，當函數是凸函數時是函數值減小的方向走；當函數是凹函數時是往函數值增大的方向移動。而矩陣分解的目標函數L是凸函數，因此，通過梯度下降法我們能夠得到目標函數L的極小值（理想情況是最小值）。
言歸正傳，通過上面的講解，我們可以獲取梯度下降演算法的因子矩陣更新公式，具體如下：

（3）和（4）中的γ指的是步長，也即是學習速率，它是一個超參數，需要調參確定。對於梯度見（1）和（2）。
下面說下迭代終止的條件。迭代終止的條件有很多種，就目前我了解的主要有
1） 設置一個閾值，當L函數值小於閾值時就停止迭代，不常用
2） 設置一個閾值，當前後兩次函數值變化絕對值小於閾值時，停止迭代
3） 設置固定迭代次數
另外還有一個問題，當用戶-項目評分矩陣R非常稀疏時，就會出現過擬合（overfitting）的問題，過擬合問題的解決方法就是正則化（regularization）。正則化其實就是在目標函數中加上用戶因子向量和項目因子向量的二范數，當然也可以加上一范數。至於加上一范數還是二范數要看具體情況，一范數會使很多因子為0，從而減小模型大小，而二范數則不會它只能使因子接近於0，而不能使其為0，關於這個的介紹可參考論文Regression Shrinkage and Selection via the Lasso。引入正則化項後目標函數變為：

（5）中λ_1和λ_2是指正則項的權重，這兩個值可以取一樣，具體取值也需要根據數據集調參得到。優化方法和前面一樣，只是梯度公式需要更新一下。
矩陣分解演算法目前在推薦系統中應用非常廣泛，對於使用RMSE作為評價指標的系統尤為明顯，因為矩陣分解的目標就是使RMSE取值最小。但矩陣分解有其弱點，就是解釋性差，不能很好為推薦結果做出解釋。
後面會繼續介紹矩陣分解演算法的擴展性問題，就是如何加入隱反饋信息，加入時間信息等。