地理社交網絡位置推薦*

景寧，王躍華，鐘志農，吳燁(國防科技大學電子科學與工程學院，湖南長沙410073)

地理社交網絡位置推薦*

景寧，王躍華，鐘志農，吳燁
(國防科技大學電子科學與工程學院，湖南長沙410073)

地理社交網絡將地理位置信息融合進傳統社交網絡，將人們的現實生活和虛擬世界的生活連接在一起。作為地理社交網絡的一個重要應用，位置推薦可以向人們推薦其可能感興趣的位置，為人們的出行提供參考，極大地便利了人們的生活。在此背景下，論文研究了地理社交網絡位置推薦的基本概念，分析了位置推薦常用的方法，描述了典型的數據集及推薦效果的評估方法，指出了位置推薦面臨的主要問題，并展望了未來可能的研究方向，為相關領域的研究提供參考。

地理社交網絡；位置推薦；協同過濾；數據稀疏性；冷啟動

隨著Web技術的迅速發展，不斷產生的各種各樣的網絡應用，如微博、博客、微信等，越來越受到人們的歡迎。Facebook，Twitter，Flickr等在線社交網絡服務(online social networking service)已成為互聯網上發展最快也最受歡迎的應用。隨著定位技術的發展和普及，人們無論在室內還是室外都很容易通過智能移動設備獲取他們自身的物理位置［1］，基于位置的服務也逐漸普及起來［2］。社交網絡和基于位置的服務的融合促成了地理社交網絡，即基于位置的社交網絡［3］(Location-Based Social Network，LBSN)，如國外的Foursquare，Yelp，Facebook Place，國內的街旁網、點評網等的誕生。在地理社交網絡中，人們不但可以進行信息交互，還可以分享博客、視頻、圖像等信息［4-6］，尤其是用戶與好友分享訪問過的位置及相關社交信息，使得人們在虛擬網絡中的行為與現實世界所處位置聯系起來［7］，加強了人們之間的交流與溝通。

城市的快速擴張誕生了大量的餐館、影院、公園、購物中心等場所，極大地拓展了人們的生活區域，為人們的出行提供了更多的選擇，但由此也帶來了一些問題，比如“到哪里去玩?”“在哪個餐館吃飯?”“去哪個商場購物?”等［8-9］。如何解決這樣的問題，以滿足人們探索新位置的需求，成為一個十分有意義的工作。位置推薦正是解決此類問題的一個方法。

1 問題描述

1.1 地理社交網絡

地理社交網絡，即在現存的社交網絡中加入位置因素，以便社會結構中的人們可以共享嵌入位置的信息?；谌藗冊谖锢硎澜缰杏晌恢眯畔⑼瞥龅南嚓P性，地理社交網絡中包含了一種新的社會結構［10］。地理社交網絡可以劃分為三個層次:用戶層、位置層和內容層［11］，如圖1所示。

圖1 地理社交網絡結構［10］Fig.1 Structure of LBSN

從圖1可以得出3種地理社交網絡的圖:用戶-用戶圖、用戶-位置圖以及位置-位置圖。對用戶-用戶圖，可以基于社交網絡計算用戶的相似性。對于用戶-位置圖，每一條邊都代表用戶對該位置有進行簽到訪問，用戶對這個位置的訪問次數可以用邊的權重表示。從圖1中同時還可以得到用戶的出行軌跡。對于位置-位置圖，節點連線表示用戶連續訪問這兩個位置。

1.2 地理社交網絡數據

地理社交網絡數據除具有傳統社交網絡中的好友關系外，還引入了位置信息。位置信息將用戶在網絡中的行為與物理世界聯系起來。位置信息的引入為地理社交網絡帶來了一些獨特的性質:

位置之間的距離:大量文獻［12-16］研究表明，用戶出行與位置之間的距離具有極大的關系。用戶從某一位置去往另一位置的概率服從冪率分布，即兩地之間距離越近，概率越大，如圖2所示。

圖2 距離對簽到概率的影響［13］Fig.2 Influence of distance on check-in frequency［13］

位置的級別:位置通常具有不同層級。一個位置可以是一個餐館，也可以是一個城市，甚至是一個國家。因此，不同層級的位置意味著不同的用戶-位置圖。通常來說，用戶分享越低層級的位置(如一個餐館或公園)代表著用戶具有更緊密的關系，比如兩個總是在同一個餐館簽到的人之間的關系通常要比兩個總是在同一個城市簽到的人之間的關系強。

時序性:用戶在不同的地方簽到，則這兩個簽到位置在時間上具有時序性［14，17］。如果兩個用戶簽到的位置相同，且具有相同的簽到順序，比如先到位置A簽到，后在位置B簽到，則這兩個用戶可能具有更強的相似性。

時間特性:用戶在某位置簽到，簽到的時間往往代表用戶的某種習慣。比如工作日期間用戶甲通常在早上7:30在位置A簽到，而中午12:00通常在位置B簽到，晚上18:00通常在位置C簽到。這樣的簽到往往代表用戶一天的活動狀態或生活習慣。

1.3 位置推薦

下面給出位置推薦一些相關的定義。

定義1(興趣點，POI)一個興趣點就是一個用戶可能覺得有用或有趣的具體位置，可用一個唯一的字符串標志。其對應現實世界的一個具體位置，記為l={ID，(latitude，longitude)，category}，其中ID為興趣點唯一標志，(latitude，longitude)為興趣點的經緯度，category表示興趣點的類別信息，如餐館、影院等。所有興趣點組合在一起稱為興趣點集合，記為L={l1，l2，…，ln}。Lu+和Lu-分別表示某用戶訪問過和未訪問過的興趣點集合。

興趣點有時也稱位置(location，venue，place或position等)，在不引起混淆的情況下，本文興趣點與位置意義等同。

定義2(簽到，check-in)某個用戶u在某個時間t，訪問了某個興趣點l稱為一次簽到，記為c=(u，t，l)。

定義3(簽到歷史，check-in history)某用戶u的簽到歷史表示某段時間(ts，te)內，用戶u的簽到集合，記為Cu，(ts，te)=≤teand cu·t＞ts}，其中ts表示起始時間，te表示結束時間。

定義4(位置推薦，location recommendation)位置推薦是指位置推薦系統根據用戶的簽到歷史、用戶好友的簽到歷史、好友關系強度以及興趣點的位置、類別、流行度等信息向用戶推薦其未訪問過但可能感興趣的位置，并過濾掉不感興趣的位置，以快速、高效地滿足用戶訪問新位置的需求。

2 位置推薦方法

位置推薦算法有很多，根據采用的方法不同可以分為基于協同過濾(collaborative filteringbased)的位置推薦、基于內容(content-based)的位置推薦以及混合模型的位置推薦，其中最常用的方法是基于協同過濾的位置推薦方法。

2.1 基于協同過濾的位置推薦

協同過濾算法假設具有相同或者相似興趣偏好的用戶的信息需求也是相似的，其基本思想是利用“人群的智慧(wisdom of the crowd)”對信息進行過濾篩選［18］。協同過濾算法通過挖掘用戶的歷史標注信息(購買、觀看、點擊)來發現相似用戶或項目，然后利用相似用戶或項目的評分信息來預測當前用戶對項目的喜好程度。按照實現方式的不同，協同過濾算法可以分為兩大類:基于記憶(memory-based)的方法和基于模型(modelbased)的方法。

2.1.1 基于記憶的方法

根據假設條件的不同，基于記憶的方法又可分為兩類:基于用戶(user-based)的方法和基于項目(item-based)的方法?；谟脩舻姆椒僭O具有相同習慣的用戶具有相同的愛好；基于項目的方法則假設用戶會喜歡與他之前評分較高的項目相似的項目?；谟洃浀姆椒ㄍǔ７譃閮蓚€步驟:首先根據用戶(項目)的標注信息計算出相似用戶(項目)集合，稱為鄰居集合，然后根據用戶(項目)與鄰居集合中的用戶(項目)的相似度進行推薦。用戶相似度的計算方法有多種，目前應用最多的是余弦相似度(cosine similarity)和皮爾遜相關系數(Pearson correlation coefficient)。

基于用戶的協同過濾算法(user-based collaborative filtering algorithm)根據用戶行為的相似度進行相似度計算，然后給用戶推薦和他有相似興趣愛好的用戶喜歡的項目。因為是基于其他用戶的興趣愛好來進行推薦，即如果一個位置被越多的用戶喜歡，那么它被推薦的概率越高［18］，所以基于用戶的協同過濾算法比較容易發現熱門位置。在地點推薦的場景中，用戶和地點通過簽到聯系起來，用戶的簽到也反映了用戶對于各種地點的偏好。

如表1所示，假設要為用戶3推薦位置，由用戶3與用戶1之間有3個簽到位置相同，而用戶3與用戶2之間只有1個相同的簽到位置，由此可以判斷用戶3與用戶1的簽到行為更為相似。那么，推薦系統在為用戶3推薦位置的時候更可能推薦用戶1簽到過的“梅溪湖”，而不是用戶2簽到過的“岳麓山”和“世界之窗”。

表1 用戶簽到位置Tab.1 Users’check-in POIs

基于協同過濾的位置推薦［19］目前主要考慮的因素包括:地理位置［20-22］、距離［23-24］(包括用戶-位置距離、位置-位置距離等)、用戶社交關系［25-26］、時間［27］等。

Ference等［28］考慮到傳統基于協同過濾的位置推薦方法由于沒有考慮到用戶當前所處位置可能引起推薦位置距離用戶太遠的問題，提出了一種基于用戶的協同過濾方法，綜合考慮用戶的偏好信息、用戶當前位置的附近區域以及社交信息等因素，為地理社交網絡手機用戶提供推薦服務。Mao等［13］研究用戶簽到位置，發現用戶訪問位置的聚集現象和位置之間距離滿足冪率分布，由此建立統一的描述框架，線性地融合了用戶的興趣和地理的影響進行位置推薦。王靜金［11］考慮用戶當前位置與興趣點的距離，認為由于人的行動的限制，過遠的興趣點需要先過濾掉，且用戶社交關系在位置推薦中具有重要作用，因此提出基于用戶當前位置和社交影響力的用戶協同過濾方法。Li等［15］認為用戶對興趣點的評分并不能完全代表用戶對該興趣點的喜好程度，而在一段時間內的相對評分才能夠更好地表示用戶對該興趣點的偏好程度，由此提出了基于時間窗-用戶相對評分方法的推薦方法。Wang等［29］認為用戶過去的簽到信息以及簽到位置的空間屬性和用戶的社交屬性在位置推薦中具有重要的作用，由此提出基于用戶歷史簽到信息、簽到位置信息、社交信息以及相似用戶信息的推薦方法。Konstas等［30］認為，在考慮用戶社交因素時，不能只看用戶是否為好友關系，同時需要考慮用戶好友關系的強度，而這個強度可以使用用戶和用戶的共同好友個數來確定。Quan等［14］認為大多數用戶在每天不同時段會訪問不同的位置，并且用戶的出行存在一定的規律性，因此時間在位置推薦中起著重要的作用，由此通過計算不同時間段用戶出行模式的相似度，結合地理位置信息對用戶出行的影響，提出了時間敏感的位置推薦方法。

基于項目的協同過濾算法(item-based collaborative filtering algorithm)根據項目之間的相似度進行計算，然后向用戶推薦與其之前訪問過的項目相似的新項目，如果一個項目與用戶之前喜歡過的項目很相似，那么該項目推薦出來的概率就比較高?；陧椖康膮f同過濾算法主要是對目標用戶所評價的一組項目進行研究，并計算這些項目與目標項目之間的相似性，然后從中選擇出前N個作為推薦項目輸出。

2.1.2 基于模型的方法

基于模型的方法［1，6，31］的基本思想是采用機器學習技術，建立相關的學習模型(如聚類模型、貝葉斯網絡模型等)，利用評價矩陣中的信息進行訓練得到模型系數，然后利用該模型對推薦結果進行預測?；谀Ｐ偷姆椒ㄗ畛Ｓ玫氖腔诰仃嚪纸獾姆椒ǎ?2-34］。

給定頻率矩陣F(F反映了用戶訪問興趣點的頻率，F∈RM×N)，可以對它進行低秩的矩陣分解來進行位置推薦，實際上就是把用戶和興趣點映射到一個維度為K?min(M，N)的聯合隱式空間，使得用戶對興趣點的偏好被建模成它們在隱式空間中的點積。這個映射問題可以通過解決式(1)所示的范數近似問題來完成:

式中，P∈RM×K和Q∈RN×K分別是用戶隱向量和興趣點隱向量?！是矩陣的Frobenius范數，也就是矩陣里面每個元素的平方和的根。這個問題可以通過取奇異值分解的前k對奇異向量來得到唯一的解。然而，由于擁有大量的用戶和興趣點數量，對這兩類隱向量交替求解最小二乘問題更可行。

連德富［6］在矩陣分解模型中擴充用戶隱向量和興趣點隱向量，用以描述地理社交網絡中移動行為隱含的空間聚集效應，有效解決矩陣稀疏的問題。Cheng等［34］采用矩陣分解的方法，考慮了時間序列模式和局域化區域(localized regions)屬性，成功實現了個性化的位置推薦系統。Gao等［35］依據用戶的簽到時間和簽到位置的強關聯性，基于LBSN中用戶移動的時間屬性，提出了基于低秩矩陣分解的推薦方法。Berjani等［36］在位置推薦中采用geometric embeddings方法。Yang等［37］在位置推薦中引入了sentiment-recommendation(基于概率矩陣分解)的方法并通過實驗驗證了算法的有效性。

2.2 基于內容的位置推薦

基于內容的位置推薦方法的基本思想是通過分析用戶的屬性和文本信息，發掘出與用戶興趣愛好相關的關鍵詞或者標簽、情緒指示信息以及興趣點的特征，如標簽、類別等信息，然后利用這些知識構建用戶的興趣檔案(profile)，并將這些興趣檔案和產品特征進行匹配后做出推薦［5，38-40］。

Gao［1］認為傳統基于內容的位置推薦方法沒有充分利用興趣點屬性信息、用戶興趣信息和用戶的情緒指示信息，由此研究了用戶相關的內容信息(用戶興趣信息和用戶的情緒指示信息)以及興趣點相關內容信息(興趣點屬性信息)，并提出了一個可以綜合利用這些內容信息的位置推薦框架。Liu等［16］認為位置推薦受到多方面因素的影響，包括用戶偏好信息、地理位置影響和用戶的行為習慣等，并在此基礎上提出了一個聚集文檔主題生成(Latent Dirichlet Allocation，LDA)模型和矩陣分解的方法，綜合利用上述因素進行位置推薦。Hu等［41-42］在社交關聯中采用用戶興趣和位置屬性等內容信息發掘用戶關系，并采用主題模型對位置推薦進行建模，取得了較好的推薦效果。

基于內容的方法最大的優點是對冷啟動問題具有較好的魯棒性，因為地理社交網絡在新用戶注冊的時候通常會讓用戶填寫一些個人信息，這些信息能夠比較準確地描述用戶的特征和喜好。但基于內容的方法同樣有其缺點:一是獲取用戶的屬性或者文本信息的難度較大且代價較高；二是沒有考慮用戶群組的興趣愛好信息，因此可能使推薦效果較差；三是基于內容的方法需要對用戶和位置的結構化信息進行創建和維護，其代價會比較大，尤其是社交網絡中的用戶和位置信息多數是由用戶產生的。

2.3 混合模型的位置推薦

混合模型的位置推薦即采用不同方法進行位置推薦，綜合使用內容信息和協同過濾進行位置推薦的方法。此種方法能夠較好地解決數據稀疏性問題，對冷啟動問題也有較好的效果，但缺點是復雜度較高，性能較差。

Leung等［43］在協同過濾方法的基礎上，分析不同用戶類別和不同時間偏好對位置推薦的影響，提出一種動態聚類規則的位置推薦方法。Nunes等［44］認為傳統的單純使用協同過濾的位置推薦方法只是利用了用戶的社交信息和興趣點的位置信息，對興趣點的地理信息(如區域等)利用不夠充分，因此提出了一個融合協同過濾和興趣點地理信息的融合模型，利用相似用戶信息、訪問過與未訪問過的興趣點的距離以及用戶感興趣的區域信息等因素進行位置推薦，并在Foursquare和Gowalla數據集上進行實驗，取得了較好的效果。Liu等［45］研究了位置標簽的影響，并提出了一種在基于模型的協同過濾方法(矩陣分解)上結合LDA模型的方法進行位置推薦。

3 數據集與推薦效果評估方法

3.1 數據集

地理社交網絡有很多的數據集，像Foursquare和Gowalla等。很多的數據集從網絡中都可以獲取到。表2列舉了幾個比較有代表性的數據集。

表2 地理社交網絡數據集Tab.2 Datasets of LBSNs

3.2 評估方法

位置推薦系統的推薦效果如何通常需要進行評估。常用的評估方法如下。

3.2.1 用戶調查法

研究者邀請一些人作為實驗對象，使用推薦系統，并對使用效果進行評價，如Symeonidis等［46］提出的推薦系統可以向用戶推薦好友、位置以及活動。用戶調查法通常是研究者給出一個評價標準，用戶對每一個推薦任務推薦出來的top-k個推薦結果進行主觀評價，以評估推薦系統推薦效果的好壞。用戶調查法通常代價比較大，且實施比較困難，而且由于用戶調查實驗對象的限制，評價結果可靠性無法保證。

3.2.2 準確率(precision)和召回率(recall)

研究者通常將一個數據集拆分為訓練集和測試集兩部分。對于一個測試集，令TopN(u)為根據訓練集數據給用戶做出的推薦列表，T(u)為用戶在測試集上的行為列表。由此，推薦結果的召回率定義為:

式中，U為用戶集。

推薦結果的準確率定義為:

推薦結果的召回率表示被推薦出來的且在測試集中用戶訪問過的位置所占總推薦數的比例；準確率則表示被推薦出來的且在測試集中用戶訪問過的位置所占總訓練集的比例［34］。

通常綜合考慮算法這兩方面得分以更加全面地衡量推薦算法的推薦性能。而為了全面評測top-N推薦的準確率和召回率，常用的方法是選取不同的推薦列表長度N，計算出一組準確率/召回率，然后畫出準確率/召回率曲線。

3.2.3 平均精度均值

平均精度均值(Mean Average Precision，MAP)［18］一般被用于信息檢索中用來測量搜索引擎的效果，搜索結果的MAP值越高，表明越相關的條目排得越靠前，在推薦系統里用來檢測準確率和預期分值是否正相關。推薦列表的順序也是MAP考慮的因素，即當給目標用戶提供top-N個興趣點為推薦列表時，這些推薦項目在列表中的順序也很重要。比如當我們給用戶u推薦興趣點，那么最好應該是正確地推測其在推薦列表的最前面。因此MAP可用來強調高排名的相關用戶。MAP的定義如式(4)所示:

式中，N是測試數據集中用戶的數量，cu是與用戶u相關的用戶的數量，precisionu@k是用戶u的推薦列表中推薦項目為k時的準確率。

3.2.4 交叉驗證法

在k-折交叉驗證(k-fold cross-validation)法中，初始數據集隨機地劃分k個互不相交的子集D0，D1，…，Dk，每個子集的大小大致相等。訓練和檢驗進行k次。在第i次迭代，分區Di用作檢驗集，其余的分區一起作訓練集。這樣每個數據都被訓練了相同的次數，并且都被測試了一次。

3.2.5 時間分割法

在數據集的時間間隔中選擇一個時間點，把時間點前的簽到數據當作訓練集，時間點之后的數據作為測試集。這種方法在實際LBSNs的推薦系統中很類似，因為在某一個特定的推薦時間點只知道之前的簽到情況。

4 位置推薦面臨的問題

4.1 數據稀疏性問題

數據稀疏性是指在推薦系統中，由于用戶和項目的數量十分龐大，而用戶往往只在少數項目中有評分記錄(在位置推薦中，用戶和興趣點數目龐大，但用戶往往只訪問過有限的興趣點，評分記錄也很少)，這就導致用戶-評分矩陣非常稀疏，即數據稀疏性問題。由于用戶之間共同訪問過的興趣點過少，因此，基于記憶的方法無法精確計算用戶(項目)之間的相似度，從而導致鄰居集合的選取不準確，影響推薦的精度。如果一個推薦系統中用戶過少，項目太多，那么很多的項目可能從沒有人訪問過，這樣很可能使得項目根本無法推薦。

4.2 冷啟動問題

冷啟動問題［31］，或稱新用戶/新項目問題，是指推薦系統中一個新用戶注冊或一個新項目產生時引起的問題。冷啟動問題是稀疏性問題的特殊情況，即新用戶/項目注冊，系統沒有該用戶的訪問記錄，從而也無法使用用戶評價矩陣對其進行推薦。在實際的推薦系統中，特別是新上線的推薦系統，由于用戶的增長，冷啟動問題表現更為突出。

4.3 當前位置與常居地距離問題

當前位置與常居地距離問題是指當用戶遠離其常居地(經常簽到的區域)時，推薦系統不能準確向其推薦當前位置附近的興趣點的問題［28］。由于推薦系統通常會使用用戶的簽到歷史采用協同過濾的方式進行位置推薦，一旦用戶遠離常居地，則再利用用戶的簽到歷史對其進行位置推薦，會使得推薦位置仍在常居地附近，與用戶當前所在位置相距較遠，推薦的興趣點顯然滿足不了用戶的實際需求。

4.4 連續性的序列位置推薦問題

很多情況下用戶需要獲得連續性的序列位置推薦［1，8］，比如當用戶去“窮游”或“自駕游”的時候。此時用戶對自己所處的城市或景區并不十分了解，而通過旅行社或者網絡獲取的旅游信息往往不能滿足用戶個性化的旅行需求。因此，綜合考慮景點的類型、訪問景點的時間限制、用戶個人游覽時間以及游覽偏好等信息為用戶進行旅游規劃等問題亟待解決。

4.5 團體下的位置推薦問題

人們在組織活動中通常以團體為單位。當人們在進行團體活動的時候，往往需要考慮大多數人的意愿來進行活動的規劃。目前的位置推薦通常是對單個人進行的，對團體情況下的位置推薦鮮少涉及，難以滿足人們此種情況下的需求。團體下的位置推薦某種程度上可以看作是個人位置推薦問題的聚合，通過把個人位置推薦的結果進行整合和排序作為團體下的位置推薦方案。但這只是一種解決方案，實際中團體情況下的位置推薦需要考慮更多的因素。

5 未來研究方向

目前位置推薦多采用基于用戶的協同過濾方法，考慮的影響因素通常為用戶信息、位置信息、用戶當前位置與興趣點位置距離、用戶訪問歷史以及用戶好友信息等，對于位置的屬性信息以及時間信息利用得并不充分，而且基于協同過濾的方法有較大的數據稀疏性問題和冷啟動問題。因此，位置推薦還有很多問題值得研究:

1)用戶相似度計算方法:將城市(全球)進行格網劃分，將興趣點映射到格網中，利用格網對用戶歷史簽到位置進行軌跡建模，利用用戶簽到的軌跡信息計算用戶相似度。

2)位置推薦混合模型:綜合利用用戶、位置屬性和標簽信息以及用戶評分信息，綜合考慮用戶的社交屬性、所處地理區域以及時間等因素，即采用混合模型方式進行位置推薦。

3)位置推薦與位置預測融合:傳統位置推薦中只是對用戶未到過的位置(新位置)進行推薦，沒有考慮用戶去過的地方。實際上，用戶需求不只是新位置，用戶曾經到過的地方其實也可能是用戶想去的地方。

6 結論

地理社交網絡的興起，使得人們在虛擬世界可以與現實世界聯系起來，方便了人們的溝通與交流，大大方便了人們的出行。地理社交網絡中的位置推薦，已經成為人們研究的一個熱點。本文綜述了地理社交網絡位置推薦的概念、研究現狀、采用的方法、面臨的問題和未來的研究方向。盡管目前在位置推薦方面已經有許多的研究成果，但總的來說，位置推薦仍然處于剛起步的階段，尚有許多亟待解決的問題。

References)

［1］Gao H J.Personalized POI recommendation on location-based social networks［D］.USA:Arizona State University，2014.

［2］劉乾.基于社交網絡和地理位置信息的好友推薦方法研究［D］.杭州:浙江大學，2013.LIU Qian.Fiend recommendation based on social network and location information［D］.Hangzhou:Zhejiang University，2013.(in Chinese)

［3］Bao J，Zheng Y，Wilkie D，et al.Recommendations in location-based social networks:a survey［J］.GeoInformatica，2015，19(3):525-565.

［4］Zhang JD，Chow C Y，Zheng Y.ORec:an opinion-based point-of-interest recommendation［C］//Proceedings of the 24th ACM International Conference on Information and Knowledgement，ACM，2015:1641-1650.

［5］Gao H，Tang J，Hu X，et al.Content-aware point of interest recommendation on location-based social networks［C］// Proceedings of the 29th Conference on Artificial Intelligence，AAAI，2015:1721-1727.

［6］連德富.基于位置社交網絡的數據挖掘［D］.合肥:中國科學技術大學，2014.LIAN Defu.Data mining on location-based social networks［D］.Hefei:University of Science and Technology of China，2014.(in Chinese)

［7］Cranshaw J，Toch E，Hong J，et al.Bridging the gap between physical location and online social networks［C］// Proceedings of the 12th ACM International Conference on Ubiquitous Computing，ACM，2010:119-128.

［8］Gionis A，Lappas T，Pelechrinis K，et al.Customized tour recommendations in urban areas［C］//Proceedings of the7th ACM International Conference on Web Search and Data Mining，ACM，2014:313-322.

［9］Cho E，Myers S A，Leskovec J.Friendship and mobility: user movement in location-based social networks［C］// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2011:1082-1090.

［10］Zheng Y，Zhou X F.Computing with spatial trajectories［M］.USA:Springer，2011.

［11］王靜金.基于位置社交網絡的個性化地點推薦算法研究［D］.廈門:廈門大學，2014.WANG Jingjin.Personalized location recommendation on location-based social networks［D］.Xiamen:Xiamen University，2014.(in Chinese)

［12］Levandoski J，SarwatM，Eldawy A，etal.LARS:a locationaware recommender system［C］//Proceedings of IEEE 28th International Conference on Data Engineering，2012:450-461.

［13］Mao Y，Yin P F，Lee W C，et al.Exploiting geographical influence for collaborative point-of-interest recommendation［C］// Proceedings of the 34th Annual ACM SIGIR Conference，ACM，2011:325-334.

［14］Quan Y，Gao C，Ma Z Y，et al.Time-aware point-of-interest recommendation［C］//Proceedings of the36th Annual ACM SIGIR Conference，ACM，2013:363-372.

［15］Li X，Xu G D，Chen E H，et al.Learning recency based comparative choice towards point-of-interest recommendation［J］.Expert Systems with Applications，2015，42(9):4274-4283.

［16］Liu B，Fu Y J，Yao Z J，et al.Learning geographical preferences for point-of-interest recommendation［C］// Proceedings of 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2013: 1043-1051.

［17］Gao H J，Tang JL，Liu H.Exploring social-historical ties on location-based social networks［C］//Proceedings of the 6th International Conference on Weblogs and Social Media，AAAI，2012:114-121.

［18］劉青文.基于協同過濾的推薦算法研究［D］.合肥:中國科學技術大學，2013.LIU Qingwen.Research on recommender systems based on collaborative filtering［D］.Hefei:University of Science and Technology of China，2013.(in Chinese)

［19］Zhou D Q，Wang B，Rahimi S，et al.A study of recommending locations on location-based social network by collaborative filtering［C］//Proceedings of the 25th Canadian Conference on Artificial Intelligence，Springer，2012:255-266.

［20］Ye M，Janowicz K，LeeW，et al.What you are is when you are:the temporal dimension of feature types in location-based social networks［C］//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，ACM，2011:102-111.

［21］Ye M，Yin P，Lee W C.Location recommendation for location-based social networks［C］//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，ACM，2010:458-461.

［22］Zhang J D，Chow C Y.iGSLR:personalized geo-social location recommendation:a kernel density estimation approach［C］//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，ACM，2013:324-333.

［23］Gao H J，Tang J L，Liu H.Mobile location prediction in spatio-temporal context［C］//Proceedings of Nokia Mobile Data ChallengeWorkshop，2012.

［24］Noulas A，Scellato S，Lathia N，etal.A random walk around the city:new venue recommendation in location-based social networks［C］//Proceedings of the IEEE International Conference on Social Computing，IEEE，2012:144-153.

［25］Ye M，Liu X J，Lee W C.Exploring social influence for recommendation:a generative model approach［C］// Proceedings of Annual International ACM SIGIR Conferenceon Research and Development in Information Retrieval，ACM，2012:325-334.

［26］Cheng C，Yang H Q，King I，etal.Fusedmatrix factorization with geographical and social influence in location-based social networks［C］//Proceedings of the 26th Conference on Artificial Intelligence，AAAI，2012:17-23.

［27］Gao H J，Tang JL，Hu X，et al.Modeling temporal effects of humanmobile behavior on location-based social networks［C］// Proceedings of the 22nd ACM International Conference on Information＆Knowledge Management，ACM，2013:1673-1678.

［28］Ference G，Ye M，Lee W C.Location recommendation for out-of-town users in location-based social networks［C］// Proceedings of the 22nd ACM International Conference on Information and Knowledge Management，ACM，2013:721-726.

［29］Wang H，Terrovitis M，Mamoulis N.Location recommendation in location-based social networks using user check-in data［C］//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，ACM，2013:374-383.

［30］Konstas I，Stathopoulos V，Jose JM.On social networks and collaborative recommendation［C］//Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval，ACM，2009:195-202.

［31］Long X L，Joshi J.A hits-based POI recommendation algorithm for location based social networks［C］// Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining，ACM，2013:642-647.

［32］Zhou K，Yang SH，Zha H Y.Functionalmatrix factorizations for cold-start recommendation［C］//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval，ACM，2011:315-324.

［33］Yu Y H，Chen X G.A survey of point-of-interest recommendation in location-based social networks［C］// Proceedings of the 29th Conference on Artificial Intelligence，AAAI，2015:53-60.

［34］Cheng C，Yang H Q，Lyu M R，et al.Where you like to go next:successive point-of-interest recommendation［C］// Proceedings of the Twenty-third International Joint Conference on Artificial Intelligence，AAAI，2013:2605-2611.

［35］Gao H J，Tang JL，Hu X，et al.Exploring temporal effects for location recommendation on location-based social networks［C］//Proceedings of the 7th ACM Conference on Recommender Systems，ACM，2013:93-100.

［36］Berjani B，Strufe T.A recommendation system for spots in location-based online social networks［C］//Proceedings of the 4th Workshop on Social Networks，Article，ACM，2011.

［37］Yang D Q，Zhang D Q，Yu Z Y，et al.A sentimentenhanced personalized location recommendation system［C］// Proceedings of the 24th ACM Conference on Hypertext and Social Media，ACM，2013:119-128.

［38］Ramaswamy L，Deepak P，Polavarapu R，et al.Caesar:a context-aware，social recommender system for low-end mobile devices［C］//Proceedings of the 10th International Conference on Mobile Data Management:Systems，Services and Middleware，IEEE，2009:338-347.

［39］Adomavicius G，Tuzhilin A.Context-aware recommender systems［C］//Proceedings of the 2008 ACM Conference on Recommender Systems，ACM，2008:217-253.

［40］Yin H Z，Sun Y Z，CuiB，etal.LCARS:a location-contentaware recommender system［C］//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2013:221-229.

［41］Hu B，Ester M.Spatial topicmodeling in online socialmedia for location recommendation［C］//Proceedings of the 7th ACM Conference on Recommender Systems，ACM，2013: 25-32.

［42］Hu B，Ester M.Social topic modeling for point-of-interest recommendation in location-based social networks［C］// Proceedings of the IEEE International Conference on Data Mining，IEEE，2014:845-850.

［43］Leung KW T，Lee D L，LeeW C.Clr:a collaborative location recommendation framework based on co-clustering［C］// Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval，ACM，2011:305-314.

［44］Nunes I，Marinho L.A personalized geographic-based diffusion model for location recommendations in LBSN［C］// Proceedings of the 9th Latin American Web Congress，IEEE，2014:59-67.

［45］Liu B，Xiong H.Point-of-interest recommendation in location based social networks with topic and location awareness［C］// Proceedings of the 2013 SIAM International Conference on Data Mining，SIAM，2013:396-404.

［46］Symeonidis P，Krinis A，Manolopoulos Y.GeoSocialRec: explaining recommendations in location-based social networks［C］//Proceedings of the 17th East European Conference，ADBIS 2013，Springer，2013:84-97.

Location recommendation on location-based social networks

JING Ning，WANG Yuehua，ZHONG Zhinong，WU Ye
(College of Electronic Science and Engineering，National University of Defense Technology，Changsha 410073，China)

Location-based social networks，which add geo-information into traditional social networks，link people’s virtual and real world lives.As an important application of location-based social networks，location recommendation can recommend places that peoplemay be interested in，provide choices for people’s out-going and make people’s livesmuch more convenient.Against this background，the relevant concepts of location recommendation，the methods it usually uses，data sets it deals with，evaluation methods for recommendation effectiveness and the problems it faceswere delved and the future possible research directionswere forecasted，hoping to providemore useful reference for researches in relevant fields.

location-based social networks；location recommendation；collaborative filtering；data sparsity；cold start

TP393

A

1001-2486(2015)05-001-08

10.11887/j.cn.201505001

http://journal.nudt.edu.cn

2015-07-01

高性能GIS關鍵技術與軟件系統(2015AA123901)

景寧(1963—)，男，重慶人，教授，博士，博士生導師，E-mail:ningjing@nudt.edu.cn