LBSN中基于聚類的二分圖網(wǎng)絡(luò)推薦算法

賀開明　王賾

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

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

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

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

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

1? 相關(guān)工作

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

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

2? 基于用戶聚類的二分圖興趣點推薦

2.1 基本定義

在LBSN中，u是用戶集合U中的一個用戶，l是興趣點集合L中的一個興趣點，cui=1表示用戶簽到過（或者是訪問過）興趣點l，cui=0表示沒有簽到。t是時間集合T中的一個時間段，可以劃分為幾個連續(xù)時間的時間段，以時間段作為時間單位。因為在實際生活中，很少有用戶在一天的0：00到6：00這個時間段有簽到活動，所以該文只考慮從6點開始到晚上24：00的這段時間。

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

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

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

2.2 用戶聚類

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

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

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

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

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

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

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

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

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

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

（4）

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

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

（5）

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

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

2.4 聯(lián)合推薦

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

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

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

3? 實驗與分析

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

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

3.2 評價指標(biāo)

在興趣點推薦問題中，一般采用準(zhǔn)確率（precision）和召回率（recall）來評價算法的推薦效果。在該文中先要計算每個時間段的準(zhǔn)確率和召回率，計算公式如下：

（7）

（8）

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

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

（9）

（10）

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

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

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

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

4? 結(jié)語

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

參考文獻(xiàn)

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

[2] 高榕，李晶，杜博，等.一種融合情景和評論信息的位置社交網(wǎng)絡(luò)興趣點推薦模型[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è)大學(xué)學(xué)報，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ò)散的個性化推薦算法研究[D].北京郵電大學(xué)，2018.