位置社交網(wǎng)絡(luò)的潛在好友推薦模型研究*

孫曉晨，徐雅斌,2

（1.北京信息科技大學(xué)計算機學(xué)院 北京 100101；2.網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點實驗室 北京 100101）

1 引言

位置服務(wù)（location-based service，LBS）又稱定位服務(wù)，是通過GPS（global positioning system，全球定位系統(tǒng)）、WLAN（wireless local area network，無線局域網(wǎng)）等技術(shù)獲得移動終端的位置信息（如經(jīng)緯度坐標數(shù)據(jù)），并將這些位置信息提供給移動通信用戶及通信系統(tǒng)，實現(xiàn)各種與位置相關(guān)的業(yè)務(wù)。位置服務(wù)與傳統(tǒng)在線社交網(wǎng)絡(luò)逐漸融合，從而產(chǎn)生了位置社交網(wǎng)站 （location-based online social network，LBSN）。國 外 典 型 的LBSN主 要 有Foursquare、Geolife等，國內(nèi)發(fā)展比較好的LBSN主要有街旁、陌陌等。隨著位置服務(wù)的廣泛應(yīng)用，傳統(tǒng)在線社交網(wǎng)絡(luò)也開始引入位置服務(wù)，如微博的“微領(lǐng)地”應(yīng)用。

位置社交網(wǎng)絡(luò)不僅可以像傳統(tǒng)在線社交網(wǎng)絡(luò)那樣分享博客、照片、視頻進行信息交互，而且可以隨時隨地地定位和分享位置信息[1]。用戶可以通過電腦、手機及其他移動終端進行簽到，并將所處的位置信息及時告訴他的朋友。當簽到信息發(fā)生變化時，用戶能通過社交網(wǎng)站進行同步更新，這樣就可以方便快捷地與好友分享自己的最新動態(tài)。

位置社交網(wǎng)絡(luò)的意義在于分享與位置相關(guān)的內(nèi)容，并借此結(jié)識朋友。因此，通過研究和分析位置社交網(wǎng)絡(luò)中與位置相關(guān)的歷史數(shù)據(jù)及用戶個人興趣信息，并建立位置社交網(wǎng)絡(luò)的潛在好友推薦模型，就可以為用戶推薦一些與他們行為、興趣相似的好友，從而幫助用戶結(jié)識更多在實際生活中未曾見面但卻與自己興趣相投的其他用戶，從而更好地發(fā)展自己的社交圈。同時，為用戶推薦潛在好友，使用戶體會到社交網(wǎng)絡(luò)應(yīng)用的方便性，從而活躍于社交網(wǎng)絡(luò)中，有助于位置社交網(wǎng)絡(luò)的健康發(fā)展。

2 相關(guān)工作

迄今為止，國內(nèi)外學(xué)者在用戶推薦服務(wù)方面做了大量工作。參考文獻[2]中根據(jù)好友的好友進行潛在用戶推薦，因為用戶的兩個朋友成為好友的概率比隨機兩個人成為好友的概率高。參考文獻[3]和參考文獻[4]都是通過對用戶的軌跡進行建模，以此來分析用戶的軌跡相似度，進而度量用戶之間的相似性。但是它們的建模方法有所不同，參考文獻[3]中的建模方法采用HGSM（hierarchical-graph-based similarity measurement，基于等級結(jié)構(gòu)圖的相似度測量）算法，而參考文獻[4]中的建模方法采用PST（probabilistic suffix tree，概率后綴樹）。參考文獻[5]利用在線社交關(guān)系，并利用矩陣分解的方法進行潛在用戶推薦，取得了很好的效果。參考文獻[6]中通過用戶的歷史位置進行建模，可以分析出用戶的行為模式，然后根據(jù)用戶行為模式之間的相似性，向用戶推薦潛在好友或進行用戶行為的異常檢測。參考文獻[7]利用用戶的標簽信息和時間信息建立推薦模型，較好地分析了用戶的興趣愛好，具有很好的性能。參考文獻[8]采用改進協(xié)同過濾算法對交友網(wǎng)站中的用戶進行網(wǎng)上交友推薦，將交友雙方的興趣和吸引力等因素都考慮到推薦模型中，從而提高推薦效果。

綜合分析發(fā)現(xiàn)：參考文獻[1,2,5,7,8]主要是根據(jù)傳統(tǒng)的社交關(guān)系進行潛在用戶推薦；參考文獻[3,4]利用社交網(wǎng)站中的位置軌跡信息進行潛在用戶推薦；參考文獻[6]則利用社交網(wǎng)站中的歷史位置信息分析用戶的行為模式，然后利用用戶的行為模式相似性進行潛在用戶推薦及行為異常檢測。

考慮用戶簽到歷史信息、用戶影響力等因素，本文提出了一種利用用戶對位置的隱性評價計算用戶之間位置相似度的方法，進行潛在用戶推薦。該方法首先對用戶簽到的位置興趣點進行聚類，得到位置興趣區(qū)域；然后利用用戶的好友關(guān)系、用戶影響力、簽到特性來計算用戶在各個位置興趣點的位置權(quán)重，再利用向量空間模型計算用戶位置相似性及好友相似度；最后根據(jù)用戶綜合相似度進行潛在好友推薦。

3 用戶影響力分析與計算

本文對Gowalla、Brightkite等LBSN的簽到數(shù)據(jù)進行挖掘分析，發(fā)現(xiàn)53%左右的LBSN用戶完成了85%的簽到，如圖1所示，而且統(tǒng)計得到1年內(nèi)35%的用戶簽到次數(shù)少于10次，由此可以看出LBSN中存在核心用戶。這些核心用戶在LBSN中處于領(lǐng)導(dǎo)地位，他們在LBSN中很活躍，擁有很多LBSN好友，并且分享位置信息的意愿很強。

圖1 Gowalla和Brightkite簽到數(shù)據(jù)分析

位置社交網(wǎng)絡(luò)的用戶影響力是指用戶在位置社交網(wǎng)絡(luò)中對其他用戶的影響和帶動能力。它是用戶在社交網(wǎng)絡(luò)中所處重要程度的判斷標準，反映了用戶之間的交互關(guān)系和親密程度，同時對社交網(wǎng)絡(luò)的發(fā)展產(chǎn)生一定的推動力。用戶的影響力越大，別人對他的關(guān)注度就越高，對網(wǎng)絡(luò)信息的傳播推動作用也就越強。也就是說，在位置社交網(wǎng)絡(luò)中如果一個用戶的影響力很高，那么他所推薦的事物（無論是位置信息還是各類網(wǎng)絡(luò)廣告、網(wǎng)絡(luò)應(yīng)用）都很容易被傳播，很容易被別人接受。因此，位置社交網(wǎng)絡(luò)的用戶影響力是影響推薦服務(wù)的重要因素之一。

在LBSN中用戶影響力受到很多因素的影響，其中包括發(fā)揮自身影響力的意愿、自身活躍程度、好友數(shù)量、好友質(zhì)量、好友活躍程度等。綜合考慮各方面因素，本文的用戶影響力考慮了用戶自身發(fā)揮影響力的意愿和用戶影響度，計算方法如式（1）所示：

其中，Ii表示用戶i的影響力，Ni表示用戶i在時間T內(nèi)的簽到次數(shù)，Ni/T表示用戶發(fā)揮自身影響力的意愿，可以理解為：用戶在單位時間內(nèi)簽到的次數(shù)越多，用戶發(fā)揮其影響力的意愿就越高。LIR(i)表示用戶的影響度，關(guān)于它的計算，借鑒PageRank的思想，其值應(yīng)介于0和1之間，在包括自身影響度的同時，也要包括其好友對他的影響度，計算方法如式（2）所示：

其中，LIR(i)、LIR(v)分別表示用戶i和用戶v的影響力；d是權(quán)重系數(shù)，表示用戶好友對其影響所占的比重（本文選取0.85）；C(v)=Pi/(Pi+Pv)，表示用戶v的影響能力分配給用戶u的比例因子，Pi=∑v∈FiNv，F(xiàn)i是用戶u的好友集合，Nv是用戶v在LBSN中的等級。用戶等級可以通過用戶的簽到次數(shù)來衡量，因為在位置社交網(wǎng)站上，如果用戶在某一位置簽到次數(shù)最多，那么他會成為這一位置的地主，具有很強的號召力和說服力。將所有LIR的初始值設(shè)為0.1，通過迭代到收斂為止，可以得到所有用戶的LIR。該方法涉及的數(shù)據(jù)隨著用戶數(shù)量的不斷增加可以進行增量更新。

4 潛在好友推薦模型

位置社交網(wǎng)絡(luò)中的簽到數(shù)據(jù)包含用戶簽到位置的經(jīng)度和緯度這一新維度，記錄了用戶訪問的關(guān)鍵地點，形成了用戶的離散化行為軌跡。位置社交網(wǎng)絡(luò)的用戶行為軌跡由一系列離散的時空點組成，雖然它不像GPS那樣記錄用戶行為的連續(xù)軌跡，但是其記錄的離散化軌跡更能體現(xiàn)用戶強烈的目的性。每一個簽到位置對于用戶來說都有一定的意義，能夠表現(xiàn)出用戶的興趣愛好等，同時，每個位置對用戶的重要程度是不一樣的。因此，本文根據(jù)用戶之間的位置相似度和好友相似度，計算用戶的綜合相似度，從而進行潛在好友推薦。

根據(jù)實際情況可知，用戶的兩個朋友成為好友的概率比隨機兩個人成為好友的概率要高，同時，相近的位置一般屬于同一個區(qū)域，因而當用戶訪問相近或相同位置時，他們可能有相似或相同的行為目的。例如，當兩個用戶都經(jīng)常在雍和宮這類古代寺廟簽到時，說明他們具有一定的相似性或相同性，進而可以進行好友推薦。此外，每個位置對于用戶來說重要程度是不一樣的，如果兩個用戶對于很多位置持有相同的位置權(quán)重，那么可以認為他們具有一定的相似度。因此，本文判斷用戶相似性基于幾條經(jīng)驗，包括：用戶之間擁有共同的好友、用戶具有相同或相似的位置簽到歷史記錄、用戶持有相同位置權(quán)重的位置等的數(shù)量，這些數(shù)量越多，用戶之間的相似度越高。

4.1 位置聚類

在位置社交網(wǎng)絡(luò)中，用戶會在自己感興趣的地方進行簽到，每一個簽到位置稱為位置興趣點[9]（location point of interest，LPOI）。LPOI中包含位置的唯一標識號、經(jīng)緯度和名稱，即LPOI=(lcationID,latitude,longitude,name)。用戶在位置興趣點簽到時，位置社交網(wǎng)絡(luò)會留下用戶的簽到記錄（checkin），其中包括用戶ID、用戶訪問的LPOI、簽到時間、對位置興趣點的評價或此時的心情，表示為checkin=(userID,LPOI,time,text)。其中，text是可選內(nèi)容。

因為在某一個實際位置附近可能有很多不同的LPOI，所以在用戶訪問相近位置時可能在不同的LPOI上簽到。如果只是簡單地通過判斷用戶是否訪問同一個LPOI來得到用戶之間的位置相似度，那么這種數(shù)據(jù)是很稀疏的。因此，本文采用聚類的方法將相近的LPOI聚到同一區(qū)域，然后再根據(jù)用戶訪問的各個聚類區(qū)域，計算用戶之間的位置相似性。利用聚類的方法，可以將用戶經(jīng)常訪問的LPOI聚集到一塊，而用戶偶爾訪問或很少有人訪問的位置將被視為噪音而過濾掉。

本文采用DBSCAN算法[10,11]對用戶訪問的位置興趣點進行聚類。該算法是一種基于密度的空間聚類算法，與層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把達到一定高密度的區(qū)域劃分為簇，并可以在有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任何形狀的聚類。也就是說，該算法可以將一些高密度的LPOI劃分為簇，并且將LPOI數(shù)據(jù)庫中的噪聲LPOI排除在外。本文將聚集的LPOI集合定義為位置興趣點區(qū)域 （regional point of interest position，RPIP）。

對LPOI的DBSCAN聚類需要給出鄰域ε和minPts兩個對象參數(shù)，它們可以根據(jù)區(qū)域含LPOI的密度來決定。

LPOI的DBSCAN聚類算法描述如下。

（1）輸入LPOI集合L={L1,L2,…,Ln}；

（2）通過計算每平方千米含有LPOI的個數(shù)，選取適合的鄰域參數(shù)ε和聚類簇內(nèi)最少包含LPOI的個數(shù)minPts；

（3）遍歷LPOI整個集合，計算從Li到Lj在平面坐標上的距離，是否滿足密度可達的條件；

（4）若密度可達點的數(shù)量大于minPts，則構(gòu)成一個RPIP；否則，繼續(xù)遍歷LPOI集合；

（5）遍歷完LPOI集合，輸出RPIP集合R={R1,R2,…,Rn}。

4.2 位置權(quán)重表示

定義1位置權(quán)重（position weight）就是用戶對聚類后的位置興趣點區(qū)域（RPIP）的重視程度，也可以理解為用戶對RPIP的評分。

在位置社交網(wǎng)絡(luò)中，用戶對某一地理位置的重視程度可以用在某位置的簽到次數(shù)來衡量，在一定程度上反映了用戶對該位置的興趣，是一種隱式評價。但是不能準確地表示用戶對位置的興趣度，僅表明用戶自身對位置興趣點的評價，忽略了用戶好友對用戶的影響。在位置社交網(wǎng)絡(luò)中，用戶在某一位置興趣點簽到不僅要考慮自身的意愿，還要考慮用戶好友對他的影響，因為在現(xiàn)實生活中用戶去一個新位置進行活動時經(jīng)常會考慮自己好友所給的意見或者好友的經(jīng)歷?；诖怂枷?，本文給出了計算用戶位置權(quán)重的方法。

位置權(quán)重用Wij表示，即用戶i在位置j的位置權(quán)重，Wij的數(shù)值越大則表示位置j對于用戶i越重要，其計算式為：

其中，Nij表示用戶i在位置興趣點區(qū)域j的簽到次數(shù)；Ni表示用戶i在各個位置興趣點區(qū)域的總簽到次數(shù)；Nfj表示用戶i的朋友f在位置興趣點區(qū)域j的總簽到次數(shù)；Nj表示所有用戶在位置興趣點區(qū)域j的簽到總數(shù)；Wuser表示用戶在某一位置興趣點區(qū)域的自身位置權(quán)重；Wfriend表示用戶的好友在某一位置興趣點區(qū)域的位置權(quán)重；α是權(quán)重因子（本文選擇0.85）；I為影響因子，表示用戶的好友對用戶在某位置興趣點區(qū)域的平均影響力；Ik表示用戶的朋友k對用戶的影響因子，是用戶好友的影響力，其值通過對式（1）迭代到收斂取得；M表示用戶的好友個數(shù)。

4.3 用戶相似度計算

位置社交網(wǎng)絡(luò)上包含3種關(guān)系：人與人的關(guān)系、人與位置的關(guān)系及位置之間的關(guān)系，這些關(guān)系會影響用戶相似度的計算。LBSN用戶之間擁有共同好友，在一定程度上說明用戶之間具有相似度，用戶之間共同好友的個數(shù)越多，說明他們越相似；用戶的簽到位置一般會選在自己喜歡的位置或者對自己有意義的位置，位置記錄能夠表現(xiàn)用戶的愛好及行為習(xí)慣，因此，簽到位置的相似性也能體現(xiàn)用戶之間的相似度，用戶之間所選擇的簽到位置越相似，他們越相似。綜合以上兩點，本文計算相似度的方法采用兩種相似度的加權(quán)之和，如式（5）所示：

其中，SimL表示位置相似度，SimF表示好友相似度，b為加權(quán)系數(shù)。

4.3.1 位置相似度計算

本文利用空間向量模型計算用戶之間的位置權(quán)重相似度，即用戶的位置相似度。向量Li表示用戶在各個位置興趣點區(qū)域的位置權(quán)重向量，其中Li=[Wi1,Wi2,…,Wij]，Wij表示用戶i在位置興趣點區(qū)域j的位置權(quán)重。用戶之間位置權(quán)重相似的位置越多，可以理解為他們的相似度越高，也可以說他們成為好友的可能性越大。所有用戶訪問的位置興趣區(qū)域的位置權(quán)重構(gòu)成用戶位置權(quán)重矩陣，然后用余弦相似性方法計算用戶之間的相似度。

用戶位置權(quán)重矩陣表示為：

其中，m為位置社交網(wǎng)絡(luò)的用戶數(shù)，n為位置興趣區(qū)域的總數(shù)，Wij為用戶i在位置興趣點j的位置權(quán)重。

把用戶在各個位置興趣區(qū)域的位置權(quán)重看成n維向量空間上的向量，用向量余弦夾角度量用戶之間的相似度。設(shè)用戶X與用戶Y在n維向量空間中表示為WX和WY，通過式（7）計算用戶之間相似度：

4.3.2 好友相似度計算

根據(jù)六度分割原理可以知道，通過一定次數(shù)的傳遞，人能通過朋友的朋友認識社交網(wǎng)絡(luò)中的任何人。因此，兩個用戶具有共同好友，他們成為朋友的概率比兩個沒有任何關(guān)系的陌生人成為朋友的概率大。本文利用共同好友比重度量好友相似度，如式（8）所示：

其中，UX為用戶X的好友集合，UY為用戶Y的好友集合。

4.4 產(chǎn)生TopK推薦

根據(jù)前文所述，本文分別計算出任意用戶之間位置相似度和好友相似度，再計算用戶的綜合相似度，并根據(jù)綜合相似度進行TopK推薦，得到最終的推薦列表。通過位置相似度和好友相似度進行好友推薦可以看成兩個屬性的TopK推薦問題，位置相似度是一個屬性，好友相似性是另一個屬性，通過前文的計算得到各自對應(yīng)的值，最后綜合計算最優(yōu)值，從而得到最適合推薦的K個好友。

5 實驗數(shù)據(jù)與實驗結(jié)果

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

本文采用LBSN網(wǎng)站Gowalla的2009-2010年的簽到數(shù)據(jù)集[12]，其中包含640萬條簽到記錄、70萬個簽到位置、19萬個用戶的200萬條好友關(guān)系。實際上對位置數(shù)據(jù)中的無效用戶（即注冊后很少簽到的用戶）和很少有人簽到的位置興趣點（即到訪人數(shù)很少的點）進行挖掘是沒有意義的，因此需要對數(shù)據(jù)進行預(yù)處理，移除無意義點，減少數(shù)據(jù)量。本文將一些很少訪問的位置和具有很少好友的用戶進行清理，清洗過程中設(shè)定用戶在規(guī)定時間ΔT內(nèi)的最小簽到頻率Fmin（本文Fmin=1）和最大簽到頻率Fmax（本文Fmax=8），如果用戶簽到頻率小于Fmin，則該用戶的相應(yīng)數(shù)據(jù)視為無效；如果用戶簽到頻率大于Fmax，則視為虛假簽到，將其相應(yīng)的數(shù)據(jù)進行清除。經(jīng)過數(shù)據(jù)清洗后，最終得到2 689個用戶的5萬多條好友關(guān)系、135萬多條簽到記錄、23萬多個簽到位置。從所清洗的數(shù)據(jù)集中隨機選取500個用戶進行實驗研究，這些用戶的平均好友數(shù)為20個，平均簽到次數(shù)為689次。將所選取的數(shù)據(jù)集存儲在MySQL數(shù)據(jù)庫中，建立新的數(shù)據(jù)庫表，分別為用戶好友表（user_friend）、用戶簽到 表（user_checkin）、RPIP表（location_PRIP）、位置用戶簽到表（location_user），其中用戶好友表記錄用戶的好友，用戶簽到表記錄用戶訪問位置興趣區(qū)域，RPIP表記錄每個RPIP具體包含的LPOI，位置用戶表記錄在每個RPIP簽到的用戶。

5.2 方法評測標準

本文的推薦效果由召回率和精確度進行度量[13]。將數(shù)據(jù)集中的好友關(guān)系劃分為訓(xùn)練集（training set）與測試集（test set），訓(xùn)練集用于建立潛在好友推薦模型，測試集用于對潛在好友推薦模型進行驗證。L(u)是對訓(xùn)練集上的用戶做出的推薦列表，即推薦結(jié)果，R(u)是測試集上已存在的真實關(guān)系。推薦結(jié)果可能包括相關(guān)結(jié)果（relevant result，RR）和 不 相 關(guān) 結(jié) 果（irrelevant result，IR），即L(u)=RR+IR，其中相關(guān)結(jié)果就是實際存在的好友關(guān)系，不相關(guān)結(jié)果則是在測試集中不存在的好友關(guān)系。測試集中應(yīng)該包含所有存在的結(jié)果，即包括推薦結(jié)果中相關(guān)結(jié)果和未推薦的相關(guān)結(jié)果（no relevant result，NRR），則R(u)=RR+NRR。

定義2召回率（recall）就是推薦結(jié)果中相關(guān)結(jié)果占好友總數(shù)的比重，如式（9）所示：

定義3精確度（accuracy）就是推薦結(jié)果中相關(guān)結(jié)果占所有推薦結(jié)果的比重，如式（10）所示：

定義4 F指標是一種綜合考慮召回率和精確度的指標，如式（11）所示：

在本文中，如果算法A的召回率和精確度總體高于算法B，認為算法A比算法B具有更高的推薦性能[14]。

5.3 實驗結(jié)果及分析

本文根據(jù)LPOI的密度，將DBSCAN聚類的鄰域ε取300，minPts取10，圖2為聚類結(jié)果中部分RPIP顯示結(jié)果，橫縱坐標分別為LPOI的緯度和經(jīng)度，由圖2可知聚類效果還可以。

圖2 部分RPIP結(jié)果

在本實驗中將數(shù)據(jù)集的90%作為訓(xùn)練集，10%作為測試集。式（5）中的系數(shù)b∈{0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1}。當b=0時，推薦方法為只考慮用戶好友相似性，而不考慮用戶的位置簽到信息，所得推薦列表僅與社交網(wǎng)絡(luò)好友相似度有關(guān)。當b=1時，推薦方法為只考慮位置相似性，所得推薦列表僅與用戶的簽到位置信息有關(guān)。其余幾組數(shù)據(jù)表示綜合考慮用戶好友相似度和用戶位置相似度，這就是本文提出的結(jié)合好友相似度和簽到位置相似度的推薦算法。通過上述參數(shù)設(shè)置，可以對比得出本文算法中好友相似度和位置相似性所占比重對推薦結(jié)果產(chǎn)生的影響。推薦列表大小N取值為25，系數(shù)b作為橫軸，計算此推薦模型中所有用戶的召回率和精確度，進而計算其平均F指標，如圖3所示。

圖3 不同系數(shù)下的F指標

F指標綜合考慮了召回率和精確度，其大小可以衡量推薦算法的性能。由圖3可知，完全基于位置相似度的推薦算法（即b=1時）性能要略高于完全基于好友相似度的推薦算法（即b=0時），同時，本文推薦算法的效果隨著系數(shù)b的增加而先增加后下降，當b=0.8時本算法的推薦質(zhì)量最高。

由上述實驗可知：b=0.8時，本推薦方法效果最好，因此以下實驗中取b=0.8。以下為本方法分別與基于Jaccard系數(shù)的推薦方法（利用Jaccard系數(shù)[15]求位置相似度，從而得到用戶間相似度，再根據(jù)用戶間相似度的高低進行潛在好友推薦）和基于好友相似度的推薦方法（簡稱UserRec，其方法是利用第3.3節(jié)計算用戶間的相似度，再根據(jù)用戶間相似度的高低進行潛在好友推薦）的對比試驗。其中推薦列表個數(shù)N分別為3、5、10、15、20、25，其精確度和召回率結(jié)果如圖4、圖5所示。通過實驗結(jié)果可以看出，本文提出的推薦算法的精確度和召回率比其他兩種方法都高。雖然召回率在N=3和N=5時沒有表現(xiàn)出很好的優(yōu)越性，但是N>10時開始明顯優(yōu)于上述其他兩種方法?？傮w來說，本文推薦方法具有較好的性能。

圖4 精確度結(jié)果

圖5 召回率結(jié)果

6 結(jié)束語

本文對潛在好友推薦模型進行了研究，旨在主動為用戶提供有效信息，解決信息過載等問題，有效地為用戶推薦合適的潛在好友，更好地發(fā)展用戶的社交圈，同時為位置社交網(wǎng)絡(luò)的健康發(fā)展貢獻一份力量。首先，本文利用基于密度聚類的DBSCAN算法，將各個位置興趣點聚類為不同的位置興趣區(qū)域，這樣比只用位置興趣點進行相似度計算更加快捷準確；然后，再計算所有用戶在各個位置興趣區(qū)域的位置權(quán)重，如果用戶在很多位置興趣區(qū)域的位置權(quán)重相似，那么用戶之間的相似度就很高；最后，得到用戶間的位置相似度及好友相似度，再對它們進行權(quán)重疊加，進而得到潛在好友推薦列表，實現(xiàn)TopK推薦。利用真實數(shù)據(jù)對潛在好友推薦模型進行實驗驗證，結(jié)果表明，本文方法的推薦性能相比基于Jaccard系數(shù)的推薦方法和基于社交網(wǎng)絡(luò)關(guān)系的推薦方法有明顯提高，由此證明了該方法的有效性。

1 翟紅生,于海鵬.在線社交網(wǎng)絡(luò)中的位置服務(wù)研究進展與趨勢.計算機應(yīng)用研究,2013,30(11):3221～3227

2 Hruschka D J,Henrich J.Friendship,cliquishness,and the emergence of cooperation.Journal of Theoretical Biology,2006,239(1):1～15

3 Li Q,Zheng Y,Xie X,et al.Mining user similarity based on location history.Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,New York,USA,2008:31～34

4 Hung C C,Chang C W,Peng W C.Mining trajectory profiles for discovering user communities.Proceedings of the International Workshop on Location Based Social Networks,New York,USA,2009:1～8

5 Ma H,Zhou D,Liu C.Recommender systems with social regularization.Proceedings of the 4th ACM International Conference on Web Search and Data Mining,New York,USA,2011:287～296

6 Zhang D,Li N,Zhou Z H,et al.IBAT:detecting anomalous taxi trajectories from GPS traces.Proceedings of the 13th International Conference on Ubiquitous Computing,New York,USA,2011:99～108

7 Zheng N,Li Q.A recommender system based on tag and time information for social tagging systems.Expert Systems with Applications,2011,38(4):4575～4587

8 Zha o K,Wang X,Yu M,et al.User recommendation in reciprocal and bipartite social networks——a case study of online dating.IEEE Intelligent Systems,2013,17(3):29～30

9 Liu B,Xiong H,Liu B,et al.Point-of-interest recommendation in location based social networks with topic and location awareness.Proceedings of SIAM International Conference on Data Mining,Austin,Texas,USA,2013:396～404

10 邢冬麗,趙美紅,陳文成.基于密度的DBSCAN算法.計算機工程與應(yīng)用,2007,43(20):216～221

11 Dunham H M.數(shù)據(jù)挖掘教程.郭崇慧,田鳳占,靳曉明譯.北京:清華大學(xué)出版社,2005

12 Cho E,Myers S A,Leskovec J.Friendship and mobility:user movement in location-based social networks.Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,USA,2011:1082～1090

13 Yang T,Cui Y,Jin Y.BPR-UserRec:a personalized user recommendation method in social tagging systems.The Journal of China Universities of Posts and Telecommunications,2013,20(1):122～128

14 Spertus E,Sahami M,Buyukkokten O.Evaluating similarity measures:a large-scale study in the orkut social network.Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining,New York,USA,2005:678～684

15 Tan P N,Steinbach M,Kumar V.數(shù)據(jù)挖掘?qū)д?范明,范宏建譯.北京:人民郵電出版社,2010