基于ASVD的協(xié)同過濾推薦算法

李春春,李 俊

(中國科學技術大學 信息科學技術學院 自動化系,合肥 230026)

1 引 言

協(xié)同過濾算法是現(xiàn)今個性化推薦領域應用最為成功的推薦算法[1].隨著隱語義模型[2]的提出和計算機集群運算能力的增強,基于協(xié)同過濾的個性化推薦算法已為電子商務等領域帶來巨大的商業(yè)價值[3],顯著提高系統(tǒng)的推薦質量,并有效提升用戶的體驗.

這其中最受研究者關注的就是SVD(Singular Value Decomposition,奇異值分解)模型[4].SVD用于解決用戶-項目評分矩陣中的數據稀疏性問題,通過將高維的稀疏評分矩陣降維,挖掘原始數據中用戶和項目的潛在特征,來補全矩陣中的缺失值,以預測用戶對未評分項目的實際評分.

文獻[5]提出將SVD模型應用到協(xié)同過濾推薦系統(tǒng)中,利用評分矩陣分解后的奇異值來分別構建用戶、項目的特征向量矩陣,從而挖掘出原始數據中的潛在語義特征來實現(xiàn)評分預測,但是需要事先將稀疏矩陣中的缺失值進行補全,造成巨大的計算開銷.文獻[2]提出了加入偏置的BSVD(Bias SVD)模型,在評分預測公式中加入用戶、項目各自特有的屬性,從而提升推薦系統(tǒng)的可解釋性,但是未有效利用用戶的歷史行為信息.文獻[6]進一步提出了隱語義模型SVD++,加入用戶歷史行為信息,并利用梯度下降法來更新SVD模型中的參數,取得了2006年Netflix Prize比賽冠軍.但是SVD++模型及其后續(xù)一些改進算法[7,8]只針對用戶的特征矩陣進行擴展,沒有考慮到項目的特征矩陣亦可以擴展的對偶性質.

本文針對電影評分預測問題,分析SVD方法的矩陣代數原理,采用矩陣分解模型對原始稀疏評分矩陣降維,構建用戶、電影各自的特征向量矩陣實現(xiàn)預測,充分考慮推薦系統(tǒng)中用戶、電影各自特有的屬性特征,以及用戶的歷史行為信息,利用包含用戶喜好(如瀏覽)的隱性特征向量矩陣替換原SVD模型中的用戶特征向量矩陣,實現(xiàn)非對稱SVD模型,并將項目的特征矩陣也進行擴展形成對偶模型.在MovieLens公開數據集上進行實驗,與目前廣泛使用的SVD++模型進行性能分析對比,探討基于ASVD的預測方法在協(xié)同過濾中應用的優(yōu)勢.

2 相關工作

目前影響協(xié)同過濾算法推薦精度的關鍵就是評分數據集的稀疏性問題,學者們通過引入機器學習和知識發(fā)現(xiàn)中的部分技術到協(xié)同過濾算法中,來克服這一問題,形成了各種基于模型的協(xié)同過濾算法,其中以基于SVD的算法最具有代表性.

文獻[9]通過加入標簽信息來構造用戶和項目的特征矩陣,同時考慮用戶評分的時間上下文信息來減低預測誤差.

文獻[10]提出一種非對稱的加權相似度協(xié)同過濾算法,通過計算用戶共同評分項目所占比例來確定用戶相似度非對稱加權因子,以表現(xiàn)用戶之間相互影響的差異性,但是該方法只能計算用戶之間的相似度,適用范圍有待擴展.

文獻[11]提出了一種ESVD算法,通過計算用戶和項目自身已知評分的流行度,在首次迭代時利用計算出的 “理想”評分來填充稀疏數據集中的未評分數據,接著在填充后的數據集上應用BSVD算法,以實現(xiàn)更加準確的矩陣分解模型,并且該算法考慮了用戶、項目的對稱性質,分別建立了基于用戶和基于項目的ESVD算法.但是該算法并沒有有效地利用數據集中用戶的歷史行為數據.

3 SVD原理分析

SVD模型是通過高維用戶項目評分矩陣分解后的奇異值來分別構建低維用戶、項目的特征向量矩陣,從而挖掘出原始數據中的潛在語義特征來實現(xiàn)評分預測.通過SVD可以得到任意矩陣的滿秩分解,實現(xiàn)數據壓縮.

3.1 正交變換

在歐幾里得空間中,一個正交矩陣對應的正交變換不改變任意向量的實際尺寸和向量的空間位置,只是通過正交變換將向量用另一組正交基表示.假設在二維空間中存在一個向量OA,用標準坐標系e1、e2表示為(a,b)T,用另一組坐標系e1′、e2′表示為(a′,b′)T,則存在正交矩陣U使得(a′,b′)T=U(a,b)T,即:

(1)

由式(1)可知,正交矩陣U行(列)向量之間都是兩兩正交的單位向量.如果認為坐標系不動,則U把向量OA順時針旋轉了θ角度.并且通過正交變換,將標準正交基e1、e2映射為另一組標準正交基e1′、e2′.

3.2 特征值分解

假設滿秩對稱矩陣Am×m的m個不同的特征值為ξi,i=1,2,…,m,對應的單位特征向量為xi,i=1,2,…,m,則有Axi=ξixi,令:

(2)

(3)

AU=UΛ

(4)

由于A是對稱陣,其特征向量兩兩正交,所以U是正交陣,進而有如下的特征值分解存在:

A=UΛU-1=UΛUT

(5)

假設用向量x左乘對稱陣A,就相當于對該向量的長度進行縮放,而且對坐標軸進行了旋轉,也就是矩陣A將一組標準正交基變換到了另一組標準正交基,來表示向量x.

3.3 奇異值分解

在機器學習領域,有相當多矩陣奇異值的應用,諸如做特征壓縮的主成分分析[12],搜索引擎的隱性語義分析[13],圖像壓縮相關算法[14],推薦系統(tǒng)[15]等.

特征值分解和奇異值分解的目標雖然都是提取矩陣的重要特征,但是二者還是有所區(qū)別.前述特征值分解模型的局限性在于A必須是對稱矩陣,但是現(xiàn)實中數據集所形成的矩陣大多都是m×n維(m≠n),奇異值分解就是解決任意矩陣分解與降維的模型.

對任意評分矩陣Am×n,假設其秩為l=rank(A),l≤m,本節(jié)的目標是通過SVD得到A的矩陣分解,即用戶、項目各自的特征向量矩陣.假設n維空間存在一組正交基{v1,v2,…,vn},經過A變換后的{Av1,Av2,…,Avn}還是兩兩正交的,則有:

(6)

如果正交基v選擇為ATA的特征向量,由于ATA是對稱陣,所以向量v之間兩兩正交,令ξ為ATA的特征值,有:

(7)

這樣就得到之前假設的n維空間的一組正交基.接著對映射后的正交基進行單位化,令u為單位向量,有:

(8)

Avi=σiui

(9)

vi稱為矩陣A的右奇異向量,ui為左奇異向量.分別對{v1,v2,…,vl}、{u1,u2,…,ul}正交基進行擴展,使得擴展后的{v1,v2,…,vn}、{u1,u2,…,um}分別為n維和m維空間中的正交基,得到矩陣A的奇異值分解為

(10)

式(10)中,U、V是正交陣,Σ是對角陣,且對角線上元素為σi,0≤i≤n.這個式子表示矩陣A將一個向量從V這組正交基空間旋轉到U這組正交基組成的空間,并且按照Σ在各個方向進行縮放,縮放倍數為A的奇異值大小.

4 基于ASVD的評分預測算法

針對推薦系統(tǒng)中的評分預測問題,作者對公式(10)進行簡化,令:

(11)

(12)

則可以得到矩陣A的矩陣分解為:

A=XY

(13)

因此可以利用用戶對項目的評分數據集構建一個評分矩陣R,行代表用戶,列代表項目,矩陣中的值代表用戶對項目的評分.則由公式(13)可以得到評分矩陣R的一個奇異值分解:

RU×I=PU×KQK×I

(14)

式中U代表用戶數,I代表項目數,K代表選取的隱特征數.基本的SVD預測方法就是利用R中的已知評分數據訓練P、Q兩個矩陣,以最好地擬合矩陣R,則未知評分項就可以通過式(15)計算:

(15)

4.1 Bias SVD

對實際數據集進行分析,發(fā)現(xiàn)用戶對項目的評分不僅取決于用戶和項目之間的某種潛在特征關系,還取決于推薦系統(tǒng)本身所采用數據集的特有屬性,以及用戶、項目自身的特有屬性[16],因此對SVD預測評分式進行改進,加入這幾項特有屬性信息,構成Bias SVD模型:

(16)

式中μ為訓練集所有已知評分的平均分,代表推薦系統(tǒng)自身的屬性,bu為用戶自身特有屬性,比如某用戶打分比較隨和,總是給分偏高,bi為項目自身特有屬性,比如某部優(yōu)秀獲獎影片,會受到用戶一致好評.實際訓練模型時,bu、bi所屬向量均初始化為0即可.

4.2 SVD++

更進一步分析訓練數據,在式(16)中加入用戶的歷史行為記錄,也就是用戶瀏覽過的項目信息(即使未評分),從而對用戶的特征矩陣P進行擴展,形成SVD++模型[6]:

(17)

式(17)中N(u)表示用戶u的行為記錄,即該用戶瀏覽的和評過分的項目集合大小,yj代表該項目集合的屬性向量.

4.3 ASVD

現(xiàn)實中大多數推薦系統(tǒng)的用戶數量成千萬級別甚至上億[17],如果還按照上述預測模型去存儲代表所有用戶屬性的二維矩陣,會占用巨大存儲空間和計算代價.考慮到用戶的歷史行為信息本身就能反映用戶的喜好特征,本文提出直接使用用戶評過分的項目和用戶瀏覽過但尚未評分的項目屬性來表示用戶屬性,并把這個模型稱之為非對稱奇異值分解模型(ASVD),預測公式如下:

(18)

式(18)中R(u)表示用戶u評過分的項目集合,N(u)表示用戶u瀏覽過但沒有評過分的項目集合,xj、yj分別代表相應項目集合的屬性向量.實際訓練模型時,xj、yj所屬向量也均初始化為0即可.

(19)

為了簡單起見,記:

(20)

以目標函數L關于各個參數偏導數的負數做為梯度下降的方向,則各參數的迭代更新式為:

qki=qki+α(euizk-λqki)

(21)

bu=bu+α(eui-λbu)

(22)

bi=bi+α(eui-λbi)

(23)

(24)

(25)

式中α代表學習速率,λ代表正則化系數,A、B代表的含義如下:

(26)

(27)

具體過程如算法1所示.

算法1.ASVD算法

輸入:用戶-項目評分訓練集R,測試集R′,隱特征數K,學習速率α,正則化系數λ,迭代次數iter,訓練閾值ε

1)按行讀取R、R′中所有用戶、項目ID至UserIDMap、ItemIDMap表中,并將已知評分和所有瀏覽數據以Node自定義形式存至rateMatrix、hisMatrix表中.

2)以rand(0,1)/sqrt(K)初始化qi所屬特征向量矩陣,其他參數所屬向量全部初始化為0.

3)根據迭代更新公式(21-25),利用R中所有數據訓練qi、xj、yj、bu、bi所屬向量.

4)判斷本輪與上一輪訓練誤差相差的絕對值是否小于既定閾值ε,小于,則跳至步驟6;否則,執(zhí)行步驟5.

5)如果迭代次數小于iter,跳至步驟3,否則,執(zhí)行步驟6.

在算法1中,輸入參數α、λ、iter的值需要重復大量的實驗進行調整,以使算法性能達到最優(yōu),此項工作這里不再贅述,后續(xù)實驗主要研究隱特征數K對模型預測精度的影響.

4.4 對偶模型

受到基于用戶和基于物品的協(xié)同過濾算法啟發(fā),本文進而提出ASVD模型的對偶算法(d-ASVD),保持用戶的特征向量不變,對項目的特征向量進行替換,使用對項目評過分的用戶集合和瀏覽過該項目但沒有評過分的用戶集合來表示項目屬性,展開后的d-ASVD預測公式如式(28)所示:

(28)

式(28)中R(i)表示給項目i評過分的用戶集合,N(i)表示瀏覽過項目i但沒有評過分的用戶集合,xv、yv分別代表相應用戶集合的屬性向量.

(29)

5 實驗結果與分析

5.1 數據集及評價指標

本文采用美國Minnesota大學GroupLens項目組在互聯(lián)網上公開的MovieLens數據集進行實驗[18],它也是國內外很多研究學者用來評價電影評分預測算法效果的熱門數據集,其中100k數據集中有100000條評分記錄,用戶數量943名,項目數量1682個;1M數據集中有1000209條評分記錄,用戶數量6040名,項目數量接近3900個,項目的評分是{1,2,3,4,5}整數集合中的一個.按照一定的規(guī)則分割這兩個數據集,均劃分成訓練集和測試集,比例為δ:1-δ,本文選取δ=0.8.在訓練數據集上訓練本文提出模型的各個參數,然后在測試數據集上利用訓練好的模型進行評分預測,得出預測精度.

本文選取RMSE(Root Mean Square Error,均方根誤差)作為預測精度的評價指標,該誤差越小,就代表模型的推薦效果越好:

(30)

5.2 結果分析

為驗證本文提出的ASVD算法及其對偶模型的預測精度,在MovieLens數據集上進行實驗,SVD++算法的基準RMSE采用文獻[19]給出的數據(如實驗結果圖中的紅線baseline所示).實驗中各個模型學習速率α、正則化系數λ的設置如表1所示.

表1 實驗參數配置Table 1 Experimental parameter configuration

實驗結果如圖1和圖2所示.

圖1 MovieLens100k上各算法RMSE比較Fig.1 RMSE comparison on MovieLens100k

由圖中實驗結果可知,ASVD算法及其對偶模型的預測精度隨著隱特征數的增加而增加,相比于SVD++模型,在MovieLens100k數據集上提升了4.3%的預測精度,在MovieLens1M數據集上提升了7.7%的預測精度.

圖2 MovieLens1M上各算法RMSE比較Fig.2 RMSE comparison on MovieLens1M

6 結束語

本文提出ASVD算法及其對偶模型,利用包含用戶喜好(如瀏覽)的隱性特征向量矩陣替換原SVD模型中用戶特征向量矩陣,實驗結果表明,本文提出的模型能有效提高推薦系統(tǒng)的預測精度.下一步考慮在ASVD及其對偶模型中加入標簽和時間信息,更充分地利用訓練數據中的隱含特征,并對預測公式進行擴展,加入基于鄰居的推薦算法形成多層混合推薦模型進行評分預測.

：

[1] Bokde D,Girase S,Mukhopadhyay D.Matrix factorization model in collaborative filtering algorithms:a survey[J].Procedia Computer Science,2015,49(4):136-146.

[2] Koren Y,Bell R,Volinsky C.Matrix factorization techniques for recommender systems[J].Computer,2009,42(8):30-37.

[3] Lu J,Wu D,Mao M,et al.Recommender system application developments:a survey[J].Decision Support Systems,2015,74(3):12-32.

[4] Hubbard J H,Hubbard B B.Vector calculus,linear algebra,and differential forms:a unified approach[M].Matrix Editions,2015.

[5] Sarwar B,Karypis G,Konstan J,et al.Application of dimensionality reduction in recommender system-a case study[C].Proceedings of the ACM WebKDD 2000 Web Mining for E-Commerce Workshop,ACM,New York,2000.

[6] Koren Y.Factorization meets the neighborhood:a multifaceted collaborative filtering model[C].Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM,Las Vegas,2008:426-434.

[7] Cao J,Hu H,Luo T,et al.Distributed design and implementation of SVD++ algorithm for e-commerce personalized recommender system[C].National Conference on Embedded System Technology,Springer Singapore,2015:30-44.

[8] Zhao J,Meng F,Wu W,et al.A novel social recommender algorithm based on SVD++ [J].International Journal of Computer Science and Information Security,2016,14(10):150-161.

[9] Dou Ling-yuan,Wang Xin-hua,Sun Ke.Collaborative filtering fusing label features and time comtext [J].Journal of Chinese Computer Systems,2016,37(1):48-52.

[10] Liu Zhu-song,Ou Shi-hua,Huang Shu-qiang.Collaborative filtering recommendation algorithm based on asymmetric weighted user similarity [J].Journal of Chinese Computer Systems,2017,38(4):721-725.

[11] Guan X,Li C T,Guan Y.Enhanced SVD for collaborative filtering[C].Pacific-Asia Conference on Knowledge Discovery and Data Mining.Springer International Publishing,2016:503-514.

[12] Shamir O.A Stochastic PCA and SVD algorithm with an exponential convergence rate[C].The 32nd International Conference on Machine Learning (ICML),2015:144-152.

[13] Alghamdi R,Alfalqi K.A survey of topic modeling in text mining [J].International Journal of Advanced Computer Science and Applications (IJACSA),2015,6(1):147-153.

[14] Rufai A M,Anbarjafari G,Demirel H.Lossy image compression using singular value decomposition and wavelet difference reduction[J].Digital Signal Processing,2014,24(1):117-123.

[15] Zhou X,He J,Huang G,et al.SVD-based incremental approaches for recommender systems[J].Journal of Computer and System Sciences,2015,81(4):717-733.

[16] Li C,Yang C.The research based on the matrix factorization recommendation algorithms[C].Advanced Information Management,Communicates,Electronic and Automation Control Conference (IMCEC),IEEE,2016:691-698.

[17] Harper F M,Konstan J A.The movielens datasets:history and context [J].ACM Transactions on Interactive Intelligent Systems (TiiS),2016,5(4):19:1-19:19.

[18] Igual L,Seguí S.Recommender systems[M].Introduction to Data Science，Springer International Publishing,2017:165-179.

[19] Meymandpour R,Davis J G.Enhancing recommender systems using linked open data-based semantic analysis of items[C].Proceedings of the 3rd Australasian Web Conference (AWC 2015),2015,27:11-17.

附中文參考文獻：

[9] 竇羚源,王新華,孫 克.融合標簽特征和時間上下文的協(xié)同過濾推薦算法[J].小型微型計算機系統(tǒng),2016,37(1):48-52.

[10] 劉竹松,歐仕華,黃書強.基于非對稱加權相似度的協(xié)同過濾推薦算法[J].小型微型計算機系統(tǒng),2017,38(4):721-725.