Personalized Ranking Metric Embedding forNext New POI Recommendation

摘 要：基于位置的社交網絡（LBSNS）的快速發展提供了大量的記錄數據，這能夠提供許多服務，比如，信息點（POI）推薦。在本文中，我們研究了一個新的POI推薦的問題，使新的信息點基于用戶的當前位置來被推薦。這個挑戰在于精確的了解用戶的序列信息和個性化推薦模型是有難度的。為此目的，我們求助于公制嵌入方法的推薦，這就避免了矩陣分解技術的缺點。我們提出了一個個性化的排名指標嵌入方法（PRME）來模擬個性化序列。實驗基于兩個現實世界LBSN數據集，結果顯示為我們的新算法優于最先進的POI推薦方法。

關鍵詞：社交網絡、信息點、馬爾可夫鏈算法、數據集

1. Introduction

隨著基于位置的社交網絡（LBSNS）的日益普及，用戶想通過記錄POIs來分享他們的位置。大量的記錄數據提供了機會來更好地了解用戶的移動性的行為，在此基礎上推薦的POI將成為有價值的。 POI的推薦是很有價值的，它可以幫助用戶探索他們周圍的環境。POI推薦的重要性是已經引起了大量的對開發推薦技術感興趣的研究。

相比于POI推薦，下一個POI推薦目前受到的關注較少。除了用戶的偏好，下一個POI推薦額外考慮了用戶的記錄序列信息。因為人體行為表現出的有序模式，有序行為對POI的推薦很重要。我們分析兩個真實世界的數據集來驗證用戶的有序行為。我們開發了一個公制嵌入算法來模擬POI的有序轉移。為了模擬個性化序列信息，我們提出了一種新穎的PRME算法，它既考慮到有序轉移也考慮到用戶偏好。

2. Related Work

定位推薦最近吸引了深入的研究關注。大多數以前的方法是基于協同過濾（CF）技術。其中最流行的CF算法是基于用戶的CF，它利用相似用戶簽入的用于建議的目的。在基于CF算法主要利用用戶的喜好提出建議。目前，地域的影響力已經融合與CF的算法，以提高POI建議。例如，混合高斯分布和冪律分布已經提出來建模地域影響。

3. Next New POI Recommendation

我們使用兩個可公開獲得的數據集。第一個數據集是在新加坡Foursquare的簽到，而第二個是在加利福尼亞州和內華達州Gowalla的簽到數據集。我們用這兩個數據集一年的數據。每辦理入住手續是<用戶的形式的元組； POI；時間>。各個POI與緯度和經度相關聯。我們剔除誰擁有簽入少于10個興趣點的用戶，以及已經訪問了少于10個用戶的興趣點。

3.1 Observations on real-world datasets

觀察1：新的位置的探索，圖1示出的新的POI對所有用戶上兩個數據集，每50天平均比率。例如，該比率在第100天是POI的比例拜訪，但沒有被訪問過在先前天第100天。新的POI的比例是相當高的（大部分在0.4以上的比例）的兩個數據集，這意味著人們總是喜歡探索新的興趣點。這種觀察是根據最近的研究結果[連等人，2013]。

觀察2：暫時影響，圖2（a）示出兩個連續的簽入的時間差的累積分布函數（CDF）。圖2（a）表明，50%以上的連續檢查插件發生在少于24小時。與此同時，許多連續的簽入發生在較長的時間。為25%以上的連續的簽到，他們的時間差異超過48小時大。

（圖1顯示了新的POI對所有用戶上兩個數據集，每50天平均比率）

觀察3：空間影響，我們計算了兩個連續簽入的地理距離并繪制在圖2（b）的CDF分布，這表明70%連續簽到有不足10公里的兩個數據集。該CDF曲線增加快時，距離小，這意味著大多數簽到發生在附近地區。該結果表明用戶的下一個動作由它們的當前的位置的影響。這一發現是根據所報告的結果。

.（圖（a）顯示兩個連續的記錄數據之間的時間差的累積分布函數圖（b）顯示了兩個連續的記錄數據之間的地理位置距離的累積分布函數）

3.2 Next new POI problem definition

當兩個簽入發生在很短的時間內，馬爾可夫鏈屬性存。根據觀測1，用戶傾向于訪問新的POI為他們的勘探利益，這表明這表明新的POI為用戶的問題是有意義的。

根據一個很短的時間周期和新的POI用戶意愿內連續屬性，我們正式定義下面N2-POI建議問題。

對于一組用戶的U和一組的POI L，C是歷史校驗數據，并且 是一組POI中的用戶U已經訪問過。鑒于用戶u當前POIlC 時， N2-POI問題是推薦一套POI ，可實現用戶U接下來的訪問和興趣點是新的用戶

4 Personalized Ranking Metric Embedding

為了模擬順序信息，我們需要在馬爾可夫鏈模型的轉移概率。然而，由于該數據稀疏，這是不可行通過使用標準計數方法估計的轉換。度量嵌入模型可以用來處理數據稀疏和推廣到未觀察到的數據。我們代表每個POI作為一個潛在的空間中的一個點。我們假設在潛在空間的POI之間的歐幾里德距離反映了轉換概率。距離越大，轉場的強度越低。

I

where ，

在度量嵌入模型，將各個POI升具有在K維空間中的位置X（l）。鑒于觀察到的連續的POI轉換，目標是學習所有POI的位置。我們涉及的一對，li和lj的轉移概率，以歐氏距離的公式定義。

其中 ，K為潛在空間和Z（LI）的維數， 是正常化術語。

5.Conclusion and FutureWork

在本文中，我們研究了下一個新的POI推薦的問題。我們提出了一個新穎的成對公制嵌入來模型化連續的POI轉移。我們進一步發展出PRME-G，這個模型連接了三個因素：連續轉移，個人偏好和地域的影響力。我們的算法性能表現在兩個數據集中進行大量的實驗。幾個有趣的未來發展方向可以作進一步的探索，例如產品的推薦和朋友的推薦。

References

[Chen et al.， 2012] Shuo Chen， Josh L Moore， Douglas Turnbull， and Thorsten Joachims. Playlist prediction via metric embedding. In KDD， pages 714–722， 2012.

[Chen et al.， 2013] Shuo Chen， Jiexun Xu， and Thorsten Joachims. Multi-space probabilistic sequence modeling. In KDD， pages 865–873， 2013.

[Chen et al.， 2015] Xuefeng Chen， Yifeng Zeng， Gao Cong， Shengchao Qin， Yanping Xiang， and Yuanshun Dai. On information coverage for location category based point-ofinterest recommendation. In AAAI， pages 37–43， 2015.

[Cheng et al.， 2012] Chen Cheng， Haiqin Yang， Irwin King， and Michael R Lyu. Fused matrix factorization with geographical and social influence in location-based social networks. In AAAI， 2012.

[Cheng et al.， 2013] Chen Cheng， Haiqin Yang， Michael R Lyu， and Irwin King. Where you like to go next： Successive point-of-interest recommendation. In IJCAI， pages 2605–2611， 2013.

作者簡介：

尹榮（1992.8.4—）， 男，漢，上海，本科，中國電信股份有限公司上海分公司、助理工程師、項目管理。