内嵌时空信息的照片数据中的游览模式探索

徐志明,梁 循,李志宇,齐金山

(中国人民大学 信息学院 信息系,北京 100872)(淮阴师范学院 计算机科学与技术学院,江苏 淮安 223300)

1 引 言

随着多媒体技术和互联网技术的发展,人们开始越来越多地在社交网站上分享自己当前的状态以及发布自己拍摄的照片等信息.与此同时,越来越多的数码产品如数码相机、智能手机等移动设备可以拍摄带有元数据(metadata)的照片,这些照片中除了包含图像信息外,还包含了照片拍摄的时间、地理位置等信息.国外一些网站如Flickr、Panoramio等还为用户提供了地理位置标注、检索、浏览、分类以及分类等功能,这为探索用户行为提供了更多可以使用的数据.

带有地理信息的照片是获得用户所处位置,了解用户行为习惯的一个重要数据来源.研究者利用带有地理位置标签的照片做了很多的研究工作,具体集中在兴趣点发掘和旅游推荐[1-6],照片拍摄地点预测[7,8],用户行为模式分析[9,10]等方面.例如,文献[1]针对地理数据的层次性,分别在全局和局部进行了聚类来找到用户关注的兴趣点并对兴趣点使用关联规则进行挖掘,文献[4]结合了基于主题和协同过滤的方法,在用户参观过的兴趣点较少的情况下仍然可以提取用户特征,在数据稀疏的情况下仍然能较好地推荐.文献[7]对照片拍摄位置以及照片内容之间的关系进行建模,然后使用聚类的方法预测照片的拍摄位置.文献[9]对Flickr用户上传的照片进行分析,探索了游客和当地人,男性和女性等不同群体用户的拍摄习惯.在地理兴趣点挖掘时,主要依靠聚类方法[1,6,11,12].如文献[6]在进行旅游推荐之前,首先应用DBSCAN算法对数据点进行聚类来找到旅游地标,而文献[11]在DBSCAN聚类算法的基础上针对地理应用进行扩展,将用户考虑到聚类中,以此得到更加鲁棒的聚类结果.文献[12]提出使用栅格结构对地理数据进行聚类.

在文献[13]中,作者提出利用带有标签信息的照片挖掘出兴趣点,然后利用这些兴趣点构建用户每天的游览轨迹,接着对这些轨迹进行分析找出一些游览次序上的模式.但是根据从Flickr上下载的照片数据,我们发现一些照片的拍摄时间字段和实际情况不符.下页图1中为三张来自Flickr的由不同用户拍摄的照片,根据Flickr接口提供的数据,这三张照片拍摄时间均在23～24点,但是故宫的最早开放时间是早上8:00,最晚闭馆时间为下午17:00,在该时间段游客是不允许进入并拍照的.而且从照片内容可以看出,这些照片都是在白天拍摄的,所以这些照片中的时间是错误的,不能直接使用照片中带有的确定的时间(如零点)作为分割照片序列的依据.

图1 三位不同用户在“23点”拍摄的照片Fig.1 Three photos taken by three different users after 11 p.m.

虽然Flickr提供了部分用户所在时区,但是该数据可靠性难以保证,我们尝试使用时区信息进行纠正,但是仍然有大量照片的内容和拍摄时间不符.由于实际可获得照片的拍摄时间是有偏差的(我们认为主要是因为用户的拍照设备没有更新时区,所以照片的时间上虽然是有误差的,但是照片拍摄的时间顺序是正确的),所以使用具体的时间(如零点)对户游览的次序进行分割是不合理的.因此应该找到另一个方法对用户拍摄的照片序列进行分段,以获得游客在各次游览活动中拍摄的照片,来更加全面准确地反映游客的游览行为.

图2 2011年1月至2016年9月,6451位用户在北京的“停留时间”分布Fig.2 Distribution of 6451 users′ stay-time from January 2011 to September 2016 in Beijing

图2为从Flickr上获取的,在2011年1月1日至2016年9月30在北京拍摄照片的用户的“停留时间”分布.“停留时间”定义为用户在北京拍摄的最后一张照片与第一张照片的时间差.“停留时间”在一定程度上反映了用户和北京的关系,外地游客更有可能在北京作短时间的停留,所以他们的“停留时间”较短,而北京本地人可以随时在北京进行拍摄照片,他们的“停留时间”就比较长.从图2可以看出,有大约50%的用户在北京的“停留时间”少于24小时,说明了他们只有很短时间停留在北京或者在北京但只有较短时间有拍摄照片的习惯,因此我们认为在这些较短的停留时间段内,用户有计划地进行了一些游览活动.随着停留时间的增加,用户数量呈现出递减的趋势,但是最后仍然有大量的用户的“停留时间”很长,说明他们为北京本地用户,或者他们有多次到北京的游览行为.因此根据“停留时间”可以发现，大部分在北京拍摄照片的用户更多的是游客,而且Flickr的用户中北京用户占比非常小,北京作为国际性大都市,能够吸引来自世界各地的游客,所以在北京拍摄的照片大部分是外地游客拍摄的,在一定程度上体现了游客的游览偏好.

因此,我们提出从游客拍摄的照片数据出发,来挖掘游客的游览偏好并给出部分量化指标.首先使用每个用户照片的拍摄时间间隔对拍摄记录进行分割,在此基础上定义长途旅游记录和短途旅游记录,紧接着将其转化为体现游览顺序的关键径,最后在大量用户关键径的支持下,利用转移频率量化游客的游览偏好.

2 基于关键径的旅游路线挖掘

2.1 总体框架

游客只会在自己感兴趣的区域拍照,很少在自己行进路线上频繁拍照,而且用户选择上传的照片也是自己拍摄照片的子集,所以能够获得的拍摄记录更多反应的是游客喜欢拍照并且把照片上传的位置,以及游览这些点的时间,而不是行进轨迹.所以为了找到通用性的游览轨迹,我们应该把那些反映少数人偏好的拍摄点删除,把剩下的拍摄点划分成不同的兴趣区域,并以游客游览兴趣区域的顺序来表示游览路线.为了更好地表述本文的方法,我们提出以下定义.

定义1.拍摄记录PA=

,i=1,2,3,….拍摄记录为一个用户在特定时间段[t1,t2]拍摄行为的集合.其中pi=(lati,lgti,ti)表示拍摄点,lati和lgti分别为拍摄该照片拍摄的纬度和经度(由于GPS偏差在本文所述模型中影响可以忽略,所以使用照片拍摄时自带的GPS信息作为用户拍摄照片时实际的地理坐标.),ti为用户拍摄照片的时间,满足p1.t=t1,p|PA|.t=t2(|PA|表示取序列的长度),且pi+1.t≥pi.t.由于用户上传的照片只是实际游览时拍摄照片的子集,所以我们能获得的数据也是不完整的.

定义2.最大记录间隔TPA=max(pi+1.t-pi.t),i=1,…,|PA|-1.最大记录间隔用来描述用户拍摄记录PA中相邻的照片的最大拍摄时间间隔.

定义3.当拍摄记录PA满足条件TPA≤Δt,称PA为旅游记录,记为PΔt,代表一个用户在一次活动中拍摄记录集合.例如游客在游览故宫时拍摄照片的记录集合构成了游览拍摄记录,若在此次游览活动中相邻拍摄照片的最大时间差为t′,则有Δt≥t′.对应地,游客在花费几天在北京游玩拍摄记录也构成了一个旅游记录,只是Δt较大.

定义4.长途旅游记录.针对拍摄记录PA,通过把相邻时间间隔小于Δt的元素分为一组即可得到旅游记录序列,记为PP=,i=1,….对于PΔt,i如果有i=1∨(S(PΔt,i)-F(PΔt,i-1)>tmax)并且i=|PP|∨(S(PΔt,i+1)-F(PΔt,i)>tmax)则称它为长途旅游记录.式中∨表示逻辑表达式中的或者,(S(PΔt,i)和F(PΔt,i-1)分别表示取拍摄记录的第一个元素的时间和最后一个元素的时间.长途旅游记录代表了一个游客在在较长时间段之内进行对某地仅进行了一次游览,所以该次游览更可能是有规划的,系统性的游览.

定义5.短途旅游记录.针对拍摄记录PA,通过把相邻时间间隔小于Δt的元素分为一组即可得到旅游记录序列,记为PP=,i=1,….对于PΔt,i如果有i>1∧(S(PΔt,i)-F(PΔt,i-1)

定义6.拍摄兴趣区r.拍摄兴趣区是指游客在这里拍摄了大量照片的区域,用户一般会在景点拍摄大量照片,除此之外,当发生一些较为重要的事件时也会拍摄照片.因为在本文讨论的范围内,拍摄兴趣区均为景点,后文与景点通用.

定义7.关键径v=,i=1,2,3,….关键径是拍摄兴趣区构成的序列,元素之间的顺序体现了游览顺序.由于一般游客只有在一次游览行为中经过一个景点一次,所以令 它表示了一个游客在特定时间段内,访问了哪些拍摄兴趣区以及第一次访问这些区域的时间顺序.

定义8.转移频率:R.转移频率反应了游客在不同拍摄兴趣区之间游览次序的偏好,包含了四个元素:紧邻后向频率RMN,ra,rb,紧邻前向频率RMP,ra,rb,全局后向频率RN,ra,rb和平均全局后向频率RNA,r.

定义8.1.

I(x)表示指示函数,若x代表的表达式为真,该函数返回1,否则返回0.In(r,v)表示取元素r在序列v中从1开始的下标.该指标反映了拍摄兴趣区rb紧挨着ra之后出现的频率,体现了人们在游览ra之后喜欢直接转到哪些地方.

定义8.2.

该指标反映了拍摄兴趣区ra紧挨着rb之前出现的频率,体现了人们在游览rb之前喜欢从哪些地方直接过来.

定义8.3.

该指标反映了拍摄兴趣区ra和rb同时出现时,ra在rb之前出现的频率,从整体上体现了人们在ra和rb之间游览的先后次序偏好.

定义8.4.

关键径的提取整体流程如图3所示.在图3(a),(b),(c)中,每个点表示用户在该位置拍摄了照片,相同灰度的点表示来自同一个拍摄记录(或旅游记录),点之间的箭头表示时间的先后关系.图3(a)中表示了用户拍摄记录的初始数据PA1和PA2,包含拍摄位置以及时间(顺序)信息,数据点之间的连线代表了时间上的先后关系.在图3(b)中,根据Δt对每个用户的拍摄记录进行分割得到旅游记录,由于点p1和p2之间的时间差大于阈值Δt,所以对PA1进行分组,得到两个旅游记录P1和P2,同时由于PA2中时间差均小于Δt,所以由它得到旅游记录P3.在图3(c)中,由于图3(b)中得到的3个旅游记录均为长途旅游记录,所以使用它们的数据点找到拍摄兴趣区ra、rb、rc、rd,如图中虚线框所示.最后,将长途旅游记录经过兴趣区的顺序作为关键径,如图3(d)所示.

图3 关键径生成流程Fig.3 Process of generating key-path

2.2 拍摄兴趣区发现

由于拍摄兴趣区是有多名用户拍摄了大量照片的区域,所以可以使用聚类的方法来找到这些区域,我们使用密度峰值聚类算法(DPC,Clustering by fast search and find of Density Peaks)[14]中来发现关键区域.DPC算法首先计算所有数据点的局部密度,然后将具有较大密度并且和最近更大密度数据点的距离较远的点作为聚类中心,最后把剩下的数据点和它的最近的更大密度点的分成一类.该算法可以忽略异常数据点、使用参数较少(可以不设置聚类个数)并且能够获得不规则的聚类[15,16].DPC聚类的步骤见算法1.

算法1.DPC聚类算法.

输入:待聚类数据点,截断距离dc

输出:每个数据点所属类

1.计算所有数据点对之间的距离

2.根据dc计算所有数据点的局部密度

3.找到所有数据点的最近更大密度点,并保存它们之间的距离

4.确定聚类中心

5.将聚类中心之外的数据点分配到相应的类别中

使用聚类算法的目的是发现反映更多游客偏好的拍摄兴趣区,而不是将这些拍摄记录分为几类,所以我们对原始的DPC聚类算法进行了相应的调整.一是使用栅格消除单个用户在一次游览中在相近位置拍摄大量照片对数据点局部密度的影响,二是使用平均密度来排除边缘点,找到具有较高密度的拍摄兴趣区.

为了加快数据的处理速度以及反映更多游客的偏好,我们利用选定范围内的经纬度坐标将拍摄点进行栅格化处理,栅格的权重定义为:

wbi=∑F(bi,PΔt)

(1)

公式(1)中栅格的权重表示在该栅格有拍摄行为的一次游览记录.与之前学者[11]的方法略有不同,我们在栅格化时消除单个用户在相近位置拍摄大量照片对数据点密度造成的影响.考虑到一个用户可能有多次游览,而每次游览都代表这该地区的吸引力,所以没有使用在栅格中有拍摄记录的用户的数量作为栅格的权重,而是使用不同的PΔt.

对数据进行栅格化之后,使用公式(1)计算栅格的权重,然后将栅格作为待聚类的数据点,数据点的位置使用栅格所在的行和列的坐标来表示.设新的数据点集为S={bi},i=1,2,3,…,其中bi=(xi,yi,wi),栅格间的距离定义为:

(2)

数据点bi的局部密度ρi可以被被定义为:

(3)

式(3)表示ρi等于与数据点bi的距离小于dc(截断距离)的点的权重之和,截断距离dc需要事先确定.在求得所有数据点的局部密度之后,下一步就是确定数据点bi和最近的具有更高密度的数据点之间的距离,该距离δi的定义为:

(4)

当bi是密度最大的数据点时,

(5)

紧接着使用ρi和δi的乘积的前k大的数据点作为聚类中心.在确定了聚类中心之后,下一步就是将聚类中心之外的数据点划分到相应的类中.仍然是按照ρ降序的方式访问数据点,将它们划分所属的类中.

原始的DPC聚类算法会将数据点划分到相应的类中,但是现在需要找到密度较高拍摄兴趣区,拍摄兴趣区的特点是具有较高的密度,并且数据点之间的距离较近.所以在划分数据点所属类时,使用边界距离db和密度系数α来判断该数据点是否应该加到相应的类中.

算法2.确定聚类中心之外数据点所属类.

输入:已确定聚类中心数据点的聚类编号列表cluster,数据点的局部密度density,按局部密度排序对应的下标sort_index,与各个数据点距离最近的具有更高(或相等)的局部密度的数据点near_index

输出:所有数据点聚类编号

1. FOR i=1:n

2. IF -1 (cluster[i]

3. count[cluster[i]]=1

4. sum[cluster[i]]=local_density[i]

5. END IF

6. END FOR

7. FOR i=1:n

8. curi=sort_index[i]

9. IF -1=cluster[curi]&& -1 ( near_index[curi]

10. hCluster=cluster[near_index[curi]]

11. IF density[curi]>(Q*sum[hCluster]/count[hCluster]) && near_index[curi]>DISTANCE

12. cluster[curi]=hCluster

13. count[hCluster]=count[hCluster] + 1

14. sum[hCluster]=sum[hCluster] + density[curi]

15. END IF

16. END IF

17. END FOR

2.3 关键径

在找到拍摄兴趣区之后,下一步就可以将用户的拍照记录映射到拍摄兴趣区中,生成关键径，按照时间顺序访问用户的每一个拍摄记录,判断拍摄位置是否在一个拍摄兴趣区内,如果是则表示该用户在此时刻在游览该区域,并且如果该用户之前未访问过该拍摄兴趣区,则在关键径添加该点,如果不是则跳过该记录.最后即可得到该用户游览的关键径.

关键径反映了游客选择游览哪些拍摄兴趣区,以及以什么样是顺序进行游览,这体现了用户的选择与偏好,也包含了一些规划,如游客偏向于最后的游览位置靠近出口.所以,游览历史体现了人们对于该景点各个子区域的游览的规划,通过对所有人的路径进行分析,可以找到受到最多人欢迎的游览顺序.

为了从所有用户的关键径中挖掘出共有的游览模式,需要度量不同关键径之间的距离,在这里我们首先使用LCS(Longest Common Subsequence)算法来计算两个关键径之间的最大公共路径长度L(P,Q),然后定义它们之间的相似性为:

(6)

根据经验可知,长度短的关键径数量较多,更容易获得更高的密度,长度较长的关键路径数量较少,且更难发现距离近的其他数据点,所以不容易设定确定聚类中心的密度阈值,这里仍然使用DPC聚类算法,然后根据决策图来确定聚类数量,然后从聚类结果中找到有价值的游览模式.

3 实验及分析

3.1 数据获取

由于Flickr网站上有大量带有GPS信息的照片,并且Flickr提供了下载相关数据的API( https://www.flickr.com/services/apps/create/),所以我们从Flickr上下载实验数据.我们主要使用flickr.photos.search接口来获得需要的照片,该方法的参数主要包含照片的生成时间范围,以及照片的拍摄地点.我们使用的参数如表1所示.由于该接口对一次检索的照片数量有限制,所以们按月份依次获取在该范围内的照片,最后对所有的数据进行汇总.

表1 使用Flickr获取照片时使用的主要参数
Table 1 Parameters used when fetching photos with Flickr API

参数值描述minimum＿longitude115．7照片拍摄范围的最小经度minimum＿latitude39．4照片拍摄范围的最小纬度maximum＿longitude117．4照片拍摄范围的最大经度maximum＿latitude41．6照片拍摄范围的最大纬度min＿taken＿date11/1/1照片拍摄最早时间max＿taken＿date16/9/30照片拍摄最晚时间

在Flickr上传照片时,如果照片的exif信息中含有拍摄时间信息,则该网站会把该时间作为照片的拍摄时间,否则会把该照片的上传时间作为拍摄时间,所以在获得了照片数据之后,把照片信息中的“taken unknown”字段为1的照片删除,以获得带有正确拍摄时间的照片.

然后根据这些照片带有的用户ID获取用户的个人信息.根据用户自己设置的所在地信息,从2011年1月1日到2016年9月30来北京参观的游客的统计见图4.图4中除最右侧的直方图为来自中国的用户外,其他为各个大洲在每年来北京的游客数量(亚洲为除去中国人后剩余的数量).从图中可以发现,发达地区每年来北京旅游的游客数量普遍高于欠发达地区.

图4 2011年1月至2016年9月到北京旅游的游客分布Fig.4 Distribution of users visited Beijing from January 2011 to September 2016

我们分别利用1月到12月拍摄的照片进行聚类,并设定聚类个数为10,总共得到16个拍摄兴趣区.在对每一个月份的数据进行聚类时,根据聚类中心的排名对聚类对应的景点进行打分,从第1名到第10名的分数递减,没有出现在该月聚类结果中的兴趣区得分为0.这16个景点在各个月份的得分情况如图5所示,图中横坐标表示12个月份,纵坐标为16个兴趣区,图中点的面积越大代表该景点在该月的排名越靠前.

图5 16个兴趣区在12个月中的排名Fig.5 Clustering results of 16 regions of interests in 12 months

从图5中可以发现,故宫、天安门广场和天坛公园作为北京的标志性景点,常年是最受欢迎热门景点之一,但是受到农历春节的影响,天安门广场和天坛公园的影响力减弱,王府井的影响力增加.三里屯太古里作为一个综合休闲娱乐区也能在一年中保持非常高的吸引力.颐和园是一座园林式景点,它的受欢迎程度受到了季节的影响,从3月到10月份的受欢迎程度高于冬天的几个月份.

3.2 轨迹切割时间Δt的确定

为了确定合适的轨迹切割时间,我们分别令Δt为12h、24h、48h、72h和96h进行实验,统计不同的Δt对每个用户切割得到的轨迹的数量,对应的结果如图6所示.横坐标代表切割所得的旅游记录数量,纵坐标表示对应该数量的用户数.从图中可以发现随着Δt的减小,旅游记录数量为1的用户数量逐渐减少,这主要是因为使用较短的Δt可会把一些使用较大Δt切割所获得的结果再次进行切割,从而体现为分段数量较多的用户数增加,图中旅游记录数量2-8段的曲线反映了该结果.从图6中还可以发现当Δt为72h时只含有一个轨迹用户的数目达到了一个平衡,我们认为72h是一个较为合理的切割时间.

图6 不同的时间阈值Δt对用户旅游记录的影响Fig.6 Effect of Δt on the number of trip records of each user

一般本地用户在北京进行拍摄活动会非常方便,所以在几年间容易有较多拍摄记录,而且这些记录相隔时间容易大于一个时间阈值T(假设为7天),所以他们更容易有较多的轨迹.而外地游客一般在一段时间内只来北京一次,如果在该地有较多的轨迹,那么这些轨迹的时间间隔应该较大,一般可以达到几个月,所以使用轨迹数量为1的数量的稳定性可以反映是否是有计划游览的.对于来北京出差的用户来说,旅游只是在闲暇时间的活动,所以可能有较大的最大记录间隔TPA.另外由于所获得数据是户游览拍摄照片的子集,时间间隔也会因用户的选择而扩大.

图7 长途旅游和短途旅游记录Fig.7 Short-trips and long-trips

在使用72h作为分割时间获得了所有的旅游记录后,接着使用6个月作为Tmax来分别获取长途旅游记录和短途旅游记录.使用Google Earth软件分别将短途旅游记录和长途旅游记录中连续的拍摄点连线并在地图上标出,得到如图7所示的结果.从图中可以看出著名景点体现出了很强的吸引力,有大量的用户在那里拍摄了照片,其次可以发现在短途旅游记录中拍摄的照片大多分散在北京城区而长途旅游记录中的照片明显具有很强的集中性(景点),以及在景点之间进行转移.因此不同类型的旅游记录形态体现了分类方法的有效性.

3.3 关键径

为了获得关键径,首先使用5333组长途旅游记录中的数据点进行聚类,得到20个拍摄兴趣区,然后把“穿过”拍摄兴趣区的旅游记录的数量少于150的区域删除,得到了如下聚类结果:天坛公园、鸟巢、王府井、慕田峪长城、天安门广场、三里屯、颐和园、雍和宫、故宫、国际机场、景山公园、后海,可以发现所有拍摄兴趣区除了国际机场外均为较为著名的景点.首都国际机场是中国最繁忙的国际空港,相比于其他典型景点,能吸引游客在此拍照的主要原因一是它的现代化的设施与建筑,另一个原因我们认为是它更像是一个游览的预备点,是在北京进行游览的起始点.

接着即可得到代表游览这些景点次序的关键径,关键径的节点数目和对应的数量关系如表2所示.从表2中可以发现有3274(61.39%)条关键径的节点数目为0(表示未“穿过”任何拍摄兴趣区),而在剩下的节点数目不为0的关键径中,大部分关键径节点数目为1,占比为62.17%.另外,可以发现随着关键径节点数量的增加,对应的关键径的数量也是逐渐减少的,最长的关键径长度为10,数量为2.

表2 关键径节点数量与关键径数量关系
Table 2 Number of key-paths with different length

长度012345>5数量327412803481891126763

将紧邻后向频率超过0.2的转移在图中标识出来的结果见图8.兴趣区后括号中的数字为访问次数,兴趣区之间的有向连线表示兴趣区访问先后次序.例如从天安门指向故宫的标有0.71的箭头表示离开天安门后直接去故宫的频率为0.71.从图中可以看出,其他大部分景点到故宫的紧邻后向频率均超过了0.2,体现了故宫相对其他景点的吸引力较强.另一个显著的特点是紧邻后向频率超过0.25的均发生在距离较近的景点之间,体现了游客偏向于游览一个景点后去距离较近的另一个景点.从天安门广场到故宫的转移频率达到了0.71,这与广场距离故宫的距离非常近有关.而且由于故宫的游览方向是确定的,游客必须从午门(南门)进入,从神武门(北门)离开,所以游客更有可能先参观天安门广场然后从南门进入故宫,从而减少路途上的时间.

将所有紧邻前向频率大于0.2的兴趣区对标出,结果如图9所示.兴趣区后括号中的数字为访问次数,兴趣区之间的有向连线表示访问先后次序.例如从故宫指向颐和园的标有0.31的箭头表示在游览颐和园之前有比例为0.31的用户参观了故宫.从图中可以发现所有兴趣区和故宫的紧邻前向频率均超过了0.2,表明了对所有其他兴趣区而言,有相当大的比例游客刚去过故宫,故宫像一个“兴趣核心”,辐射到其它兴趣区.

图9 所有兴趣区之间不小于0.2的紧邻前向频率Fig.9 Regions of Interest with previous visit frequency no less than 0.2

将全局后向频率超过0.7的兴趣区对在图中标出,得到如图10所示的结果,每个兴趣区括号中的数字为平均全局转移概率.箭头的指向表示兴趣区排列的先后关系.例如从天安门广场指向故宫标有0.78的箭头表示在天安门广场和故宫同时出现的关键径中,天安门广场排在故宫前面的频率为0.78(故宫排在天安门广场后面的频率为0.22).从整体上来看,平均全局后向频率超过0.6的只有故宫和天安门广场,表明这两个景点是游客最早参观的,同时天安门广场的0.66大于故宫的0.60也与之前的游客先去天安门广场再去故宫相互呼应.平均全局后向频率最低的是慕田峪长城和鸟巢,说明游客偏向于最后再去这两个地方.

图10 所有兴趣区之间不小于0.7的全局后向频率Fig.10 Regions of Interest with average global next visit frequency no less than 0.7

通过观察全局后向频率超过0.7的兴趣区可以发现,由天安门广场指出的箭头最多,说明这里更普遍地被作为游览的起点.由天安门广场出发,经(故宫、)颐和园、三里屯和雍和宫形成了一个较长的游览路径,在这条路径中颐和园(0.46)和三里屯(0.51)的平均全局后向频率较低,但是仍然有相对于其他兴趣区(分别对应三里屯和雍和宫)有较强的优先性.从图还可以发现,存在由国际机场在前的全局后向频率达到0.7,同时也存在国际机场在后的全局后向频率达到0.7.表明部分游客从国际机场出发,进行游览,最后也有很多游客从国际机场离开.这种情形导致了国际机场的平均全局后向频率趋近于0.5.这体现了国际机场对来北京旅游的游客的重要性.

上文的分析只能找到任意两个兴趣点对之间的游览先后次序关系,并不能从整体上发现常见的游览模式.所以接下来通过对所有的关键径聚类的方法找到频繁出现的游览行为.通过之前的实验可以发现,故宫和天安门广场作为最热门的景点,共同出现的频率很高,而且由于两者在地理位置上也比较近,所以在接下来的实验中我们将天安门广场作为故宫的一部分.然后选取所有长度不小于3的关键径进行聚类,选取排名前5的聚类中心,它们分别是:(故宫->鸟巢->天坛公园)、(故宫->天坛公园->鸟巢)、(故宫->后海->天坛公园)、(故宫->天坛公园->后海)、(故宫->天坛公园->慕田峪长城),可以发现所有的关键径都以故宫为起点,并且包含天坛公园,说明了游客大多是以故宫作为游览的起点.它们之间的区别主要是第三个景点是哪里,以及以什么样的顺序对它们进行游览.

最后将发现概括如下:

1)故宫作为北京“超级景点”,更容易作为在北京游览的起点,同时也吸引着来自其他景点的游客.

2)游客偏向于在游览了一个景点之后去更近的下一个景点,特别是能明显节省旅游时间时.

3)对于通过乘坐飞机这一交通方式来北京旅游的游客来说,首都国际机场能吸引游客在此拍照,体现了不同交通方式对游客拍摄行为的影响.

4 总 结

本文提出一种对连续拍摄照片的时间分割准则,并基于密度峰值聚类(DPC)的方法定义拍摄兴趣区和游览路径,接着还定义了紧邻后向频率,紧邻前向频率,全局后向频率和平均全局后向频率.基于在北京地区拍摄的20万张照片的时空信息,使用提出的方法对游客游览北京的模式进行了分析,验证了方法的有效性.本文所做的工作仍然处于初级阶段,找到更加精准地描述游览行为的模型需要付出更多的努力.

[1] Ickjai Lee,Cai Guo-chen,Kyungmi Lee.Exploration of geo-tagged photos through data mining approaches[J].Expert Systems with Applications,2014,41(2):397-405.

[2] Imran Memon,Chen Ling,Abdul Majid,et al.Travel recommendation using geo-tagged photos in social media for tourist[J].Wireless Personal Communications,2015,80(4):1347-1362.

[3] Peng Pai,Shou Li-dan,Chen Ke,et al.The knowing camera:recognizing places-of-interest in smartphone photos[J].Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval,ACM,2013:969-972.

[4] Jiang Shu-hui,Qian Xue-ming,Shen Jia-lie,et al.Author topic model-based collaborative filtering for personalized POI recommendations[J].IEEE Transactions on Multimedia,2015,17(6):907-918.

[5] Kwan Hui Lim.Recommending tours and places-of-interest based on user interests from geo-tagged photos[C].Proceedings of the 2015 ACM SIGMOD on PhD Symposium,ACM,2015:33-38.

[6] Sun Ye-ran,Fan Hong-chao,Mohamed Bakillah,et al.Road-based travel recommendation using geo-tagged images[J].Computers,Environment and Urban Systems,2015,53:110-122.

[7] Li Li-jia,Rahul Kumar Jha,Bart Thomee,et al.Where the photos were taken:location prediction by learning from flickr photos[M].Large-Scale Visual Geo-Localization.Springer International Publishing,2016:41-58.

[8] Andrew Gallagher,Dhiraj Joshi,Yu Jie,et al.Geo-location inference from image content and user tags[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops,IEEE,2009:55-62.

[9] Cao Yan-peng,Kay O′Halloran.Learning human photo shooting patterns from large-scale community photo collections[J].Multimedia Tools and Applications,2015,74(24):11499-11516.

[10] Su Shi-liang,Wan Chen,Hu Yi-xuan,et al.Characterizing geographical preferences of international tourists and the local influential factors in China using geo-tagged photos on social media[J].Applied Geography,2016,73:26-37.

[11] Slava Kisilevich,Florian Mansmann,Daniel Keim.P-DBSCAN:a density based clustering algorithm for exploration and analysis of attractive areas using collections of geo-tagged photos[C].Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application,ACM,2010:38.

[12] Zhao Qin-pei,Shi Yang,Liu Qin,et al.A grid-growing clustering algorithm for geo-spatial data[J].Pattern Recognition Letters,2015,53:77-84.

[13] Zheng Yan-tao,Zha Zheng-jun,Tat-Seng Chua.Mining travel patterns from geotagged photos[J].ACM Transactions on Intelligent Systems and Technology (TIST),2012,3(3):1-18.

[14] Alex Rodriguez,Alessandro Laio.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):492-1496.

[15] Nurjahan Begum,Liudmila Ulanova,Wang Jun,et al.Accelerating dynamic time warping clustering with a novel admissible pruning strategy[C].Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM,2015:49-58.

[16] Zhang Yang,Xia Yun-qing,Liu Yi,et al.Clustering sentences with density peaks for multi-document summarization[C].Proceedings of Human Language Technologies:the 2015 Annual Conference of the North American Chapter of the ACL,2015:1262-1267.