基于貝葉斯后驗(yàn)概率和非合作博弈的推薦算法

索 巖 程向羽(河南師范大學(xué)新聯(lián)學(xué)院 河南 新鄉(xiāng) 453000)

2(河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453000)

0 引 言

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，人與人之間的社交日益網(wǎng)絡(luò)化、虛擬化，人們?cè)絹碓搅?xí)慣于通過社交軟件獲得情投意合的朋友和感興趣的活動(dòng)。但面對(duì)龐大的社交數(shù)據(jù)，人們難以從錯(cuò)綜復(fù)雜信息中獲得自己感興趣的內(nèi)容。個(gè)性化推薦可以有的放矢地為用戶推薦感興趣的社友或活動(dòng)，目前國內(nèi)外學(xué)者通過不同的手段深入分析客戶行為模式和交互數(shù)據(jù)以求獲得用戶潛在的興趣點(diǎn)。例如，文獻(xiàn)[1]利用加權(quán)平均聚合法推導(dǎo)用戶興趣偏好，然后融合矩陣分解和協(xié)同過濾向用戶推薦好友；文獻(xiàn)[2]利用用戶好友評(píng)價(jià)矩陣分析好友的重要程度及興趣匹配度,借助加權(quán)平均評(píng)分模式向用戶推薦興趣相似度高的好友；文獻(xiàn)[3]利用隨機(jī)游走預(yù)測(cè)單一用戶興趣偏好，聚合用戶組興趣偏好得到共同的興趣類，為用戶推薦活動(dòng)或興趣相投的好友；文獻(xiàn)[4]利用用戶好友對(duì)活動(dòng)的興趣的不同反饋，建立基于納什均衡的好友推薦機(jī)制；文獻(xiàn)[5]利用LDA計(jì)算用戶興趣相似度，融合用戶影響力和興趣相似度預(yù)測(cè)用戶好友組整體偏好，以此向組內(nèi)用戶推薦書籍；文獻(xiàn)[6]提出了一種貝葉斯地理生成模式，以簽到地為組聚合組內(nèi)用戶興趣，基于此向同一地理組內(nèi)的用戶推薦活動(dòng)；文獻(xiàn)[7]對(duì)用戶的顯式和隱式行為進(jìn)行建模，現(xiàn)實(shí)用戶個(gè)性化活動(dòng)推薦；文獻(xiàn)[8]研究了用戶短期行為和長(zhǎng)期興趣偏好的關(guān)系，利用馬爾可夫鏈解決數(shù)據(jù)稀疏問題，借助概率模型向用戶個(gè)性化推薦活動(dòng)。以上研究方法大多通過分析用戶交互信息獲取用戶的興趣偏好，以興趣偏好為依據(jù)，采用協(xié)同過濾等方法向用戶進(jìn)行個(gè)性化推薦，這些方法雖然便捷有效，但受制于交互信息量少等數(shù)據(jù)稀疏問題[9-10]，推薦的查準(zhǔn)率有待提高。為了進(jìn)一步提高協(xié)同過濾推薦算法的推薦精度，本文提出了一種基于貝葉斯后驗(yàn)概率和非合作博弈的推薦算法。

1 用戶隱式行為特性

在用戶實(shí)際網(wǎng)絡(luò)環(huán)境中，與其產(chǎn)生交互的無非有人或物兩大類。人與人之間產(chǎn)生信任，人對(duì)物產(chǎn)生興趣，無論是信任還是興趣都是用戶隱式行為特征。一個(gè)用戶多次瀏覽、咨詢一個(gè)活動(dòng)，這些交互信息體現(xiàn)了用戶對(duì)活動(dòng)的興趣度，表明用戶可能想?yún)⑴c活動(dòng)，同理，用戶間也存在信任。這些隱式特征的背后蘊(yùn)含著用戶的行為趨向，本文重點(diǎn)考慮用戶對(duì)活動(dòng)的興趣度和用戶間的信任度，通過文件主題模型求取用戶與其參加過的所有社交活動(dòng)的主題分布，利用隱含主題概率分布來表征用戶對(duì)活動(dòng)的興趣度；利用用戶間的信任傳遞機(jī)制求取用戶的直接信任值和間接信任值。假設(shè)用戶集合為U，被評(píng)價(jià)過的社交活動(dòng)集合為S，未被評(píng)價(jià)的新社交活動(dòng)集合為S′。

1.1 用戶對(duì)活動(dòng)興趣度

本文利用文件主題模型(Latent dirichlet allocation,LDA)求取用戶ui參加過的社交活動(dòng)S的主題分布，并用其表示目標(biāo)用戶ui的興趣度。LDA假設(shè)在一個(gè)文檔中包含一些主題構(gòu)成的概率分布，而主題又是由一些單詞構(gòu)成的概率分布。設(shè)docui表示用戶ui所參加過社交活動(dòng)形成的文件，利用LDA求取docui中隱含主題多項(xiàng)式分布。參考文獻(xiàn)[11]方法，將用戶社交文件docui的主題概率分布近似看作用戶對(duì)社交活動(dòng)的興趣度。在docui中隱含主題詞與單詞的概率wt服從超參數(shù)α的狄利克雷分布，文件與單詞的概率φdocui服從超參數(shù)β的狄利克雷分布。對(duì)文件docui中的第m個(gè)單詞，利用參數(shù)φdocui的多項(xiàng)式分布Mult(φdocui)形成單詞主題配對(duì)pdocui,m，利用參數(shù)wt的多項(xiàng)式分布Mult(wt)對(duì)文件docui中的第m單詞生成wdocui,m。據(jù)此，可得出如下生成概率：

P(W,Z|κ,γ)=P(W|Z,γ)·P(Z|κ)

(1)

式中：P(W|Z,γ)表示文檔docui對(duì)應(yīng)的主題概率；P(Z|κ)表示給定某個(gè)主題詞生成詞的概率；W、Z表示所有詞集合和主題集合。由于不可能從模型中推斷出參數(shù)κ和γ，采用吉布斯采樣從單詞可觀條件下計(jì)算所屬主題的概率分布P(Z|W,γ)：

(2)

(3)

(4)

(5)

設(shè)用戶ui的文件為docui，社交活動(dòng)sj的文件為docsj，兩者所對(duì)應(yīng)的主題分布為φdocui和φdocsj，為了求取用戶與社交活動(dòng)主題的相似度，本文引入庫爾貝克-萊布勒(Kullback-Leibler,KL)散度[11]和延森-香農(nóng)(Jen-sen-Shannon)散度[12]來計(jì)算兩者之間的相似度，延森-香農(nóng)散度定義為：

(6)

式中：KL(·)表示庫爾貝克-萊布勒散度，定義如下：

(7)

JS(ui‖sj)會(huì)隨著φdocui和φdocsj兩者主題分布的差別而增大，這里定義用戶ui對(duì)社交活動(dòng)sj的興趣度為ini,j：

ini,j=1-JS(ui‖sj)

(8)

1.2 用戶間信任度

在網(wǎng)絡(luò)社交活動(dòng)中，用戶間的信任一般分為直接信任和間接信任[13]。直接信任就是基于用戶間的某種認(rèn)知而產(chǎn)生的一對(duì)一信任，而間接信任就是用戶因某個(gè)中間人的推薦而對(duì)另一個(gè)用戶的信任。

對(duì)于給定的社交活動(dòng)網(wǎng)絡(luò)，可將其對(duì)應(yīng)看成一個(gè)用戶間因信任值而形成的信任網(wǎng)絡(luò)Q=(U,E,D)，其中U表示社交用戶集合，E為信任網(wǎng)絡(luò)中有向邊的集合，每一條邊e(ui,uj)表示用戶ui對(duì)用戶uj的信任關(guān)系，D表示有向邊上的信任度集合，wi,j表示用戶ui對(duì)用戶uj的直接信任度值。

在給定的信任網(wǎng)絡(luò)Q=(U,E,D)中，目標(biāo)用戶ui對(duì)非直接信任用戶ux的信任感知是基于一條可達(dá)路徑pa=(ui,…,uy,uz,…,ux)，并且路徑pa上任意邊e(uy,uz)的信任度都大于所設(shè)定的信任閾值wθ，那么路徑pa就是一條信任路徑。但信任也會(huì)隨著路徑的加大而衰減，因此須在信任路徑中規(guī)定一定的跳數(shù)閾值hθ。

若一個(gè)用戶被較多的其他用戶所信任，那么一般表明此用戶的可信度較高，反之亦然。基于此，借鑒Pagerank算法思想求取用戶的信任度：

(9)

式中：Tui表示用戶ui信任用戶集合；|Tui|表示信任用戶集合中用戶的數(shù)量；Nuj、Nur分別表示用戶uj、ur被信任的用戶個(gè)數(shù)。用戶節(jié)點(diǎn)間的信任度是基于用戶面對(duì)面的直接信任產(chǎn)生的，但在實(shí)際的社交網(wǎng)絡(luò)中，許多用戶間可能不存在或存在不明顯的潛在信任關(guān)系，這樣得到的信任矩陣非常稀疏，計(jì)算信任相似度的難度就會(huì)增大。為此，本文在計(jì)算用戶信任矩陣前，引入信任傳遞以計(jì)算無交集用戶間的信任度，若兩個(gè)用戶間沒有直接信任關(guān)系，其信任度的計(jì)算式為：

(10)

(11)

則用戶之間的信任度可表示為：

式中：utumun表示用戶um對(duì)用戶un的信任度。

2 基于貝葉斯后驗(yàn)概率的行為預(yù)測(cè)

(12)

根據(jù)貝葉斯后驗(yàn)相關(guān)理論，可推導(dǎo)出用戶ui參與活動(dòng)sj的概率為：

(13)

式中：Sig(·)表示邏輯函數(shù)。社交活動(dòng)sj對(duì)用戶ui選擇參與其他類似活動(dòng)的貢獻(xiàn)率πj,i計(jì)算如下：

(14)

(15)

[Sig(-πj,iini,j-utumun)]δ(ci,j,1)[1-Sig(-πj,iini,j-utumun)][1-δ(ci,j,1)]

(16)

式中：δ(x,y)為克羅內(nèi)克函數(shù)。根據(jù)興趣度ini,j、用戶間的信任度utuiuj過程變量的先驗(yàn)分布，式(16)可表示為：

(17)

這是通過貝葉斯后驗(yàn)概率來擬合訓(xùn)練樣本數(shù)據(jù)以預(yù)測(cè)用戶決策行為。這種行為的不確定性符合香農(nóng)信息熵的概念，即一個(gè)人的行為決策是不確定的，是否決定參與受多方面信息的影響，綜合正向信息越多，其參與的可能性就越大。為了使樣本預(yù)測(cè)值與實(shí)際值的差值最小化，需要基于信息熵構(gòu)建二者之間的對(duì)數(shù)損失函數(shù)：

(18)

建立損失函數(shù)式(18)作為優(yōu)化目標(biāo)：

(19)

將式(17)代入式(18)中可得：

(20)

根據(jù)高斯分布，式(20)可近似為：

(21)

將式(16)代入式(21)中可得：

Li,j∝-δ(ci,j,1)log[Sig(-πj,iini,j-utumun)]-

[1-δ(ci,j,1)]log[1-Sig(-πj,iini,j-utumun)]-

(22)

(23)

(24)

(25)

(26)

(27)

(28)

迭代終止后，算法就得到基于貝葉斯后驗(yàn)概率的用戶興趣和信任顯示反饋：

INi,j=[in1,1,in1,2,…,ini,j-1,ini,j]i∈[1,|U|],j∈[1,M]

(29)

UTm,n=[ut1,1,ut1,2,…,ut(|U|,|U|)]

(30)

若經(jīng)g輪迭代不滿足以上收斂條件，則需執(zhí)行第g+1輪迭代：

(31)

(32)

3 基于博弈論的活動(dòng)推薦

(33)

(34)

式中：τ≥1，以保證代價(jià)函數(shù)為凸函數(shù)；ξ1、ξ2為均衡系數(shù)，并且ξ1、ξ2≥0,ξ1+ξ2=1。用戶ui的效益函數(shù)為：

(35)

在其他用戶不改變自己策略的前提下，用戶此時(shí)所選的策略能使其他用戶的策略取得最大效益，則稱此時(shí)的策略組合達(dá)到納什均衡，即：

(36)

(37)

圖1 算法框架示意圖

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

4.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)標(biāo)準(zhǔn)

為了仿真實(shí)驗(yàn)的有效性，這里利用豆瓣同城(北京、上海、廣州、深圳)在2017年1月1日—2019年10月31日期間的所有社交活動(dòng)，主要采集的信息包括用戶信息和社交活動(dòng)信息，具體如表1所示。

表1 數(shù)據(jù)統(tǒng)計(jì)明細(xì)

采用查準(zhǔn)率Precision、查全率Recall和平均絕對(duì)誤差MAE三個(gè)評(píng)價(jià)指標(biāo)評(píng)估各推薦算法的性能，其計(jì)算公式見式(38)-式(40)。

(38)

(39)

(40)

式中：Pj為候選社交活動(dòng)sj的被關(guān)注數(shù);Hj為候選社交活動(dòng)sj的實(shí)際參與數(shù)；Nh為候選社交活動(dòng)個(gè)數(shù)。

4.2 參數(shù)設(shè)置

(a) 參數(shù)變化對(duì)模型的影響

(a) 參數(shù)變化對(duì)模型的影響

表2 參數(shù)設(shè)置

實(shí)驗(yàn)硬件環(huán)境為Intel(R)Core(TM) i7- 9700@3 GHz,RAM:8 GB，在Windows 7操作系統(tǒng)上使用Python編程實(shí)現(xiàn)。將豆瓣北京、上海、廣州、深圳四個(gè)城市數(shù)據(jù)集合中已結(jié)束社交活動(dòng)作為訓(xùn)練集，新社交活動(dòng)作為測(cè)試集，為驗(yàn)證本文所提算法的性能，將本文算法與文獻(xiàn)[14]、文獻(xiàn)[15]和文獻(xiàn)[16]算法進(jìn)行社交活動(dòng)推薦效果對(duì)比。文獻(xiàn)[14]提出了一種基于用戶行為特征的個(gè)性化推薦算法，通過學(xué)習(xí)用戶以往行為特征建立潛在空間的偏好特征映射，將用戶-項(xiàng)目交互分解為因數(shù)，并在推薦中將用戶的靜態(tài)和動(dòng)態(tài)偏好組合在一起；文獻(xiàn)[15]算法是一種個(gè)性化社會(huì)推薦算法，是對(duì)面向隱式反饋貝葉斯個(gè)性化排序推薦的改進(jìn)；文獻(xiàn)[16]建立用戶活動(dòng)交互頻數(shù)的置信度，并將偏好置信度視為顯示反饋的評(píng)分，借助矩陣分解策略為用戶提供推薦。

4.3 不同算法的查準(zhǔn)率和查全率對(duì)比

將四種算法分別在豆瓣同城北京、上海、廣州、深圳四個(gè)數(shù)據(jù)子集上進(jìn)行新社交活動(dòng)推薦，N表示推薦活動(dòng)的個(gè)數(shù)。不同N值下四種算法的查準(zhǔn)率和查全率如圖4所示。

圖4 各算法不同N值下評(píng)價(jià)指標(biāo)對(duì)比

本文算法在不同N值下的推薦指標(biāo)明顯優(yōu)于其他三種推薦算法，說明本文算法利用貝葉斯后驗(yàn)概率對(duì)用戶興趣度和信任度的預(yù)測(cè)與實(shí)際情況基本一致，基于非合作博弈用戶效益最大化的納什均衡結(jié)果符合用戶的實(shí)際需求，最終取得了較高的查準(zhǔn)率和查全率。圖4(a)和圖4(b)展示了四種算法在豆瓣同城北京數(shù)據(jù)集上的推薦結(jié)果，隨著N值的增大，查準(zhǔn)率先增后降，查全率則是一直增大，其中在N=7之前，文獻(xiàn)[14]算法的查準(zhǔn)率高于本文算法。圖4(c)和圖4(d)展示了四種算法在豆瓣同城上海數(shù)據(jù)集上的推薦結(jié)果，隨著N值的增大，查準(zhǔn)率也是先增后降，查全率則是一直增大，只是在N=6之前，文獻(xiàn)[14]算法的查準(zhǔn)率高于本文算法。圖4(e)和圖4(f)展示了四種算法在豆瓣同城廣州數(shù)據(jù)集上的推薦結(jié)果，隨著N值的增大，查準(zhǔn)率和查全率的變化趨勢(shì)跟之前一樣，在N=6之前，文獻(xiàn)[14]算法的查準(zhǔn)率高于本文算法。圖4(g)和圖4(h)展示了四種算法在豆瓣同城深圳數(shù)據(jù)集上的推薦結(jié)果，隨著N值的增大，查準(zhǔn)率和查全率的變化趨勢(shì)跟與在北京、上海、廣州數(shù)據(jù)集上一致，不同的是在N=5之前，文獻(xiàn)[14]算法的查準(zhǔn)率高于本文算法。綜上可知，本文算法適合應(yīng)用于較大規(guī)模的數(shù)據(jù)集上，隨著數(shù)據(jù)集的增大，基于貝葉斯后驗(yàn)概率擬合的隱式特征更能符合用戶的真實(shí)情況。總體上，本文算法相較于其他三種算法在查準(zhǔn)率上至少提高了3.13%，在查全率上至少提高了2.62%。

4.4 不同算法的MAE對(duì)比

為了比較本文算法與其他兩種算法在MAE上的差異，以訓(xùn)練集所占比例為變量，四種算法MAE的變化如圖5所示。

圖5 不同算法間的MAE對(duì)比

可以看出，四種算法隨著訓(xùn)練集所占比例的增加，MAE都呈下降的趨勢(shì)，但本文算法的MAE值整體上都高于其他三種算法。在豆瓣同城北京和上海數(shù)據(jù)集上，當(dāng)訓(xùn)練集所占比例大于70%后，本文算法的MAE值明顯高于其他三種算法，且MAE下降的幅度緩慢；在豆瓣同城廣州和深圳數(shù)據(jù)集上，本文算法的MAE值在各個(gè)比例訓(xùn)練集省都高于其他三種算法，但整體上小于豆瓣同城北京和上海數(shù)據(jù)集上的MAE值，這是由于后兩個(gè)數(shù)據(jù)集的規(guī)模和新社交活動(dòng)量都小于前兩個(gè)數(shù)據(jù)集，這對(duì)貝葉斯后驗(yàn)概率的擬合造成偏差，最終導(dǎo)致活動(dòng)推薦結(jié)果與實(shí)際值的偏差變大。

5 結(jié) 語

針對(duì)傳統(tǒng)協(xié)同過濾推薦算法推薦精度低等問題，提出了一種基于貝葉斯后驗(yàn)概率預(yù)測(cè)和非合作博弈的個(gè)性化推薦算法。算法將用戶的興趣度和信任度等隱

式特征賦予合理的先驗(yàn)分布，建立隱式特征生成過程的聯(lián)合概率表達(dá)，借助貝葉斯后驗(yàn)概率預(yù)測(cè)隱式特征后的顯式反饋；將推薦結(jié)果轉(zhuǎn)化為非合作博弈中用戶效益最大化的納什均衡求解，最終活動(dòng)推薦給用戶的活動(dòng)集合。與其他三種推薦算法相比，本文算法有較高的查準(zhǔn)率、查全率和平均絕對(duì)誤差。但先驗(yàn)?zāi)Ｐ蛥?shù)的獲取僅靠經(jīng)驗(yàn)，如何進(jìn)一步降低參數(shù)的敏感性將是后續(xù)研究的重點(diǎn)。