潘拓宇,朱珍民,滕吉,葉劍,曾慶峰
(1中國科學(xué)院計算技術(shù)研究所,北京100190;2湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105)
網(wǎng)絡(luò)的快速發(fā)展帶來了信息量的指數(shù)級增長,如何從這些海量的信息中抽取出用戶感興趣的內(nèi)容變得意義重大,這就是當(dāng)前眾多大型網(wǎng)站,數(shù)字圖書館等廣泛研究的個性化服務(wù)推薦技術(shù)。個性化服務(wù)推薦技術(shù)主要分為基于內(nèi)容過濾,基于協(xié)同過濾,以及混合過濾三種類型。目前應(yīng)用較為成功的是基于協(xié)同過濾的個性化信息推薦技術(shù)[1-2]。
本文對服務(wù)本身進行描述,并對其內(nèi)容進行過濾抽象出服務(wù)主題和特定主體。以此對整個服務(wù)項目集合進行服務(wù)子類的劃分,通過建立用戶興趣概率模型,來計算出要推薦的服務(wù)子類集合,然后再對每個推薦服務(wù)子類中特定的項目和用戶進行項目協(xié)同過濾,從而得到某個用戶的推薦項目集合結(jié)果。
本文第二節(jié)介紹個性化推薦系統(tǒng)的相關(guān)工作和已有進展。第三節(jié)描述該本體模型下的推薦過程,包括用戶子類的興趣概率計算和在服務(wù)子類中具體項目推薦計算。第四節(jié)為模型實現(xiàn)和實驗結(jié)果分析。最后一節(jié)對全文總結(jié)和將來工作進行展望。
基于協(xié)同過濾技術(shù)由于推薦精度較高且與服務(wù)資源的無關(guān)性,使得它成為近些年來個性化服務(wù)技術(shù)的主流,比較典型的方法包括:文獻[3]提出使用基于項目的協(xié)同過濾代替基于用戶的協(xié)同過濾,它首先計算項目之間的相關(guān)性,然后通過用戶對相關(guān)項目的評分預(yù)測用戶對未評分項目的評分。實驗證明了前者在計算性能和推薦的品質(zhì)上明顯高于后者,在后續(xù)的工作中作者又進一步擴展該方法[4]。文獻[5]提出一種結(jié)合項目訪問概率和協(xié)同過濾的方法,解決了普通協(xié)同過濾中的新用戶加入無法有效推薦問題。文獻[6]提出一種利用聯(lián)合式檢索框架(associative retrieval framework)和相關(guān)傳播激活算法(related sp reading activation)從他們過去一些行為和反饋中提取傳遞聯(lián)合體(transitive associations),有效解決了用戶評分矩陣稀疏性問題。單純的基于某種協(xié)同過濾的技術(shù)在實踐過程中容易遇到兩個很難解決的問題,一個是稀疏性,也就是指在系統(tǒng)使用初期,由于系統(tǒng)資源還未獲得足夠多的評價,該方法很難利用這些評價來發(fā)現(xiàn)相似的用戶。另一個是可擴展性,也就是指隨著系統(tǒng)用戶和資源的增多,該方法的性能會越來越低。對于這些問題,雖然最近人們通過聚類,矩陣劃分,粗糙集,模糊集,貝葉斯網(wǎng)絡(luò),修正相似度公式[7-11]等方法改進但始終未從根本上解決上述問題。
另一方面在特定領(lǐng)域資源模型表達較好的情況下,人們更加傾向使用簡單快速的內(nèi)容過濾技術(shù)。但它往往使用向量模型精確表達用戶興趣,使得用戶和資源項目的相似度計算精度大大降低,雖然可以通過概率模型和模糊集加強相似計算的精度,但與協(xié)同過濾模型相比在沒有很好的預(yù)處理下,內(nèi)容過濾推薦精度要遠遠低于協(xié)同過濾技術(shù)。Bayesian網(wǎng)絡(luò)技術(shù)利用訓(xùn)練集創(chuàng)建相應(yīng)的模型,模型用決策樹表示,節(jié)點和邊表示用戶或者項目信息。訓(xùn)練得到的模型非常小,所以對模型的應(yīng)用非???。這種方法適合于用戶的興趣愛好變化比較慢的場合。內(nèi)容過濾方法最大的缺點就是每個用戶或者項目都只能被分到一個類中。當(dāng)類的粒度較大時,在同一個類下項目或用戶不能具體區(qū)分,而當(dāng)類較小的時候,可能會出現(xiàn)有多個子類符合同個項目或用戶的分配。
混合過濾是為了消除各種技術(shù)的缺點,利用它們各自優(yōu)點來達到一個較好的推薦效果。文獻[12]提出了基于內(nèi)容的協(xié)作過濾方法,也就是利用用戶瀏覽過的資源內(nèi)容來預(yù)期用戶對其他資源的評價,這樣可以增加資源評價的密度,并利用這些評價再進行協(xié)作過濾,從而提高協(xié)作過濾的性能。文獻[13]通過不同用戶對同一項目,同一用戶對不同項目以及其他用戶對相似項目三方面的預(yù)測融合,結(jié)合項目協(xié)同過濾和用戶分類衰退,并利用這些評價再進行協(xié)作過濾,從而提高協(xié)作過濾的性能。文獻[14]提出了一種混合項目和用戶兩方面的評分預(yù)測算法,改善協(xié)同過濾方法的數(shù)據(jù)稀疏性。文獻[15]提出了先進行協(xié)作過濾,然后對中間結(jié)果再做內(nèi)容過濾的評分預(yù)測,有效改善內(nèi)容過濾中不能發(fā)現(xiàn)新的其他用戶未訪問過的可能感興趣的內(nèi)容。
基于內(nèi)容過濾的技術(shù)優(yōu)點是簡單、有效,缺點是矢量模型計算精度較低,難以區(qū)分資源內(nèi)容的品質(zhì)和風(fēng)格,而且不能為用戶發(fā)現(xiàn)新的感興趣的資源,只能發(fā)現(xiàn)與用戶已有興趣相似的資源?;趨f(xié)作過濾的技術(shù)其優(yōu)點是能為用戶發(fā)現(xiàn)新的感興趣的資源,并且能夠為一些非結(jié)構(gòu)化對象進行推薦比如電影,歌曲等,但是有兩個很難解決的缺點,一個是稀疏性,即在系統(tǒng)使用初期,由于系統(tǒng)資源還未獲得足夠多的評價,系統(tǒng)很難利用這些評價來發(fā)現(xiàn)相似用戶。另一個是系統(tǒng)的可擴展性,即隨著系統(tǒng)資源和用戶數(shù)量增加,系統(tǒng)的性能會越來越低。
為了克服普通內(nèi)容過濾方法中矢量模型計算精度較低,改善協(xié)同過濾中用戶評分?jǐn)?shù)據(jù)的極端稀疏性,本文提出了一個基于內(nèi)容過濾和項目協(xié)同過濾的混合個性化服務(wù)推薦子模型。該模型對服務(wù)本身進行描述,并對整個服務(wù)項目集合進行以概率模型為基礎(chǔ)的服務(wù)子類層次結(jié)構(gòu)劃分。通過先前的用戶訓(xùn)練和使用時的數(shù)據(jù)統(tǒng)計,來計算出要推薦的服務(wù)子類集合,然后再對每個推薦服務(wù)子類中特定的項目和用戶進行項目協(xié)同過濾,從而得到某個用戶的推薦項目集合結(jié)果。仿真實驗結(jié)果表明,該子模型具有較高服務(wù)推薦的準(zhǔn)確率和召回率。
本服務(wù)推薦模型框架分為三個部分,按服務(wù)提供流程分為:服務(wù)內(nèi)容預(yù)處理部分,內(nèi)容過濾部分和協(xié)同過濾部分。我們通過服務(wù)子類本體,對整個項目集合進行服務(wù)子類的劃分,為后續(xù)統(tǒng)計每個用戶興趣分布提供模板。當(dāng)用戶注冊登入后,根據(jù)一個時間窗內(nèi)(如兩個星期)的歷史訪問信息的統(tǒng)計,計算出新的興趣分布,然后以此為基礎(chǔ)對新的可能感興趣子類進行特定范圍內(nèi)的基于項目的協(xié)同過濾計算得到具體推薦服務(wù)項目返回給用戶,從而完成推薦過程,如圖1。
圖1 服務(wù)推薦模型框架
通過服務(wù)內(nèi)容預(yù)處理,我們得到以服務(wù)子類屬性為節(jié)點的服務(wù)層次結(jié)構(gòu)圖,如圖2。其中Si,F j,Ck,Al分別對應(yīng)著服務(wù)類型,服務(wù)領(lǐng)域,服務(wù)主題,特定主體。路徑SiFjCkAl則對應(yīng)著一特定服務(wù)子類。
假定每段路徑表示為某服務(wù)子類屬性層次結(jié)構(gòu)下起點到終點的興趣概率,那么每個服務(wù)子類的興趣概率為:
設(shè)不同服務(wù)子類屬性粒度的集合為X,Y
圖2 服務(wù)子類屬性本體層次結(jié)構(gòu)
在具體應(yīng)用中,我們使用專家經(jīng)驗值或用戶使用項目的頻率Freq(一般是后者)來代替(1)式中每段部分路徑興趣概率P:
在沒有專家經(jīng)驗值和用戶使用項目的頻率(或者是使用次數(shù)λ達不到某一啟動閥值α,即用戶是偶爾使用該服務(wù)子類中的項目,不考慮為用戶的真正興趣)的情況下,我們用剩余興趣量(即該服務(wù)子類屬性粒度層下,總頻率減去其他已有使用項目的頻率)乘上一個估計因子 μ(在本模型中用該服務(wù)粒度下已有興趣量的最大值,即猜想在剩余興趣量中,沒有比已有興趣比值更大的剩余興趣分量,顯然比傳統(tǒng)的1/n更接近真實興趣,因為針對同一個領(lǐng)域或主題,用戶的興趣量很少是均勻的),即:
例1:假設(shè)圖2中實線路徑為系統(tǒng)對某個(或某類)用戶的項目服務(wù)使用頻率進行學(xué)習(xí)和統(tǒng)計后,得到的k(這里設(shè)定k=3)個先前最感興趣(即使用頻率最高)的服務(wù)子類S1 F2 C3 A4,S2 F2 C3 A4,S3F5C6A7。根據(jù)公式(1),(2)我們可得:p1=0.242 2,p2=0.061 8,p3=0.201 1。那么除了這k個可直接推薦的服務(wù)子類外,與此類似我們還應(yīng)該計算出其他相關(guān)子類。如圖2中虛線路徑為三種典型代表。利用公式(1),(2),(3)可得路徑S2 F 4 C3 A4,S2F5C7A8,S3F2C3A4的p4=0.035 9,p5=0.036 3,p6=0.019 9。最后根據(jù)興趣概率 P值大小對所有結(jié)果選取前m個推薦服務(wù)子類。
在選擇m個服務(wù)子類后,根據(jù)每個子類的興趣概率在m子類中的比重依次確定各子類的具體推薦項目數(shù)量。
圖3 某子類中的項目—用戶評分矩陣及其項目之間相似關(guān)系
求出未訪問過的其他項目的估計評分,Fu,j是第u個用戶對第j個項目的預(yù)測評分。最后根據(jù)下式
即在有預(yù)測評分情況下,選擇評分最高的前t個項目;在沒有預(yù)測評分但有其他用戶評分的情況下,選擇最熱點(訪問次數(shù)最多)的前t個項目;否則隨機選取時間最新t個項目,推薦給用戶。
實驗分為兩個部分,實驗一與實驗二為第一部分,實驗三為第二部分。在第一部分中實現(xiàn)并驗證以本文提出的理論模型為基礎(chǔ)的個性化混合Web服務(wù)推薦平臺。在第二部分中是用衡量推薦方法質(zhì)量中比較常用的M ovieLens數(shù)據(jù)集驗證OHR方法的推薦質(zhì)量,并與傳統(tǒng)協(xié)同過濾方法進行對比分析。
在第一部分中,沒有采用用戶手動評分(因大多數(shù)用戶不會或不愿主動參與評分),而是采取了用戶訪問過某項目,則認為他對該項目的評分是1否則為0.2的策略,評分高低的設(shè)定(有一定梯度)不影響推薦方法本身。在第二部分中,我們利用標(biāo)準(zhǔn)數(shù)據(jù)集,用訓(xùn)練集來推薦用戶未訪問過的項目,用測試集來驗證此方法的可靠性以及發(fā)現(xiàn)新興趣的能力。
采用信息檢索領(lǐng)域廣泛使用的準(zhǔn)確率(p recision)和召回率(recall)來評價實驗結(jié)果。本實驗準(zhǔn)確率和召回率的定義如下:
據(jù)實驗統(tǒng)計,實驗數(shù)據(jù)集共有4種服務(wù)類型覆蓋13個服務(wù)領(lǐng)域,63個主題和537個特定本體,共4 098個具體項目。它們分別來自各大門戶網(wǎng)站的新聞信息,中國農(nóng)業(yè)信息網(wǎng)的政策與科技信息,商務(wù)平臺中用戶自己發(fā)布的交易信息等。
【實驗1】 隨機選取6組用戶,每次隨機抽取40個用戶分別使用傳統(tǒng)基于項目協(xié)同過濾(IBCF),傳統(tǒng)基于用戶協(xié)同過濾(UBCF)和本文提出的基于本體的混合推薦方法(簡稱OHR)推薦10個頁面并計算出其相應(yīng)推薦的平均準(zhǔn)確率(實驗結(jié)果見圖4)。
圖4 OHR方法與傳統(tǒng)協(xié)同過濾方法的準(zhǔn)確率比較
如圖4所示,OHR方法在推薦服務(wù)子類范圍較小(k=3,m=6)的情況下,平均推薦精度比傳統(tǒng)基于項目過濾方法要提高了5%~8%。在推薦服務(wù)子類范圍擴大,推薦項目數(shù)量較少的情況下,推薦精度會略有下降(實驗結(jié)果見圖5)。
圖5 OHR方法與傳統(tǒng)協(xié)同過濾方法的召回率比較
【實驗2】 隨機選取上述全體用戶的某次會話。據(jù)統(tǒng)計,大多數(shù)用戶訪問服務(wù)子類的數(shù)量在8~25個之間,用戶的平均訪問項目為63個,在此基礎(chǔ)上我們分別計算出4種方法在推薦項目數(shù)為10,20,30,40,50的召回率。
如圖5所示,本文提出的方法在推薦服務(wù)子類范圍較大(k=5,m=10)的情況下,隨著推薦項目的增多其召回率的大小和上升速度明顯高于傳統(tǒng)協(xié)同過濾方法。
通過實驗我們得知隨著k和m值增加,推薦服務(wù)子類范圍隨之增大,推薦服務(wù)的召回率(recall)越高,但推薦服務(wù)的準(zhǔn)確率(precision)會有所越低。反之,雖然推薦服務(wù)的準(zhǔn)確率會很高,但是由于過濾掉了很多非主要興趣的服務(wù)子類,使得推薦服務(wù)的召回率(recall)會有所降低。
【實驗3】 我們使用目前在衡量推薦方法質(zhì)量中比較常用的 M ovieLens數(shù)據(jù)集(http://movielens.umn.edu)對本文提出的方法與傳統(tǒng)協(xié)同過濾方法再次進行比較驗證。這個數(shù)據(jù)集由美國M innesota大學(xué)的GroupLens研究小組創(chuàng)建并維護,它包括943個用戶對1 682部電影的100 000個評分(評分值 1~5,5表示“perfect”,而“1”表示“bad”)記錄,每個用戶至少評價了20部電影,并已經(jīng)以80%訓(xùn)練集,20%測試集的劃分比例生成了7組實驗集,其中ua,ub組中的測試集中每個用戶評分?jǐn)?shù)量被標(biāo)準(zhǔn)化為10個。
在TopN的推薦結(jié)果評價中,既要考慮命中數(shù)量問題(命中數(shù)量越多越好)又要考慮推薦精度問題(推薦精度的評估標(biāo)準(zhǔn)一般采用平均絕對偏差MAE(m ean absolute error),通過計算預(yù)測用戶的評分與用戶的實際評分之間的偏差來度量預(yù)測的準(zhǔn)確性,MAE越小意味著推薦的精度越高),為了權(quán)衡兩者,本文建議提出一種新的評價TopN推薦結(jié)果的綜合標(biāo)準(zhǔn):每命中項目 M AE影響值M PH(MAE per hit)。即每推薦一個命中項目所帶來的平均絕對偏差代價。同MAE相似,MPH值越小,意味著每推薦一個命中項目所帶來的平均絕對偏差代價越小,TopN的推薦質(zhì)量越高。
對M ovieLens該數(shù)據(jù)集中的7個數(shù)據(jù)組,分別計算出 OHR4(k=m=4),OHR6(k=m=6),OHR8(k=m=8),IBCF Top10,Top15,Top20的NH,MAE,MPH值(如表1所示)。
從上表數(shù)據(jù)分析,可得到在推薦Top10的所有實驗中,雖然OHR4,OH R6,OH R8比同條件下IBCF方法的平均MAE值分別要高3%,6%,8%,但平均推薦項目命中數(shù)量(NH)卻分別提高了13%,23%,22%(如圖6所示,Uavg為各組實驗MPH的平均值)尤其是在標(biāo)準(zhǔn)Top10實驗(即測試集中每個用戶評分?jǐn)?shù)量被標(biāo)準(zhǔn)化為 10個)ua,ub組中OHR方法的優(yōu)勢更加明顯。在Top15,Top20的實驗中,OH R對IBCF方法的綜合推薦質(zhì)量優(yōu)勢逐漸減小。這是因為隨著推薦項目數(shù)量的增多,次要興趣的項目也逐漸增多的緣故,導(dǎo)致了綜合推薦質(zhì)量相對優(yōu)勢有所下降。在實際應(yīng)用中,由于應(yīng)用系統(tǒng)本身信息表現(xiàn)空間有限,用戶的最感興趣信息集中,推薦數(shù)量一般不超過十個,綜合考慮OH R方法推薦質(zhì)量明顯好于傳統(tǒng)方法。
表1 OHR方法與基于項目協(xié)同過濾方法在推薦TOP-10,15,20的NH,MAE,MPH
圖6 OHR方法與基于項目協(xié)同過濾方法在TOP-10的MPH比較
個性化服務(wù)推薦目前被廣泛地應(yīng)用于電子商務(wù),Web檢索,數(shù)字圖書館等各個領(lǐng)域,而現(xiàn)有的推薦方法存在著許多不足。本文提出的基于本體的個性化混合服務(wù)推薦模型(OHR),能夠簡潔高效地表達服務(wù)的核心內(nèi)容,方便自然的描述用戶興趣的分布變化,以及較準(zhǔn)確和廣泛的向用戶提供服務(wù)。實驗結(jié)果表明本模型在服務(wù)推薦上具有較高的準(zhǔn)確率和發(fā)現(xiàn)用戶新興趣的能力,但如何通過收集更多的上下文信息更加精確地描述用戶興趣仍是一個困難的問題,而怎樣實現(xiàn)不同服務(wù)主元的跨類型領(lǐng)域的服務(wù)推薦則是我們進一步要研究的重點。
[1] 許海玲,吳瀟,李曉東,閻保平.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報,2009,20(2):350-362.
[2] Gediminas Adomavicius,A lexander Tuzhilin,Tow ard the NextGeneration of Recommender Systems:A Survey of the State-of-the-A rt and Possib le Extensions[C]//IEEE T ransactions on Know ledge and Data Engineering,2005,17(6):734-749.
[3] B.Sarwar,G.Karypis,J.Konstan,and J.Ried l,I-tem-Based Collaborative Filtering Recommendation A lgorithms[C]//Proc.10th Int'lWWW Conf.,2001.
[4] M ukund Ddeshpande,George Karypis,Item-Based Top-N Recommendation A lgorithms[J].ACM Transactions on Information Systems,2004,22(1):143-177.
[5] K.Yu,A.Schwaighofer,V.Tresp,X.Xu,and H.-P.K riegel,Probabilistic Memory-Based Collaborative Filtering[J].IEEE Trans.Know ledgeand Data Eng.,2004,16(1):56-69.
[6] Z.H uang,H.Chen,and D.Zeng,App lying Associative Retrieval Techniques to A lleviate the Sparsity Prob lem in Collaborative Filtering[J].ACM T rans.Information System s,2004,22(1):116-142.
[7] 王明文,陶紅亮,熊小勇.雙向聚類迭代的協(xié)同過濾推薦算法[J].中文信息學(xué)報,2008,22(4):61-65.
[8] 宗勝,姜麗紅.推薦系統(tǒng)中遺漏值解決方法的研究[J].計算機應(yīng)用與軟件,2008,(6)
[9] 戴亞娥,龔松杰.個性化服務(wù)中基于模糊聚類的協(xié)同過濾推薦[J].計算機工程與科學(xué),2009,(4)
[10] 羅喜軍,王韜丞,杜小勇,劉紅巖,何軍.基于類別的推薦-種解決協(xié)同推薦中冷啟動問題的方法.計算機研究與發(fā)展,2007,z3.
[11] 歐潔.基于貝葉斯網(wǎng)絡(luò)模型的用戶興趣聯(lián)合推送[J].計算機科學(xué)2003,30(12):73-77.
[12] Balabanovic,M.,Shoham,Y.Fab:content-based,co llaborative recommendation[J].Communications of the ACM,1997,40(3):66-72.
[13] Jun Wang,A rjen P.de V ries,Marcel J.T.Reinders,Unifying User-based and Item-based Co llaborative Filtering App roaches by Sim ilarity Fusion[C]//Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval Pages:501-508.
[14] Rong Hu,Yansheng Lu,A Hybrid User and Item-Based Co llaborative Filtering w ith Smoothing on Sparse Data[C]//16th International Conference on A rtificial Reality and Telexistence——Workshops(ICAT'06),2006:184-189.
[15] James Sa lter,N ick Antonopou los,CinemaSc reen Recommender Agent:Combining Collaborative and Content-Based Filtering[C]//IEEE Intelligent Systems,2006,21(1):35-41.