張 昪

(蘭州財經(jīng)大學 信息工程學院，甘肅 蘭州 730000)

基于概率矩陣分解的推薦算法

張 昪

(蘭州財經(jīng)大學 信息工程學院，甘肅 蘭州 730000)

為了解決傳統(tǒng)協(xié)同過濾推薦算法的可擴展性差和數(shù)據(jù)稀疏性的問題，提出了一種基于隨機梯度下降的概率矩陣分解推薦算法。該算法是生成兩個服從高斯分布的隨機數(shù)矩陣，不斷訓練和更新使得這兩個矩陣的內(nèi)積趨近于用戶評分矩陣，為了避免模型過度擬合訓練數(shù)據(jù)，在此基礎上加入正則項進行約束，并通過批處理的隨機梯度下降法來優(yōu)化模型。在MovieLens提供的數(shù)據(jù)集上進行實驗驗證，與傳統(tǒng)的協(xié)同過濾算法相比較，該算法不僅緩解了可擴展性問題和稀疏性問題，而且推薦的準確度也得以提升。

推薦算法；協(xié)同過濾；概率矩陣分解(PMF)；隨機梯度下降法(SGD)

0 引言

隨著互聯(lián)網(wǎng)技術的飛速發(fā)展，當今社會已經(jīng)進入了信息爆炸的時代，人們想要從海量的數(shù)據(jù)中搜索到自己需求的信息無異于大海撈針，在這種情況下，個性化推薦技術迅速的發(fā)展起來。這是一種信息過濾手段，可以挖掘用戶的興趣愛好，針對不同的用戶提供個性化服務，解決了信息過載的問題。通過個性化推薦能使用戶從瀏覽者變?yōu)橘徺I者，提高用戶對網(wǎng)站的忠誠度，從而增加網(wǎng)站效益。目前幾乎所有電子商務、在線音樂視頻網(wǎng)站都不同程度的使用了推薦技術，例如國外的Amazon、Youtube、Pandora以及國內(nèi)的阿里巴巴、豆瓣電影、蝦米音樂等。

目前主流的推薦算法有六種[1]，即：協(xié)同過濾推薦、基于內(nèi)容推薦、基于關聯(lián)規(guī)則推薦、基于效用推薦、基于知識推薦和在以上五種推薦技術上的混合推薦算法。文獻[2]分析了各類算法的優(yōu)點和不足，提出了改進的方法和未來可能研究的方向。其中應用最為廣泛的是協(xié)同過濾算法[3]，但協(xié)同過濾算法仍存在以下幾種問題，如：推薦的實時性難以保證、算法的可擴展性差、冷啟動問題和稀疏性問題，針對這些問題有許多學者在協(xié)同過濾算法上進行了不同的改進。

為了提高推薦的實時響應速度，鄧愛林等提出項目聚類協(xié)同過濾算法[4]，根據(jù)用戶對項目評分的相似性對項目進行聚類，生成相應的聚類中心，在此基礎上計算目標項目與聚類中心的相似性，在推薦中考慮與目標項目在同一類中的其他項目，該算法可以有效地提高在線最近鄰查詢速度，但是推薦精度沒有顯著降低。李海霞提出將蟻群算法融合到協(xié)同過濾算法中[5]，該算法使用蟻群算法實現(xiàn)用戶聚類，從而在一定程度上降低了候選鄰居集的數(shù)量，然后在用戶簇中運用融合用戶和項目的協(xié)同過濾推薦算法對用戶進行推薦，雖然能夠解決候選鄰居集較大的問題，但是蟻群算法簇數(shù)目過高，并且存在蟻群算法的孤立點。

為了解決可擴展性差的問題，Sarwar BM等人提出基于奇異值分解的協(xié)同過濾算法[6]，將一個比較復雜的矩陣用更小更簡單的3個子矩陣的相乘來表示，這3個小矩陣描述了大矩陣重要的特性，該算法可以有效的解決一義多詞問題，顯著提高推薦系統(tǒng)的伸縮性，但是降維會導致信息損失，并且在空間維數(shù)很高的情況下，降維效果難以保證。

為了解決冷啟動問題，何佳知提出基于內(nèi)容和協(xié)同過濾的混合算法[7]，使用用戶-特征評分矩陣代替?zhèn)鹘y(tǒng)的用戶-項目評分矩陣，根據(jù)用戶對項目特征，對具有相同特征偏好的用戶進行聚類，生成相應的聚類中心，推薦時，首先確定目標用戶喜好的特征類型，再計算與所有聚類中心的相似性，從而確定最近鄰居的所屬簇，最后借助最近鄰完成對目標用戶的推薦。

為了解決數(shù)據(jù)稀疏性問題，許多研究者通過矩陣分解來降維，最早的矩陣分解模型利用的是奇異值分解[8]，但這個方法在一開始時需要對矩陣的缺失值進行填充，從而將一個稀疏矩陣轉化成一個稠密矩陣，然后進行分解，然而，對高維稠密矩陣進行分解的時間復雜度和空間復雜度都特別高。此外，常用的解決數(shù)據(jù)稀疏性問題的方法還有主成分分析方法[9]，通過主成分分析，降低矩陣的稀疏性，保留了最能代表用戶興趣的維度，提高了推薦的質(zhì)量，但該算法舍棄了部分用戶評價或用戶，不可避免的要損失一些有價值的信息。

本文為了解決數(shù)據(jù)稀疏性問題，也是以矩陣分解為基礎，提出了基于概率矩陣分解[10](Probabilistic Matrix Factorization，PMF)的方法，從概率的角度將用戶和項目的一些潛在信息映射到低維的特征空間，然后利用低維的特征向量的線性組合來解釋特定用戶對特定項目的喜好程度。此外，為了提高推薦速度，還加入了批處理模塊，使模型收斂更加穩(wěn)定，以得到用戶個性化的推薦。

1 問題描述

其中用戶未評分的項目用0代替，推薦算法就是要預測出用戶未測評的項目。

1.1 矩陣分解

矩陣分解的思想是每一個用戶和每一個項目都有自己的一些特性，矩陣分解的方法可以從用戶評分矩陣中分解出用戶-特征矩陣，項目-特征矩陣。

1.2 基于用戶的協(xié)同過濾

基于用戶的協(xié)同過濾算法(CF-User)主要利用整個用戶-項目評分矩陣進行推薦，尋找與目標用戶相似度高的用戶，認為目標用戶與其有相同的愛好，將該用戶選擇的項目推薦給目標用戶[11]。

該算法可以概括為兩步：

①計算用戶之間的相似度，構造用戶相似度矩陣；

②采用相應的算法估計評分，并據(jù)此為目標用戶進行推薦。

常用的相似度的計算方法有皮爾森相關系數(shù)[12]

(1)

余弦相似度[13]

(2)

按照相似度的大小進行排序，選擇前k個用戶或者相似度大于指定閾值的用戶作為最近鄰居集N。通過計算目標用戶x的最近鄰居集N來預測x未作評分的項目，具體方法如公式(3)：

(3)

最終可以選擇預測分數(shù)較高的前S個項目作為推薦結果。然而在一個系統(tǒng)中，用戶的數(shù)量是不斷發(fā)生變化的，此時基于用戶的協(xié)同過濾算法往往需要重新計算不同用戶間的相似度，更新用戶相似度矩陣，時間復雜度高，可擴展性差。

1.3 基于項目的協(xié)同過濾算法

基于項目的協(xié)同過濾算法(CF-Item)通過用戶-項目評價數(shù)據(jù)建模，也是利用用戶-項目評價數(shù)據(jù)進行推薦，計算不同項目之間的相似度，認為用戶會喜歡同一類項目，將相似度較高的項目推薦給目標用戶[14]。

該算法可以概括為兩步：

①計算項目之間的相似度，構造項目相似度矩陣；

②采用相應的算法估計評分，并據(jù)此將相似度較高的項目推薦給相關用戶。

構造項目相似度矩陣的方法以及目標用戶對項目預測評分的方法與基于用戶協(xié)同過濾的計算方法相類似。

基于項目的協(xié)同過濾算法同樣也存在著當項目不斷變化時，也要重新計算不同項目間的相似性，更新項目相似度矩陣，仍然存在著可擴展性差、時間復雜度高等問題。

2 基于概率矩陣分解的算法

(4)

其中，Iij為指示函數(shù)，Iij=1表示用戶i對項目j進行過評分，Iij=0表示用戶i對項目j未進行過評分。

(5)

(6)

由公式(4)、(5)、(6)可得到U和V的聯(lián)合概率分布：

(7)

對U和V的概率分布取對數(shù)得：

(8)

求解公式(8)的最大值可等價替換為求帶正則化參數(shù)的誤差函數(shù)的最小值，如公式(9)：

(9)

為了解出目標函數(shù)，本文采用隨機梯度下降法(SGD)，這種算法通過對參數(shù)求導的方法來找到目標函數(shù)的參數(shù)下降最快的方向，讓變量沿著這個方向不斷移動，直到移動到極小值點。

對它求導，可以發(fā)現(xiàn)每次迭代的時候，Ui和Vj的更新公式變成：

(11)

Ui←Ui+α×(e×Vj-λ×Ui)

(12)

Vj←Vj+α×(e×Ui-λ×Vj)

(13)

其中，α為隨機梯度下降的學習率。

此外，為了提高算法的推薦效率，加入了批處理模塊，對于實驗中的90000條訓練數(shù)據(jù)，將其分成9個批次，每次處理10000條數(shù)據(jù)，這樣很大程度上減少了模型訓練的運算量，同時也減小了對每條訓練數(shù)據(jù)進行計算時造成的模型收斂的不穩(wěn)定性。

基于概率矩陣分解的推薦算法如下：

輸入：訓練集train_vec，測試集probe_vec

輸出：預測評分pred_out，平方根誤差RMSE

①設置正則化參數(shù)，最大迭代次數(shù)maxepoch，分解維度feat

②生成電影數(shù)量(1682)feat和用戶數(shù)量(943)feat兩個標準正態(tài)分布矩陣

③if迭代次數(shù)epoch

④采用批處理，分為9個批次，每次處理10000條評分記錄，if批處理次數(shù)batch<9，

⑤計算損失函數(shù)p,根據(jù)負梯度方向不斷更新2)的兩個矩陣

⑥end

⑦讀入測試集，根據(jù)2的兩個矩陣計算測試集的預測評分，將大于5的評分替換為5，將小于1的評分替換為1

⑧計算RMSE

⑨end

3 實驗實證與分析

3.1 實驗環(huán)境

本文所涉及的實驗均在DELL計算機上實現(xiàn)，操作系統(tǒng)采用Windows7 32位，內(nèi)存為2G，處理器為AMDAthlon(tm)ⅡNeoK345Dual-CoreProcessor1.40GHz,本文提出的模型均在Matlab2012b平臺上用Matlab語言編寫實現(xiàn)。

3.2 數(shù)據(jù)集

本文將隨機選取90000條記錄作為訓練集，剩余10000條記錄作為測試集。

3.3 度量標準

預測評分準確度用來衡量算法計算出來的預測評分與用戶給出的真實評分之間的吻合程度，通過誤差來表示推薦結果是否符合用戶的需求。主要的評價指標有平均絕對誤差(MAE)和平均方根誤差(RMSE)[15]，而RMSE加大了對預測不準的用戶項目評分的懲罰(平方項的懲罰)，因而對推薦算法的評測更加苛刻。本文選用RMSE作為評價指標。

RMSE通過計算預測的用戶評分與實際的用戶評分之間的偏差來度量預測的準確性。推薦算法整體的RMSE越小，意味著推薦的質(zhì)量越高，算法的RMSE表示為公式(14)：

(14)

3.4 實驗結果分析

3.4.1 參數(shù)對實驗結果的影響

由圖1可以看出，當λ∈[0.05，0.1]時，模型的平方根誤差明顯獲得了較低的誤差，在下面的實驗中，統(tǒng)一取λ=0.1為最優(yōu)值。

3.4.2 分解維度和迭代次數(shù)對實驗結果的影響

實驗中動態(tài)考慮分解維度和迭代次數(shù)的影響，分別取迭代次數(shù)為10、20、30、40、50，分解維度為2、5、10、15、20，實驗結果如圖2所示。

由圖2可以看出，當分解維度不變的情況下隨著迭代次數(shù)的增加，RMSE略有下降；當?shù)螖?shù)不變的情況下分解維度先下降后又上升，在分解維度為5時取得最小的RMSE，因此迭代次數(shù)為50次，分解維度為5時，RMSE取得最小值。

3.4.3 不同算法預測準確度的比較

為了驗證PMF算法預測準確度的實際效果，將其與傳統(tǒng)的基于用戶和基于項目的協(xié)同過濾算法進行比較，分別選取鄰居個數(shù)為10、20、30、40、50，實驗結果如圖3所示。

由圖3可以看出，隨著鄰居個數(shù)的增加，CF-User和CF-Item算法的RMSE均有所上升，CF-Item算法的RMSE要低于CF-User算法，而PMF算法相比于其他兩種算法在不同的鄰居個數(shù)的情況下均能獲得較低的RMSE值，由此也證明了PMF算法確實能提高推薦算法的預測準確度。

3.4.4 數(shù)據(jù)稀疏性對實驗結果的影響

為了驗證PMF算法的抗稀疏性的效果，下面將分為4組對比實驗，查看數(shù)據(jù)越來越稀疏的情況下，PMF算法和CF算法的推薦效果，實驗結果如圖4所示。

*注：①將數(shù)據(jù)集中訓練集隨機取80000條作為訓練集，測試集保持不變；②將數(shù)據(jù)集中訓練集隨機取70000條作為訓練集，測試集保持不變；③將數(shù)據(jù)集中訓練集隨機取60000條作為訓練集，測試集保持不變；④將數(shù)據(jù)集中訓練集隨機取50000條作為訓練集，測試集保持不變由圖4可以看出，隨著數(shù)據(jù)越來越稀疏，三種算法的RMSE都略有上升，但PMF算法的RMSE始終低于CF-Item和CF-User算法，有著更好的抗稀疏性。

3.4.5 可擴展性對實驗結果的影響

將實驗數(shù)據(jù)集由原來的943個用戶對1682部電影的100000條評價記錄擴展到6040個用戶對3952部電影的1000209條評價記錄，各個算法所需的時間如表1所示。

表1 三種算法的時間比較

由表1可以看出，由于用戶和項目的數(shù)量發(fā)生變化，傳統(tǒng)的協(xié)同過濾算法需要重新計算用戶相似矩陣和項目相似矩陣，花費大量的時間，CF-User所需的時間幾乎是PMF算法的100倍，而CF-Item則是PMF算法的125倍，該實驗表明PMF在算法擴展性方面明顯優(yōu)于傳統(tǒng)的協(xié)同過濾算法。

4 結語

伴隨著信息大爆炸的背景，越來越多的研究者開始關注推薦算法，但是傳統(tǒng)的推薦算法依然存在著一些不足，如算法的可擴展性低、抗稀疏性差等問題，針對這些問題，本文提出了基于概率矩陣分解的推薦算法，在MovieLens數(shù)據(jù)集下，對提出的算法和傳統(tǒng)的協(xié)同過濾算法進行了對比分析。實驗表明，基于概率矩陣分解的推薦算法能夠有效的緩解這些問題，同時提高了推薦的準確度。但PMF算法包含了太多的人為經(jīng)驗參數(shù)，在以后的工作中，將考慮使用貝葉斯矩陣分解來研究推薦問題。

[1] ADOMAVICIUS.G,TUZHILIN.A.Toward the Next Generation of Recommender Systems:A Survey of the State-of-the-Art and Possible Extensions[J].IEEE Transactions on knowledge and Data Engineering,2005,17(17):734-749.

[2] 楊博,趙鵬飛.推薦算法綜述[J].山西大學學報(自然科學版),2011,34(3):337-350.

[3] 陳潔敏,湯庸,李建國,等.個性化推薦算法研究[J].華南師范大學學報(自然科學版),2014(5):8-15.

[4] 鄧愛林,左子葉,朱揚勇.基于項目聚類的協(xié)同過濾推薦算法[J].小型微型計算機系統(tǒng),2004,25(9):1665-1670.

[5] 李海霞.基于蟻群聚類的電子商務個性化推薦算法研究[D].山東:山東師范大學,2014.

[6] SARWAR BM,KARYPIS G,KONSTAN JA,et al.Application of dimensionality reduction in recommender system-A case study[C].ACM WebKDD 2000 Workshop,2000.

[7] 何佳知.基于內(nèi)容和協(xié)同過濾的混合算法在推薦系統(tǒng)中的應用研究[D].上海:東華大學,2016.

[8] BILLSUS D,PAZZANI MJ.Learning Collaborative Information Filters[C].ICML.1998,98:46-54.

[9] 李遠博,曹菡.基于PCA降維的協(xié)同過濾推薦算法[J].計算機技術與發(fā)展,2016(2):26-30.

[10] MNIH A,SALAKHUTDINOV R. Probabilistic matrix factorization[C].Advances in Neural Information Processing Systems.2007:1257-1264.

[11] 熊海濤.面向復雜數(shù)據(jù)的推薦分析研究[M].北京：北京理工大學出版社，2015.

[12] RESNICK P,IAKOVOU N,SUSHAK M,et al.GroupLens:An open Architecture for Collaborative Filtering of Netnews[C].Process of the 1994 Computer Supported Cooperative Work Conference,1994:175-186.

[13] BREESE JS,HECKERMAN D,KADIE C.Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C].Process of the 14th Coference on Uncertainty in Artificial Intelligence,1998:43-52.

[14] DUECK D,FREY B.Probabilistic sparse matrix factorization[J].University of Toronto,Toronto:Technical Report:PSI-2004-23,2004.

[15] RICCI F,ROKACHL,SHAPIRA B,et al.Recommender system hand-book[M].[S.l.]:Springer,2011.

[16] 張航,葉東毅.一種基于多正則化參數(shù)的矩陣分解推薦算法[J].計算機工程與應用,2017,53(3):74-79.

[責任編輯、校對：周 千]

A Recommendation Algorithm Based on Probabilistic Matrix Factorization

ZHANGBian

(College of Information Engineering,Lanzhou University of Finance and Economics,Lanzhou 730000,China)

In this paper,we propose a probabilistic matrix factorization recommendation algorithm based on stochastic gradient descent to solve the problem of poor scalability and data sparsity.This algorithm is to generate two random number matrices with Gaussian distribution,which are then continuously trained and updated to make their inner product close to user rating matrix.In order to avoid over-fitting the training data,the regularization constraint is applied,and the model is optimized through the batch process of stochastic gradient descent.Data from experiment on the MovieLens show that the proposed algorithm not only relieves the problem of poor scalability and data sparsity,but also improves the accuracy compared with the traditional collaborative filtering algorithm.

recommendation algorithm;collaborative filtering;probabilistic matrix factorization;stochastic gradient descent

2017-02-21

張昪(1994-)，女，山西臨汾人，碩士研究生，主要從事數(shù)據(jù)挖掘個性化理論與方法研究。

TP301.6

A

1008-9233(2017)03-0078-06