基于相似度融合和動態預測的興趣點推薦算法

李心茹，夏 陽，張碩碩

中國礦業大學 計算機學院，江蘇 徐州 221000

1 引言

社會經濟的快速發展，給人們的生活帶來更多的樂趣，人們興趣點（如旅游景點、博物館、賓館、餐廳等）的數量也飛速增長，且會根據個人愛好選擇與自己興趣相投的興趣點[1-2]。如何幫助用戶從大量的興趣點中發現自己感興趣的點是一個困難的問題，興趣點推薦就是幫助用戶篩選出與用戶興趣一致的位置并且縮短決策的時間。

目前，大多數興趣點推薦算法是基于興趣點的歷史簽到數據及上下文信息（如時間、地理位置、標簽、評論等）來挖掘符合用戶偏好且尚未訪問的興趣點，并改善用戶簽到矩陣的稀疏性問題和冷啟動問題。高榕等人[3]提出了使用LDA主題模型提取用戶特征向量融入矩陣分解，利用矩陣分解進行填充缺失評分。Degemmis等人[4]研究了一種矩陣填充技術，將評分矩陣中的缺失值填充為一種缺省值，以此緩解數據稀疏性問題。Gao等人[5]在興趣點推薦時利用了POI相關的描述信息和用戶個人情緒信息。Yin等人[6]利用LDA主題模型，預測用戶的興趣度，每個主題通過學習用戶的歷史簽到數據和POI的分類信息得到。Ren等人[7]將興趣、地理、社會等六種上下文信息分別建模，融入到概率矩陣模型中。Zhao等人[8]借鑒了社會上的用戶評分為用戶進行評分預測，并將用戶個人興趣、人際交往評分相似性等四種因素融合到矩陣分解中。

總體來說，上述的興趣點推薦算法都一定程度上提高了推薦質量，緩解了數據稀疏性，但是也存在一些問題：（1）模型計算復雜度太高，模型訓練時間過長。（2）部分算法在計算相似度時僅使用用戶的簽到評分，而由于POI簽到矩陣的高稀疏性，會導致推薦結果不準確。（3）矩陣填充技術，由于缺省值設置不準確，由此引來了新的誤差[9]。（4）算法中大都利用用戶簽到的歷史數據，而忽略了用戶的評論和標簽等信息，不能很好地解決冷啟動問題。

針對上述興趣點推薦面臨的問題及上述研究存在的不足，本文提出了一種基于相似度融合和動態預測的興趣點推薦算法，該算法命名為SI-DP（point of interest recommendation algorithm based on Similarity Integration and Dynamic Prediction）。該算法的基本思想是：首先將用戶的評論信息、標簽信息及POI相關的文本信息各自進行主題建模進行相似度計算，并且利用用戶簽到數據進行相似度度量，兩者融合，很好地解決了推薦系統中的冷啟動問題，并且提高了推薦的質量，最后在推薦生成階段，利用動態預測法填補缺失的訪問概率，緩解了數據稀疏性問題，降低了算法的復雜性。

概括起來，本文做出了兩點對興趣點的貢獻：

（1）由于興趣點推薦中的數據除了包含用戶的簽到評分之外，還有用戶評論、標簽、地理位置等上下文信息，本文利用潛在的LDA主題模型挖掘興趣點和用戶相關的文本信息，學習用戶的興趣特征，利用用戶的興趣特征向量進行相似性度量。并且使用傳統的興趣點推薦方法計算用戶相似度，然后和利用LDA模型提取用戶特征計算的用戶相似度進行線性融合，很好地解決了推薦系統中的冷啟動問題。

（2）在推薦生成階段，使用動態預測的方法計算最近鄰居缺失的訪問概率，降低了算法的復雜性，提高了推薦質量。本文在一個真實數據集上進行了實驗，實驗結果表明：相比其他主流算法，本文提出的算法在推薦的準確率和召回率上提高了很多。

傳統基于內存的協同過濾算法[10]分兩種：基于用戶的協同過濾算法和基于物品的協同過濾算法。本文使用的是基于用戶的協同過濾算法，其基本思想為：在推薦系統中，當用戶A需要推薦時，先找到和用戶A有相似興趣的用戶，然后把那些符合用戶偏好的、而用戶A未知的興趣點推薦給A。

傳統的基于協同過濾的興趣點推薦算法主要分為以下幾個步驟：生成用戶興趣模型、發現最近鄰集[11]、計算訪問概率、生成推薦列表。

在預測用戶對某興趣點的訪問概率時，基于用戶的協同過濾算法為：首先根據用戶的興趣點訪問序列[12]計算出該用戶與其他用戶的相似性，然后選取若干個最相似的用戶[13]，并對這些相似用戶指定興趣點的訪問記錄值加權求和。

定義用戶集合為U，興趣點集合為P，用戶對興趣點的訪問矩陣為C，其中用戶cu,p=1表示用戶u∈U訪問過興趣點 p∈P，cu,p=0表示u沒有訪問過興趣點p。給定用戶u，如果該用戶沒有訪問過興趣點 p，那么u在未來訪問 p的概率為：

其中u與v的相似性為用戶v的權重wu,v。

在公式（1）中，用戶間的相似性權重可以由很多方法計算得來，本文主要應用余弦相似性[14]來計算兩個用戶之間的相似性。對于用戶v與u，其余弦相似性的計算公式為：

LDA主題模型[15]是2003年由Blei等人提出。可以用來識別大規模文檔集（document collection）或語料庫（corpus）中潛藏的主題信息。它將文檔中的主題以概率分布的形式給出，從而得到了文檔的主題分布，最后再根據主題進行分類或者聚類。在文本信息分析中，LDA模型除了兼顧文本的多語義性之外，還有降維的作用。對于用戶或者POI來說，將用戶或者POI相關的文本信息輸入進去，可以挖掘它們的潛在主題特征，從而用主題向量表示[16]。

LDA主題模型的生成過程為：首先，隨機選擇話題分布θ；然后，對文檔中的每個詞w，先從第一點中產生的分布中隨機選擇一個話題z，再按照主題z的單詞概率生成一個詞w。LDA模型如圖1所示。

圖1 LDA模型

其中α和β表示語料級別的參數，θ是一個K維主題向量。

用戶或POI的潛在特征挖掘過程可以看作生成過程的逆過程。

2 SI-DP推薦算法

為了緩解數據稀疏性和冷啟動問題，本算法使用LDA主題模型構建用戶特征向量，進行相似性度量，同時結合簽到數據進行相似性度量。一般情況下，擁有相似主題特征而且同時簽到過很多興趣點的用戶更相似，所以本文將兩種相似性度量線性融合，發現最近鄰居集，該相似度融合算法命名為SI（Similarity Integration）算法。在預測訪問概率階段，為了降低算法復雜性的同時提高推薦質量，提出一種動態預測法，動態填充最近鄰對當前興趣點訪問缺失的簽到數據，本文將該算法命名為DP（Dynamic Prediction）算法。

2.1 基于LDA模型的相似性度量

傳統的基于協同過濾的興趣點推薦算法在進行用戶間相似性度量時僅考慮用戶簽到評分數據，忽略了用戶的評論和標簽等信息對相似度的影響。對此，本文提出使用LDA主題模型從用戶評論和標簽等信息中提取用戶和興趣點的潛在特征，并進行相似性度量。該算法首先匯集與同一個POI有關的所有評論和描述信息到一個文檔即 pi，然后把同一用戶簽到過的POIs的所有的評論和用戶標簽等信息，匯集到一個文檔即uj，這樣獲得了一個包含大量的文檔集合，每一個文檔對應著一個POI或者一個用戶。給定POI和用戶中隱含的主題數K，最終需要得到一個POI和用戶的主題分布θp和θu，θp和θu都為K維向量，每一維代表該POI或者用戶在相應主題下的概率。

通過LDA主題模型得到每個POI或者用戶的主題特征，用戶i的主題向量用θui表示，興趣點 j的主題向量用θpj表示，表示用戶i屬于主題m的概率，wm

(pj)表示興趣點 j屬于主題m的概率，則基于主題求出用戶最近鄰如公式（3）所示：

基于主題求出的POI的最近鄰如公式（4）所示：

2.2 使用SI算法選擇最近鄰居集合

本文在傳統的基于簽到數據度量相似性的基礎上，融合了2.1中基于LDA主題模型的相似性計算，將兩種相似度進行線性融合。假設使用LDA模型求解出的用戶的最近鄰集合為Ul={ul1,ul2,…,ulm}，基于簽到數據度量相似性的方法求解出的最近鄰集合為Ut={ut1,ut2,…,utn}，則用戶的最近鄰集合表示為Ub=Ul?Ut，對于最近鄰集的交集Uj=Ul?Ut，在預測訪問概率時將賦予更高的權重。用戶的相似度設置為：

其中，siml(ua,ub)為使用LDA主題模型建模后求解出了相似性，simt(ua,ub)為基于傳統利用簽到數據求出的相似性。μ為參數，本文設置為0.6。

2.3 基于DP算法的訪問概率預測及推薦列表的生成

在興趣點推薦中，由于數據的高稀疏性，所以在利用求得的最近鄰居集進行訪問概率預測時，常常出現最近鄰對當前興趣點的簽到缺失的情況，為了進一步緩解數據稀疏性，本文引入動態填充評分的思想，避免帶來新的誤差。動態預測，即動態填充用戶當前缺失的簽到數據，當出現最近鄰對當前POI簽到缺失情況，即利用公式（4）求出當前POI的近鄰集，然后基于近鄰集對近鄰預測當前POI的訪問概率，最后利用基于用戶的預測方法進行訪問概率預測。

假設目標用戶為u，當前POI為 p，用戶的最近鄰集為M，用戶h為最近鄰集的任意用戶，則用戶h對當前POI的訪問預測為：

其中N為用戶h最近鄰POI集，sim(p ,l)為利用公式（4）求得的興趣點 p和興趣點l的相似度。最終，用戶u對當前POI的訪問概率為：

其中v表示用戶u的最近鄰集，wu,h表示用戶u和用戶h的相似度權重。根據公式（7）計算出用戶的預測訪問概率，再按訪問概率的大小進行排序，選擇前N個最大的POI生成目標用戶top-N的推薦列表。

3 實驗及實驗結果分析

3.1 實驗數據集

本文在實驗中采用了真實的數據集，Foursquare數據集，該數據集為公開數據集，Foursquare是一個基于位置的社交網絡，允許用戶簽到。考慮到算法的準確性，本文將少于5次簽到的用戶和POI過濾掉。本文實驗所使用的數據集包含5 234個用戶，6 839個POI和48 294條簽到或者評價。由于數據集中用戶-興趣點矩陣密度非常低而造成了很多主流的興趣點推薦算法的精度低，所以本文的數據集中，用戶-興趣點矩陣密度較低，最終得到的準確率偏低也是合理的。

3.2 評價指標

關于推薦性能，本文采用了兩個廣泛使用的指標評估TopN的興趣點推薦性能，即召回率Recall和準確率Precision，簡寫為Rr和Pr，對于目標用戶uj，Pr表示前r個被推薦的興趣點命中測試集上的興趣點的比例,Rr表示前r個被推薦的興趣點被用戶實際訪問過的占多少比例。具體計算方法如下列公式所示，其中V()uj表示用戶uj簽到過的POI，R()uj表示前r個被推薦的POI。

其中T表示測試集中的用戶量。

3.3 實驗結果及分析

為了驗證本文推薦算法的質量，本文將數據集分為80%的測試集和20%的訓練集。同時本文做了三組對比實驗，分別對比了COS、SI、LDA-CF三種算法的有效性來驗證本算法的有效性。對比算法詳細描述如下：

（1）COS，基于余弦相似性的協同過濾推薦算法，該方法只利用用戶的簽到數據計算相似性，沒有用戶相關的上下文信息。

（2）SI，基于LDA主題模型挖掘標簽信息的主題特征向量和傳統基于簽到數據進行相似度度量的融合，該方法在使用LDA主題模型進行潛在特征向量挖掘時，僅使用了用戶和POI的標簽信息。

（3）LDA-CF，基于矩陣分解和LDA主題模型相結合的興趣點推薦算法。

3.3.1 參數影響

關于鄰居集中最近鄰個數K，圖2和圖3展現出在不同近鄰個數下本文推薦算法和其他算法的比較。由圖2可知，在鄰居數大于60時，推薦的準確率和召回率明顯提升，在120～140時最高，本文將最近鄰數K設置到160。經過多次實驗，進行最近鄰實驗時，本文將SI、SI-DP算法所需的話題數設置在70。

圖2 不同近鄰下三種算法準確率對比圖

圖3 不同近鄰下三種算法召回率對比圖

從圖2和圖3中可以看出，與COS相比，SI算法的召回率和準確率都有明顯的提升，表明采用LDA模型與利用簽到數據相似度融合的方法使得用戶偏好的興趣點出現的次數有所增加，并且有助于提高推薦算法的質量。同時融合LDA模型的相似度計算方法一定程度上緩解傳統協同過濾算法的冷啟動問題。不同近鄰數量下，SI-DP與COS相比，準確率和召回率形成明顯對比，表明SI和動態預測相結合的算法優于COS推薦算法，同時準確率和召回率的提高明顯高于SI算法，說明融合的動態預測算法降低了預測誤差，提高了推薦算法的準確率。

實驗中，首先在數據集上針對LDA-CF、SI、SI-DP算法中用到的不同數量的話題進行參數的調整，確定達到最優結果的主題數量值，然后進行不同算法的效果比較，由圖4和圖5可以看出，隨著主題數量的增加，準確率和召回率都在不斷增加，在K=70時，達到最優結果，參數調整時，本文設置top-N中N的數量為10，最近鄰數量設置在140。

圖4 準確率

圖5 召回率

3.3.2 實驗結果分析

經過參數的調整實驗，本文將最近鄰數量設置為140，話題數量設置為70，關于前K個推薦給用戶的POI，如圖6和圖7展現出了本文所提的SI-DP算法與其他主流興趣點推薦算法的推薦準確度比較結果。從圖中可以明顯看出：隨著推薦列表中被推薦的POIs數量K的增加，準確率降低、召回率上升。因為用戶簽到矩陣的密度低，所以興趣點推薦算法的精度不是很高。

圖6 四種算法準確率對比圖

圖7 四種算法召回率對比圖

分別對比了COS、SI、LDA-CF三種算法，從兩幅圖中可以直觀地看出，SI-DP算法的推薦精確度明顯優于其他三種算法，所提出的SI和主流算法中的LDA-CF的推薦精度相差不大，較COS有明顯的改變。

綜合上述多個對比實驗說明，基于主題模型和動態預測的興趣點推薦算法可以減少預測誤差，緩解數據稀疏和冷啟動問題并且提高了推薦算法質量。

4 結束語

對于興趣點推薦中的數據稀疏問題和傳統協同過濾中的冷啟動問題，本文提出了首先利用LDA模型挖掘用戶的潛在特征向量，然后進行相似度計算。同時利用傳統的協同過濾算法中使用簽到數據計算相似度，最后將兩者融合，使用戶的相似性更貼近于真實。為了進一步緩解興趣點簽到矩陣的高稀疏性，在訪問概率預測時加入了動態預測方法，進而提出一種基于相似度融合和動態預測的興趣點推薦算法。真實數據集上的實驗結果表明，本文提出的SI-DP推薦算法優于其他幾種主流推薦算法。

：

[1]劉樹棟，孟祥武.基于位置的社會化網絡推薦系統[J].計算機學報，2015，38（2）：322-336.

[2]Ye Mao，Yin Peifeng，Lee W C，et al.Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proc of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM Press，2011：325-334.

[3]高榕，李晶，杜博，等.一種融合情景和評論信息的位置社交網絡興趣點推薦模型[J].計算機研究與發展，2016，53（4）：752-763.

[4]Degemmis M，Lops P，Semeraro G.A content-collaborative recommender that exploits word net-based user profiles for neighborhood formation[J].User Modeling and User-adapted Interaction，2007，17（3）：217-255.

[5]Gao H J，Tang J L，Hu X，et al.Content-aware point of interest recommendation on location-based social networks[C]//Proceedingsofthe29thAAAIConference on Artificial Intelligence，Astin，USA，2015：1721-1727.

[6]Yin H，Cui B，Sun Y Z，et al.LCARS：A spatial item recommender system[J].ACM Transactions on Information Systems，2014，32（3）.

[7]Ren X，Song M，Haihong E，et al.Context-aware probabilistic matrix factorization modeling for point-of-interest recommendation[J].Neurocomputing，2017，241（7）：38-55.

[8]Zhao G S，Qian X M，Xie X.User-service rating prediction by exploring social users’rating behaviors[J].Journal of IEEE Transactions on Multimedia，2016，18（3）：496-506.

[9]Leng Yajun，Lu Qing，Liang changyong.Survey of recommendation based on collaborative filtering[J].Pattern Recognition and Artificial Intelligence，2014，27（8）：720-734.

[10]Jiang S H，Qian X M，Shen J L，et al.Author topic model-based collaborative filtering for personalized POI[J].Journal of IEEE Transactions on Multimedia，2015，17（6）：907-918.

[11]Bart P，Knijnenburg，Sivakumar S，et al.Recommender systems for self-actualization[C]//Proceedings of the 10th ACM Conference on Recommender Systems，Boston，MA，USA，2016：11-14.

[12]Cheng C，Yang H，Lyu M R，et al.Where you like to go next：Successive point-of-interest recommendation[C]//Proceedings of the 23th International Conference on Artificial Intelligence，Beijing，China，2013：2605-2611.

[13]Sun Guangfu，Wu Le，Liu Qi，et al.Recommendations based on collaborative filtering by exploiting sequential behaviors[J].Journal of Software，2013，24（11）：2721-2733.[14]Zhao Qinqin，Lu Kai，Wang Bin.SPCF：a memory based collaborative filtering algorithm via propagation[J].Chinese Journal of Computers，2013，36（3）：671-676.

[15]Silva E D S D.New probabilistic models for recommender systems with rich contextual and content information[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining，New York，2017.

[16]任星怡，宋美娜，宋俊德.基于用戶簽到行為的興趣點推薦[J].計算機學報，2017，39（1）：28-51.