孫曉晨，徐雅斌,2

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

1 引言

位置服務(wù)（location-based service，LBS）又稱定位服務(wù)，是通過GPS（global positioning system，全球定位系統(tǒng)）、WLAN（wireless local area network，無線局域網(wǎng)）等技術(shù)獲得移動(dòng)終端的位置信息（如經(jīng)緯度坐標(biāo)數(shù)據(jù)），并將這些位置信息提供給移動(dòng)通信用戶及通信系統(tǒng)，實(shí)現(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ò)那樣分享博客、照片、視頻進(jìn)行信息交互，而且可以隨時(shí)隨地地定位和分享位置信息[1]。用戶可以通過電腦、手機(jī)及其他移動(dòng)終端進(jìn)行簽到，并將所處的位置信息及時(shí)告訴他的朋友。當(dāng)簽到信息發(fā)生變化時(shí)，用戶能通過社交網(wǎng)站進(jìn)行同步更新，這樣就可以方便快捷地與好友分享自己的最新動(dòng)態(tài)。

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

2 相關(guān)工作

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

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

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

3 用戶影響力分析與計(jì)算

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

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

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

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

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

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

4 潛在好友推薦模型

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

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

4.1 位置聚類

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

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

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

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

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

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

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

（3）遍歷LPOI整個(gè)集合，計(jì)算從Li到Lj在平面坐標(biāo)上的距離，是否滿足密度可達(dá)的條件；

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

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

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

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

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

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

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

4.3 用戶相似度計(jì)算

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

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

4.3.1 位置相似度計(jì)算

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

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

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

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

4.3.2 好友相似度計(jì)算

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

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

4.4 產(chǎn)生TopK推薦

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

5 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果

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

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

5.2 方法評(píng)測標(biāo)準(zhǔn)

本文的推薦效果由召回率和精確度進(jìn)行度量[13]。將數(shù)據(jù)集中的好友關(guān)系劃分為訓(xùn)練集（training set）與測試集（test set），訓(xùn)練集用于建立潛在好友推薦模型，測試集用于對(duì)潛在好友推薦模型進(jìn)行驗(yàn)證。L(u)是對(duì)訓(xùn)練集上的用戶做出的推薦列表，即推薦結(jié)果，R(u)是測試集上已存在的真實(shí)關(guān)系。推薦結(jié)果可能包括相關(guān)結(jié)果（relevant result，RR）和 不 相 關(guān) 結(jié) 果（irrelevant result，IR），即L(u)=RR+IR，其中相關(guān)結(jié)果就是實(shí)際存在的好友關(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指標(biāo)是一種綜合考慮召回率和精確度的指標(biāo)，如式（11）所示：

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

5.3 實(shí)驗(yàn)結(jié)果及分析

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

圖2 部分RPIP結(jié)果

在本實(shí)驗(yàn)中將數(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}。當(dāng)b=0時(shí)，推薦方法為只考慮用戶好友相似性，而不考慮用戶的位置簽到信息，所得推薦列表僅與社交網(wǎng)絡(luò)好友相似度有關(guān)。當(dāng)b=1時(shí)，推薦方法為只考慮位置相似性，所得推薦列表僅與用戶的簽到位置信息有關(guān)。其余幾組數(shù)據(jù)表示綜合考慮用戶好友相似度和用戶位置相似度，這就是本文提出的結(jié)合好友相似度和簽到位置相似度的推薦算法。通過上述參數(shù)設(shè)置，可以對(duì)比得出本文算法中好友相似度和位置相似性所占比重對(duì)推薦結(jié)果產(chǎn)生的影響。推薦列表大小N取值為25，系數(shù)b作為橫軸，計(jì)算此推薦模型中所有用戶的召回率和精確度，進(jìn)而計(jì)算其平均F指標(biāo)，如圖3所示。

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

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

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

圖4 精確度結(jié)果

圖5 召回率結(jié)果

6 結(jié)束語

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

1 翟紅生,于海鵬.在線社交網(wǎng)絡(luò)中的位置服務(wù)研究進(jìn)展與趨勢.計(jì)算機(jī)應(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算法.計(jì)算機(jī)工程與應(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