基于Geo-tagged照片的旅游推薦研究

王 楠，曹 菡

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

基于Geo-tagged照片的旅游推薦研究

王 楠，曹 菡

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

在Web2.0時(shí)代，隨著智能手機(jī)、數(shù)碼相機(jī)和GPS導(dǎo)航系統(tǒng)等電子產(chǎn)品的廣泛普及和社交網(wǎng)站的迅速發(fā)展，涌現(xiàn)出各種UGC(User Generated Content)形式的數(shù)據(jù)。同時(shí)，人們喜歡以圖片或文字方式在網(wǎng)絡(luò)上分享自己旅游的所見所聞，社交媒體數(shù)據(jù)通常包括文本標(biāo)簽、地理位置(經(jīng)緯度)和拍攝時(shí)間等信息，這就為研究旅游推薦提供了可靠數(shù)據(jù)。使用Flickr網(wǎng)站上Geo-tagged照片數(shù)據(jù)集，采用基于密度的DBSCAN聚類算法對(duì)照片的經(jīng)緯度進(jìn)行聚類，結(jié)合TF-IDF算法為興趣點(diǎn)命名，得到游客在西安的旅游興趣點(diǎn)，然后綜合考慮用戶對(duì)興趣點(diǎn)偏好和興趣點(diǎn)屬性，利用改進(jìn)的協(xié)同過濾推薦算法為用戶提供旅游推薦服務(wù)。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效提高系統(tǒng)的推薦精度。最后構(gòu)建了用戶信任網(wǎng)絡(luò)，提高了推薦系統(tǒng)的信任度和滿意度。

Geo-tagged；DBSCAN;用戶偏好；協(xié)同過濾；信任網(wǎng)絡(luò)

0 引 言

在Web2.0時(shí)代，國外Flickr和國內(nèi)新浪微博等社交網(wǎng)站，每時(shí)每刻都會(huì)產(chǎn)生數(shù)以萬計(jì)的UGC(User Generated Content)數(shù)據(jù)。旅游作為常見的娛樂方式，人們很愿意通過文字、圖片等形式分享旅途所見。這些數(shù)據(jù)不僅包含文本，還有地理標(biāo)簽(包括經(jīng)度和緯度)等信息。傳統(tǒng)的旅行社大多數(shù)根據(jù)大眾的旅游經(jīng)歷來規(guī)劃，比較耗時(shí)，沒有充分利用信息技術(shù)等優(yōu)勢(shì)。而旅游網(wǎng)站側(cè)重?zé)狳c(diǎn)推薦和各種票務(wù)購買活動(dòng)等，無法提供針對(duì)性的旅游推薦服務(wù)。

目前很多學(xué)者利用數(shù)據(jù)挖掘等技術(shù)[1]對(duì)旅游服務(wù)做了一定研究。胥皇等[2]以“街旁網(wǎng)”簽到數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，建立地點(diǎn)和用戶偏好模型，實(shí)現(xiàn)了Android平臺(tái)上的個(gè)性化旅游包推薦系統(tǒng)；鄒永貴等[3]通過分析簽到數(shù)據(jù)和好友關(guān)系，結(jié)合R*樹的空間索引機(jī)制，利用DBSCAN聚類算法挖掘用戶的移動(dòng)軌跡；李春明等[4]利用在Panaramio上的照片數(shù)據(jù)，研究了廈門市鼓浪嶼景區(qū)的游客時(shí)空行為；Kurashima等[5]通過挖掘Flickr網(wǎng)站基于地理標(biāo)簽的照片數(shù)據(jù)，利用Mean-Shift均值漂移算法對(duì)景點(diǎn)照片聚類，并結(jié)合Markov模型和主題模型，為用戶推薦旅游線路；Majid等[6]利用Flickr中有關(guān)國內(nèi)城市的照片數(shù)據(jù)挖掘旅游偏好，提出了一個(gè)基于地理標(biāo)簽的上下文(包括天氣、位置)感知的個(gè)性化推薦方法；Lu等[7]運(yùn)用Mean-Shift聚類識(shí)別景點(diǎn)，根據(jù)用戶偏好和歷史旅游記錄把線路規(guī)劃轉(zhuǎn)換成有向圖的動(dòng)態(tài)規(guī)劃尋找最佳路徑問題，設(shè)計(jì)個(gè)性化旅游線路推薦算法；Cheng等[8]不僅利用帶有地理標(biāo)簽的圖片和旅游日志，還使用人臉識(shí)別技術(shù)挖掘游客的背景信息，考慮旅游團(tuán)體類型[9]，而后采用貝葉斯學(xué)習(xí)模型實(shí)現(xiàn)移動(dòng)旅游推薦。

協(xié)同過濾作為推薦系統(tǒng)中應(yīng)用最為成熟的技術(shù)，已應(yīng)用在電影、圖書和旅游景點(diǎn)推薦等方面?；谟脩舻膮f(xié)同過濾推薦較為社會(huì)化，基于項(xiàng)目的協(xié)同過濾推薦更加個(gè)性化。隨著個(gè)性化推薦系統(tǒng)的普及，注冊(cè)用戶將越來越多，更新變化越來越大，相比之下，旅游景點(diǎn)的變化則微乎其微。從技術(shù)上考慮，維系一個(gè)旅游用戶相似度矩陣較難，而一個(gè)旅游景點(diǎn)之間的相似度矩陣較為穩(wěn)定[10]，故文中采用基于項(xiàng)目的協(xié)同過濾算法。

目前國內(nèi)對(duì)Geo-tagged照片數(shù)據(jù)的研究較少，故文中針對(duì)Flickr圖片分享網(wǎng)站中Geo-tagged照片數(shù)據(jù)作為研究對(duì)象，使用DBSCAN算法挖掘用戶的旅游興趣點(diǎn)偏好，然后利用改進(jìn)的基于項(xiàng)目的協(xié)同過濾推薦算法為游客提供高精度的旅游推薦服務(wù)，最后構(gòu)建用戶信任網(wǎng)絡(luò)，提高推薦的信任度和滿意度。

1 研究方法概述

1.1 基于密度的DBSCAN算法

基于密度的DBSCAN[11]算法無需預(yù)先指定類簇的數(shù)目，可以發(fā)現(xiàn)任意形狀的類簇，同時(shí)可以檢測(cè)出噪聲點(diǎn)，且對(duì)噪聲點(diǎn)魯棒性較強(qiáng)。而旅游區(qū)域有不同的類簇形狀大小和規(guī)模，該算法正好符合旅游興趣點(diǎn)的分布特點(diǎn)。文中采用基于密度的DBSCAN聚類算法對(duì)照片的GPS信息(經(jīng)緯度)進(jìn)行聚類形成類簇。

DBSCAN算法的兩個(gè)重要參數(shù)為Eps(半徑)、MinPts(每一個(gè)類簇照片的最小數(shù)目)，只要滿足每個(gè)類簇的距離核心點(diǎn)Eps范圍內(nèi)的最小照片數(shù)量不小于MinPts，就可以作為一個(gè)類簇。

該算法的核心思想描述如下：從某個(gè)選定的核心點(diǎn)出發(fā)，不斷向密度可達(dá)的區(qū)域擴(kuò)張，從而得到一個(gè)包含核心點(diǎn)和邊界點(diǎn)的最大化區(qū)域，且區(qū)域中任意兩點(diǎn)都是密度相連的。

1.2 改進(jìn)的基于項(xiàng)目的協(xié)同過濾算法

傳統(tǒng)的推薦系統(tǒng)大部分都是基于評(píng)分信息的，而事實(shí)上，用戶對(duì)景點(diǎn)的評(píng)分信息很少，且評(píng)分標(biāo)準(zhǔn)不盡相同。文中采用偏好值較能真實(shí)地反映用戶對(duì)景點(diǎn)的喜愛度，同時(shí)考慮景點(diǎn)本身的屬性信息，采用綜合相似度進(jìn)行推薦。

基于項(xiàng)目協(xié)同過濾算法[12-13]的核心就是計(jì)算項(xiàng)目之間的相似度，常用的相似度計(jì)算方法有Pearson方法、余弦法和修正的余弦法等。文中采用Pearson相似度和余弦相似度計(jì)算方法分別對(duì)游客偏好評(píng)分和項(xiàng)目類型屬性進(jìn)行計(jì)算，主要步驟如下：

(1)計(jì)算項(xiàng)目相似度。

項(xiàng)目i和項(xiàng)目j之間的相似度sim(i,j)計(jì)算公式如下：

pearson_sim(i,j)=

用戶偏好矩陣如表1所示。

表1 用戶偏好矩陣

其中,rui表示用戶u對(duì)項(xiàng)目i的偏好值(0～5之間)，數(shù)值大小代表偏好程度。

項(xiàng)目屬性矩陣如表2所示，項(xiàng)目有k個(gè)屬性。

表2 項(xiàng)目屬性矩陣

計(jì)算任意兩個(gè)項(xiàng)目之間的相似度后得到初步的n*n的相似度矩陣，然后進(jìn)行最大值歸一化處理，作為最終的項(xiàng)目相似度矩陣，歸一化公式具體如下:

(2)找出項(xiàng)目的k近鄰，預(yù)測(cè)用戶的未評(píng)分項(xiàng)目，進(jìn)而推薦。

由(1)計(jì)算的項(xiàng)目相似度矩陣，可以得到項(xiàng)目i的相似項(xiàng)目集合kNS(i)，同時(shí)要求用戶必須評(píng)論過該相似項(xiàng)目，預(yù)測(cè)用戶u對(duì)未表示偏好的項(xiàng)目i的偏好度pui，具體公式如下：

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

文中利用Python語言編寫程序，爬取Flickr上有關(guān)西安周邊帶有地理標(biāo)簽信息的照片數(shù)據(jù)。以西安市的地理坐標(biāo)(108.950 00，34.266 67)為中心，獲取方圓32km范圍內(nèi)的照片數(shù)據(jù)。文中共獲取28 745條Geo-tagged照片數(shù)據(jù)，每張照片信息包括照片ID、用戶ID、拍攝時(shí)間、GPS坐標(biāo)和文本標(biāo)簽信息，如表3所示。

表3 Geo-tagged照片數(shù)據(jù)

2.1 基于Geo-tagged照片數(shù)據(jù)的聚類和命名

DBSCAN的兩個(gè)參數(shù)Eps和MinPts決定聚類規(guī)模和類簇個(gè)數(shù)，參數(shù)的取值直接影響整個(gè)算法的性能。文中對(duì)比了不同Eps和MinPts下的聚類結(jié)果，見圖1。

經(jīng)不同參數(shù)下的聚類效果對(duì)比，當(dāng)Eps=0.5時(shí)，聚類數(shù)達(dá)到最大值；聚類數(shù)隨著MinPts的增大而減少，當(dāng)MinPts=40時(shí)聚類數(shù)達(dá)到最大值，故文中選擇參數(shù)Eps=0.5 km，MinPts=40。

對(duì)比MeanShift聚類算法[14]，bandwidth設(shè)置為500 m，最終得到13個(gè)類簇，且12個(gè)類簇是相同的，說明該算法能夠有效地挖掘旅游興趣點(diǎn)。確定好類簇后，再采用TF-IDF技術(shù)統(tǒng)計(jì)分析文本標(biāo)簽，計(jì)算一個(gè)類簇中所有文本標(biāo)簽的頻率，選擇較高頻率的標(biāo)簽作為候選興趣點(diǎn)名稱。最終得到旅游興趣點(diǎn)及其名稱有鐘鼓樓、城墻、大雁塔、小雁塔、兵馬俑、華清池、陜西歷史博物館、陜西自然博物館、大唐西市、欣集古鎮(zhèn)以及西安北站和咸陽機(jī)場(chǎng)等13個(gè)類簇。同時(shí)各景點(diǎn)所屬類型有：自然風(fēng)光、歷史遺跡、古鎮(zhèn)民俗、博物館、主題公園、宗教場(chǎng)所。

圖1 不同參數(shù)下的聚類結(jié)果

聚類結(jié)果出現(xiàn)了西安北站和咸陽機(jī)場(chǎng)兩個(gè)熱點(diǎn)，雖然不是旅游景點(diǎn)，卻是旅游必去的交通興趣點(diǎn)。通常人們?nèi)ヒ粋€(gè)新地方旅游，都會(huì)在始發(fā)點(diǎn)或終點(diǎn)(一般是火車站或機(jī)場(chǎng))拍照留念，屬于游客的普遍行為，這一結(jié)果說明該算法能夠有效地挖掘旅游興趣點(diǎn)。同時(shí)，由于西安某些旅游景點(diǎn)距離太近，文中將它們歸為一個(gè)景點(diǎn)，如鐘鼓樓、回民街等。

2.2 構(gòu)建用戶偏好模型

通過以上挖掘出的旅游熱點(diǎn)區(qū)域，統(tǒng)計(jì)每個(gè)游客游玩過的景點(diǎn)，并計(jì)算出游客對(duì)旅游景點(diǎn)的偏好度ruli。文中偏好度由兩部分組成，即游玩次數(shù)(從開始游玩拍照時(shí)間起，每隔8小時(shí)為一次訪問)和該景點(diǎn)照片比例，具體公式如下：

其中，freuli表示用戶u游玩景點(diǎn)li的頻次；nuli表示用戶u在景點(diǎn)li拍攝的照片數(shù)量。

考慮到每個(gè)人上傳照片數(shù)量的習(xí)慣不同，照片比例采用用戶在該景點(diǎn)的照片數(shù)量與用戶照片總量的比值，避免因個(gè)人習(xí)慣不同造成的誤差。

2.3 改進(jìn)的基于項(xiàng)目協(xié)同過濾算法及其在旅游推薦中的應(yīng)用

為了驗(yàn)證文中改進(jìn)算法的高效性，采用經(jīng)典的平均絕對(duì)偏差(Mean Absolute Error，MAE)[15]為評(píng)價(jià)指標(biāo)，通過計(jì)算預(yù)測(cè)的用戶評(píng)分與實(shí)際的用戶評(píng)分之間的誤差來度量。

首先計(jì)算用戶u的平均絕對(duì)誤差(MAUE)，公式如下：

其中，R(u)為推薦項(xiàng)目集；T(u)為測(cè)試集中用戶u的評(píng)分集。

然后計(jì)算出所有待推薦用戶的MAUE，最終得到系統(tǒng)的MAE，如下所示：

MAE越小，預(yù)測(cè)值與實(shí)際值之間的差異越小，說明推薦系統(tǒng)的精度越高。

文中對(duì)比傳統(tǒng)的基于項(xiàng)目的協(xié)同過濾(itemCF)和改進(jìn)的歸一化綜合項(xiàng)目相似度的協(xié)同過濾(improved_itemCF)，結(jié)果如圖2所示。

圖2 算法性能對(duì)比圖

從圖2中可以看出，隨著項(xiàng)目近鄰數(shù)目不斷增大，MAE值越來越小，最后趨于穩(wěn)定，說明增加相似項(xiàng)目個(gè)數(shù)可以在一定程度上降低MAE，且文中改進(jìn)算法的平均絕對(duì)誤差始終是最低，說明該算法能夠得到較好的推薦精度。

2.4 構(gòu)建用戶信任網(wǎng)絡(luò)

據(jù)美國某機(jī)構(gòu)調(diào)研分析，發(fā)現(xiàn)90%的人們選擇信任朋友的推薦意見[10]。也就是說，用戶之間的信任度在一定程度上影響用戶旅游線路的選擇。社會(huì)化網(wǎng)絡(luò)的推薦很好地模擬了現(xiàn)實(shí)社會(huì)中的推薦。故文中通過構(gòu)建游客信任網(wǎng)絡(luò)，了解游客之間的信任度，進(jìn)而用于加權(quán)影響景點(diǎn)推薦值。

首先通過構(gòu)建用戶—用戶社交矩陣，利用PageRank算法分析每個(gè)用戶的PageRank值，即權(quán)威度，然后利用權(quán)威度計(jì)算用戶之間的信任度，如下所示：

其中，用戶uj是ua的好友，ua的所有好友為{u1,u2,ub,…,uj,…,un}；PR(uj)是用戶uj的PageRank值。

用戶對(duì)景點(diǎn)的信任度轉(zhuǎn)換成用戶對(duì)游玩過該景點(diǎn)的游客的信任度的均值。假設(shè)系統(tǒng)為用戶ua推薦景點(diǎn)i，而去過景點(diǎn)i的用戶有Ui={u1,u2,…,uk}，則

3 結(jié)束語

文中首先使用Flickr網(wǎng)站的Geo-tagged照片數(shù)據(jù)集，并用基于密度的DBSCAN聚類算法對(duì)照片的經(jīng)緯度進(jìn)行聚類，獲取Flickr游客在西安的旅游興趣點(diǎn)集合，同時(shí)對(duì)比MeanShift聚類算法進(jìn)一步驗(yàn)證文中聚類算法的有效性；然后綜合考慮用戶偏好和興趣點(diǎn)屬性等因素，利用改進(jìn)的基于項(xiàng)目的協(xié)同過濾推薦算法為用戶提供旅游推薦服務(wù)；最后構(gòu)建用戶信任網(wǎng)絡(luò)。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效提高系統(tǒng)的推薦精度和滿意度。

在未來的研究中，將盡可能獲取更多的西安旅游數(shù)據(jù)，挖掘出更多的旅游興趣點(diǎn)，同時(shí)為了給用戶提供更加個(gè)性化的旅游推薦服務(wù)，對(duì)推薦算法有待進(jìn)一步改進(jìn)。

[1] 吳春陽,何友全.數(shù)據(jù)挖掘技術(shù)及其在旅游線路規(guī)劃系統(tǒng)的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(9):235-238.

[2] 胥 皇,於志文,封 云,等.基于LBSN的個(gè)性化旅游包推薦系統(tǒng)[J].計(jì)算機(jī)與現(xiàn)代化,2014(1):186-191.

[3] 鄒永貴,萬建斌,夏 英.基于路網(wǎng)的LBSN用戶移動(dòng)軌跡聚類挖掘方法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(8):2410-2414.

[4] 李春明,王亞軍,劉 尹,等.基于地理參考照片的景區(qū)游客時(shí)空行為研究[J].旅游學(xué)刊,2013,28(10):30-36.

[5]KurashimaT,IwataT,IrieG,etal.Travelrouterecommendationusinggeotagsinphotosharingsites[C]//ProcofACMconferenceoninformation&knowledgemanagement.[s.l.]:ACM,2010:579-588.

[6]MajidA,ChenL,ChenG,etal.Acontext-awarepersonalizedtravelrecommendationsystembasedongeotaggedsocialmediadatamining[J].InternationalJournalofGeographicalInformationScience,2013,27(4):1-23.

[7]LuX,WangC,YangJM,etal.Photo2Trip:generatingtravelroutesfromgeo-taggedphotosfortripplanning[C]//Procofinternationalconferenceonmultimedia.[s.l.]:[s.n.],2010:143-152.

[8] Cheng A J,Chen Y Y,Huang Y T,et al.Personalized travel recommendation by mining people attributes from community-contributed photos[C]//Proceedings of the 19th international conference on multimedia 2011.Scottsdale,AZ,USA:[s.n.],2011:291-303.

[9] Chen Y Y,Cheng A J,Hsu W H.Travel recommendation by mining people attributes and travel group types from community-contributed photos[J].IEEE Transactions on Multimedia,2013,15(6):1283-1295.

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

[11] Ester M,Kriegel H P,Sander J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proc of 2nd international conference on knowledge discovery and data mining.[s.l.]:[s.n.],1996:226-231.

[12] 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.Hong Kong,China:[s.n.],2001:285-295.

[13] 鄧愛林,朱揚(yáng)勇,施伯樂.基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào),2003,14(9):1621-1628.

[14] Comaniciu D,Meer P.Mean shift:a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.

[15] Willmott C J,Matsuura K.Advantages of the Mean Absolute Error (MAE) over the Root Mean Square Error (RMSE) in assessing average model performance[J].Climate Research,2005,30(1):79-82.

Study on Travel Recommendation Based on Geo-tagged Photos

WANG Nan,CAO Han

(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China)

In the Web2.0 era,with the popularity of smart phones,digital cameras and GPS navigation systems and other portable electronic products widely available and the rapid development of social network,all kinds of UGC (User Generated Content) are emerging by the social networking sites.Meanwhile,more and more tourists tend to share their travel seen and heard on the network with pictures or texts,and those social media data usually contain textual labels,spatial location (in terms of latitude and longitude),taken time and other information,which provide truly reliable data.Therefore,the Geo-tagged photo from Flickr is used as data sources,applying the density-based clustering algorithm DBSCAN to cluster latitude and longitude of photos,and getting Points Of Interest (POIs) in Xi’an with TF-IDF algorithm.The travel recommendation is provided using improved collaborative filtering algorithm,which considers both user preferences and attributes of POI.The results show that it can improve the recommendation accuracy effectively.Finally the trust network for users is built to improve the trust and satisfaction of the recommendation system.

Geo-tagged;DBSCAN;user preferences;collaborative filtering;trust network

2016-01-10

2016-04-14

時(shí)間：2016-09-19

國家自然科學(xué)基金資助項(xiàng)目(41271387)

王 楠(1991-)，女，碩士研究生，研究方向?yàn)榭臻g數(shù)據(jù)挖掘、智慧旅游；曹 菡，教授，研究方向?yàn)椴⑿杏?jì)算與大數(shù)據(jù)處理、空間數(shù)據(jù)挖掘、智慧旅游。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0842.052.html

TP39

A

1673-629X(2016)10-0123-04

10.3969/j.issn.1673-629X.2016.10.027