推薦系統 | 矩陣分解(SVD)原理和實戰

本文收錄在推薦系統專欄，專欄系統化的整理推薦系統相關的算法和框架，並記錄了相關實踐經驗，所有代碼都已整理至推薦算法實戰集合(hub-recsys)。

目錄

一. 特徵分解

1.1 特徵求解：

1.2 標準化：

1.3 特徵分解條件

二. SVD

2.1 定義

2.2 求解方法

2.3 相關特性　

2.4 SVD的python實現

2.5 SVD在PCA中的應用

三. 推薦系統中的SVD

3.1 問題定義

3.2 SVD應用

3.2.1 traditional-SVD

3.2.2 FunkSVD

3.2.3 BiasSVD

3.2.4 SVD++

3.3 矩陣分解推薦小結

3.4 SVD實現用戶評分預測(MovieLens數據集)

特徵分解——>奇異值分解（SVD）——>隱語義模型（LFM），三個算法在前者的基礎上推導而成，按順序先後出現。三者均用於矩陣降維。其中：特徵分解可用於主成分分析。奇異值分解（SVD）和隱語義模型（LFM）可用於推薦系統中，將評分矩陣補全、降維。
一. 特徵分解

1.1 特徵求解：

特徵分解是指將矩陣分解為由其特徵值和特徵向量表示的矩陣之積的方法，我們首先回顧下特徵值和特徵向量的定義：

上式中，λ是矩陣A的一個特徵值，x是矩陣A的特徵值λ對應的一個n維特徵向量。站在特徵向量的角度，特徵向量的幾何含義是：特徵向量x通過方陣A變換，只縮放，方向不變。

求得A的n個特徵值後，組成對角矩陣∑，A的特徵分解就可以表示為：

其中U是n個特徵向量組成的n×n維方陣，∑是這n個特徵值為主對角線的n×n維方陣。

1.2 標準化：

一般我們會把U的這n個特徵向量標準化（可使用施密特正交化方法），即滿足||𝑤𝑖||2=1, 或者說𝑤𝑖𝑇𝑤𝑖=1。標準化後∑的𝑛個特徵向量為標準正交基，滿足∑𝑇∑=𝐼，即∑𝑇=∑−1, 也就是說∑為酉矩陣。這樣我們的特徵分解表達式可以寫成

1.3 特徵分解條件

根據上述條件，實對稱矩陣一定可以進行特徵分解。但是針對更一般的情況，由於特徵分解矩陣A必須為方陣，對於行和列不相同的矩陣，應該如何分解，可以引出我們下文討論的SVD。

二. SVD
2.1 定義

SVD也是對矩陣進行分解，但是和特徵分解不同，SVD並不要求要分解的矩陣為方陣。假設我們的矩陣A是一個𝑚×𝑛的矩陣，那麼我們定義矩陣A的SVD為：

其中U是一個𝑚×𝑚矩陣，Σ是一個𝑚×𝑛矩陣，除了主對角線上的元素以外全為0，主對角線上的每個元素都稱為奇異值，V是一個𝑛×𝑛的矩陣。U和V都是酉矩陣，即滿足𝑈𝑇𝑈=𝐼,𝑉𝑇𝑉=𝐼。

2.2 求解方法

那麼我們如何求出SVD分解後的𝑈,Σ,𝑉，簡單的方式是和轉置矩陣相乘，獲得方陣，然後再對方陣進行特徵分解。

利用式（2-2）特徵值分解，得到的特徵矩陣即為𝑈；利用式（2-3）特徵值分解，得到的特徵矩陣即為𝑉；對Σ𝑇Σ或的特徵值開方，可以得到所有的奇異值。

2.3 相關特性　

奇異值可以被看作成一個矩陣的代表值，或者說，奇異值能夠代表這個矩陣的信息。當奇異值越大時，它代表的信息越多。也就是說，我們也可以用最大的k個的奇異值和對應的左右奇異向量來近似描述矩陣，並且SVD的求解可實現並行化，SVD的缺點是分解出的矩陣解釋性往往不強，有點黑盒子的味道，不過這不影響它的使用。

2.4 SVD的python實現

矩陣數據讀取

import numpy as np
import pandas as pd
from scipy.io import loadmat
 
# 讀取數據，使用自己數據集的路徑。
train_data_mat = loadmat("../data/train_data2.mat")
train_data = train_data_mat["Data"]
print(train_data.shape)


特徵值分解
# 數據必需先轉為浮點型，否則在計算的過程中會溢出，導致結果不準確
train_dataFloat = train_data / 255.0
# 計算特徵值和特徵向量
eval_sigma1,evec_u = np.linalg.eigh(train_dataFloat.dot(train_dataFloat.T))


計算奇異矩陣
#降序排列後，逆序輸出
eval1_sort_idx = np.argsort(eval_sigma1)[::-1]
# 將特徵值對應的特徵向量也對應排好序
eval_sigma1 = np.sort(eval_sigma1)[::-1]
evec_u = evec_u[:,eval1_sort_idx]
# 計算奇異值矩陣的逆
eval_sigma1 = np.sqrt(eval_sigma1)
eval_sigma1_inv = np.linalg.inv(np.diag(eval_sigma1))
# 計算右奇異矩陣
evec_part_v = eval_sigma1_inv.dot((evec_u.T).dot(train_dataFloat))

上面的計算出的evec_u, eval_sigma1, evec_part_v分別為左奇異矩陣，所有奇異值，右奇異矩陣。


2.5 SVD在PCA中的應用
對於PCA降維而言，需要找到樣本協方差矩陣𝑋𝑇𝑋的最大的d個特徵向量，然後用這最大的d個特徵向量張成的矩陣來做低維投影降維。可以看出，在這個過程中需要先求出協方差矩陣𝑋𝑇𝑋，當樣本數多樣本特徵數也多的時候，這個計算量是很大的。
SVD也可以得到協方差矩陣𝑋𝑇𝑋最大的d個特徵向量張成的矩陣，但是SVD有個好處，有一些SVD的實現算法可以不求先求出協方差矩陣𝑋𝑇𝑋，也能求出我們的右奇異矩陣𝑉V。也就是說，我們的PCA算法可以不用做特徵分解，而是做SVD來完成。這個方法在樣本量很大的時候很有效。
PCA僅僅使用了我們SVD的右奇異矩陣，沒有使用左奇異矩陣。左奇異矩陣可以用於行數的壓縮。相對的，右奇異矩陣可以用於列數即特徵維度的壓縮，也就是我們的PCA降維。　　　　

三. 推薦系統中的SVD

在推薦系統 - 概述和技術演進中，我們提到利用矩陣分解是Model-Based協同過濾是廣泛使用的方法。

3.1 問題定義
在推薦系統中，我們常常遇到的問題是這樣的，我們有很多用戶和物品，也有少部分用戶對少部分物品的評分，我們希望預測目標用戶對其他未評分物品的評分，進而將評分高的物品推薦給目標用戶。比如下面的用戶物品評分表：
用戶\物品物品1物品2物品3物品4物品5物品6物品7用戶13
5

1
用戶2
2



4用戶3


4


用戶4

2


1用戶51


4

即對於一個M行（M個user），N列（N個item）的矩陣，我們的任務是要通過分析已有的數據（觀測數據）來對未知數據進行預測，即這是一個矩陣補全（填充）任務。

3.2 SVD應用3.2.1 traditional-SVD
此時可以將這個用戶物品對應的𝑚×𝑛矩陣𝑀進行SVD分解，並通過選擇部分較大的一些奇異值來同時進行降維，也就是說矩陣𝑀此時分解為：

從而可以使用矩陣的乘積對稀疏空缺物品的評分做預測，然後再對評分排序，將高評分的物品推薦給用戶。
缺點：
評分矩陣不稠密：用全局平均值或者用用戶物品平均值補全。
耗時巨大：userItem維度通常很大，SVD分解耗時巨大的。
分解方式比較單一，獲取的特徵的方式不夠靈活，是否可以完全表徵用戶和item特徵。

3.2.2 FunkSVD
FunkSVD用於解決 traditional-SVD 計算耗時大的問題，同時避免解決稀疏的問題，將期望矩陣𝑀分解成兩個矩陣Q和P的乘積。

FunkSVD如何將矩陣𝑀分解為𝑃和𝑄呢？這裡採用了線性回歸的思想。我們的目標是讓用戶的評分和用矩陣乘積得到的評分殘差儘可能的小，也就是說，可以用均方差作為損失函數，來尋找最終的𝑃和𝑄。借鑑線性回歸的思想，通過最小化觀察數據的平方來尋求最優的用戶和項目的隱含向量表示。同時為了避免過度擬合（Overfitting）觀測數據，加入正則項。

最終可通過梯度下降或者隨機梯度下降法來尋求最優解。
　　　　
3.2.3 BiasSVD
BiasSVD假設評分系統包括三部分的偏置因素：1. 用戶有一些和物品無關的評分因素，稱為用戶偏置項（用戶就喜歡打高分），2.物品也有一些和用戶無關的評分因素，稱為物品偏置項（山寨商品）
假設評分系統平均分為𝜇,第i個用戶的用戶偏置項為𝑏𝑖,而第j個物品的物品偏置項為𝑏𝑗，則加入了偏置項以後的優化目標函數如下所示：

通過迭代我們最終可以得到𝑃和𝑄，進而用於推薦。BiasSVD增加了一些額外因素的考慮，因此在某些場景會比FunkSVD表現好。

3.2.4 SVD++
SVD++算法在BiasSVD算法上進一步做了增強，這裡它增加考慮用戶的隱式反饋。

它是基於這樣的假設：用戶對於項目的歷史評分記錄或者瀏覽記錄可以從側面反映用戶的偏好，比如用戶對某個項目進行了評分，可以從側面反映他對於這個項目感興趣，同時這樣的行為事實也蘊含一定的信息。其中N(i)為用戶i所產生行為的物品集合；ys為隱藏的對於項目j的個人喜好偏置，是一個我們所要學習的參數；至於|N(i)|的負二分之一次方是一個經驗公式。

3.3 矩陣分解推薦小結
矩陣分解用於推薦方法本身來說，它容易編程實現，實現複雜度低，預測效果也好，同時還能保持擴展性，小的推薦系統用矩陣分解應該是一個不錯的選擇。
但是當數據的特徵和維度逐漸增多時，不再具備優勢，無法引入更多的side-information，同時也並沒有解決數據稀疏和冷啟動問題。

3.4 SVD實現用戶評分預測(MovieLens數據集)
'''Version:1.0Created on 2014-02-25@Author:Dior'''
import randomimport mathimport cPickle as pickle
class SVD():    def __init__(self,allfile,trainfile,testfile,factorNum=10):                self.allfile=allfile                self.trainfile=trainfile                self.testfile=testfile                self.factorNum=factorNum                self.userNum=self.getUserNum()                self.itemNum=self.getItemNum()                self.learningRate=0.01                self.regularization=0.05                self.initModel()        def getUserNum(self):        file=self.allfile        cnt=0        userSet=set()        for line in open(file):            user=line.split('\t')[0].strip()            if user not in userSet:                userSet.add(user)                cnt+=1        return cnt        def getItemNum(self):        file=self.allfile        cnt=0        itemSet=set()        for line in open(file):            item=line.split('\t')[1].strip()            if item not in itemSet:                itemSet.add(item)                cnt+=1        return cnt        def initModel(self):        self.av=self.average(self.trainfile)        self.bu=[0.0 for i in range(self.userNum)]        self.bi=[0.0 for i in range(self.itemNum)]        temp=math.sqrt(self.factorNum)        self.pu=[[(0.1*random.random()/temp) for i in range(self.factorNum)] for j in range(self.userNum)]        self.qi=[[0.1*random.random()/temp for i in range(self.factorNum)] for j in range(self.itemNum)]        print "Initialize end.The user number is:%d,item number is:%d,the average score is:%f" % (self.userNum,self.itemNum,self.av)         def train(self,iterTimes=100):        print "Beginning to train the model......"        trainfile=self.trainfile        preRmse=10000.0        for iter in range(iterTimes):            fi=open(trainfile,'r')                        for line in fi:                content=line.split('\t')                user=int(content[0].strip())-1                item=int(content[1].strip())-1                rating=float(content[2].strip())                                pscore=self.predictScore(self.av,self.bu[user],self.bi[item],self.pu[user],self.qi[item])                                eui=rating-pscore
                                self.bu[user]+=self.learningRate*(eui-self.regularization*self.bu[user])                self.bi[item]+=self.learningRate*(eui-self.regularization*self.bi[item])                for k in range(self.factorNum):                    temp=self.pu[user][k]                                        self.pu[user][k]+=self.learningRate*(eui*self.qi[user][k]-self.regularization*self.pu[user][k])                    self.qi[item][k]+=self.learningRate*(temp*eui-self.regularization*self.qi[item][k])                                        fi.close()                        curRmse=self.test(self.av,self.bu,self.bi,self.pu,self.qi)            print "Iteration %d times,RMSE is : %f" % (iter+1,curRmse)            if curRmse>preRmse:                break            else:                preRmse=curRmse        print "Iteration finished!"        def test(self,av,bu,bi,pu,qi):        testfile=self.testfile        rmse=0.0        cnt=0        fi=open(testfile)        for line in fi:            cnt+=1            content=line.split('\t')            user=int(content[0].strip())-1            item=int(content[1].strip())-1            score=float(content[2].strip())            pscore=self.predictScore(av,bu[user],bi[item],pu[user],qi[item])            rmse+=math.pow(score-pscore,2)        fi.close()        return math.sqrt(rmse/cnt)        def average(self,filename):        result=0.0        cnt=0        for line in open(filename):            cnt+=1            score=float(line.split('\t')[2].strip())            result+=score        return result/cnt        def innerProduct(self,v1,v2):        result=0.0        for i in range(len(v1)):            result+=v1[i]*v2[i]        return result    def predictScore(self,av,bu,bi,pu,qi):        pscore=av+bu+bi+self.innerProduct(pu,qi)        if pscore<1:            pscore=1        if pscore>5:            pscore=5        return pscore
if __name__=='__main__':    s=SVD("data\\u.data","data\\ua.base","data\\ua.test")            s.train()
排序學習（Learning to rank）綜述
今日頭條 | 推薦算法原理詳解
Tensorflow架構
喜歡的話點個在看吧👇