地理分層結(jié)構(gòu)與社會(huì)關(guān)系的興趣點(diǎn)推薦

李昱杭 楊艷 高靜遠(yuǎn)

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

關(guān)鍵詞：矩陣分解;地理分層結(jié)構(gòu);社會(huì)關(guān)系;推薦;興趣點(diǎn)

中圖分類(lèi)號(hào)：TP311 ? ? 文獻(xiàn)標(biāo)識(shí)碼：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）

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

然而，當(dāng)前的大多數(shù)矩陣分解模型都存在一個(gè)問(wèn)題：它們只考慮用戶和POI的偏好，沒(méi)有考慮到用戶的多種社交關(guān)系和最近一段時(shí)間熱門(mén)的POI對(duì)用戶的影響，例如，年輕人可能喜歡去他仰慕的公眾人物簽到過(guò)的POI進(jìn)行簽到，用戶也有更大的可能性喜歡去與他具有相似行為的用戶去過(guò)的POI進(jìn)行簽到。此外，年輕人可能會(huì)去最近比較火暴的店簽到，因此，只考慮用戶偏好和POI的屬性，來(lái)推測(cè)這個(gè)用戶的行為會(huì)降低POI推薦的準(zhǔn)確率。

為了進(jìn)一步提高實(shí)驗(yàn)表現(xiàn)，本文在之前的方法基礎(chǔ)上提出一種新的用戶的社交關(guān)系，并提出全局影響力與熱門(mén)POI的概念，向用戶進(jìn)行更為準(zhǔn)確的POI推薦，提出了一種地理分層結(jié)構(gòu)與社會(huì)關(guān)系的推薦算法（Hierarchical Geographic and Social Matrix Factorization，HGS-MF），實(shí)驗(yàn)結(jié)果表明，在Yelp和Gowalla兩個(gè)真實(shí)數(shù)據(jù)集上與相關(guān)的算法相比較，該算法在召回率，準(zhǔn)確率等評(píng)價(jià)指標(biāo)上相對(duì)于傳統(tǒng)方法都得到了顯著提高。

2 ? 相關(guān)工作（Related work）

近些年，隨著地理位置的社會(huì)網(wǎng)（LBSN）的發(fā)展，研究者可以更方便地分析用戶的簽到記錄進(jìn)而分析用戶的行為習(xí)慣，從而得到其偏好。許多研究者嘗試提高POI推薦模型，從而提高實(shí)驗(yàn)效果。

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

在傳統(tǒng)的基于時(shí)間影響的推薦模型基礎(chǔ)上，文獻(xiàn)[8]—文獻(xiàn)[9]提出時(shí)間感知的協(xié)同過(guò)濾推薦模型，通過(guò)結(jié)合時(shí)間因素和地理影響因素，根據(jù)人們?nèi)粘Ｉ盍?xí)慣劃分時(shí)間軸，并將中午時(shí)段作為午餐時(shí)段，但是每個(gè)人的生活作息不同，用部分人的日常生活習(xí)慣推測(cè)每個(gè)人的行為是不準(zhǔn)確的，并且會(huì)降低POI推薦的效果。

在傳統(tǒng)的基于矩陣分解的推薦模型基礎(chǔ)上，Li等人[10]通過(guò)結(jié)合時(shí)間影響，考慮用戶偏好、地理圖形影響和用戶移動(dòng)性行為，利用地理因子分解方法實(shí)現(xiàn)的POI推薦，但是忽略了社交關(guān)系對(duì)用戶的重要影響;Hu等人[11]根據(jù)用戶簽到頻數(shù)，提取用戶對(duì)POI的偏好，從而實(shí)現(xiàn)POI推薦，但是它沒(méi)有考慮地理因素影響，并且在社交關(guān)系方面考慮的不夠全面;Zhao等人[1]、Lian等人[2]分析用戶的簽到數(shù)據(jù)，發(fā)現(xiàn)用戶簽到行為具有地理規(guī)律，并且發(fā)現(xiàn)POI的類(lèi)別具有一定的層級(jí)關(guān)系，但其未考慮用戶的社會(huì)關(guān)系，并且在POI的影響力方面考慮的不全面。

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

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

3.1 ? 基礎(chǔ)模型

3.1.1 ? 加權(quán)矩陣分解模型

給定用戶簽到頻數(shù)矩陣，其中M、N分別為用戶的個(gè)數(shù)和POI個(gè)數(shù)，矩陣中每一項(xiàng)表示用戶在POI 簽到的次數(shù)。

3.2 ? HGS-MF算法

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

3.2.1 ? 社會(huì)關(guān)系

在現(xiàn)實(shí)生活中，用戶在訪問(wèn)某POI時(shí)，更傾向于傾聽(tīng)朋友的意見(jiàn)。用戶的朋友往往與用戶擁有相同的行為習(xí)慣，在用戶未訪問(wèn)過(guò)的POI，用戶往往會(huì)聽(tīng)從朋友的推薦[12]。

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

定義1（用戶好友關(guān)系矩陣）：設(shè)F為用戶的好友列表，滿足，矩陣中每一項(xiàng)表示用戶與用戶的好友關(guān)系，如果滿足好友關(guān)系，則值為1，否則為0。

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

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

5 ? 結(jié)論（Conclusion）

本文利用用戶的社會(huì)關(guān)系，提出了一個(gè)新的用戶相似性度量、全局影響力以及熱門(mén)POI的概念，在此基礎(chǔ)上提出結(jié)合分層地理矩陣分解模型得到HGS-MF模型，利用兩步優(yōu)化，第一步優(yōu)化采用交替最小二乘法和梯度下降方法求解單層模型，第二步采用KKT條件優(yōu)化分層模型。實(shí)驗(yàn)結(jié)果表明，融合社會(huì)關(guān)系與熱門(mén)POI影響力的加權(quán)矩陣分解能夠有效地提高推薦性能，模型優(yōu)于傳統(tǒng)的POI推薦算法。未來(lái)將嘗試將本文提出的模型和深度學(xué)習(xí)相結(jié)合，期待進(jìn)一步提高興趣點(diǎn)推薦性能。

參考文獻(xiàn)（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，F(xiàn)u 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.

作者簡(jiǎn)介：

李昱杭（1997-），女，碩士生.研究領(lǐng)域：社會(huì)網(wǎng)，數(shù)據(jù)挖掘.

楊 ?艷（1975-），女，博士，教授.研究領(lǐng)域：社會(huì)網(wǎng)，數(shù)據(jù)挖掘.本文通訊作者.

高靜遠(yuǎn)（1994-），男，碩士生.研究領(lǐng)域：社會(huì)網(wǎng)，POI推薦.