一種改進的基于位置的推薦算法

劉建東

摘要：基于位置的推薦算法在根據位置信息劃分數據子集時會產生數據稀疏問題，對此提出了一種改進的推薦算法。該算法充分考慮了不同位置所產生的推薦結果的差異性，分別為相應的推薦結果設置不同權重，然后線性求和。改進算法既解決了數據的稀疏問題，又考慮了用戶興趣的本地化。實驗結果表明，改進的算法提高了推薦準確性。

關鍵詞：基于位置；推薦算法；數據稀疏

DOIDOI：10.11907/rjdk.161555

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2016）009003902

基金項目基金項目：

作者簡介作者簡介：劉建東（1978-），男，湖南城步人，吉首大學張家界學院教學科研部講師，研究方向為計算機應用技術。

0引言

隨著在線社交網絡與智能手機技術的快速發展，用戶不僅僅滿足于在社交平臺用文字和圖片來分享經歷，還希望分享更豐富的信息，如在何時何地做了哪些事情等?，F在大部分智能手機都能提供基于地點的簽到服務，在線社交網絡如Foursquare、Gowalla等網站也支持基于地點的簽到服務。因此，用戶可利用智能手機在社交網絡分享去過的地點。這些分享的地點構成了用戶的運動軌跡。顯然，經常去戶外運動的用戶與喜歡文藝的用戶分享的地點是有差異的。因此，具有不同興趣的用戶分享的運動軌跡是不一樣的。換句話說，用戶興趣不同，分享的地點也就不同，地點與用戶興趣之間產生了關聯。因此，如何根據用戶的簽到地點來提供個性化服務是研究人員感興趣的課題。

目前，基于地點的推薦算法有兩個方向：①根據用戶之間的距離進行推薦。如Foursquare通過計算用戶與好友之間的距離推出探索功能，該功能可以為用戶推薦附近的好友，LBS軟件也提供了推薦附近餐館與商店的功能；②根據用戶的簽到地點為用戶進行分類。因為用戶的簽到地點相同，用戶興趣可能相似，典型的是一個被稱為LARS（Location Aware Recommender System）的推薦系統。該系統由明尼蘇達大學的研究人員提出，主要思想是將用戶按興趣相似度進行分類，為同類的用戶推薦物品或者地點。評價興趣相似度的標準有兩個：①用戶共同喜歡的物品越多，用戶的興趣越相似；②用戶簽到的地點越接近，用戶的興趣越相似。對于第①個標準而言，其實就是基于物品的協同過濾算法，該算法是經典的推薦算法，具體過程可參看文獻。本文主要討論第②個標準。因為簽到地點具有多級結構，所以LARS根據地點的范圍從大到小逐級劃分數據集，如簽到地點具有國家、省、市的樹狀結構。LARS首先根據國家把數據集劃分成不同的子集set1，set2，..seti..；接著按省份將數據集seti劃分為（seti1，seti2，seti3，...setil）等子集，然后依次按市劃分。一般來說，seti1，seti2，seti3，...setil數據子集內用戶興趣的相似度比seti內用戶興趣的相似度更高，因此，劃分子集提高了推薦準確性。但是按LARS劃分數據子集的用戶數據量可能不夠，進而影響推薦效果。子集內用戶數據量少的問題稱為數據稀疏問題，本文主要工作是針對可能存在的數據稀疏問題提出解決辦法，改善推薦效果。

1數據稀疏問題

用戶在使用在線社交網絡時喜歡分享自己的位置，從而會形成如下形式的數據記錄：（用戶，用戶位置，物品，評分）。本文用（ui，pi，wk，si）表示第i個用戶在位置pi評論第k個物品時所生成的數據。用戶興趣不同，分享的位置會有差異，所以LARS會根據用戶簽到位置對用戶數據集進行劃分。但是位置信息是一個樹狀結構，比如，國家、省、市、縣的結構。因此，數據集也會被劃分成一個樹狀結構，本文把該樹狀結構稱為樹狀數據集。樹狀數據集的節點包含了所有同一個位置的用戶行為數據。

如圖1所示，用戶u的評論數據信息是：（u，p22，wk，sj），那么推薦算法就會根據位置信息依次找到“p”，“p2”，“p22”這3個節點，在找到節點后把該數據信息依次劃分到“p”，“p2”，“p22”3個節點上。一般地，在劃分數據集過程中，p節點上的數據被劃分為i個子集（p1，p2，..pi），從概率上來說，pk節點上的數據量只是p節點上的1i。而隨著算法的進行，pk節點上的數據被劃分為j個子集（pk1，pk2，..pkj）。同樣的道理，子集pkl（1<=l<=j）節點上的數據量只是pk節點上的1j。更一般地，假設第n層節點的分支數是Nn，那么第n層上任一個節點的數據量只是總數據量上的1∏c=n-1c=1Nc。其中c表示層次。顯然，層次越深的節點所表示的位置越準確，但是所得到的數據量越少。

因為數據量降低的幅度很大，所以隨著子集的劃分，產生數據稀疏的可能性就越高。如果某個節點上的數據量太少，那么基于物品的協同過濾算法在該節點就無法有效進行，影響推薦的準確性，因此要對數據稀疏問題提出解決辦法。

2基于位置推薦的改進算法

2.1算法改進思路

基于位置的推薦算法根據位置信息對數據集進行劃分，劃分的層次越多，同類中用戶之間的位置越接近，用戶興趣的相似度越高，推薦效果越準確。但是另一方面，層次越多，劃分的子集包含的數據量越少，這樣又會降低推薦的準確性。因此，劃分子集時既要考慮用戶興趣的相似度，也要考慮子集的數量?；谖恢玫耐扑]算法問題在于僅計算深層次節點，即僅考慮了興趣相似度，卻忽略了數據量；相反，如果只考慮頂層節點，也會存在問題。因為頂層節點的用戶數據量大，用戶興趣的相似度低，這樣會忽略用戶興趣的相似度?？偠灾?，不能只考慮單獨的節點。因為不同層次的節點在用戶興趣的相似度和用戶數據量上有各自的優點和不足，所以改進算法的思路是綜合考慮不同層次的節點，利用基于物品的協同過濾算法為每個節點的數據子集生成推薦列表，然后分別為每個推薦列表設置不同的權重，最后按設置的權重將這些推薦列表進行線性相加，選擇排名最高的前N條記錄推薦。改進的基于位置的推薦算法流程如圖2所示，因為位置信息都是省-市-縣的三層樹狀結構，所以本算法也只考慮三層劃分。

2.2改進算法具體步驟

2.2.1輸入

輸入用戶uk的位置pk以及樹狀數據集Data_Tree，在使用基于物品的協同過濾算法時，輸入物品最相似的個數K，然后輸入前三層節點的數據集對應的推薦權重（λ1、λ2、λ3）。其中λi（1≤i≤3）代表數據集樹中第i層結點上的用戶行為產生的推薦列表權重，最后輸入推薦列表數目N。

2.2.2逐步計算推薦列表

（1）在Data_Tree中根據用戶位置pk從根節點開始搜索，相應找到路線上的節點N1、N2、N3其中Ni（1≤i≤3）表示第i層上的節點。

（2）得到節點Ni對應的用戶數據子集UserSet（Ni）。

（3）利用基于物品的協同過濾算法得到UserSet（Ni）的推薦列表List（i）。

wkl=W（k）∩W（l）W（k）W（l）（1）

Iuk=∑l∈N（u）∩S（l，K）wklrul（2）

公式（1）和公式（2）是基于物品的協同過濾算法計算公式，其中公式（1）是計算物品k與物品l之間的相似度， wkl是用戶數據子集中物品k與物品l的相似度，W（k）表示喜歡物品k的用戶數，W（l）表示喜歡物品l的用戶數。公式（2）是計算用戶u對物品k的興趣，其中N（u）表示用戶u喜歡物品的集合，S（l，K）表示和物品l最相似的K個物品的集合，wkl是用戶數據子集中物品k和物品l的相似度，rul是用戶u對物品l的興趣。

2.2.3線性相加計算結果

根據每個節點對應的推薦權重，計算List=∑i=3i=1λi*List（i）得到綜合推薦列表，然后進行相似度排序，選擇前N個物品進行推薦。

3實驗及結果分析

實驗采用MovieLens提供的測試數據集，MovieLens數據集來自用戶對電影的評價。該數據集包含了用戶位置信息。實驗將從數據集中提取100位用戶對800部電影的評價信息，選擇其中80%的數據作訓練集，另外20%作測試集。

實驗依次設置權重參數λ1、λ2、λ3的值為0.1、0.2、0.7，然后以基于位置的推薦算法和改進的推薦算法做實驗。實驗結果發現，改進算法的推薦結果準確性與召回率提高10%左右。其中準確性和召回率的計算公式如公式（3）和公式（4）所示。

Precision@N=∑uR（u，N）∩T（u）∑uR（u，N）（3）

Recall@N=∑uR（u，N）∩T（u）∑uT（u）（4）

4結語

本文針對基于位置的推薦算法在劃分數據子集時產生的數據稀疏問題，提出了對不同節點的推薦列表進行線性加權的解決辦法。實驗結果表明，改進的推薦算法提高了推薦結果的準確性。

參考文獻參考文獻：

[1]項亮.推薦系統實踐[M].北京：人民郵電出版社，2012.

[2]GOWALLA[EB/OL].http：//mashable.com/category/gowalla/.

[3]劉樹棟，孟祥武.一種基于移動用戶位置的網絡推薦方法[J].軟件導刊，2014，25（11）：5674.

[4]MAFENGWO[EB/OL].http：//www.mafengwo.cn/

[5]CHAKPABORTY B.Integrating awareness in user oriented route recommendation system[C].The International Joint Conference on Neural Networks，New Jersey：IEEE Press，2012.15.

[6]徐雅斌，孫曉晨.位置社交網絡的個性化位置推薦[J].北京郵電大學學報，2007，38（5）：118-122.

[7]FOURSQUARE[EB/OL].https：//foursquare.com/

[8]PLACES.GOOGLE[EB/OL].http：//places.google.com/rate

責任編輯（責任編輯：杜能鋼）