賀開明　王賾

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

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

中圖分類號：TP391.3 ? ?文獻標識碼：A 文章編號：1672-3791（2019）12（a）-0018-02

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

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

1? 相關工作

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

有學者研究表明聚類方法可以降低推薦算法的計算復雜度[4]，同時有研究表明用戶簽到的興趣點類型與時間有一定的關聯(lián)度[5]，利用二分圖網(wǎng)絡模型的相關算法[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）和用戶之間本身存在的好友關系trust（u，v）結合起來由α平衡兩者的權重影響從而計算得到的：

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

其中

（2）

trust（u，v）是用戶之間的好友關系值

，u和v是好友關系? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

，u和v不是好友關系

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

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

2.2 用戶聚類

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

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

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

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

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

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

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

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

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

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

（4）

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

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

（5）

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

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

2.4 聯(lián)合推薦

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

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

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

3? 實驗與分析

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

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

3.2 評價指標

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

（7）

（8）

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

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

（9）

（10）

3.3 實驗結果與分析

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

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

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

4? 結語

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

參考文獻

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

[2] 高榕，李晶，杜博，等.一種融合情景和評論信息的位置社交網(wǎng)絡興趣點推薦模型[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)絡協(xié)同推薦算法[J].沈陽工業(yè)大學學報，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] 陳桂林.基于物質擴散的個性化推薦算法研究[D].北京郵電大學，2018.