推薦演算法入門（2）Python 手寫 SVD 與 Funk-SVD 篇
對於一個大型的視頻網站來說，我們需要「好」的內容的視頻的權重被迅速提拔起來被更多的人看見，那麼就需要一套完整的評分系統，預測評分顯得尤為重要了。不過，並不是所有的協同過濾結果都是合理的，比如說，大部分電商平檯面臨的刷單問題，其實就是欺騙推薦系統獲取權重的方法。
這一節，我們主要介紹 SVD，通過矩陣分解的方法來降低數據中的噪點，將數據最終轉化成特徵向量。
上文鏈接：
今晚的風兒很喧囂：推薦演算法入門（1）相似度計算方法大全
數據來源：
以下題目和數據均來自於千里碼，一個優質的程序員答題網站。
現在從豆瓣的用戶中抽取了500左右個比較活躍的用戶，這些用戶都是忠實的電影迷，大部分人涉獵了上百部電影。
這裡有個80多萬行的文本文件，文件的每行是三個數字，分別是 userid，movieid，rating。代表一個用戶對一部電影的評分。rating代表評分的星級，如上圖中的紅框所示，星級從低到高依次是1-5。接下來有個行數為10001的文本文件（第一行為title），文件的每行為2個數字，分別代表userid和movieid，請你預測如果該用戶觀看了這部電影，會給該電影打多少分，你的預測值為1個大小為1-5的整數。本題的答案是一個長度為1萬的字元串，字元串的第k位代表你對第k行的預測結果。如果你的預測結果和實際答案的差值的絕對值的和小於6000，通過該題。
或許你有更多的方法實現推薦，不來千里碼試試嗎？
答案提交地址：
http://www.qlcoder.com/task/7650一、矩陣奇異值分解（Singular Value Decomposition）
在很多情況下，數據的一小部分包含了數據的絕大部分信息，用線性代數的許多矩陣分解方法都可以將矩陣特徵表現成新的易於理解的形式，在這一過程之中，實際是一個提取數據集合特徵值的過程，有利於我們提高演算法的精準度，減少數據運算量。
最常見的矩陣分解演算法就是矩陣奇異值分解（SVD），SVD 在圖像壓縮、推薦系統、金融數學等領域都有應用，著名的主成成分分析演算法（PCA）也是通過 SVD 實現的。
二、SVD 理論簡介
假設數據 M 是一個 m*n 階的樣本矩陣，其中的元素全部屬於域 K，那麼矩陣分解可得：
描述成： U（m*m），sigma（m*n），VT（n*n）
矩陣 sigma 除了對角元素不為0以外，其他元素都為0，並且對角元素是從大到小順序排列的，這些對角元素就是奇異值。
所以。對於任意的奇異值分解，矩陣 sigma 的對角線上的元素等於M的奇異值。U和V的列分別是奇異值中的左奇異向量和右奇異向量。
這一段是來源於百度百科的介紹，其實已經解釋清楚了 SVD 是啥了，那麼 SVD 的三個矩陣如何計算？如果你不想過多了解也沒關係，因為單靠原始的 SVD 效率並不是很高，想要手擼 SVD的，這篇文章講的比我好。
漫漫成長：奇異值分解（SVD）
三、SVD 圖像降噪
這是一個圖像化說明 svd 的例子，雖然各種意義上面的意義不明。
保留的奇異值越多，圖片的特徵保留的越明顯，當奇異值減少時，圖片中的像素間的差距逐漸減小（表現的模糊）。
import numpy as npfrom PIL import Image# 使用奇異值總和的百分比進行篩選def svd(data,scale): # scale 代表你要保留的奇異值比例 u,sigma,v = np.linalg.svd(data) svd_data = np.zeros(data.shape) total = sum(sigma) sum_data = 0 for index,item in enumerate(sigma): svd_data += item * np.dot(u[:,index].reshape(-1,1),v[index,:].reshape(1,-1)) sum_data += item if sum_data >= scale * total: break return svd_datadef compress(data,scale): r = svd(data[:,:,0],scale) g = svd(data[:,:,1],scale) b = svd(data[:,:,2],scale) result = np.stack((r,g,b),2) result[result > 255] = 255 result[result < 0] = 0 result = result.astype(int) return resultif __name__ == __main__: image = Image.open(test.jpg) width,height = image.size arr = np.zeros((width,height,3)) # RGB for x in range(width): for y in range(height): arr[x][y] = image.getpixel((x, y)) # 原生 range 不支持浮點數，所以用 np.arange 代替 for c in np.arange(.1,.9,.2): result = compress(arr,c) for x in range(width): for y in range(height): image.putpixel((x, y),(result[x,y,0],result[x,y,1],result[x,y,2])) image.save(test_+str(int(100 * c))+%.jpg)
四、Netflix Prize
提到協同過濾演算法，也提了 svd，就不得不提由美國 Netflix 公司舉辦的 Netflix Prize，這是一個旨在解決電影評分預測問題的競賽，因為高昂的獎金，已經成為了協同過濾發展的風尚了。
也許你已經看過了很多的關於 svd 的文章了，也已經悉知了 svd 的原理了，決定向領導打包票開始寫高階協同過濾演算法了。然後翻了翻往年的 Netflix Prize，納尼。。。 我是誰？我在哪？然後可以收拾收拾刪庫跑路了。推薦演算法水之深，我們都是新萌。
Netflix Prize - Wikipedia
五、Netflix Prize 大放異彩的 Funk SVD 演算法
1. 傳統 SVD 分解在元素缺失上面的問題
歷史上對缺失值的研究有很多，對於一個沒有被打分的物品來說，到底是應該給它補一個 0 值，還是應該給它補一個平均值呢？由於在實際過程中，元素缺失值是非常多的，這就導致了早期的 SVD 不論通過以上哪種方法進行補全在實際的應用之中都是不可以被接受的。
直到 2006年 Netflix Prize 中 Simon Funk 在博客公開的演算法。將評分矩陣分解成兩個低維矩陣相乘，Simon Funk的思想很簡單：可以直接通過訓練集中的觀察值利用最小化均方根學習P，Q矩陣。這種模型也被稱作是 LFM （隱語義模型），下面是他當年的博客，有興趣可以了解一下。
Try This at Home
簡單的來說就是將原本的 SVD 的思想上加上了線性回歸，也就是說，我們可以用均方差作為損失函數，來尋找 P 和 q 的最終值，線性回歸和均方差對於機器學習的同學們來說一定不陌生了，如果你還沒有了解過，可能一下子理解不了下面的公式，那麼我建議還是先從線性回歸學起，便於理解。不過，線性回歸也就是一句話 —— 線性函數參數調優。
今晚的風兒很喧囂：斯坦福大學機器學習課程（介紹和線性回歸）
2.加入偏移項後的 Funk-SVD
在 Funk-SVD 獲得巨大成功之後，很多著名的模型都是對 Funk-SVD 進行縫縫補補得到的（詳情可參見 Netflix Prize `Koren:2009` `Ricci:2010`），於是就有了在預測模型中添加三項偏移的模型，被稱為 BaisSVD。
- Biased Item
- Biased User
- Biased Mean
Biased Item（物品偏移），表示了物品接受的評分和用戶沒有多大關係，物品本身質量決定了的偏移。
Biased User（用戶偏移），有些用戶喜歡打高分，有些用戶喜歡打低分，用戶決定的偏移。
Biased Mean（全局平均值偏移），根據網站全局打分設置的偏移，可能和整體用戶群和物品質量有相對應的關係。
3.公式說明
符號含義：
rates 學習率
regularization 正則化項 b biased 偏移
矩陣 M 經過Funk SVD 分解之後，只分解出兩個矩陣P和Q：
對於某一個用戶的評分使用 Funk SVD 進行矩陣分解得到的結果就是：
那麼我們需要最小化的損失函數就是：
損失就是：
使用隨機梯度下降調參：
還有一種情況就是，拋棄biased，也就是：
最後
和其他的氣人博主不同，掛完公式不掛代碼。下一節，我們將提取開源庫 Surprise 中的核心思想，僅依賴 numpy 手擼高效的 SVD 演算法（又想騙我裝機器學習環境），基本完成本題需求。其實 github 已經有完備註釋，可以提前查看的啦。。。
如有錯誤歡迎指出。關愛新萌，人人有責。
持續更新的github倉庫鏈接：
ThomasHuai/Recommend
歡迎點贊，歡迎評論一起交流學習，感謝支持。
推薦閱讀：
※Coursera Machine Learning疑惑與解答-第1篇-Week3 Assignments
※支持向量機SVM總結之拉格朗日對偶問題
※Lagrange Duality