基于停留时间的语义行为模式挖掘

郭黎敏 1 高 需 2,3 武 斌 2 郭皓明 2 徐怀野 2 魏闫艳 2 王之欣 2 焉 丽 2 田 霂 2

1 (北京工业大学 北京 100124) 2 (中国科学院软件研究所 北京 100190) 3 (中国科学院大学 北京 100049)(guolimin@bjut.edu.cn)

摘 要: 移动对象的语义行为模式挖掘是当前移动对象研究中关注的热点,有益于诸多应用场景,如朋友推荐系统、轨迹破案领域和个性化服务等.目前语义行为模式挖掘方法没有考虑移动对象在停留点的停留时间,不能准确地分辨出移动对象之间的不同行为模式.为了解决上述问题,提出了一种基于停留时间的语义行为模式挖掘(discovering common behavior using staying duration on semantic trajectory, DSTra)方法,首先挖掘每个移动对象的频繁语义行为模式,然后定义语义行为模式之间的相似性度量方法,最后采用层次聚类的方法对移动对象进行聚类,找出具有相似行为模式的移动对象群体.实验结果表明:该方法不仅具有合理性和有效性,同时还具有较高的准确率和较好的效率.

关键词: 语义轨迹;停留时间;语义行为模式;模式相似度;移动对象聚类

随着移动便携设备的广泛普及以及无线通信技术和全球定位技术的飞速发展,移动对象可以方便地获取其位置信息并对移动轨迹进行存储管理.移动轨迹本身的价值使得各种基于位置的服务越来越受到国内外研究学者的关注,移动对象的轨迹模式挖掘是其中最受关注的热点问题之一.本文研究了移动对象的语义行为模式挖掘方法,即在移动对象语义轨迹的基础上,找出具有相似行为模式的移动对象群体.

事实上,移动对象轨迹记录了人们在现实世界中的活动,而这些活动在一定程度上反映了其生活方式或行为习惯,因此通过对轨迹数据进行分析,挖掘出移动对象的行为模式,发现移动对象之间相关性具有重要的研究价值与广泛的应用领域.如在朋友推荐系统中,通过用户分享的轨迹数据,发现用户的生活方式、兴趣爱好等,推荐趣味相投的朋友;在轨迹破案领域,分析犯罪行为遗留的轨迹信息,结合对嫌疑人的关联分析,查找案件的同伙关系人,并发现嫌疑人的移动模式及其规律,预测其发展走向,协助案件侦破;在个性化服务中,帮助服务供应商了解用户的生活规律,预测用户的行驶路径,实现商品或路径推荐.可以说,移动对象的轨迹模式挖掘技术已经得到了人们日益广泛的重视.

移动对象的轨迹模式挖掘可以分为两大类:基于地理信息的轨迹模式挖掘和基于语义信息的轨迹模式挖掘.其中,前者主要关注轨迹的位置特征,如轨迹形状、行驶方向、速度等;后者则主要关注轨迹的语义信息.在基于地理信息的轨迹模式挖掘方法中,位置越靠近并且形状越相似的轨迹被认为越相似.如图1所示,仅从轨迹的位置特征考虑, MO 1 MO 2 最相似,因为 MO 1 MO 2 的轨迹距离最接近并且形状最相似.然而,基于地理位置的相似性度量缺乏语义信息,并不能挖掘移动对象的移动模式.在基于语义信息的轨迹模式挖掘方法中,语义轨迹对移动对象行驶路径中的地理位置标注上了语义信息,图1中语义层的轨迹是地理层中的移动轨迹对应的语义轨迹.然而,现有的基于语义信息的轨迹模式挖掘方法没有考虑移动对象在每个停留点的停留时间.例如,在图1中 MO 1 MO 3 具有相同的移动模式:家→饭店→公司→饭店,但是实际上 MO 1 MO 3 并不相似,因为 MO 1 在饭店工作,去公司送外卖后再返回饭店,而 MO 3 在饭店吃完早餐后去公司上班,并再次返回饭店吃午饭.因此,现有的基于语义的方法不能准确地分辨出移动对象之间不同的生活方式.

Fig. 1 Geographic and semantic trajectories
图1 地理信息轨迹和语义信息轨迹

Fig. 2 User behaviors with staying durations
图2 基于停留时间的语义行为模式挖掘

通过上述分析可以看出,在轨迹模式挖掘技术方面,目前缺乏一种能够处理移动对象停留时间的高准确性的轨迹模式挖掘方法.为了解决上述问题,本文提出了一种基于停留时间的语义行为模式挖掘(discovering common behavior using staying duration on semantic trajectory, DSTra)方法.DSTra具备2种优势:1)能够提高不同语义行为模式之间的区分度;2)能够发现具有相似生活方式或行为习惯的移动对象群体.在图2中,如果考虑每个停留点的停留时间,就能容易地区分出图1中 MO 1 MO 3 具有不同的行为模式.由于 MO 1 MO 3 在公司和饭店的不同停留时间体现了其不同的意图,因此可以分辨出 MO 1 MO 3 具有不同的行为模式.由此可以从图2中挖掘出语义行为模式 (家,10)→(饭店,1)→(公司,4)→(饭店,1.5),并逐步找出具有相似行为模式的移动对象聚类{ MO 3 , MO 4 }.

DSTra的基本思路是:在一系列移动对象的语义轨迹集合中,1)挖掘出每个移动对象的基于停留时间的频繁语义行为模式;2)基于停留时间给出了语义行为模式之间的相似性度量方法;3)通过模式之间的相似性,采用层次聚类的方法对移动对象聚类,每一个聚类代表具有一系列相似语义行为模式的移动对象集合,也就是具有相似生活方式、行为习惯的移动对象集合.归纳总结本文的主要贡献有5点:

1) 定义了基于停留时间的语义行为模式;

2) 提出了一种基于停留时间的语义行为模式挖掘算法;

3) 提出了一种基于停留时间的语义行为模式相似性度量方法;

4) 提出了一种基于模式相似性的移动对象聚类算法;

5) 验证了DSTra方法在挖掘语义行为模式时的有效性、高准确性及高效性.

1 相关工作

本节首先介绍了轨迹相似性度量方法,然后概述了现有的轨迹模式挖掘技术.

轨迹相似性度量方法主要分为两大类:基于地理信息的相似性度量和基于语义信息的相似性度量.

基于地理信息的相似性度量关注的是轨迹的位置特征,早期的研究主要是基于欧氏距离的度量方法,其中最具代表性的有DTW [1] ,EDR [2] ,LCSS [3] .此外,针对轨迹模式之间的相似性度量也进行了相关的研究 [4-7] ,文献[4]研究了基于线索的轨迹相似性.文献[5]提出了3种距离度量方法;基于语义信息的相似性度量主要关注的是轨迹的语义特征,文献[8-11]对语义轨迹进行了研究,语义轨迹被定义为一系列时空位置与相应停留点的集合,如此不仅能抽取位置信息还能挖掘语义信息.另外,研究学者在语义轨迹相似性领域也进行了相关的讨论和研究 [12-16] .这些文献中,首先将轨迹转换为语义轨迹,然后通过移动对象之间的相似性进行用户推荐.文献[15]依据用户之间轨迹模式的相似性定义用户之间的相似性.文献[13-14]通过层次树状结构计算相似性.文献[16]结合了位置及语义特征预测用户未来的位置.

基于地理信息的相似性度量方法只能处理轨迹的位置信息,而基于语义信息的相似性度量方法不能处理轨迹中的停留时间,因此现有的相似性度量方法不能解决基于停留时间的轨迹相似性问题.

现有的轨迹模式挖掘方法可以分为2大类:轨迹模式挖掘和轨迹聚类.

轨迹模式挖掘研究的是移动对象的运动模式,早期的研究主要关注的是轨迹的时空属性 [17-20] ,其基本思想是通过序列模式挖掘找出频繁轨迹模式.由于这些方法没有考虑停留时间对轨迹模式的影响,因此不能有效地区分不同的轨迹模式.

轨迹聚类的目标在于挖掘具有相同运动模式的移动对象集合 [21-26] .除此之外,另一类研究的目标在于找出移动对象集合的公共路径,文献[5]将每条轨迹划分为一系列子轨迹,然后基于距离函数进行聚类.文献[27]在轨迹划分和聚类的过程中同时考虑了时间和空间因素.

上述轨迹模式挖掘方法从移动对象的个体或群体的角度出发进行研究,但是既不能挖掘移动对象的公共行为模式,也不能处理语义轨迹.为了解决上述问题,本文提出了一种基于停留时间的语义行为模式挖掘方法.

2 问题定义

本节以语义轨迹为基础,首先给出了语义行为模式的相关问题定义,然后介绍了DSTra方法的系统架构.

为便于叙述,表1给出了本文的符号描述表.

定义1. 语义点.语义点A定义为

A=( A , t ),

其中, A 是移动对象的停留点, t 是移动对象在 A 的停留时间.

定义2. 语义轨迹.语义轨迹 S 是一组移动对象语义点的有序序列,定义为

.

Table 1 List of Symbols

表1 符号描述表

SymbolDescriptionAAnnotationASemanticstopSSemantictrajectorySSemanticannotationsequencePSemantictrajectorypatternPSemantictrajectorypatternsetDSemantictrajectorydatasetS1≅S2S1isequaltoS2S≺PSmatchesPfminMinimumsupportthresholdδtDurationthresholdδlenMinimumlengththresholdLD(α)α-projecteddatabaseP⊕QAppendQtoPLCSLongestcommonsub-sequenceWTimeweight

S 的语义符号序列 是移动对象停留点构成的有序序列.

不失一般性,我们使用字母表示移动对象的停留点,表2为某一移动对象的语义轨迹集合实例.

Table 2 An Example of Semantic Trajectory Dataset

表2 语义轨迹集合

SidSemanticTrajectory1{(a,10),(b,4),(c,1),(b,4)}2{(b,1),(d,2),(e,0.5),(f,2)}3{(a,10),(b,1),(c,4),(b,1.5)}4{(a,10),(b,0.5),(d,0.5),(c,4),(f,0.5),(b,1.5)}

定义3. 语义轨迹等价.给定停留阈值 δ t ,语义轨迹 S 1 S 2 等价定义为 S 1 S 2 ,当且仅当满足条件:

2)∀ .

其中,条件2对相应2个语义点之间的停留时间进行了约束,即停留时间比例差受限于 δ t .

定义4. 语义行为模式.语义行为模式 P 是一组相似语义轨迹的共同模式,定义为

.

为了更好地描述语义行为模式挖掘,我们定义了语义行为模式与语义轨迹之间的匹配关系.

定义5. 模式匹配.给定语义行为模式 P 和语义轨迹 S S 匹配 P 定义为 S P ,当且仅当 S 存在子序列 S P ,使得 S P P .

移动对象的行为语义提取即从语义轨迹集合中挖掘出频繁语义行为模式.

定义6. 行为语义提取.给定语义轨迹集合 和最小支持度 f min ,行为语义提取即找出所有满足如下条件的最长语义行为模式

.

以表2为例,假设 δ t =0.5, f min =0.5,依据定义6,{( a ,10),( b ,0.5),( c ,4),( b ,1.5)}是一个语义行为模式.然而任意形如{( a ,10),( b , t ),( c ,4),( b ,1.5)}( t ∈[0.5,1])的行为模式都满足条件.因此,我们采用平均停留时间来表示行为模式中的停留时间.

问题描述:给定语义轨迹集合D、最小支持度 f min 和停留阈值 δ t ,移动对象的语义行为模式挖掘步骤如下:1)依据 f min δ t ,从D中进行行为语义提取,找出所有语义行为模式的集合P;2)度量P中模式之间的相似度;3)在相似度的基础上,依据移动对象的相似生活方式、行为习惯等进行聚类.

由此,我们提出了一种语义行为模式的挖掘方法——基于停留时间的语义行为模式挖掘DSTra.DSTra的系统结构如图3所示,可以分为3部分:1)语义行为模式挖掘(semantic trajectory pattern mining,STPM);2)模式相似性度量(pattern similarity, P-Similarity);3)基于模式相似性的移动对象聚类(similarity-based user clustering, SU-Clustering).

Fig. 3 System overview of DSTra
图3 DSTra的系统结构

图3中,1)提出了基于停留时间的语义行为模式挖掘算法,并对每个移动对象进行了行为语义抽取;2)设计了基于时间权重的语义行为模式相似度度量方法;3)在模式相似性的基础上,采用剪枝策略进行层次聚类,找出所有具有相似行为模式的移动对象群体.

3 基于停留时间的语义行为模式挖掘算法

本节首先给出了相关数据结构,然后详细介绍了语义行为模式挖掘算法STPM.

在语义行为模式挖掘之前,首先要将原始轨迹转换为语义轨迹,相关研究较为丰富 [7] ,鉴于篇幅所限,在此处不再详述;然后针对每一个移动对象,提取其主要的语义行为模式集合.

在PrefixSpan算法的基础上,我们提出了基于停留时间的语义行为模式挖掘算法STPM.STPM与PrefixSpan的不同之处在于投影数据库的构建,对于 α ,PrefixSpan中 α -投影数据库是由第1次出现的 α 为前缀的子序列构成,而STPM中并不总以第1次出现的 α 为前缀.我们采用类似文献[28]中的数据结构来构建 α -投影数据库.

定义7. 投影数据库.给定语义轨迹集合D, α 的投影数据库 tuple 是一个四元组,定义为

tuple = sid , pos , t , proj

其中, sid 是语义轨迹在D中的标识号; pos α 中最后一个停留点在语义轨迹中的位置; t 是在 α 中最后一个停留点的停留时间; proj pos 位置上以 α 为前缀的子序列.

表3为表2中语义轨迹集合的 b -投影数据库.

Table 3 b -projected Database

表3 b -投影数据库

Prefixtuple1,2,4,{(c,1),(b,4)}1,4,4,∅2,1,1,{(d,2),(e,0.5),(f,2)}b3,2,1,{(c,4),(b,1)}3,4,1.5,∅4,2,0.5,{(d,0.5),(c,4),(f,0.5),(b,1)}4,6,1.5,∅

STPM算法的伪代码如算法1所示.STPM是深度优先递归算法,递归地扩展语义行为模式,以及试探其是否满足频繁语义行为模式的条件,并通过不断构建投影数据库有效降低支持度及停留时间计算的时间复杂度.

算法1. STPM算法.

输入:语义轨迹集合D、最小支持度 f min 、停留阈值 δ t 、语义行为模式 P

输出:频繁语义行为模式集合P.

*L D ( P )中长为1的频繁语义符号*

S 1 Frequent (L D ( P ));

③ for β in S 1 do

*扩展模式 P *

P ′← P β ; * P 后扩展 β *

⑥ L D ( P )←∅;

*建立 P ′的投影数据库*

⑧ for tp in L D ( P ) do

S ←D( tp . sid );

⑩ for i : i > tp .

L D ( P ′)←L D ( P ′) ∪ tp . sid , i , S i . t , tp . proj β

*递归构建频繁语义行为模式*

*选取L D ( P ′)中有效集合*

∪P extend

end for

return P.

在算法1中,我们首先找出L D ( P )中长度为1的频繁语义符号项集 S 1 ,并将 P S 1 中的语义符号 β 进行扩展(行①~⑥);然后在语义轨迹集合D中构造模式 P ′= P β 的投影数据库(行⑦ );接下来,递归地构建频繁语义行为模式(行 ),对于L D ( P ′)中的每一个项集 tp ′,我们调用函数 ValidSet ()返回L D ( P ′)中与 tp ′等价的有效集合 M ,若为频繁模式,则调用函数 GeneratePattern ()构建频繁语义行为模式,并递归调用函数 STPM ()扩展模式.

算法1中行 ,函数 ValidSet ()依据定义3,计算出与 tp ′等价的停留时间范围.假设 tp ′= sid , pos , t , proj ,那么 tp ′的等价停留时间范围 R

R =[ tp ′. t , tp ′. t 1- δ t ].

函数 ValidSet ()最终返回L D ( P ′)中停留时间在 R 范围内的项集 M .

算法1中行 ,函数 GeneratePattern ()根据有效集合 M 中的平均停留时间构建 β 的停留时间.假设 的停留时间 t β

.

函数 GeneratePattern ()最终返回语义行为模式 P ′= P ⊕( β , t β ).

在表3中,假设 δ t =0.5, tp ′= 3,4,1.5,∅ ,则等价停留时间 R =[1.5,3],等价项集 M ={ 3,4,1.5,∅ , 4,6,1.5,∅ },停留点 b 的平均停留时间 t b =(1.5+1.5) 2=1.5.

4 语义行为模式相似性

本节介绍了语义行为模式之间的相似性度量方法.

从直觉上来说,语义行为模式之间的相似性与其之间的公共子串相关,因此我们采用公共子串来度量模式之间的相似性.

定义8. 最长公共子串.给定2个语义行为模式 P 1 P 2 P 1 P 2 的最长公共子串 LCS 满足条件:

1) LCS P 1 LCS P 2

2) ∀ 2.

其中∀ i ,∃ i ,∃ .

为了突出停留时间对语义行为模式的影响,我们给出了时间权值的定义.

定义9. 时间权值.给定语义行为模式 P 1 P 2 及其最长公共子串 LCS ,对于A i LCS ,A i 的时间权值定义为

).

定义10. 语义行为模式相似度.给定语义行为模式 P 1 P 2 及其最长公共子串 LCS P 1 P 2 之间的相似度定义为

其中A i LCS .

假设 δ t =0.5,给定2个语义行为模式 P ={( a ,10),( b ,1),( c ,4)} 和 Q ={( a ,10),( b ,0.5),( d ,0.5),( c ,4)},那么 P Q 的最长公共子串为 LCS ( P , Q )= ( a ,10),( b ,0.75),( c ,4) .表4给出了 LCS 的时间权值,因此 P Q 之间的相似度为 Sim ( P , Q )=(1 3+1 4)×(1+0.5+1)=1.46.

Table 4 An Example of Time-Weight

表4 时间权值

SemanticTrajectoryPatternLCSA1A2A3(a,10)(b,0.75)(c,4)P1014Q100.54WP,Q(A)10.51

动态规划是寻找最长公共子串最有效的方法,动态规划方法采用二维数组标识中间计算结果,避免了重复计算而提高了效率.我们修改了文献[29]中的算法,采用矩阵 SM 保存最长公共子串计算过程中语义行为模式之间的时间权值.给定语义行为模式 P Q SM [ i , j ]的计算公式定义为

SM [ i , j ]=

(1)

其中, max( P i . t , Q j . t ).

算法2. P-Similarity算法.

输入:语义行为模式 P Q 、停留阈值 δ t

输出:相似度 Sim .

① for i =0 to | P | do

SM [ i ,0]. count ←0, SM [ i ,0]. t ←0;

③ end for

④ for j =0 to | Q | do

SM [0, j ]. count ←0, SM [0, j ]. t ←0;

⑥ end for

⑦ for i =1 to | P | do

⑧ for j =1 to | Q | do

⑨ if P i Q j w.r.t δ t then

SM [ i , j ]. count SM [ i -1, j -1]+ w i j

]. t ←( P i . t + Q j . t ) 2;

se if SM [ i -1, j ]. count > SM [ i , j -1]. count then

end for

]. count ×(1 | P |+1 | Q |).

算法2中,我们采用动态规划算法逐步计算了 P Q 之间的相似度,矩阵 SM 分别存储了 P Q 之间的时间权重 SM [ i , j ]. count 和平均停留时间 SM [ i , j ]. t .以表4中的 P Q 为例,首先初始化矩阵的第1行第1列,设置为0(行①~④),如图4所示;然后依据式(1)逐步计算 SM 中的数值(行⑤~ ).图4中,算法首先计算 SM [1,1],由于( a ,10)≅( a ,10),根据式(1)可以得到 SM [1,1]. count =0+1=1,停留时间取平均值 SM [1,1]. t =(10+10) 2=10;然后处理 SM [1,2],由于( b ,0.5)与( a ,10)不等价,因此 SM [1,2]不增加,取值 SM [1,1]与 SM [0,2]中数值较大者,即 SM [1,2]= SM [1,1]=(1,10).通过这种方式,能逐步计算出 SM 中的数值,直至最后找出最长公共子串.

P(a,10)(b,1)(c,4)Q(0,0)(0,0)(0,0)(0,0)(a,10)(0,0)↖(1,10)←(1,10)←(1,10)(b,0.5)(0,0)↑(1,10)↖(1.5,0.75)←(1.5,0.75)(d,0.5)(0,0)↑(1,10)↑(1.5,0.75)←(1.5,0.75)(c,4)(0,0)↑(1,10)↑(1.5,0.75)↖(2.5,4)

Fig. 4 An example of P-Similarity
图4 P-Similarity算法实例

5 基于模式相似性的移动对象聚类

本节介绍了如何在语义行为模式相似性的基础上找出具有相似行为模式的移动对象集合,并提出了基于模式相似性的移动对象聚类算法SU-Clustering,然后在此基础上介绍了SU-Clustering的优化算法.

由于基于密度的聚类算法可能引入噪声点,因此我们采用了层次聚类的方法.为了保证移动对象聚类的有效性,限定同一聚类中语义行为模式之间的最长公共子串长度不能小于长度阈值 δ len .

假设语义行为模式挖掘得到集合 ,其中 c i =( U , P ), P 是语义行为模式, U 是与 P 对应的移动对象.SU-Clustering算法的基本思想是由底至上的层次聚类,首先将每个 c i (语义行为模式及其对应的移动对象)视为单独的聚类,然后依据模式之间的相似性进行聚类,直至聚类中的最长公共子串长度小于 δ len 为止.完整的SU-Clustering聚类算法如算法3所示.

算法3. SU-Clustering算法.

输入:集合 、长度阈值 δ len 、最小移动对象个数 μ

输出:移动对象聚类集合 MO .

MO ←∅;

② for i =1 to n -1 do

③ for j = i +1 to n do

* Sim []存储相似度、 Lcs []存储最长公共子串*

Sim [ i , j ], Lcs [ i , j ]← P - Similarity ( c i . P , c j . P );

⑥ end for

⑦ end for

⑧ while true do *由底至上层次聚类*

*找出最相似的一对语义行为模式*

FindSimPattern ( Sim , Lcs , δ len );

找到最相似的2个模式 c p c q then

←( c p . U c q . U , Lcs [ p , q ]); *合并 c p , c q *

C C\c p c q ; *从 C 中移除 c p c q *

else *找不到满足条件的模式对*

end while

c . U |> μ then

end for

return MO .

算法3中行⑧,函数 FindSimPattern ()返回满足一对最相似聚类 c p c q 的条件:

2) c p . U c q . U =∅.

算法3中行 ,函数 Adjust ()更新了矩阵 Sim 和矩阵 Lcs ,计算了 c new . P 与其他聚类的语义行为模式之间的相似性与最长公共子串.

假设语义行为模式个数为 n ,语义行为模式的平均长度为 m ,迭代次数为 n 1 ,那么初始化矩阵 Sim 和矩阵 Lcs 的时间复杂度为 O ( n 2 m 2 ),层次聚类的时间复杂度为 O ( n 1 nm 2 ).因为 n 1 < n ,所以算法3的时间复杂度为 O ( n 2 m 2 + n 1 nm 2 )= O ( n 2 m 2 ).

在每次迭代过程中,函数 Adjust ()需要调用 n 次函数 P - Similarity ()以更新矩阵 Sim 和矩阵 Lcs ,而这将带来较大的时间开销.为了避免不必要的计算,我们给出了剪枝策略性质1.

性质1. 假设给定语义行为模式 P Q P Q 的最长公共子串长度的边界值等于 P Q 之间等价的语义点个数,记作 LCS - Boundary ( P , Q ).

假设停留阈值 δ t =0.5,语义行为模式 P ={( a ,1),( b ,2),( c ,3)}, Q ={( a ,0.1),( b ,3),( c ,4.5)},由于 ,根据性质1, LCS - Boundary ( P , Q )=2.

利用性质1,我们能通过剪枝策略对函数 Adjust ()进行优化,优化后 Adjust ()算法如算法4:

算法4. Adjust算法.

输入:相似度矩阵 Sim ,最长公共子串矩阵 Lcs ,语义行为模式 c p , c q , c new ,长度阈值 δ len .

*从矩阵 Sim Lcs 中删除 c p c q 对应的行列*

② 从 Sim Lcs 中删除第 p 行和第 q 列;

* c new 插入最后一行,计算与其他行的 Sim Lcs *

④ for i =1 to n -1 do

⑤ if LCS - Boundary ( c new . P , c i . P )≥ δ len then

Sim [ n , i ], Lcs [ n , i ]← P - Similarity ( c new . P , c i . P );

⑦ end if

⑧ end for

⑨ return

假设语义行为模式个数为 n ,语义行为模式的平均长度为 m ,那么算法4的时间复杂度为 O ( nm 2 ).虽然在最坏的情况下,算法4不能优化 Adjust ()算法,但在实验中我们发现优化后的聚类算法能大约提高50%的效率,因此剪枝策略可以有效地减少不必要的计算代价,提高效率.

6 实验结果与分析

本节实现了DSTra实验系统,并在真实数据集和模拟数据集的基础上,对语义行为模式的有效性、准确性以及效率进行了一系列实验验证.

实验所用的真实数据集来自GeoLife [30-32] ,GeoLife数据集是由微软亚洲研究院182名志愿者采集的9 462条GPS轨迹构成.实验所用的模拟数据由机器产生,我们模拟了一系列移动对象,并依据每个移动对象的行为习惯对其生成了一系列语义轨迹.为了真实模拟移动对象的语义轨迹,我们使用了2个参数控制移动对象的行为习惯: N pc Pr .具体来说,我们将语义行为模式共分为 N pc 种类型,每一类语义行为模式描述移动对象的一类行为习惯或生活方式.对于每个移动对象,其中 Pr 比例的语义轨迹随机生成,剩下的语义轨迹依据 N pc 中的一部分行为模式生成.据此模拟的数据既具有一定的行为习惯又具有一定的灵活性,能较真实地还原移动对象的轨迹.

实验程序用C++编写,编译工具为GCC 4.4.6,优化选项为-O2.实验硬件平台处理器为Intel ® Xeon ® CPU E5-2630,主频为2.3 GHz,内存大小为4 GB;软件平台为CentOS release 6.2(Final).我们将从3个方面来分析DSTra的性能:1)语义行为模式挖掘的有效性;2)语义行为模式挖掘的准确率;3)语义行为模式挖掘的效率.表5给出了实验中的主要参数.

Table 5 Experiment Settings

表5 实验中的主要参数

ParametersValueMeaningNmo100NumberofMovingObjectsNtrj1000NumberofSemanticTrajectoriesofEachmoLpattern4-12AverageLengthofEachPatternδt0.1-0.3DurationThresholdδlen3MinimumLengthThresholdfmin0.1-0.5MinimumSupportThresholdNpc20NumberofPatternCategoriesPr0.2RandomProbability

6.1 有效性验证

本节在真实数据集GeoLife的基础上验证了语义行为模式的有效性.

由于GeoLife数据集中的轨迹为GPS轨迹数据,因此不能在DSTra中直接使用,需要进行预处理.我们在处理中结合北京市POI数据库,首先从GeoLife数据集中挖掘出家、公司、超市、游览地、商场、车站、学校、公园、饭店几类具有代表性的访问点;然后以此为依据,将GPS轨迹转换为相应的语义轨迹;最后选择了周末节假日的语义轨迹以发现更有趣的生活方式.

为了显示停留时间对语义行为模式的影响,我们统计了语义轨迹中每个访问点的停留时间(假设志愿者关闭采集器后都在家中),并忽略了无法统计停留时间的语义轨迹.图5是115号志愿者(简称115号)的语义行为模式在Google Map中的展示.参数设置为: f min =0.1, δ t =0.2.

Fig. 5 Semantic trajectory patterns of No.115
图5 115号语义行为模式

图5(a)(b)是从115号的语义轨迹中抽取出的语义行为模式.可以看出,图5(a)(b)的轨迹位置并不相似,基于地理位置信息的轨迹模式挖掘方法不能发现用户的生活方式,而DSTra方法能有效地挖掘出语义行为模式(家,7.5 h)→(游览地,2.5 h)→(家,11 h),表示115号有周末出去游的生活习惯.

图6是73号志愿者(简称73号)的语义行为模式在Google Map中的展示.参数设置为: f min =0.1, δ t =0.2.

Fig. 6 Semantic trajectory patterns of No.73
图6 73号语义行为模式

图6是从73号的语义轨迹中抽取中的语义行为模式,即(游览地,5.5 h)→(家,11 h).可以看出,DSTra方法可以准确地区分出115号与73号2种不同的生活方式,其中115号偏向周末小游一趟,73号则偏向周末外出畅游,而没有考虑停留时间的轨迹模式挖掘方法却不能分辨出其中差别.由此,根据用户相似的生活习惯,DSTra可以将用户进行聚类,同一聚类内的用户具有相似生活方式或行为习惯.

6.2 准确性验证

本节模拟了100个移动对象,并依据每个移动对象的行为习惯各生成了1 000条语义轨迹,其中20%条语义轨迹随机生成,80%条语义轨迹依据20种行为习惯生成.为了更好地评估语义行为模式挖掘的准确率,我们给出了准确率的定义:

其中, ξ correct 是正确的语义行为模式个数, ξ all 是所有的语义行为模式个数.图7是准确率与最小支持度 f min 以及停留阈值 δ t 的关系,参数设置为: N mo =100, N trj =1 000, L pattern =6, N pc =20, Pr =0.2.

图7(a)显示随着最小支持度的增加,语义行为模式的准确率也随之增加,这是因为随着最小支持度的增加,挖掘出的语义行为模式更主流,相应地错误的模式也就随之减少,准确率增加.图7(b)显示语义行为模式的准确率随着停留阈值的增加而逐渐减少,由于停留阈值增加会导致不同模式的区分度降低,从而导致准确率下降.

Fig. 7 Precision evaluation
图7 准确性评估

6.3 效率验证

本节在模拟数据集的基础上验证了SU-Clustering及其优化算法Optimized-SUC的执行效率.图8是SU-Clustering与Optimized-SUC算法的效率评估,图8(a)中停留阈值 δ t =0.2,图8(b)中模式平均长度 L pattern =6,其他参数设置为: N mo =100, N trj =1 000, f min =0.2, δ len =3.

Fig. 8 Runtime evaluation
图8 效率评估

图8(a)为执行时间与模式平均长度的关系,随着模式平均长度的增加,SU-Clustering和Optimized-SUC的执行时间都逐渐增加,这是由于随着模式平均长度的增加,算法中最耗时的最长公共子串匹配的计算复杂度增加,从而导致效率下降.与此相似,图8(b)中SU-Clustering和Optimized-SUC的效率也随着停留阈值的增加而下降,因为最长公共子串匹配的时间复杂度也随着停留阈值增加而增加.除此之外,图8(a)(b)都显示,算法Optimized-SUC的性能明显优于算法SU-Clustering,充分表明Optimized-SUC中的剪枝策略具有显著的效果.

实验结果显示,本文提出的语义行为模式挖掘方法不仅具有合理性和有效性,同时还具有较高的准确率和较好的挖掘效率.

7 结 论

本文提出了一种语义行为模式挖掘方法,能够挖掘出具有相似行为习惯或生活方式的移动对象群体.为了提高不同语义行为模式之间的区分度,本文引入了停留时间的概念,并在此基础上提出了一种基于停留时间的语义行为模式挖掘方法DSTra.DSTra挖掘框架分为3部分:语义行为模式挖掘、模式相似性度量、基于模式相似性的移动对象聚类.DSTra方法具有广泛的应用前景.如在朋友推荐系统中,根据用户提供的日常行为轨迹,挖掘出每个用户的语义行为模式,利用模式相似性度量方法计算语义行为模式之间的相似性,最后基于模式相似性对用户进行聚类,发现具有相似生活方式或行为习惯的用户,并将聚类内的用户相互进行推荐.实验结果表明,DSTra方法不仅具有合理性和有效性,还能够准确并且有效地挖掘出语义行为模式.

参考文献:

[1]Keogh E J. Exact indexing of dynamic time warping[C] Proc of VLDB’02. San Francisco: Morgan Kaufman, 2002: 406-417

[2]Chen L, Ozsu M, Oria V. Robust and fast similarity search for moving object trajectories[C] Proc of ACM SIGMOD’05. New York: ACM, 2005: 491-502

[3]Vlachos M, Hadjieleftheriou M, Gunopulos D, et al. Indexing multidimensional time-series[J]. VLDB Journal, 2006, 15(1): 1-20

[4]Hung C C, Peng W C, Lee W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J]. VLDB Journal, 2015, 24(2): 169-192

[5]Lee J G, Han Jiawei, Whang K Y. Trajectory clustering: A partition-and-group framework[C] Proc of ACM SIGMOD’07. New York: ACM, 2007: 593-604

[6]Li Quannan, Zheng Yu, Xie Xing, et al. Mining user similarity based on location history[C] Proc of Sigspatial GIS’08. New York: ACM, 2008

[7]Zheng Yu, Zhang Lizhu, Ma Zhengxin, et al. Recommending friends and locations based on individual location history[J]. ACM Trans on the Web, 2011, 5(1): 1-44

[8]Parent C, Spaccapietra S, Renso C, et al. Semantic trajectories modeling and analysis[J]. ACM Computing Surveys, 2013, 45(4): No.42

[9]Yan Zhixian, Chakraborty D, Parent C, et al. SeMiTri: A framework for semantic annotation of heterogeneous trajectories[C] Proc of EDBT’11. New York: ACM, 2011: 259-270

[10]Spaccapietra S, Parent C. Adding meaning to your steps[C] Proc of ER’11. Berlin: Springer, 2011: 13-31

[11]Alvares L O, Bogorny V, Kuijpers B, et al. Towards semantic trajectory knowledge discovery[EB OL]. 2007[2015-06-21]. https: uhdspace.uhasselt.be dspace bitstream 1942 1832 1 towards.pdf

[12]Liu Hechen, Schneider M. Similarity measurement of moving object trajectories[C] Proc of IWGS’12. New York: ACM, 2012: 19-22

[13]Zheng Yu, Zhang Lizhu, Xie Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C] Proc of WWW’09. New York: ACM, 2009: 791-800

[14]Zheng Yu, Xie Xing. Learning travel recommendations from user-generated GPS traces[J]. ACM Trans on Intelligent Systems and Technology, 2011, 2(1): No.2

[15]Ying J J C, Lu E H C, Lee W C, et al. Mining user similarity from semantic trajectories[C] Proc of LBSN’10. New York: ACM, 2010: 19-26

[16]Ying J C, Chen H S, Lin K W, et al. Semantic trajectory-based high utility item recommendation system[J]. Expert Systems with Applications, 2014, 41: 4762-4776

[17]Zhu Feixiang. Mining ship spatial trajectory patterns from AIS database for maritime surveillance[C] Proc of ICEMMS’11. Piscataway, NJ: IEEE, 2011: 772-775

[18]Smouse P E, Focardi S, Moorcroft P R, et al. Stochastic modeling of animal movement[J]. Philosophical Trans of the Royal Society of London-Series B: Biological Sciences, 2010, 365(1550): 2201-2211

[19]Li Zhenhui, Ji Ming, Lee J G, et al. MoveMine: Mining moving object databases[C] Proc of ACM SIGMOD’10. New York: ACM, 2010: 1203-1206

[20]Tsai H P, Yang D N, Chen M S. Mining group movement patterns for tracking moving objects efficiently[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(2): 266-281

[21]Zheng Kai, Zheng Yu, Yuan N J. On discovery of gathering patterns from trajectories[C] Proc of ICDE’13. Piscataway, NJ: IEEE, 2013: 242-253

[22]Guo Limin, Huang Guangyan, Ding Zhiming. Efficient detection of emergency event from moving object data streams[C] Proc of DASFAA’14. Berlin: Springer, 2014: 422-437

[23]Jeung Hoyoung, Shen Hengtao, Zhou Xiaofang. Convoy queries in spatio-temporal databases[C] Proc of ICDE’08. Piscataway, NJ: IEEE, 2008: 1457-1459

[24]Al-Naymat G, Chawla S, Gudmundsson J. Dimensionality reduction for long duration and complex spatio-temporal queries[C] Proc of SAC’07. New York: ACM, 2007: 393-397

[25]Li Zhenhui, Ding Bolin, Han Jiawei, et al. Swarm: Mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 723-734

[26]Tang L A, Zheng Yu. On discovery of traveling companions from streaming trajectories[C] Proc of ICDE’12. Piscataway, NJ: IEEE, 2012: 186-197

[27]Wu H R, Yeh M Y, Chen M S. Profiling moving objects by dividing and clustering trajectories spatiotemporally[C] Proc of TKDE’12. Piscataway, NJ: IEEE, 2012: 2615-2628

[28]Srikant R, Agrawal R. Mining sequential patterns: Generalizations and performance improvements[C] Proc of the 5th Int Conf on Extending Database Technology. Piscataway, NJ: IEEE, 1996: 3-17

[29]Bergroth L, Hakonen H, Raita T. A survey of longest common subsequence algorithms[C] Proc of SPIRE’00. Piscataway, NJ: IEEE, 2000: 39-48

[30]Zheng Yu, Zhang Lizhu, Xie Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C] Proc of Int Conf on World Wild Web (WWW 2009). New York: ACM, 2009: 791-800

[31]Zheng Yu, Li Quannan, Chen Yukun, et al. Understanding mobility based on GPS data[C] Proc of ACM Conf on Ubiquitous Computing(UbiComp 2008). New York: ACM, 2008: 312-321

[32]Zheng Yu, Xie Xing, Ma Weiying. GeoLife: A collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin, 2010, 33(2): 32-40

Guo Limin, born in 1984. PhD and lecturer in Beijing University of Technology. Her main research interests include database research and implementation, spatial-temporal data mining, storage, query and analysis of big data, etc.

Gao Xu, born in 1980. PhD candidate and lecturer in the Institute of Software, Chinese Academy of Sciences. His main research interests include database and knowledge base systems, and spatial-temporal database.

Wu Bin, born in 1982. PhD and research fellow in the Institute of Software, Chinese Academy of Sciences. His main research interests include massive data management and multidimensional data analysis.

Guo Haoming, born in 1978. PhD and senior engineer in the Institute of Software, Chinese Academy of Sciences. His main research interests include massive data management and multidimensional data analysis.

Xu Huaiye, born in 1987. Master and engineer in the Institute of Software, Chinese Academy of Sciences. His main research interests include massive data management and multidimensional data analysis.

Wei Yanyan, born in 1990. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. Her main research interests include massive data management and multidimensional data analysis.

Wang Zhixin, born in 1989. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. Her main research interests include massive data management and multidimensional data analysis.

Yan Li, born in 1990. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. Her main research interests include networked control system.

Tian Mu, born in 1989. Master and assistant engineer in the Institute of Software, Chinese Academy of Sciences. His main research interest includes networked control system.

Discovering Common Behavior Using Staying Duration on Semantic Trajectory

Guo Limin 1 , Gao Xu 2,3 , Wu Bin 2 , Guo Haoming 2 , Xu Huaiye 2 , Wei Yanyan 2 , Wang Zhixin 2 , Yan Li 2 , and Tian Mu 2

1 ( Beijing University of Technology , Beijing 100124) 2 ( Institute of Software , Chinese Academy of Sciences , Beijing 100190) 3 ( University of Chinese Academy of Sciences , Beijing 100049)

Abstract: With the advancement of mobile computing technology and the widespread use of GPS-enabled mobile devices, research on semantic trajectories has attracted a lot of attentions in recent years, and the semantic trajectory pattern mining is one of the most important issues. Most existing methods discover the similar behavior of moving objects through the analysis of sequences of stops. However, these methods have not considered the duration of staying on a stop which affects the accuracy to distinguish different behavior patterns. In order to solve the problem, this paper proposes a novel approach for discovering common behavior using staying duration on semantic trajectory (DSTra) which can easily differentiate trajectory patterns. DSTra can be used to detect the group that has similar lifestyle, habit or behavior patterns. Semantic trajectory patterns of each moving object are mined firstly. Then, the time-weight based pattern similarity measurement is designed. After that, a hierarchical clustering method with pruning strategy is proposed, where each cluster represents the common behavior patterns from moving objects. Finally, experiments on both real-world dataset and synthetic dataset demonstrate the effectiveness, precision and efficiency of DSTra.

Key words: semantic trajectory; staying duration; semantic trajectory pattern; pattern similarity; moving object clustering

收稿日期: 2015-09-01;

修回日期: 2016-11-04

基金项目: 国家自然科学基金项目(61402449,91546111,91646201);中国科学院重点部署项目(KGZD-EW-102-3-3);北京市教委重点项目(KZ201610005009);北京工业大学“17内涵发展定额——引进人才科研启动费” This work was supported by the National Natural Science Foundation of China (61402449, 91546111, 91646201), the Key Deployment Project of the Chinese Academy of Sciences (KGZD-EW-102-3-3), the Key Project of Beijing Municipal Education Commission (KZ201610005009), and the Connotation Development 2017—Introducing the Talents Scientific Research Foundation of Beijing University of Technology.

中图法分类号: TP311