基于KL散度與JS散度相似度融合推薦算法

胡 文，景玉海

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

現(xiàn)今信息爆炸式的增長，宣告著人們正處于一個無法從浩瀚信息海洋中高效篩選出自己所需信息的”信息超載”[1]時代.面臨該亟需解決的問題，推薦系統(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)一利用社會、順序、時間和空間模式來表征用戶的登記行為，將CPS系統(tǒng)中的異構(gòu)流數(shù)據(jù)融入多模貝葉斯嵌入模型，來共同為用戶決策推薦.Ren等人[6]將興趣，地理，社會和分類相關(guān)性分?jǐn)?shù)整合到推薦算法的概率矩陣分解模型PMF中，利用聯(lián)合后的分?jǐn)?shù)進(jìn)行推薦.Ye等人[7]利用個人偏好、好友關(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)的評論信息這3個因素融合后進(jìn)行興趣點(diǎn)推薦.Hu等人[9]在進(jìn)行推薦時應(yīng)用了STT(Spatio-Temporal Topic)模型，將用戶的概況與簽到的時空主題相結(jié)合來提高推薦精度.

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

為有效解決以上推薦時出現(xiàn)的問題及研究中包含的不完善之處，設(shè)計(jì)了一種基于KL散度和JS散度所求相似度融合的推薦算法，其基本內(nèi)容為：首先將每個項(xiàng)目相關(guān)的評論文本信息進(jìn)行主題建模計(jì)算項(xiàng)目間隱性相似度，再利用所有用戶對每個項(xiàng)目的評分進(jìn)行顯性相似度度量，兩者融合，最后在推薦生成階段，將融合后的相似度加入到基于項(xiàng)目的協(xié)同過濾中，來生成得分最高的前N個項(xiàng)目進(jìn)行推薦，讓推薦系統(tǒng)中的冷啟動問題得到緩解，在解決數(shù)據(jù)稀疏性問題方面也取得了較好的功效，降低了生成推薦時計(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時效性較強(qiáng)，Item-Based CF個性化較強(qiáng).另外，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)督的學(xué)習(xí)方法來挖掘文檔集中潛藏的主題信息，即通過LDA模型可以得到文檔的各個主題的概率分布.在評論信息建模分析過程中，LDA模型不但兼顧了文本的多語義性，同時還起到降維的效果，即將document-word分布，映射為document-topic分布和topic-word分布.LDA模型如圖1所示.

圖1 LDA模型

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

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

1.3 KL散度和JS散度

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

(1)

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

(2)

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

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

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

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

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

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

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

(6)

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

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

(7)

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

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

定義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ù)項(xiàng)目相似矩陣S，可得到項(xiàng)目I1的K個最近鄰居集合S(I1,K)，即為和項(xiàng)目I1最相似的K個項(xiàng)目的集合.

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

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

(9)

其中：ruI2為用戶u給項(xiàng)目I2的評分，S(I1,I2)為項(xiàng)目I1和項(xiàng)目I2的相似性.根據(jù)預(yù)測值Pu,I1，最終排序可以做前Top-N個項(xiàng)目推薦，即取預(yù)測值最高的前N個項(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)的帶有評分和評論信息的所有項(xiàng)目列表item_list，與目標(biāo)用戶u最相似的項(xiàng)目數(shù)量P，主題數(shù)量T，推薦項(xiàng)目數(shù)量N.

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

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

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

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

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

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

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

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

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

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

表3 評分與評論文本格式

3.2 評價指標(biāo)

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

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

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

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

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

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

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

從圖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的時候達(dá)到最優(yōu)推薦效果.

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

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

3.3.2 最終推薦對比分析

經(jīng)過使用多組數(shù)據(jù)進(jìn)行參數(shù)調(diào)整的分析驗(yàn)證后，將最相似的興趣點(diǎn)數(shù)量設(shè)置為80，LDA主題數(shù)量設(shè)置為60，將產(chǎn)生前Top-N個興趣點(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ù)量增加時，Precision降低、Recall上升.其中本文的基于KL和JS相似度融合后的推薦方法在準(zhǔn)確率和召回率方面都高于傳統(tǒng)的基于Cosine計(jì)算相似度的方法，在一定程度上緩解了傳統(tǒng)方法依賴于用戶共同評分項(xiàng)計(jì)算POI相似度的問題，提高了推薦的質(zhì)量.

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

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

4 結(jié) 語

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