近似到达时间约束下的语义轨迹频繁模式挖掘-吴瑕 , 唐祖锴 , 祝园园 , 彭煜玮 , 彭智勇.pdf

上善若水

158

21页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(10):31843204 [doi: 10.13328/j.cnki.jos.005418] http://www.jos.org.cn

近似到达时间约束下的语义轨迹频繁模式挖掘



吴

瑕

1,2

唐祖锴

祝园园

彭煜玮

彭智勇

(软件工程国家重点实验室(武汉大学),湖北武汉 430072)

(武汉大学计算机学院,湖北武汉 430072)

(武汉理工大学计算机科学与技术学院,湖北武汉 430070)

通讯作者: 彭智勇, E-mail: peng@whu.edu.cn

摘要: 随着 GPS 定位技术的不断发展与智能移动设备的普及,轨迹数据的获取变得越来越容易,同时,轨迹数据

相关应用的需求也逐渐增多.在轨迹数据上加入语义信息,可以得到体积较小、质量较高、能够更好地反映用户行

为的语义轨迹,在其上实现旅游线路推荐、路线预测、用户生活模式挖掘、朋友推荐等应用,可以更好地满足用户

需求.挖掘语义轨迹的频繁模式是实现这些应用的技术基础,而在很多情况下,用户对语义轨迹频繁模式常存在到达

时间方面的需求,比如按特定时间游玩热门景点的同时需要按时到达车站候车.现有的语义轨迹模式挖掘方法大多

没有考虑到达时间的约束,挖掘出的频繁模式缺少到达时间信息;少数方法考虑了精确的到达时间,但因为约束太强

会导致无法挖掘到频繁的模式.因此,首次对近似到达时间约束下的语义轨迹频繁模式(approximate arrival-time

constrained frequent pattern,简称 AAFP)挖掘方法进行了研究,并给出了其形式化定义;通过时间轴划分提出了挖掘

AAFP 的基线算法,并通过建立索引 AAP-tree 提出了改进后的高效、灵活的 AAFP 挖掘算法;之后提出了信息熵增

量公式,并给出了时间轴划分及 AAP-tree 的高效维护方法;最后在真实数据集上进行实验,验证了方法的有效性及

高效性.

关键词: 轨迹数据,语义轨迹,近似到达时间,轨迹频繁模式,频繁模式挖掘

中图法分类号: TP311

中文引用格式: 吴瑕,唐祖锴,祝园园,彭煜玮,彭智勇.近似到达时间约束下的语义轨迹频繁模式挖掘.软件学报, 2018,29(10):

31843204. http.//www.jos.org.cn/1000-9825/5418.htm

英文引用格式: Wu X, Tang ZK, Zhu YY, Peng YW, Peng ZY. Frequent pattern mining with approximate arrival-time in

semantic trajectories. Ruan Jian Xue Bao/Journal of Software, 2018,29(10):31843204 (in Chinese). http.//www.jos.org.cn/1000-

9825/5418.htm

Frequent Pattern Mining With Approximate Arrival-Time in Semantic Trajectories

WU Xia

1,2

, TANG Zu-Kai

, ZHU Yuan-Yuan

, PENG Yu-Wei

, PENG Zhi-Yong

(State Key Laboratory of Software Engineering (Wuhan University), Wuhan 430072, China)

(Computer School, Wuhan University, Wuhan 430072, China)

(School of Computer Science and Technology, Wuhan University of Technology, Wuhan 430070, China)

Abstra ct : Along with the development of the GPS positioning technology and smart mobile devices, more and more trajectory data are

collected continuously every day. Thus, managing and mining useful information from these trajectories is critical in many application

areas. Compared with raw trajectory data, semantic trajectory data equipped with semantic information has better quality, less volume and

基金项目: 科技部国家重点研发计划(2016YFB1000700); 国家自然科学基金(61502349)

Foundation item: Ministry of Science and Technology of China, National Key Research and Development Program (2016YFB

1000700); National Natural Science Foundation of China (61502349)

收稿时间: 2017-05-07; 修改时间: 2017-08-25; 采用时间: 2017-09-25; jos 在线出版时间: 2018-03-13

CNKI 网络优先出版: 2018-03-13 17:17:54, http://kns.cnki.net/kcms/detail/11.2560.TP.20180313.1717.002.html

吴瑕等:近似到达时间约束下的语义轨迹频繁模式挖掘

3185

higher description ability, and thus it can be used in many applications such as trip recommendation, next location prediction, life pattern

understanding, and friend recommendation. Mining frequent pattern in semantic trajectories is the fundamental problem in above tasks. In

many circumstances, users may have the requirements on the arrival-time, e.g., users may want to visit a popular view spot at a certain

timestamp and then arrive the railway station on time. Most of existing approaches on semantic trajectory pattern mining do not consider

the arrival-time, and only a few existing approaches take the accurate arrival-time as the constraint, but they can barely find frequent

patterns under such a strict time constraint. This paper, for the first time, studies the approximate arrival-time constrained frequent pattern

(AAFP) mining problem. First, a baseline algorithm of mining AAFP is given by dividing the time axis into intervals. Then, an improved

flexible algorithm is proposed to significantly improve the efficiency based on the AAP-tree index. Finally, a strategy to maintain the

AAP-tree and the set of time axis partitions is introduced based on incremental information entropy. The experimental results on real

trajectory datasets validate the effectiveness and efficiency of the proposed algorithms.

Key words: trajectory data; semantic trajectory; approximate arrival-time; trajectory frequent pattern; frequent pattern mining

随着 GPS 定位技术的不断发展与智能移动设备的普及,轨迹数据的获取变得越来越容易,同时轨迹数据相

关应用的需求也逐渐增多.轨迹数据(trajectory data)具有数据量大、更新频率快、价值密度低等特点,会导致基

于轨迹的挖掘、查询等效率低,效果不理想.若在轨迹数据上加入语义信息,则可得到体积较小、质量较高、能

够更好地反映用户行为的语义轨迹(semantic trajectory).因此,近年来不少学者开始关注基于语义轨迹的研究,

并在其上实现旅游线路推荐、路线预测、用户生活模式挖掘、朋友推荐等应用,以更好地满足用户需求.

语义轨迹的频繁模式挖掘(frequent pattern mining)是实现这些应用的技术基础

[1]

,例如,一位游客希望系统

为他推荐热门旅游路线,系统将频繁模式{景点→美食街→火车站,0.12}推荐给游客,表示模式“景点→美食街

→火车站”在历史轨迹集中出现的概率为 12%,是一条热门路线.然而,在很多情况下,用户对语义轨迹模式常存

在到达时间方面的需求,比如,用户需要在上午 10:00 游览景点、中午 12:00 到达饭店且下午 16:00 到达火车站,

同时希望推荐的线路是热门线路,则需要挖掘出包含到达时间的语义轨迹模式以适应此类应用的需求.比如,模

式{景点,10:00→美食街,12:00→火车站,16:00,0.12},我们称这样的模式为在到达时间约束下的语义轨迹频

繁模式(arrival-time constrained frequent pattern,简称 AFP).

目前,现有的大多语义轨迹频繁模式挖掘方法无法挖掘出 AFP,因为一部分方法

[2,3]

完全没有考虑时间,而另

一部分方法考虑

[47]

的是行程时间(travel-time),即从一个地点转移到另一个地点所花费的时间,并没有考虑具

体到达某个地点的时刻.文献[8]虽然提供了一种可以用于挖掘 AFP 的方法,但是这种方法精确地将到达时刻考

虑到语义轨迹模式中,基本无法挖掘到频繁的模式.如图 1 所示,给定 5 条历史语义轨迹,设频繁度为 0.05(在历史

轨迹集中出现的概率大于 5%就认为是频繁的),用传统频繁模式挖掘方法可以挖掘到若干频繁模式,但是这些

频繁模式都没有到达时间信息;若精确地考虑到达时间,使用文献[8]的方法挖掘 AFP,则挖掘不到频繁度高于

0.05 的 AFP,因为在文献[8]给出的方法中,只要到达时刻不一致,即为不同的模式,如“景点,10:10→美食街,

11:55”与“景点,9:50→美食街,12:20”是两个不同的模式.

在现实生活中,用户希望“12:00 去吃饭”,其实并不是要求非常准确的“12:00 整”到达饭店,“12:00 左右”更符

合用户的实际需求,因此,本文将考

虑语义轨迹在近似到达时间约束下的频繁模式(approximate arrival-time

constrained frequent pattern,简称 AAFP)挖掘.如图 1 所示,AAFP 方法能够挖掘出 AFP 方法不能挖掘出的频繁模

式,同时,近似地满足用户对到达时间的要求.比如,本例中 AAFP 方法认为“景点,10:10→美食街,11:55”“景

点 ,9:50→ 美食街,12:20” 与 “ 景点,10:05→ 美食街,12:30” 是同一个 AAFP:{ 景点,10:05→ 美食

街,12:30,0.07}.

然而,考虑近似到达时间后会带来一些挑战.首先,如何合理地划分时间轴在实现“近似到达时间”的同时使

其不破坏数据分布特征;其次,语义轨迹频繁模式挖掘效率通常是非常低的

[9,10]

,考虑到达时间后会使基础频繁

项增多,使其挖掘效率更低,如何保证挖掘效率是一个难点;最后,在新数据到来后,会改变数据的分布特征,同时

改变时间轴划分,从而改变语义轨迹 AAFP 的挖掘结果,如何维护时间轴划分以及挖掘结果也是需要解决的问

题.为了解决这些问题,本文首先使用信息熵聚类方法将语义轨迹集中各个地点的时间轴合理地划分开,并提出

了挖掘语义轨迹 AAFP 的基线算法.之后,为了改进基线算法,使其更高效、更灵活,本文建立了一个多层混合索

of 21

免费下载

软件学报计算机技术

关注

评论