胡 文，景玉海

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

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

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

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

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

1 相關(guān)工作

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

基于協(xié)同過濾的推薦，即從用戶歷史簽到記錄角度進行推薦，可進一步分為基于內(nèi)存的推薦和基于模型的推薦，基于內(nèi)存的推薦就是傳統(tǒng)的User-Based CF和Item-Based CF[10].User-Based CF時效性較強，Item-Based CF個性化較強.另外，User-Based CF存在冷啟動問題，使推薦不易被用戶闡釋，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)督的學習方法來挖掘文檔集中潛藏的主題信息，即通過LDA模型可以得到文檔的各個主題的概率分布.在評論信息建模分析過程中，LDA模型不但兼顧了文本的多語義性，同時還起到降維的效果，即將document-word分布，映射為document-topic分布和topic-word分布.LDA模型如圖1所示.

圖1 LDA模型

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

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

1.3 KL散度和JS散度

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

(1)

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

(2)

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

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

2.1 項目間KL散度相似度的定義及計算

在計算項目間KL散度相似度時主要使用了王永等[14]人在電影推薦上相似度計算方法.

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

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

(3)

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

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

(4)

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

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

(5)

于此同時初始化一個矩陣KL_Sim，用來存儲任意兩個項目間的相似性.

2.2 項目間JS散度相似性的定義及計算

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

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

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

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

(6)

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

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

(7)

在得到任意兩個項目間的相似度后，初始化一個矩陣JS_Sim，用來存儲任意兩個項目間的相似性.

2.3 將任意兩個項目之間的相似度進行融合

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

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

(8)

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

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

2.4 生成項目推薦列表

定義5：計算被推薦者u對項目I1的最終評分Pu,I1如式(9)所示：

(9)

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

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

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

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

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

輸出：為目標用戶u推薦其可能感興趣點列表

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

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

表3 評分與評論文本格式

3.2 評價指標

為驗證推薦算法的性能，特使用準確率(Precision)和召回率(Recall)這兩個衡量指標對Top-N興趣點推薦進行評測.Precision和Recall是實驗數(shù)據(jù)集上多組用戶的平均值.

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

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

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

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

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

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

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

圖2 #P-nearest neighbors

圖3 #P-nearest neighbors

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

圖4 不同Topic數(shù)量下的兩個方法的準確率對比圖

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

3.3.2 最終推薦對比分析

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

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

圖6 不同被推薦POI數(shù)量下的兩個方法準確率對比圖

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

4 結(jié) 語

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