地理分層結構與社會關系的興趣點推薦

李昱杭 楊艷 高靜遠

摘 ?要：隨著基于地理位置的社交網絡的興起，興趣點（POI）推薦引起了人們的許多關注。POI推薦向用戶推薦他們可能感興趣但沒有訪問過的地方，從而解決用戶“下一步去哪”的問題。本文提出新的用戶相似性度量、全局影響力以及熱門POI的概念。綜合考慮了多個影響因素之間的關系，以地理分層結構的矩陣分解模型（HGMF）為基礎，提出新的POI推薦算法HGS-MF。在Yelp和Gowalla社交網絡數據集上對HGS-MF進行了評估。實驗結果表明，HGS-MF方法的實驗表現均優于傳統的POI推薦算法。

關鍵詞：矩陣分解;地理分層結構;社會關系;推薦;興趣點

中圖分類號：TP311 ? ? 文獻標識碼：A

Abstract：With the rise of location-based social networks，Points of Interest （POI） recommendations have attracted a lot of attention.The POI recommends places which users may be interested in but have not visited，thus addressing the user's issue about Where to Go Next.This paper proposes new user similarity measures，global influences，and the concept of popular POIs.Based on the relationship between multiple influencing factors，a new POI recommendation algorithm HGS-MF is proposed based on the Hierarchical Geographical Matrix Factorization model （HGMF）.HGS-MF is evaluated on the social network datasets of Yelp and Gowalla.The experimental results show that the performance of the HGS-MF method is superior to that of the traditional POI recommendation algorithm.

Keywords：matrix factorization;geographical hierarchy;social relationship;recommendation;Points of Interest

1 ? 引言（Introduction）

隨著移動設備的普及與定位技術的進步，越來越多的人們通過社交軟件分享生活。由于大規模移動記錄的易得性和社交網絡信息的廣泛性，POI推薦成為熱門的話題，很多研究工作者通過對用戶的簽到記錄進行分析，從而獲取用戶的偏好。例如：Zhao等人[1]、Lian等人[2]、Liu等人[3]對用戶的簽到數據進行分析，發現用戶簽到行為具有一定的地理規律，通過簽到行為可以將完全不吸引用戶的地點與未被發現但可能吸引用戶的地方進行區分。此外，POI的類別具有一定的層級關系，某些類別的POI可以進一步地劃分，用戶的內容偏好也同樣呈現出一定的層次結構[4]。

然而，當前的大多數矩陣分解模型都存在一個問題：它們只考慮用戶和POI的偏好，沒有考慮到用戶的多種社交關系和最近一段時間熱門的POI對用戶的影響，例如，年輕人可能喜歡去他仰慕的公眾人物簽到過的POI進行簽到，用戶也有更大的可能性喜歡去與他具有相似行為的用戶去過的POI進行簽到。此外，年輕人可能會去最近比較火暴的店簽到，因此，只考慮用戶偏好和POI的屬性，來推測這個用戶的行為會降低POI推薦的準確率。

為了進一步提高實驗表現，本文在之前的方法基礎上提出一種新的用戶的社交關系，并提出全局影響力與熱門POI的概念，向用戶進行更為準確的POI推薦，提出了一種地理分層結構與社會關系的推薦算法（Hierarchical Geographic and Social Matrix Factorization，HGS-MF），實驗結果表明，在Yelp和Gowalla兩個真實數據集上與相關的算法相比較，該算法在召回率，準確率等評價指標上相對于傳統方法都得到了顯著提高。

2 ? 相關工作（Related work）

近些年，隨著地理位置的社會網（LBSN）的發展，研究者可以更方便地分析用戶的簽到記錄進而分析用戶的行為習慣，從而得到其偏好。許多研究者嘗試提高POI推薦模型，從而提高實驗效果。

在傳統的基于用戶的協同過濾模型基礎上，文獻[5]—文獻[6]融合用戶偏好、社會影響和地理影響因素，旨在提高推薦的準確性，但它沒有考慮POI具有一定地理層級的關系，比如美術家更喜歡去美術博物館簽到，而不是普通博物館;Li等人[7]根據社交朋友和類似用戶的簽到記錄建模，從而提高模型的實驗表現，但它考慮社交因素不夠全面，并未考慮公眾人物對用戶的影響。

在傳統的基于時間影響的推薦模型基礎上，文獻[8]—文獻[9]提出時間感知的協同過濾推薦模型，通過結合時間因素和地理影響因素，根據人們日常生活習慣劃分時間軸，并將中午時段作為午餐時段，但是每個人的生活作息不同，用部分人的日常生活習慣推測每個人的行為是不準確的，并且會降低POI推薦的效果。

在傳統的基于矩陣分解的推薦模型基礎上，Li等人[10]通過結合時間影響，考慮用戶偏好、地理圖形影響和用戶移動性行為，利用地理因子分解方法實現的POI推薦，但是忽略了社交關系對用戶的重要影響;Hu等人[11]根據用戶簽到頻數，提取用戶對POI的偏好，從而實現POI推薦，但是它沒有考慮地理因素影響，并且在社交關系方面考慮的不夠全面;Zhao等人[1]、Lian等人[2]分析用戶的簽到數據，發現用戶簽到行為具有地理規律，并且發現POI的類別具有一定的層級關系，但其未考慮用戶的社會關系，并且在POI的影響力方面考慮的不全面。

這些算法雖然在一定程度上解決了POI推薦領域上的一些問題，但是仍具有一定的局限性，例如：用戶相似性的影響因素選取過于單一，沒有充分挖掘POI的熱門信息，沒有充分利用用戶的社交關系。本文基于分層地理矩陣分解模型。提出一種新的用戶的社交關系，并提出全局影響力與熱門POI的概念，從而向用戶進行更為準確的POI推薦。

3 ? HGS-MF算法（HGS-MF algorithm）

3.1 ? 基礎模型

3.1.1 ? 加權矩陣分解模型

給定用戶簽到頻數矩陣，其中M、N分別為用戶的個數和POI個數，矩陣中每一項表示用戶在POI 簽到的次數。

3.2 ? HGS-MF算法

本算法在HGMF模型的基礎上進行改進，提出新的用戶相似性度量、全局影響力和熱門POI的概念。

3.2.1 ? 社會關系

在現實生活中，用戶在訪問某POI時，更傾向于傾聽朋友的意見。用戶的朋友往往與用戶擁有相同的行為習慣，在用戶未訪問過的POI，用戶往往會聽從朋友的推薦[12]。

本文認為社交關系由用戶相似度與用戶的影響力兩方面組成。在目前已有的用戶相似度計算中，只考慮在相同POI簽到的用戶的相似性，以及擁有公共好友的用戶相似性，并沒有考慮到用戶的多種社交關系和最近一段時間熱門的POI對用戶的影響。本文在這兩種相似度的基礎上提出時間影響下的用戶相似性，并且在目前已有的POI推薦中，沒有在社交關系中考慮到用戶的影響力因素，本文提出了用戶全局影響力，并融入社交關系中。

定義1（用戶好友關系矩陣）：設F為用戶的好友列表，滿足，矩陣中每一項表示用戶與用戶的好友關系，如果滿足好友關系，則值為1，否則為0。

定義2（時間影響用戶行為矩陣）：設T為在時間影響下的用戶的行為矩陣，本文將時間分為24小時，滿足，矩陣中每一項表示用戶i在時間段內在POI 的簽到情況，如果簽到則為1，否則為0。

根據對比可以看出，在參數均最優的情況下，HGS-MF模型在精確率與召回率兩方面都高于其他算法。

5 ? 結論（Conclusion）

本文利用用戶的社會關系，提出了一個新的用戶相似性度量、全局影響力以及熱門POI的概念，在此基礎上提出結合分層地理矩陣分解模型得到HGS-MF模型，利用兩步優化，第一步優化采用交替最小二乘法和梯度下降方法求解單層模型，第二步采用KKT條件優化分層模型。實驗結果表明，融合社會關系與熱門POI影響力的加權矩陣分解能夠有效地提高推薦性能，模型優于傳統的POI推薦算法。未來將嘗試將本文提出的模型和深度學習相結合，期待進一步提高興趣點推薦性能。

參考文獻（References）

[1] Zhao P，Xu X，Liu Y，et al.Exploiting Hierarchical Structures for POI Recommendation[J].IEEE International Conference on Data Mining （ICDM），2017：655-664.

[2] Lian D，Zhao C，Xie X，et al.GeoMF：Joint Geographical Modeling and Matrix Factorization for Point-of-Interest Recommendation[C].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.ACM，2014：831-840.

[3] Liu B，Fu Y，Yao Z，et al.Learning geographical preferences for point-of-interest recommendation[C].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.ACM，2013：1043-1051.

[4] Moreno-Jimenez J M，Vargas L G.A Probabilistic Study of Preference Structures in the Analytic Hierarchy Process with Interval Judgments[J].Mathematical and Computer Modelling，1993，17（4-5）：73-81.

[5] Ye M，Yin P，Lee W C .Location recommendation for location-based social networks[C].Acm Sigspatial International Symposium on Advances in Geographic Information Systems.DBLP，2010：458.

[6] Ye M，Yin P F，Lee W C，et al.Exploiting Geographical Influence for Collaborative Point-of-interest Recommendation[C].International Acm Sigir Conference on Research & Development in Information Retrieval.ACM，2011：325-334.

[7] Li H，Hong R，Zhu S，et al.Point-of-Interest Recommender Systems：A Separate-Space Perspective[C].2015 IEEE International Conference on Data Mining （ICDM）.IEEE Computer Society，2015：231-240.

[8] Yuan Q，Cong G，Ma Z，et al.Time-aware point-of-interest recommendation[C].International Acm Sigir Conference on Research & Development in Information Retrieval.ACM，2013：363-372.

[9] Yuan Q，Cong G，Sun A.Recommendation with Geographical and Temporal Influences[C].Acm International Conference on Conference on Information & Knowledge Management.ACM，2014：659-668.

[10] LiX T，CongG，et al.Rank-GeoFM：A Ranking based Geographical Factorization Method for Point of Interest Recommendation[C].Proceedings of the 38th International ACM SIGIR Conferenceon Researchand Development in Information Retrieval，2015：433-442.

[11] Hu Y，Koren Y，Volinsky C.Collaborative Filtering for Implicit Feedback Datasets[C].Eighth IEEE International Conference on Data Mining.2008：263-272.

[12] 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：364-373.

[13] Xianyi Z，Qian W，Yunquan Z.Model-driven Level 3 BLAS Performance Optimization on Loongson 3A Processor[C].2012 IEEE 18th International Conference on Parallel and Distributed Systems.IEEE，2012：684-691.

[14] Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C].International Conference on World Wide Web，2001：285-295.

作者簡介：

李昱杭（1997-），女，碩士生.研究領域：社會網，數據挖掘.

楊 ?艷（1975-），女，博士，教授.研究領域：社會網，數據挖掘.本文通訊作者.

高靜遠（1994-），男，碩士生.研究領域：社會網，POI推薦.