基于區(qū)域活躍用戶的好友推薦和位置推薦算法

董立巖, 王雪松, 王朝陽, 李永麗

(1. 吉林大學 計算機科學與技術學院, 長春 130012； 2. 東北師范大學 信息科學與技術學院, 長春 130117)

定位技術使用戶可隨時通過移動便攜互聯(lián)網(wǎng)設備分享其活動的地理位置, 使基于位置的社交網(wǎng)絡[1-2]推薦成為目前該領域的研究熱點, 其中包括基于好友用戶的推薦[3-4]和基于專家用戶的推薦[5]等.

社交網(wǎng)絡中好友的推薦研究目前已有很多結果[6-12]. Wu等[9]將在線友誼信息和離線用戶行為考慮到好友推薦中, 采用Markov鏈基于位置聚類和閾值評估的余弦相似理論方法進行推薦; Lin等[10]提出了一種基于3種傳統(tǒng)朋友關系的線性框架提高推薦的準確性.

專家用戶即為在社交網(wǎng)絡中擁有較大影響力的用戶. 專家用戶擁有豐富的經(jīng)驗, 可給出相對普通用戶更準確的評價, 專家用戶更易獲取其他用戶的信任, 專家用戶簽到的位置也更值得推薦. 但專家用戶的尋找范圍可能相對過大, 傳統(tǒng)算法中專家用戶的范圍一般為全國范圍內, 這樣的范圍對于普通用戶不具有普遍性. 普通用戶的活動可能只集中在10 km或5 km為直徑的范圍內, 距離因素對推薦具有重要影響[6]. 本文提出一種基于區(qū)域活躍用戶的推薦算法, 將區(qū)域活躍用戶作為推薦標準, 為普通用戶推薦, 更符合用戶的要求.

1 區(qū)域活躍用戶定義

本文推薦算法使用區(qū)域活躍用戶(一種專家用戶)作為推薦標準. 通過專家用戶的位置信息和時間信息, 先計算給定區(qū)域內的區(qū)域活躍用戶, 再將得到的區(qū)域活躍用戶推薦給普通用戶, 同時計算用戶間的相似度為目標用戶進行好友推薦. 獲取區(qū)域活躍用戶后, 根據(jù)區(qū)域活躍用戶的簽到記錄, 為用戶推薦價值高的位置.

1.1 區(qū)域活躍用戶度量標準

區(qū)域活躍用戶是指在特定區(qū)域內社交活動頻繁、 簽到頻率高并頻繁分享個人體驗的專家用戶. 區(qū)域活躍用戶在一定程度上對該區(qū)域的興趣點及項目了解程度較高, 相應排名靠前. 用戶的活躍程度評判標準根據(jù)用戶的簽到數(shù)據(jù)衡量, 主要分為兩方面： 1) 用戶在區(qū)域內的簽到地點數(shù)目[7], 若用戶在特定區(qū)域內的簽到較少, 則一定程度上可認定該用戶為非區(qū)域活躍用戶, 且推薦價值較低； 2) 用戶的總簽到次數(shù), 部分用戶進行特定活動時, 簽到地點可能會很多, 但總簽到次數(shù)少, 這種情況可認定用戶為非區(qū)域活躍用戶. 簽到數(shù)據(jù)體現(xiàn)了用戶在社交網(wǎng)絡中的活躍程度, 簽到地點和數(shù)量多說明用戶在特定區(qū)域活躍度高, 其推薦價值高. 故本文采用用戶簽到數(shù)據(jù)中的簽到地點數(shù)目和簽到總次數(shù)兩個標準對用戶進行評審, 判斷其是否為區(qū)域活躍用戶[8].

1.2 區(qū)域活躍用戶計算過程

本文根據(jù)簽到數(shù)據(jù)集, 通過用戶簽到地點數(shù)和用戶的簽到總次數(shù)進行區(qū)域活躍用戶計算, 步驟如下:

1) 獲取用戶當前位置, 并以用戶簽到地點的經(jīng)度和緯度進行位置展示, 根據(jù)用戶當前位置確定需要進行計算的區(qū)域. 獲取以用戶位置為圓心、R為半徑圓的范圍內所有簽到數(shù)據(jù). 將得到的區(qū)域數(shù)據(jù)集記為RDS(region data set). 該步驟確定區(qū)域, 并獲取區(qū)域內的所有簽到數(shù)據(jù).

2) 根據(jù)步驟1)獲得的部分簽到數(shù)據(jù)集, 對數(shù)據(jù)集中的每個用戶進行簽到地點數(shù)的計算, 以獲得用戶在該區(qū)域內進行過簽到的所有地點, 計算公式為

(1)

其中：L表示地點集合,L∈RDS;cu,i表示用戶u在地點i的簽到記錄;I為指示函數(shù), 若用戶在i位置有簽到記錄, 則I=1, 否則I=0. 最后得到在區(qū)域內用戶簽到地點數(shù)的集合.

3) 根據(jù)步驟1)獲得的部分簽到數(shù)據(jù)集, 計算數(shù)據(jù)集中每個用戶在該區(qū)域內的簽到總次數(shù). 計算區(qū)域內每個用戶在區(qū)域地點簽到次數(shù)的總和, 計算公式為

(2)

其中:L表示地點集合,L∈RDS;cu,j表示用戶u在地點i的簽到記錄, 用戶的所有簽到記錄全部計算. 在該過程中根據(jù)用戶所在區(qū)域的簽到總次數(shù)進行排序, 得到每個用戶在區(qū)域L內的簽到總次數(shù). 計算結果反應了用戶對區(qū)域了解的廣度.

4) 將上述步驟中得到的基于簽到地點數(shù)的用戶排序與基于簽到總數(shù)的用戶排序, 分別選取top-N簽到地點數(shù)的用戶和top-N簽到總數(shù)的用戶, 求得兩個用戶集的交集, 得到區(qū)域活躍用戶集, 根據(jù)區(qū)域活躍用戶集進行推薦. 這里定義區(qū)域活躍用戶集為raus(regional active user set).

2 基于區(qū)域活躍用戶的推薦方法

2.1 用戶的好友推薦方法

若用戶在所屬社交網(wǎng)絡中屬于新用戶, 則可將對于區(qū)域了解程度最高的專家用戶推薦給新用戶, 而這些區(qū)域了解程度高的專家用戶即為本文提出的區(qū)域活躍用戶. 根據(jù)計算得到的區(qū)域活躍用戶集raus, 將集合用戶中的top-N活躍用戶推薦給目標用戶. 而該top-N活躍用戶的選取方式也分為基于用戶總簽到數(shù)和用戶簽到地點數(shù)兩種.

若用戶在所屬社交網(wǎng)絡中為老用戶, 則該用戶有一定的簽到記錄, 在為老用戶進行好友推薦時, 此時用戶的簽到信息在一定程度上也反映了用戶的喜好[13-14]. 本文根據(jù)計算區(qū)域活躍用戶與目標用戶之間的相似度進行度量, 通過簽到位置的相似度判斷是否進行好友推薦, 若兩個用戶在區(qū)域內具有較多共同的簽到記錄, 則表明用戶的相似度高, 相似度計算公式為

(3)

2.2 基于區(qū)域活躍用戶的位置推薦

位置推薦[15]分為兩種形式: 1) 用戶簽到數(shù)據(jù)少甚至無數(shù)據(jù), 此時屬于冷啟動類型[16], 將區(qū)域活躍用戶簽到頻繁的位置推薦給用戶； 2) 對具有一定簽到數(shù)據(jù)的用戶進行推薦, 通過計算用戶之間的相似度[17], 尋找出與用戶相似度最高的區(qū)域活躍用戶, 將該區(qū)域活躍用戶簽到過但目標用戶未進行簽到的地點推薦給目標用戶. 在位置推薦時, 推薦的衡量標準也分為兩種： 基于位置的被簽到總次數(shù)和基于位置的被簽到總人次.

基于區(qū)域活躍用戶簽到數(shù)推薦方法的計算公式為

(4)

其中：Uraus表示區(qū)域活躍用戶集；L∈RDS;cu,i表示用戶u在位置i的簽到記錄. 計算在選定區(qū)域內, 所有區(qū)域活躍用戶在需要進行推薦位置的簽到總數(shù). 基于區(qū)域活躍用戶簽到人次推薦方法的計算公式為

(5)

對于不同的目標用戶, 其衡量接受推薦的標準可能不同, 被簽到次數(shù)與總簽到人次均可作為標準. 綜合考慮兩種標準得到綜合推薦方法, 記為

raus(uk,li)=α·rauscc(uk,li)+(1-α)·rauslc(uk,li).

(6)

時間因素[18]對推薦的準確性具有重要影響. 加入時間因素, 只考慮簽到時間與用戶當前時間差值在一定范圍內的簽到, 若超出該時間差值范圍, 則將不考慮該簽到記錄. 加入時間因素基于位置被簽到總數(shù)推薦方法的計算公式為

(7)

其中：t表示用戶進行推薦的時間；tu表示數(shù)據(jù)集中用戶的簽到時間, 本文假設該時間的選擇只考慮24 h內的時間劃分.

同理, 加入時間因素基于位置被簽到人次推薦方法的計算公式為

(8)

最終得到加入時間因素的綜合推薦算法為

raus(uk,li)=α·rauscct(uk,li)+(1-α)·rauslct(uk,li).

(9)

3 實 驗

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

本文的數(shù)據(jù)集源于Gowalla數(shù)據(jù)集, 收集了用戶在2009-02--2010-10期間的簽到數(shù)據(jù), 包含6 442 890條簽到數(shù)據(jù), 其中有196 591個節(jié)點, 950 327條邊. 節(jié)點表示用戶, 邊表示用戶之間的好友關系. Gowalla數(shù)據(jù)集中包含兩個文本文件： Gowalla_edges.txt和Gowalla_totalCheckins.txt. 其中Gowalla_edges.txt文件中記錄了用戶的好友關系, Gowalla_totalCheckins.txt文件中記錄了用戶的簽到信息.

3.2 實驗結果與分析

實驗通過給定用戶的經(jīng)度和緯度及選定區(qū)域的半徑大小獲取該區(qū)域內的推薦位置, 選取

lat=30.255 730 992 7, lon=-97.763 385 772 7

為用戶當前位置, 設定不同區(qū)域半徑R. 當R=10 000時, 得到了基于位置簽到總數(shù)的推薦概率排名前20的位置以及基于位置簽到人次的推薦概率排名前20的位置, 結果分別列于表1和表2.

表1 基于位置被簽到總次數(shù)的推薦概率Table 1 Recommendation probability based on total number of places checked in

表2 基于地點被簽到總人次的推薦概率Table 2 Recommendation probability of total number of people based on location checked in

由表1可見, 位置ID為420315的位置被簽到次數(shù)最多. 由表2可見, 位置ID為9241的簽到總人次數(shù)最多. 兩種不同推薦結果表明, 不同的推薦方式得到的推薦結果不相同. 設α=0.4, 由式(9)可得列于表3的最終推薦結果.

表3 綜合推薦概率Table 3 Comprehensive recommendation probability

圖1 不同N值的精確率比較Fig.1 Comparison of precision rates with different N values

由表3可見, 當同時考慮位置的被簽到總次數(shù)和簽到人次時, 得到的推薦結果與只考慮某一條件的實驗結果存在較大差異, 證明了本文提出綜合考慮兩個因素的正確性, 當α=0.4時, 推薦結果較好.

下面將本文推薦方法與目前已有經(jīng)典的位置推薦算法進行比較, 以證明本文算法的有效性. 不同算法的實驗對比結果如圖1～圖3所示. 進行比較的算法如下：

1) USG算法[19], 基于用戶偏好、 社會關系、 地理位置的推薦算法, 是目前被廣泛應用的推薦方法；

2) UP算法, 根據(jù)用戶歷史簽到數(shù)據(jù)中獲取用戶愛好的推薦算法;

3) FB算法, 基于社會關系的推薦算法.

圖2 不同N值的召回率比較Fig.2 Comparison of recall rates with different N values

圖3 不同N值的F-measure值比較Fig.3 Comparison of F-measure values with different N values

由圖1～圖3可見, 本文提出的基于區(qū)域活躍用戶的位置推薦算法相比于其他傳統(tǒng)推薦算法的精確率、 召回率和F-measure值均有一定的提高.

綜上所述, 本文提出了一種新的推薦機制——基于區(qū)域活躍用戶的推薦方法, 根據(jù)用戶的位置信息和時間信息進行位置推薦及好友推薦使推薦更具實時性. 首先考慮用戶尋求推薦所在位置, 計算出該區(qū)域中的活躍用戶, 然后將這些活躍用戶推薦給其他用戶, 可最大程度地完成相應推薦. 在基于區(qū)域活躍用戶的基礎上, 添加時間因素. 推薦標準變?yōu)榛诤灥娇偞螖?shù)與基于簽到總人數(shù)相融合. 兩種標準在深度和廣度上進行推薦, 可選擇相應權重決定對應標準所占百分數(shù). 最后在真實簽到數(shù)據(jù)集Gowall上進行實驗. 實驗結果表明, 本文提出的將位置的被簽到總次數(shù)與位置的被簽到人次相融合更合理, 同時算法在準確率、 召回率、F-measure值上均有一定提高.