融合社交關(guān)系與代價(jià)敏感的興趣點(diǎn)推薦算法

張進(jìn)，孫福振，王紹卿，徐上上

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255049)

近年來社交網(wǎng)絡(luò)應(yīng)用的一個(gè)明顯進(jìn)步是引入空間技術(shù)，促進(jìn)了基于位置的社交網(wǎng)絡(luò)location-based social network, LBSN)的蓬勃發(fā)展，如Foursquare, Twinkle和GeoLife。在LBSN中，基于空間技術(shù)的位置也被稱為興趣點(diǎn)(point-of-interest, POI)，例如餐館、商店和博物館等。然而，LBSN的興趣點(diǎn)推薦面臨很多的問題，例如矩陣稀疏、推薦精度不高、模型性能不高等。選擇合適的上下文信息與推薦方法是提高推薦精度、更好地挖掘用戶偏好的一種方法。在LBSN中，興趣點(diǎn)推薦融合多種上下文信息，Jamali等[1]提出了SocialMF算法，將社交關(guān)系融合矩陣分解，集成信任傳遞機(jī)制，緩解了冷啟動(dòng)問題。Du等[2]將L1正則融入ListMLE算法損失函數(shù)中，緩解了排序列表的稀疏問題。Xu等[3]探究了基于Group的列表級(jí)排序?qū)W習(xí)算法，將關(guān)聯(lián)性高和關(guān)聯(lián)性低的標(biāo)簽劃分為組的形式，結(jié)合無監(jiān)督學(xué)習(xí)生成更準(zhǔn)確的標(biāo)簽。Yu等[4]探究高斯建模用戶簽到分布，利用BPR優(yōu)化泊松矩陣分解過程，Zhang等[5]使用高斯核密度估計(jì)計(jì)算用戶的地理因素對(duì)興趣點(diǎn)推薦的影響。

近年來，有研究者將排序?qū)W習(xí)方法融入推薦過程中。排序?qū)W習(xí)是利用機(jī)器學(xué)習(xí)方法對(duì)物品或興趣點(diǎn)進(jìn)行排序，輸出符合用戶偏好的興趣點(diǎn)列表。按照訓(xùn)練數(shù)據(jù)的形式不同分為點(diǎn)級(jí)排序?qū)W習(xí)、對(duì)級(jí)排序?qū)W習(xí)以及列表級(jí)排序?qū)W習(xí)。Yin等[6]基于用戶隱式反饋使用點(diǎn)級(jí)排序?qū)W習(xí)方法挖掘隱含特征矩陣。Pan等[7]考慮用戶傾向于物品之間的偏序關(guān)系，在物品對(duì)集合上定義損失函數(shù)并學(xué)習(xí)排序模型。Li等[8]利用列表級(jí)方法ListNet處理特征矩陣，對(duì)比排序性能的差異。Chen等[9]將列表級(jí)排序應(yīng)用到餐廳推薦中，利用排序模型學(xué)習(xí)基模型產(chǎn)生的結(jié)果，為垂直搜索提供了查詢與推薦方案。上述算法融入不同的上下文信息，大部分采用矩陣分解的方式計(jì)算用戶潛在特征向量，存在一定的局限性：僅僅考慮單個(gè)物品或兩個(gè)物品之間的關(guān)系，未能考慮推薦列表整體的特性。對(duì)于分布不均勻的數(shù)據(jù)，物品對(duì)或興趣點(diǎn)對(duì)的差異過大，從而對(duì)推薦精度的影響程度存在差異。

為挖掘個(gè)性化的用戶偏好，從推薦列表整體出發(fā)，考慮用戶推薦列表中不同位置的關(guān)注度存在差異。本文改進(jìn)列表級(jí)排序?qū)W習(xí)方法，把ListMLE[10]引入興趣點(diǎn)推薦，并融合社交信息作為打分函數(shù)計(jì)算方式，采用代價(jià)敏感方式賦予列表不同位置不同權(quán)重，最終得到排序模型，為用戶產(chǎn)生推薦結(jié)果。

1 ListMLE算法

設(shè)定一個(gè)隨機(jī)初始化打分函數(shù)Score對(duì)這n個(gè)興趣點(diǎn)列表進(jìn)行評(píng)價(jià):

(1)

Sort函數(shù)呈降序排列，則它們對(duì)應(yīng)的人工排名為

(2)

將集合表示為T={(U,H),Y}，此集合作為ListMLE的訓(xùn)練集。將用戶的興趣點(diǎn)列表表示為向量x(j)，每個(gè)向量都由打分函數(shù)得出對(duì)應(yīng)分?jǐn)?shù)。因此將訓(xùn)練集改寫為T={X,Y}。

依據(jù)Plackeet-luce模型，定義排序模型中序列的概率為

(3)

式中：w為模型參數(shù);y(i)和y(k)為排序列表中第i和k個(gè)興趣點(diǎn)。因此排序似然函數(shù)為

(4)

對(duì)似然函數(shù)求導(dǎo)得梯度公式(5)：

(5)

根據(jù)公式(5)使用梯度下降算法求得參數(shù)w，通過訓(xùn)練獲取排序模型后，可以對(duì)用戶的興趣點(diǎn)列表進(jìn)行排序后進(jìn)行推薦。ListMLE算法的步驟如下：

1)首先預(yù)處理數(shù)據(jù)，將數(shù)據(jù)預(yù)處理成列表形式{(x(1),y(1)),(x(2),y(2))，…，(x(m),y(m))} ，同時(shí)定義學(xué)習(xí)率η以及容忍誤差ε。

2)其次初始化神經(jīng)網(wǎng)絡(luò)參數(shù)w，開始循環(huán),將所有的樣本輸入到神經(jīng)網(wǎng)絡(luò)中，并計(jì)算梯度Δw，通過梯度依次更新參數(shù)w，直至所有樣本已經(jīng)訓(xùn)練完成。

3)每次循環(huán)計(jì)算訓(xùn)練集的損失，直至損失小于設(shè)定的容忍誤差ε。循環(huán)結(jié)束后輸出訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)參數(shù)w并產(chǎn)生推薦結(jié)果。

在數(shù)據(jù)的處理過程中，ListMLE算法一般采用隨機(jī)初始化函數(shù)Score的方式對(duì)每個(gè)列表進(jìn)行初始化的打分，在基于位置的社交網(wǎng)絡(luò)中，上下文信息是解決初始化問題以及冷啟動(dòng)問題的有效途徑，本文接下來采用用戶之間的社交關(guān)系信息作為初始化列表分?jǐn)?shù)的依據(jù)，同時(shí)針對(duì)用戶對(duì)于列表前后部分的關(guān)注度存在差異的問題，使用代價(jià)敏感的方式賦予列表中不同位置的興趣點(diǎn)不同的權(quán)重，以此作為基于社交信任與代價(jià)敏感的得分函數(shù)。

2 融合社交關(guān)系與代價(jià)敏感的推薦算法

社交關(guān)系是基于位置社交網(wǎng)絡(luò)環(huán)境下的一個(gè)重要的上下文信息，存在社交關(guān)系的用戶在不斷地相互影響他們之間的興趣偏好。據(jù)此在訓(xùn)練前假設(shè)用戶的興趣愛好完全由社交關(guān)系決定，即用戶A喜歡的興趣點(diǎn)對(duì)于他的朋友用戶B同樣喜歡。在實(shí)際應(yīng)用中，排序列表中不同的位置代表了用戶對(duì)興趣點(diǎn)不同的偏好程度，排名越靠前代表用戶對(duì)于此興趣點(diǎn)的興趣越大，但列表中不同位置興趣點(diǎn)排序出現(xiàn)錯(cuò)誤的代價(jià)不同，用戶往往關(guān)心排序列表前面的興趣點(diǎn)，對(duì)于排序列表靠后的興趣點(diǎn)的關(guān)心程度有一定的下降，代價(jià)敏感學(xué)習(xí)也是基于此原理。

2.1 社交關(guān)系影響

2.1.1 社交相似度計(jì)算

首先采用皮爾森相關(guān)系數(shù)計(jì)算用戶之間的相似度，如公式(6)所示：

sim(u1,u2)=

(6)

2.1.2 信任度計(jì)算

在傳統(tǒng)的社交關(guān)系矩陣Ru1，u2，用戶u1與用戶u2存在社會(huì)關(guān)系，則對(duì)應(yīng)元素值為1，反之為0。社交關(guān)系集合為U{u1,u2|Ru1,u2=1}。

對(duì)于社交關(guān)系集合，本文利用信任度計(jì)算衡量用戶之間的社交關(guān)系遠(yuǎn)近。信任度是由用戶共同簽到數(shù)量與用戶簽到質(zhì)量決定。共同簽到數(shù)量比值T1計(jì)算見公式(7)：

(7)

式中Nu1u2表示用戶u1與用戶u2之間的共同的興趣點(diǎn)數(shù)量。簽到質(zhì)量是具有社交關(guān)系用戶對(duì)于興趣點(diǎn)的頻率與其他用戶對(duì)于此興趣點(diǎn)的簽到頻率之差是否小于一個(gè)閾值δ。簽到質(zhì)量T2計(jì)算見公式(8)和公式(9)：

(8)

式中：Qu1，i表示用戶u1對(duì)興趣點(diǎn)i的簽到頻率;δ表示閾值。

(9)

用戶之間信任度T計(jì)算見公式(10)：

T=T1+T2。

(10)

2.2 代價(jià)敏感打分函數(shù)

融合社交相似度與信任度表示打分函數(shù)中社交關(guān)系的影響，公式如下：

Social_Score(u，i)=sim(u1,u2)·

T(u1,u2)·Uu,i。

(11)

代價(jià)敏感學(xué)習(xí)賦予排序列表中每個(gè)興趣點(diǎn)不同的權(quán)重，計(jì)算排序列表時(shí)為列表中每個(gè)興趣點(diǎn)學(xué)習(xí)權(quán)重αi，權(quán)重αi之和為1且隨著排序列表興趣點(diǎn)位置變化，權(quán)重由前向后不斷降低。將計(jì)算出的社交關(guān)系影響與代價(jià)敏感方法結(jié)合得出打分函數(shù)的計(jì)算見公式(12)：

(12)

式中：L表示興趣點(diǎn)列表的長度；u表示用戶；i表示興趣點(diǎn)。

2.3 改進(jìn)的ListMLE推薦算法

所提推薦算法考慮到用戶信任關(guān)系，將用戶間社交關(guān)系信息作為初始化列表分?jǐn)?shù)的依據(jù)；同時(shí)考慮到列表前后關(guān)注度差異，使用代價(jià)敏感的方式賦予列表中不同位置的興趣點(diǎn)不同的權(quán)重。為提升推薦質(zhì)量，將社交關(guān)系與代價(jià)敏感打分函數(shù)融合到ListMLE算法中，算法偽代碼描述如下：

輸入：用戶-興趣點(diǎn)簽到數(shù)據(jù)，用戶-社交關(guān)系數(shù)據(jù)集，用戶-興趣點(diǎn)-地理位置信息數(shù)據(jù)集。

輸出：TOP-K推薦列表

步驟1 數(shù)據(jù)預(yù)處理，依據(jù)數(shù)據(jù)集為每個(gè)用戶生成一定數(shù)量的推薦列表 。

步驟2 社交關(guān)系影響計(jì)算。通過公式(6)計(jì)算興趣點(diǎn)的相似度。通過公式(7)—公式(10)計(jì)算興趣點(diǎn)之間的信任度，并最終通過公式(11)計(jì)算社交關(guān)系對(duì)每個(gè)用戶每個(gè)興趣點(diǎn)的影響。

步驟3 基于代價(jià)敏感設(shè)置推薦列表中每個(gè)興趣點(diǎn)的權(quán)重，選取不同代價(jià)敏感列表長度，學(xué)習(xí)不同列表興趣點(diǎn)的權(quán)重，依據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選取最優(yōu)參數(shù)作為推薦列表的最終得分

步驟4 將步驟2中得到社交關(guān)系影響與步驟3得到推薦列表長度與權(quán)重融合生成推薦列表分?jǐn)?shù)即公式(12)。

步驟5 將推薦列表與分?jǐn)?shù)輸入神經(jīng)網(wǎng)絡(luò)，依據(jù)公式(4)排序損失函數(shù)利用梯度下降算法計(jì)算更新參數(shù)w，產(chǎn)生推薦結(jié)果。

3 實(shí)驗(yàn)數(shù)據(jù)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)所用數(shù)據(jù)集為Gowalla數(shù)據(jù)集。Gowalla是基于位置的社交網(wǎng)站，在此網(wǎng)站上用戶通過簽到分享位置，數(shù)據(jù)集源自SNAP網(wǎng)站，包括18 737個(gè)用戶對(duì)于32 510個(gè)興趣點(diǎn)的簽到信息。

實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM)i7-6700HQ，2.6 GHZ CPU 24 GB RAM，在Window10系統(tǒng)下采用Python3.6實(shí)現(xiàn)算法，選取PyCharm (Community Edition)作為開發(fā)平臺(tái)。

3.2 實(shí)驗(yàn)對(duì)比

3.2.1 模型與其他模型對(duì)比

實(shí)驗(yàn)選取準(zhǔn)確率、召回率作為算法評(píng)價(jià)標(biāo)準(zhǔn)[11]，比較融合了社交關(guān)系與代價(jià)敏感的改進(jìn)ListMLE、RankGEOFM[12]、ListNet[13]與對(duì)級(jí)排序?qū)W習(xí)方法BPR-MF[14-15]四種算法在Gowalla數(shù)據(jù)集下的評(píng)價(jià)標(biāo)準(zhǔn)的差異，討論分析了融合社交關(guān)系與代價(jià)敏感打分函數(shù)的影響。

1)為探究列表級(jí)排序?qū)W習(xí)方法與對(duì)級(jí)排序方法在興趣點(diǎn)推薦領(lǐng)域中的推薦精度差異， BPR-MF算法特征向量長度為10。四種模型在Gowalla數(shù)據(jù)集下的精度對(duì)比如圖1和2所示。

圖 1 改進(jìn)ListMLE與其他模型在Gowalla數(shù)據(jù)集中準(zhǔn)確度對(duì)比圖Fig.1 Comparison of ListMLE and other models of accuracy in Gowalla dataset

圖 2 改進(jìn)ListMLE與其他模型在Gowalla數(shù)據(jù)集中召回率對(duì)比圖Fig.2 Comparison of ListMLE and other models of recall in Gowalla dataset

2)改進(jìn)ListMLE算法和ListNET算法隨著TOP-K值的變化呈穩(wěn)定下降趨勢(shì)，而BPR-MF算法在TOP-K值為[10,20]之間出現(xiàn)了一定程度的波動(dòng)，驗(yàn)證了列表級(jí)排序?qū)W習(xí)的健壯性和穩(wěn)定性。當(dāng)TOP-K值為5、10、15、20、25時(shí)，改進(jìn)ListMLE算法相比于BPR-MF算法分別提升了18.8%、65.8%、29.7%、34.7%、51.2%。BPR-MF算法是基于對(duì)級(jí)排序?qū)W習(xí)的興趣點(diǎn)推薦方法，訓(xùn)練數(shù)據(jù)是以用戶與兩個(gè)興趣點(diǎn)的偏序關(guān)系對(duì)的形式，通過對(duì)比兩種算法的準(zhǔn)確度，改進(jìn)ListMLE在準(zhǔn)確度上相比BPR-MF算法有明顯的提升，同時(shí)對(duì)比改進(jìn)ListNET算法，RankGEOFM算法和BPR-MF算法，可以看出列表級(jí)的排序?qū)W習(xí)方法在推薦精度上比對(duì)級(jí)的排序?qū)W習(xí)方法在興趣點(diǎn)推薦中有明顯的提升，驗(yàn)證了將訓(xùn)練數(shù)據(jù)以列表的形式輸入更符合實(shí)際的理念和貼近用戶的偏好。此外，通過四種算法召回率的對(duì)比，改進(jìn)的ListMLE算法在召回率上也優(yōu)于其他四種算法。

3.2.2 融合社交關(guān)系與代價(jià)敏感的打分函數(shù)對(duì)比

為驗(yàn)證融合社交關(guān)系的代價(jià)敏感函數(shù)對(duì)于ListMLE算法的影響，設(shè)計(jì)實(shí)驗(yàn)選取Gowalla數(shù)據(jù)集，設(shè)置TOP-K值為5、10、15、20。對(duì)比未加入代價(jià)敏感權(quán)重的ListMLE算法與加入代價(jià)敏感權(quán)重的ListMLE算法的準(zhǔn)確度，實(shí)驗(yàn)結(jié)果見圖3。有代價(jià)敏感的ListMLE算法在準(zhǔn)確度上相對(duì)于沒有加入代價(jià)敏感學(xué)習(xí)的ListMLE算法分別提升了16.3%、15.2%、12.5%、14.5%。在準(zhǔn)確度的對(duì)比下，代價(jià)敏感學(xué)習(xí)對(duì)于推薦結(jié)果有較為顯著的提升，驗(yàn)證了代價(jià)敏感學(xué)習(xí)的意義，即用戶往往對(duì)于排序列表前面的興趣點(diǎn)更為看重，對(duì)于排序列表后面的興趣點(diǎn)的關(guān)注程度會(huì)有一定的下降。

圖 3 代價(jià)敏感函數(shù)與非代價(jià)敏感函數(shù)準(zhǔn)確度對(duì)比Fig. 3 Comparison of cost-sensitive function and non-cost-sensitive function in precision

3.2.3 代價(jià)敏感的排序列表長度

圖4表示在Gowalla數(shù)據(jù)集下改進(jìn)ListMLE算法在不同的興趣點(diǎn)列表長度下的準(zhǔn)確度和召回率。首先選取實(shí)驗(yàn)區(qū)間[4,12]，設(shè)置步長變化為1，改進(jìn)ListMLE算法的準(zhǔn)確度在權(quán)重賦值列表長度為6時(shí)取得最優(yōu)值0.071，召回率取得最優(yōu)值0.042，在4時(shí)準(zhǔn)確度取得次優(yōu)值0.068，召回率為0.04，之后呈現(xiàn)不斷下降趨勢(shì)。由圖4可以看出，用戶對(duì)于排序列表的重視僅限于排序列表中的頭部位置，隨著列表長度的增加，用戶對(duì)于興趣點(diǎn)的重視也在不斷下降，側(cè)面反映了用戶的偏好，也驗(yàn)證了代價(jià)敏感的思想的有效性。

實(shí)驗(yàn)表明在代價(jià)敏感函數(shù)中，將興趣點(diǎn)列表的長度設(shè)置為6時(shí)，ListMLE算法的推薦精度達(dá)到最優(yōu)。

圖4 代價(jià)敏感列表長度Fig.4 Length of list with cost-sensitive

4 結(jié)束語

為緩解興趣點(diǎn)推薦過程中的數(shù)據(jù)稀疏問題，進(jìn)一步提高推薦精度，提出一種融合代價(jià)敏感與社交關(guān)系的改進(jìn)ListMLE推薦算法。針對(duì)ListMLE算法中打分函數(shù)不能很好地?cái)M合用戶興趣偏好問題，提出了融合社交信任的方式作為打分函數(shù)的依據(jù)，并依據(jù)用戶對(duì)于推薦列表的不同位置存在不同的關(guān)注程度，將代價(jià)敏感學(xué)習(xí)融入打分函數(shù)，生成基于社交信任與代價(jià)敏感的打分函數(shù)應(yīng)用到興趣點(diǎn)推薦過程中。實(shí)驗(yàn)結(jié)果證明，改進(jìn)的ListMLE算法在興趣點(diǎn)推薦領(lǐng)域中不同數(shù)據(jù)集下的準(zhǔn)確度和召回率優(yōu)于基線算法。

未來將嘗試對(duì)多種上下文信息融合展開深入研究，并使用深度學(xué)習(xí)模型與算法結(jié)合，以進(jìn)一步提高推薦性能。