《基于用户轨迹挖掘位置服务》由会员分享，可在线阅读，更多相关《基于用户轨迹挖掘位置服务（11页珍藏版）》请在金锄头文库上搜索。
1、基于基于用户用户轨迹轨迹挖掘的挖掘的智能智能位置服务位置服务 郑宇， 谢幸 Enable Smart Location-Based Services by Mining User Trajectories Yu Zheng, Xing Xie Abstract: The advance of GPS-enabled devices has facilitated people to log their location history with GPS trajectories. These trajectories imply to some extent an individuals be
2、haviors and interests related to their outdoor movements. Therefore, we can understand users and locations as well as the correlation between them based on these trajectories. By mining a users life pattern from their trajectories, we are able to automatically respond to the users unspoken needs. By
3、 mining multiple users trajectories, we can find out the top interesting locations, travel sequences and the travel experts in a given region. This information can enable generic travel recommendation and help people understand an unfamiliar city with minimal effort. By measuring the similarity betw
4、een different users location histories, we could estimate the similarity between users and perform a personalized friend recommendation. Using such user similarity, a personalized location recommendation can be conducted in terms of the location history of a user and that of others. Overall, we can
5、mine from the user trajectories rich knowledge, which may enable many smart location-based services, such as generic travel recommenders and personalized friend & location recommendations. Key Words: location-based services, GPS trajectory, trajectory mining, location history 关键词: 基于位置的服务, GPS轨迹, 轨迹
6、数据挖掘, 用户位置历史 用户轨迹数据的产生用户轨迹数据的产生 随着各种定位技术（如全球定位系统 GPS 和无线蜂窝网）的发展和普及，用户可以很方便 的获取个人位置信息，使用各种基于位置的服务（LBS），并将自己的移动过程以轨迹的 形式记录下来。用户记录这些轨迹的目的有很多，比如， 1） 为了保证车辆的安全和有效调度，以及对交通流量的分析，很多出租、邮政和货运 车辆都配备了 GPS 设备。这些设备以一定的频率向某些特定的管控中心定时发送 自己的坐标。将这些点按时间顺序连接起来就可得到车辆的运行轨迹。 2） 爱好自行车、远足和登山等户外运动的人，通常利用 GPS 设备记录下自己的行程1， 2。一
7、方面，这些线路能保障他们沿原路返回，避免迷路；另一方面，运动结束后， 这些爱好者也可从这些轨迹中提炼出丰富的信息，如本次运动的总里程数、海拔高 度变化、速度和加速度变化以及爬坡难度等。这些信息有助于提高它们的运动水平。 日后，这些轨迹即可成为他们征服某些挑战的见证，也为其他户外运动爱好者提供 了更多的路线选择。 3） 通过将轨迹与旅行过程中拍摄的照片自动关联并在电子地图上显示，用户不仅可以 很直观的再现自己的行程、回忆起所见所闻，也可方便的与朋友分享旅行经历3， 4，5，6。相比枯燥而抽象的文字描述，这些关联了照片的线路可以在短时间内向 他人呈现更直观、更生动的信息（如关键的转向、上车及换乘地
8、点、景点的游览顺 序和停留时间、风景的特色和美丽程度等）。当他人希望去跟随和重复这次旅行时， 这些轨迹又可成为最有效的导游，节约用户规划行程的时间，并在一些关键点上向 给用户给出及时、有效的提示。 轨迹和基于位置的服务轨迹和基于位置的服务 轨迹本身的价值以及其产生的便捷性很快催生了一批基于轨迹的位置服务，如前面提到的 路线分享16，以及车辆调度和安保。但单纯的可视化和轨迹交换并未充分发掘出轨迹中 隐藏的知识。其实，轨迹记录了用户在真实世界的活动，而这些活动将在一定程度上体现 了个人的意图、喜好和行为模式。如某个用户的轨迹经常出现在运动场馆，表明该用户可 能会喜欢体育活动；而经常穿越湖光山色的路
9、线也表征用户对户外活动的喜好。更细粒度 的分析甚至可以根据用户经常光顾的餐馆类别（如川菜馆、湘菜馆）来判别出用户的口味。 因此，如何挖掘轨迹中蕴含的知识就变得尤其重要。 这里的知识可以是从个人数据中挖掘出的用户行为、意图、经验和生活模式712；也 可以是集合多人数据来发现热点地区和经典线路13，甚至理解人和人之间的相关性14， 15，以及人在地域之间的活动模式16，17。如果了解了个人的生活规律，基于位置的服 务就可以在适当的时候给予用户有效的推荐。如分析出用户通常在周末的下午要去超市买 东西，服务提供商就可以在合适的时间智能地将超市的折扣信息发送到该用户的移动终端。 如果掌握了一个城市的热点
10、地区和经典旅行线路，服务提供商就可根据游客当前的位置来 推荐周边的景点，并在游客访问完某个景点后智能地推荐下一个景点和具体的游玩线路。 在“云”计算被人为是大势所趋的今天，只有将所有的个人轨迹汇集和整合到“云”端， 对这些轨迹进行深度的分析和挖掘，完成“数据信息知识智能”的过程，并最终用 这些知识和智能来更好的为“端”服务，才能为用户提供更深层次、更人性化、更有效的 位置服务18。 理解个人历史轨迹理解个人历史轨迹 地图匹配地图匹配 通常情况下，民用 GPS 使用 CA 码传输信号，其所能达到的定位精度一般在 10-20 米之间。 在某些道路稠密的地段，这个误差将使用户的当前位置映射到错误的道
11、路上。这将给用户 的定位和导航带来很大的麻烦。因此，国际上有一系列被称为地图匹配（map matching） 的工作在研究如何将带有位置偏差的 GPS 轨迹映射到正确的道路上。由于其功能的重要性 和基础性，地图匹配也是很多基于轨迹的位置服务中必不可少的模块。 对于高采样率的轨迹，即 GPS 设备以高频率（如每 2 秒一个点）输出定位坐标，目前 已经有很成熟的技术和产品来解决这个问题。大家日常生活中所用的各种 GPS 导航软件都 采用了相应的地图匹配技术。但随着 GPS 移动终端数目的与日俱增，实时获取 GPS 设备位 置信息的通信和存储代价不断加大，对能源的消耗也不断增加。于是，在很多应用里，
12、人 们并不希望 GPS 设备以很高的频率输出定位坐标。比如，北京拥有约 7 万辆出租车，为了 管理和调度这些车辆，每辆车都配备了 GPS 装置。如果每辆车每秒钟都向交通管理部门发 送自己的坐标，一天的产生的数据量就将达到 1 个 TB。这个数据量将带来沉重的存储和 通信负担，并浪费巨大的能源。同时，对于车辆的调度和管理，这样高的采样频率也没有 必要。因此，在实际情况中，一辆车基本在每 1 分钟、甚至几分钟才向交通管理部门发送 一个坐标。此类应用产生了大量的低采样率 GPS 轨迹，也为以前的那些地图匹配算法带来 了新的挑战。 在文献8中，我们针对这种低采样率的 GPS 轨迹提出了一种基于全局信息
13、的匹配方法。 其主要创新思想包括以下三点（结合图 1 给出的事例具体说明，其中红点为记录的 GPS 点， 而蓝色虚线为实际走过的道路）： 1） 前后位置信息：如图 1 所示，一个 GPS 点 c 被映射到哪条道路上不仅取决于点 c 到 周边道路的距离，也取决于它的相邻 GPS 采样点 a，b，d 和 e 的映射情况。如果 我们可以确定 a，b，d 和 e 属于水平路段，那点 c 也很可能属于水平路段，即便点 c 距离垂直路段更近。 2） 相互影响：如图 1 所示，在映射点 c 时，前后临近的点 a，b，d 和 e 将作为参考对 象来辅助点 c 的映射。而反过来，在映射点 d 时，点 c 将作为
14、 d 的参考点。因此， 一个点既会受周边点的影响，也会影响到周边的点。 3） 影响随距离衰减：在映射点 c 时，相对于点 f 而言，b 和 d 距离 c 更近，所以它们 给点 c 的影响应大于 f 点。即点 f 的匹配结果跟 c 将被映射到哪条道路上已经没有 太大的关系。 图 1. GPS 轨迹的地图匹配样例 交通方式判别交通方式判别 用户在记录自己的行程时可能采用不同的交通方式，如步行或开车；甚至在同一次行程中 也会变换自己的交通方式，如先乘坐公交车，然后开始步行。如果能从用户的 GPS 轨迹中 a b cde f 自动学习出线路产生时用户选用的交通模式，那对线路的分类和推荐将有很大的帮助。
15、比 如，帮组寻找自驾游的用户保留开车的线路，而过滤掉那些公交、骑车和步行线路。 基于 GPS 轨迹的交通工具判别的主要挑战来自于两个方面。一个是交通工具的速度通 常会受到交通状况的影响。比如，堵车的时候，汽车的运行速度可能跟正常路段的骑车速 度相差无几。因此，单单基于速度的判别方法的识别精度小于 50%。其二，用户在一次行 程中通常会变换交通方式，如从开车到步行。这使得同一条线路可能会包含多种交通方式。 如不能进行有效的分割，判断的结果也会包含不可避免的错误。 这项研究工作的主要创新点来源于以下三个方面（细节请参阅文献10，11，12）： 1） 我们提出了一种有效的路线分割方法。其主要的思想是
16、利用步行路段来分割轨迹。 在典型的场景下，人们在变换一种交通方式之前必需采用步行，即便步行的长度很 短。比如，从公交车下车到乘坐另一辆出租车的过程中，用户必须通过走路来过渡。 2） 我们发觉了一些受交通状况影响不大的特征，如方向改变率等，并结合监督学习的 方法来训练一个分类模型。如图 2 所示，通常情况下，人在驾车时不可能像步行 一样随意而灵活的改变自己的前进方向。而人即便有意识的走直线，其产生的线路 也免不了要出现蜿蜒。 3） 我们提出了一种后处理方法。该方法从大量的线路中挖掘出一个隐含的地图，并分 析了不同路段上各种交通工具的使用概率和交通工具之间的转移概率。因此，巧妙 地利用了自然常识、地理限制和地图信息来修正错误的判别。 图 2 驾汽和步行的方向改变情况 频繁模式挖掘频繁模式挖掘9 用户历史轨迹中出现的频繁模式反映了个人的生活习惯和行为规律。如果可以很好的从轨 迹中理解到这些知识，服务提供商将可以为用户提供更深入、更个性化的位置服务。而要 从轨迹中挖掘这些频繁模式，首先要面临的困难就是如何对个人的历史轨迹建模
