張 偉 韓林玉 張佃磊 任鵬杰 馬 軍 陳竹敏

(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101) (will_zhang2014@outlook.com)

GeoPMF:距離敏感的旅游推薦模型

張 偉 韓林玉 張佃磊 任鵬杰 馬 軍 陳竹敏

(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101) (will_zhang2014@outlook.com)

雖然目前旅游者可以利用Web搜索引擎來選擇旅游景點(diǎn)，但往往難以獲得較好符合自身需要的旅游規(guī)劃.而旅游推薦系統(tǒng)是解決上述問題的有效方式.一個(gè)好的旅游推薦模型應(yīng)具有個(gè)性化并能考慮用戶時(shí)間和費(fèi)用的限制.調(diào)研表明，用戶在選擇旅游景點(diǎn)時(shí)，目的地與用戶常居地的距離常常是一個(gè)需要考慮的問題.因?yàn)槁眯芯嚯x往往可以間接地反映了時(shí)間和費(fèi)用的影響.于是，在貝葉斯模型和概率矩陣分解模型的基礎(chǔ)上，提出一個(gè)旅行距離敏感的旅游推薦模型(geographical probabilistic matrix factorization, GeoPMF).主要思想是基于每個(gè)用戶的旅游歷史，推算出一個(gè)最偏好的旅游距離，并作為一種權(quán)重,添加到傳統(tǒng)的基于概率矩陣分解的推薦模型中.在攜程網(wǎng)站的旅游數(shù)據(jù)集上的實(shí)驗(yàn)表明，與基準(zhǔn)方法相比，GeoPMF 的RMSE(root mean square error)可以降低近10%；與傳統(tǒng)概率矩陣分解模型(PMF)相比，通過考慮距離因子，RMSE平均降幅近3.5%.

旅游推薦；推薦系統(tǒng)；概率矩陣分解模型；距離敏感;GeoPMF算法

近年來，旅游已成為人們娛樂消遣的重要方式.據(jù)國家統(tǒng)計(jì)局網(wǎng)站發(fā)布的《2014年國民經(jīng)濟(jì)和社會(huì)發(fā)展統(tǒng)計(jì)公報(bào)》①http://www.stats.gov.cn/tjsj/zxfb/201502/t20150226_685799.html顯示，2014年全年，我國出國游的人數(shù)達(dá)1億人次,國內(nèi)游達(dá)36億人次.旅游已成為推薦系統(tǒng)[1]的重要應(yīng)用領(lǐng)域之一.目前國內(nèi)攜程、途牛和去哪兒網(wǎng)等旅游網(wǎng)站收集了大量的用戶反饋數(shù)據(jù)，為用戶對(duì)景點(diǎn)的選擇提供了依據(jù).顯然，若能通過旅游推薦系統(tǒng)，為用戶提供更具個(gè)性化的推薦，將會(huì)極大地提高推薦系統(tǒng)的可用性.

關(guān)于旅游推薦已有不少工作.Ge等人[2]認(rèn)為旅行花費(fèi)對(duì)景點(diǎn)選擇有重要的影響，這里花費(fèi)包括費(fèi)用和時(shí)間.他們把旅行花費(fèi)表示為一個(gè)時(shí)間，資金二元組.對(duì)于每個(gè)旅游者，都對(duì)應(yīng)一個(gè)時(shí)間，資金二元組，用以表示用戶的預(yù)期偏好；對(duì)于每個(gè)景點(diǎn)，也有一個(gè)時(shí)間，資金二元組，視為每個(gè)景點(diǎn)的固有屬性.然后利用貝葉斯模型，將這2個(gè)二元組作為評(píng)分預(yù)測(cè)概率的先驗(yàn)條件進(jìn)行建模，給出旅游推薦.在結(jié)合地理因素方面，Tobler[3]在對(duì)基于位置的社交網(wǎng)絡(luò)(LBSN)的研究中，通過對(duì)用戶移動(dòng)設(shè)備GPS信息的記錄，發(fā)現(xiàn)了一種簽到地點(diǎn)的空間聚類現(xiàn)象[3]，即個(gè)人游覽地點(diǎn)趨向于聚在一起.在興趣點(diǎn)(point-of-interest, POI)推薦的研究中，Ye等人[4]提出了一種結(jié)合用戶社交行為和地理因素的推薦模型，該模型是基于傳統(tǒng)的協(xié)同過濾算法中對(duì)相似度的計(jì)算，首先找到與用戶興趣最近鄰的K個(gè)用戶，將這K個(gè)用戶對(duì)該景點(diǎn)評(píng)分的加權(quán)平均作為評(píng)分的預(yù)測(cè)，只是在計(jì)算權(quán)值的時(shí)候結(jié)合了社交和地理信息.在考慮地理因素時(shí)，Ye等人通過分析Foursquare和Whrrl數(shù)據(jù)集，也發(fā)現(xiàn)了空間聚類現(xiàn)象.進(jìn)一步地，Ye提出了一種指數(shù)模型來建模簽到概率與距離的關(guān)系，并利用簽到概率來計(jì)算新的權(quán)值.最終，該模型提高了興趣點(diǎn)推薦的準(zhǔn)確率.然而，這種模型不能很好地解決數(shù)據(jù)稀疏性問題，當(dāng)有新數(shù)據(jù)加入時(shí)，還要重新計(jì)算權(quán)值.而且該模型需要計(jì)算每個(gè)用戶去過的地點(diǎn)兩兩之間的距離，增大了計(jì)算量.Horozov等人[5]提出一種基于權(quán)重的矩陣分解模型來解決這一問題.在用戶特征向量和興趣點(diǎn)特征向量的基礎(chǔ)上，他們提出了用戶活動(dòng)區(qū)域矩陣和興趣點(diǎn)影響力矩陣.指出興趣點(diǎn)的影響力表現(xiàn)在用戶到過某個(gè)景點(diǎn)再去周圍景點(diǎn)的概率，是一種與距離有關(guān)的二維正態(tài)分布形式.Horozov的模型是利用用戶的簽到信息，不包含用戶的反饋打分，初始待分解矩陣中的元素是用戶對(duì)每個(gè)景點(diǎn)的簽到頻次.

已有的研究大多是利用用戶對(duì)地點(diǎn)的簽到數(shù)據(jù).利用簽到的頻次作為待分解的矩陣中的元素，或者將簽到與否描述為一個(gè)布爾變量，利用形成的0-1矩陣計(jì)算用戶相似度.這些方法利用的信息過少；在推薦上考慮用戶的反饋不足；之前基于距離的推薦大多是景點(diǎn)之間的實(shí)地距離，而不是景點(diǎn)與用戶之間的距離，個(gè)性化不強(qiáng).針對(duì)上述問題，本文利用用戶常居地到各個(gè)景點(diǎn)的距離這一地理信息，結(jié)合貝葉斯模型[6-7]，提出一種針對(duì)旅游景點(diǎn)的推薦算法，即距離敏感的旅游推薦模型(geographical probabilistic matrix factorization, GeoPMF).其主要思想是基于每個(gè)用戶的旅游歷史，推算出一個(gè)最偏好的旅游距離，并作為一種權(quán)重添加到傳統(tǒng)的基于概率矩陣分解的推薦模型中.我們模型中的目標(biāo)函數(shù)是一個(gè)具有連續(xù)性的凸函數(shù)，能夠利用隨機(jī)梯度下降快速地訓(xùn)練模型.在攜程網(wǎng)站的旅游數(shù)據(jù)集上的實(shí)驗(yàn)表明，與基準(zhǔn)方法相比，GeoPMF 的RMSE(root mean square error)可以降低近10%；與傳統(tǒng)概率矩陣分解模型(PMF)相比，通過考慮距離因子，RMSE平均降幅近3.5%.

1 基于距離因子的旅游推薦模型

1.1 GeoPMF模型基本框架

較之于傳統(tǒng)的推薦領(lǐng)域，如電影[8-10]、音樂[11-13]、在線商店[14]，旅游推薦數(shù)據(jù)稀疏性問題更加嚴(yán)重.其主要原因在于用戶旅游的頻度較小.相對(duì)影視、音樂等活動(dòng)，旅游的花費(fèi)通常偏高，使得用戶旅游的次數(shù)大大低于傳統(tǒng)推薦領(lǐng)域的行為頻次.我們將攜程網(wǎng)站數(shù)據(jù)的統(tǒng)計(jì)結(jié)果與其他領(lǐng)域的數(shù)據(jù)集進(jìn)行了對(duì)比分析，如表1所示.可以看出，對(duì)于前4個(gè)數(shù)據(jù)集，最稀疏的是Ciao數(shù)據(jù)集，其打分矩陣取值為空的元素占了99.97%;相比而言，攜程數(shù)據(jù)更加稀疏，僅是Ciao的40%.

Table 1 The Sparsity Comparison Between Ctrip and

為了解決稀疏性問題，GeoPMF采用矩陣分解的思路，并將距離因素考慮進(jìn)來.在選擇旅游景點(diǎn)時(shí)，用戶會(huì)考慮景點(diǎn)與自身所在地之間距離的可接受范圍.對(duì)于每一個(gè)用戶，我們將景點(diǎn)劃歸為不同的距離區(qū)段，比如在10 km范圍、10～20 km范圍等等，每一個(gè)距離區(qū)段用戶選擇的概率有差異；而且對(duì)每一個(gè)用戶來說，都有一個(gè)最偏好的距離區(qū)段.GeoPMF正是將這2個(gè)距離區(qū)段引入矩陣分解模型.圖1給出本模型的實(shí)現(xiàn)方法.首先，我們經(jīng)過數(shù)據(jù)預(yù)處理操作，從攜程旅游數(shù)據(jù)中得到用戶對(duì)景點(diǎn)的打分矩陣；然后，利用百度LBS開放平臺(tái)根據(jù)景點(diǎn)地理信息獲得其GPS信息，并計(jì)算每個(gè)用戶-景點(diǎn)對(duì)之間的距離，得到距離區(qū)段矩陣；最后，將這2個(gè)矩陣作為GeoPMF模型的輸入，通過隨機(jī)梯度下降法訓(xùn)練出模型參數(shù)，最終輸出用戶預(yù)測(cè)評(píng)分矩陣.

Fig. 1 The framework of GeoPMF model圖1 GeoPMF模型框架

Fig. 2 Users’ tourism destination spots distribution on Ctrip website圖2 攜程網(wǎng)站不同用戶的旅游景點(diǎn)位置分布

1.2 距離對(duì)景點(diǎn)選擇影響的研究

本文在攜程網(wǎng)旅游數(shù)據(jù)中隨機(jī)選取了部分用戶，在地圖上標(biāo)注他們的旅游目的地，結(jié)果如圖2所示.圖2中用不同顏色的圖標(biāo)區(qū)分不同用戶的旅游歷史，圖釘用來標(biāo)識(shí)用戶的常居地.這些信息都是從攜程網(wǎng)的旅游評(píng)論記錄中獲得.就旅游歷史與用戶常居地的相對(duì)距離來看，不同用戶的行為差異較大.有些用戶偏向僅去距離常居地較近的景點(diǎn)，如用戶2、用戶3和用戶10.而像用戶1、用戶9，卻偏向選擇較遠(yuǎn)的景點(diǎn).

基于對(duì)旅游行為的觀察，本文對(duì)該現(xiàn)象給出的解釋是，用戶選擇景點(diǎn)之前，首先對(duì)要去的距離區(qū)段有一個(gè)基本的定位.前面提到的Ye等人[4]利用指數(shù)模型對(duì)景點(diǎn)實(shí)地距離與選擇景點(diǎn)的概率進(jìn)行了建模，但由于該模型本身具有計(jì)算概率值復(fù)雜、不能解決稀疏性等缺點(diǎn)，因此本文嘗試通過新的方式對(duì)二者關(guān)系進(jìn)行建模.首先，基于上述解釋，我們認(rèn)為景點(diǎn)所處的區(qū)段比實(shí)地距離更有考慮價(jià)值，鑒于此，在獲取用戶景點(diǎn)的經(jīng)緯度信息后，我們計(jì)算出每個(gè)用戶與去過的景點(diǎn)的距離，然后按照10 km為單位為這些景點(diǎn)進(jìn)行區(qū)段劃分.本文對(duì)不同區(qū)段內(nèi)旅游數(shù)量統(tǒng)計(jì)處理，結(jié)果如圖3所示.橫坐標(biāo)表示不同的距離區(qū)段，縱坐標(biāo)是在每個(gè)區(qū)段內(nèi)旅游頻數(shù).從圖3中可以看出，用戶在不同區(qū)段內(nèi)旅游頻次與距離區(qū)段有明顯相關(guān)性.

Fig. 3 The tourism frequency histogram in different distance sections圖3 不同距離區(qū)段內(nèi)旅游頻次直方圖

然而，景點(diǎn)對(duì)用戶的吸引力不僅在于旅游頻次，還在于用戶的評(píng)分，用戶對(duì)景點(diǎn)的評(píng)分高低說明用戶對(duì)該景點(diǎn)的喜歡程度.為了描述用戶對(duì)不同區(qū)段景點(diǎn)的偏好，我們定義了一個(gè)概率函數(shù)，見式(1)：

(1)

其中，c表示距離區(qū)段編號(hào)，以10 km為單位；κ表示用戶i去過的景點(diǎn)集合；Ii j(c)為指示函數(shù)，當(dāng)景點(diǎn)j位于用戶i的第c個(gè)區(qū)段時(shí)為1，否則為0；ri j是用戶i對(duì)景點(diǎn)j的評(píng)分.我們用P(c)來估計(jì)用戶對(duì)不同距離區(qū)段的喜好程度.統(tǒng)計(jì)結(jié)果如圖4所示.橫坐標(biāo)為不同距離區(qū)段;縱坐標(biāo)表示用戶選擇該區(qū)段的概率，即P(c).從中看出，用戶對(duì)不同區(qū)段內(nèi)景點(diǎn)的喜好程度與距離區(qū)段也存在明顯的相關(guān)性.而且，總體而言，用戶更喜好距離較近的景點(diǎn).

Fig. 4 The probability distribution of user preference with different tourist attractions圖4 用戶對(duì)不同景點(diǎn)偏好的概率分布

經(jīng)過上述統(tǒng)計(jì)分析，我們得出結(jié)論：景點(diǎn)所處的距離區(qū)段不僅對(duì)用戶旅行目的地的選擇有重要影響，也間接地影響了用戶對(duì)去過景點(diǎn)的反饋評(píng)分.本文假設(shè)每個(gè)用戶在旅游的時(shí)候心中有一個(gè)最偏愛的距離區(qū)段即di，它與景點(diǎn)對(duì)應(yīng)的距離區(qū)段Di j之間的偏差越小，用戶選擇的概率越大，給較高評(píng)分的概率也越大.因此，在1.3節(jié)中，我們將2個(gè)距離因子：用戶最偏愛的距離區(qū)段c和表示景點(diǎn)屬性的距離區(qū)段矩陣D作為考慮因素，建立一個(gè)對(duì)旅行距離敏感的旅游推薦模型GeoPMF.

1.3 GeoPMF模型的形式化

GeoPMF將景點(diǎn)相對(duì)于每個(gè)用戶所處的距離區(qū)段作為考慮因素.為此，本文引入距離區(qū)段矩陣D，其中每一個(gè)元素Di j表示相對(duì)于用戶i的常居地來說，景點(diǎn)j所處的距離區(qū)段.用戶i最偏愛的距離區(qū)段記為di.接著，我們將Si j引入到矩陣分解模型中.Si j表示用戶i最偏愛區(qū)段di與景點(diǎn)j所處區(qū)段Di j的相似度，取值范圍是[0,1].區(qū)別于傳統(tǒng)矩陣分解，我們對(duì)評(píng)分矩陣的分解見式(2)：

(2)

Fig. 5 Rating matrix decomposition of GeoPMF圖5 GeoPMF的評(píng)分矩陣分解

設(shè)評(píng)分的估計(jì)值與真實(shí)值之間存在誤差為ε，并假設(shè)ε服從高斯分布，則

(3)

其中N(Ri j|μ,σ2)是滿足均值為μ、方差為σ2的高斯分布.

Si j的定義基于以下思想：對(duì)于用戶去過的景點(diǎn)，所處的距離區(qū)段Di j與di的差值會(huì)影響用戶的反饋評(píng)分，二者偏差越小，用戶給高分的可能性越大；對(duì)于用戶沒有去過的景點(diǎn)，Di j與di偏差越小，用戶選擇該景點(diǎn)作為旅游目的地的可能性也越大.因此，可采用歐氏距離來計(jì)算相似度，見式(4).對(duì)于每一個(gè)Si j，表示用戶最偏愛距離區(qū)段di與景點(diǎn)所處距離區(qū)段Di j的近似程度，值越大，二者越近似，用戶選擇該景點(diǎn)的概率越高.

Si j=S(di,Di j)=1-‖di-Di j‖2.

(4)

根據(jù)極大似然估計(jì)的思想，假設(shè)Ri j之間是獨(dú)立同分布的，我們得到用戶評(píng)分矩陣的似然函數(shù)為式(5)：

(5)

(6)

其中，C是一個(gè)與參數(shù)無關(guān)的常量.

使上述目標(biāo)函數(shù)最大化，等價(jià)于最小化公式：

(7)

(8)

式(8)就是GeoPMF最終的目標(biāo)函數(shù).我們利用隨機(jī)梯度下降法(stochastic gradient descent, SGD)學(xué)習(xí)得到參數(shù)U，V，d.

GeoPMF的概率模型圖如圖6(b).較之于模型PMF(圖6(a))，本文在預(yù)測(cè)評(píng)分時(shí)，引入距離因子di和距離區(qū)段矩陣D.

2 實(shí) 驗(yàn)

2.1 數(shù)據(jù)集

1) 攜程網(wǎng)旅游數(shù)據(jù).本文實(shí)驗(yàn)數(shù)據(jù)集采用攜程網(wǎng)旅游攻略的用戶評(píng)論信息.數(shù)據(jù)集包含用戶節(jié)點(diǎn)283 952個(gè)、景點(diǎn)節(jié)點(diǎn)20 688個(gè)、用戶打分723 732個(gè)，見表1所示.

2) 獲取地理信息.根據(jù)景點(diǎn)節(jié)點(diǎn)的名稱信息，使用百度地圖提供的開放API，生成景點(diǎn)以及用戶常居地的經(jīng)緯度坐標(biāo).距離選取10 km為步長，每10 km表示一個(gè)區(qū)段.我們計(jì)算了每個(gè)用戶常居地到他去過的景點(diǎn)之間的距離，確定景點(diǎn)所屬的距離區(qū)段用以形成距離區(qū)段矩陣D.

3) 生成訓(xùn)練集測(cè)試集.本文采用按時(shí)間分割的方式劃分測(cè)試集訓(xùn)練集，見圖7所示.首先，去掉評(píng)論次數(shù)少于3條的用戶的所有評(píng)分?jǐn)?shù)據(jù)；然后，按照每個(gè)用戶評(píng)論時(shí)間的順序?qū)υu(píng)分?jǐn)?shù)據(jù)排序；最后，按照2∶1的比例將每個(gè)用戶前23的評(píng)分作為訓(xùn)練集，剩余的作為測(cè)試集，并且對(duì)于訓(xùn)練集中的每個(gè)用戶，保證在測(cè)試集中至少有一個(gè)評(píng)分?jǐn)?shù)據(jù).

經(jīng)過數(shù)據(jù)處理，我們最終得到3個(gè)數(shù)據(jù)文件：訓(xùn)練集文件(xctour_train.txt)、測(cè)試集文件(xtour_test.txt)和距離區(qū)段文件(distance_section.txt).訓(xùn)練集和測(cè)試集所包含用戶數(shù)、景點(diǎn)數(shù)以及評(píng)分?jǐn)?shù)等統(tǒng)計(jì)信息，見表2.距離區(qū)段文件保存了每個(gè)用戶去過的所有景點(diǎn)所屬的距離區(qū)段信息，共包含300 677個(gè)距離區(qū)段數(shù)據(jù).

Fig. 7 Preprocessing on Ctrip dataset圖7 攜程數(shù)據(jù)集預(yù)處理

DatasetFileSize∕MBUserNumberSiteNumberRatingNumberorSectionNumberMinScoreorMinDistanceMaxScoreorMaxDistanceSetRatio∕%TrainingSet2.4631408171771935411564.37TestSet1.3731408204511071361535.63SectionFile4.0731408205883006770458

2.2 基準(zhǔn)方法

1) GlobalAverage.用戶評(píng)分矩陣所有真實(shí)值的平均值作為評(píng)分預(yù)測(cè)值.

2) ItemAverage.對(duì)某一景點(diǎn)的評(píng)分等于該景點(diǎn)收到的所有評(píng)分的平均值.

SVD是一種最基本的矩陣分解模型.

4) PMF.由Salakhutdinov等人[16]首先提出，其概率模型圖見圖6(a).他假設(shè)預(yù)測(cè)評(píng)分與真實(shí)評(píng)分之間存在高斯噪聲，并假設(shè)U,V滿足均值為0的高斯分布.最終得到的損失函數(shù)為式(10)：

5) SocialMF.由Jamali和Ester[17]提出，將社交網(wǎng)絡(luò)中的信任關(guān)系結(jié)合到矩陣分解中，其目標(biāo)函數(shù)形式為式(11)：

其中,T表示信任關(guān)系矩陣，當(dāng)用戶v關(guān)注用戶i時(shí)，Ti,v=1;Ni表示用戶i所關(guān)注的其他用戶的集合.通過加入信任關(guān)系這一特征，Jamali和Ester通過實(shí)驗(yàn)證明該方法能顯著降低RMSE.在攜程旅游數(shù)據(jù)中也能夠取得用戶之間的關(guān)注信息，而且GeoPMF和SocialMF都是以矩陣分解為基礎(chǔ)，區(qū)別在于選取的上下文信息以及建模形式不同，因此我們將SocialMF也作為比較對(duì)象進(jìn)行實(shí)驗(yàn).

上述所有的推薦算法都在我們處理過的攜程訓(xùn)練集xctour_train.txt上進(jìn)行實(shí)驗(yàn).

2.3 評(píng)價(jià)指標(biāo)

在推薦領(lǐng)域，評(píng)價(jià)一個(gè)推薦算法預(yù)測(cè)評(píng)分的好壞，常用的評(píng)價(jià)指標(biāo)是RMSE，用來表示估計(jì)評(píng)分的誤差，定義為式(12)：

2.4 參數(shù)設(shè)置

PMF，SVD正規(guī)項(xiàng)λU=λV=0.001，GeoPMF正規(guī)項(xiàng)設(shè)置為λU=λV=0.01.d的每一項(xiàng)利用景點(diǎn)距離區(qū)段均值進(jìn)行初始化，即di初值為D對(duì)應(yīng)行向量元素的均值.矩陣U,V中元素取值服從均值為0、標(biāo)準(zhǔn)差為0.1高斯分布.

2.5 結(jié)果比較

1) GeoPMF與基準(zhǔn)方法及傳統(tǒng)矩陣分解的比較.考慮特征向量Ui和Vj的維數(shù)K，即潛在因子數(shù)會(huì)對(duì)結(jié)果造成影響，我們?cè)O(shè)置了不同的特征向量維數(shù)進(jìn)行實(shí)驗(yàn)，得到圖8中的結(jié)果.最下面的一條線是GeoPMF的結(jié)果.總體來看，矩陣分解方法要比基準(zhǔn)方法效果好.基準(zhǔn)方法GlobalAverage和ItemAverage是直接利用均值進(jìn)行預(yù)測(cè)，所以RMSE并不發(fā)生變化，在圖8中表現(xiàn)為直線.而PMF和SVD區(qū)別僅在于正規(guī)項(xiàng)的加入，所以2條曲線幾乎一致.在每個(gè)維度下，GeoPMF的結(jié)果都要優(yōu)于其他方法.橫向來看，對(duì)于GeoPMF，SocialMF，SVD來說，隨著特征向量維數(shù)的增加，RMSE先減少后增加，均在維數(shù)為5達(dá)到最優(yōu).隨著特征向量維數(shù)的增加，GeoPMF的結(jié)果與PMF和SVD之間差距逐漸增大.當(dāng)特征向量維數(shù)為5時(shí)，RMSE降低幅度近1%，在達(dá)到穩(wěn)定狀態(tài)時(shí)，RMSE降低幅度達(dá)到5%.SocialMF的RMSE在特征向量維數(shù)為5時(shí)達(dá)到最優(yōu)，但最優(yōu)值也要稍差于GeoPMF，且維數(shù)繼續(xù)增加時(shí)，RMSE劇烈升高，SocialMF實(shí)驗(yàn)結(jié)果惡化.最終實(shí)驗(yàn)結(jié)果顯示，較之于基準(zhǔn)方法，GeoPMF的RMSE平均降幅為9%，最優(yōu)值降幅為10%；較之于矩陣分解方法PMF和SVD，RMSE平均降幅為3.5%，最優(yōu)值降幅為1%.

Fig. 8 Impact of dimensionality K on RMSE圖8 特征向量維數(shù)K對(duì)RMSE的影響

雖然從上述實(shí)驗(yàn)結(jié)果我們看到GeoPMF模型的優(yōu)越性，但是為了驗(yàn)證GeoPMF實(shí)驗(yàn)結(jié)果是真正優(yōu)于基準(zhǔn)方法，還是因?yàn)閮?yōu)化過程的隨機(jī)初始化等導(dǎo)致的性能提高，本文對(duì)圖8中實(shí)驗(yàn)結(jié)果進(jìn)行了顯著性檢驗(yàn)[18].我們對(duì)PMF和GeoPMF的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行顯著性分析，表3是對(duì)2組數(shù)據(jù)進(jìn)行獨(dú)立T檢驗(yàn)的結(jié)果.從結(jié)果中看出，顯著性為0.005，說明二者方差存在顯著性差異，在方差不等的情況下，雙尾顯著性為0.000;而當(dāng)顯著性小于0.05時(shí)，認(rèn)為配對(duì)樣本之間存在顯著差異，即后測(cè)與前測(cè)之間存在顯著差異，說明GeoPMF對(duì)于RMSE的降低效果顯著.

Table 3 T-test Result in SPSS表3 SPSS T-檢驗(yàn)結(jié)果

接著，我們比較不同算法RMSE隨迭代次數(shù)的變化.根據(jù)上述實(shí)驗(yàn)結(jié)果，我們將特征向量維數(shù)固定于5.實(shí)驗(yàn)結(jié)果如圖9所示.從圖9可看出，GeoPMF效果也要優(yōu)于其他推薦算法，當(dāng)算法收斂時(shí)，RMSE達(dá)到0.79，較之于基準(zhǔn)方法和PMF分別有10%和1%的提高，并且也稍優(yōu)于SocialMF方法.總體來看，隨著迭代次數(shù)的增加，GeoPMF的RMSE不斷降低，收斂后較之于PMF和SVD，更加穩(wěn)定.另外，可以看出，而SVD由于沒有引入正規(guī)項(xiàng)，當(dāng)?shù)螖?shù)達(dá)到30時(shí)，RMSE出現(xiàn)上升趨勢(shì)，說明存在過擬合現(xiàn)象.

Fig. 9 Impact of iter number on RMSE (K=5)圖9 迭代次數(shù)對(duì)RMSE的影響(K=5)

2) 距離區(qū)段可視化.d是在模型假設(shè)中定義的區(qū)段向量，其中的每一個(gè)元素di代表用戶最偏好距離。我們通過隨機(jī)梯度下降學(xué)習(xí)矩陣U，V的同時(shí)，也學(xué)習(xí)得到d.為了直觀地展示距離區(qū)段這一距離因子，我們對(duì)d的學(xué)習(xí)結(jié)果和用戶已經(jīng)去過的景點(diǎn)區(qū)段進(jìn)行了可視化分析，如圖10所示.橫坐標(biāo)表示隨機(jī)選取的13位用戶.每一位用戶對(duì)應(yīng)縱軸的一列散點(diǎn)集合，我們用Du表示與用戶對(duì)應(yīng)的一列點(diǎn)集.其中，每一列的每一個(gè)星型符號(hào)表示用戶去過的景點(diǎn)所屬距離區(qū)段即Di j，菱形表示GeoPMF模型學(xué)習(xí)得到的用戶最偏好區(qū)段di.注意，在訓(xùn)練開始前，d中元素是用D中對(duì)應(yīng)的每一行距離區(qū)段均值進(jìn)行初始化的.從圖10中看出，在訓(xùn)練結(jié)束后，菱形落在星型符號(hào)集中分布的區(qū)域周圍，即d更加靠近用戶最常去的距離區(qū)段，這與人們的經(jīng)驗(yàn)一致.

3) 模型效率.表4是對(duì)矩陣分解算法運(yùn)行時(shí)間的統(tǒng)計(jì)結(jié)果.從表4可看出，GeoPMF運(yùn)行時(shí)間較之于PMF和SVD有所增加.由于算法引入距離區(qū)段矩陣，并且在學(xué)習(xí)過程中要同時(shí)學(xué)習(xí)距離區(qū)段向量d，使得性能相對(duì)PMF和SVD來說有所降低.但這種運(yùn)行時(shí)間的增加相對(duì)于RMSE的降低來說是在可接受范圍之內(nèi)的.而SocialMF的運(yùn)行時(shí)間較之于GeoPMF增加了近3倍，且從前面的實(shí)驗(yàn)結(jié)果看，GeoPMF的實(shí)驗(yàn)結(jié)果也要稍優(yōu)于SocialMF，這也更加體現(xiàn)了GeoPMF的優(yōu)越性.

Table 4 The Runtime of Recommendation Algorithms表4 推薦算法運(yùn)行時(shí)間

3 總結(jié)及未來工作

本文中，我們對(duì)攜程網(wǎng)旅游數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，證明景點(diǎn)所處的距離區(qū)段在旅游目的地選擇中是一個(gè)重要的考慮因素.據(jù)此，我們提出了一種基于距離因子的旅游推薦模型GeoPMF，從矩陣分解的角度研究了旅游推薦算法，目的是降低評(píng)分估計(jì)誤差.我們結(jié)合PMF，將用戶最偏愛距離區(qū)段和景點(diǎn)實(shí)際所處的距離區(qū)段作為考慮條件，納入概率分解模型.這樣做的好處是，我們就既考慮用戶對(duì)景點(diǎn)本身的偏好，同時(shí)考慮了用戶對(duì)距離區(qū)段的偏好.在最終的實(shí)驗(yàn)結(jié)果中，RMSE降低到0.79.通過與基準(zhǔn)方法的比較，證明了GeoPMF對(duì)降低RMSE有顯著效果.同時(shí)，GeoPMF對(duì)用戶旅游景點(diǎn)的選擇上也有一定指導(dǎo)意義.

在未來的工作中，我們會(huì)將GeoPMF應(yīng)用于其他旅游網(wǎng)站的數(shù)據(jù)以及其他包含地理信息的數(shù)據(jù)集，用來驗(yàn)證該模型的適應(yīng)性.另外，我們的GeoPMF也有一定局限性，首先，我們模型選擇用戶的常居地是一個(gè)定值，在現(xiàn)實(shí)生活中，用戶的地理位置往往伴隨著遷徙行為，比如一個(gè)用戶常居地從一個(gè)省份到另一個(gè)省份；其次，當(dāng)用戶到達(dá)一個(gè)景點(diǎn)進(jìn)行旅游時(shí)，常常會(huì)對(duì)所在目的地的周邊景點(diǎn)也產(chǎn)生興趣.另外，除了考慮物理距離，還應(yīng)考慮交通的便利性.對(duì)于以上情況，我們會(huì)以GeoPMF為基礎(chǔ)，結(jié)合景點(diǎn)選擇中的各種影響因素，提出一種更具泛化能力的模型，為旅游者的行程做出更好的規(guī)劃.

[1]Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749

[2]Ge Y, Liu Q, Xiong H, et al. Cost-aware travel tour recommendation[C] //Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2011: 983-991

[3]Tobler W. A computer movie simulating urban growth in the detroit region [J]. Economic Geography, 1970, 46: 234-240

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

[5]Horozov T, Narasimhan N, Vasudevan V. Using location for personalized poi recommendations in mobile environments [C] //Proc of the Int Symp on Applications Internet. Los Alamitos, CA: IEEE Computer Society, 2006: 625-636

[6]Ji Junzhong, Liu Chunnian, Sha Zhiqiang. Bayesian belief network model learning, inference and applications [J]. Computer Engineering and Applications 2003, 39(5): 24-27 (in Chinese)(冀俊忠, 劉椿年, 沙志強(qiáng). 貝葉斯網(wǎng)模型的學(xué)習(xí)、推理和應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2003, 39(5): 24-27)

[7]Cheng Lanlan, He Pilian, Sun Yueheng. Study on Chinese keyword extraction algorithm based on naive Bayes model [J]. Journal of Computer Applications, 2005, 25(12): 2780-2782 (in Chinese)(程嵐嵐, 何丕廉, 孫越恒. 基于樸素貝葉斯模型的中文關(guān)鍵詞提取算法研究[J]. 計(jì)算機(jī)應(yīng)用, 2005, 25(12): 2780-2782)

[8]Lekakos G, Caravelas P. A hybrid approach for movie recommendation [J]. Multimedia Tools & Applications, 2008, 36(1/2): 55-70

[9]Biancalana C, Gasparetti F, Micarelli A, et al. Context-aware movie recommendation based on signal srocessing and machine learning [C] //Proc of the 2nd Challenge on Context-Aware Movie Recommendation. New York: ACM, 2011: 5-10

[10]Mirza B J, Keller B J, Ramakrishnan N. Studying recommendation algorithms by graph analysis [J]. Journal of Intelligent Information Systems, 2003, 20(2): 131-160

[11]Cano P, Koppenberger M, Wack N. Content-based music audio recommendation[C] //Proc of the 13th Annual ACM Int Conf on Multimedia. New York: ACM, 2005: 211-212

[12]Chen H, Chen A L P. A music recommendation system based on music data grouping and user interests [C] //Proc of the 10th Int Conf on Information and knowledge Management. New York: ACM, 2001: 231-238

[13]Li Ruimin, Lin Hongfei, Yan Jun. Mining latent semantic on user-tag-item for personalized music recommendation [J]. Journal of Computer Research and Development, 2014, 51(10): 2270-2276 (in Chinese)(李瑞敏, 林鴻飛, 閆俊. 基于用戶-標(biāo)簽-項(xiàng)目語義挖掘的個(gè)性化音樂推薦[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(10): 2270-2276)

[14]Lee K C, Kwon S. Online shopping recommendation mechanism and its influence on consumer decisions and behaviors: A causal map approach[J]. Expert Systems with Applications, 2008, 35(4): 1567-1574

[15]Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model [C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[16]Salakhutdinov R, Mnih A. Probabilistic matrix factorization[C/OL] //Proc of the Advances in Neural Information Processing Systems. 2007: 1257-1264 [2015-11-16]. http: //papers.nips.cc/paper/3208-probabilistic-matrix-factorization.pdf

[17]Jamali M, Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C] //Proc of the 4th ACM Conf on Recommender Systems. New York: ACM, 2010: 135-142

[18]Zhou Yuzhu, Jiang Fenghua. The regression analysis of the experimental DATAS and the remarkable examination [J]. Physical Experiment of College, 2001, 14(4): 43-46 (in Chinese)(周玉珠, 姜奉華. 實(shí)驗(yàn)數(shù)據(jù)的一元線性回歸分析及其顯著性檢驗(yàn)[J]. 大學(xué)物理實(shí)驗(yàn), 2001, 14(4): 43-46)

Zhang Wei, born in 1993. PhD candidate in Shandong University. Student member of CCF. His main research interests include information retrieval, tweet summarization and recommender system.

Han Linyu, born in 1992. Master candidate in Shandong University. Student member of CCF. Her main research interests include information retrieval, Web data mining and recommender systems(zhangdianlei11@gmail.com).

Zhang Dianlei, born in 1993. Master candidate in Shandong University. Student member of CCF. His main research interests include information retrieval, data mining and recommender systems(zhangdianlei11@gmail.com).

Ren Pengjie, born in 1990. PhD candidate in Shandong University. Student member of CCF. His main research interests include information retrieval, data mining.

Ma Jun, born in 1956. Professor and PhD supervisor in Shandong University. Senior member of CCF. His main research interests include information retrieval, data mining, parallel computing, natural language processing.

Chen Zhumin, born in 1977. Associate professor and master supervisor in Shandong University. Senior member of CCF. His main research interests include Web information retrieval, data mining, and social computing(chenzhumin@sdu.edu.cn).

GeoPMF: A Distance-Aware Tour Recommendation Model

Zhang Wei, Han Linyu, Zhang Dianlei, Ren Pengjie, Ma Jun, and Chen Zhumin

(SchoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

Although people can use Web search engines to explore scenic spots for traveling, they often find it very difficult to discover the sighting sites which match their personalized need well. Tour recommendation systems can be used to solve the issue. A good tour recommendation system should be able to provide personalized recommendation and take the time and cost factors into account. Furthermore, our investigation shows that often a useruwill consider the distance between herhis habitual residence and the tour destination when shehe makes herhis travel plan. It is because that the travel distance reflects the effect of time and cost indirectly. Therefore, we propose a distance-aware tour recommendation model, named GeoPMF (geographical probabilistic matrix factorization), which is developed based on the Bayesian model and PMF (probabilistic matrix factorization). The main idea of GeoPMF is that for each user we try to get a most preferred travel distance span by mining her past tour records. Then we use it as a kind of weight factors added into the traditional PMF model. Experiments on travel data of Ctrip show that, our new method can decreaseRMSE(root mean square error) nearly 10% compared with some baseline methods. And when compared with the traditional PMF model, the average decline onRMSEis nearly 3.5% in virtue of the distance factor.

tour recommendation; recommender system; probabilistic matrix factorization (PMF) model; distance-aware; GeoPMF

2015-09-15；

2015-12-22

國家自然科學(xué)基金項(xiàng)目(61272240,61672322)；山東省自然科學(xué)基金項(xiàng)目(ZR2012FM037)；微軟國際合作基金項(xiàng)目(FY14-RES-THEME-25) This work was supported by the National Natural Science Foundation of China(61272240,61672322), the Natural Science Foundation of Shandong Province(ZR2012FM037), and the Microsoft International Cooperation Fund Project (FY14-RES-THEME-25).

馬軍(majun@sdu.edu.cn)

TP301