劉建東

摘要：基于位置的推薦算法在根據(jù)位置信息劃分?jǐn)?shù)據(jù)子集時會產(chǎn)生數(shù)據(jù)稀疏問題，對此提出了一種改進(jìn)的推薦算法。該算法充分考慮了不同位置所產(chǎn)生的推薦結(jié)果的差異性，分別為相應(yīng)的推薦結(jié)果設(shè)置不同權(quán)重，然后線性求和。改進(jìn)算法既解決了數(shù)據(jù)的稀疏問題，又考慮了用戶興趣的本地化。實驗結(jié)果表明，改進(jìn)的算法提高了推薦準(zhǔn)確性。

關(guān)鍵詞：基于位置；推薦算法；數(shù)據(jù)稀疏

DOIDOI：10.11907/rjdk.161555

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2016）009003902

基金項目基金項目：

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

0引言

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

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

1數(shù)據(jù)稀疏問題

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

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

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

2基于位置推薦的改進(jìn)算法

2.1算法改進(jìn)思路

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

2.2改進(jìn)算法具體步驟

2.2.1輸入

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

2.2.2逐步計算推薦列表

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

（2）得到節(jié)點Ni對應(yīng)的用戶數(shù)據(jù)子集UserSet（Ni）。

（3）利用基于物品的協(xié)同過濾算法得到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）是基于物品的協(xié)同過濾算法計算公式，其中公式（1）是計算物品k與物品l之間的相似度， wkl是用戶數(shù)據(jù)子集中物品k與物品l的相似度，W（k）表示喜歡物品k的用戶數(shù)，W（l）表示喜歡物品l的用戶數(shù)。公式（2）是計算用戶u對物品k的興趣，其中N（u）表示用戶u喜歡物品的集合，S（l，K）表示和物品l最相似的K個物品的集合，wkl是用戶數(shù)據(jù)子集中物品k和物品l的相似度，rul是用戶u對物品l的興趣。

2.2.3線性相加計算結(jié)果

根據(jù)每個節(jié)點對應(yīng)的推薦權(quán)重，計算List=∑i=3i=1λi*List（i）得到綜合推薦列表，然后進(jìn)行相似度排序，選擇前N個物品進(jìn)行推薦。

3實驗及結(jié)果分析

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

實驗依次設(shè)置權(quán)重參數(shù)λ1、λ2、λ3的值為0.1、0.2、0.7，然后以基于位置的推薦算法和改進(jìn)的推薦算法做實驗。實驗結(jié)果發(fā)現(xiàn)，改進(jìn)算法的推薦結(jié)果準(zhǔn)確性與召回率提高10%左右。其中準(zhǔn)確性和召回率的計算公式如公式（3）和公式（4）所示。

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

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

4結(jié)語

本文針對基于位置的推薦算法在劃分?jǐn)?shù)據(jù)子集時產(chǎn)生的數(shù)據(jù)稀疏問題，提出了對不同節(jié)點的推薦列表進(jìn)行線性加權(quán)的解決辦法。實驗結(jié)果表明，改進(jìn)的推薦算法提高了推薦結(jié)果的準(zhǔn)確性。

參考文獻(xiàn)參考文獻(xiàn)：

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

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

[3]劉樹棟，孟祥武.一種基于移動用戶位置的網(wǎng)絡(luò)推薦方法[J].軟件導(dǎo)刊，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]徐雅斌，孫曉晨.位置社交網(wǎng)絡(luò)的個性化位置推薦[J].北京郵電大學(xué)學(xué)報，2007，38（5）：118-122.

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

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

責(zé)任編輯（責(zé)任編輯：杜能鋼）