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

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

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

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

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

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

隨著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)還是室外都很容易通過智能移動(dòng)設(shè)備獲取他們自身的物理位置［1］，基于位置的服務(wù)也逐漸普及起來［2］。社交網(wǎng)絡(luò)和基于位置的服務(wù)的融合促成了地理社交網(wǎng)絡(luò)，即基于位置的社交網(wǎng)絡(luò)［3］(Location-Based Social Network，LBSN)，如國(guó)外的Foursquare，Yelp，F(xiàn)acebook Place，國(guó)內(nèi)的街旁網(wǎng)、點(diǎn)評(píng)網(wǎng)等的誕生。在地理社交網(wǎng)絡(luò)中，人們不但可以進(jìn)行信息交互，還可以分享博客、視頻、圖像等信息［4-6］，尤其是用戶與好友分享訪問過的位置及相關(guān)社交信息，使得人們?cè)谔摂M網(wǎng)絡(luò)中的行為與現(xiàn)實(shí)世界所處位置聯(lián)系起來［7］，加強(qiáng)了人們之間的交流與溝通。

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

1 問題描述

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

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

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

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

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ò)帶來了一些獨(dú)特的性質(zhì):

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

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

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

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

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

1.3 位置推薦

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

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

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

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

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

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

2 位置推薦方法

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

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

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

2.1.1 基于記憶的方法

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

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

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

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

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

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

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

2.1.2 基于模型的方法

基于模型的方法［1，6，31］的基本思想是采用機(jī)器學(xué)習(xí)技術(shù)，建立相關(guān)的學(xué)習(xí)模型(如聚類模型、貝葉斯網(wǎng)絡(luò)模型等)，利用評(píng)價(jià)矩陣中的信息進(jìn)行訓(xùn)練得到模型系數(shù)，然后利用該模型對(duì)推薦結(jié)果進(jìn)行預(yù)測(cè)。基于模型的方法最常用的是基于矩陣分解的方法［32-34］。

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

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

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

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

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

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

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

2.3 混合模型的位置推薦

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

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

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

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

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

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

3.2 評(píng)估方法

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

3.2.1 用戶調(diào)查法

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

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

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

式中，U為用戶集。

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

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

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

3.2.3 平均精度均值

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

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

3.2.4 交叉驗(yàn)證法

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

3.2.5 時(shí)間分割法

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

4 位置推薦面臨的問題

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

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

4.2 冷啟動(dòng)問題

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

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

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

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

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

4.5 團(tuán)體下的位置推薦問題

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

5 未來研究方向

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

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

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

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

6 結(jié)論

地理社交網(wǎng)絡(luò)的興起，使得人們?cè)谔摂M世界可以與現(xiàn)實(shí)世界聯(lián)系起來，方便了人們的溝通與交流，大大方便了人們的出行。地理社交網(wǎng)絡(luò)中的位置推薦，已經(jīng)成為人們研究的一個(gè)熱點(diǎn)。本文綜述了地理社交網(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］.合肥:中國(guó)科學(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ò)的個(gè)性化地點(diǎn)推薦算法研究［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］.合肥:中國(guó)科學(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