基于項(xiàng)目近鄰的約束概率矩陣分解算法

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

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

基于項(xiàng)目近鄰的約束概率矩陣分解算法

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

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

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

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

0 引 言

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

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

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

1 CPMF算法概述

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

(1)

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

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

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

(2)

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

(3)

(4)

(5)

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

(6)

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

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

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

2 ICPMF算法描述

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

ICPMF算法的兩個(gè)過程皆可由線下計(jì)算完成，并進(jìn)行周期性更新。

2.1 項(xiàng)目近鄰的選擇

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

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

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

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

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

具體步驟如下：

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

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

(8)

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

2.2 ICPMF算法模型

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

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

圖2 ICPMF算法模型

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

(10)

(11)

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

3.2 評價(jià)標(biāo)準(zhǔn)

3.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

圖4 λS對ICPMF的影響

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

4 結(jié)束語

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

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

[2] 王國霞,劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(jì)算機(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] 孫光福,吳 樂,劉 淇,等.基于時(shí)序行為的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào),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

時(shí)間：2016-09-19

國家“863”高技術(shù)發(fā)展計(jì)劃項(xiàng)目(2006AA01Z201)

張?zhí)旖?1992-)，男，碩士研究生,研究方向?yàn)閿?shù)據(jù)挖掘、大數(shù)據(jù)、云計(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