基于項目近鄰的約束概率矩陣分解算法

張天杰，曹蘇燕，閆世洋

(南京郵電大學 計算機學院，江蘇 南京 210003)

基于項目近鄰的約束概率矩陣分解算法

張天杰，曹蘇燕，閆世洋

(南京郵電大學 計算機學院，江蘇 南京 210003)

在個性化推薦領域，協同過濾是目前最為成功應用最為廣泛的推薦技術之一。約束概率矩陣分解算法便是一種基于模型的協同過濾算法，它能有效地面對推薦系統中遇到的海量數據問題，保證推薦的實時性。然而，傳統的約束概率矩陣分解算法并沒有考慮用戶或者項目之間的關系，使得算法的推薦質量受到影響。為進一步提高算法推薦的質量,文中在約束概率矩陣分解算法模型的基礎上引入項目近鄰關系,通過結合從項目簡介中提取的固有特征和用戶評定的標簽特征兩方面信息來確定項目的最近鄰居集合，并將該鄰居集合融合到基于約束的概率矩陣分解模型中產生推薦。通過在真實的數據集上的驗證結果表明，該算法能夠更有效地預測用戶對項目的評分，提高算法的推薦精度。

推薦系統；協同過濾；約束概率矩陣分解；項目近鄰

0 引 言

在推薦系統[1-3]領域，協同過濾推薦(Collaborative Filtering)以其推薦策略簡單、實用、適用對象多樣的特性而備受青睞。根據使用策略的不同，協同過濾可以分為基于內存的協同過濾(Memory based)和基于模型的協同過濾(Model based)[4]。基于內存的協同過濾主要包括基于用戶[5]和基于項目[6]兩類，兩者的重點分別為尋找相似的用戶和項目。然而，基于內存的協同過濾對于用戶項目評分矩陣的稀疏性比較敏感，并且隨著系統用戶、項目量的增大，計算量呈非線性增長趨勢，不利于實時性推薦。基于模型的協同過濾推薦通過采用線下學習、周期性更新的方式對評分數據進行挖掘。目前，常見的基于模型的協同過濾方法有聚類模型方法[7]、貝葉斯網絡[8]、矩陣分解[9]等。相比較基于內存的協同過濾算法，這類算法具有更好的擴展性,在面對海量數據時推薦更具實時性。約束概率矩陣分解算法[10](Constrained Probabilistic Matrix Factorization，CPMF)便是一種基于模型的協同過濾推薦的經典算法，其可以在線性時間內產生推薦,相比較了其他推薦策略能更有效地應對評分稀疏、海量數據等問題[10]。

然而，傳統的CPMF算法模型并未考慮用戶或者項目之間的關系，算法僅使用了用戶對項目的評分信息，忽略了很多額外的信息，從而影響了實際的推薦效果。近年來，學者們[11-13]從評分矩陣信息以外的信息中挖掘用戶或項目的關系并將其用于協同過濾算法中，從而實現對原有算法推薦效果的提升。

考慮到項目的關系往往比用戶的關系更具穩定性，不需要頻繁更新，對于大型系統更具優勢[6]，文中從項目角度出發，提出了一種基于項目近鄰的約束概率矩陣分解算法(Item-neighborhood-based Constrained Probabilistic Matrix Factorization，ICPMF)。在ICPMF中，結合從項目簡介中提取固有特征和用戶對項目評定的標簽特征兩方面信息來挖掘項目之間相互影響的關系，將其量化為項目之間的相似度，通過相似度的大小來確定項目的近鄰集合，并將該鄰居集合融合到CPMF中實現推薦。

1 CPMF算法概述

約束概率矩陣分解算法是由Salakhutdinov等[10]提出的一種基于模型的協同過濾推薦策略，是一種潛在特征因子分解算法。該算法假設每個用戶的興趣只受幾個潛在的特征影響，并假設這些特征向量符合均值為0的高斯先驗分布，通過用戶對項目的評分記錄來學習獲得每個用戶和項目的潛在特征向量，最后利用得到的低維度的潛在特征向量矩陣計算出用戶對項目的預測評分，進而產生推薦。CPMF能夠通過線下學習潛在特征，線上直接使用學習到的潛在特征向量計算出用戶對某個項目的預測評分，從而可以快速地為用戶產生要推薦的項目集合。實驗結果表明，CPMF在推薦準確性和抗稀疏性上和其他只使用用戶-項目評分矩陣的協同過濾算法比較更具優勢[10]。

(1)

其中，W∈RD×M為潛在相似約束矩陣，Wk為W的第k列；Y∈RD×N,Yi代表Y的第i列；I為指示函數，即如果用戶i對項目k有評分，則Iik為1，否則Iik為0，當用戶i沒有評分時Ui=Yi。

根據以上的定義，已觀察到的評分數據的條件概率定義如式(2)。

p(R|Y,V,W,σ2)=

(2)

其中，g(x)=1/(1+e-x)用于將預測評分區間映射到[0,1]上；Rij對應用戶i對項目j的評分數據，通過函數t(x)=(x-1)/(K-1)將其從1到K映射到[0,1]區間上；Yi、Wk、Vj先驗服從均值為0的高斯先驗分布且相互獨立，即如式(3)、(4)、(5)所示。

(3)

(4)

(5)

由貝葉斯推理可得，Y,V,W的后驗概率分布如式(6)所示。

(6)

將式(3)、(4)、(5)帶入式(6)，對上述的后驗概率取對數后并最大化后驗，化簡后等價于式(7)。

CPMF算法的圖模型[10]如圖1所示。

圖1 約束概率矩陣分解模型

2 ICPMF算法描述

結合前文對于CPMF算法的描述，文中提出的ICPMF算法共包括兩個過程：根據項目的簡介和標簽信息進行項目近鄰選擇；根據相似性假設將項目近鄰關系融入到CPMF算法中進行特征向量學習，得到用戶和項目的潛在特征向量。

ICPMF算法的兩個過程皆可由線下計算完成，并進行周期性更新。

2.1 項目近鄰的選擇

一般而言，項目簡介是系統為用戶介紹特定的項目內容而設，如圖書有圖書內容簡介、電影有劇情簡介等。項目簡介一般由一段簡短的文本描述，是對項目特征的一段客觀描述，通過項目簡介用戶可以了解項目的內容和它所具有的一些特征。所以作為為用戶導航的一種方式，項目簡介中往往蘊含了項目所具有的一些固有特性，即客觀特性。標簽則一般由使用過某個項目的用戶給出，是用來描述信息的關鍵詞，可以實現對信息的分類[14]，對于每一個項目而言標簽往往反映了用戶對其使用過項目的主觀感受，對于同樣的項目而言，不同的用戶可能會給出截然不同的標簽，所以系統在收集用戶為項目添加的標簽信息時往往會附帶標簽的數量，從而能夠更好地衡量標簽對項目的價值。

考慮到以上情況，為了更好地構建項目的特征，進而尋找到更加合理的項目近鄰關系，文中結合項目簡介和用戶對項目打的標簽兩方面數據對項目近鄰進行計算和選擇。具體的近鄰選擇過程包括：

(1)項目特征的選取和權重計算得到項目的特征向量；

(2)針對任一項目Itemj，根據特征向量計算其與系統中任一其他項目Iteml的項目間的相似度得到S(j,l)；

(3)選擇相似度最大的L個項目作為項目j的近鄰Nj。

具體步驟如下：

Step1：對項目j的簡介內容進行中文分詞(文中采用IKAnalyzer中文分詞器)，過濾停止詞和虛詞，并對剩余的詞進行詞頻統計。

Step2:以Step1統計出的詞作為項目的一組特征，并根據對應的詞頻，計算TF-IDF[15]值作為詞權重、計算項目標簽的TF-IDF值作為標簽的權重。TF-IDF計算公式如下：

(8)

Step4：計算項目j與任一其他項目l的余弦相似度得到S(j,l)，如式(9)所示，并選取和項目j相似度最大的L個項目集合作為項目j的近鄰Nj。

2.2 ICPMF算法模型

其中，Nj為項目j的鄰居集合；S(j,l)為項目j與項目l的相似度，即權重參數。

ICPMF算法的模型圖如圖2所示。

圖2 ICPMF算法模型

具體地，對于項目的潛在特征先驗概率可以表示為式(10)，與式(7)類似通過貝葉斯推理，后驗概率如式(11)所示，將式(2)、(3)、(4)、(10)帶入后，進行對數處理并且最大化，除去常數項后等價于最小化公式(12)。

(10)

(11)

3 實 驗

3.1 實驗數據

為了探究文中所提算法的推薦效果，從豆瓣讀書上抓取了真實的數據集作為實驗數據。該數據集共包含三部分：34 250個用戶對10 897本圖書所做出的評分信息共258 111條，其中評分區間為[1,5]的整數；用戶對圖書添加的標簽共23 084個，并附帶了每個標簽被用戶添加的次數；評分信息中每本圖書的簡介信息，圖書簡介信息平均在300字左右。

實驗中使用了開源的分詞工具IK Analyzer 2012對圖書簡介信息進行分詞并進行停止詞過濾。實驗采用10折交叉實驗的方式，將總數據集分成10份，每次取1份作為測試集，剩余作為訓練集，迭代10次后，取10次評價標準的平均值作為算法最終的評測結果。

3.2 評價標準

3.3 實驗結果及分析

實驗共包括兩部分：(1)比較CPMF、TCPMF、ICPMF算法在不同的特征向量維度D下的推薦準確度情況，其中TCPMF為只使用標簽信息計算項目近鄰的ICPMF算法，ICPMF則融合了項目簡介和標簽兩方面信息進行項目近鄰計算。(2)測試參數λS對于ICPMF的影響。實驗中設定所使用到的參數λY=λV=λW=0.001。

圖3為三種算法在不同的特征維度D下的推薦準確度情況，其中TCPMF和ICPMF的項目近鄰個數L=25，參數λS=5。

圖3 不同特征向量維度D下各算法結果比較

由圖3可知，融入了項目近鄰信息的ICPMF和TCPMF的推薦準確度明顯好于CPMF，ICPMF好于TCPMF，這說明文中將項目近鄰關系融入CPMF算法進行推薦的有效性，同時也表明在項目近鄰計算時融合從項目簡介中提取固有特征和標簽特征這兩方面信息進行項目近鄰計算的合理性。

圖4比較了不同的λS取值對ICPMF算法的影響，實驗中將λS的值分別設為0.1，0.5，1，5，10，25，并設用戶近鄰個數L=25，特征向量維度D=10。

圖4 λS對ICPMF的影響

由圖4可知，λS對ICPMF的推薦準確度產生了較明顯的影響，當λS在[0.1,5]上變化時，ICPMF的推薦準確率隨著λS的增大而提高，當λS大于5時算法的準確率隨之下降，由此可知項目近鄰的引入對改進CPMF算法的有效性。

4 結束語

文中通過結合項目簡介和用戶為項目添加的標簽兩方面信息來挖掘系統中項目的近鄰關系，并將該近鄰關系融入CPMF算法中進行評分預測。在真實的數據集上的實驗結果表明，提出的方法和傳統的CPMF算法相比能夠有效地提高推薦算法評分預測的準確度，進而驗證了文中項目近鄰關系計算方法的合理性和將此近鄰關系融入CPMF算法的有效性。然而，實驗中也發現，訓練過程中存在特征向量初始值設置問題以及如何防止模型過擬合問題，這些值得進一步研究。

[1]RicciF,RokachL,ShapiraB.Introductiontorecommendersystemshandbook[M].US:Springer,2011.

[2] 王國霞,劉賀平.個性化推薦系統綜述[J].計算機工程與應用,2012,48(7):66-76.

[3] 任 磊.推薦系統關鍵技術研究[D].上海:華東師范大學,2012.

[4] 劉士琛.面向推薦系統的關鍵問題研究及應用[D].合肥:中國科學技術大學,2014.

[5]AdomaviciusG,TuzhilinA.Towardthenextgenerationofrecommendersystems:asurveyofthestate-of-the-artandpossibleextensions[J].IEEETransactionsonKnowledgeandDataEngineering,2005,17(6):734-749.

[6]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Proceedingsofthe10thinternationalconferenceonworldwideweb.[s.l.]:ACM,2001:285-295.

[7]O’ConnorM,HerlockerJ.Clusteringitemsforcollaborativefiltering[C]//ProceedingsoftheACMSIGIRworkshoponrecommendersystems.UCBerkeley:ACM,1999.

[8]MiyaharaK,PazzaniMJ.CollaborativefilteringwiththesimpleBayesianclassifier[M]//PRICAI2000topicsinartificialintelligence.Berlin:Springer,2000:679-689.

[9]GoldbergK,RoederT,GuptaD,etal.Eigentaste:aconstanttimecollaborativefilteringalgorithm[J].InformationRetrieval,2001,4(2):133-151.

[10]MnihA,SalakhutdinovR.Probabilisticmatrixfactorization[C]//Procofadvancesinneuralinformationprocessingsystems.[s.l.]:[s.n.],2007:1257-1264.

[11]MaH,YangH,LyuMR,etal.SoRec:socialrecommendationusingprobabilisticmatrixfactorization[C]//Procofinternationalconferenceoninformation&knowledgemanagement.[s.l.]:ACM,2008:931-940.

[12] 孫光福,吳 樂,劉 淇,等.基于時序行為的協同過濾推薦算法[J].軟件學報,2013,24(11):2721-2733.

[13]Tso-SutterKHL,MarinhoLB,Schmidt-ThiemeL.Tag-awarerecommendersystemsbyfusionofcollaborativefilteringalgorithms[C]//Proceedingsofthe2008ACMsymposiumonappliedcomputing.[s.l.]:ACM,2008:1995-1999.

[14]DuWH,RauJW,HuangJW,etal.Improvingthequalityoftagsusingstatetransitiononprogressiveimagesearchandrecommendationsystem[C]//ProcofIEEEinternationalconferenceonsystems,man,andcybernetics.[s.l.]:IEEE,2012:3233-3238.

[15]JoachimsT.AprobabilisticanalysisoftheRocchioalgorithmwithTFIDFfortextcategorization[R].USA:Carnegie-MellonUniversity,1996.

[16]SaltonG,WongA,YangCS.Avectorspacemodelforautomaticindexing[M].[s.l.]:MorganKaufmannPublishersInc.,1997.

A Constrained Probabilistic Matrix Factorization AlgorithmBased on Item-neighborhood

ZHANG Tian-jie，CAO Su-yan,YAN Shi-yang

(College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Collaborative filtering is one of the most successful applications in the field of personalized recommendation.Constrained probabilistic matrix factorization is a model-based collaborative filtering algorithm which can effectively deal with the problem of scalability in large-scale recommendation system and guarantee the real-time of recommendation.However,the traditional one does not consider the relationship between the users or the items,which makes the quality of the algorithm affected.It takes the relationship of item-neighborhood into the algorithm model of constrained probability matrix factorization to improve the quality of the proposed algorithm.To guarantee the accuracy of item-neighborhood,the inherent features extracted from the item’s summary and the tag of user marked for the item are used to get the set of the nearest neighbor for the items,then the item-neighborhood set is applied into the framework of the constrained probabilistic matrix factorization algorithm.The experiments on real datasets show that the proposed algorithm can predict the user’s rating on the item more effectively,and improve the accuracy of the recommendation.

recommendation system;collaborative filtering;constrained probabilistic matrix factorization;item-neighborhood

2016-01-10

2016-04-13

時間：2016-09-19

國家“863”高技術發展計劃項目(2006AA01Z201)

張天杰(1992-)，男，碩士研究生,研究方向為數據挖掘、大數據、云計算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0842.054.html

TP311

A

1673-629X(2016)10-0064-05

10.3969/j.issn.1673-629X.2016.10.014