王 楠，曹 菡

(陜西師范大學 計算機科學學院，陜西 西安 710119)

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

王 楠，曹 菡

(陜西師范大學 計算機科學學院，陜西 西安 710119)

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

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

0 引 言

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

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

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

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

1 研究方法概述

1.1 基于密度的DBSCAN算法

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

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

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

1.2 改進的基于項目的協(xié)同過濾算法

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

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

(1)計算項目相似度。

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

pearson_sim(i,j)=

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

表1 用戶偏好矩陣

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

項目屬性矩陣如表2所示，項目有k個屬性。

表2 項目屬性矩陣

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

(2)找出項目的k近鄰，預測用戶的未評分項目，進而推薦。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了驗證文中改進算法的高效性，采用經(jīng)典的平均絕對偏差(Mean Absolute Error，MAE)[15]為評價指標，通過計算預測的用戶評分與實際的用戶評分之間的誤差來度量。

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

其中，R(u)為推薦項目集；T(u)為測試集中用戶u的評分集。

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

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

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

圖2 算法性能對比圖

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

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

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

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

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

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

3 結(jié)束語

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

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

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

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

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

[4] 李春明,王亞軍,劉 尹,等.基于地理參考照片的景區(qū)游客時空行為研究[J].旅游學刊,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] 項 亮.推薦系統(tǒng)實踐[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] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協(xié)同過濾推薦算法[J].軟件學報,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

時間：2016-09-19

國家自然科學基金資助項目(41271387)

王 楠(1991-)，女，碩士研究生，研究方向為空間數(shù)據(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