賀開(kāi)明　王賾

摘? 要：興趣點(diǎn)推薦是基于位置的社交網(wǎng)絡(luò)（Location Based Social Network，LBSN）的重要服務(wù)，近年來(lái)關(guān)于興趣點(diǎn)推薦的算法深受學(xué)者關(guān)注，然而由于多方面的原因，許多推薦算法仍存在一些不足。該文提出的是在用戶聚類的基礎(chǔ)上利用二分圖網(wǎng)絡(luò)進(jìn)行推薦的算法。實(shí)驗(yàn)表明，該算法取得了比較良好的推薦效果。

關(guān)鍵詞：基于位置的社交網(wǎng)絡(luò)? 聚類? 二分圖網(wǎng)絡(luò)? 興趣點(diǎn)推薦

中圖分類號(hào)：TP391.3 ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2019）12（a）-0018-02

近年來(lái)隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展， 基于位置的社交網(wǎng)絡(luò)（Location Based Social Network，LBSN）也得到迅猛發(fā)展[1]，如Foursquare、Gowalla、微博等，與傳統(tǒng)社交網(wǎng)絡(luò)最大的區(qū)別就是有了地理位置信息，用戶可以對(duì)自己訪問(wèn)過(guò)的興趣點(diǎn)進(jìn)行簽到，并且可以隨時(shí)分享給好友。LBSN的服務(wù)宗旨就是要為用戶推薦一些新興趣點(diǎn)，幫助用戶更好地發(fā)現(xiàn)生活樂(lè)趣，同時(shí)還能促進(jìn)興趣點(diǎn)相關(guān)的商業(yè)發(fā)展，具有重要的意義。

個(gè)性化的推薦技術(shù)在不同應(yīng)用領(lǐng)域也受到廣泛關(guān)注，然而用戶面對(duì)生活中龐大的信息量做選擇時(shí)還是有些迷茫，用戶所想要的是可以根據(jù)其所處的狀態(tài)信息給出一些個(gè)性化的興趣點(diǎn)推薦，但是LBSN中的簽到密度通常較為稀疏，給興趣點(diǎn)推薦帶來(lái)了困難。因此興趣點(diǎn)推薦的研究仍需要進(jìn)一步探索。

1? 相關(guān)工作

基于位置的社交網(wǎng)絡(luò)推薦技術(shù)發(fā)展至今已經(jīng)有了不少進(jìn)展。高榕等人[2]在矩陣分解的基礎(chǔ)上利用興趣點(diǎn)的評(píng)論信息、用戶社會(huì)關(guān)系以及地理信息這3種因素推薦興趣點(diǎn)。LIU等人認(rèn)為用戶屬性、興趣點(diǎn)屬性以及興趣點(diǎn)間距離共同決定著用戶評(píng)分，因此構(gòu)建了貝葉斯圖模型給用戶推薦他們可能喜歡的興趣點(diǎn)[3]。以上的這些研究整體上來(lái)說(shuō)都是在所有用戶簽到信息的基礎(chǔ)上利用各種簽到信息進(jìn)行推薦。

有學(xué)者研究表明聚類方法可以降低推薦算法的計(jì)算復(fù)雜度[4]，同時(shí)有研究表明用戶簽到的興趣點(diǎn)類型與時(shí)間有一定的關(guān)聯(lián)度[5]，利用二分圖網(wǎng)絡(luò)模型的相關(guān)算法[6]可以很好地把簽到信息中的用戶、興趣點(diǎn)、時(shí)間這3個(gè)重要信息很好地聯(lián)合起來(lái)，對(duì)于研究在特定時(shí)間給用戶推薦興趣點(diǎn)有重要意義。

2? 基于用戶聚類的二分圖興趣點(diǎn)推薦

2.1 基本定義

在LBSN中，u是用戶集合U中的一個(gè)用戶，l是興趣點(diǎn)集合L中的一個(gè)興趣點(diǎn)，cui=1表示用戶簽到過(guò)（或者是訪問(wèn)過(guò)）興趣點(diǎn)l，cui=0表示沒(méi)有簽到。t是時(shí)間集合T中的一個(gè)時(shí)間段，可以劃分為幾個(gè)連續(xù)時(shí)間的時(shí)間段，以時(shí)間段作為時(shí)間單位。因?yàn)樵趯?shí)際生活中，很少有用戶在一天的0：00到6：00這個(gè)時(shí)間段有簽到活動(dòng)，所以該文只考慮從6點(diǎn)開(kāi)始到晚上24：00的這段時(shí)間。

定義1? 用戶相似度：用戶相似度是由常用的余弦相似度cos（u，v）和用戶之間本身存在的好友關(guān)系trust（u，v）結(jié)合起來(lái)由α平衡兩者的權(quán)重影響從而計(jì)算得到的：

Sim（u，v）=α*trust（u，v）+（1-α）*cos（u，v）? ? ? ? ? ? ? ? ? ? ? ? （1）

其中

（2）

trust（u，v）是用戶之間的好友關(guān)系值

，u和v是好友關(guān)系? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

，u和v不是好友關(guān)系

定義2? 用戶-興趣點(diǎn)二分圖網(wǎng)絡(luò)：令G（U，L，E）表示一個(gè)二分圖網(wǎng)絡(luò)，其中U代表用戶節(jié)點(diǎn)集，L為興趣點(diǎn)節(jié)點(diǎn)集，E為用戶-興趣點(diǎn)二分圖邊集，每一條邊表示用戶簽到過(guò)此興趣點(diǎn)。假設(shè)用戶節(jié)點(diǎn)數(shù)|U|=m，興趣點(diǎn)節(jié)點(diǎn)數(shù)|L|=n，則節(jié)點(diǎn)總數(shù)為r=m+n。

定義3? 時(shí)間-興趣點(diǎn)二分圖網(wǎng)絡(luò)：令G（T，L，E）表示一個(gè)二分圖網(wǎng)絡(luò)，其中T代表時(shí)間節(jié)點(diǎn)集，L為興趣點(diǎn)節(jié)點(diǎn)集，E為時(shí)間-興趣點(diǎn)二分圖邊集，每一條邊表示在該時(shí)間段有用戶簽到過(guò)此興趣點(diǎn)。

2.2 用戶聚類

為了提高推薦結(jié)果國(guó)的有效性和準(zhǔn)確性，首先需要用戶聚類，從中找出聚類結(jié)果中的有用信息，為下一步的聯(lián)合推薦奠定基礎(chǔ)。為了保證比較好的聚類結(jié)果，我們借鑒k-means算法的思想，提出了比較有效的聚類算法。該聚類算法的具體步驟如下。

（1）基于定義1計(jì)算出來(lái)的用戶相似度，按照從大到小選出和其他用戶相似度總和處于前p位的用戶作為用戶聚類中心。

（2）利用用戶相似度判斷每個(gè)用戶與哪個(gè)中心用戶的相似度最大，然后就可以把除用戶聚類中心以外的所有用戶加入到與它有最大相似度的中心用戶中。

（3）直到所有用戶都加入到對(duì)應(yīng)的用戶聚類中心時(shí)算法終止，所有用戶成功聚類到p個(gè)用戶群體中。

2.3 基于二分圖網(wǎng)絡(luò)物質(zhì)擴(kuò)散的推薦

在二分圖中基于物質(zhì)擴(kuò)散的推薦算法相當(dāng)于傳統(tǒng)推薦中的隨機(jī)游走算法，它將視野匯聚在那些較流行的節(jié)點(diǎn)上， 傾向于推薦較流行的物品，從而提高推薦的精確性。圖1是一個(gè)典型的二分圖網(wǎng)絡(luò)。該文中用到了定義2和定義3的兩個(gè)二分圖。

下面我們以用戶-興趣點(diǎn)二分圖網(wǎng)絡(luò)為例描述對(duì)應(yīng)的物質(zhì)擴(kuò)散推薦算法：

定義用戶節(jié)點(diǎn)集U={0，1，2，…，m-1};興趣點(diǎn)節(jié)點(diǎn)集L={0，1，2，…，n-1}。物質(zhì)擴(kuò)散算法在整個(gè)傳遞過(guò)程中，每個(gè)節(jié)點(diǎn)的資源都是通過(guò)二分圖中的邊均勻傳遞，總資源始終不變。算法可以分為以下三步。

（1）對(duì)目標(biāo)用戶簽到過(guò)的興趣點(diǎn)節(jié)點(diǎn)賦予一個(gè)初始的資源αul=cl=1，否則αul=cl=0。

（2）興趣點(diǎn)節(jié)點(diǎn)資源通過(guò)二分圖中的連邊均勻地分配到所有簽到過(guò)該興趣點(diǎn)的用戶節(jié)點(diǎn)。用戶節(jié)點(diǎn)對(duì)從不同興趣點(diǎn)得到的資源值進(jìn)行累加，從而求得用戶u得到的資源值bu。

（4）

k（Ol）為二分圖中興趣點(diǎn)節(jié)點(diǎn)l的度。

（3）所有用戶的資源值也將通過(guò)二分圖中的連邊均勻地分配到他們簽到過(guò)的興趣點(diǎn)節(jié)點(diǎn)。興趣點(diǎn)節(jié)點(diǎn)對(duì)從不同用戶得到的資源值進(jìn)行累加，從而求得興趣點(diǎn)l得到的資源值：

（5）

k（Ou）為二分圖中用戶節(jié)點(diǎn)u的度。

在給定目標(biāo)用戶的情況下，通過(guò)上面的算法就可以求得所有興趣點(diǎn)節(jié)點(diǎn)的資源值。同理，在時(shí)間-興趣點(diǎn)二分圖網(wǎng)絡(luò)中，我們也可以在給定時(shí)間的情況下，利用物質(zhì)擴(kuò)散算法求出所有興趣點(diǎn)節(jié)點(diǎn)的資源值c''l。

2.4 聯(lián)合推薦

給定用戶u和時(shí)間t，然后給用戶u推薦他感興趣的興趣點(diǎn)。我們利用用戶-興趣點(diǎn)、時(shí)間-興趣點(diǎn)二分圖網(wǎng)絡(luò)分別通過(guò)物質(zhì)擴(kuò)散算法得到目標(biāo)用戶相應(yīng)的興趣點(diǎn)資源值c'l和時(shí)間段相應(yīng)的興趣點(diǎn)資源值c''l。為了進(jìn)一步提高推薦的準(zhǔn)確性，因此我們通過(guò)引入的可調(diào)節(jié)參數(shù)λ∈[0，1]調(diào)節(jié)這兩個(gè)網(wǎng)絡(luò)的影響權(quán)重：

cl=λc'l+（1-λ）c''l? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

然后按照興趣點(diǎn)資源值cl的大小降序排列，選取前top-k個(gè)未簽到過(guò)的興趣點(diǎn)推薦給目標(biāo)用戶u。

3? 實(shí)驗(yàn)與分析

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

該文實(shí)驗(yàn)所用的數(shù)據(jù)集是Gowalla公開(kāi)數(shù)據(jù)集，此數(shù)據(jù)集中每條簽到記錄提供的信息有用戶ID、興趣點(diǎn)ID、簽到興趣點(diǎn)的經(jīng)緯度坐標(biāo)以及簽到時(shí)間，此數(shù)據(jù)集總共包含6442882條用戶簽到記錄。在該文中對(duì)該數(shù)據(jù)集經(jīng)過(guò)預(yù)處理后，得到了包含18737個(gè)用戶對(duì)32510個(gè)興趣點(diǎn)的總共1278274條簽到記錄，所有的簽到記錄按從6點(diǎn)開(kāi)始到晚上24點(diǎn)按每6個(gè)小時(shí)劃分一個(gè)時(shí)間段，總共劃分3個(gè)時(shí)間段。整個(gè)數(shù)據(jù)集按簽到時(shí)間順序選取了70%的數(shù)據(jù)作為訓(xùn)練集，剩下的30%作為測(cè)試集。

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

在興趣點(diǎn)推薦問(wèn)題中，一般采用準(zhǔn)確率（precision）和召回率（recall）來(lái)評(píng)價(jià)算法的推薦效果。在該文中先要計(jì)算每個(gè)時(shí)間段的準(zhǔn)確率和召回率，計(jì)算公式如下：

（7）

（8）

其中R（ut）是算法給用戶u在t時(shí)間推薦的興趣點(diǎn)結(jié)果，F(xiàn)（ut）是測(cè)試集中戶u在t時(shí)間真實(shí)簽到的興趣點(diǎn)結(jié)果。

接下來(lái)可以通過(guò)求所有時(shí)間段準(zhǔn)確率和召回率的平均值得出整體的準(zhǔn)確率和召回率，計(jì)算公式如下：

（9）

（10）

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

該文算法的所有的實(shí)驗(yàn)都是取p=3個(gè)用戶聚類中心開(kāi)始的，在得到用戶的聚類結(jié)果后開(kāi)始給聚類結(jié)果中的每個(gè)用戶進(jìn)行推薦。首先評(píng)估了公式（6）中λ參數(shù)對(duì)推薦結(jié)果的影響，從中得出參數(shù)λ取值0.7時(shí)推薦效果最好。

接下來(lái)把該文的推薦算法與包含時(shí)間信息的協(xié)同過(guò)濾方法（CF-T）進(jìn)行對(duì)比和分析，此次對(duì)比實(shí)驗(yàn)中我們的算法對(duì)公式（6）中的參數(shù)λ取值0.7，以便實(shí)驗(yàn)效果達(dá)到最佳。此次對(duì)比實(shí)驗(yàn)針對(duì)的同一數(shù)據(jù)集，推薦興趣點(diǎn)個(gè)數(shù)k分別取值5、10、15、20這4種情況，就這兩種推薦算法的準(zhǔn)確率和召回率進(jìn)行對(duì)比（見(jiàn)圖2、圖3）。

實(shí)驗(yàn)結(jié)果顯示，隨著推薦興趣點(diǎn)個(gè)數(shù)k的增長(zhǎng)，兩種算法的準(zhǔn)確率（precision）開(kāi)始降低，召回率（recall）逐漸升高，符合預(yù)期的實(shí)驗(yàn)效果。同時(shí)也可以看到該文提出的基于聚類的二分圖網(wǎng)絡(luò)推薦算法不管在準(zhǔn)確率還是召回率方面都明顯優(yōu)于CF-T推薦算法。

4? 結(jié)語(yǔ)

該文首先通過(guò)引入聚類算法對(duì)用戶聚類，降低了與目標(biāo)用戶不想似的其他用戶對(duì)推薦結(jié)果的干擾，之后在用戶、興趣點(diǎn)、時(shí)間構(gòu)成的兩個(gè)二分圖網(wǎng)絡(luò)利用物質(zhì)擴(kuò)散算法進(jìn)行聯(lián)合推薦，實(shí)驗(yàn)結(jié)果表明該文算法取得了預(yù)期效果，但是如果能考慮興趣點(diǎn)種類、用戶性別等因素，將更有利于實(shí)現(xiàn)個(gè)性化的推薦，提高推薦效果。

參考文獻(xiàn)

[1] Zheng Y，Zhou X.Computing with Spatial Trajectories[M]. Springer New York，2011：243-276.

[2] 高榕，李晶，杜博，等.一種融合情景和評(píng)論信息的位置社交網(wǎng)絡(luò)興趣點(diǎn)推薦模型[J].計(jì)算機(jī)研究與發(fā)展，2016，53（4）：752-763.

[3] Liu B，F(xiàn)u Y，Yao Z，et al. Learning geographical preferences for point-of-interest recommendation[A].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining[C].2013：1043-1051.

[4] 鄭懷宇.基于用戶聚類的二分圖網(wǎng)絡(luò)協(xié)同推薦算法[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2018，40（3）：316-321.

[5] Yuan Q，Cong G，Ma Z，et al.Time-aware point-of-interest recommendation[A].International Acm Sigir Conference on Research & Development in Information Retrieval.ACM[C].2013：363-372.

[6] 陳桂林.基于物質(zhì)擴(kuò)散的個(gè)性化推薦算法研究[D].北京郵電大學(xué)，2018.