简单的基于地理图片的旅行路线还原

在学校时关注基于地理信息的数据挖掘已久，毕业后几无涉足。本文小结当时的一些工作——基于带地理信息的图片的旅行路线还原，也就是通过人们分享的少量图片，还原出用户旅行时的完整的旅行路线。主要方法是先基于HMM的Viterbi算法，解码出用户旅行时的景点路线，之后通过景点间选取均值的方法，还原出用户完整的旅行路线。内容比较实用有趣，感兴趣的同学可以更多探索。

    随着信息技术的发展和人们生活水平的提高，使得旅游业爆炸式发展，个性化的和自助式的旅游越来越得到人们的欢迎，在线旅游服务(Online Travel Service, OTS)也已经成为旅游业发展的一个趋势，在发达国家，OTC占整个旅游收益的40%左右，国内也超过5%，而且正以非常迅猛的速度增长。然而OTC本应是食、住、行、游、购、娱等的组合体，目前OTC企业(如Expedia，Qunar等)都着重于“住”和“行”之上的在线旅游预订方面，虽然仍然提供浅显的旅行攻略与检索，但是均无法与位置结合，也难以满足个性化的需求，均十分缺少创新的内容。

    在另一方面，由于GPS的发展和普及，特别是GPS在各种手持终端(如手机、PDA、数码相机等)上的应用，业界通过UGC的方法获取大量蕴含地理信息共享资源，例如Google latitude和Foooooot上共享的GPS路线，Flickr、Panoramio等的带GPS信息的图片。在Geo图片共享方面，Geo图片与地理位置的结合既能便于平台的数据维护，也有益于增强用户体验，导致各大网站上的Geo图片增长速度非常快，其Geo图片量都数以亿计，同时也给这些图片共享网站带来了新的活力，对于Qzone、Weibo和Facebook上更为便捷的图片分享，其量更难以估量。由于Geo图片所携带的Geo信息都是摄影者的拍照构图时所选的位置，而且共享到网站上的图片大都经过了人们的筛选，这样，可以认为这些共享的图片Geo信息均为生活或旅行中的兴趣点(Interest of Point, POI)，图1中左图为人们在Flickr上共享的位于北京市的24多万张Geo图片(2008年至2010年)的Geo点位图，图1中右图为Flickr上共享的位于颐和园内的10498张Geo图片(2008年到2011年)的Geo点位图，可以非常清晰地看出：绝大部分图片都是在旅游景区中拍摄的，在具体的景区中，图片又朝热门景点集聚。

    本文正是根据这些Geo图片，还原用户完整的旅行路线的。

图1. 北京市内的Geo图片和颐和园内的Geo图片的位置图

1 景点聚类

1.1数据清洗

    在Flickr上，为了更好地组织数据结构，都建议用户共享带Geo信息的图片，但图片中的Geo信息都是由硬件设备(如嵌GPS芯片的智能手机和数据相机)带来的，对于本身不带Geo信息的图片，官方提供地图接口，可以自定义地理位置。而对于用户来说，自定义地理标注能使其图片更容易被搜索，也能提高交互的感觉，因而大多数用户都愿意标注地理信息。然而，这些自标注的Geo信息并不满足旅行路线还原的精度，严重影响实验结果。人们在标注地理信息时，大都是将同一相册中的大量图片标注在同一个地点上，因而我们可以根据相册图片的地理坐标含信息量的多少进行判断。信息论中的“信息熵”能表示变量不确定性的大小，如下公式所示，随机变量P(x)越离散，信息商H(X)将越大，进一步可将H(X)归一化成U(X)。通过一定的阈值控制，可对自标注图片进行筛选。

1.2景点聚类

    绝大部分图片都是随人的主观意志拍摄的，虽然人们存在喜好不同，但都有对美的追求，景区中的好的景致(景点)总能吸引到大家的驻足留影，对于平淡的景致，自然游客就十分稀寥，留下的图片也就少了。而且某处照片的多少，用户的多少都能比较好地反映人们对此景点的兴趣度。从图1中，可以明显地看出颐和园内游客基本上聚在东北宫廷建筑区域，在广阔的耕织园区和苏堤之上，游客比较稀少，同时也可以看出，图片明显地聚集于各景点。

图2. 颐和园内的景点聚类图

    密度聚类算法(Density-Based Spatial Clustering of Applacations with Noise, DBSCAN)能把具有足够高密度的Geo点的区域划分出来，并可以在带有噪声的空间数据集中发现任意形状的聚类，因而DBSCAN十分契合从景区Geo图片中抽取景点。同时不同的密度参数，可以抽取出不同粒度的景点(或景区)。图2中的黄点便是通过DBSCAN在颐和园内聚类出的景点信息。

2 路线还原 

2.1景点路线识别

    HMM是一种用于描述随机过程统计特性的概率模型。它是一个双重随机过程，即由马尔可夫链和一般随机过程两个部分组成。其中马尔可夫链用来描述状态的迁移，用迁移概率描述；一般随机过程用来描述状态与观察序列间的关系，用观察值概率描述。其形式化定义是：HMM是一个五元组 μ=(S, K, P, A, B) ，其中 S是状态的集合，K是输出字符的集合，P是初始状态的概率，A是状态转移的概率。B是输出字符的概率分布。

    在此，将聚类出的景点当成隐含状态S，K为Geo图片点，B可通过Geo点距离景点中心远近刻画，(P、A不述)，通过HMM的Viterbi算法，便可以由用户的Geo图片序列——观测序列，解码出用户旅行时的景点序列。

图3. 景点间Mean还原图

2.2 均值还原

    由于用户上传的Geo图片十分有限，从而通过HMM的Viterbi算法得出的景点路线序列也是十分粗糙。Mean值能反映整体样本的倾向特征，体现某一样本空间中期望的取值。其算法思想如图3所示，在Sight A和Sight B间进行旅行路线还原，先求AB为直径的圆内的所有Geo点的Mean值(以AB为直径圆可以理解为给定起始位置后，人们的主要活动范围)，如果满足阈值条件，路线还原结束，否则将此Mean值点当成还原点C，这样在图3中将路线AB拟合成ACB，再将ACB拟合成ADCEB，显然，通过拟合后，路线更加平滑，由Mean值的物理意义，可以知道，还原后的路线正是大众路线的方向。

    图4为颐和园内某用户的旅行路线还原图，旗帜外为该用户共享Geo的图片点，共7张Geo图片，通过景点还原，还原出的路线如绿线所示，通过Mean值还原，路线如红线所示。景点路线能赋予旅行路线更多的意义，均值还原的路线可以使路线更符合用户的感观。

图4. 颐和园内某用户旅行路线还原图

3 实验分析

    对于提出的基于Geo图片的路线还原方法，最难的在于方法评估，客观数据中，基本不存在既有人们旅行时的完整旅行Gps路线记录，同时又拍摄对应的Geo图片分享的数据，从而十分难以衡量路线还原方法的好坏。在此通过对个人GPS轨迹进行关键区域(Significant Region, SR)识别，用以模拟Geo图片，用于分析评估路线还原方法。

    在旅行时，人们在SR处，例如景致美观的地方，人们行走的速率将会减小，甚至停下来观赏，在某些景点处，人们甚至会回环着观赏，因而SR的识别中，速率v的变化和角度q的变化将是十分重要的，在此引入长角率(Length Angle Ratio, LAR)来衡量SR与v和q的关系，LAR的定义如下公式所示，这样，LAR值越大，说明此处越重要，通过对LAR进行域值限定，便可得到重要区域路线(Significant Region Route, SRR)，如图5所示，便为一条GPS轨迹的SR识别过程，左图为完整的GPS轨迹，右图为通过LAR计算后，满足阈值的LAR点组成的SRR。对于Geo点，大都是人们停下来时拍摄的，其中还伴随着人们对图片选景、角度等的斟酌和焦距、曝光度等的调节，因而如果同时记录下了完整的GPS轨迹时，绝大部分Geo点的LAR值都十分大，当将LAR阈值设定足够大时，识别出来的SRR完全可以当成是一个用户的Geo图片序列S，而且对SRR应用我们提出的路线还原方法的，得到的还原路线与原GPS路线进行比较，便可以判断还原路线的好坏。

图5. 个人GPS的SRR识别

    在实验评测中，将由比较SRR还原出来的路线和原GPS路线，通过刻画两者的相似关系来对衡量方法的好坏。

    由图6左图所示，Router1和Route2为地理空间中的两条轨迹，直观地说，如果Route1和Route2的之间的面积越小(也就是图中阴影部分面积越小)，Route1和Route2越相似。在图6右图中给出了相似度(Sim)的定义，图中绿线为GPS路线，红线为还原路线，Sim定义为1-（路线间的面积和AB圆域面积的比值），也就是如图中阴影部分的面积比上以AB为直径的圆域面积，这样Sim越大，两路线越相似。通过对41条完整的GPS轨迹进行实验测试，最后的平均相似度达82.3%。

图6. 路线相似度比较  

----------------------