胡 文，景玉海

(哈爾濱商業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，哈爾濱 150028)

現(xiàn)今信息爆炸式的增長(zhǎng)，宣告著人們正處于一個(gè)無法從浩瀚信息海洋中高效篩選出自己所需信息的”信息超載”[1]時(shí)代.面臨該亟需解決的問題，推薦系統(tǒng)[2]這一無需用戶詳細(xì)描述需求信息，而是依據(jù)其歷史日常行為和數(shù)據(jù)，構(gòu)建相應(yīng)模型去挖掘用戶需求和興趣工具應(yīng)運(yùn)而生，大量推薦算法[3]被設(shè)計(jì)出來.

其中融合其他信息源，使得相似度計(jì)算準(zhǔn)確率提高的變體協(xié)同過濾(CF)[4]算法思想更加普遍.Huang L等人[5]通過統(tǒng)一利用社會(huì)、順序、時(shí)間和空間模式來表征用戶的登記行為，將CPS系統(tǒng)中的異構(gòu)流數(shù)據(jù)融入多模貝葉斯嵌入模型，來共同為用戶決策推薦.Ren等人[6]將興趣，地理，社會(huì)和分類相關(guān)性分?jǐn)?shù)整合到推薦算法的概率矩陣分解模型PMF中，利用聯(lián)合后的分?jǐn)?shù)進(jìn)行推薦.Ye等人[7]利用個(gè)人偏好、好友關(guān)系和興趣點(diǎn)距離三方面因素，聯(lián)合User-based CF(基于用戶協(xié)同過濾)算法、建立在好友關(guān)系之上的協(xié)同過濾和應(yīng)用地理位置信息的推薦方法提出混合CF(協(xié)同過濾)算法，讓推薦精度有所提高.王嘯巖等人[8]提出SoGeoCom融合推薦模型，該模型將用戶社交關(guān)系數(shù)據(jù)、地理位置數(shù)據(jù)和興趣點(diǎn)的評(píng)論信息這3個(gè)因素融合后進(jìn)行興趣點(diǎn)推薦.Hu等人[9]在進(jìn)行推薦時(shí)應(yīng)用了STT(Spatio-Temporal Topic)模型，將用戶的概況與簽到的時(shí)空主題相結(jié)合來提高推薦精度.

大體來講，以上推薦算法在數(shù)據(jù)稀疏性緩解上取得了一定的成效，讓推薦質(zhì)量進(jìn)一步提升，但也有一些不足：1)大多數(shù)算法都應(yīng)用的是基于用戶(User-Based CF)算法，時(shí)效性較強(qiáng)，但個(gè)性化不太明顯，存在冷啟動(dòng)問題.2)在計(jì)算項(xiàng)目或用戶相似度時(shí)僅使用用戶簽到的共同評(píng)分項(xiàng)，但由于用戶-興趣點(diǎn)簽到矩陣具有高度稀疏性，則會(huì)使推薦結(jié)果不準(zhǔn)確.3)訓(xùn)練模型花費(fèi)較長(zhǎng)的時(shí)間，模型計(jì)算復(fù)雜度較高.

為有效解決以上推薦時(shí)出現(xiàn)的問題及研究中包含的不完善之處，設(shè)計(jì)了一種基于KL散度和JS散度所求相似度融合的推薦算法，其基本內(nèi)容為：首先將每個(gè)項(xiàng)目相關(guān)的評(píng)論文本信息進(jìn)行主題建模計(jì)算項(xiàng)目間隱性相似度，再利用所有用戶對(duì)每個(gè)項(xiàng)目的評(píng)分進(jìn)行顯性相似度度量，兩者融合，最后在推薦生成階段，將融合后的相似度加入到基于項(xiàng)目的協(xié)同過濾中，來生成得分最高的前N個(gè)項(xiàng)目進(jìn)行推薦，讓推薦系統(tǒng)中的冷啟動(dòng)問題得到緩解，在解決數(shù)據(jù)稀疏性問題方面也取得了較好的功效，降低了生成推薦時(shí)計(jì)算的復(fù)雜性，提高了推薦的質(zhì)量.

1 相關(guān)工作

1.1 基于項(xiàng)目的協(xié)同過濾

基于協(xié)同過濾的推薦，即從用戶歷史簽到記錄角度進(jìn)行推薦，可進(jìn)一步分為基于內(nèi)存的推薦和基于模型的推薦，基于內(nèi)存的推薦就是傳統(tǒng)的User-Based CF和Item-Based CF[10].User-Based CF時(shí)效性較強(qiáng)，Item-Based CF個(gè)性化較強(qiáng).另外，User-Based CF存在冷啟動(dòng)問題，使推薦不易被用戶闡釋，Item-Based CF恰恰相反，不僅可以迅速推薦，而且可以令用戶比較信服[11].本文在Item-Based CF算法基礎(chǔ)上，提出基于KL散度與JS散度相似度融合的變體的Item-Based CF推薦算法.

1.2 隱含狄利克雷分布(LDA)

Blei等人在2003年提出LDA(Latent Dirichlet Allocation)主題模型[12].LDA又稱三層(文檔層(document)、主題層(topic)、詞層(word))貝葉斯模型.通過無監(jiān)督的學(xué)習(xí)方法來挖掘文檔集中潛藏的主題信息，即通過LDA模型可以得到文檔的各個(gè)主題的概率分布.在評(píng)論信息建模分析過程中，LDA模型不但兼顧了文本的多語義性，同時(shí)還起到降維的效果，即將document-word分布，映射為document-topic分布和topic-word分布.LDA模型如圖1所示.

圖1 LDA模型

其生產(chǎn)過程如下：對(duì)于一篇文檔中的每個(gè)單詞，LDA依據(jù)Dirichlet分布參數(shù)α得到某個(gè)document-topic分布θ并在topic多項(xiàng)式分布θ中抽取一個(gè)topic(用z來表示)，再則依據(jù)狄利克雷分布參數(shù)β得到當(dāng)前topic-word分布Φ，然后從主題z所對(duì)應(yīng)的word多項(xiàng)分布Φ中抽取一個(gè)word(用w來表示).將這個(gè)步驟重復(fù)N次，就生成了文檔d.Φ即為word分布，θ即為topic分布，N表示document的word總數(shù)，M表示document的總數(shù).

所有項(xiàng)目間評(píng)論的隱含相似性的挖掘過程即為以上生成過程的逆向推導(dǎo)過程.基于KL散度與JS散度相似度融合的推薦算法主要運(yùn)用LDA主題模型根據(jù)項(xiàng)目的評(píng)論信息來判斷每個(gè)項(xiàng)目所屬主題的概率分布θ.

1.3 KL散度和JS散度

Kullback-Leibler Divergence(KL散度)又可以被叫做KL距離，作為信息論中統(tǒng)計(jì)變量間獨(dú)立性的重要指標(biāo)而存在.即從概率分布的角度去衡量2個(gè)變量間的距離[13].在連續(xù)區(qū)間D中如若P1和P2分別為兩個(gè)不同的概率密度函數(shù)，那么離散變量KL散度見式(1)：

(1)

由于KL散度不具有對(duì)稱性，即D(P1‖P2)≠D(P2‖P1)，為解決此問題，有人提出了JS散度來作為相似度衡量的指標(biāo).現(xiàn)有兩個(gè)概率分布P1和P2.其JS散度公式見式(2).

(2)

本文經(jīng)過LDA主題分配模型處理每個(gè)項(xiàng)目評(píng)論數(shù)據(jù)得到每個(gè)項(xiàng)目屬于T個(gè)主題的概率分布后，利用JS散度去衡量任意兩個(gè)項(xiàng)目基于主題概率分布的JS散度相似度，即為隱性反饋相似度.

2 KL和JS相似度融合的推薦算法

2.1 項(xiàng)目間KL散度相似度的定義及計(jì)算

在計(jì)算項(xiàng)目間KL散度相似度時(shí)主要使用了王永等[14]人在電影推薦上相似度計(jì)算方法.

定義1：在用戶簽到的實(shí)驗(yàn)數(shù)據(jù)集中,定義所有項(xiàng)目的集合為I={I1,I2,…,Ii}，每個(gè)項(xiàng)目的評(píng)分列表集合為L(zhǎng)ist={List1,List2,…,Listi}，每個(gè)項(xiàng)目評(píng)分列表中有$a個(gè)范圍在(1-5)之間的數(shù)字，即任意一個(gè)項(xiàng)目s評(píng)分列表List={r1,r2,…r$a}(其中s>=1且s<=i，$a為所有用戶對(duì)項(xiàng)目s的評(píng)分總數(shù)量).

根據(jù)以上定義，假如存在任意兩個(gè)項(xiàng)目I1和I2,將所有用戶對(duì)它們的評(píng)分視作兩個(gè)評(píng)分序列,記為L(zhǎng)ist1和List2,根據(jù)公式(3)[14]可得任意兩個(gè)項(xiàng)目I1與I2的KL距離D(I1,I2)為：

(3)

其中：PI1為項(xiàng)目I1的概率密度函數(shù)，max為評(píng)分的最大值(數(shù)據(jù)集的評(píng)分為1～5分),PI1r=$r/$a為項(xiàng)目I1的評(píng)分列表中分?jǐn)?shù)為r的比率，$a為所有用戶對(duì)項(xiàng)目I1評(píng)分的數(shù)量，$r為分值為r的數(shù)量，同理得到PI2r.

由于KL散度不具有對(duì)稱性，即D(I1,I2)≠D(I2,I1)，最終采用的KL距離為式(4)所示[14]：

(4)

定義2：在得到任意兩個(gè)項(xiàng)目之間的KL距離距離Dd(I1,I2)后，則可以計(jì)算任意兩個(gè)項(xiàng)目之間的基于評(píng)分概率分布的KL相似度如式(5)所示[14]：

KL(I1,I2)=sim(I1,I2)=1/1+Dd(I1,I2)

(5)

于此同時(shí)初始化一個(gè)矩陣KL_Sim，用來存儲(chǔ)任意兩個(gè)項(xiàng)目間的相似性.

2.2 項(xiàng)目間JS散度相似性的定義及計(jì)算

為了讓相似度的計(jì)算更加準(zhǔn)確，本文在KL散度相似度的基礎(chǔ)上基于評(píng)論文本信息在主題上的概率分布，引入JS散度再次進(jìn)行項(xiàng)目間相似性度量.即應(yīng)用LDA主題模型挖掘興趣點(diǎn)相關(guān)的評(píng)論信息，學(xué)習(xí)項(xiàng)目的topic分布特征，并用topic向量表示出來，其中定義主題topic的數(shù)量為T，引入JS散度進(jìn)行相似性度量.實(shí)現(xiàn)步驟如下：

1) 首先匯集任意項(xiàng)目所有評(píng)論的描述信息到一個(gè)document，再將所有document匯集成一個(gè)大文檔，從而獲得了一個(gè)包括超大量document的集合，其中的每一個(gè)document對(duì)應(yīng)著一個(gè)項(xiàng)目.

2) 假定被推薦者偏好的topic數(shù)量為T(即topic維度為T)，任意兩個(gè)項(xiàng)目為I1和I2.采用吉布斯采樣法以及似然函數(shù)估計(jì)法，能夠得出topic-word分布Φ和項(xiàng)目的主題分布θ，其中θ為T維向量，向量中的每個(gè)數(shù)字(即每一維)代表該項(xiàng)目相應(yīng)topic下的分布的概率,則PI1=θI1,PI2=θI2.

3) 引入JS散度指標(biāo)來衡量任意兩個(gè)項(xiàng)目之間的相似程度.輸入任意兩個(gè)項(xiàng)目I1和I2主題分布PI1和PI2，利用JS散度計(jì)算任意兩個(gè)項(xiàng)目的主題分布的概率之間的JS距離如式(6)所示:

(6)

定義3：在得到任意兩個(gè)項(xiàng)目之間基于JS的相似度距離后，給出如下定義來計(jì)算任意兩個(gè)項(xiàng)目之間的JS相似度如式(7)所示：

JS(I1,I2)=sim2(I1,I2)=1/1+JS(PI1‖PI2)

(7)

在得到任意兩個(gè)項(xiàng)目間的相似度后，初始化一個(gè)矩陣JS_Sim，用來存儲(chǔ)任意兩個(gè)項(xiàng)目間的相似性.

2.3 將任意兩個(gè)項(xiàng)目之間的相似度進(jìn)行融合

定義4：將得出的基于KL散度的相似度和基于JS散度的相似度融合，即最終的相似度如式(8)所示:

S(I1,I2)=KL(I1,I2)*JS(I1,I2)

(8)

根據(jù)定義2和定義3所得的兩個(gè)相似度矩陣KL_Sim和JS_Sim可得到相似性矩陣S=KL_Sim*JS_Sim=[S(I1,.I2)]n*n，如下所示：

根據(jù)項(xiàng)目相似矩陣S，可得到項(xiàng)目I1的K個(gè)最近鄰居集合S(I1,K)，即為和項(xiàng)目I1最相似的K個(gè)項(xiàng)目的集合.

2.4 生成項(xiàng)目推薦列表

定義5：計(jì)算被推薦者u對(duì)項(xiàng)目I1的最終評(píng)分Pu,I1如式(9)所示：

(9)

其中：ruI2為用戶u給項(xiàng)目I2的評(píng)分，S(I1,I2)為項(xiàng)目I1和項(xiàng)目I2的相似性.根據(jù)預(yù)測(cè)值Pu,I1，最終排序可以做前Top-N個(gè)項(xiàng)目推薦，即取預(yù)測(cè)值最高的前N個(gè)項(xiàng)目作為用戶的項(xiàng)目推薦集.

2.5 本文算法實(shí)現(xiàn)

基于上述分析，本文提出基于KL和JS相似度融合的推薦算法如算法1所示：

算法1：基于KL和JS相似度融合的推薦算法

輸入：item_list,P, T, N,KL_Sim,JS_Sim.

輸出：為目標(biāo)用戶u推薦其可能感興趣點(diǎn)列表

for m,n in enumerate(item_list):

KL_Sim.append(KL(m,n))

JS_Sim.append(JS(m,n))

return KL_Sim,JS_Sim

end for

S=KL_Sim*JS_Sim

S(m,K)=get_SK(S)

Top_N_List=Top_N(S(m,K),run)

return Top_N_List

輸入包括目標(biāo)用戶在內(nèi)的帶有評(píng)分和評(píng)論信息的所有項(xiàng)目列表item_list，與目標(biāo)用戶u最相似的項(xiàng)目數(shù)量P，主題數(shù)量T，推薦項(xiàng)目數(shù)量N.

首先:利用式(5) 計(jì)算任意兩個(gè)項(xiàng)目之間KL相似度KL(m,n)，得到基于KL(m,n)的相似度矩陣KL_Sim；

其次:利用式(7) 計(jì)算任意兩個(gè)項(xiàng)目之間JS相似度JS(m,n)，得到基于JS(m,n)的相似度矩陣JS_Sim;

然后:利用式(8)，得到任意兩個(gè)項(xiàng)目之間的相似度矩陣S，通過get_SK函數(shù)得到最近鄰居項(xiàng)目集合S(m,K)；

最后:利用式(9)，將得分最高的前K個(gè)項(xiàng)目形成Top_N_List列表推薦給目標(biāo)用戶u.

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

為驗(yàn)證本文推薦算法相對(duì)于傳統(tǒng)算法的優(yōu)越之處，將本文推薦算法與傳統(tǒng)的推薦算法應(yīng)用于興趣點(diǎn)(POI)推薦當(dāng)中，得出實(shí)驗(yàn)結(jié)果，通過對(duì)比與分析，進(jìn)而得出結(jié)論.

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

本節(jié)使用從美國最大點(diǎn)評(píng)網(wǎng)站Yelp數(shù)據(jù)集收集的數(shù)據(jù)進(jìn)行數(shù)據(jù)分析.Yelp數(shù)據(jù)集包括1 326 101個(gè)用戶和174 567個(gè)興趣點(diǎn).此外Yelp還包括了5 261 669條評(píng)論和49 626 957個(gè)朋友友誼對(duì)，統(tǒng)計(jì)結(jié)果及數(shù)據(jù)格式見表1～3所示.

表1 Yelp數(shù)據(jù)集統(tǒng)計(jì)

表2 社交關(guān)系數(shù)據(jù)格式

表3 評(píng)分與評(píng)論文本格式

3.2 評(píng)價(jià)指標(biāo)

為驗(yàn)證推薦算法的性能，特使用準(zhǔn)確率(Precision)和召回率(Recall)這兩個(gè)衡量指標(biāo)對(duì)Top-N興趣點(diǎn)推薦進(jìn)行評(píng)測(cè).Precision和Recall是實(shí)驗(yàn)數(shù)據(jù)集上多組用戶的平均值.

其中：Ivisited表示測(cè)試數(shù)據(jù)集中被推薦者已經(jīng)留下簽到數(shù)據(jù)的POI集合.Ire表示前N個(gè)被推薦的POI集合.

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

本文主要使用的是基于用戶友誼對(duì)之間的興趣點(diǎn)訪問數(shù)據(jù)，為測(cè)試算法，按照7∶3的比例將每個(gè)數(shù)據(jù)集隨機(jī)分成70%的訓(xùn)練集和30%的測(cè)試集并且考慮到算法的準(zhǔn)確性，將簽到次數(shù)少于3的朋友用戶和POI除去.同時(shí)本文主要和基于用戶共同評(píng)分項(xiàng)的利用余弦相似度計(jì)算興趣點(diǎn)間相似性后，再融入到傳統(tǒng)的Item-Based CF算法做POI推薦形成對(duì)比，得出實(shí)驗(yàn)結(jié)論.本文算法與對(duì)比算法描述如下：

1)傳統(tǒng)方法(Cos-ItemCf)，基于余弦相似度的協(xié)同過濾(CF)推薦算法，該方法只利用用戶的共同評(píng)分興趣點(diǎn)計(jì)算相似性，在沒有加入POI相關(guān)的上下文信息的情況下，在傳統(tǒng)的Item-Based CF算法中應(yīng)用做前Top-N個(gè)POI推薦.

2)本文算法(LDA-ItemCf)，基于所有用戶對(duì)每個(gè)興趣點(diǎn)的評(píng)分列表，使用KL散度計(jì)算任意兩個(gè)興趣點(diǎn)之間的顯性相似度，基于每個(gè)興趣點(diǎn)的評(píng)論信息，結(jié)合LDA模型使用JS散度挖掘興趣點(diǎn)之間的隱性相似度.將顯性相似度和隱性相似度融合后，融入到Item-Based CF算法做前Top-N個(gè)POI推薦.

3.3.1 影響參數(shù)對(duì)比分析

從圖2、3中可以看出相似度融合后的方法準(zhǔn)確率和召回率都高于傳統(tǒng)的Cosine計(jì)算的相似度的方法.即表明使用本文方法在推薦中出現(xiàn)在用戶喜歡列表中的興趣點(diǎn)數(shù)增加，提高了推薦的準(zhǔn)確性.

圖2 #P-nearest neighbors

圖3 #P-nearest neighbors

從圖4、5中發(fā)現(xiàn)，實(shí)驗(yàn)中LDA的Topic數(shù)量影響最終的推薦結(jié)果.Topic數(shù)量增多，準(zhǔn)確率和召回率也在上升，在Topic數(shù)量為60的時(shí)候達(dá)到最優(yōu)推薦效果.

圖4 不同Topic數(shù)量下的兩個(gè)方法的準(zhǔn)確率對(duì)比圖

圖5 不同Topic數(shù)量下的兩個(gè)方法的召回率對(duì)比圖

3.3.2 最終推薦對(duì)比分析

經(jīng)過使用多組數(shù)據(jù)進(jìn)行參數(shù)調(diào)整的分析驗(yàn)證后，將最相似的興趣點(diǎn)數(shù)量設(shè)置為80，LDA主題數(shù)量設(shè)置為60，將產(chǎn)生前Top-N個(gè)興趣點(diǎn)推薦給用戶，如圖6、7得到了本文算法與傳統(tǒng)的基于項(xiàng)目的POI推薦算法的推薦比較結(jié)果.

從圖中可以明顯看出：因?yàn)槠浜灥綌?shù)據(jù)存在數(shù)據(jù)稀疏性問題，所以從實(shí)驗(yàn)所得的準(zhǔn)確率和召回率來看興趣點(diǎn)推薦算法的精度不是很高.由于Precision和Recall的計(jì)算公式的性質(zhì).當(dāng)推薦列表中被推薦的POI數(shù)量增加時(shí)，Precision降低、Recall上升.其中本文的基于KL和JS相似度融合后的推薦方法在準(zhǔn)確率和召回率方面都高于傳統(tǒng)的基于Cosine計(jì)算相似度的方法，在一定程度上緩解了傳統(tǒng)方法依賴于用戶共同評(píng)分項(xiàng)計(jì)算POI相似度的問題，提高了推薦的質(zhì)量.

圖6 不同被推薦POI數(shù)量下的兩個(gè)方法準(zhǔn)確率對(duì)比圖

圖7 不同被推薦POI數(shù)量下的兩個(gè)方法召回率對(duì)比圖

4 結(jié) 語

傳統(tǒng)方法在計(jì)算項(xiàng)目間相似性時(shí)，通常只考慮了用戶共同評(píng)分項(xiàng)，在實(shí)際應(yīng)用中，由于數(shù)據(jù)集的稀疏性會(huì)導(dǎo)致共同評(píng)分項(xiàng)十分稀少，造成在計(jì)算項(xiàng)目間相似性時(shí)存在一定的誤差，影響推薦效果.本文引入信息論中的KL散度和JS散度，分別計(jì)算項(xiàng)目之間基于評(píng)分值概率密度分布的相似性和基于評(píng)論信息的主題概率密度分布的相似性，將兩個(gè)相似性融合后應(yīng)用到傳統(tǒng)的基于項(xiàng)目的協(xié)同過濾算法中進(jìn)行興趣點(diǎn)推薦.在一定程度上緩解了數(shù)據(jù)稀疏性的問題，使得計(jì)算項(xiàng)目間相似性時(shí)不僅局限在共同評(píng)分項(xiàng)，與此同時(shí)，充分利用了興趣點(diǎn)評(píng)分和評(píng)論的信息，增強(qiáng)了推薦的可靠性和準(zhǔn)確性.在真實(shí)的數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)分析表明，該方法具有良好的性能且優(yōu)于傳統(tǒng)的基于項(xiàng)目進(jìn)行興趣點(diǎn)推薦的協(xié)同過算法，具有良好的應(yīng)用價(jià)值.