基于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