李寒露，解 慶，唐伶俐，劉永堅

（武漢理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430070）

0 引言

興趣點（Point-Of-Interest，POI）推薦一直受著基于位置的社 交 網(wǎng) 絡(luò)（Location-Based Social Networks，LBSNs）（例 如Foursquare和Facebook等）快速發(fā)展的推動。這些LSBNs允許用戶彼此連接，發(fā)布物理位置并分享與位置相關(guān)聯(lián)的信息［1］。而LBSNs 中的POI 推薦意在幫助用戶探索新的和有趣的地方。例如，當(dāng)用戶去吃飯時，推薦系統(tǒng)會為用戶找到附近其感興趣的餐館或者小吃的詳細(xì)信息；這樣不僅可以改善用戶的體驗，同時也能為商家?guī)硇碌哪繕?biāo)客戶。目前，大多數(shù)研究主要在協(xié)同過濾（Collaborative Filtering，CF）的基礎(chǔ)上加入其他影響因子進(jìn)行推薦，但是存在以下幾點不足：

1）數(shù)據(jù)噪聲過濾方法需要改進(jìn)：龐大的用戶簽到數(shù)據(jù)中不可避免地混雜許多噪聲數(shù)據(jù)，過多的噪聲數(shù)據(jù)會導(dǎo)致推薦質(zhì)量的降低［2］。如果能夠在數(shù)據(jù)預(yù)處理階段提前過濾掉不符合用戶行為習(xí)慣的簽到信息數(shù)據(jù)，可以提高推薦的精度，降低計算量。

2）興趣點重要性分析未能有效考慮用戶個性化因素：在LBSNs中，通常按照訪問次數(shù)排序的方法計算興趣點重要性，但僅僅考慮用戶的訪問次數(shù)，會導(dǎo)致興趣點重要性對于所有用戶都是同等的，而實際上，對于不同的用戶每個興趣點的重要性是不同的。

針對上述問題，本文提出了RecSI（Recommendation by Spatiotemporal information and POI Importance）模型，主要貢獻(xiàn)如下：

1）將地理信息和興趣點之間吸引力設(shè)置為預(yù)處理條件，過濾數(shù)據(jù)集中的數(shù)據(jù)噪聲。

2）引入用戶社交關(guān)系網(wǎng)絡(luò)，通過計算用戶與好友之間的相似程度和興趣點對于好友的重要程度，來評估興趣點對于目標(biāo)用戶的重要性。

1 相關(guān)工作

協(xié)同過濾（CF）是興趣點推薦中最常見的技術(shù)，它分為基于記憶和基于模型的方法?；谟洃浀姆椒ㄓ址譃榛陧椖亢陀脩魞深悺Ｔ诨谟脩舻姆椒ㄖ?，通過采用諸如Cosine 或Pearson 的測量函數(shù)來計算某些用戶之間的相似性權(quán)重。隨后，將使用相同POI上的類似用戶的評級來計算用戶訪問POI的概率［3］。而在基于項目的方法中，首先找到共同訪問的POI，然后計算在類似POI 上的用戶評級的加權(quán)混合［4］。但是這些方法都未能取得很好的推薦結(jié)果，因此，不少研究加入其他的影響因子以改進(jìn)推薦的結(jié)果。

地理影響［3-6］在POI 推薦中起著至關(guān)重要的作用，因為用戶在LBSNs中的活動受到地理位置的限制。Cheng等［5］假設(shè)用戶傾向于在幾個中心周圍進(jìn)行簽到活動，并使用多中心高斯模型（Multi-center Gaussian Model，MGM）對同一用戶的兩個位置之間的距離進(jìn)行建模，以捕獲地理影響，然后進(jìn)一步用矩陣分解進(jìn)行POI 推薦。Ye 等［3］通過采用冪律分布（Power-law Distribution，PD）對用戶的位置進(jìn)行建模，并提出了一種基于地理影響的樸素貝葉斯POI 推薦算法。Zhang 等［6］認(rèn)為，當(dāng)LBSNs向用戶推薦POI而不是所有用戶的共同分布時，應(yīng)該個性化對用戶移動性的地理影響，所以他們通過使用核密度估計（Kernel Density Estimation，KDE）來模擬地理影響。

在POI 推薦中，一般利用時間影響［7-12］來提高在特定時間向查詢用戶推薦新位置的概率。例如，人們總是在工作日和周末訪問不同的地方，用戶的偏好也會發(fā)生改變。Guo等［7］通過將用戶的簽到時間進(jìn)行分段，并且對較近的時間段賦予較高的權(quán)重進(jìn)行推薦。Zheng 等［8］利用時間戳將原始用戶POI信息進(jìn)行劃分，結(jié)合LDA（Latent Dirichlet Allocation）算法［9］來推斷用戶的興趣和POI 的主題分布進(jìn)行POI 推薦。大多數(shù)關(guān)于時間影響的研究都只是經(jīng)驗性地對時間進(jìn)行均勻劃分，沒有考慮用戶訪問POI 時間上的動態(tài)性，所以王楠等［11］在利用多種信息進(jìn)行時間敏感的新位置POI 推薦，提出基于層次聚類的時間動態(tài)分段算法，結(jié)合直接朋友和潛在朋友兩種社交關(guān)系構(gòu)建模型。

在LBSNs 中社交因素［13-17］也起著重要的作用。在日常生活中，人們在訪問新的地方時往往會詢問朋友的意見，因此利用用戶之間的社交關(guān)系在一定程度上能夠解決冷啟動問題，提高推薦的準(zhǔn)確率。Li等［13］認(rèn)為用戶的簽到空間由社交朋友空間和用戶的興趣空間兩部分組成，并分別構(gòu)建了社交朋友概率分解（Social Friend Probabilistic Matrix Factorization，SFPMF）模型和用戶興趣概率分解（User Interest Probabilistic Matrix Factorization，UIPMF）模型，然后將兩種分解模型進(jìn)行線性融合來進(jìn)行興趣點推薦。Li等［16］認(rèn)為LBSNs網(wǎng)絡(luò)中存在三種朋友，并開發(fā)了一個兩步框架來利用三種朋友信息來提高興趣點推薦的準(zhǔn)確性。

2 問題分析

在本章中介紹一些與模型相關(guān)的方法和概念。在這之前先定義問題的描述。

2.1 問題描述

LBSNs 上面匯集了大量用戶的歷史簽到數(shù)據(jù)，這些歷史簽到數(shù)據(jù)中包含的各種上下文信息能夠為分析用戶偏好提供幫助，從而進(jìn)一步提高興趣點推薦的精度。LBSNs 中包含了用戶集合U={u1，u2，…，un}、興趣點集合L={l1，l2，…，lm}，n、m分別是用戶和興趣點的數(shù)量。數(shù)據(jù)集D={d1，d2，…}，其中di={u，l，t}，由用戶u、興趣點l和簽到時間t組成，描述了用戶u在時間t訪問了興趣點l。

興趣點推薦 根據(jù)已有簽到數(shù)據(jù)d={u，lj，t}，向用戶u推薦在某個時刻t上他可能感興趣但還未訪問的前K個興趣點集合。

為了方便討論，表1列出了本文使用的一些重要符號。

表1 本文所用符號及其描述Tab.1 Symbols used in this paper and their descriptions

2.2 興趣點中的地理影響

一般情況下，人們外出活動的范圍經(jīng)常受到地理位置的限制。在歷史簽到數(shù)據(jù)中，可以發(fā)現(xiàn)用戶的歷史簽到行為往往呈現(xiàn)出聚類的現(xiàn)象，并發(fā)生在相對較近的空間內(nèi)，造成用戶簽到空間的空間聚類［3］，因此，在對目標(biāo)用戶進(jìn)行POI 推薦時，POI的地理位置起著至關(guān)重要的作用。POI的地理位置分為用戶與POI之間的距離和POI與POI之間的距離，根據(jù)經(jīng)驗通常用戶更傾向于訪問距離較近的興趣點，并且所訪問的興趣點受到以前所訪問過的興趣點的影響，兩個興趣點之間的吸引力越大，相互間的影響力越大，用戶訪問的概率就越大。

文獻(xiàn)［2］驗證在Foursquare 數(shù)據(jù)集中，發(fā)現(xiàn)超過89.3%以上的用戶平均簽到的距離在10 km 以內(nèi)，分析得出人們更傾向于訪問與之前的記錄相近的興趣點，并提出基于位置的過濾算法將原始數(shù)據(jù)根據(jù)距離信息進(jìn)行過濾，以排除遠(yuǎn)離日?；顒臃秶呐d趣點。本文在此的基礎(chǔ)上加入興趣點之間的吸引力來進(jìn)一步過濾候選集的范圍。

根據(jù)文獻(xiàn)［18］提出的式（1）計算所有用戶已訪問過兩個POI之間的相互影響力：

其中：gi表示POIli地理的地理影響力，hj表示POIlj相對POIli的地理敏感性，di，j表示兩個POI 之間的距離。根據(jù)文獻(xiàn)［19］知道POI 之間的距離符合冪律分布，因此根據(jù)冪律分布得到公式f(di，j)=，其中di，j表示兩個興趣點之間的距離。

式（1）的結(jié)果如圖1 所示，圖中橫坐標(biāo)表示任意兩個POI之間的吸引力，縱坐標(biāo)表示任意兩個POI 之間平均吸引力小于指定區(qū)間的用戶比例。

如圖1顯示，超過80%以上的POI之間存在超過0.6以上的相互吸引力，可以認(rèn)為當(dāng)POI 之間相互吸引力超過0.6 時，用戶訪問的概率越大。通過相互之間的吸引力的計算，可以分析得出人們在相同的距離下，更傾向于訪問POI 之間吸引力更大的興趣點。

因此本文提出基于興趣點之間吸引力的過濾算法（Attractiveness between POIs based Filtering Algorithm，APFA），將原始數(shù)據(jù)集分別基于距離和POI 之間相互吸引力進(jìn)行過濾，去除用戶平時出行范圍內(nèi)很少去的POI，與用戶已經(jīng)訪問過的POI 相互之間吸引力較小的POI 進(jìn)行過濾得到兩個候選集，最后將這兩個候選集合并取交集，形成最后的用于推薦的候選集，以避免噪聲POI的影響，提高推薦的精度。

圖1 興趣點之間相互吸引力Fig.1 Mutual attraction between POIs

3 RecSI模型

本章描述本文提出的POI 推薦模型RecSI。RecSI 模型由兩個部分組成：一個是用戶對于興趣點的偏好程度；另一個是興趣點對用戶的重要性。該模型的主要貢獻(xiàn)在于：1）考慮到一天中不同時間段內(nèi)用戶對POI 類別的偏好程度不同，計算用戶在每個時間段內(nèi)的偏好；2）將興趣點對用戶的重要性加入到最后的推薦模型中，提高了推薦的質(zhì)量。

3.1 基于時間因素的用戶偏好建模

根據(jù)用戶在一天中不同的時間段內(nèi)對興趣點的偏好程度不一樣，本文在文獻(xiàn)［11］提出的基于層次聚類的時間動態(tài)分段方法的基礎(chǔ)上討論用戶在每個時間段的用戶偏好，本文將時間段分為4段。

研究表明，用戶在一天中不同的時間段對興趣點的喜愛程度是不同的，而在LBSNs 中POI有不同的類別，每個類別信息都可以反映POI 提供的服務(wù)以及服務(wù)的風(fēng)格，當(dāng)一個用戶越喜歡某一個種類，在時間段t內(nèi)訪問這個類別所屬的POI就越頻繁，因此可以通過分析在時間段內(nèi)用戶所訪問的POI 的類別信息來挖掘用戶的偏好程度。

在本文的數(shù)據(jù)集Foursquare 中每個POI 都是由8 個類別和240個子類別標(biāo)記，通過式（2）計算用戶u在時間段t內(nèi)對所有POI類別的偏好得分向量，以此構(gòu)建用戶u的類別偏好向量，用于表示用戶u在時間段t內(nèi)對不同類別POI的偏好程度。

其中Ct(u，ck)表示用戶在時間段t內(nèi)在ck類別的POI上的簽到總數(shù)。

但是類別偏好向量只是表示了用戶u對某一類POI 的偏好程度，而每個種類的POI 里面有包含很多的POI，將這里面的POI同等重要的推薦給用戶是不合理的。實際上，每個POI對于用戶而言都有不同的吸引程度，同類別中越受歡迎的POI 對用戶的吸引力越大，用戶簽到就越頻繁，因此為了捕獲同類別中POI 的受歡迎程度，引入POI 的受歡迎程度（即POI的流行度）作為同類別不同POI的權(quán)重。

根據(jù)用戶的歷史簽到數(shù)據(jù)，可以得到兩個數(shù)據(jù)標(biāo)簽：POI在時間段t內(nèi)總訪問的用戶量Ucountt(lj)和POI的總簽到數(shù)量Pcountt(lj)，這兩個數(shù)據(jù)標(biāo)簽可以很直觀地表現(xiàn)出POI 的受歡迎程度，在對其進(jìn)行標(biāo)準(zhǔn)化后，根據(jù)式（3）計算兩者之間的幾何平均數(shù)，得到在時間段t內(nèi)POIlj的流行度：

由此本文在考慮類別信息和流行度的同時，根據(jù)式（4）計算用戶u在時間段t內(nèi)對POI的偏好：

3.2 基于興趣點重要性建模

興趣點的重要性在一定程度上會影響推薦結(jié)果。以前的研究多數(shù)是按照訪問次數(shù)排序的方法計算興趣點重要性，僅僅考慮用戶的訪問次數(shù)，從而導(dǎo)致興趣點重要性對于所有用戶都是同等的，但實際上，對于不同用戶而言每個興趣點的重要程度是不同的。因此本文將引入用戶社交關(guān)系網(wǎng)絡(luò)，通過計算用戶與好友之間的相似程度和興趣點對于好友的重要程度，來計算興趣點對于目標(biāo)用戶的重要程度。具體按照下面的順序計算興趣點對用戶的重要性：

1）計算用戶與好友之間的相似程度。

根據(jù)用戶在LBSNs 中的簽到信息和社交關(guān)系，將用戶的朋友定義為位置好友和社交好友兩種，具體定義如下：

其中α表示相似因子，siml(u，v)和sims(u，v)分別表示好友位置相似性和好友相似性，由式（7）、（8）計算得出：

其中tu，j表示用戶u在興趣點lj的訪問狀態(tài)：若tu，j=1，代表用戶u在興趣點lj進(jìn)行了簽到；tu，j=0 則 代表用戶u未進(jìn)行簽到。Fu與Fv分別代表用戶u與用戶v的好友集合。

2）計算用戶好友中每個興趣點的重要程度。

本文定義了一個興趣點上下文圖來捕獲興趣點對用戶的重要程度。

定義3興趣點上下文圖。興趣點上下文圖表示為GLL=(L，ELL)，其中頂點lj∈L表示用戶所訪問過的興趣點，有向邊e=(li，lj)表示用戶在某一天中訪問了興趣點li之后訪問了興趣點lj。每條邊的權(quán)重ci，j表示用戶從興趣點li訪問興趣點lj的次數(shù)。

本文使用文獻(xiàn)［20］中提出的加權(quán)PageRank（Weighted PageRank，WPR）公式計算興趣點lj對用戶u的重要程度：

其中：β∈[0，1]為阻尼系數(shù)，可以把它視為其他興趣點對目標(biāo)興趣點的貢獻(xiàn)；I(lj)表示指向興趣點lj的興趣點的集合；由式（10）計算得出：

其中R(lk)表表示興趣點lk所指向的興趣點的集合。

3）計算興趣點對用戶的重要程度。

根據(jù)式（11）本文將用戶與好友之間的相似程度和興趣點對朋友的重要程度相結(jié)合來計算興趣點對用戶的重要程度：

其中Fu表示用戶u的朋友集合。

3.3 興趣點推薦

對用戶的簽到行為進(jìn)行建模時，本文認(rèn)為用戶最后簽到?jīng)Q策由兩個因素決定：1）用戶對興趣點的偏好程度；2）興趣點的重要性。當(dāng)用戶對興趣點的偏好程度越大，并且興趣點對用戶的重要性越高，用戶訪問它的概率越大。因此采用線性組合模型對用戶的偏好和興趣點重要性進(jìn)行建模，計算用戶u在當(dāng)前時間段t內(nèi)對興趣點lj的訪問得分為：

整個RecSI推薦模型偽代碼如算法1所示。

算法1 RecSI推薦模型算法。

輸入：用戶u、用戶集合U、用戶簽到數(shù)據(jù)集D、興趣點集合L、興趣點類別集合C、用戶u的社交好友集合Fu；

輸出：前K個興趣點組成的推薦列表TOP-K。

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)集

本文算法使用Foursquare 真實的數(shù)據(jù)集［21］進(jìn)行評估。通過刪除訪問次數(shù)少于10 個興趣點的用戶以及被訪問次數(shù)少于10 個用戶的興趣點來對數(shù)據(jù)集進(jìn)行預(yù)處理。預(yù)處理以后數(shù)據(jù)集包含88 193 個POI 和6 118 個用戶生成的115 890 個簽入，此外數(shù)據(jù)集中的每個POI都與其經(jīng)緯度相關(guān)聯(lián)，并且每個POI 都是由8 個類別和240 個子類別標(biāo)記。對于每個用戶，按照時間順序?qū)λ?她的簽到進(jìn)行排序，并將前80%的簽到作為訓(xùn)練數(shù)據(jù)，20%數(shù)據(jù)作為測試數(shù)據(jù)。

4.2 評價指標(biāo)

本文采用兩個在推薦系統(tǒng)中廣泛使用的評價指標(biāo)，即精確率Precision@K和召回率Recall@K，指標(biāo)評價如式（13）、（14）所示：

其中：K是推薦列表中興趣點的數(shù)量，是用戶在時間t內(nèi)推薦列表中前K個興趣點的集合，Tui，t是用戶在時間t內(nèi)訪問過興趣點的集合。本實驗中K設(shè)置為5，10，15，20。

4.3 參數(shù)選擇

在對興趣點重要性進(jìn)行建模時，需要確定相似因子α和興趣點重要性參數(shù)β的取值：根據(jù)α的不同取值可以調(diào)節(jié)好友社交因子中好友相似性和好友位置相似性所占的比例；β是在計算興趣點重要性中其他興趣點對目標(biāo)興趣點的貢獻(xiàn)，決定了興趣點之間的轉(zhuǎn)移概率和網(wǎng)絡(luò)的收斂速度。接下來確定兩個參數(shù)的選擇。

1）參數(shù)α的選擇。

首先固定參數(shù)β，然后再選取不同的α值進(jìn)行TOP-5 的推薦。推薦結(jié)果如圖2（a）所示?？梢钥闯觯?dāng)α=0.5 時，推薦效果最好，因此在后面的實驗中，參數(shù)α的值設(shè)為0.5。

2）參數(shù)β值的選擇。

固定參數(shù)α的值為0.5，觀察參數(shù)β在［0，1］范圍內(nèi)的變化，如圖2（b）所示。當(dāng)β=0.6 時，準(zhǔn)確率和召回率達(dá)到最大值，因此本文將參數(shù)β的值設(shè)為0.6。

圖2 不同參數(shù)對應(yīng)的準(zhǔn)確率和召回率Fig.2 Precision and recall under different parameters

4.4 算法對比

為了驗證本文中提出的模型的性能，選擇以下具有代表行的興趣點推薦方法進(jìn)行比較：

UPOI-Walk（Urban POI-Walk）模型［15］：融合用戶偏好，社交關(guān)系與流行度因素，使用基于HITS（Hyperlink-Induced Topic Search）的隨機(jī)游走方法進(jìn)行興趣點推薦。

TPR-TF（Time-aware POI Recommendation based on Tensor Factorization）模型［11］：利用時間敏感性提出基于層次聚類的時間動態(tài)分類算法，將時間敏感性和用戶的朋友影響相結(jié)合進(jìn)行興趣點推薦。

GCSR （Geography-Category-Socialsentiment fusion Recommendation）模型［17］：融合了分類流行度偏好、地理位置、社交關(guān)系與情感傾向因素的興趣點推薦。

UTE+SE（User with Temporal preference and smoothing Enhancement+Spacial influence with popularity Enhancement）模型［22］：利用用戶時間增強和空間流行度增強相結(jié)合的方法建立混合興趣點推薦模型。

五種推薦模型算法在準(zhǔn)確率和召回率的實驗結(jié)果如圖3（a）和圖3（b）所示。

圖3 五種推薦模型的對比實驗結(jié)果Fig.3 Comparison experimental results of five recommendation models

從圖3（a）和圖3（b）可以看出，本文提出的RecSI 模型的精確率和召回率都優(yōu)于其他模型。在幾個方法中，UTE+SE模型將時間和空間影響融合到興趣點推薦中，利用相似時間槽內(nèi)時間的相似性，結(jié)合平滑技術(shù)，在一定程度上緩解了數(shù)據(jù)稀疏性問題，但是推薦的性能并沒有得到很大的改善，因此在對比模型中的準(zhǔn)確率和召回率最低。US 模型將用戶偏好、社交關(guān)系與流行度因素納入到興趣點推薦中，因此相比UTE+SE 模型，在準(zhǔn)確率和召回率都有了很大的提升，但是與RecSI模型相比，由于沒有考慮地理位置和興趣點重要性對推薦結(jié)果影響，所以準(zhǔn)確率和召回率的提高受到了限制。TPR-TF 模型通過時間敏感性，直接將時間作為特征向量融入到推薦模型中，同時考慮了社交關(guān)系中的直接朋友和間接朋友的影響，與US 模型相比，TPR-TF 模型考慮了時間的敏感性，因此推薦的結(jié)果有一定程度的提升，但是相比RecSI 模型，因為所使用到的影響因素相對較少，所以模型的準(zhǔn)確率和召回率都受到了一定程度的影響。GCSR 模型不僅將地理信息、社交信息、興趣點種類信息加入興趣點推薦中，還融入了用戶的評論信息，考慮用戶的情感傾向，所以相對TPR-TF 模型準(zhǔn)確率和召回率有很大程度的提高，但是與RecSI 模型相比，GCSR 模型沒考慮時間因素和興趣點的重要性，因此推薦的準(zhǔn)確率和召回率相對較低。RecSI 模型不僅考慮時間因素、地理位置、興趣點類別以及興趣點流行度，同時將社交關(guān)系與興趣點重要性相融合，因此推薦的準(zhǔn)確率和召回率最好。

5 結(jié)語

在本文中提出了融合時間地理信息和興趣點重要性的POI推薦算法（RecSI）。通過興趣點的地理位置和相互之間的吸引力去除數(shù)據(jù)集中噪聲POI，減少推薦過程中的噪聲困擾，將用戶的動態(tài)偏好和興趣點的重要性結(jié)合納入推薦框架中，同時引入時間信息、興趣點類別信息、流行度和社交信息，實現(xiàn)在當(dāng)前時間為目標(biāo)用戶推薦新的興趣點集。通過在Foursquare 數(shù)據(jù)集上與其他推薦算法相比，驗證了RecSI 模型的準(zhǔn)確率和召回率都有所提高。在未來的工作希望將其他的上下文信息（例如：文本信息）加入到本文的模型中，以研究其對推薦結(jié)果的影響。