2. 中国科学院大学, 北京 100049;
3. 新疆理化技术研究所 新疆民族语音语言信息处理实验室, 乌鲁木齐 830011
2. University of the Chinese Academy of Sciences, Beijing 100049, China;
3. Xinjiang Laboratory of Minority Speech and Language Information Processing, Urumqi Xinjiang 8300111, China
感应器、位置捕获和跟踪设备的广泛使用产生了大量的全球定位系统(Global Positioning System, GPS)数据,但是个人的GPS数据具有私密性,往往不易获得,而近几年图像识别技术的极大发展使交通系统卡口自动车牌识别(Automatic Number Plate Recognition, ANPR)[1]数据的可靠性大幅增强,且ANPR数据较GPS数据更易获得,包含的信息也更有价值。伴随车辆组是指具有相同或者相似轨迹的车辆群组,这种信息与人的关系紧密,可用于群体发现、频繁路径挖掘以及异常检测。挖掘GPS数据伴随模式的方法很多,并取得了长足的发展,然而ANPR数据与GPS数据相比具有采样点固定而时间戳不同的特点,在ANPR数据上应用GPS数据的挖掘方法需要作出一些修改,甚至有的方法并不适用。另外类ANPR数据伴随模式挖掘的研究还比较少,现有的少数的针对类ANPR数据伴随模式挖掘的方法也存在性能上的缺陷。因此本文提出一种针对类ANPR轨迹数据共现次数特征的方法(Trajectory Based Density-Based Spatial Clustering of Applications with Noise,TB-DBSCAN)挖掘轨迹数据中采样点不同但采样点距离近且轨迹相似的伴随车辆组。本文的主要贡献是:1)借鉴GPS轨迹数据相似度计算方法,提出一种新的方法衡量类ANPR轨迹数据中共现的次数作为轨迹的相似度,该方法综合考虑了ANPR轨迹的地点、方向和时间特征。2)基于轨迹的相似度,运用基于密度的空间聚类(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法[2]方法有效挖掘类ANPR数据的伴随车辆组。
1 研究现状挖掘轨迹数据伴随模式的研究从数据类型可以分为两类:基于GPS数据和基于ANPR数据。
1.1 基于GPS数据伴随模式是指具有相同或者相似轨迹的移动对象群体,伴随模式的定义经历了从Flock[3]、Convoy[4]到Swarm[5]的衍变,这三者的区别主要在于“相近的空间距离”以及“共同移动一段时间”这两个概念定义上的区别。
构成伴随模式的移动对象其轨迹是相似的,那么可以通过衡量轨迹的相似度挖掘伴随模式[6]。CPD(Closest-Pair Distance)以轨迹间欧氏距离[7]的最小值作为轨迹间的距离;SPD(Sum-of-Pairs Distance)[8]使用两条轨迹对应点的距离之和衡量两条轨迹的相似度,要求两条轨迹具有相同长度或者截取相同长度; 但是这一约束在应用中难以实现,DTW(Dynamic Time Wrapping)[9]改善这一约束,其基本思想是可以对某些点重复多次以获得最优的点与点的对应效果,再通过对应点欧氏距离计算轨迹相似度。以上方法将每一个点都看作正常的数据,但是现实中噪声数据往往是不可避免的,如何降低噪声数据对结果的影响也是不可忽视的问题。将轨迹数据看作一个序列,找出其中最长共同子序列(Longest Common Sub Sequence,LCSS)[10],则可衡量轨迹的相似程度,这个方法需要一个匹配阈值α和一个时间阈值β,由于不需要轨迹中所有的点都有匹配,这在一定程度上降低了噪声的影响。与LCSS寻找最长共同子序列相反,实时序列编辑距离(Edit Distance on Real Sequence,EDR)[11]借鉴编辑距离的思想,通过轨迹中不同部分的大小来衡量轨迹的相似程度。ERP(Edit distance with Real Penalty)算法[12]则综合了DTW算法和EDR算法,该算法使用恒定参考点计算距离。
利用最小边界矩形(Minimum Bounding Rectangle, MBR)[13]计算轨迹的距离主要考虑轨迹端点,轨迹距离就是构成最小边界矩形的距离,如图 1(a)所示。计算方法如下:
$ \begin{array}{l} {D_{{\rm{MBR}}}} = \\ \sqrt {{{\left( {\Delta \left( {\left[ {{x_l}{\rm{,}}{x_u}} \right]{\rm{,}}\left[ {{{x'}_l}{\rm{,}}{{x'}_u}} \right]} \right)} \right)}^2} + {{\left( {\Delta \left( {\left[ {{y_l}{\rm{,}}{y_u}} \right]{\rm{,}}\left[ {{{y'}_l}{\rm{,}}{{y'}_u}} \right]} \right)} \right)}^2}} \end{array} $ |
$ \begin{array}{l} \Delta \left( {\left[ {{x_l}{\rm{,}}{x_u}} \right],\left[ {{{x'}_l}{\rm{,}}{{x'}_u}} \right]} \right) = \\ \quad \left\{ {\begin{array}{*{20}{l}} {0,}&{\left[ {{x_l}{\rm{,}}{x_u}} \right] \cap \left[ {{{x'}_l}{\rm{,}}{{x'}_u}} \right] \ne 0}\\ {{{x'}_l} - {x_{\rm{u}}},}&{{{x'}_l} > {x_u}}\\ {{x_l} - {{x'}_u},}&{{x_l} > {{x'}_u}} \end{array}} \right. \end{array} $ |
将豪斯多夫距离(Hausdorff Distance)运用在轨迹距离方面就产生了轨迹豪斯多夫距离(Trajectory-Hausdorff Distance)[14],如图 1(b)所示,该方法对轨迹中的每一段作如下处理:
$ {D_{{\rm{Hausdorff}}}} = {\omega _1}{d_ \bot } + {\omega _2}{d_\parallel } + {\omega _3}{d_\theta } $ |
其中:
最小边界矩形距离与豪斯多夫距离相比,豪斯多夫距离的计算较为复杂,最小边界矩形距离只考虑轨迹段的端点,豪斯多夫距离还考虑了轨迹段的方向差异与长度差异,更能标识轨迹间的相似度。而在伴随车辆组的挖掘中,轨迹段端点相同并不代表轨迹中移动对象的伴随,因此豪斯多夫距离更适用于伴随车辆组的挖掘。
1.2 基于ANPR数据Convy[4]的概念也可用于ANPR数据,文献[1]中将Convy的概念引入ANPR数据,并运用聚类的方法挖掘伴随车辆组。
挖掘ANPR数据中的伴随模式,符合伴随模式的移动对象在多个采样点共现,这些采样点构成的序列在这组移动对象的轨迹中是频繁的,将挖掘伴随车辆组转化为利用关联分析算法挖掘轨迹序列频繁模式。利用FP-Growth算法结合滑动时间窗口[15-16]以减少阶段数据量挖掘伴随车辆组取得较好的效果,FP-DTC(FP-Growth to Discover Travelling Companions)[17]算法通过Spark框架优化了FP-Growth算法。但是对于ANPR数据,该类方法以移动对象作为索引将ANPR数据转化为事务集[16]进行挖掘有两个缺点:1)任意两个对象其轨迹数据往往只有一小部分轨迹序列相同,也就是共享前缀少,那么构建FP-Tree就需要为每条事物建立分支,造成内存的大量消耗。2)挖掘不同时间段的ANPR轨迹数据,都需要转化为事务集并重新构建FP-Tree,频繁地构建FP-Tree则造成效率降低。
点伴随[18]则以一个采样点(如一个摄像头)的数据作为挖掘单元来挖掘动态ANPR数据的伴随车辆组,但是对同一个伴随车辆组的对象分别通过距离特别相近的采样点(比如并行车道的两个摄像头)的情形不能有效挖掘,缺乏对采样点距离的考虑。
2 挖掘伴随模式 2.1 问题定义及分析类ANPR数据集包含移动对象集ODB={o1, o2, …, on}和轨迹数据集
如图 2所示,通过两个移动对象的轨迹tDB1、tDB2可以看出两者共同在采样点l1点和l2点出现,在l1为同时出现,在l2出现的时间在T1范围内,比较相近。在A1、A2区域距离比较近,而出现的时间也在T2、T3内。
这样的轨迹在现实生活中符合伴随模式,但是点伴随方法对于这样的数据并不能有效地挖掘。因此本文提出基于轨迹共现次数的轨迹相似度,其中引入轨迹豪斯多夫距离处理距离特别相近的采样点,豪斯多夫距离不仅衡量了采样点的地理距离,同时可以考虑采样点周围轨迹的相似度。基于该相似度,运用DBSCAN方法进行聚类,与FP-Growth方法相比具有较优的效率。图 3为本文方法的总体流程。
ANPR数据共现并不是严格意义上的在同一地点同一时间出现,也要考虑相近位置相近时间的共现。对于类ANPR数据,以移动对象ok建立索引,按照时间戳排序,得到移动对象的轨迹数据tDBk。首先处理轨迹中编号相同的点,比较两者的时间戳差值是否在设定的时间差阈值τ内,若是则计共现次数加1。其次遍历编号不相同的点,两两比较其豪斯多夫距离的差值,若小于设定的距离阈值ω,比较两者的时间戳差值是否符合时间差阈值τ,若都符合阈值,则计共现次数加1。最终对共现次数取倒数,则可以表示移动对象彼此间的距离。
算法 1 计算轨迹相似度。
输入 数据集
输出 轨迹间的共现次数。
1) scanTDB(数据集
for tDBk in
for tDBj>k in TDBj=1, 2, 3, …, n
n=trajectorySimilarity(tDBk,tDBj, 时间差阈值τ,距离阈值ω)
return n
2) trajectorySimilarity(tDBk,tDBj, 时间差阈值τ,距离阈值ω)
n=0
for pnk in tDBk
if lnk of pnk contained by pmj of tDBj
if timeDistance(pnk,pmj) < 时间差阈值τ
n=n+1
//在轨迹tDBj中查找时间戳与pnk时间戳在时间差阈值τ
//内的pmj
else C=queryCloseL(pnk,tDBj)
for each pmj in C
//计算在时间差阈值τ内的点构成的豪斯多夫距离
if HausdorffDistance(pnk,pmj) < 距离阈值ω
n=n+1
return n
2.3 移动对象聚类轨迹相似程度作为移动对象之间的距离,可以对移动对象进行聚类。聚类的方法采用基于密度的DBSCAN算法,该算法需要两个参数:扫描半径ε和最小包含点数minPts,DBSCAN算法的几个定义如下:
ε邻域 给定对象半径为ε内的区域称为该对象的ε邻域。
核心对象 如果给定对象ε邻域内的样本点数大于等于minPts,则称该对象为核心对象。
直接密度可达 对于样本集合D,如果样本点q在p的ε邻域内,且p为核心对象,则对象q从对象p直接密度可达。
密度可达 对于样本集合D,给定一串样本点p1, p2, …, pn,p=p1,q=pn,对象pi从pi-1直接密度可达,则对象q从对象p密度可达。
密度相连 存在样本集合D中的一点o,若对象o到对象p和对象q都是密度可达,则p和q密度相连。
DBSCAN算法通过检查数据集中每个对象的ε邻域搜索簇,如果对象p的ε邻域包含的点数多于minPts,则创建一个以p为核心对象的簇;之后DBSCAN迭代地聚集从核心对象直接密度可达的对象,并合并一些密度可达簇;当所有对象都被归于某个簇,算法结束。
算法 2 移动对象聚类。
输入 数据集D、半径ε、最小包含点数minPts;
输出 移动对象类簇集合。
1) DBSCAN(数据集D,半径ε,最小包含点数minPts)
Cid=0 //类别标示
for each unvisited point P in dataset D //遍历
mark P as visited //已经访问
NeighborPts=regionQuery(P,ε) //计算这个点的邻域
if sizeof(NeighborPts) < minPts //不能作为核心点
mark P as NOISE //标记为噪声数据
else
//作为核心点,根据该点创建一个类别
Cid=next cluster
expandCluster(P,NeighborPts,Cid,ε,minPts)
//根据该核心对象扩展类别
2) expandCluster(P,NeighborPts,Cid,ε,minPts)
add P to cluster Cid //扩展类别,核心对象先加入
for each point P′ in NeighborPts
//然后针对核心对象ε邻域内的点
if P′ is not visited
//如果该点没有被访问
mark P′ as visited //进行访问
NeighborPts′=regionQuery(P′,ε)
//如果该对象为核心对象,则扩充该类别
if sizeof(NeighborPts′)>=minPts
NeighborPts=NeighborPts joined with NeighborPts′
if P′ is not yet member of any cluster
//如果邻域内点不是核心点,并且无类别,比如噪
//声数据,则加入此类别
add P′ to cluster Cid
3) regionQuery(P,ε) //计算ε邻域
return all points within P′s ε-neighborhood
3 实验为了验证所提方法对车辆伴随模式挖掘的准确性和有效性,本文进行了多组实验。采用的数据为中国某省份交通系统数据,该数据经过融合、清洗,最终形成类ANPR数据。为评估本文所提出的算法,通过与FP-Growth算法的实验比较,分析算法的性能和有效性,实验机器系统为Windows 7 64位,CPU型号为Intel Core i7-6700 CPU 3.40 GHz, 内存16 GB,JDK版本为1.80,其中使用的数据库为MongDB3.0及Redis3.0.5。
本文提出的方法有4个参数,分别是计算轨迹相似度的时间差阈值τ、距离阈值ω,DBSCAN算法的扫描半径ε和最小包含点数minPts。这些参数的选择应该根据应用场景估算。对于类ANPR数据的伴随模式,伴随车辆的距离一般不超过1 km,1 km地理距离经纬度的差距约为0.01,据此估算出两段首位端点各相差0.01时轨迹段的豪斯多夫距离为0.05;由于本文数据采集区域大,访问一个地点的时间差距不超过60 km;扫描半径ε代表两个移动对象可以判定为伴随模式的最小距离,若两个移动对象有20个点符合共现的要求则视为伴随模式,则扫描半径ε应设为0.05;最小包含点数minPts则对应伴随模式包含移动对象的个数,按照最小值则为2。
3.1 性能测试与分析为检验此方法的效率,本文通过与FP-Growth算法进行比较以评估该算法的性能。本文选择了不同时间段的数据比较在不同数据规模下的效率,各实验数据集描述如表 1。
不同规模数据集的实验结果如图 4所示,对比发现在相同数据量下,本文算法运行时间要少于FP-Growth算法。主要有以下原因:1)本文算法是基于轨迹特征的聚类方法,轨迹特征只需要计算一次,在实际应用中可以采用增量方法,而FP-Growth算法基于FP-Tree,对不同的数据集都要建立FP-Tree。2)对于类ANPR数据而言,在数据集中共享前缀的事物比较少,造成FP-Tree要为每一条事物建立分支,使算法内存消耗增大,造成在数据量较大时运行时间急剧增大,而本文的算法只需要存储轨迹特征值。3)轨迹特征值数据结构简单,方便存储,可做增量处理(实验中存储在Redis中,一种内存键值数据库,便于管理,也可持久化),而FP-Tree结构复杂,只能存储于内存中。
表 2为在不同数据规模下FP-GROWTH算法和本文算法挖掘出的伴随模式个数及平均大小对比。
图 5对比显示了表 2第6组伴随模式的可视化效果, 其中非伴随车辆组轨迹颜色为灰色,不同伴随车辆组轨迹以不同的非灰颜色进行着色,其轨迹为实线,所有非伴随车辆组轨迹为虚线。图 5(a)、(c)为FP-Growth算法的结果,图 5(b)、(d)为本文TB-DBSCAN算法的结果,其中图 5(a)、(b)分别显示了两种算法结果的整体情况,图 5(c)、(d)分别显示了图 5(a)、(b)中A区域的细节情况。图 5(a)中实线轨迹标识FP-Growth挖掘的第一个伴随车辆组,图 5(c)中虚线轨迹标识第二个伴随车辆组;图 5(b)中虚线轨迹标识本文算法挖掘出的伴随车辆组轨迹。
从图 5(a)、(b)对比看出FP-Growth算法没有挖掘出本文算法挖掘出的伴随模式,而且图(a)显示挖掘出的模式内部轨迹并不相似,图(c)、(d)对比显示了FP-Growth算法判定为伴随车辆组的轨迹在本文算法中为噪声数据,而实际上图(c)中的虚线轨迹部分并不是伴随车辆组,图(c)中的伴随车辆组其轨迹数据端点相同,但是序列是相反的,这里体现使用豪斯多夫距离区分轨迹段方向差异的优势。
以上对比表明本文算法相比FP-Growth算法,能够区分具有相似轨迹但是移动方向不同的移动对象,避免如图 5(b)中轨迹数据的干扰,更能有效区分噪声数据和伴随车辆组。同时由于文中2.2节共现的定义,对于在小型区域内移动的对象不完全在相同地点出现而在距离较近地点出现的轨迹也可进行挖掘,从而保证合理模式的挖掘。
4 结语本文论述并借鉴了比较成熟的基于GPS数据伴随模式挖掘方法,鉴于现有类ANPR数据伴随车辆组挖掘方法的缺陷,提出一种统计类ANPR轨迹数据共现的方法,该方法从整体轨迹出发,不仅考虑的了ANPR轨迹中编号相同的点,还通过豪斯多夫距离衡量编号不同采样点周围的子轨迹相似度,有效表征了ANPR轨迹的相似度,并基于此相似度通过聚类方法挖掘伴随车辆组,改善挖掘效果。但是在实验过程中发现将轨迹归纳为共现次数这一特征也有缺陷,在后续的研究中将探索更有效的轨迹特征化方法。另外类ANPR数据量巨大,在后续工作中将采用Spark框架进行并行化处理。
[1] | HOMAYOUNFAR A, HO A T S, ZHU N, et al. Multi-vehicle convoy analysis based on ANPR data[C]//Proceedings of the 4th International Conference on Imaging for Crime Detection and Prevention. Piscataway, NJ:IEEE, 2011:38. |
[2] | ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA:AAAI Press, 1996:226-231. |
[3] | GUDMUNDSSON J, VAN KREVELD M. Computing longest duration flocks in trajectory data[C]//Proceedings of Annual ACM International Symposium on Advances in Geographic Information Systems. New York:ACM, 2006:35-42. |
[4] | JEUNG H, YIU M L, ZHOU X, et al. Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1068-1080. DOI:10.14778/1453856 |
[5] | LI Z, DING B, HAN J, et al. Swarm:mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 723-734. |
[6] | TANG L, ZHENG Y, YUAN J, et al. A framework of traveling companion discovery on trajectory data streams[J]. ACM Transactions on Intelligent Systems and Technology, 2014, 5(1): 1-34. |
[7] | DEZA E, DEZA M M. Encyclopedia of Distances[M]. Berlin: Springer, 2009: 94. |
[8] | AGRAWAL R, FALOUTSOS C, SWAMI A. Efficient similarity search in sequence databases[C]//Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms. Berlin:Springer, 1993:69-84. |
[9] | YI B K, JAGADISH H V, FALOUTSOS C. Efficient retrieval of similar time sequences under time warping[C]//Proceedings of the 14th International Conference on Data Engineering. Piscataway, NJ:IEEE, 1998:201-208. |
[10] | VLACHOS M, KOLLIOS G, GUNOPULOS D. Discovering similar multidimensional trajectories[C]//Proceedings of the 18th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2002:673-684. |
[11] | CHEN L, ÖZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2005:491-502. |
[12] | CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]//Proceedings of the 13th International Conference on Very Large Data Bases. Toronto:VLDB Endowment, 2004, 30:792-803. |
[13] | JEUNG H, YIU M L, JENSEN C S. Trajectory Pattern Mining[M]. New York: Springer, 2011: 143-177. |
[14] | LEE J G, HAN J, WHANG K Y. Trajectory clustering:a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2007:593-604. |
[15] | 方艾芬, 李先通, 蔄世明, 等. 基于关联规则挖掘的伴随车辆发现算法[J]. 计算机应用与软件, 2012, 29(2): 94-96. (FANG A F, LI X T, MAN S M, et al. A discovery algorithm of traveling companions based on association rule mining[J]. Computer Applications and Software, 2012, 29(2): 94-96.) |
[16] | HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record, 2000, 29(2): 1-12. DOI:10.1145/335191 |
[17] | 曹波, 韩燕波, 王桂玲. 基于车牌识别大数据的伴随车辆组发现方法[J]. 计算机应用, 2015, 35(11): 3203-3207. (CAO B, HAN Y B, WANG G L. Discovery method of travelling companions based on big data of license plate recognition[J]. Journal of Computer Applications, 2015, 35(11): 3203-3207. DOI:10.11772/j.issn.1001-9081.2015.11.3203) |
[18] | 朱美玲, 王雄斌, 张守利, 等. 基于大规模流式车牌识别数据的即时伴随车辆发现[J]. 中国科学技术大学学报, 2016, 46(1): 47-55. (ZHU M L, WANG X B, ZHANG S L, et al. Instant traveling companion discovery based on large scale streaming ANPR data[J]. Journal of University of Science and Technology of China, 2016, 46(1): 47-55.) |