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

劉建東

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

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

DOIDOI：10.11907/rjdk.161555

中圖分類號(hào)：TP312

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

基金項(xiàng)目基金項(xiàng)目：

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

0引言

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

目前，基于地點(diǎn)的推薦算法有兩個(gè)方向：①根據(jù)用戶之間的距離進(jìn)行推薦。如Foursquare通過計(jì)算用戶與好友之間的距離推出探索功能，該功能可以為用戶推薦附近的好友，LBS軟件也提供了推薦附近餐館與商店的功能；②根據(jù)用戶的簽到地點(diǎn)為用戶進(jìn)行分類。因?yàn)橛脩舻暮灥降攸c(diǎn)相同，用戶興趣可能相似，典型的是一個(gè)被稱為LARS（Location Aware Recommender System）的推薦系統(tǒng)。該系統(tǒng)由明尼蘇達(dá)大學(xué)的研究人員提出，主要思想是將用戶按興趣相似度進(jìn)行分類，為同類的用戶推薦物品或者地點(diǎn)。評(píng)價(jià)興趣相似度的標(biāo)準(zhǔn)有兩個(gè)：①用戶共同喜歡的物品越多，用戶的興趣越相似；②用戶簽到的地點(diǎn)越接近，用戶的興趣越相似。對(duì)于第①個(gè)標(biāo)準(zhǔn)而言，其實(shí)就是基于物品的協(xié)同過濾算法，該算法是經(jīng)典的推薦算法，具體過程可參看文獻(xiàn)。本文主要討論第②個(gè)標(biāo)準(zhǔn)。因?yàn)楹灥降攸c(diǎn)具有多級(jí)結(jié)構(gòu)，所以LARS根據(jù)地點(diǎn)的范圍從大到小逐級(jí)劃分?jǐn)?shù)據(jù)集，如簽到地點(diǎn)具有國家、省、市的樹狀結(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ù)稀疏問題，本文主要工作是針對(duì)可能存在的數(shù)據(jù)稀疏問題提出解決辦法，改善推薦效果。

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

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

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

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

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

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

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

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

2.2.1輸入

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

2.2.2逐步計(jì)算推薦列表

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

（2）得到節(jié)點(diǎn)Ni對(duì)應(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é)同過濾算法計(jì)算公式，其中公式（1）是計(jì)算物品k與物品l之間的相似度， wkl是用戶數(shù)據(jù)子集中物品k與物品l的相似度，W（k）表示喜歡物品k的用戶數(shù)，W（l）表示喜歡物品l的用戶數(shù)。公式（2）是計(jì)算用戶u對(duì)物品k的興趣，其中N（u）表示用戶u喜歡物品的集合，S（l，K）表示和物品l最相似的K個(gè)物品的集合，wkl是用戶數(shù)據(jù)子集中物品k和物品l的相似度，rul是用戶u對(duì)物品l的興趣。

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

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

3實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

[3]劉樹棟，孟祥武.一種基于移動(dòng)用戶位置的網(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ò)的個(gè)性化位置推薦[J].北京郵電大學(xué)學(xué)報(bào)，2007，38（5）：118-122.

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

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

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