一種融合地理位置信息的協(xié)同過濾推薦算法

魯 驍 ，王書鑫 ，王 斌 ，魯 凱

(1. 國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心，北京 100029；2. 中國科學(xué)院大學(xué)，北京 100049；3. 中國科學(xué)院 信息工程研究所，北京 100093；4. University of California，Santa Cruz，USA)

一種融合地理位置信息的協(xié)同過濾推薦算法

魯 驍1，王書鑫2，王 斌3，魯 凱4

(1. 國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心，北京 100029；2. 中國科學(xué)院大學(xué)，北京 100049；3. 中國科學(xué)院 信息工程研究所，北京 100093；4. University of California，Santa Cruz，USA)

目前，基于用戶消費(fèi)數(shù)據(jù)構(gòu)建的推薦系統(tǒng)在電子商務(wù)領(lǐng)域發(fā)揮著越來越大的作用，而在這些數(shù)據(jù)中，商家本身具有的地理位置信息忠實(shí)地記錄了用戶的消費(fèi)痕跡，能夠有效反映出用戶在地理位置維度上的個(gè)人偏好信息，從而對推薦系統(tǒng)具有非常重要的意義?，F(xiàn)有工作一般只利用了用戶對地點(diǎn)的評價(jià)以及地點(diǎn)之間的距離，無法反映出不同地點(diǎn)之間的關(guān)聯(lián)關(guān)系，以及用戶在不同地點(diǎn)中的偏好權(quán)重問題。該文從地理區(qū)域劃分的角度出發(fā)，研究了用戶在區(qū)域范圍內(nèi)的消費(fèi)興趣偏好，以及不同粒度級別的區(qū)域劃分方法對推薦模型的影響，探索了在推薦過程中有效融合地域信息的方法，考慮了包括地區(qū)的全局性影響、用戶對地區(qū)的偏好等，結(jié)合這些因素提出了融合地理位置信息的推薦模型LGE、LGN及LRSVD。通過在Yelp數(shù)據(jù)集上的實(shí)驗(yàn)表明，這些模型相比于傳統(tǒng)的推薦算法能夠有效提高預(yù)測效果。

推薦系統(tǒng)；協(xié)同過濾；地理位置信息；鄰居模型；隱參數(shù)模型

1 引言

隨著互聯(lián)網(wǎng)和電子商務(wù)的發(fā)展，越來越多的商家開始在網(wǎng)上推廣商品及服務(wù)，并涌現(xiàn)出了各種提供在線展示、預(yù)約、購買、團(tuán)購等服務(wù)的網(wǎng)站，國內(nèi)規(guī)模較大的如大眾點(diǎn)評和口碑網(wǎng)，國外較有名的如Yelp等，這些網(wǎng)站在提供商家展示信息的同時(shí)，也為用戶提供了信息反饋的渠道，從而產(chǎn)生了大量的用戶對商家的消費(fèi)數(shù)據(jù)，包括消費(fèi)記錄、評價(jià)打分、評論內(nèi)容等信息，根據(jù)Yelp發(fā)布的2013年第二季度財(cái)報(bào)顯示，截至2013年7月30日，Yelp網(wǎng)站中累積用戶點(diǎn)評數(shù)量超過4 250萬條，月獨(dú)立用戶達(dá)到1.08億。如何有效利用這些數(shù)據(jù)來更好地為用戶推薦商家，對工業(yè)界和學(xué)術(shù)界來說都是一個(gè)挑戰(zhàn)。

在學(xué)術(shù)界，目前大量的研究集中在根據(jù)用戶反饋進(jìn)行推薦。具體到生活服務(wù)的推薦，情況又有所不同，由于商家都是線下實(shí)體店，真正的消費(fèi)是在實(shí)體店完成的，其中有一個(gè)很重要的因素就是地理位置，在現(xiàn)實(shí)生活中，不同地區(qū)的商家，服務(wù)質(zhì)量與其所在的位置有著很大的關(guān)系，而用戶本身也有著地理位置屬性，其消費(fèi)活動(dòng)一般會(huì)局限在部分地區(qū)范圍，所以在根據(jù)線上用戶的評論數(shù)據(jù)進(jìn)行個(gè)性化推薦的同時(shí)，必須對地理位置進(jìn)行著重考慮。以此為出發(fā)點(diǎn)，本文提出融合了地理位置信息的推薦模型，并在Recsys 2013公布的Yelp數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了該方法的有效性。

本文后續(xù)內(nèi)容安排如下：第二節(jié)主要介紹常用的推薦算法；第三節(jié)闡述融合地理位置信息的推薦模型，主要包括考慮地區(qū)偏置的全局影響模型LGE，以地理位置信息來改進(jìn)相似度計(jì)算的全局鄰居模型LGN，以及融合了前述工作的隱參數(shù)模型LRSVD；第四節(jié)展示在Yelp數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果，并對結(jié)果進(jìn)行分析；第五節(jié)是結(jié)論及未來工作。

2 相關(guān)工作

自從Tapestry系統(tǒng)[1]最早提出協(xié)同過濾的概念之后，協(xié)同過濾方法越來越受到研究者和商業(yè)系統(tǒng)的重視，較有名的推薦系統(tǒng)應(yīng)用包括GroupLens、MovieLens、Netflix等，從2007年開始，ACM Recsys會(huì)議每年都會(huì)組織一次關(guān)于推薦算法的討論，以促進(jìn)推薦算法的發(fā)展。

經(jīng)典的協(xié)同過濾推薦算法可以分為基于記憶的方法和基于模型的方法?；谟洃浀姆椒╗2-4]，是利用用戶對物品的打分來計(jì)算用戶或物品之間的相似度，并根據(jù)相似的用戶或物品來進(jìn)行推薦，其中經(jīng)典的方法如user-based KNN[2]， item-based KNN[3-4]等，這類方法實(shí)現(xiàn)起來比較簡單，但也有許多限制，受數(shù)據(jù)稀疏性影響較大[5]。為了克服這個(gè)問題，研究者提出了基于模型的方法，通過機(jī)器學(xué)習(xí)來訓(xùn)練模型中的參數(shù)，發(fā)掘數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，常見的包括鄰居模型[6-7]、貝葉斯網(wǎng)絡(luò)[8-9]、聚類模型[10-11]、因子分解模型[12]等，基于用戶和物品偏好的RSVD模型[13]得到了普遍應(yīng)用。與此同時(shí)，融合上下文的推薦方法[14-18]也越來越受到重視，推薦系統(tǒng)中的上下文信息包括了時(shí)間因素、人口特征、社會(huì)特征、環(huán)境因素、地理位置、物品類別等，利用這些屬性能夠挖掘出更多的有用信息，改善數(shù)據(jù)稀疏性的問題。Li[14]將上下文信息作為用戶特征，Oku[15]通過SVM模型來做上下文敏感的預(yù)測。

另外，在特定的應(yīng)用場景中，尤其是在線下生活服務(wù)推薦中[19-25]，地理位置作為一種重要的上下文信息，受到了很多研究者的重視。Zheng[19]提出了LBSN (Location-Based Social Network)的概念，用于表示人們基于真實(shí)地理位置而發(fā)展出來的一種新型社交關(guān)系結(jié)構(gòu)。目前推薦系統(tǒng)對地理位置信息的利用，主要體現(xiàn)在兩個(gè)方面。

一種是基于共同地點(diǎn)，以用戶的消費(fèi)地點(diǎn)為對象，通過統(tǒng)計(jì)不同用戶之間的共同消費(fèi)地點(diǎn)來計(jì)算用戶之間的相似度，如Mao[20]設(shè)計(jì)了基于用戶共同活動(dòng)地點(diǎn)的好友相似度評估方法，并提出了基于好友的協(xié)同過濾模型，以用戶消費(fèi)的地點(diǎn)為對象，來衡量用戶之間的相似度，在此工作基礎(chǔ)上，進(jìn)一步提出融合了用戶喜好、社交影響力以及地域影響力等因素的模型[21]，實(shí)現(xiàn)了基于概率的用戶興趣地點(diǎn)推薦。Sabar[22]根據(jù)用戶的實(shí)時(shí)上下文信息，包括用戶過去常去的地點(diǎn)以及當(dāng)前的活動(dòng)地點(diǎn)為用戶提供更貼近生活的推薦服務(wù)。這種方法是以用戶-地點(diǎn)為數(shù)據(jù)對進(jìn)行推薦，其缺點(diǎn)在于沒有考慮地點(diǎn)之間的關(guān)聯(lián)關(guān)系。

另一種是基于距離，根據(jù)地理位置來計(jì)算用戶消費(fèi)地點(diǎn)之間的距離，并將其加入到模型因子中來調(diào)整推薦模型，如Park[23]基于用戶使用的移動(dòng)設(shè)備中的信息，包括上下文信息、時(shí)間、天氣、GPS數(shù)據(jù)等，對待推薦項(xiàng)的地理位置按照相對距離的遠(yuǎn)近劃分為Near、Mid、Far三類，利用貝葉斯網(wǎng)絡(luò)構(gòu)建了用戶的個(gè)人偏好模型，從而為用戶推薦感興趣的餐廳。Cao[24]通過分析用戶的GPS數(shù)據(jù)，構(gòu)建用戶-地點(diǎn)的雙層網(wǎng)絡(luò)，并利用隨機(jī)游走算法來為地點(diǎn)進(jìn)行排序，從而抽取出有顯著意義的地點(diǎn)。Kuo[25]將商戶的地理位置作為排序因子之一，通過讓用戶選擇相對距離的重要性，并結(jié)合用戶的長期興趣和短期興趣，構(gòu)建了用戶的周邊服務(wù)推薦系統(tǒng)。

以距離作為因素來構(gòu)建推薦模型，能夠有效地將用戶在不同地點(diǎn)的消費(fèi)偏好關(guān)聯(lián)起來，但其計(jì)算方法主要根據(jù)GPS數(shù)據(jù)中的絕對距離，而忽略了地理位置天然具有區(qū)域概念的事實(shí)。而且這兩種方法都只基于用戶在地點(diǎn)中的消費(fèi)打分，而由于單點(diǎn)的消費(fèi)記錄無法反映出用戶對地點(diǎn)的消費(fèi)次數(shù)，從而忽略了用戶在不同地點(diǎn)中由于消費(fèi)次數(shù)的不同應(yīng)當(dāng)具有不同的偏好權(quán)重。只有以區(qū)域?yàn)閱挝贿M(jìn)行消費(fèi)次數(shù)的統(tǒng)計(jì)，才能有效利用權(quán)重這個(gè)因素。

根據(jù)上述不足，本文主要從地理位置的區(qū)域性出發(fā)，首先考慮區(qū)域性偏好對用戶潛在喜好的影響，在此基礎(chǔ)上，提出了以地理區(qū)域?yàn)閱挝坏娜粥従幽Ｐ?，在這個(gè)過程中提出了帶權(quán)重的基于地理位置的用戶相似度計(jì)算方法，并解決了整合不同層次區(qū)域劃分方法的問題，最后，本文還將地域因素加入到隱參數(shù)模型中，并融合了前兩步的工作以進(jìn)一步提供算法的推薦效果。

3 本文工作

本文研究發(fā)現(xiàn)，在消費(fèi)者對商家反饋信息中，有著顯著的地域效應(yīng)，主要體現(xiàn)在以下三個(gè)方面。

1) 不同的地域之間消費(fèi)情況有明顯區(qū)別，會(huì)對其范圍內(nèi)的商家產(chǎn)生全局性的影響，甚至同一品牌的商家在不同地區(qū)的分店可能會(huì)有不同的平均得分，這些地區(qū)之間的區(qū)別具有現(xiàn)實(shí)原因，例如經(jīng)濟(jì)情況、交通情況等；

2) 用戶的消費(fèi)行為一般會(huì)呈現(xiàn)出地域較為集中的趨勢，說明用戶在選擇商家進(jìn)行消費(fèi)時(shí)，地域也是一個(gè)潛在的偏好因素；

3) 對于地理位置信息本身，按照其范圍大小有粒度上的區(qū)別，如省、市、街區(qū)等，不同粒度的地理信息將對推薦產(chǎn)生不同的影響，應(yīng)當(dāng)分層考慮。

3.1 地理位置的全局性影響

數(shù)據(jù)集中商家的數(shù)量、商家的平均消費(fèi)數(shù)量以及用戶的評分反饋都能從特定方面反映出當(dāng)前地區(qū)的消費(fèi)情況，而不同地域之間的消費(fèi)情況具有很大的差異，如圖1展示了Yelp數(shù)據(jù)集中各城市的消費(fèi)數(shù)量以及平均得分情況。

圖1 Yelp數(shù)據(jù)集中各城市的消費(fèi)數(shù)量及平均得分差異

圖中橫坐標(biāo)表示消費(fèi)數(shù)量由高到低的各個(gè)城市，左側(cè)縱坐標(biāo)表示在每個(gè)城市中的消費(fèi)數(shù)量，右側(cè)縱坐標(biāo)表示在各城市中所有消費(fèi)評價(jià)的平均分，柱狀圖由高到低展示了各城市之間消費(fèi)數(shù)量的差異，可以看出大部分消費(fèi)集中在少量幾個(gè)城市中。折線圖顯示了各城市的平均得分，可以看出根據(jù)地區(qū)的不同，其總體平均分是有明顯區(qū)別的。

本文在后續(xù)工作中用b這一項(xiàng)來代表全局范圍內(nèi)的地區(qū)偏置，其中表示商家i所在的地區(qū)，對于每個(gè)商家i而言，其所在地區(qū)是固定的，即商家與地區(qū)是1∶1的映射關(guān)系，所以對于每一個(gè)商家，都有唯一的地區(qū)偏置項(xiàng)。

3.2 用戶對地理位置的偏好

本文從用戶的評價(jià)信息與商家信息中統(tǒng)計(jì)了用戶消費(fèi)的覆蓋范圍，根據(jù)商家所在的城市，統(tǒng)計(jì)出用戶消費(fèi)的城市分布，可以看出每個(gè)用戶都有較為常去的城市，說明用戶對城市本身具有一種偏好。接下來，本文對商家的詳細(xì)地址進(jìn)行了分析，抽取出其所在的街區(qū)郵編號碼，由于城市內(nèi)部都以街區(qū)進(jìn)行區(qū)域劃分，所以能夠用郵編號碼來表示商家的街區(qū)分布，從而能夠統(tǒng)計(jì)出用戶消費(fèi)的街區(qū)分布。 圖2、圖3所示是分別從城市和街區(qū)兩個(gè)粒度上統(tǒng)計(jì)的Yelp用戶消費(fèi)記錄分布。

圖2 用戶消費(fèi)城市分布統(tǒng)計(jì)圖

圖3 用戶消費(fèi)街區(qū)分布統(tǒng)計(jì)圖

圖2和圖3的橫坐標(biāo)表示各個(gè)用戶曾經(jīng)去消費(fèi)過的地區(qū)數(shù)量，縱坐標(biāo)表示各個(gè)用戶的消費(fèi)數(shù)量，圖中的箱線圖直觀地展現(xiàn)了用戶消費(fèi)地區(qū)數(shù)量的分布情況，從圖2中可以看出，用戶的消費(fèi)地點(diǎn)都比較集中，大多數(shù)用戶的消費(fèi)都集中分布在幾個(gè)城市中。將位置信息的精度放縮到街區(qū)范圍內(nèi)，從圖3中也可以看到類似的情況，用戶消費(fèi)的街區(qū)分布也較為集中，大多數(shù)用戶的消費(fèi)覆蓋街區(qū)不超過十個(gè)，從而呈現(xiàn)出用戶對地點(diǎn)的一種偏好，這個(gè)現(xiàn)象比較符合真實(shí)情況，日常生活中，用戶的消費(fèi)地點(diǎn)和其所在的地理位置息息相關(guān)，比如用戶傾向于在家庭居住地或工作地點(diǎn)附近進(jìn)行消費(fèi)。

對于用戶，每個(gè)用戶在不同的地區(qū)會(huì)有不同的消費(fèi)記錄，從而形成了他們在這些地區(qū)中的個(gè)性化偏好，本文從這點(diǎn)出發(fā)，考慮用戶消費(fèi)習(xí)慣在地區(qū)上的體現(xiàn)，提出用戶對每個(gè)地域都有偏置，通過與全局偏好組合，可以將用戶的偏置用式(1)進(jìn)行表示。

(1)

其中，bu表示用戶u的基本偏置，表示商家i所在的地區(qū)，bu()表示用戶對地區(qū)的偏置，具體計(jì)算方法如式(2)所示。

(2)

其中，αu,表示用戶對地區(qū)的偏好，ωu,用來調(diào)節(jié)其權(quán)重大小。

由于用戶在不同城市中的消費(fèi)記錄并不均衡，用戶的大部分消費(fèi)都分布在幾個(gè)城市中，較為集中，所以本文在處理用戶的地理位置偏好時(shí)，將根據(jù)其在每個(gè)地區(qū)的消費(fèi)頻次，進(jìn)行權(quán)重調(diào)節(jié)，消費(fèi)次數(shù)較少的城市，用戶對該城市偏好的權(quán)重相對較小，權(quán)重的計(jì)算如式(3)所示。

(3)

其中，Cu,表示用戶在地區(qū)的消費(fèi)次數(shù)，Su表示用戶的全部消費(fèi)次數(shù)。

根據(jù)以上推導(dǎo)，從而得到用戶的地理位置偏好表示如式(4)所示。

(4)

該公式意味著，用戶消費(fèi)較少的城市，其個(gè)性化偏好較弱，而在消費(fèi)較多的城市，其權(quán)重較大，具有更明顯的個(gè)性化偏好。一個(gè)極端的例子就是，用戶在某個(gè)城市沒有打分記錄，則根據(jù)上述公式可計(jì)算出用戶對該城市的偏好為0，從而只有全局偏好，而沒有地理位置偏好。

3.3 基于地理位置信息的全局影響模型

在前面兩小節(jié)的工作基礎(chǔ)上，考慮到商家的地區(qū)偏置項(xiàng)以及用戶對地理位置的偏好，本文以全局影響模型[24]為原型，提出了基于地理位置的全局影響模型(Location-basedGlobalEffects)，以下簡稱為LGE，模型的具體計(jì)算方法如式(5)所示。

(5)

3.4 基于地理位置信息的全局鄰居模型

本文考慮根據(jù)用戶的消費(fèi)地區(qū)信息來計(jì)算用戶之間的相似度，并將前文中的地區(qū)全局影響、用戶對地理位置的偏置融合到全局鄰居模型[6-7,26]中，提出了基于地理位置的全局鄰居模型(Location-based Global Neighborhood)，簡稱為LGN模型，以解決兩個(gè)問題：第一是對用戶-地理位置建模，在地理區(qū)域的維度空間上來表示用戶，而且需要考慮到用戶在各地區(qū)上的偏好權(quán)重不同；其次，地理位置具有明顯的層級特征，需要充分考慮不同級別的地區(qū)表示之間的融合問題。

3.4.1 帶權(quán)重的地理位置特征表示方法

以地理位置為特征來表示用戶，則用戶地理位置特征向量可以表示為式(6)。

(6)

以此便可以將用戶表示為地理區(qū)域上的向量。

隨后，本文考慮了用戶對區(qū)域的消費(fèi)偏好，認(rèn)為用戶對其消費(fèi)區(qū)域的偏好將通過其消費(fèi)記錄反映出來，所以在表示用戶的地理位置特征向量時(shí)，為每一維特征加上不同的權(quán)重wi，以表示其對不同區(qū)域的偏好，如式(7)所示。

(7)

其中，權(quán)重wu,i的計(jì)算方法參考文檔的tf-idf計(jì)算方法，此處假設(shè)以地理區(qū)域?yàn)樵~項(xiàng)，每個(gè)用戶為文檔，則可以將用戶-地理區(qū)域模型轉(zhuǎn)換為文檔的詞袋模型來進(jìn)行表示，詞頻tf代表用戶在區(qū)域i的消費(fèi)次數(shù)，文檔頻率df代表所有在區(qū)域i消費(fèi)過的用戶數(shù)量，從而可以根據(jù)tf-idf的公式得到用戶的地理區(qū)域權(quán)重計(jì)算公式，如式(8)所示。

(8)

其中，tfu,i表示用戶u在區(qū)域i的消費(fèi)次數(shù)，dfi表示所有在區(qū)域i消費(fèi)過的用戶數(shù)量，N表示用戶總數(shù)。

3.4.2 考慮地理位置層級關(guān)系的相似度計(jì)算方法

在將用戶表示為地理區(qū)域的向量空間后，可以對用戶進(jìn)行相似度計(jì)算，從而完成相似用戶的選擇。本文選用余弦相似度來進(jìn)行計(jì)算，如式(9)所示。

(9)

在這個(gè)過程中，本文發(fā)現(xiàn)地理區(qū)域的選擇面臨很強(qiáng)的粒度選擇問題。具體而言，地理位置具有明確的級別劃分的概念，不同級別能夠代表不同范圍的地區(qū)，如中國的地區(qū)行政級別劃分方法為：省/市/區(qū)/縣，而美國地區(qū)行政級別劃分方法為：州/市/區(qū)，不同粒度的劃分方法將對區(qū)域的用戶消費(fèi)統(tǒng)計(jì)產(chǎn)生不同的影響。

從這點(diǎn)出發(fā)，本文在研究地理位置對推薦算法的影響時(shí)，也對其粒度級別進(jìn)行了考慮，將不同的地區(qū)粒度融合在一起進(jìn)行計(jì)算。參考上一小節(jié)，在每一個(gè)區(qū)域級別上建立獨(dú)立的用戶-區(qū)域向量模型，向量空間的維度為該層級別上地理區(qū)域的劃分集合，例如在省級粒度上，就以省作為維度，這樣對于有K層級別的地理位置而言，就相應(yīng)建立了K個(gè)用戶-地理區(qū)域的向量空間，每個(gè)向量空間進(jìn)行獨(dú)立的向量相似度計(jì)算，之后通過線性插值的方法進(jìn)行不同級別的相似度計(jì)算結(jié)果融合。

本文采用雙層級別劃分的地理位置表示方法，考慮城市和街區(qū)兩個(gè)粒度級別，融合方法如式(10)所示。

(10)

其中，每一層級別Li上的相似度表示為simLi，η作為調(diào)節(jié)系數(shù)來管理各個(gè)層次之間的權(quán)重比例。在計(jì)算出相似度之后，對于用戶u，將和其關(guān)聯(lián)的用戶的相似度按照降序進(jìn)行排列，取出前K個(gè)用戶作為鄰居用戶集合NK(u)。

3.4.3 LGN模型

基于上述工作，本文提出基于地理位置的全局鄰居模型，如式(11)所示。

(11)

其中，PK(i)=P(i)∩NK(u)表示從訓(xùn)練集中對商家i評分的用戶集合中，選出與用戶u相似的Top-K鄰居用戶集合，AK(i)=A(i)∩NK(u)表示從全部數(shù)據(jù)集中對商家i評分的用戶集合中，選出與用戶u相似的Top-K鄰居用戶集合，bv,i為用戶v對商家i的基準(zhǔn)預(yù)測評分，這里采用本文提出的LGE模型來進(jìn)行計(jì)算[參見式(5)]，ωuv為偏移量，表示v對u的可預(yù)測程度，Cuo為模型參數(shù)。

3.5 基于地理位置信息的隱參數(shù)模型

在前面兩節(jié)中，本文分別提出了對地理位置敏感的LGE和LGN模型，在此工作基礎(chǔ)上，本文改進(jìn)了隱參數(shù)模型RSVD[13]， 加入了地理偏置、用戶對地理位置的偏置以及改進(jìn)的最近鄰計(jì)算方法，并融合了隱參數(shù)模型，提出了LRSVD模型，從而緩解數(shù)據(jù)稀疏帶來的影響。

(12)

4 實(shí)驗(yàn)和結(jié)論

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文使用Recsys 2013提供的Yelp消費(fèi)評論數(shù)據(jù)，該數(shù)據(jù)集收集了Yelp網(wǎng)站中位于美國亞利桑那州各個(gè)城市的商家信息以及消費(fèi)者打分記錄。數(shù)據(jù)集主要包括兩個(gè)部分：訓(xùn)練集、測試集。數(shù)據(jù)詳細(xì)信息如表1所示。

表1 Yelp商家評分?jǐn)?shù)據(jù)集

其中，用戶對商家的評分值范圍為1～5。通過表1可以看出，整個(gè)數(shù)據(jù)集包含了超過20萬條用戶評分?jǐn)?shù)據(jù)，訓(xùn)練集中只有一條評分?jǐn)?shù)據(jù)的用戶數(shù)量為22 829，接近總用戶數(shù)的一半，通過計(jì)算得到訓(xùn)練集的稀疏度約為99.96%，而測試集中新出現(xiàn)的用戶數(shù)為5 315，占測試集用戶數(shù)的44.5%左右，新出現(xiàn)的商家數(shù)為1 205，約占測試集商家數(shù)的21.6%。

本文使用的地理位置信息包括城市名稱、郵編號兩種，郵編號用來代表街區(qū)的信息，具有唯一性。另外，由于數(shù)據(jù)集中商家的地理位置信息存在一些噪音，例如單詞拼寫錯(cuò)誤、城市中帶有其他位置信息，導(dǎo)致數(shù)據(jù)格式不一致，所以在從地址中抽取出城市信息時(shí)，采用了編輯距離算法[27]來修正錯(cuò)誤的城市名稱拼寫。

另外，為了便于對模型參數(shù)進(jìn)行擬合訓(xùn)練，本文依據(jù)訓(xùn)練集和測試集中用戶數(shù)與商家數(shù)的比例，對原始訓(xùn)練集數(shù)據(jù)進(jìn)行了切分，得到五份新的訓(xùn)練集和驗(yàn)證集，表2所示是各個(gè)子數(shù)據(jù)集中用戶和商家的數(shù)據(jù)統(tǒng)計(jì)。

表2 新的訓(xùn)練集與驗(yàn)證集

在切分?jǐn)?shù)據(jù)集的過程中，本文不僅保持訓(xùn)練集與驗(yàn)證集中用戶-項(xiàng)的比例，而且盡量維持驗(yàn)證集中冷啟動(dòng)用戶的比例，以便與原始數(shù)據(jù)集保持一致。

4.2 評價(jià)指標(biāo)

本文采用RMSE(均方誤差)作為實(shí)驗(yàn)的評價(jià)指標(biāo)，計(jì)算公式如式(13)所示。

(13)

RMSE放大了預(yù)測值與真實(shí)值之間的絕對誤差，從而加大了對預(yù)測不準(zhǔn)的評分?jǐn)?shù)據(jù)的懲罰，因而對系統(tǒng)的評測更為苛刻一些。

4.3 模型參數(shù)訓(xùn)練

本文通過平方損失函數(shù)來評估算法的誤差，計(jì)算方法如式(14)所示。

(14)

對以上損失函數(shù)，可以采用最小二乘法或梯度下降來求解參數(shù)，以LRSVD為例，優(yōu)化目標(biāo)函數(shù)的計(jì)算公式為式(15)。

(15)

其中，公式中第二項(xiàng)用來防止過擬合。

本文通過NelderMead方法[28]來訓(xùn)練步長參數(shù)和正則化參數(shù)λ，實(shí)驗(yàn)過程中設(shè)定NelderMead的迭代次數(shù)為50次，可以得到各個(gè)模型的最優(yōu)RMSE值。

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

本文對前面章節(jié)中提出的LGE、LGN和LRSVD三個(gè)模型進(jìn)行了實(shí)驗(yàn)，為了便于比較模型之間的效果差異，本文主要選擇了以下幾個(gè)模型做對比：

?GE：全局影響模型(GlobalEffects)

?GN：全局鄰居模型(GlobalNeighborhood)

?RSVD：正則化奇異值分解模型(RegularizedSingularValueDecomposition)

?FCF[3]：基于好友地理位置的協(xié)同過濾(Friend-basedCollaborativeFiltering)

其中，前三個(gè)模型是基本對照組，不具有地理位置因素，F(xiàn)CF是在經(jīng)典KNN推薦模型的基礎(chǔ)上加入地理位置的改進(jìn)模型。

首先，本文比較了GN與LGN在取不同K值情況下的表現(xiàn)，GE和LGE與K值無關(guān)，作為基本對照，各模型的表現(xiàn)如圖4所示。

圖4 改進(jìn)的KNN模型隨著K取值變化的效果比較

圖4中橫坐標(biāo)表示選取的相似鄰居好友的個(gè)數(shù)，縱坐標(biāo)表示各個(gè)模型的RMSE值，從圖4可以看出，LGE模型比GE模型有較大的效果提升，說明將地區(qū)偏置和用戶偏置融入到模型中確實(shí)能夠提高模型的效果。隨著K取值的不斷增加，三個(gè)KNN模型的效果都越來越好，其中FCF和LGN表現(xiàn)都優(yōu)于GN，從而證明在模型中融入地理位置因素后能夠有效降低模型的RMSE值，而將地理位置及權(quán)重融入到最近鄰計(jì)算中的LGN模型，相對于GN和FCF能夠更加顯著地降低預(yù)測誤差。另外，在本文實(shí)驗(yàn)過程中發(fā)現(xiàn)，由于Yelp數(shù)據(jù)集比較稀疏，當(dāng)K值超過50之后，效果提升不再明顯。

隨后，本文取K=50，對LRSVD進(jìn)行了效果分析，圖5所示是LRSVD與RSVD兩個(gè)模型的實(shí)驗(yàn)結(jié)果。

圖5 隱參數(shù)模型隨著隱變量數(shù)量變化的效果比較

圖5中橫坐標(biāo)表示隱參數(shù)的數(shù)量，縱坐標(biāo)表示各個(gè)模型的RMSE值，其中GE模型僅提供基礎(chǔ)預(yù)測誤差作為參考，可以看出由于數(shù)據(jù)稀疏導(dǎo)致原始RSVD的效果并不理想，甚至比基本的全局影響模型還要差，而LRSVD由于綜合了地區(qū)偏差、用戶的地區(qū)偏差，以及基于地域的最近鄰等因素，大幅度降低了預(yù)測誤差，達(dá)到了很好的效果。而且隨著隱變量數(shù)量(factorsize)的增加，兩個(gè)模型的RMSE值都逐漸減小，而相比于傳統(tǒng)的RSVD模型，考慮了地理位置因素的LRSVD的效果有更明顯的提升。最后，本文取K=50，f=100，并與GE、GN、RSVD、FCF等模型進(jìn)行效果對比，并以FCF為參考做了威斯康辛顯著性檢驗(yàn)，結(jié)果如表3所示。

表3 與其他模型的效果比較

從表3可以看出，本文提出的LGE、LGN和LRSVD相對于原始的GE、GN和RSVD模型都有明顯的效果提升，而且與經(jīng)典的基于好友地理位置的FCF模型相比而言，LGN和LRSVD的效果也有顯著的提升，由此可以充分說明本文提出的融合地理位置信息的方法能夠有效利用地理位置因素來提高算法的推薦效果。

另外，本文還與Recsys Challenge 2013公布的其他隊(duì)伍的結(jié)果進(jìn)行了對比，如表4所示。

表4 與Recsys Challenge 2013其他隊(duì)伍的效果比較

Recsys Challenge 2013在比賽中給出的benchmark是根據(jù)計(jì)算所有用戶的平均打分值得到的，值為1.27，很容易被超越，最后各個(gè)比賽隊(duì)伍公開的最好效果達(dá)到1.21，本文的單個(gè)模型最好效果能夠達(dá)到1.215 17，與第二名的結(jié)果接近，另外，本文將LRSVD與LGE、LGN、RSVD和biasMF等其他幾種模型的結(jié)果進(jìn)行融合，最后效果能夠達(dá)到1.037 23，充分說明了本文的模型不僅能夠有效提升推薦效果，而且對其他模型的結(jié)果也具有補(bǔ)充增強(qiáng)作用。

5 總結(jié)和展望

本文主要介紹了一種基于地理位置信息進(jìn)行協(xié)同過濾的推薦算法，該算法有效利用了物品的地理位置信息，并分析了位置信息對用戶評價(jià)產(chǎn)生的影響，充分考慮了包括地區(qū)的全局性影響、用戶對地區(qū)的偏好、通過用戶消費(fèi)的地點(diǎn)記錄來改善最近鄰計(jì)算方法，以及在隱參數(shù)模型中加入地區(qū)信息等各個(gè)方面，結(jié)合這些因素提出了融合地理位置信息的推薦模型。實(shí)驗(yàn)結(jié)果驗(yàn)證了模型的有效性。

未來工作主要包括以下幾個(gè)方面：研究商家的行業(yè)類別信息與地理位置信息之間潛在的關(guān)聯(lián)關(guān)系；考慮地理位置信息所攜帶的其他知識數(shù)據(jù)，將地理位置信息與其他的上下文信息進(jìn)行有效結(jié)合，并用統(tǒng)一的模型來表示。

[1] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM, 2001: 285-295.

[2] Resnick P, Iacovou N, Suchak M, et al. GroupLens: an open architecture for collaborative filtering of netnews[C]//Proceedings of the 1994 ACM conference on computer supported cooperative work. ACM, 1994: 175-186.

[3] Linden G, Smith B, York J. Amazon. com recommendations: Item-to-item collaborative filtering[J]. Internet Computing, IEEE, 2003, 7(1): 76-80.

[4] Linden G D, Jacobi J A, Benson E A. Collaborative recommendations using item-to-item similarity mappings: U.S. Patent 6,266,649[P]. 2001-7-24.

[5] Su X, Khoshgoftaar T M. A survey of collaborative filtering techniques[J]. Advances in artificial intelligence, 2009: 4.

[6] Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, 2008: 426-434.

[7] Koren Y. Factor in the neighbors: Scalable and accurate collaborative filtering[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2010, 4(1): 1.

[8] Miyahara K, Pazzani M J. Collaborative filtering with the simple Bayesian classifier[M].PRICAI 2000 Topics in Artificial Intelligence. Springer Berlin Heidelberg, 2000: 679-689.

[9] Su X, Khoshgoftaar T M. Collaborative filtering for multi-class data using belief nets algorithms[C]//Proceedings of the Tools with Artificial Intelligence, 2006. ICTAI’06. 18th IEEE International Conference on. IEEE, 2006: 497-504.

[10] Ungar L H, Foster D P. Clustering methods for collaborative filtering[C]//Proceedings of the AAAI Workshop on Recommendation Systems. 1998, 1:114-129.

[11] 王明文,陶紅亮,熊小勇. 雙向聚類迭代的協(xié)同過濾推薦算法[J]. 中文信息學(xué)報(bào), 2008, 22(4):61-65.

[12] Hofmann T. Latent semantic models for collaborative filtering[J]. ACM Transactions on Information Systems (TOIS), 2004, 22(1): 89-115.

[13] Paterek A. Improving regularized singular value decomposition for collaborative filtering[C]//Proceedings of KDD cup and workshop. 2007: 5-8.

[14] Li Y, Nie J, Zhang Y, et al. Contextual recommendation based on text mining[C]//Proceedings of the 23rd International Conference on Computational Linguistics: Posters. Association for Computational Linguistics, 2010: 692-700.

[15] Oku K, Nakajima S, Miyazaki J, et al. Context-aware SVM for context-dependent information recommendation[C]//Proceedings of the Mobile Data Management, 2006. MDM 2006. 7th International Conference on. IEEE, 2006: 109-109.

[16] Rendle S, Gantner Z, Freudenthaler C, et al. Fast context-aware recommendations with factorization machines[C]//Proceedings of the 34th International ACM SIGIR conference on Research and Development in Information Retrieval. ACM, 2011: 635-644.

[17] Koren Y. Collaborative filtering with temporal dynamics[J]. Communications of the ACM, 2010, 53(4): 89-97.

[18] Panniello U, Tuzhilin A, Gorgoglione M, et al. Experimental comparison of pre-vs. post-filtering approaches in context-aware recommender systems[C]//Proceedings of the 3rd ACM Conference on Recommender Systems. ACM, 2009: 265-268.

[19] Y Zheng, X Zhou. Computing with spatial trajectories[M]. Springer Science & Business Media, 2011.

[20] Ye Mao, Peifeng Yin, Wang-Chien Lee. Location recommendation for location-based social networks[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010: 458-461.

[21] Ye M, Yin P, Lee W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2011: 325-334.

[22] Ebrahimi S, Villegas N M, Müller H A, et al. SmarterDeals: a context-aware deal recommendation system based on the smartercontext engine[C]//Proceedings of the 2012 Conference of the Center for Advanced Studies on Collaborative Research. IBM Corp., 2012: 116-130.

[23] Park M H, Hong J H, Cho S B. Location-based recommendationsystem using bayesian user’s preference model in mobile devices[M]. Ubiquitous Intelligence and Computing. Springer Berlin Heidelberg, 2007.

[24] Cao X, Cong G, Jensen C S. Mining significant semantic locations from GPS data[C]//Proceedings of the VLDB Endowment, 2010, 3(1-2): 1009-1020.

[25] Kuo M H, Chen L C, Liang C W. Building and evaluating a location-based service recommendation system with a preference adjustment mechanism[J]. Expert Systems with Applications, 2009, 36(2): 3543-3554.

[26] Bell R M, Koren Y. Scalable collaborative filtering with jointly derived neighborhood interpolation weights[C]//Proceedings of the Data Mining, ICDM 2007. Seventh IEEE International Conference on. IEEE, 2007: 43-52.

[27] Christopher D. Manning，Prabhakar Raghavan，Hinrich Schutze，王斌(譯). 信息檢索導(dǎo)論[M]. 北京：人民郵電出版社，2010.

[28] Lagarias J C, Reeds J A, Wright M H, et al. Convergence properties of the Nelder—Mead simplex method in low dimensions[J]. SIAM Journal on Optimization, 1998, 9(1): 112-147.

A Collaborative Filtering Algorithm Combing Location Information

LU Xiao1，WANG Shuxin2，WANG Bin3，LU Kai4

(1. National Computer Network and Information Security Administration Center, Beijing 100029，China；2. University of Chinese Academy of Sciences，Beijing 100049，China；3. Institute of Information Engineering, Chinese Academy of Sciences，Beijing 100093, China; 4. University of California，Santa Cruz，USA)

Recommendation system based on users’ consumption data is playing an increasingly large application value in e-commerce, And in these data, businesses’ location information which can effectively reflect the user’s personal geographical preference, would make an important significance on recommender system. Existing work generally use only users’ review data as well as the distance between locations, which cannot reflect the relationships between different locations, not to mention that user preferences in different locations should has different weight. This paper proceed from the perspective of geographical area, and study the users’ preferences within the area, as well as the impact of different area partition methods on recommend models. Then we explore to incorporate recommender systems with geographical information effectively, including the location’s global effects and user’s regional preferences, proposing recommendation models, such as LGE, LGN and LRSVD. Experimental evaluation on Yelp dataset demonstrates that our models can effectively improve the prediction results comparing to the traditional methods.

recommender systems； collaborative filtering； location information； neighborhood model； latent factor model

魯驍(1986—)，博士，工程師，主要研究領(lǐng)域?yàn)樯缃痪W(wǎng)絡(luò)、推薦系統(tǒng)、機(jī)器學(xué)習(xí)。E?mail：luxiao@cert．org．cn王書鑫(1985—)，博士，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)、數(shù)量化投資。E?mail：sxwang@szse．cn王斌(1972—)，博士，研究員，主要研究領(lǐng)域?yàn)樾畔z索與自然語言處理。E?mail：wangbin@iie．a(chǎn)c．cn

1003-0077(2016)02-0064-10

2013-10-30 定稿日期： 2014-03-03

國家自然科學(xué)基金青年基金(61402466)

TP391

A