融合多種影響因子的興趣點(diǎn)推薦算法

吳會(huì)叢 李嬌娥 趙明星 高凱

摘 要：?為了解決興趣點(diǎn)推薦任務(wù)中的數(shù)據(jù)稀疏性問(wèn)題和充分利用位置社交網(wǎng)絡(luò)中的多樣信息提高個(gè)性化推薦質(zhì)量，提出了一種融合多種影響因子的興趣點(diǎn)推薦算法。分別對(duì)地理信息和社會(huì)信息進(jìn)行地理影響力建模和社會(huì)影響力建模，并聯(lián)合時(shí)間信息和地理信息進(jìn)行時(shí)空影響力建模，然后以加權(quán)求和的方式整合3種影響力評(píng)分得到用戶偏好分?jǐn)?shù)，根據(jù)用戶偏好分?jǐn)?shù)為每個(gè)用戶提供1個(gè)包含Top-N個(gè)興趣點(diǎn)的推薦列表。實(shí)驗(yàn)結(jié)果顯示，在2個(gè)公開(kāi)數(shù)據(jù)集上，融合多種影響因子的興趣點(diǎn)推薦模型的性能優(yōu)于對(duì)比模型。地理-社會(huì)-時(shí)空影響是興趣點(diǎn)推薦任務(wù)中的關(guān)鍵，對(duì)這3種影響建?？蔀槿诤详P(guān)鍵信息的興趣點(diǎn)推薦研究提供參考。

關(guān)鍵詞： 自然語(yǔ)言處理;興趣點(diǎn)推薦;地理影響力建模;社會(huì)影響力建模;時(shí)空影響力建模

中圖分類(lèi)號(hào)：TP319文獻(xiàn)標(biāo)識(shí)碼： A

doi：10.7535/hbkd.2020yx06004

Point-of-interest recommendation algorithm

integrating multiple impact factors

WU Huicong， LI Jiaoe， ZHAO Mingxing， GAO Kai

（School of Information Science and Engineering， Hebei University of Science and Technology， Shijiazhuang， Hebei 050018， China）

In order to solve the problem of data sparseness in the task of point-of-interest recommendation and make full use of the diverse information in the location-based social network to further improve the quality of personalized recommendation， a point-of-interest recommendation algorithm integrating multiple impact factors was proposed. Geographic influence modeling and social influence modeling were performed on geographic information and social information， and temporal information and geographic information were combined to model temporal and spatial influence， and the three influence scores were integrated in a weighted summation manner to obtain user preference score. According to the user preference score， each user was provided with a recommendation list containing Top-N points of interest. The experimental results show that on the two public datasets， the point-of-interest recommendation model that integrates multiple impact factors performs better than the baselines. In addition to the user check-in frequency， the geographic-social-spatial-temporal influence is also a key part of the point-of-interest recommendation task， and the modeling of these three influences is of great significance， which provides certain reference value for the research of point-of-interest recommendation integrating key information.

natural language processing; point-of-interest recommendation; geographic influence modeling; social influence modeling; spatial-temporal influence modeling

近年來(lái)，隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展和成熟，位置社交網(wǎng)絡(luò)（location-based social network， LBSN）逐漸興起并成為人們生活中的重要組成部分。興趣點(diǎn)（point-of-interest， POI）推薦在LSBN中起著至關(guān)重要的作用，不僅是推薦領(lǐng)域中一個(gè)非常重要的任務(wù)，也是時(shí)空數(shù)據(jù)挖掘中的一項(xiàng)極具意義的應(yīng)用型研究。

不同于傳統(tǒng)推薦任務(wù)，在POI推薦場(chǎng)景中，蘊(yùn)含著大量的時(shí)間信息、地理信息和社會(huì)信息，用戶在進(jìn)行下一個(gè)興趣點(diǎn)的選擇時(shí)，除了遵從自身的喜好外，還可能會(huì)受到時(shí)間的影響、地理的影響和社會(huì)的影響。如圖1所示，本文將聯(lián)合用戶和未簽到過(guò)的興趣點(diǎn)之間的3種影響力（地理影響力、社會(huì)影響力和時(shí)空影響力）建模，預(yù)測(cè)目標(biāo)用戶對(duì)未簽到過(guò)興趣點(diǎn)的偏好分?jǐn)?shù)。

2.3 社會(huì)影響力建模

用戶之間的社會(huì)聯(lián)系也被廣泛使用，以提高興趣點(diǎn)推薦系統(tǒng)的性能，因?yàn)橄啾饶吧?，社交好友在POI上更有可能有共同興趣。因此，本文通過(guò)利用目標(biāo)用戶u與在目標(biāo)興趣點(diǎn)v上簽到過(guò)的好友之間的社會(huì)影響力來(lái)推斷用戶u與興趣點(diǎn)v的相關(guān)性得分。該過(guò)程包括3個(gè)步驟：社會(huì)聚合、社會(huì)簽到頻率分布估計(jì)和社會(huì)影響力分?jǐn)?shù)計(jì)算。

步驟1：社會(huì)聚合（即聚合用戶u的好友在目標(biāo)興趣點(diǎn)v上的簽到頻率） 給定一個(gè)用戶u和一個(gè)未簽到過(guò)的目標(biāo)興趣點(diǎn)v，根據(jù)式（8）匯總用戶u的好友們（如u′，其中Su，u′=1）在v上的簽到頻率xu，v：

xu，v=∑[DD（X]u′Su，u′·Ru′，v，（8）

式中：Ru′，v為用戶u′在目標(biāo)興趣點(diǎn)v上的簽到頻率;Su，u′表示用戶u與用戶u′是否是好友關(guān)系，如果Su，u′=1，則說(shuō)明用戶

u與用戶u′間存在好友關(guān)系，否則，不存在好友關(guān)系。

步驟2：社會(huì)簽到頻率分布估計(jì) 在真實(shí)世界的數(shù)據(jù)集中，社會(huì)簽到頻率的隨機(jī)變量x遵循冪律分布[17]，其概率密度函數(shù)可被定義為

fSo（x）=（β-1）（1+x）-β， x≥0， β>1。

其中β的計(jì)算公式如下：

β=1+[∑[DD（X]u∈U ∑[DD（X]v∈Vln（1+xu，v）]-1。

步驟3：社會(huì)影響力得分計(jì)算 基于社會(huì)簽到頻率分布，對(duì)所有用戶歷史簽到數(shù)據(jù)進(jìn)行學(xué)習(xí)后，將社交簽到頻率轉(zhuǎn)換為正則化的影響力分?jǐn)?shù)?；趂So（x）的累積分布函數(shù)，定義xu，v的社會(huì)影響力分?jǐn)?shù)為

sSo（xu，v）=∫xu，v0fSo（z）dz=1-（1+xu，v）1-β。（9）

社會(huì)影響力分?jǐn)?shù)sSo反映了用戶在POIs上的所有社會(huì)簽到頻率的相對(duì)位置，因?yàn)?-β<0，所以sSo是一個(gè)遞增函數(shù)，隨社會(huì)簽到頻率xu，v的增大而增大。

2.4 時(shí)空影響力建模

當(dāng)前有關(guān)興趣點(diǎn)推薦的研究往往對(duì)時(shí)間信息和地理信息分開(kāi)進(jìn)行建模，但是用戶在不同的時(shí)間狀態(tài)（如工作日或休息日）下簽到活動(dòng)中心也是不同的。因此，基于文獻(xiàn)＼[21＼]的思想，本文除了進(jìn)行地理影響力建模，

還聯(lián)合考慮地理影響力和時(shí)間影響力，進(jìn)行時(shí)空影響力建模。

用戶的簽到活動(dòng)往往是基于中心的模式，所以需要獲取若干個(gè)用戶簽到活動(dòng)中心。首先，對(duì)于每個(gè)用戶u在某個(gè)時(shí)間狀態(tài)T簽到過(guò)的興趣點(diǎn)Vu，T按照簽到頻率排序，然后選擇簽到最頻繁的興趣點(diǎn)，將與其距離小于距離α的興趣點(diǎn)劃分為一個(gè)區(qū)域，得到簽到活動(dòng)中心集合Cu，T。

給定用戶u在時(shí)間狀態(tài)T下的簽到活動(dòng)中心集合Cu，T，用戶u訪問(wèn)興趣點(diǎn)v的時(shí)空影響力得分為

sTemGeo（u，v|Cu，T）=∑|Cu，T|Cu，T

1dist（v，Cu，T） freqCu，T∑i∈Cu，Tfreqi，

式中：1dist（v，Cu，T）為根據(jù)興趣點(diǎn)v與簽到活動(dòng)中心Cu，T之間的距離確定興趣點(diǎn)v是否屬于簽到活動(dòng)中心Cu，T的打分;freqCu，T為用戶u在簽到活動(dòng)中心Cu，T的簽到頻率;∑i∈cu，Tfreqi為用戶在所有簽到活動(dòng)中心內(nèi)的簽到概率。

本文只考慮工作時(shí)間狀態(tài)和休息時(shí)間狀態(tài)。時(shí)間狀態(tài)的劃分是根據(jù)用戶對(duì)興趣點(diǎn)的簽到時(shí)間，周一—周五每天8：00—18：00規(guī)定為工作時(shí)間狀態(tài)，其他時(shí)間為休息時(shí)間狀態(tài)。因此，時(shí)空影響力得分sTemGeo（u，v|Cu，T）可進(jìn)一步定義為

sTemGeo（u，v|Cu，T）=sTemGeo（u，v|Cu，WT）+sTemGeo（u，v|Cu，LT），（10）

式中：sTemGeo（u，v|Cu，WT）為工作時(shí)間狀態(tài)下的時(shí)空影響力得分;sTemGeo（u，v|Cu，LT）為休息時(shí)間狀態(tài)下的時(shí)空影響力得分。

2.5 興趣點(diǎn)推薦

融合式（7）、式（9）和式（10）給定的地理影響力得分、社會(huì)影響力得分和時(shí)空影響力得分，根據(jù)用戶u對(duì)興趣點(diǎn)v的偏好，基于加權(quán)求和的方式，把這些影響力得分整合，得到一個(gè)統(tǒng)一的偏好分?jǐn)?shù)s（u，v）：

s（u，v）=λ1sGeo+λ2sSo（xu，v）+λ3sTemGeo（u，v|Cu，T），

式中λ1，λ2和λ3分別為地理影響力得分、社會(huì)影響力得分和時(shí)空影響力得分的權(quán)重系數(shù)，且保證λ1+λ2+λ3=1。

按照偏好分?jǐn)?shù)s（u，v）排序，推薦給用戶u得分值最高的Top-N個(gè)興趣點(diǎn)。

3 實(shí) 驗(yàn)

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

為了證明本文所建模型的有效性，在Gowalla數(shù)據(jù)集和Foursquare數(shù)據(jù)集[3]2個(gè)公開(kāi)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。Gowalla數(shù)據(jù)集記錄了2009-02-01—2010-10-31全球范圍內(nèi)的簽到數(shù)據(jù)，F(xiàn)oursquare數(shù)據(jù)集包括2012-04-01—2013-09-31的簽到數(shù)據(jù)。每條簽到記錄都包含1個(gè)用戶、1個(gè)POI興趣點(diǎn)（緯度和經(jīng)度）和1個(gè)簽到時(shí)間戳。在實(shí)驗(yàn)過(guò)程中，本文對(duì)數(shù)據(jù)集進(jìn)行了預(yù)處理。對(duì)于Gowalla數(shù)據(jù)集，將簽到次數(shù)少于15的用戶和被訪問(wèn)人數(shù)不足10的興趣點(diǎn)刪除;對(duì)于Foursquare數(shù)據(jù)集，將簽到次數(shù)少于10的用戶和被訪問(wèn)人數(shù)不足10的興趣點(diǎn)刪除。被處理過(guò)的數(shù)據(jù)集詳細(xì)信息如表1所示。

本文將每個(gè)數(shù)據(jù)集劃分為訓(xùn)練數(shù)據(jù)、驗(yàn)證數(shù)據(jù)和測(cè)試數(shù)據(jù)。對(duì)于每個(gè)用戶，將最早期的70%簽到作為訓(xùn)練數(shù)據(jù)，將最近期的20%簽到作為測(cè)試數(shù)據(jù)，其余的10%作為驗(yàn)證數(shù)據(jù)。

3.2 評(píng)價(jià)指標(biāo)設(shè)定

為評(píng)估推薦模型的性能，本文使用3個(gè)評(píng)測(cè)指標(biāo)：Precision@N，Recall@N和nDCG@N，其中N∈{10，20}。Precision@N是指推薦結(jié)果中用戶實(shí)際訪問(wèn)的興趣點(diǎn)數(shù)量占推薦結(jié)果總數(shù)的比例，反映推薦的準(zhǔn)確性;Recall@N是指推薦結(jié)果里用戶實(shí)際訪問(wèn)的興趣點(diǎn)數(shù)量占用戶實(shí)際訪問(wèn)興趣點(diǎn)總數(shù)的比例，反映推薦的全面性;nDCG@N是一種表示推薦模型排序質(zhì)量的度量方法。

3.3 參數(shù)設(shè)置

本文采用工程化的方法進(jìn)行了參數(shù)的選擇，最優(yōu)結(jié)果可能略有偏差。在進(jìn)行的所有對(duì)比實(shí)驗(yàn)中，對(duì)于Gowalla數(shù)據(jù)集，當(dāng)α=40時(shí)，模型性能最佳，對(duì)于Foursuqare數(shù)據(jù)集，當(dāng)α=15時(shí)模型性能最佳。在融合3種影響力時(shí)的權(quán)重設(shè)置上，對(duì)于Gowalla數(shù)據(jù)集，當(dāng)λ1=0.7，λ2=0.2，λ3=0.1時(shí)，模型性能最佳。Foursquare數(shù)據(jù)集中不存在社交關(guān)系數(shù)據(jù)，因此當(dāng)λ1=0.9，λ2=0.0，λ3=0.1時(shí)，模型性能最佳。

3.4 實(shí)驗(yàn)結(jié)果與分析

3.4.1 實(shí)驗(yàn)結(jié)果

為了證明本文模型的有效性，將其與以下4種基線方法進(jìn)行比較。

PFM[22]：是一類(lèi)基于概率的模型，在用戶-POI簽到矩陣分解的基礎(chǔ)上實(shí)現(xiàn)，可以直接對(duì)簽到頻率數(shù)據(jù)進(jìn)行建模，將Beta分布作為先驗(yàn)值放在潛在矩陣U和V上，對(duì)簽到頻率的建模符合泊松分布。

MGMPFM[4]：是一種結(jié)合了PFM輸出以及地理建模方法的混合模型，采用多中心高斯模型作為地理建模方法。

LRT[18]：是一個(gè)時(shí)間增強(qiáng)的矩陣分解模型，分別為每個(gè)時(shí)間間隔進(jìn)行簽到矩陣的分解，以在不同的時(shí)間對(duì)用戶進(jìn)行建模。

iGLSR[12]：利用POI推薦的地理偏好和社會(huì)影響力，采用基于好友的協(xié)同過(guò)濾對(duì)社會(huì)影響力建模。對(duì)于每個(gè)用戶，iGLSR使用核密度估計(jì)（kernel density estimation，KDE）從歷史簽到記錄中學(xué)習(xí)距離分布。因此，用戶訪問(wèn)新的POI的概率是基于POI與用戶所訪問(wèn)的POI之間的距離的KDE值。

由于無(wú)法獲取Foursquare數(shù)據(jù)集中的好友社交關(guān)系數(shù)據(jù)，因此對(duì)2個(gè)數(shù)據(jù)集進(jìn)行分開(kāi)實(shí)驗(yàn)：在Gowalla數(shù)據(jù)集上完整利用了本文提出3種影響力模型，而在Foursquare數(shù)據(jù)集上只利用了本文所提出的地理影響力模型和時(shí)空影響力模型。2個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果分別如表2和表3所示，本文所有實(shí)驗(yàn)中對(duì)比模型的實(shí)驗(yàn)結(jié)果來(lái)自文獻(xiàn)＼[20＼]和文獻(xiàn)＼[21＼]。其中MGMPFM模型是基于地理信息建模的，LRT模型是基于時(shí)間信息建模的，iGLSR模型是基于地理信息和社交信息建模的。

從表2可知，所提出的融合多種影響因子的興趣點(diǎn)推薦模型與其他4種基線模型相比性能有所提升。

由此可見(jiàn)，本文基于時(shí)間信息、地理信息和社交信息等多種上下文信息的建模是有意義的。

從表3可知，本文提出的用于興趣點(diǎn)推薦的地理影響力模型和時(shí)空影響力模型的效果明顯好于其他3種模型。

3.4.2 實(shí)驗(yàn)分析

1）模型參數(shù)影響分析 圖4展示了在Gowalla數(shù)據(jù)集上本文模型中的距離閾值參數(shù)α在不同取值時(shí)，Precision@10，Recall@10和nDCG@10 3個(gè)評(píng)測(cè)指標(biāo)的結(jié)果。從圖4可知，在Gowalla數(shù)據(jù)集上，α=40時(shí)模型效果最好，可以綜合反映出用戶的簽到行為具有活動(dòng)中心性。

2）用戶簽到POIs數(shù)量影響分析 本文僅在Gowalla數(shù)據(jù)集上進(jìn)行有關(guān)用戶簽到POIs數(shù)量影響的實(shí)驗(yàn)和分析，即研究訓(xùn)練數(shù)據(jù)量大小對(duì)實(shí)驗(yàn)結(jié)果的影響。分別對(duì)隨機(jī)選擇的40%，60%和80%訓(xùn)練數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，對(duì)比結(jié)果如圖5所示。從圖5可知，在不同比例的數(shù)據(jù)上，本文模型的性能均優(yōu)于4種基線模型，說(shuō)明本文模型很好地解決了當(dāng)前興趣點(diǎn)推薦任務(wù)中的數(shù)據(jù)稀疏性問(wèn)題。

3）3種影響力的影響分析 本文僅在Gowalla數(shù)據(jù)集上進(jìn)行了3種影響力的影響分析，即分別單獨(dú)利用其中1種影響力進(jìn)行興趣點(diǎn)推薦。如表4所示，本文進(jìn)行了5組實(shí)驗(yàn)：僅利用地理影響力建模（Geo）、僅利用社會(huì)影響力建模（So）、僅利用時(shí)空影響力建模（TemGeo）、融合地理影響力建模與社會(huì)影響力建模（Geo+So）、融合3種影響力建模（Geo+So+TemGeo）。從表4可知，融合3種影響力的興趣點(diǎn)推薦模型性能均好于僅利用1種或2種影響力的推薦模型，證明了所提出的融合多種影響因子的興趣點(diǎn)推薦模型的有效性。

4 結(jié) 語(yǔ)

本文提出了融合多種影響因子的興趣點(diǎn)推薦模型，分別對(duì)地理信息、社會(huì)信息進(jìn)行地理影響力建模和社會(huì)影響力建模，并聯(lián)合時(shí)間信息和地理信息進(jìn)行時(shí)空影響力建模，然后以加權(quán)求和的方式整合3種影響力評(píng)分得到用戶偏好分?jǐn)?shù)，達(dá)到了充分利用位置社交網(wǎng)絡(luò)中的信息提高興趣點(diǎn)推薦性能的目的。通過(guò)與其他模型比較，證明了此模型是有效的。

本文模型仍有較大的提升空間。首先，基于地理影響力建模，僅考慮了單個(gè)用戶頻繁活動(dòng)中心，有一定的局限性;其次，基于社會(huì)影響力建模，只考慮了直接好友關(guān)系;最后，基于時(shí)空影響力建模，時(shí)間狀態(tài)僅籠統(tǒng)地劃分為工作時(shí)間和休息時(shí)間，且在2種時(shí)間狀態(tài)的界定上還有不足。除此之外，未來(lái)的工作中擬考慮整合更豐富的上下文信息（如用戶評(píng)論信息）到興趣點(diǎn)推薦模型中。

參考文獻(xiàn)/References：

[1]BAO Jie， ZHENG Yu， WILKIE D， et al. Recommendations in location-based social networks： A survey[J]. GeoInformatica， 2015， 19（3）： 525-565.

[2]YIN Hongzhi， SUN Yizhou， CUI Bin， et al. LCARS： A location-content-aware recommender system[C]// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： [s.n.]， 2013： 221-229.

[3]LIU Yiding， PHAM T A N， CONG Gao， et al. An experimental evaluation of point-of-interest recommendation in location-based social networks[C]// Proceedings of the VLDB Endowment. Trondheim：[s.n.]， 2017： 1010-1021.

[4]CHENG Chen， YANG Haiqin， KING I， et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]// Proceedings of the 26th AAAI Conference on Artificial Intelligence. Toronto：[s.n.]， 2012： 17-23.

[5]YE Mao， YIN Peifeng， LEE W C， et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Beijing： [s.n.]， 2011： 325-334.

[6]FARRAHI K， GATICA-PEREZ D. Discovering routines from large-scale human locations using probabilistic topic models[J]. ACM Transactions on Intelligent Systems and Technology， 2011， 2（1）： 1-27.

[7]KURASHIMA T， IWATA T， HOSHIDE T， et al. Geo topic model： Joint modeling of user's activity area and interests for location recommendation[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. Rome：[s.n.]， 2013： 375-384.

[8]LIU Xin， LIU Yong， ABERER K， et al. Personalized point-of-interest recommendation by mining users' preference transition[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. Burlingame： [s.n.]， 2013： 733-738.

[9]FU Yanjie， LIU Bin， GE Yong， et al. User preference learning with multiple information fusion for restaurant recommendation[C]//Proceedings of the 2014 SIAM International Conference on Data Mining. Philadelphia： [s.n.]， 2014： 470-478.

[10]YUAN Quan， CONG Gao， MA Zongyang， et al. Time-aware point-of-interest recommendation[C]//Proceedings of the 36th ACM SIGIR Conference on Research and Development in Information Retrieval. Dublin： [s.n.]， 2013： 363-372.

[11]YUAN Quan， CONG Gao， SUN Aixin. Graph-based point-of-interest recommendation with geographical and temporal influences[C]//Proceedings of the 23th ACM International Conference on Information and Knowledge Management. Shanghai： [s.n.]， 2014： 659-668.

[12]ZHANG Jiadong， CHOW C Y. iGLSR： 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. Orlando： [s.n.]， 2013： 334-343.

[13]ZHANG Jiadong， CHOWA C Y. CoRe： Exploiting the personalized influence of two-dimensional geographic coordinates for location recommendations[J]. Journal of Information Sciences， 2015， 291： 163-181.

[14]ZHANG Jiadong， CHOWA C Y， LI Yanhua. LORE： Exploiting sequential influence for location recommendations[C]//Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Dallas： [s.n.]， 2014： 103-112.