收稿日期:20190730;修回日期:20190928
作者简介:吴瑕(1986),女(彝族),云南昆明人,讲师,博士,主要研究方向为轨迹数据管理、轨迹数据挖掘;赵小明(1981),男,副教授,硕士,
主要研究方向为海量数据分析与信息服务、计算智能与知识发现;余建坤(1962)(通信作者),教授,硕士,主要研究方向为数据挖掘、模糊数据处
理、商务智能(2534194025@qq.com).
轨迹图谱:一种基于知识图谱结构的轨迹信息抽取方法
吴 瑕,赵小明,余建坤
(云南财经大学 云南省经济社会大数据研究院,昆明 650221)
摘 要:现有的这些方法对轨迹数据需根据不同的应用设计不同的数据结构、存储结构、查询算法等,缺少通用
性。为了使得轨迹数据更具有通用性,提出了将轨迹转换为知识图谱结构的方法。该方法结合轨迹数据的特点
及知识图谱的定义,分别抽取出轨迹数据的实体、关系、属性并构造了轨迹图谱。转换为轨迹图谱后的轨迹数据
具有通用的图结构,可直接支持轨迹的基本查询、范围查询、最近邻查询、关键词查询、模式查询等,并可轻易地
将其添加到各种现有的知识库中。最终通过在真实数据集上的实验,对比了各类轨迹查询在轨迹图谱方法及普
通数据库方法中的表现,证明了轨迹图谱方法的高效性及通用性。
关键词:轨迹数据;轨迹图谱;轨迹挖掘;轨迹查询;知识图谱
中图分类号:TP392 文献标志码:A 文章编号:10013695(2020)11011325508
doi:10.19734/j.issn.10013695.2019.07.0270
Trajectorygraph:methodoftrajectoryinformation
identifyingbasedonknowledgegraph
WuXia,ZhaoXiaoming,YuJiankun
(BigDataResearchInstituteofYunnanEconomy&Society,YunnanUniversityofFinanceandEconomics,Kunming650221,China)
Abstract:Fordifferentapplications,manymethodsneedtrajectoriestobedesignedandstoredindifferentdatastructures,and
searchedbydifferentalgorithms,thatistosaytheyarelackofuniversalproperty.Forthepurposeofincreasingtheuniversal
propertyoftrajectories
,thispaperproposedamethodtotranslatetrajectoriesintotrajectorygraphswhichhavethesamestruc
turesasknowledgegraphs,andproposedmethodfirstidentifiedentities,relationsandattributesaccordingtothefeaturesoftra
jectoriesinturn,thengroupedthem intotrajectorygraphs.Trajectorygraphsaregraphs,theycansupportthebasicqueries,
rangequeries,nearestneighborqueries,keywordsearchesandpatternsearchesoftrajectories,alsocanbeaddedintoexisting
knowledgebaseseasily.Atlast,thispapertookanexperimentalanalysisonrealdata,comparestheperformancesofproposed
methodandcommondatabasemethod,itshowsthatproposedmethodisefficientanduniversal.
Keywords:trajectorydata;trajectorygraph;trajectorymining;trajectorysearch;knowledgegraph
0 引言
随着我国人民生活水平的不断提高,智能手机、家用汽车
的使用已经越来越普遍。截至 2018年 6月,中国智能手机普
及率已达 68%,而全国机动车保有量已达 3.19亿辆。这些设
备在极大方便人们生活的同时,会源源不断地产生大量的轨迹
数据。轨迹(
trajectory)数据是指记录物体运动轨迹的数据,通
常轨迹数据由一系列的、按照时间顺序排列的元组组成,其中每
个元组由一个时间点以及物体在该时间点上所在位置的坐标组
成
[1]
,例如,GPS定位数据。轨迹数据蕴涵着大量有社会价值及
商业价值的信息,若有效地利用这些信息,可实现诸多有利于社
会发展的、有价值的、实用的应用,例如:交通规划、城市规划、灾
难预警、旅游线路推荐、商品推荐、精准营销、社交网络朋友推
荐、智能家居等
[2]
。然而,轨迹数据是典型的大数据,具有数据
量巨大、价值密度低、获取频率快、非结构化、高维度等特点
[3]
,
想要发现并利用轨迹中隐藏的信息并非容易之事。
为此,近年来不少研究关注如何从轨迹数据中发现一些有
价值的信息,例如,轨迹语义发现
[4]
、轨迹频繁模式挖掘
[5]
、轨
迹行为发现
[6]
、相似轨迹聚类
[7]
等。现有的诸多研究从不同
的角度并使用不同的方法尝试去发现轨迹中的各类信息,但是
这些方法大多是基于某种特定的场景和特定的应用来实现的,
例如:轨迹语义发现更多地关心轨迹经过的地点信息,常用于
轨迹关键词查询等;轨迹频繁模式挖掘更多地关心轨迹中频繁
出现的子轨迹,常用于热度推荐等;轨迹行为发现更多地关心
轨迹中用户的行为模式,常用于朋友推荐等。换言之,现有的
轨迹信息发现方法都是相对独立的,缺少通用性,对不同的应
用,需设计不同的数据结构、存储结构、查询算法等。
本文将从轨迹数据中抽取出各类信息,构建基于轨迹数据
的知识图谱,将轨迹数据转换为图数据,使其继承知识图谱语
义丰富、结构友好、数据质量高、易挖掘、易检索等特点,称其为
轨迹图谱。这样,轨迹图谱将包含轨迹中蕴涵的诸多信息并具
有通用的图结构,不但可支持多类型的轨迹查询,还可轻易地
将其添加到各种现有的知识库中,作为知识库信息的补充,以
支持其他领域的应用,如问答系统等。本文首次将轨迹数据转
换为知识图谱结构,并形式化定义了轨迹图谱;从空间、时间、
地理三个维度,抽取出轨迹数据中的实体、关系及属性,并构建
了轨迹图谱;在轨迹图谱上实现了轨迹的基本查询、范围查询、
最近邻查询、关键词查询及模式查询,使得轨迹图谱在结构不
变的情况下可直接支持多种类的轨迹信息发现;在真实数据
集上进行实验,通过对比各类轨迹查询在轨迹图谱方法及普通
数据库方 法中的表现,证明了轨迹 图谱方法的 高效性及通
用性。
第 37卷第 11期
2020年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No11
Nov.2020