收稿日期:20180409;修回日期:20180529 基金项目:国家自然科学基金资助项目(41201465);江苏省自然科学基金资助项目
(BK2012439);江苏省社会发展项目(BE2016774)
作者简介:张海涛(1978),男,副教授,博士,主要研究方向为移动 GIS理论方法与关键技术、时空数据挖掘、LBS隐私保护等(zhanghaitao@
njupt.edu.cn);蒋继飞(1993),男,硕士,主要研究方向为数据挖掘、隐私保护;周欢(1993),男,硕士,主要研究方向为隐私保护.
基于模式匹配度的用户移动规则
挖掘及位置预测方法研究
张海涛
a
,蒋继飞
b
,周 欢
b
(南京邮电大学 a.地理与生物信息学院;b.通信与信息工程学院,南京 210003)
摘 要:传统的移动用户位置预测方法由于模式支持度计算方式不合理,存在预测精度偏低的问题。为此,提
出了一种基于模式匹配度的用户移动规则挖掘及位置预测方法,并将其用于移动通信系统中,以基台覆盖范围
网格为单元的用户位置预测。具体包括三个步骤:通过图的遍历挖掘用户移动模式、基于用户移动模式生成用
户移动规则和依据用户移动规则进行位置预测。实验分析使用 10个批次轨迹数据进行用户移动规则挖掘,结
果表明,该方法挖掘出的用户移动规则数少、支持度高、置信度高,具有高精度的优点。
关键词:移动用户;位置预测;模式匹配度;用户移动规则
中图分类号:TP393 文献标志码:A 文章编号:10013695(2019)11012325804
doi:10.19734/j.issn.10013695.2018.04.0280
Methodofminingusermobilerulebasedonpatternmatching
degreeandlocationprediction
ZhangHaitao
a
,JiangJifei
b
,ZhouHuan
b
(a.CollegeofGeographic&BiologicInformation,b.CollegeofCommunication&InformationTechnology,NanjingUniversityofPosts&Tele
communications,Nanjing210003,China)
Abstract:Thetraditionalmobileuserlocationpredictionmethodhasaproblemoflowpredictionaccuracyduetounreasonable
calculationofsupport.Toovercomethesechallenges,thispaperpresentedamethodcalledminingusermobilerulebasedon
patternmatchingdegreeandlocationprediction.Itcanpredictlocationwiththebasecoveragemeshastheunitformobileus
ersinmobilecommunicationsystems.Thedetailedprocedurecontainedthreephases
:a)miningusermobilepatternsfrom
graphtraversal;b)generatingusermobilerulesfromusermobilepatterns;c)predictingbasedonusermobilerules.Finally,
theconductedexperimentson10batchesoftrajectorydatademonstratethatthismethodhasthecharacteristicsoffewerrules,
highersupport,andhigherconfidencethantraditionalmethods,andhighlypredictaccuracy.
Keywords:mobileuser;locationprediction;patternmatchingdegree;usermobilerule
随着计算机技术和通信技术的发展,移动通信系统日益普
及
[1,2]
。移动计算为人们在任何时间地点访问任何数据的需
求提供了实现手段,被视为计算机的热点领域
[3,4]
。移动计算
具有移动性、网络多样性等特点
[5~7]
。目前,以 3G、4G为主的
移动通信系统,具有服务用户庞大及数据服务类型多样性(如
视频、声音、图像等)的特点。为保障服务的质量,需要对移动
通信系统中的移动用户信息进行更加有效的管理。移动性位
置管理也即移动用户的位置信息存储、更新和预测,是移动通
信系统管理的主要内容
[8~11]
。其中,移动用户的位置预测可
以有效地用于系统资源的时空分配,以提高移动通信系统的资
源利用率,并降低移动用户在基台覆盖范围网格(mesh)之间
切换(handover)时产生的系统延迟及掉线
[12~14]
,最终能够明
显地提高移动通信网络的服务质量。针对位置预测,国内外学
者提出了很多解决方法。文献[15,16]提出了一种 GMM 和
LMM相结合的方法,使用 GMM与 LMM分别建立用户在基台
覆盖范围网格间和基台覆盖范围网格内的移动模型,并基于移
动用户的运动轨迹与移动模型的匹配,对移动用户的位置进行
预测。文献[17]利用 Apriori算法对用户移动轨迹进行处理,
提取用 户 移 动 模 式 来 进 行 用 户 位 置 预 测。Morzy
[18,19]
利 用
Aprior算法进行改进后生成关联规则,后来又依据改进的 Pre
fixSpan
算法提取出用户移动的频繁模式,通过对用户的频繁
模式进行处理生成预测位置的用户规则。
上述方法存在的共性问题是用于用户位置预测的模式或
规则,其支持度计算方法都是采用简单的计数方式,用户位置
预测的精度较低,不能对用户位置预测的高精度问题进行有效
处理。而高精度是保证移动通信系统为移动用户高效分配系
统资源的关键技术问题。因此本文提出一种基于模式匹配度
的用户移动规则挖掘及位置预测方法研究。
1 位置预测方法的基本原理
定义 1 G=〈V,E〉表示移动通信系统中所有基台覆盖范
围形成的有方向性的、无 权 重 的 图 结 构。假 设
T=〈C
1
,C
2
,
C
3
,…,C
n
〉表示用户在基台覆盖范围内的移动路径即移动序
列,每个 C
K
网格,且连续的网格之间空间邻近。序列数据库 D
为〈sid,T〉的元组集合,其中 sid为当前移动序列的 id,T表示
移动序列。假设
L
K
为根据序列数据库挖掘出长度为 K的用户
移动模式集合,对每一个长度为 K的用户移动模式检查其最
后一个网格是否在 G中有空间邻近点,若有,将其添加到该用
户移动模式,最终形成长度为 K+1的候选模式集合 C
K+1
。根
第 36卷第 11期
2019年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.36No.11
Nov.2019