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

張?zhí)旖埽芴K燕，閆世洋

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

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

張?zhí)旖埽芴K燕，閆世洋

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

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

推薦系統(tǒng)；協(xié)同過濾；約束概率矩陣分解；項目近鄰

0 引 言

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

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

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

1 CPMF算法概述

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

(1)

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

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

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

(2)

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

(3)

(4)

(5)

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

(6)

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

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

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

2 ICPMF算法描述

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

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

2.1 項目近鄰的選擇

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

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

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

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

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

具體步驟如下：

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

Step2:以Step1統(tǒng)計出的詞作為項目的一組特征，并根據(jù)對應(yīng)的詞頻，計算TF-IDF[15]值作為詞權(quán)重、計算項目標簽的TF-IDF值作為標簽的權(quán)重。TF-IDF計算公式如下：

(8)

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

2.2 ICPMF算法模型

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

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

圖2 ICPMF算法模型

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

(10)

(11)

3 實 驗

3.1 實驗數(shù)據(jù)

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

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

3.2 評價標準

3.3 實驗結(jié)果及分析

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

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

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

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

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

圖4 λS對ICPMF的影響

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

4 結(jié)束語

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

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

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

[3] 任 磊.推薦系統(tǒng)關(guān)鍵技術(shù)研究[D].上海:華東師范大學(xué),2012.

[4] 劉士琛.面向推薦系統(tǒng)的關(guān)鍵問題研究及應(yīng)用[D].合肥:中國科學(xué)技術(shù)大學(xué),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] 孫光福,吳 樂,劉 淇,等.基于時序行為的協(xié)同過濾推薦算法[J].軟件學(xué)報,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”高技術(shù)發(fā)展計劃項目(2006AA01Z201)

張?zhí)旖?1992-)，男，碩士研究生,研究方向為數(shù)據(jù)挖掘、大數(shù)據(jù)、云計算。

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