基于評分相似性的群稀疏矩陣分解推薦算法

盛 偉，王保云，何 苗，余 英

(云南師范大學 信息學院，昆明 650500)

基于評分相似性的群稀疏矩陣分解推薦算法

盛 偉，王保云*，何 苗，余 英

(云南師范大學 信息學院，昆明 650500)

(*通信作者電子郵箱wspbmly@163.com)

如何提高系統的推薦精度，是當前推薦系統面臨的重要問題。對矩陣分解模型進行了研究，針對評分數據的群結構性問題，提出了一種基于評分相似性的群稀疏矩陣分解模型(SSMF-GS)。首先，根據用戶的評分行為對評分數據矩陣進行分群，獲得相似用戶群評分矩陣；然后，通過SSMF-GS算法對相似用戶群評分矩陣進行群稀疏矩陣分解；最后,采用交替優化算法對模型進行求解。所提模型可以篩選出不同用戶群的偏好潛在項目特征，提升了潛在特征的可解釋性。在GroupLens網站上提供的MovieLens數據集上進行仿真實驗，實驗結果表明，所提算法可以顯著提高預測精度，平均絕對誤差(MAE)及均方根誤差(RMSE)指標均表現出良好的性能。

群稀疏；矩陣分解；L2,1范數正則化；潛在特征

0 引言

隨著Internet的快速發展，數據資源每天以幾何數量級增加，在如今電子商務蓬勃發展的時代，賣家提供的商品種類和數量非常龐大，如何快速有效地找到最需要的商品成為消費者的一個難題。在這種背景下，推薦系統(Recommender System, RS)應運而生，它能夠為消費者推薦潛在喜歡的商品。協同過濾(Collaborative Filtering, CF)方法[1]是推薦系統中應用比較廣泛的技術，其主要分為兩類：基于記憶(memory-based)和基于模型(model-based)。基于記憶的算法通過分析用戶的歷史喜好信息，尋找相似的用戶或項目，然后根據這些相似的用戶或項目對目標用戶的喜好程度進行預測，如K近鄰算法(K-Nearest Neighbor,KNN)。真實的購買環境中，用戶不可能對每一個項目進行評分，導致評分數據極度稀疏。當沒有足量的評分可用時，基于記憶的方法很難提供準確的預測[2]。基于模型的算法主要利用已有用戶喜好信息，訓練出一個推薦模型進行推薦，如基于矩陣分解[3-4]、概率模型[5]、圖模型[6]算法等。

矩陣分解推薦算法是一類實現簡單、預測精度高的CF推薦技術。它的目標是將原始評分矩陣分解為兩個低維度的潛在特征矩陣，這在一定程度上改善了數據稀疏性問題[7]。Koren等[3]詳述了矩陣分解算法在推薦系統中的應用，這些算法在一定程度上提高了推薦精度，但沒有考慮評分數據的群結構性問題。Salakhutdinov 等[4]提出了一種概率矩陣分解推薦算法，該算法較好地解決了冷啟動問題，但也沒有考慮評分數據的群結構性問題。Yuan等[8]提出了一種群稀疏矩陣分解推薦算法，該算法能夠挖掘多種類型的評分數據信息，但其僅針對評分數據具有列相關性的問題。

在推薦系統中，輸入數據往往是一種類型的評分矩陣，比如常見的圖書評分矩陣、電影評分矩陣等。現實生活中，用戶可以分為不同的群體，同一個群體內的用戶通常具有相似的興趣愛好，而評分矩陣中的一行表示一個用戶的評分行為，這使得評分矩陣的行具有很高的相關性。本文主要利用群稀疏約束將評分矩陣的群聚性轉化為用戶群與潛在特征的關系。以電影推薦系統為例，用戶群與潛在電影特征的關系如表1所示，存在3類觀影群體：年輕觀眾u1，女性觀眾u2，男性觀眾u3，每部電影用4個潛在特征來表示：恐怖、喜劇、動作和愛情。從表1中可以看出，u1選擇潛在特征{1}和{2}；u2偏好潛在特征{2}和{4}；u3喜好潛在特征{1}和{3}。本文的目的是根據評分相似性從評分矩陣中找出這3類群體，并篩選出它們喜好的潛在特征，而傳統的矩陣分解模型忽略了這些信息，這在一定程度上降低了推薦信息的利用率。

表1 用戶群與潛在電影特征的關系Tab. 1 Relationship between user groups and latent movie features

本文針對評分數據的群結構性問題，提出了一種基于評分相似性的群稀疏矩陣分解推薦算法(Score Similarity based Matrix Factorization recommendation algorithm with Group Sparsity，SSMF-GS)。該算法首先根據評分的相似性對用戶進行分群；然后在矩陣分解過程中利用L2,1范數訓練得到一個群稀疏的潛在用戶特征矩陣；最后通過潛在用戶特征矩陣和潛在項目特征矩陣的內積進行評分預測為目標用戶產生推薦。該方法可以自動篩選出不同用戶群的共有潛在項目特征和私有潛在項目特征，共有潛在特征表示用戶群之間的聯系，私有潛在特征則表示用戶群之間的差異。實驗結果證明本文算法具有較好的預測精度。

1 相關工作

1.1 矩陣分解推薦算法

設用戶全集為U={u1,u2,…,um}，項目全集為V={v1,v2,…,vm}，m表示用戶數量，n表示項目數量。記U中用戶ui對項目vj的評分為rij，rij=0表示用戶ui對項目vj沒有評分，完整的用戶-項目評分矩陣如表2所示。

表2 用戶-項目評分矩陣Tab. 2 User-Item rating matrix

協同過濾推薦系統中矩陣分解的思想是把評分矩陣分解為兩個低維數的矩陣p∈Rk*m和q∈Rk*n，它們分別用于描述用戶特征和項目特征。用戶和項目之間的評分關系可以通過這些潛在特征向量的內積來建模，如式(1)所示:

(1)

(2)

其中：λ表示正則化系數，K表示已有評分集合，λ(‖pi‖2+‖qj‖2)被用來防止訓練過擬合。上述模型求解可以應用隨機梯度下降(Stochastic Gradient Descent, SGD)法和交替最小二乘迭代(Alternating Least Squares, ALS) 法。

1.2 群稀疏表示

稀疏表示(Sparse Representation)在圖像分類及圖像恢復等很多實際應用中表現出非常良好的性能，因而受到廣泛的關注。稀疏表示模型一般采用L1范數來度量稀疏性，沒有考慮稀疏數據的群結構性。在很多實際應用中，數據矩陣本質上具有群結構的特性。比如，相同題材的新聞可以組成一個群，不同主題的文檔形成不同的群等。群稀疏表示模型[9]主要考慮的是稀疏數據的群結構性, 它將稀疏數據進行分群, 分別考慮每個群的稀疏先驗，其主要采用L2,1范數來度量稀疏性。文獻[10]將L2,1范數應用于有效圖像特征選擇。文獻[11]利用L2,1范數定位采樣服務質量(Quality of Service, QoS)信息中的結構化噪聲行。本文主要將L2,1范數應用于群稀疏表示潛在用戶特征矩陣。對于任意矩陣X∈Rk*m，其L2,1范數定義如式(3)所示:

(3)

2 群稀疏矩陣分解推薦算法

2.1 評分預測問題建模

上述式(2)正則化矩陣分解模型并沒有考慮到評分矩陣的群結構特性，是一種全局優化的學習過程。本文算法在保持矩陣分解算法優點的同時，將用戶群結構先驗融入到矩陣分解過程中，得到一個群稀疏的潛在用戶特征矩陣。最后通過潛在用戶特征矩陣和潛在項目特征矩陣的內積對每個用戶群內的用戶進行評分預測。

在協同過濾推薦系統中，輸入數據通常用一個如表2所示的用戶-項目評分矩陣R來表示。R中的一行表示某一個用戶對所有物品的評分，可以看作該用戶的一個評分行為向量。現實生活中，許多用戶具有相同的興趣愛好，這使他們的評分行為高度相似。本文根據用戶的評分信息將用戶集合U劃分成C個用戶群，即：U=(u1,u2,…,uC)，每個用戶群對應一個評分矩陣，即：R=(R1,R2,…,RC)。對用戶進行分群，實際上是一種聚類問題，屬于同一簇的用戶自然被劃分到同一個群。目前的聚類方法有很多，主要有k-means、近鄰傳播(Affinity Propagation，AP)聚類[12]等。由于聚類算法不是研究的重點，所以本文采用簡單高效的k-means算法對用戶進行基本聚類。

(4)

如圖1基于評分相似性的群稀疏矩陣分解所示，原始評分矩陣被劃分為3部分：R1、R2和R3，分別對應評分用戶群u1、u2和u3，分解后得到的群稀疏潛在用戶特征矩陣為pc(c=1,2,3)(pc中灰色和白色行分別表示1和0)。由式(4)可知，pc中值為1的行可以篩選出uc用戶群的偏好潛在特征。從圖1可以看出，為u1、u2和u3篩選出的潛在項目特征分別為{1,2,3}，{1,2,4}和{1,3,4}。比較u1和u2偏好的潛在特征，{1,2}是兩個用戶群的共有潛在特征，{3}和{4}是各自的私有潛在特征。通過對pc(c=1,2,3)施加群稀疏約束，本文算法能夠學習到這些不同用戶群間的共有和私有潛在特征。

圖1 基于評分相似性的群稀疏矩陣分解Fig. 1 Score similarity based matrix factorization with group sparsity

基于上述對矩陣分解和群稀疏的分析，本文引入L2,1范數正則化項到矩陣分解模型中，將評分預測問題建模為如下問題:

(5)

2.2 模型求解

由于目標函數L(p,q)含有兩個變量，無法直接進行求解，為了避免同時存在多個變量，本文采用交替優化方法將式(5)分解成下述子問題交替求解變量pc和q：

(6)

(7)

(8)

(9)

其中E是一個k×k的單位矩陣。

固定p求解q類似地，L(q)對q.j求導，并令求導結果等于0，可得：

(10)

綜上，本文將問題(5)的求解過程命名為基于評分相似性的群稀疏矩陣分解推薦算法(SSMF-GS)，詳細步驟如算法1所示。

算法1 評分相似性的群稀疏矩陣分解推薦算法。

Input：聚類后評分矩陣Rc(c=1,2,…,C)參數βc，γ，λ

1)

initialize：pc(c=1,2,…,C)，q

2)

fork=1 toK

3)

forc=1 toC

4)

5)

end for

6)

forc=1 toC

7)

8)

end for

9)

通過式(10)更新q.j；

10)

end for Output：pc(c=1,2,…,C)，q

3 實驗驗證

3.1 實驗設置

本文實驗數據采用Movielens-100k數據集(http://grouplens.org/datasets/movielens/)，包含943個用戶對1 682部電影的評分，共100 000條評分記錄，評分區間為1～5分。為了全面地評價推薦模型，本文在3種訓練集上(80%、60%、40%)做了相關實驗來驗證SSMF-GS算法在不同稀疏情形下的性能。比如，80%的訓練集是從原始評分矩陣中隨機選取80%的評分數據作為訓練集，剩余的20%作為測試集。

3.2 度量標準

預測精度可以度量出真正評分和預測評分之間的接近程度，本文選擇平均絕對方差(Mean Absolute Error, MAE)和均方根誤差(Root Mean Squared Error, RMSE)作為預測精度的評價指標。

(11)

(12)

3.3 結果及分析

為了驗證本文算法的預測性能，將其應用于電影評分預測，并與基于用戶的K近鄰(User-basedK-Nearest Neighbors,UserKNN)[13]算法、矩陣填充(Matrix Completion, MC)[14]算法、概率矩陣分解(Probabilistic Matrix Factorization, PMF)[4]算法和正則化的矩陣分解(Regularized Matrix Factorization, RMF)[3]算法進行比較。

在UserKNN中，主要參數設置為目標用戶的鄰居數目e=10。在RMF模型中，主要參數設置為潛在特征維度k=5，正則化系數λ=0.01。MC算法的實現代碼下載于http://perception.csl.illinois.edu/matrix-rank/Files/inexact_alm_mc.zip，其參數按照設計者的方法設置。PMF算法的實現代碼下載于http://www.cs.toronto.edu/～rsalakhu/BPMF.html，主要參數設置為潛在特征維度k=5，正則化系數λ1=λ2=0.01。在SSMF-GS中，固定用戶群數目為50，主要參數設置為潛在特征維度k=5，正則化系數λ=0.08，為簡單起見βc(c=1,2,…,50)=1，80%訓練集中γ=120，60%訓練集中γ=120，40%訓練集中γ=150。文本利用Matlab(2014b)進行相關實驗，實現結果如表3所示。

表3 不同稀疏度情形下預測精度比較Tab. 3 Comparison of prediction accuracy under different sparsity

從表3中可以看出，基于矩陣分解的兩種算法PMF和RMF預測精度明顯優于基于記憶算法的UserKNN，這與上述對它們的分析是吻合的，在數據非常稀疏的情況下，基于記憶的算法無法找到足量的相似用戶，導致預測精度較差。隨著訓練數據集稀疏度的增加，幾種算法的預測性能也在下降，在40%的訓練集中PMF和RMF預測精度優勢并不是十分明顯，這表明基于矩陣分解的算法也受到了數據稀疏性的制約。本文算法融入了評分數據中相似用戶群的評分信息，相對于其他幾種算法，SSMF-GS算法在預測精度上得到了顯著提升。

本文隨機抽取2個用戶群的潛在特征向量進行分析。由于每個用戶群的用戶數量不等，本文選取用戶群的前5個用戶，潛在用戶特征數向量中值為0的用叉號表示，值不為0的用圓圈表示。從圖2可以看出，用戶群1偏好潛在特征為{1,2,3,4}，用戶群2偏好的潛在特征為{1,2,3}。其中{1,2,3}為共有潛在特征，{4}為用戶群1的私有潛在特征。這表明在真實數據中，本文算法能夠為不同的用戶群篩選出共有和私有潛在特征，這也和上述圖2分析一致。

圖2 用戶群的潛在特征向量Fig. 2 Latent feature vector of user group

3.4 參數γ的影響

參數γ為群稀疏正則化系數，在SSMF-GS算法中扮演了重要的角色。如果γ取值過小，則無法區分不同用戶群的潛在項目特征；如果γ取值過大，潛在項目特征矩陣則會產生過多的0行，導致極少的潛在項目特征被篩選出來。參數γ對MAE和RMSE的影響見圖3和圖4。

圖3 參數γ對RMSE的影響Fig. 3 Impact of parameter γ on RMSE

圖4 參數γ對MAE的影響Fig. 4 Impact of parameter γ on MAE

從圖4和圖5可以看出，80%及40%訓練集中γ為120，20%訓練集中γ為150時，RMSE及MAE最低，算法預測精度最優。

4 結語

矩陣分解推薦算法能有效地改善評分數據稀疏性問題，而群稀疏表示能夠挖掘評分數據呈現出的特殊群結構。結合兩者的優點，提出一種基于評分相似性的群稀疏矩陣分解推薦算法，該算法群稀疏表示潛在用戶特征矩陣，為用戶群篩選出共有和私有潛在項目特征，通過潛在用戶特征向量和潛在項目特征向量的內積來預測用戶群中用戶對項目的評分形成推薦結果。與其他幾種推薦算法相比，本文算法獲得了更好的預測精度。

References)

[1] 冷亞軍, 陸青, 梁昌勇. 協同過濾推薦技術綜述[J].模式識別與人工智能, 2014, 27(8): 720-734.(LENG Y J, LU Q, LIANG C Y. Survey of recommendation based on collaborative filtering[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(8): 720-734.)

[2] PAGARE R, PATIL S A. Study of collaborative filtering recommendation algorithm-scalability issue[J]. International Journal of Computer Applications, 2013, 67(25):10-15.

[3] KOREN Y, BELL R, VOLINSKY C. Matrix factorization tech-niques for recommender systems[J]. Computer, 2009, 42(8): 30-37.

[4] SALAKHUTDINOV B R, MNIH A. Probabilistic matrix factorization[C]// Proceedings of the 21st Annual Conference on Neural Information Processing Systems. New York: Curran Associate Inc,2008:1257-1264.

[5] ZHANG Y, KOREN J. Efficient Bayesian hierarchical user modeling for recommendation system[C]// Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2007: 47-54.

[6] PHAM T A N, LI X, CONG G, et al. A general graph-based model for recommendation in event-based social networks[C]// Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway, NJ: IEEE, 2015: 567-578.

[7] BOKDE D, GIRASE S, MUKHOPADHYAY D. Matrix factorization model in collaborative filtering algorithms: a survey [J]. Procedia Computer Science, 2015, 49(1):136-146.

[8] YUAN T, CHENG J, ZHANG X, et al. Recommendation by mining multiple user behaviors with group sparsity[EB/OL]. [2016-10-11]. http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/download/8267/8424.

[9] HUANG J, ZHANG T. The benefit of group sparsity[J]. The Annals of Statistics, 2010, 38(4): 1978-2004.

[10] 鄭秋中, 徐軍. 一種基于群稀疏特征選擇的圖像檢索方法[J]. 計算機應用研究, 2014, 31(9):2867-2872.(ZHENG Q Z, XU J. Group sparse based feature selection for image retrieval [J]. Application Research of Computers, 2014, 31(9):2867-2872.)

[11] 陳蕾, 楊庚, 陳正宇,等. 基于結構化噪聲矩陣補全的Web服務QoS預測[J]. 通信學報, 2015, 36(6):49-59. (CHEN L, YANG G, CHEN Z Y, et al. Web services QoS prediction via matrix completion with structural noise [J]. Journal on Communications, 2015, 36(6):49-59.)

[12] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[13] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]// Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, 1998: 43-52.

[14] LIN Z, CHEN M, MA Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL]. [2016-10-11].https://arxiv.org/pdf/1009.5055v3.pdf.

This work is partially supported by the Scientific Research Foundation of Education Department of Yunnan Province (2014Y145), the Philosophical and Social Science Program of Yunnan Province (QN2015067), the Doctoral Research Starting Foundation of Yunnan Normal University (01000205020503064).

SHENG Wei, born in 1988, M. S. candidate. His research interests include recommender system.

WANG Baoyun, born in 1977, Ph. D., lecturer. His research interests include machine learning.

HE Miao, born in 1990, M. S. candidate. Her research interests include machine learning.

YU Ying, born in 1965, M. S., associate professor. Her research interests include network communication.

Score similarity based matrix factorization recommendation algorithm with group sparsity

SHENG Wei, WANG Baoyun*, HE Miao,YU Ying

(SchoolofInformationScienceandTechnology,YunnanNormalUniversity,KunmingYunnan650500,China)

How to improve the accuracy of recommendation is an important issue for the current recommendation system. The matrix decomposition model was studied, and in order to exploit the group structure of the rating data, a Score Similarity based Matrix Factorization recommendation algorithm with Group Sparsity (SSMF-GS) was proposed. Firstly, the scoring matrix was divided into groups according to the users’ rating behavior, and the similar user group scoring matrix was obtained. Then, similar users’ rating matrix was decomposed in group sparsity by SSMF-GS algorithm. Finally, the alternating optimization algorithm was applied to optimize the proposed model. The latent item features of different user groups could be filtered out and the explanability of latent features was enhanced by the proposed model. Simulation experiments were tested on MovieLens datasets provided by GroupLens website. The experimental results show that the proposed algorithm can improve recommendation accuracy significantly, and the Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) both have good performance.

group sparsity; matrix factorization;L2,1-norm regularization; latent feature

2016-10-13;

2016-12-21。 基金項目:云南省教育廳科學研究基金資助項目(2014Y145);云南省哲學社會科學規劃項目(QN2015067);云南師范大學博士啟動基金資助項目(01000205020503064)。

盛偉(1988—)，男，江蘇豐縣人，碩士研究生，主要研究方向：推薦系統； 王保云(1977—)，男，云南玉溪人，講師，博士，主要研究方向:機器學習； 何苗(1990—)，女，云南曲靖人，碩士研究生，主要研究方向：機器學習； 余英(1965—)，女，云南昆明人，副教授，碩士，主要研究方向：網絡通信。

1001-9081(2017)05-1397-05

10.11772/j.issn.1001-9081.2017.05.1397

TP181

A