融合多種影響因子的興趣點推薦算法

吳會叢 李嬌娥 趙明星 高凱

摘 要：?為了解決興趣點推薦任務中的數據稀疏性問題和充分利用位置社交網絡中的多樣信息提高個性化推薦質量，提出了一種融合多種影響因子的興趣點推薦算法。分別對地理信息和社會信息進行地理影響力建模和社會影響力建模，并聯合時間信息和地理信息進行時空影響力建模，然后以加權求和的方式整合3種影響力評分得到用戶偏好分數，根據用戶偏好分數為每個用戶提供1個包含Top-N個興趣點的推薦列表。實驗結果顯示，在2個公開數據集上，融合多種影響因子的興趣點推薦模型的性能優于對比模型。地理-社會-時空影響是興趣點推薦任務中的關鍵，對這3種影響建模可為融合關鍵信息的興趣點推薦研究提供參考。

關鍵詞： 自然語言處理;興趣點推薦;地理影響力建模;社會影響力建模;時空影響力建模

中圖分類號：TP319文獻標識碼： 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

近年來，隨著移動互聯網技術的不斷發展和成熟，位置社交網絡（location-based social network， LBSN）逐漸興起并成為人們生活中的重要組成部分。興趣點（point-of-interest， POI）推薦在LSBN中起著至關重要的作用，不僅是推薦領域中一個非常重要的任務，也是時空數據挖掘中的一項極具意義的應用型研究。

不同于傳統推薦任務，在POI推薦場景中，蘊含著大量的時間信息、地理信息和社會信息，用戶在進行下一個興趣點的選擇時，除了遵從自身的喜好外，還可能會受到時間的影響、地理的影響和社會的影響。如圖1所示，本文將聯合用戶和未簽到過的興趣點之間的3種影響力（地理影響力、社會影響力和時空影響力）建模，預測目標用戶對未簽到過興趣點的偏好分數。

2.3 社會影響力建模

用戶之間的社會聯系也被廣泛使用，以提高興趣點推薦系統的性能，因為相比陌生人，社交好友在POI上更有可能有共同興趣。因此，本文通過利用目標用戶u與在目標興趣點v上簽到過的好友之間的社會影響力來推斷用戶u與興趣點v的相關性得分。該過程包括3個步驟：社會聚合、社會簽到頻率分布估計和社會影響力分數計算。

步驟1：社會聚合（即聚合用戶u的好友在目標興趣點v上的簽到頻率） 給定一個用戶u和一個未簽到過的目標興趣點v，根據式（8）匯總用戶u的好友們（如u′，其中Su，u′=1）在v上的簽到頻率xu，v：

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

式中：Ru′，v為用戶u′在目標興趣點v上的簽到頻率;Su，u′表示用戶u與用戶u′是否是好友關系，如果Su，u′=1，則說明用戶

u與用戶u′間存在好友關系，否則，不存在好友關系。

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

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

其中β的計算公式如下：

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

步驟3：社會影響力得分計算 基于社會簽到頻率分布，對所有用戶歷史簽到數據進行學習后，將社交簽到頻率轉換為正則化的影響力分數。基于fSo（x）的累積分布函數，定義xu，v的社會影響力分數為

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

社會影響力分數sSo反映了用戶在POIs上的所有社會簽到頻率的相對位置，因為1-β<0，所以sSo是一個遞增函數，隨社會簽到頻率xu，v的增大而增大。

2.4 時空影響力建模

當前有關興趣點推薦的研究往往對時間信息和地理信息分開進行建模，但是用戶在不同的時間狀態（如工作日或休息日）下簽到活動中心也是不同的。因此，基于文獻＼[21＼]的思想，本文除了進行地理影響力建模，

還聯合考慮地理影響力和時間影響力，進行時空影響力建模。

用戶的簽到活動往往是基于中心的模式，所以需要獲取若干個用戶簽到活動中心。首先，對于每個用戶u在某個時間狀態T簽到過的興趣點Vu，T按照簽到頻率排序，然后選擇簽到最頻繁的興趣點，將與其距離小于距離α的興趣點劃分為一個區域，得到簽到活動中心集合Cu，T。

給定用戶u在時間狀態T下的簽到活動中心集合Cu，T，用戶u訪問興趣點v的時空影響力得分為

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

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

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

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

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

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

2.5 興趣點推薦

融合式（7）、式（9）和式（10）給定的地理影響力得分、社會影響力得分和時空影響力得分，根據用戶u對興趣點v的偏好，基于加權求和的方式，把這些影響力得分整合，得到一個統一的偏好分數s（u，v）：

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

式中λ1，λ2和λ3分別為地理影響力得分、社會影響力得分和時空影響力得分的權重系數，且保證λ1+λ2+λ3=1。

按照偏好分數s（u，v）排序，推薦給用戶u得分值最高的Top-N個興趣點。

3 實 驗

3.1 數據集描述

為了證明本文所建模型的有效性，在Gowalla數據集和Foursquare數據集[3]2個公開數據集上進行實驗。Gowalla數據集記錄了2009-02-01—2010-10-31全球范圍內的簽到數據，Foursquare數據集包括2012-04-01—2013-09-31的簽到數據。每條簽到記錄都包含1個用戶、1個POI興趣點（緯度和經度）和1個簽到時間戳。在實驗過程中，本文對數據集進行了預處理。對于Gowalla數據集，將簽到次數少于15的用戶和被訪問人數不足10的興趣點刪除;對于Foursquare數據集，將簽到次數少于10的用戶和被訪問人數不足10的興趣點刪除。被處理過的數據集詳細信息如表1所示。

本文將每個數據集劃分為訓練數據、驗證數據和測試數據。對于每個用戶，將最早期的70%簽到作為訓練數據，將最近期的20%簽到作為測試數據，其余的10%作為驗證數據。

3.2 評價指標設定

為評估推薦模型的性能，本文使用3個評測指標：Precision@N，Recall@N和nDCG@N，其中N∈{10，20}。Precision@N是指推薦結果中用戶實際訪問的興趣點數量占推薦結果總數的比例，反映推薦的準確性;Recall@N是指推薦結果里用戶實際訪問的興趣點數量占用戶實際訪問興趣點總數的比例，反映推薦的全面性;nDCG@N是一種表示推薦模型排序質量的度量方法。

3.3 參數設置

本文采用工程化的方法進行了參數的選擇，最優結果可能略有偏差。在進行的所有對比實驗中，對于Gowalla數據集，當α=40時，模型性能最佳，對于Foursuqare數據集，當α=15時模型性能最佳。在融合3種影響力時的權重設置上，對于Gowalla數據集，當λ1=0.7，λ2=0.2，λ3=0.1時，模型性能最佳。Foursquare數據集中不存在社交關系數據，因此當λ1=0.9，λ2=0.0，λ3=0.1時，模型性能最佳。

3.4 實驗結果與分析

3.4.1 實驗結果

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

PFM[22]：是一類基于概率的模型，在用戶-POI簽到矩陣分解的基礎上實現，可以直接對簽到頻率數據進行建模，將Beta分布作為先驗值放在潛在矩陣U和V上，對簽到頻率的建模符合泊松分布。

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

LRT[18]：是一個時間增強的矩陣分解模型，分別為每個時間間隔進行簽到矩陣的分解，以在不同的時間對用戶進行建模。

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

由于無法獲取Foursquare數據集中的好友社交關系數據，因此對2個數據集進行分開實驗：在Gowalla數據集上完整利用了本文提出3種影響力模型，而在Foursquare數據集上只利用了本文所提出的地理影響力模型和時空影響力模型。2個數據集上的實驗結果分別如表2和表3所示，本文所有實驗中對比模型的實驗結果來自文獻＼[20＼]和文獻＼[21＼]。其中MGMPFM模型是基于地理信息建模的，LRT模型是基于時間信息建模的，iGLSR模型是基于地理信息和社交信息建模的。

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

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

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

3.4.2 實驗分析

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

2）用戶簽到POIs數量影響分析 本文僅在Gowalla數據集上進行有關用戶簽到POIs數量影響的實驗和分析，即研究訓練數據量大小對實驗結果的影響。分別對隨機選擇的40%，60%和80%訓練數據進行實驗，對比結果如圖5所示。從圖5可知，在不同比例的數據上，本文模型的性能均優于4種基線模型，說明本文模型很好地解決了當前興趣點推薦任務中的數據稀疏性問題。

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

4 結 語

本文提出了融合多種影響因子的興趣點推薦模型，分別對地理信息、社會信息進行地理影響力建模和社會影響力建模，并聯合時間信息和地理信息進行時空影響力建模，然后以加權求和的方式整合3種影響力評分得到用戶偏好分數，達到了充分利用位置社交網絡中的信息提高興趣點推薦性能的目的。通過與其他模型比較，證明了此模型是有效的。

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

參考文獻/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.