焦 旭 肖迎元 鄭文廣 朱 珂

1(天津市智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室(天津理工大學(xué)) 天津 300384)2(計(jì)算機(jī)視覺與系統(tǒng)省部共建教育部重點(diǎn)實(shí)驗(yàn)室(天津理工大學(xué)) 天津 300384)3(天津外國語大學(xué)基礎(chǔ)課教學(xué)部 天津 300204)

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)、定位技術(shù)和無線傳感技術(shù)的飛速發(fā)展以及智能手機(jī)的不斷普及，基于位置的社會(huì)化網(wǎng)絡(luò)(location-based social networks, LBSNs)及其帶來的應(yīng)用服務(wù)應(yīng)運(yùn)而生,并得到了迅速的發(fā)展.目前比較流行的LBSNs有Foursquare,Gowalla,Facebook Place,Microsoft GeoLife,Bikely,Flickr,Panotamio、微信朋友圈等.其中，以Foursq-uare，Gowalla，F(xiàn)acebook Place為代表的LBSNs主要提供對(duì)興趣點(diǎn)的簽到(check-in)服務(wù)，鼓勵(lì)用戶分享其當(dāng)前位置，通過對(duì)用戶共享位置信息的分析為用戶推薦感興趣的位置和社交活動(dòng)；而以Microsoft GeoLife，Bikely為代表的LBSNs則主要記錄和分享用戶出行軌跡，提供和用戶軌跡相關(guān)的一些信息，諸如軌跡的總時(shí)長、在一個(gè)位置的駐留時(shí)長、速度、海拔和一些相應(yīng)的距離等，同時(shí)還可以展示用戶在軌跡旅程中的留言、標(biāo)簽、照片等以此來反映用戶的旅行經(jīng)驗(yàn)和經(jīng)歷以供其他用戶參考；以Flickr,Panotamio、微信朋友圈為代表的LBSNs主要是把位置信息作為一個(gè)標(biāo)簽嵌入到照片、視頻、文本等媒體信息當(dāng)中，在此類LBSNs中位置信息只作為一個(gè)新的維度被嵌入到媒體信息當(dāng)中，服務(wù)的主體仍然是媒體信息.

LBSNs中蘊(yùn)含著大量而豐富的信息，在一個(gè)LBSN中，用戶所關(guān)注的可能是某些地點(diǎn)、某些人或某些活動(dòng).針對(duì)用戶的興趣所在，為用戶提供基于位置的個(gè)性化推薦服務(wù)(基于位置的社會(huì)化網(wǎng)絡(luò)推薦服務(wù))，已成為當(dāng)前LBSNs的一項(xiàng)重要服務(wù)，得到工業(yè)界和學(xué)術(shù)界的廣泛重視，正成為推薦系統(tǒng)和社會(huì)化網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)新的研究熱點(diǎn).

1 基于位置的社會(huì)化網(wǎng)絡(luò)概述

LBSNs不僅意味著在現(xiàn)有社會(huì)化網(wǎng)絡(luò)中添加位置信息以使用戶在社交結(jié)構(gòu)中分享嵌入的位置信息，而且包括由他們?cè)诂F(xiàn)實(shí)世界中的物理位置以及他們位置標(biāo)簽媒體的內(nèi)容(例如照片、視頻和文本)產(chǎn)生的相依性連接的用戶所組成的新的社交結(jié)構(gòu)[1]，這里的物理位置由用戶在給定時(shí)間戳的瞬時(shí)位置以及用戶在特定時(shí)間段中累積的位置歷史所組成.此外，這種相依性不僅包括2個(gè)人同時(shí)出現(xiàn)在相同的物理位置或分享了相似的位置歷史，而且還包括了從用戶的位置(歷史)和位置標(biāo)簽數(shù)據(jù)推斷出的諸如共同興趣、行為和活動(dòng)的知識(shí).

通過對(duì)LBSNs的深入理解可以發(fā)現(xiàn)該網(wǎng)絡(luò)是一個(gè)異構(gòu)網(wǎng)絡(luò)，其中存在著位置與用戶2種不同屬性的節(jié)點(diǎn).根據(jù)這2種不同屬性的節(jié)點(diǎn)，基于位置的社會(huì)化網(wǎng)絡(luò)存在著3種關(guān)系：位置與位置的關(guān)系、用戶與用戶的關(guān)系、位置與用戶的關(guān)系.同時(shí)對(duì)應(yīng)于這3種關(guān)系還存在著3種不同的距離：位置與位置間的距離、用戶與用戶間的距離(指用戶當(dāng)前位置間的距離)、用戶與位置間的距離(指用戶的當(dāng)前位置與某一位置間的距離).在LBSNs中位置與位置間的距離直接反映著2個(gè)位置間的相關(guān)程度，例如多家大學(xué)就近而形成大學(xué)城、多家企業(yè)就近而形成工業(yè)園、多家商場比鄰而形成商業(yè)中心；用戶與用戶間的距離則可以反映出2個(gè)用戶之間的相似性，例如2個(gè)用戶各自的出行軌跡中的多個(gè)興趣點(diǎn)都比較接近即軌跡的相似性較高就說明這2個(gè)用戶具有相似的興趣偏好或出行模式；用戶與位置間的距離直接影響到用戶對(duì)該位置的訪問概率，例如一個(gè)用戶去超市購物一般都會(huì)選擇距離其較近的一個(gè)，文獻(xiàn)[2]基于Foursquare的簽到數(shù)據(jù)做出了關(guān)于用戶活動(dòng)模式的實(shí)證研究，研究表明用戶的簽到行為有20%是發(fā)生在1 km范圍內(nèi)的，60%是發(fā)生在1～10 km范圍內(nèi)的，20%是發(fā)生在10～100 km范圍內(nèi)的，5%是發(fā)生在100 km以外的，符合冪律分布，即較近的位置擁有較高的訪問概率，這也與Tobler地理學(xué)第一定律(任何事物都是相關(guān)的，只是相近的事物關(guān)聯(lián)更緊密)認(rèn)為人類行為與所在地區(qū)有絕對(duì)的影響，此種影響隨著距離的增大而遞減是完全一致的.由此我們也可以看到在LBSNs中位置與用戶相互依存緊密聯(lián)系，在研究位置的同時(shí)無法割裂用戶對(duì)其的訪問行為，而在研究用戶的同時(shí)也無法忽視其在不同時(shí)間所處的地理位置.

位置還具有其自身的獨(dú)特屬性，首先，位置是具有粒度屬性的.例如對(duì)一家購物超市來說，它位于某個(gè)商業(yè)中心，這個(gè)商業(yè)中心屬于某個(gè)區(qū)，這個(gè)區(qū)又屬于某個(gè)城市，這個(gè)城市又屬于某個(gè)省份，也就是說描述該購物超市的位置可采用不同的粒度：某商業(yè)中心→某區(qū)→某城市→某省.我們?cè)诓煌牧６壬险劶坝脩舴窒淼奈恢秒[含的效果是不同的，例如一個(gè)用戶去了天安門，另一個(gè)用戶去了故宮博物院，在這個(gè)細(xì)粒度下我們可以推斷2人都到過北京的歷史古跡，2人都偏好旅游且都喜歡游覽歷史古跡，2人具有極高的相似性，而如果換作是省份這一級(jí)的粗粒度，我們僅能知道2人都到過北京，其推斷出的2人的相似性就大打折扣了.其次位置還具有順序性，例如一條東西向的街道上自東向西依次有A，B，C這3個(gè)興趣點(diǎn)，自駕用戶們的訪問順序都是由A到B再到C，說明這條街道極有可能是一條單行路.

2 基于位置的社會(huì)化網(wǎng)絡(luò)推薦所面臨的挑戰(zhàn)

推薦系統(tǒng)作為有效解決“信息過載”的重要工具早已為用戶所熟悉，尤其是在電子商務(wù)方面，推薦系統(tǒng)的使用既為企業(yè)帶來了經(jīng)濟(jì)效益也大大方便了用戶，例如商品推薦領(lǐng)域的淘寶、Amazon，電影推薦領(lǐng)域的豆瓣、Netflix，音樂推薦領(lǐng)域的Last.fm，新聞推薦更是在各大門戶網(wǎng)站廣泛使用.相較于基于互聯(lián)網(wǎng)的傳統(tǒng)推薦而言，由于LBSNs中用戶與位置關(guān)系的相依性以及位置的獨(dú)特屬性，使得LBSNs的推薦變得更加復(fù)雜，存在諸多不同于傳統(tǒng)推薦的困難與挑戰(zhàn)，具體表現(xiàn)如下：

1) 在傳統(tǒng)推薦中，通常根據(jù)用戶的歷史行為建模其偏好從而為他推薦物品，比如一個(gè)用戶曾經(jīng)購買過食譜方面的書籍，通常表明他可能偏愛美食做飯，自然就應(yīng)該向其推薦烹飪類的最新書籍，但是在LBSNs中卻不一定如此，比如一個(gè)廣東的用戶偏好健身，但當(dāng)他出現(xiàn)在天安門廣場時(shí)，我們給他的推薦列表中排在前列的應(yīng)該是人民大會(huì)堂、英雄紀(jì)念碑、天安門、故宮博物院等，而不會(huì)是某個(gè)健身房或體育館，因?yàn)樗幍奈恢眯畔?情境)告訴我們?cè)撚脩舻搅吮本┑奶彀查T廣場應(yīng)該是來旅游的.

2) 在LBSNs中需要根據(jù)推薦對(duì)象的不同選擇不同的位置粒度，比如要做興趣點(diǎn)推薦，就需要選擇較細(xì)的粒度，細(xì)到餐館、影院這個(gè)級(jí)別，而如果做新聞推薦，位置粒度的選擇可以適當(dāng)粗一點(diǎn).

3) 在推薦興趣點(diǎn)時(shí)還要考慮順序性，比如在給用戶做旅程規(guī)劃時(shí)應(yīng)根據(jù)具體的起點(diǎn)和終點(diǎn)位置順序推薦它們之間的興趣點(diǎn)，避免讓用戶來回奔波；此外，如果推薦的多個(gè)興趣點(diǎn)在同一單行路上時(shí)更應(yīng)避免給自駕用戶帶來困擾.

4) 在傳統(tǒng)推薦中，用戶顯式地表達(dá)自己對(duì)物品的偏好，例如目前采用較多的是5分制評(píng)分，評(píng)分由1～5分表達(dá)了用戶對(duì)物品從很不感興趣到很偏愛的程度，換言之一個(gè)用戶對(duì)物品的評(píng)價(jià)都集中1～5分這個(gè)范圍內(nèi)，然后可以把用戶對(duì)物品的評(píng)分情況轉(zhuǎn)換為一個(gè)用戶物品矩陣.但是在LBSNs中則不然，用戶對(duì)地點(diǎn)的偏好是隱式地通過訪問頻率表達(dá)的，用戶對(duì)某一地點(diǎn)訪問的次數(shù)越多說明其偏愛此地的程度越高；其次相較于用戶對(duì)物品的評(píng)分，用戶的訪問頻率沒有固定的數(shù)值范圍，比如有的用戶對(duì)某一位置的訪問頻率可能多達(dá)幾百次，而其他用戶僅有一兩次；此外，將用戶對(duì)興趣點(diǎn)的訪問頻次轉(zhuǎn)換為一個(gè)用戶-興趣點(diǎn)簽到矩陣后可以發(fā)現(xiàn)與傳統(tǒng)推薦中的用戶-物品矩陣相比是極度稀疏的，因?yàn)閷?duì)于一個(gè)用戶來說面對(duì)現(xiàn)實(shí)世界成千上萬的興趣點(diǎn)其去過的畢竟是少數(shù)，例如根據(jù)Foursquare用戶的Twitter報(bào)告，文獻(xiàn)[3]最終確定了一個(gè)包含12 422個(gè)用戶、46 194個(gè)興趣點(diǎn)與738 445個(gè)簽到行為的數(shù)據(jù)集，其對(duì)應(yīng)的用戶-興趣點(diǎn)簽到矩陣的稀疏程度達(dá)到了99.87%，可以說是極度稀疏了，平均每個(gè)用戶簽到59.44個(gè)興趣點(diǎn)，僅是興趣點(diǎn)總數(shù)極小的一部分，同時(shí)對(duì)興趣點(diǎn)的簽到頻率數(shù)值范圍為1～786.

5) 用戶的社會(huì)屬性對(duì)用戶簽到行為的影響：傳統(tǒng)推薦根據(jù)用戶的最近鄰來對(duì)其進(jìn)行推薦，最具代表性的方法就是基于用戶的協(xié)同過濾算法，并且取得了不錯(cuò)的效果.然而文獻(xiàn)[4]的研究表明，在LBSNs中大約96%的朋友分享少于10%的常訪問地點(diǎn)，并且87.7%的用戶什么都不分享.由于大多數(shù)的朋友不分享常訪問地點(diǎn)，這就意味著不是所有的社交朋友都有助于進(jìn)行位置推薦，這也就說明了用戶的社會(huì)屬性對(duì)用戶簽到行為的影響是有限的.同時(shí)作者還發(fā)現(xiàn)，距離較近的朋友有較高的分享常訪問位置的概率，這是因?yàn)樗麄兏菀讌⑴c到相同位置的活動(dòng)當(dāng)中.這也印證了LBSNs中的用戶的社交活動(dòng)(訪問興趣點(diǎn))很大程度上受地理接近度的影響.

6) 與傳統(tǒng)推薦相比，在LBSNs中用戶本身的屬性及其所處的情境都會(huì)對(duì)推薦結(jié)果產(chǎn)生重要的影響.比如用戶的年齡、性別、收入、職業(yè)、當(dāng)前的位置、心情、當(dāng)前時(shí)間、天氣、交通情況等，因?yàn)橛脩舻钠脮?huì)隨著情境的改變而改變.同時(shí)用戶的偏好也是有粒度的，比如：一個(gè)用戶偏好旅游→偏好城市旅游→偏好參觀各大城市的博物館.因此，在LBSNs中如何融合各方面的情境來提高推薦的質(zhì)量是一個(gè)挑戰(zhàn).

3 基于位置的社會(huì)化網(wǎng)絡(luò)推薦核心技術(shù)

本節(jié)分別從推薦對(duì)象、推薦方法和評(píng)價(jià)方法3方面全面地介紹基于位置的社會(huì)化網(wǎng)絡(luò)推薦相關(guān)技術(shù).

3.1 推薦對(duì)象

在LBSNs中包含各種不同的推薦對(duì)象，本文將推薦對(duì)象劃分為4類：位置(興趣點(diǎn))、朋友、本地專家、活動(dòng)，其中位置和朋友的推薦又根據(jù)使用數(shù)據(jù)集類型的不同進(jìn)行分類介紹.

3.1.1 位置推薦

位置推薦又可分為興趣點(diǎn)推薦和旅程規(guī)劃(興趣點(diǎn)軌跡推薦)，目前的位置推薦主要使用用戶在LBSNs中的簽到(check-in)數(shù)據(jù)集或用戶GPS軌跡數(shù)據(jù)集.check-in數(shù)據(jù)集包含了帶有語義信息的興趣點(diǎn)以及豐富的用戶屬性與興趣點(diǎn)屬性，同時(shí)還包含用戶間的好友關(guān)系，因此成為許多研究人員的首選，但是用戶簽到行為的極度稀疏也是check-in數(shù)據(jù)集無法回避的問題.相較于check-in數(shù)據(jù)的極度稀疏，GPS軌跡數(shù)據(jù)集則不存在這個(gè)問題，其包含了用戶軌跡的總時(shí)長、用戶在一個(gè)位置的駐留時(shí)長、速度、海拔和一些相應(yīng)的距離等地理信息，但要使用GPS軌跡數(shù)據(jù)集的首要工作就是需要研究人員從軌跡數(shù)據(jù)中挖掘出興趣點(diǎn)的地理信息；此外，如何匹配這些挖掘出來的興趣點(diǎn)的語義信息，也是一項(xiàng)充滿挑戰(zhàn)的任務(wù).以下將按照使用數(shù)據(jù)集的不同詳細(xì)介紹.

1) 使用check-in數(shù)據(jù)集的位置推薦

用戶的簽到(check-in)行為往往會(huì)受到地理、時(shí)間、順序、社會(huì)、評(píng)論等多方面因素的影響，本文將從這5個(gè)角度分別介紹.

① 地理影響

地理影響對(duì)興趣點(diǎn)推薦是極其重要的，可以說這是其區(qū)別于傳統(tǒng)推薦最根本的特征，由于用戶的簽到行為呈現(xiàn)出空間聚類現(xiàn)象，可以用冪律分布、高斯分布、泊松分布、核密度估計(jì)的方法來建模地理影響.文獻(xiàn)[5]使用冪律分布來模擬被同一用戶訪問的2個(gè)興趣點(diǎn)的簽到概率y:

y=axb，

(1)

其中，x表示2個(gè)興趣點(diǎn)之間的距離，a和b為冪律分布的參數(shù)，可以利用觀測到的簽到數(shù)據(jù)使用線性擬合的方法獲得.文獻(xiàn)[6]發(fā)現(xiàn)在LBSNs中用戶的簽到數(shù)據(jù)具有2個(gè)獨(dú)特屬性：1)用戶趨向于圍繞著幾個(gè)中心進(jìn)行簽到，在每一個(gè)中心用戶的簽到行為是符合高斯分布的，如圖1所示；2)盡管不同的用戶對(duì)興趣點(diǎn)有著不盡相同的口味，但是一個(gè)用戶訪問一個(gè)位置的概率與其距最近中心的距離成反比，如圖2所示.這就暗示著如果一個(gè)興趣點(diǎn)距離用戶所在的位置較遠(yuǎn)，盡管用戶喜歡該處，但是也很有可能不會(huì)去.基于以上2個(gè)特點(diǎn)，文獻(xiàn)[6]使用高斯分布來建模用戶的簽到行為并且提出了多中心高斯模型(MGM).當(dāng)給定了多中心集合Cu(1≤u≤M)，用戶u訪問興趣點(diǎn)l(一個(gè)位置的經(jīng)度和緯度)的概率：

(2)

Fig. 1 A typical user’s multi-center check-in behavior[6]圖1 典型用戶多中心簽到行為[6]

Fig. 2 Check-ins probability vs. distance[6]圖2 距離相關(guān)的簽到概率[6]

(3)

其中,li=(lati,loni)T是一個(gè)經(jīng)度和緯度組成的2維列向量，K(·)是一個(gè)核函數(shù)，用式(4)表示，σ是一個(gè)平滑參數(shù)稱為帶寬，式(5)給出了其計(jì)算方法:

(4)

(5)

給定Lu={l1,l2,…,ln}，用戶u訪問新位置l的概率表示為

p(l|Lu)=

(6)

實(shí)驗(yàn)表明CoRe方法的準(zhǔn)確性和效率均優(yōu)于冪律分布、多中心高斯分布和iGSLR.文獻(xiàn)[9]對(duì)固定帶寬的核密度估計(jì)進(jìn)行改進(jìn)，采用決策的方法自適應(yīng)當(dāng)?shù)貛捯踩〉昧瞬诲e(cuò)的效果.

文獻(xiàn)[10]認(rèn)為高斯分布更適合于建模用戶的評(píng)分行為而不是用戶的簽到行為，而泊松分布擬合簽到頻率數(shù)據(jù)好于高斯分布，提出了基于Ranking的泊松矩陣分解興趣點(diǎn)推薦算法.首先，為了更加準(zhǔn)確地捕獲用戶對(duì)興趣點(diǎn)的偏好，使用泊松分布來建模用戶的簽到行為；其次，為解決興趣點(diǎn)推薦中的隱式反饋問題，利用BPR(Bayesian personalized ranking)標(biāo)準(zhǔn)來優(yōu)化泊松矩陣分解的損失函數(shù)；最后，為了進(jìn)一步改進(jìn)推薦算法的性能，利用包含地域影響力的正則化因子約束泊松矩陣分解過程.

② 時(shí)間影響

在傳統(tǒng)的推薦中，時(shí)間影響力是逐步衰減的，比如新聞或者電影都會(huì)隨著時(shí)間的推移其熱度大大衰減.在LBSNs中，可以為某一具體的時(shí)間狀態(tài)進(jìn)行興趣點(diǎn)推薦，時(shí)間影響對(duì)于興趣點(diǎn)推薦的重要作用主要表現(xiàn)在用戶簽到行為的時(shí)間周期性和時(shí)間非均勻性2個(gè)方面.

用戶簽到行為具有時(shí)間周期性是指用戶通常在相同的時(shí)間區(qū)間內(nèi)會(huì)去訪問相同或者相似的興趣點(diǎn).例如人們通常白天去圖書館，傍晚去餐館，夜晚去酒吧，工作日通常在辦公地點(diǎn)周圍活動(dòng)，周末通常會(huì)去購物中心或者公園.用戶簽到行為具有時(shí)間的非均勻性通常是指用戶的簽到偏好在1 d中的不同時(shí)間、1周中的不同日子、1年中的不同月份是存在差異的.文獻(xiàn)[11-17]分別利用時(shí)間影響進(jìn)行了興趣點(diǎn)推薦，大部分方法都是將1 d分割成多個(gè)時(shí)間區(qū)間，比如分成24 h，或分成上午、中午、下午、傍晚、晚間、深夜等，進(jìn)而使用協(xié)同過濾等一些推薦技術(shù)推斷用戶在每個(gè)時(shí)間區(qū)間的興趣點(diǎn)偏好.但是由于這些時(shí)間區(qū)間是離散化的，就會(huì)造成丟失一些時(shí)間信息，同時(shí)缺乏不同時(shí)間區(qū)間之間的時(shí)間影響相關(guān)性.為了克服離散化的缺陷，文獻(xiàn)[14]提出了一個(gè)概率框架來建模連續(xù)的時(shí)間影響，在向用戶推薦興趣點(diǎn)的同時(shí)也向用戶建議合適的訪問時(shí)間，該框架需要預(yù)測用戶u訪問興趣點(diǎn)l∈L在時(shí)間區(qū)間T的概率p(l|u,T,D)，其中，D為包含所有用戶訪問所有位置的簽到集合，p(l|u,T,D)的計(jì)算公式為

(7)

其中，p(l|u,D)是不依賴于時(shí)間區(qū)間T的用戶u訪問興趣點(diǎn)l的先驗(yàn)概率，可以通過任何非時(shí)間感知的方法獲得；f(t|u,l,D)是以用戶u和興趣點(diǎn)l為條件的時(shí)間概率密度，這也從本質(zhì)上利用了時(shí)間影響，對(duì)其進(jìn)行基于核密度的估計(jì)：

(8)

tΘti為這2個(gè)時(shí)刻的時(shí)間差，Su,l為估計(jì)f(t|u,l,D)的時(shí)間樣本，Wu,l(ti)為樣本點(diǎn)ti的權(quán)重.

③ 順序影響

文獻(xiàn)[18]的研究發(fā)現(xiàn)：大量的連續(xù)簽到是高度相關(guān)的，超過40%和60%的連續(xù)簽到行為分別發(fā)生在Foursquare和Gowalla中距離上一次簽到后的4 h以內(nèi).在Foursquare和Gowalla中大約90%的連續(xù)簽到發(fā)生在32 km范圍內(nèi)(0.5 h的車程).這也反映出用戶簽到行為的順序影響是時(shí)空相關(guān)的，它是時(shí)間周期性(人們通常白天去圖書館、傍晚去餐館、夜晚去酒吧)、興趣點(diǎn)在地理空間上的接近性(游客通常會(huì)先后游覽人民大會(huì)堂、英雄紀(jì)念碑、天安門、故宮博物院)、興趣點(diǎn)的屬性與人類習(xí)慣(人們通常會(huì)先去健身房再去餐館晚餐，如若相反是不利于人們的健康習(xí)慣的)共同作用的結(jié)果.為了利用這種順序影響進(jìn)行興趣點(diǎn)推薦，目前的許多方法都是假設(shè)下一個(gè)可能訪問的興趣點(diǎn)只與訪問過的最新的這個(gè)興趣點(diǎn)相關(guān)，因而可采用了一階Markov鏈進(jìn)行建模[19-21].然而在實(shí)際當(dāng)中，用戶下一個(gè)將要訪問的興趣點(diǎn)往往和其之前訪問過的所有興趣點(diǎn)都相關(guān)，為此文獻(xiàn)[22-23]提出：首先，從所有用戶的簽到位置序列中挖掘順序模式作為一個(gè)動(dòng)態(tài)的位置—位置遷移圖，位置—位置遷移圖不僅包括位置間的遷移計(jì)數(shù)，而且還包括位置到其他位置的外出計(jì)數(shù)，遷移概率通過遷移計(jì)數(shù)除以外出計(jì)數(shù)獲得；其次，在給定位置—位置遷移圖和用戶訪問過的位置序列的前提下，使用n階加法Markov鏈(additive Markov chain, AMC)預(yù)測該用戶訪問新位置的順序概率.

④ 社會(huì)影響

在傳統(tǒng)推薦中就已經(jīng)使用基于記憶[24-25]和基于模型[26-27]的方法來利用社會(huì)影響提高推薦系統(tǒng)的效果.在LBSNs中，基于朋友與非朋友相比會(huì)分享更多的共同興趣這一假設(shè)，可以借鑒傳統(tǒng)推薦的方法利用社會(huì)影響來提高興趣點(diǎn)推薦效果[4,6,22,28-32].文獻(xiàn)[4]使用了基于朋友的協(xié)同過濾(friend-based collaborative filtering, FCF)的方法進(jìn)行興趣點(diǎn)推薦.由于用戶僅僅訪問所有興趣點(diǎn)中的一小部分，協(xié)同過濾方法會(huì)被用戶—興趣點(diǎn)簽到矩陣的稀疏問題所困擾.為此文獻(xiàn)[32]利用用戶和已訪問某一興趣點(diǎn)的該用戶的朋友的社會(huì)相關(guān)性來推斷該用戶和未被訪問興趣點(diǎn)之間的相關(guān)性，整個(gè)方法包含3個(gè)步驟：社交頻率的聚集、社交頻率的分布估計(jì)、社交相關(guān)性得分的計(jì)算.

步驟1. 社交頻率的聚集.

給定用戶u和未訪問過的興趣點(diǎn)l，聚合用戶u的朋友(即u′,Su,u′=1)在興趣點(diǎn)l的簽到頻率或評(píng)分

(9)

其中，Ru′,l是用戶u′訪問興趣點(diǎn)l的頻率或評(píng)分，Su,u′表示用戶u和u′之間是否存在社交鏈接.

在現(xiàn)實(shí)世界中，社交簽到頻率隨機(jī)變量x符合冪律分布，概率密度函數(shù)被定義為

fSO(x)=(β-1)(1+x)-β,x≥0,β>1，

(10)

其中,β通過簽到矩陣R和社交鏈接矩陣S估計(jì)得到

(11)

步驟3. 社交相關(guān)性得分的計(jì)算.

1-(1+xu,l)1-β，

(12)

好，我沒能力不能代表大多數(shù)，我們假設(shè)一種極端情況，正好泳池里有100個(gè)打著游泳的幌子，專門去擼管的色狼。鑒于他們的偉大能力，我們計(jì)劃他們同時(shí)排出了6毫升精液，每毫升精液都有6000萬條精子。且不說這泳池的水會(huì)不會(huì)變渾，會(huì)不會(huì)有一種石楠花的味道，這600毫升濃濃的精液也就一可樂瓶，包含約360億個(gè)精子，被釋放到這1000立方米水中。

(13)

相應(yīng)地間接社會(huì)群體應(yīng)滿足：

(14)

⑤ 評(píng)論內(nèi)容影響

在LBSNs中以用戶對(duì)興趣點(diǎn)的訪問頻率作為用戶對(duì)興趣點(diǎn)的喜好程度的依據(jù)，而如果能夠有效利用用戶在某一時(shí)刻對(duì)某一興趣點(diǎn)的評(píng)論信息[31,34-35]，就能夠更加準(zhǔn)確地說明用戶對(duì)該興趣點(diǎn)的好惡，需要說明的是用戶對(duì)興趣點(diǎn)有過評(píng)論行為并不意味著該用戶一定喜歡該興趣點(diǎn)，因?yàn)橛脩舻脑u(píng)論有可能是負(fù)面的，所以要進(jìn)行語義分析，并量化出情感得分.文獻(xiàn)[31]首先做出了利用評(píng)論信息提高興趣點(diǎn)推薦的研究，利用用戶的簽到信息和評(píng)論信息為用戶進(jìn)行統(tǒng)一的混合偏好建模(hybrid preference model, HPM)，其中對(duì)評(píng)論信息分析的首要任務(wù)就是將評(píng)論信息轉(zhuǎn)化為情感得分.圖3展示了一個(gè)意大利餐廳的留言，圖3(a)是對(duì)留言的處理過程，使用了基于字典的無監(jiān)督情感分析方法僅對(duì)英文留言進(jìn)行了處理.首先在最開始的語言發(fā)現(xiàn)部分過濾掉非英語的留言；然后留言被劃分為句子和詞性(圖3中的POS)進(jìn)行識(shí)別，通過在SentiWordNet中查找獲取每個(gè)詞的情感得分，使用名詞短語拆分技術(shù)提取短語；將留言中的每一個(gè)詞的情感得分進(jìn)行累加并歸一化到區(qū)間[-1，1]獲得留言整體的情感得分，-1表示最負(fù)面，0表示中性，1表示最正面，圖3(b)展示了處理的結(jié)果；最后根據(jù)用戶的簽到頻率和留言的情感得分建立用戶—興趣點(diǎn)偏好矩陣.

Fig. 3 Sentiment analysis of tips[31]圖3 留言情感分析[31]

文獻(xiàn)[36]利用3個(gè)步驟處理評(píng)論信息：首先使用標(biāo)準(zhǔn)自然語言處理工具預(yù)處理所有評(píng)論數(shù)據(jù)，刪除停用字、標(biāo)點(diǎn)符號(hào)和數(shù)字后，為每個(gè)評(píng)論提取一組術(shù)語以表示它；其次通過分析評(píng)論預(yù)先定義一組主題，為每個(gè)主題決定一組種子術(shù)語；最后一個(gè)跨越多個(gè)主題的用戶興趣分布被表示為一個(gè)長度為k的向量，元素為通過聚集這個(gè)用戶所有評(píng)論的頻率得到的關(guān)于某一主題的頻率.由此用戶的簽到信息就有了極性，采用改進(jìn)的隨機(jī)游走算法使具有正面評(píng)價(jià)的興趣點(diǎn)得到更多的優(yōu)待和青睞.文獻(xiàn)[37]利用潛在狄利克雷分布對(duì)評(píng)論內(nèi)容信息進(jìn)行建模，也取得了不錯(cuò)的實(shí)驗(yàn)效果.

此外除了上述5種影響以外，在LBSNs中與興趣點(diǎn)相關(guān)的照片包含了豐富的關(guān)于興趣點(diǎn)屬性的獨(dú)特信息，比如形狀、結(jié)構(gòu)、紋理等，而這些關(guān)于興趣點(diǎn)的信息是無法從以上5種影響中獲得的.文獻(xiàn)[38]提出了利用視覺內(nèi)容進(jìn)行興趣點(diǎn)推薦的方法：首先以照片作為輸入，使用卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network, CNN)的VGG16模型對(duì)照片進(jìn)行分析獲取其視覺內(nèi)容，視覺內(nèi)容是一個(gè)長度為4 096的向量；其次基于獲取的視覺內(nèi)容，利用用戶的隱含特征區(qū)分照片是否為某一用戶所分享的，利用興趣點(diǎn)的隱含特征區(qū)分照片是否與某一興趣點(diǎn)相關(guān)聯(lián)；最后綜合利用上一步的分析結(jié)果建模照片的圖像特征.真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，該方法有效提高了興趣點(diǎn)推薦的精度.

2) 使用GPS數(shù)據(jù)集的位置推薦

相較于孤立的簽到信息，用戶產(chǎn)生的GPS軌跡數(shù)據(jù)包含了非常豐富的信息，其包含了用戶軌跡的總時(shí)長、2個(gè)位置間的訪問順序、經(jīng)過的路徑、用戶在一個(gè)位置的駐留時(shí)長、速度、海拔和一些相應(yīng)的距離等豐富的地理信息，同時(shí)避免了簽到數(shù)據(jù)的極度稀疏的問題.利用GPS軌跡數(shù)據(jù)可以進(jìn)行興趣點(diǎn)推薦[39-43]也可以進(jìn)行旅程規(guī)劃[44-45].

HITS算法[46-47]是鏈接分析中非?；A(chǔ)且重要的算法，Hub頁面(樞紐頁面)和Authority頁面(權(quán)威頁面)是HITS算法最基本的2個(gè)定義.所謂“Authority”頁面，是指與某個(gè)領(lǐng)域或者某個(gè)話題相關(guān)的高質(zhì)量網(wǎng)頁，而“Hub”頁面指的是包含了很多指向高質(zhì)量“Authority”頁面鏈接的網(wǎng)頁.HITS算法的基本思想是相互增強(qiáng)關(guān)系，其假設(shè)一個(gè)好的“Authority”頁面會(huì)被很多好的“Hub”頁面指向，同時(shí)一個(gè)好的“Hub”頁面會(huì)指向很多好的“Authority”頁面.文獻(xiàn)[39]將Hub看作一個(gè)訪問了許多興趣點(diǎn)的用戶，將Authority看作為一個(gè)被許多用戶所訪問的興趣點(diǎn)，同時(shí)假設(shè)在LBSNs中一個(gè)有經(jīng)驗(yàn)的用戶會(huì)訪問很多好的興趣點(diǎn)，一個(gè)好的興趣點(diǎn)會(huì)被很多有經(jīng)驗(yàn)的用戶所訪問，這也是一種相互增強(qiáng)關(guān)系，于是利用HITS算法可以發(fā)現(xiàn)并推薦好的興趣點(diǎn).文獻(xiàn)[40]發(fā)現(xiàn)使用原始的HITS算法存在一定的缺陷，如果一個(gè)興趣點(diǎn)僅僅被一個(gè)用戶訪問過且訪問次數(shù)很高，HITS算法也會(huì)給該興趣點(diǎn)分配一個(gè)很高的Authority得分，給該用戶分配一個(gè)很高的Hub得分，這顯然是不合理的.為此提出了在用戶位置圖上使用隨機(jī)游走的隨機(jī)化HITS模型，該模型具有對(duì)小的擾動(dòng)不敏感且比原始HITS模型穩(wěn)定的優(yōu)點(diǎn).

文獻(xiàn)[44-45]利用GPS數(shù)據(jù)集進(jìn)行了旅程規(guī)劃方面的研究，主要分為離線與在線2個(gè)部分,如圖4所示.離線部分的任務(wù)是構(gòu)建一張位置—興趣圖，分為2個(gè)步驟：

步驟1. 從GPS軌跡中發(fā)現(xiàn)駐留點(diǎn)然后將駐留點(diǎn)聚類為位置點(diǎn)生成位置圖.

步驟2. 在位置圖中利用文獻(xiàn)[39]提出的HITS方法推斷每一個(gè)位置的興趣值并且計(jì)算出每一個(gè)2長度的旅行序列的流行度得分，最終生成位置—興趣圖.

Fig. 4 Architecture of social itinerary recommender[45]圖4 社會(huì)旅程推薦構(gòu)架[45]

Fig. 5 Framework for modeling users location history in geographical spaces[1]圖5 地理空間用戶位置歷史建?？蚣躘1]

在線部分在接收到用戶產(chǎn)生的查詢以后要進(jìn)行3方面的工作：①對(duì)用戶的查詢進(jìn)行驗(yàn)證，從時(shí)間與空間2個(gè)方面檢查用戶查詢的可行性；②搜索位置—興趣圖，生成滿足用戶查詢的候選旅程；③對(duì)滿足用戶查詢的候選旅程進(jìn)行排序，排序分為以下2個(gè)步驟：

步驟1. 依據(jù)ETR(推薦旅程的時(shí)長與用戶給定時(shí)長的比例)、STR(用戶在一個(gè)位置的停留時(shí)長與位置間的遷移時(shí)長的比例)、IDR(一個(gè)旅程所包含的所有位置的興趣值的總和)進(jìn)行排序.

步驟2. 依據(jù)流行度得分進(jìn)行再排序最終得到Top-k的旅程推薦.

3.1.2 朋友推薦

傳統(tǒng)社交網(wǎng)絡(luò)中的朋友推薦利用用戶的屬性、社會(huì)結(jié)構(gòu)、用戶的交互等信息為用戶推薦潛在的朋友.對(duì)于朋友推薦常見的方法是將友誼預(yù)測看作為經(jīng)典的鏈接預(yù)測問題并依賴于社交網(wǎng)絡(luò)圖中的臨近度度量，用于測量2個(gè)用戶之間臨近度的方法包括共同鄰居法、Jaccard系數(shù)和Admic/Adar方法.在LBSNs中，用戶的位置歷史通常能反映出用戶的偏好，因此具有相似位置歷史的用戶很可能具有相似的偏好，因此也極有可能成為朋友.

1)使用GPS數(shù)據(jù)集的朋友推薦

文獻(xiàn)[1]使用GPS軌跡數(shù)據(jù)集提出了朋友推薦的方法，其方法的核心是用戶間相似性的度量.作者首先提出了新的框架，利用分層圖來建模用戶個(gè)人的位置歷史，如圖5所示:

在用戶的個(gè)人位置歷史建立以后，分2個(gè)步驟來計(jì)算2個(gè)用戶間的相似性：

步驟1. 在分層圖的每一個(gè)層內(nèi)尋找2個(gè)用戶移動(dòng)軌跡的相似序列.

步驟2. 在給定了相似序列以后計(jì)算2個(gè)用戶的相似性得分.

計(jì)算相似性得分時(shí)包含3個(gè)因素：①用戶移動(dòng)的順序?qū)傩?，?個(gè)用戶的位置歷史所分享的相似序列越長，2個(gè)用戶的相似度越高；②地理空間的分層屬性，即2個(gè)用戶所分享的位置歷史粒度越細(xì)，2個(gè)用戶的相似度越高，比如都去過同一所建筑物的2用戶的相似度高于都去過同一個(gè)城市的2個(gè)用戶的相似度；③不同位置的流行度，即都去過一個(gè)很少有人訪問的位置的2個(gè)用戶的相似度高于都去過一個(gè)很多人訪問過的位置的2個(gè)用戶的相似度，相似度得分的計(jì)算如下：

SimUser(LocH1,LocH2)=

(15)

(16)

(17)

(18)

式(15)表示根據(jù)2個(gè)用戶的位置歷史得出的相似性得分，其中l(wèi)表示在分層圖中所處的層，fw(l)確保越底層分配到越大的權(quán)重.式(16)表示一層中2個(gè)相似序列的相似性得分，其中j表示Seq1與Seq2中的第j個(gè)最大相似匹配；|Seq1|表示序列Seq1的長度；|Seq2|表示序列Seq2的長度，歸一化是為了防止一個(gè)有長時(shí)間位置歷史的用戶比短時(shí)間位置歷史的用戶更容易和他人相似.式(17)表示一個(gè)最大相似匹配的相似性得分，其中g(shù)w(k)根據(jù)s的長度k分配權(quán)重；ci為s中所包含的位置.式(18)表示位置c的流行度，其中N為數(shù)據(jù)集中的用戶總數(shù)，n為訪問位置c的用戶數(shù).

2) 使用check-in數(shù)據(jù)集的朋友推薦

文獻(xiàn)[48]提出了基于隨機(jī)游走的上下文感知朋友推薦算法(RWCFR)，將LBSNs建模為一個(gè)無向無權(quán)圖，為了給用戶推薦朋友，首先根據(jù)用戶當(dāng)前的上下文建立一張子圖，構(gòu)建子圖的項(xiàng)目包括：①在附近區(qū)域用戶先前訪問過的位置(個(gè)人空間上下文)；②在附近區(qū)域朋友和他們先前訪問過的位置(社會(huì)空間上下文)；③在附近區(qū)域?qū)＜液退麄兿惹霸L問過的熱門位置(社會(huì)空間上下文)；④朋友的朋友(社會(huì)上下文)；⑤訪問過當(dāng)前用戶先前訪問過的位置的用戶(社會(huì)空間上下文).在子圖建立以后，采用帶重啟的隨機(jī)游走(RWR)[49]排序潛在朋友.

文獻(xiàn)[50]使用Skyline查詢[51]進(jìn)行朋友推薦，主要分為4個(gè)步驟：

步驟1. 基于社交關(guān)系鏈接收集候選朋友和共同朋友的編號(hào).

步驟2. 基于用戶的簽到信息計(jì)算用戶與候選朋友間的距離.

步驟3. 基于簽到信息和社交關(guān)系鏈接計(jì)算位置相似性以及朋友的影響，通過位置相似性和朋友的影響獲取相似性得分.

步驟4. 使用Skyline查詢獲得朋友推薦列表.

文獻(xiàn)[52]提出了針對(duì)活動(dòng)推薦同伴問題，作者利用朋友關(guān)系可以根據(jù)朋友分享的興趣來聚合的假設(shè)，使用簽到數(shù)據(jù)集有效地解決了針對(duì)活動(dòng)推薦同伴問題；為了識(shí)別同伴間的友誼類型，使用了潛在主題模型，同時(shí)還考慮了用戶與所建議的場所位置的地理接近性，得到了很好的結(jié)果.

3.1.3 本地專家發(fā)現(xiàn)

在傳統(tǒng)社交網(wǎng)絡(luò)中通過分析信息擴(kuò)散網(wǎng)絡(luò)中節(jié)點(diǎn)的度來尋找意見領(lǐng)袖.在LBSNs中本地專家指的是對(duì)某一位置或區(qū)域非常了解且擁有很多本地知識(shí)的用戶，尋找本地專家對(duì)于基于位置的社會(huì)化網(wǎng)絡(luò)推薦系統(tǒng)有著重要的意義.

文獻(xiàn)[39]基于有經(jīng)驗(yàn)的用戶會(huì)訪問很多好的興趣點(diǎn)，好的興趣點(diǎn)會(huì)被很多有經(jīng)驗(yàn)的用戶所訪問這樣的假設(shè)，利用HITS算法推薦好的興趣點(diǎn)的同時(shí)也發(fā)現(xiàn)了本地專家.該方法分為2個(gè)步驟：

步驟1. 將地理空間劃分為基于樹的分層圖(TBHG),如圖6所示.圖6(a)表示不同粒度級(jí)別下的位置聚類，圖6(b)表示每層上位置聚類之間的關(guān)系.

步驟2. 基于有經(jīng)驗(yàn)的用戶會(huì)訪問很多好的興趣點(diǎn)，好的興趣點(diǎn)會(huì)被很多有經(jīng)驗(yàn)的用戶所訪問這樣的假設(shè)，將Hub看作用戶，將Authority看作興趣點(diǎn)，向每個(gè)用戶分配旅行經(jīng)驗(yàn)得分，向每個(gè)興趣點(diǎn)分配流行度得分,如圖7所示.由于用戶的經(jīng)驗(yàn)和興趣點(diǎn)的流行度之間也具有相互增強(qiáng)的關(guān)系，因此以利用式(19)、式(20)來對(duì)用戶經(jīng)驗(yàn)和興趣點(diǎn)流行度排序:

Fig. 6 Building a tree-based hierarchical graph[39]圖6 基于樹的分層圖的構(gòu)建[39]

Fig. 7 HITS-based inference model[39]圖7 基于HITS的推理模型[39]

(19)

(20)

Fig. 8 Demonstration of model[53]圖8 模型演示[53]

3.1.4 活動(dòng)推薦

在LBSNs中活動(dòng)推薦為用戶解決了2個(gè)問題：1)用戶有了明確要進(jìn)行的活動(dòng)為其推薦活動(dòng)場所；2)當(dāng)用戶指定一個(gè)具體的場所后為其推薦該場所適合的活動(dòng).用戶通常會(huì)分享自己在某一地點(diǎn)所進(jìn)行的活動(dòng)，通過對(duì)分享內(nèi)容的學(xué)習(xí)可以得到位置與活動(dòng)之間的相關(guān)性，以此構(gòu)建一個(gè)位置—活動(dòng)矩陣，利用這個(gè)矩陣就可以進(jìn)行活動(dòng)推薦.但是由于用戶的活動(dòng)歷史有限，用戶分享的活動(dòng)的位置遠(yuǎn)遠(yuǎn)小于實(shí)際的位置數(shù)量，因此位置—活動(dòng)矩陣是非常稀疏的.文獻(xiàn)[53]利用GPS軌跡數(shù)據(jù)，提出了協(xié)同矩陣分解模型進(jìn)行活動(dòng)推薦，為了解決位置—活動(dòng)矩陣稀疏的問題，作者基于相同類別的位置可能具有相同活動(dòng)的可能性的假設(shè)建立了 位置—特征矩陣，該矩陣表示了位置所屬的分類信息(例如餐館、酒吧、健身場所等等).顯然，一個(gè)位置可以屬于多個(gè)分類.為了推斷在給定一個(gè)用戶已進(jìn)行了一些其他活動(dòng)的情況下，在同一位置進(jìn)行某一活動(dòng)的可能性，作者建立了活動(dòng)—活動(dòng)矩陣來建模不同活動(dòng)之間的相關(guān)性.在3個(gè)矩陣建立以后,如圖8所示,使用協(xié)同矩陣分解最終得到位置—活動(dòng)矩陣，目標(biāo)函數(shù)推斷位置—活動(dòng)矩陣中缺失的值:

(21)

3.2 推薦方法

在對(duì)以上對(duì)象推薦的過程中，使用了基于內(nèi)容的、鏈接的、協(xié)同過濾、基于矩陣分解的等多種推薦方法，以下分別做簡單的總結(jié).

基于內(nèi)容的推薦方法主要是指直接將用戶的偏好屬性與位置的特征進(jìn)行匹配的推薦方法，該方法的優(yōu)點(diǎn)是不會(huì)被冷啟動(dòng)問題所困擾，但缺點(diǎn)是需要將位置信息與用戶信息結(jié)構(gòu)化，在LBSNs中完成這項(xiàng)工作代價(jià)巨大；此外，該方法無法利用從用戶推測出來的聚類信息.

基于鏈接分析的推薦方法[39-40,48]主要是指通過對(duì)已知網(wǎng)絡(luò)結(jié)構(gòu)等信息進(jìn)行分析，預(yù)測和估計(jì)未鏈接的2個(gè)節(jié)點(diǎn)之間存在鏈接的可能性，其典型代表為PageRank[54]和HITS[46-47].基于鏈接分析的推薦方法的優(yōu)點(diǎn)在于不會(huì)被冷啟動(dòng)問題所困擾，同時(shí)還考慮了用戶的經(jīng)驗(yàn)，但缺點(diǎn)是由于忽視了用戶的偏好它只能做通用推薦而無法將推薦個(gè)性化.

基于協(xié)同過濾的推薦方法[4-5,55-59]主要分為基于用戶的協(xié)同過濾和基于位置的協(xié)同過濾.在LBSNs中使用協(xié)同過濾方法主要分為3個(gè)過程：1)候選集的篩選，以此縮小計(jì)算范圍；2)相似度的計(jì)算，直接影響到推薦的性能；3)推薦得分的計(jì)算，以此排序推薦對(duì)象.該方法的優(yōu)點(diǎn)是不需要將位置信息與用戶信息結(jié)構(gòu)化同時(shí)還利用了社區(qū)意見，但缺點(diǎn)是容易受到冷啟動(dòng)問題的困擾，容易受到稀疏問題的困擾；同時(shí)由于用戶與位置數(shù)量巨大，相似性計(jì)算的代價(jià)也是巨大的，此外，由于LBSNs增長迅速，該方法的可擴(kuò)展性也受到了極大的挑戰(zhàn).

自從Netfix大獎(jiǎng)賽獲得巨大的成功，基于矩陣分解的推薦算法[60-61]受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，在LBSNs中也得到了廣泛的使用[6,10,53,62].在LBSNs的推薦服務(wù)中，基于矩陣分解的推薦算法將用戶和位置的特征向量同時(shí)映射到低維的隱藏因子空間，在低維的隱藏因子空間中，由于用戶偏好和位置特征之間的相關(guān)性可以直接計(jì)算，矩陣分解的推薦算法利用用戶和位置的低維特征向量的內(nèi)積來預(yù)測用戶對(duì)項(xiàng)目的評(píng)分.基于矩陣分解的推薦算法主要包括基本矩陣分解、非負(fù)矩陣分解和正交非負(fù)矩陣分解3種.其優(yōu)點(diǎn)是可以發(fā)現(xiàn)數(shù)據(jù)中的潛在結(jié)構(gòu)、具備優(yōu)雅的概率解釋、容易擴(kuò)展到一些指定特定先驗(yàn)信息的領(lǐng)域，許多優(yōu)化方法例如梯度下降法可以用來找到一個(gè)最優(yōu)解，適合填充稀疏矩陣.

在LBSNs中，其他的一些推薦方法還包括：基于張量分解的推薦方法[18,20,63-64]、基于元路徑的推薦方法[65]和基于神經(jīng)網(wǎng)絡(luò)的推薦方法[66]等.

3.3 評(píng)價(jià)方法

與傳統(tǒng)推薦方法使用的評(píng)價(jià)方法類似，在LBSNs中，目前常用的評(píng)價(jià)指標(biāo)有準(zhǔn)確率P、召回率R、平均精度均值(mean average precision,MAP)、歸一化折損累積增益(normalize discounted cumulative gain,NDCG)、平均絕對(duì)誤差(mean absolute error,MAE)、均方根誤差(root-mean-square error,RMSE)等.準(zhǔn)確率P、召回率R、平均絕對(duì)誤差MAE和均方根誤差RMSE的定義:

(22)

(23)

(24)

(25)

其中，yi表示真實(shí)值,fi表示預(yù)測值.

準(zhǔn)確率只考慮了推薦列表中準(zhǔn)確的推薦結(jié)果的個(gè)數(shù)，沒有考慮推薦結(jié)果之間的序.對(duì)于一個(gè)推薦系統(tǒng)而言返回的推薦結(jié)果必然是有序的，而且越準(zhǔn)確的推薦結(jié)果排序越靠前越好.于是對(duì)于一個(gè)推薦列表就需要計(jì)算其平均精度(average precision,AP)，定義為

(26)

其中,k表示推薦列表中的排名，P(k)表示推薦列表中截止到排名k的準(zhǔn)確率，rel(k)表示一個(gè)指示函數(shù)，如果在排名位置k是一個(gè)準(zhǔn)確的推薦結(jié)果其值為1，否則為0，N表示推薦總數(shù).MAP的定義為

(27)

其中，Q表示推薦的總次數(shù).

折損累積增益(discounted cumulative gain,DCG)也是一個(gè)衡量排名算法的指標(biāo)，計(jì)算公式為

(28)

其中,reli表示第i個(gè)結(jié)果的評(píng)分.NDCG的定義:

(29)

其中,IDCGp表示理想的DCGp.

在推薦系統(tǒng)中,MAP和NDCG是2個(gè)最受歡迎的排名指標(biāo)，兩者之間的主要區(qū)別是：MAP認(rèn)為對(duì)象是二元相關(guān)性(一個(gè)對(duì)象是感興趣的或者不感興趣的)，而NDCG允許以實(shí)數(shù)形式進(jìn)行相關(guān)性打分，這種關(guān)系類似分類和回歸的關(guān)系.一個(gè)推薦方法返回多個(gè)項(xiàng)并形成一個(gè)推薦列表，NDCG要評(píng)價(jià)這個(gè)列表的優(yōu)劣，其中每一項(xiàng)都有一個(gè)相關(guān)的評(píng)分值(非負(fù)數(shù))這就是所謂的增益(gain)，而對(duì)于那些沒有反饋給用戶的項(xiàng)將其增益設(shè)置為0，把這些評(píng)分值相加，就得到了累積增益(cumulative gain)，而在把這些分?jǐn)?shù)相加之前將每項(xiàng)除以一個(gè)遞增的數(shù)(通常是該項(xiàng)位置的對(duì)數(shù)值)也就是折損值就得到了DCG.在用戶與用戶之間，DCG沒有直接的可比性，所以要對(duì)其進(jìn)行歸一化處理，歸一化采取計(jì)算列表中前k項(xiàng)的DCG，然后將原DCG除以理想狀態(tài)下的DCG就得到了NDCG.

4 總結(jié)與展望

基于位置的社會(huì)化網(wǎng)絡(luò)推薦技術(shù)作為推薦系統(tǒng)和社會(huì)化網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)新的研究熱點(diǎn)受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，盡管在推薦架構(gòu)、位置建模、相似性計(jì)算、推薦算法等諸多方面基于位置的社會(huì)化網(wǎng)絡(luò)推薦技術(shù)都取得了一系列重要研究成果，但隨著數(shù)據(jù)量的爆炸性增長以及計(jì)算模式與技術(shù)的不斷演化，基于位置的社會(huì)化網(wǎng)絡(luò)推薦方面仍然存在著一些挑戰(zhàn)和潛在的研究方向：

1) 推薦技術(shù)不應(yīng)該只局限于地理空間，由于地理空間的限制，推薦系統(tǒng)無法利用2個(gè)相距遙遠(yuǎn)但擁有著相同出行習(xí)慣和共同偏好的用戶信息進(jìn)行推薦，而語義空間就很好的解決了這一問題，所以如何有效利用語義空間更好地進(jìn)行推薦是一個(gè)重要的研究方向；

2) 一個(gè)高質(zhì)量推薦的產(chǎn)生一定是多方面因素共同作用的結(jié)果，為了能讓用戶得到更滿意的推薦結(jié)果及時(shí)獲取用戶的多方面需求離不開情境信息，這就要求一個(gè)能夠整合情境的面向用戶查詢的推薦系統(tǒng)；

3) 隨著數(shù)據(jù)量的爆炸性增長，目前LBSNs中包含了海量的豐富信息，因此，如何將大數(shù)據(jù)處理技術(shù)與基于位置的社會(huì)化網(wǎng)絡(luò)推薦相結(jié)合也是一個(gè)值得關(guān)注的方向，與此同時(shí)，結(jié)合并行計(jì)算來提高運(yùn)算效率也是不可或缺的，文獻(xiàn)[67]已經(jīng)做了一些初步的探討；

4) 為了讓推薦服務(wù)能隨著時(shí)間的推移逐步提高自己的推薦質(zhì)量，接受推薦反饋并不斷調(diào)整推薦能力也是不可或缺的[68]；

5) 深度學(xué)習(xí)目前在數(shù)字圖象處理和自然語言處理方面表現(xiàn)出了巨大的潛能，如何將其無縫地應(yīng)用到基于位置的社會(huì)化網(wǎng)絡(luò)推薦方面是一個(gè)很有潛力的發(fā)展方向.