地理社交網(wǎng)絡(luò)位置推薦*

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

地理社交網(wǎng)絡(luò)位置推薦*

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

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

地理社交網(wǎng)絡(luò)；位置推薦；協(xié)同過濾；數(shù)據(jù)稀疏性；冷啟動

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

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

1 問題描述

1.1 地理社交網(wǎng)絡(luò)

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

圖1 地理社交網(wǎng)絡(luò)結(jié)構(gòu)［10］Fig.1 Structure of LBSN

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

1.2 地理社交網(wǎng)絡(luò)數(shù)據(jù)

地理社交網(wǎng)絡(luò)數(shù)據(jù)除具有傳統(tǒng)社交網(wǎng)絡(luò)中的好友關(guān)系外，還引入了位置信息。位置信息將用戶在網(wǎng)絡(luò)中的行為與物理世界聯(lián)系起來。位置信息的引入為地理社交網(wǎng)絡(luò)帶來了一些獨特的性質(zhì):

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

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

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

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

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

1.3 位置推薦

下面給出位置推薦一些相關(guān)的定義。

定義1(興趣點，POI)一個興趣點就是一個用戶可能覺得有用或有趣的具體位置，可用一個唯一的字符串標(biāo)志。其對應(yīng)現(xiàn)實世界的一個具體位置，記為l={ID，(latitude，longitude)，category}，其中ID為興趣點唯一標(biāo)志，(latitude，longitude)為興趣點的經(jīng)緯度，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)內(nèi)，用戶u的簽到集合，記為Cu，(ts，te)=≤teand cu·t＞ts}，其中ts表示起始時間，te表示結(jié)束時間。

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

2 位置推薦方法

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

2.1 基于協(xié)同過濾的位置推薦

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

2.1.1 基于記憶的方法

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

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

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

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

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

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

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

2.1.2 基于模型的方法

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

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

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

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

2.2 基于內(nèi)容的位置推薦

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

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

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

2.3 混合模型的位置推薦

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

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

3 數(shù)據(jù)集與推薦效果評估方法

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

地理社交網(wǎng)絡(luò)有很多的數(shù)據(jù)集，像Foursquare和Gowalla等。很多的數(shù)據(jù)集從網(wǎng)絡(luò)中都可以獲取到。表2列舉了幾個比較有代表性的數(shù)據(jù)集。

表2 地理社交網(wǎng)絡(luò)數(shù)據(jù)集Tab.2 Datasets of LBSNs

3.2 評估方法

位置推薦系統(tǒng)的推薦效果如何通常需要進(jìn)行評估。常用的評估方法如下。

3.2.1 用戶調(diào)查法

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

3.2.2 準(zhǔn)確率(precision)和召回率(recall)

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

式中，U為用戶集。

推薦結(jié)果的準(zhǔn)確率定義為:

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

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

3.2.3 平均精度均值

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

式中，N是測試數(shù)據(jù)集中用戶的數(shù)量，cu是與用戶u相關(guān)的用戶的數(shù)量，precisionu@k是用戶u的推薦列表中推薦項目為k時的準(zhǔn)確率。

3.2.4 交叉驗證法

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

3.2.5 時間分割法

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

4 位置推薦面臨的問題

4.1 數(shù)據(jù)稀疏性問題

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

4.2 冷啟動問題

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

4.3 當(dāng)前位置與常居地距離問題

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

4.4 連續(xù)性的序列位置推薦問題

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

4.5 團體下的位置推薦問題

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

5 未來研究方向

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

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

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

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

6 結(jié)論

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

References)

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

［2］劉乾.基于社交網(wǎng)絡(luò)和地理位置信息的好友推薦方法研究［D］.杭州:浙江大學(xué)，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］連德富.基于位置社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘［D］.合肥:中國科學(xué)技術(shù)大學(xué)，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］王靜金.基于位置社交網(wǎng)絡(luò)的個性化地點推薦算法研究［D］.廈門:廈門大學(xué)，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，F(xiàn)u 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］劉青文.基于協(xié)同過濾的推薦算法研究［D］.合肥:中國科學(xué)技術(shù)大學(xué)，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關(guān)鍵技術(shù)與軟件系統(tǒng)(2015AA123901)

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