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

王 楠，曹 菡

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

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

王 楠，曹 菡

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

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

Geo-tagged；DBSCAN;用戶偏好；協同過濾；信任網絡

0 引 言

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

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

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

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

1 研究方法概述

1.1 基于密度的DBSCAN算法

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

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

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

1.2 改進的基于項目的協同過濾算法

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

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

(1)計算項目相似度。

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

pearson_sim(i,j)=

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

表1 用戶偏好矩陣

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

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

表2 項目屬性矩陣

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

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

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

2 實驗結果及分析

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

表3 Geo-tagged照片數據

2.1 基于Geo-tagged照片數據的聚類和命名

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

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

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

圖1 不同參數下的聚類結果

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

2.2 構建用戶偏好模型

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

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

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

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

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

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

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

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

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

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

圖2 算法性能對比圖

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

2.4 構建用戶信任網絡

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

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

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

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

3 結束語

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

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

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

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

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

[4] 李春明,王亞軍,劉 尹,等.基于地理參考照片的景區游客時空行為研究[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] 項 亮.推薦系統實踐[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] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[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-)，女，碩士研究生，研究方向為空間數據挖掘、智慧旅游；曹 菡，教授，研究方向為并行計算與大數據處理、空間數據挖掘、智慧旅游。

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