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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

1.1 矩陣分解推薦算法

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

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

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

(1)

(2)

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

1.2 群稀疏表示

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

(3)

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

2.1 評分預(yù)測問題建模

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

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

(4)

如圖1基于評分相似性的群稀疏矩陣分解所示，原始評分矩陣被劃分為3部分：R1、R2和R3，分別對應(yīng)評分用戶群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)施加群稀疏約束，本文算法能夠?qū)W習(xí)到這些不同用戶群間的共有和私有潛在特征。

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

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

(5)

2.2 模型求解

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

(6)

(7)

(8)

(9)

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

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

(10)

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

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

Input：聚類后評分矩陣Rc(c=1,2,…,C)參數(shù)β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 實驗設(shè)置

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

3.2 度量標準

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

(11)

(12)

3.3 結(jié)果及分析

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

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

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

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

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

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

3.4 參數(shù)γ的影響

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

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

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

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

4 結(jié)語

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

References)

[1] 冷亞軍, 陸青, 梁昌勇. 協(xié)同過濾推薦技術(shù)綜述[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]. 計算機應(yīng)用研究, 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] 陳蕾, 楊庚, 陳正宇,等. 基于結(jié)構(gòu)化噪聲矩陣補全的Web服務(wù)QoS預(yù)測[J]. 通信學(xué)報, 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。 基金項目:云南省教育廳科學(xué)研究基金資助項目(2014Y145);云南省哲學(xué)社會科學(xué)規(guī)劃項目(QN2015067);云南師范大學(xué)博士啟動基金資助項目(01000205020503064)。

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

1001-9081(2017)05-1397-05

10.11772/j.issn.1001-9081.2017.05.1397

TP181

A