智能交通系统(intelligent transportation system, 简称ITS)是软件工程技术的典型应用领域.随着大数据时代的到来, 智能交通应用必然会产生重大变化, 新型交通应用系统的研发和部署, 也必将对大数据软件工程技术的发展起到极大促动.目前, 各种交通信息采集技术广泛应用于城市交通, 持续地产生海量且实时的时空数据.这些海量数据是交通的规划、管控、预测、引导的信息源和基础, 同时也带来了新的问题和困境:海量实时时空数据的潜在价值还没有得到有效的分析、挖掘和应用.为此, 本文重点关注一类典型的交通大数据——车牌识别流式大数据(automatic number plate recognition data, 简称ANPR)的实时分析和挖掘方法.车牌识别数据源自城市道路路口安装的交通摄像头, 提供了全天候的车辆行驶位置监视能力.本文将在车牌识别流式大数据基础上, 瞄准伴随车辆即时检测这一新兴的智能交通应用, 聚焦于伴随车辆检测的核心算法和软件实现.

1 引言

当前, 记录对象移动模式的时空数据在规模上迅速膨胀.在时空数据中发现移动对象的移动模式具有重要的研究价值.车辆是日常生活中最常见的移动对象之一.在一段时间内, 一起移动的车辆组群所具有的移动模式通常被称为车辆伴随模式.近年来, 车辆伴随模式的发现逐渐成为国内外学者关注的热点研究问题^[1-8], 相关的研究成果已经被广泛应用到智能交通等领域^[7].

当前, 移动车辆伴随模式的发现研究大多基于GPS数据^[1-8].GPS数据由安装在车辆上的GPS设备按照固定的时间间隔产生并回传.没有安装GPS设备或者设备没有开启的车辆不会产生GPS数据.在某些特殊场合下, 如车辆跟踪、犯罪嫌疑人出逃等, 嫌疑人通常会关闭甚至拆掉GPS设备以防止被公安机关发现并拦截.这使得基于GPS数据实现的车辆伴随模式发现方法无法满足上述场景的需求.

与GPS数据不同, 车牌识别数据源自城市道路路口安装的交通摄像头, 这些摄像头能够不间断采集过往车辆的信息, 包括车牌号码和采集时间.这些信息以流数据的形式传输到交通管理部门的数据中心, 用于进一步的分析和挖掘.车牌识别数据提供了全天候的车辆行驶位置监视能力, 是交通大数据的一类典型代表.当前, 我国大型城市安装的交通摄像头已经超过5 000台, 且数量仍在持续增加.摄像头采集车辆信息的速率取决于摄像头的拍摄频率, 最高可以达到每秒采集一次, 即, 高峰时期流式车牌识别数据的速率可达5 000条每秒.假设每台摄像头每天采集车辆信息的平均速率为高峰期的1/3, 则每天采集数据的总数可以达到1.44亿条, 一年的数据量可以达到PB级.

基于GPS数据, 现有研究工作已经抽象并总结了多种典型的车辆伴随模式, 包括Flock^[1-3], Convoy^{[4, 5]}, Swarm^[6], Traveling Companion^[7], Platoon^[8]等.这些模式的目的都是为了发现一段时间内一起移动的车辆群组, 但是不同模式对于伴随车辆的时空约束定义有较大不同.在时间约束上, Flock和Convoy模式要求伴随车辆经过的时间点具有连续性; Swarm和Traveling Companion对时间点的连续性没有要求; Platoon模式要求车辆组群在若干时间段内一起移动.每个时间段由不少于δ个连续的时间点组成, 且时间点总数不少于k.Platoon模式实质上是一种比上述几种模式更为通用的伴随模式, δ的不同取值可以得到上述几种不同的伴随模式.例如, 设Platoon模式实际经过了l个时间点, 当δ > l/2时, Platoon模式的时间约束与Flock/Convoy一致, 当δ=1时, Platoon模式的时间约束与Swarm/Traveling Companion一致^[8].此外, 在空间约束方面, Flock要求车辆处于圆盘形的地理区域, 而其他工作将这一约束放松至密度可达.

本文的前期工作是基于历史车牌识别数据和流式车牌识数据开展了Traveling Companion伴随模式的发现研究.首先, 基于历史车牌识别数据, 通过借鉴频繁项集挖掘经典算法Apriori算法设计了基于Spark的并行伴随车辆发现算法, 并将其应用于社区拼车^[9].随后, 我们又尝试从流式车牌识别数据中即时发现伴随车辆^[10].为实现这一目标, 我们提出了点伴随的概念, 用于描述一起通过单个摄像头的车辆组群, 并设计了点伴随检测的并行优化算法.

在前期工作的基础上, 本文聚焦于车牌识别数据流上的Platoon伴随模式的发现问题, 将其映射为带有时空约束的频繁序列挖掘问题, 并提出了相应的伴随车辆发现算法PlatoonFinder, 以在车辆通过交通摄像头时即时发现并输出车辆的Platoon伴随模式.算法的主要贡献包括:

(1) 基于车牌识别流式大数据的特点, 本文在借鉴相关工作的基础上重新定义了Platoon伴随模式;

(2) 与传统的频繁序列挖掘算法相比, PlatoonFinder算法在计算频繁序列时考虑了自定义的时空约束:首先, 要求频繁序列的每个元素在序列数据库中以足够接近的时间出现; 第二, 要求频繁序列由若干子序列组成, 每个子序列的元素在序列数据库中相邻出现;

(3) 本文一方面压缩了参与计算的序列数据库, 另一方面在构建数据库时融入了伪投影技术, 从而降低了计算复杂度, 提升了算法的性能.实验结果表明, PlatoonFinder算法的平均延时明显低于真实情况下车牌识别数据之间的最小时间间隔.

2 相关工作 2.1 伴随模式发现

研究人员进行了大量针对伴随模式的研究与探索, 提出了不同条件下的伴随模式定义及挖掘算法.以提出的时间为顺序, 典型的工作包括Flock^[1-3], Convoy^{[4, 5]}, Swarm^[6], Traveling Companion^[7], Platoon^[8]等. Flock和Convoy定义了一种强时空约束的伴随模式.Flock要求车辆组群在不少于k个连续时间点上处于一个足够小的圆形地理空间内(k可称为时间点总数阈值).Convoy将Flock的空间约束扩展为密度可达的地理空间. Swarm和Traveling Companion可以视作同一种伴随模式^[7].该模式放宽了Convoy的时间约束, 要求车辆组群在k个时间点(不一定连续)上处于密度可达的地理空间内.因此, 如果一组车辆组群的移动模式符合Flock模式, 则一定符合Convoy模式, 也一定符合Swarm和Traveling Companion模式.Platoon伴随模式也要求车辆组群在k个时间点上处于密度可达的地理空间.具体的说, Platoon模式是指车辆组群在若干个长度至少为δ(δ为正整数)的连续时间点下处于某种地理位置区域内, 且时间点的总和不少于k个.不妨设Platoon模式实际的时间点总数为l, 满足l≥k.Platoon伴随模式是更通用的模式, 用户可以通过设定δ值得到上述伴随模式.当δ > l/2, 得到的是Convoy模式; 而当δ=1时, 得到的是Swarm/Traveling Companion模式^[8].此外, Platoon伴随模式可以根据设定的阈值细化出不同于上述各种的模式.例如1 < δ < l/2时, 可以得到局部时间连续的伴随模式.因此, Platoon伴随模式既可以根据不同场景挖掘Convoy模式和Swarm/Traveling Companion模式, 也可以根据不同需求挖掘出局部时间连续模式和全局时间连续模式.这些是Flock, Convoy, Swarm, Traveling Companion等任何一个模式无法实现的.

表 1对比了上述5种伴随模式的相关工作及本文的工作.

除了上述伴随模式发现工作, 还有相当一部分研究人员专注于移动对象的聚类^[11-14].Kalnis试图找到两个连续的时间戳内有大部分的重叠移动对象^[11].Li等人采用微聚类(micro-clustering), 在对移动对象进行聚类时既考虑了移动对象的当前位置又考虑了短期内未来的位置^[12].Kriegel等人利用了模糊距离函数进行移动对象的聚类^[13].Jensen等人提出了一种增量式的方法在一段时间内对移动对象进行聚类, 减少了计算开销^[14].

此外, 近年来, 更多人开始关注大规模轨迹数据的研究.Zheng使用一系列的技术手段, 力求提高在大规模静态轨迹数据集中对移动对象组群聚类的性能^[15].Zhang提出一种聚类检索算法, 通过查找一个由移动对象组群组成的时空图来检索移动对象的聚类模式^[16].Yoo尝试使用MapReduce框架来达到更优的处理效率, 同时也提出了一种划分策略来避免数据之间关系的丢失^[17].

然而, 上述的大部分研究方法针对静态GPS数据设计, 无法直接应用于流数据的处理.流数据具有实时到达、不可预知、没有边界等特点, 流数据的这些特性导致了流数据难以存储且对实时性要求很高.显然, 静态数据方法无法满足这些需求.但在交通领域的应用中, 数据通常都是以流的形式提供的.因此, 近年来, 越来越多的学者开始研究流式交通数据的处理.除了Tang提出的流式轨迹数据上Traveling Companion模式的发现框架^[7]外, Yu针对流式轨迹数据研究了一种基于密度的聚类算法, 尝试实时地发现轨迹组群^{[18, 19]}.本文聚焦于一种特殊的流式交通数据——流式车牌识别数据, 根据前文的分析, 这种数据的到达率可以到达5 000条/秒甚至更高, 且高峰时期每台交通摄像头可以每秒产生一条数据.因此, 本文面临的问题是如何在如此高的数据到达速率下即时发现伴随车辆, 即:每当车辆通过交通监控摄像头时, 本文的方法能够快速发现该车辆的伴随车辆, 并将结果输出出来.根据流式车牌识别数据的特性, 本文方法的延时应该低于真实数据之间的最小时间间隔(1s), 以避免因数据堆积导致的延时急剧增加.而目前, 所有的相关工作都针对的是流式GPS数据并且取得了很大的进步, 虽然无法解决本文的问题, 但为本文的研究提供了坚实的基础.

2.2 频繁序列挖掘

频繁序列挖掘算法可以分为两类:基于Apriori的算法(Apriori-based algorithms)和基于投影数据的算法(projection-based algorithms).基于Apriori的典型算法包括AprioriAll^[20], AprioriSome^[20], GSP^[21], SPADE^[22], SPAM^[23]等, 这类算法的缺点是需要构建规模庞大的候选集; 基于投影数据的典型算法包括FreeSpan^[24], PrefixSpan^[25], CloSpan^[26]和BIDE^[27]等, 这类算法通过构造投影数据库而非候选集, 显著提升了算法的性能.此外, 研究人员开始关注带有约束的频繁序列挖掘问题.Helen等人提出了多维频繁序列的概念(multi-dimensional sequential pattern), 并提出了相应的挖掘算法^[28].多维频繁序列数据库与传统序列数据库的区别在于, 前者除了有SID和序列之外还包含若干属性.Pei等人归纳了频繁序列挖掘中存在的7个约束, 包括项约束(如用户只对某些项感兴趣)、长度约束(用户对频繁序列的长度约束)、超集约束(是否存在频繁序列α⊒β)、聚合约束(如频繁序列的各项和、平均值、最大最小值、方差等的约束)、正则表达式约束(对某些项的条件约束)、持续时间约束(频繁序列的各项必须在某个时间段内出现)以及间隔约束(频繁序列相邻项的时间间隔约束)^[29].而本文涉及的时间约束并没有包含在以上7种约束之内.另外, Chueh深入研究了带有时间间隔约束的频繁序列挖掘问题, 并提出了相关算法^[30].

为了提高算法性能, 部分学者对频繁序列挖掘算法进行了并行优化^[31-36].Demiriz基于SPADE提出了分析网站点击流的并行化算法webSPADE^[31].Guralnik等人提出了基于分布式内存的频繁序列挖掘并行算法^[32].Ma等人提出了一种基于分布式内存系统的闭频繁序列挖掘并行算法PFCSeq^[33].每个处理程序独立挖掘本地的闭频繁序列, 处理器之间交互的减少, 显著降低了算法的时间消耗.Qiao等人提出了一种轨迹序列挖掘算法PartSpan, 该算法使用了前缀投影技术、并行技术和候选集剪枝技术降低计算开销^[34].Yu等人利用MapReduce框架将BIDE算法并行化^[35].Kessl提出了一种基于概率模型的静态负载均衡并行算法挖掘频繁序列^[36].

以上工作都是频繁序列挖掘领域的典型工作, 为本文的算法奠定了良好的基础.本文的定理1即是根据Clospan算法^[27]的公共前缀引理(common prefix)和偏序引理(partial order)而得.然而, 以上工作并没有涉及本文提出的时空约束:没有考虑频繁序列各元素在序列中的相邻位置关系, 没有考虑频繁序列各元素在不同序列中出现的时间间隔.因此, 本文在借鉴已有工作的基础上设计了能够挖掘带有时空约束的频繁序列算法.该算法为基于车牌识别流式大数据的Platoon伴随模式发现而设计, 在未来的工作中, 我们将进一步研究带有时空约束的频繁序列挖掘通用算法, 使之得到更广泛的应用.此外, 在未来的工作中, 我们还将尝试利用并行等优化手段进一步提高算法的性能.

3 问题定义及分析

近年来, 针对运钞车、出租车等特殊车辆的罪案时有发生.犯罪分子通常会跟踪这类车辆至隐蔽的地点并实施抢劫.当车辆经过交通摄像头时, 即时检测其可疑跟踪车辆并向被跟踪车辆发出警报, 可以有效防止此类案件的发生.如图 1的3幅子图所示, 运钞车依次经过交通摄像头c₁, c₂, c₃, c₄, c₅, c₆, c₇, …, c_n.每当运钞车经过摄像头时, 即时发现其伴随车辆, 是检测运钞车的可疑跟踪车辆的有效手段.

Platoon模式要求车辆组群在若干时间段内一起移动.每个时间段由不少于d个连续的时间点组成, 且时间点总数不少于k.在车牌识别数据下, 移动车辆在不同时间点下的数据对应了不同的交通摄像头.因此, Platoon模式实际经过的时间点总数代表了实际经过的交通摄像头, 不妨设为l个.这l个摄像头按时间顺序排列, 且由若干位置相邻的摄像头序列组成.因此, δ实际上是位置相邻的摄像头子序列的长度阈值.图 1描绘了3组不同的伴随车辆, 为了便于理解, 将3组车辆的移动方式展现在不同的子图中.根据相关工作的分析, 不妨设车辆伴随模式经过的交通摄像头总数阈值为4(k=4, 即伴随车辆至少经过k个交通摄像头), l是移动模式实际经过的交通摄像头数量.图 1(1)刻画了运钞车p₁和车辆p₂在4个相邻交通摄像头下伴随; 图 1(2)刻画了运钞车p₁和车辆p₃在2个长度为2的相邻交通摄像头下伴随; 图 1(3)刻画了运钞车p₁和车辆p₄在4个不相邻交通摄像头下伴随.如果δ取值为1, 图 1(1)~图 1(3)所示的3组伴随车辆都将被返回给用户; 如果δ取值为2, 图 1(1)、图 1(2)所示两组伴随车辆将被返回给用户; 如果δ取值为大于l/2的任意整数, 图 1(1)所示伴随车辆将被返回给用户.

定义1(车牌识别数据记录, ANPR).一条车牌识别数据记录r可以由三元组r=(c, p, t)来表示, 其中, c代表交通摄像头ID, p代表车牌号码, t是时间戳.一条车牌识别数据记录r=(c, p, t)表示车牌号码为p的车辆在t时刻经过摄像头c.

示例1:(CAM14115111, 京OA89**, 08:20:54), (CAM14115111, 京QE63**, 08:20:59) 是两条真实车牌识别数据记录, 其中, CAM14115111是交通摄像头ID.这两条数据代表着车辆京OA89**和京QE63**先后在时间08:20:54和08:20:59经过了ID为CAM14115111的交通摄像头.

目前, 基于GPS数据, 大量研究工作已经给出了各种伴随模式的定义.与车牌识别数据不同, GPS数据是从连续变化的时间、经纬度、速度等方面来描述车辆的信息.大部分研究工作都利用了GPS数据的经纬度属性来计算伴随模式, 如基于密度的聚类^{[3, 6-8]}和距离计算^{[2, 4, 5]}.还有部分工作甚至利用了GPS数据的速度信息和角度信息进行计算^{[1, 4, 5]}.然而由前文的分析及定义1可知:车牌识别数据是由分布在各个路口的交通摄像头自动产生的, 并不包含经纬度、速度以及角度等信息.因此, 适用于GPS数据的方法无法直接应用到车牌识别数据中.为此, 本文借鉴前期工作中提出的点伴随概念, 利用基于时间和摄像头的聚类给出了车牌识别数据集上的Platoon伴随模式的定义.

定义2(点伴随, moment companion).已知△t为时间阈值, 交通摄像头c在时刻t下点伴随可以被定义为如下形式:

$ MC(c, t, \Delta t) = \{ r.p|r.c = c \wedge t-\Delta t \le r.t \le t\} . $

示例2:以图 1(3)为例, 交通摄像头c₁下关于某时间点存在点伴随{(c₁, p₂, t₂), (c₁, p₁, t₁)}, 其中, t₂是车辆p₂经过交通摄像头c₁的时间, t₂-t₁≤△t.同理可知, 交通摄像头c₃, c₅和c₇下也存在包含车辆p₁和p₂的点伴随.

定义3(Platoon伴随模式, platoon companion pattern).已知车辆数量阈值δ_veh, 位置相邻的交通摄像头长度阈值δ和交通摄像头总数阈值δ_cam, 时间阈值△t, (P, C, T)如果满足以下条件, 则称其为车牌识别数据上的Platoon伴随模式:

(1) |P|≥δ_veh, |C|≥δ_cam, |C_i|≥δ;

(2) 每个(P, C_i, T)满足:∀c_{i, j}∈C_i, 存在MC(c_{i, j}, t_{i, j}, △t), 满足P⊆MC(c_{i, j}, t_{i, j}, △t).

其中, P={p₁, p₂, …, p_m}是车牌号码集合; C=〈C₁, C₂, …, C_k〉是交通摄像头序列, 子序列${C_i} = \langle {c_{i, 1}}, {c_{i, 2}}, ..., {c_{i, {n_i}}}\rangle $是一组地理位置相邻的交通摄像头; T=〈T₁, T₂, …, T_k〉是时间戳序列, 子序列${T_i} = \langle {t_{i, 1}}, {t_{i, 2}}, ..., {t_{i, {n_i}}}\rangle $, 且满足:

${t_{1, 1}} < ... < {t_{1, {n_1}}} < ... < {t_{i, 1}} < ... < {t_{i, {n_i}}} < ... < {t_{k, 1}} < ... < {t_{k, {n_k}}}.$

定义4(封闭platoon伴随模式, closed platoon companion pattern).假设(P, C, T)是Platoon伴随模式, 如果∄C', T', C⊏C', T⊏T', 使得(P, C', T')是Platoon伴随模式, 则(P, C, T)是封闭Platoon伴随模式.

为了避免重复计算, 本文在车牌识别流式大数据下即时发现封闭Platoon伴随模式.

4 Platoon伴随模式发现算法 4.1 预备知识

频繁序列挖掘为本文的算法奠定了基础, 本节将简要介绍频繁序列挖掘的相关概念及经典算法.

设I={i₁, i₂, …, i_m}是项的集合, 则I的子集称为项集.序列s是一个有序项集数组, 即s=〈q₁, q₂, …, q_n〉(q_i⊆I, i=1, 2, …, n).序列数据库D是序列的集合, 其中每个序列都配有唯一的标识符, 记为SID.序列s的支持度是指序列数据库D中包含s的序列个数.如果序列s在D中的支持度超过了预定义的最小支持度, s称为频繁序列.如果序列数据库D中不存在频繁序列s', s⊏s'(⊏, ⊑用于连接序列, 表示前者是后者的子序列; 同理, ⊐, ⊒表示后者是前者的子序列), 且s'与s在D中具有相同支持度, 则频繁序列s称为闭频繁序列(closed frequent sequence).序列s在D中的投影数据库记为D_s={η|s'∈D, s'=α◊η}, 其中, s⊑α且∄α', s⊑α'⊑α.

频繁序列挖掘算法可以分为基于Apriori的算法(Apriori-based algorithms)和基于投影数据的算法(projection-based algorithms)^[37].基于投影数据的算法采用了分而治之的策略, 极大地降低了基于Apriori的算法构造候选子序列时产生的时空消耗.这类算法挖掘频繁序列的主要步骤如图 2所示.

1) 遍历序列数据库D, 生成所有的1-频繁序列(即, 长度为1的频繁序列);

2) 对每一个1-频繁序列s¹, 生成其在D的投影数据库${D_{{S^1}}}$;

3) 对每一个投影数据库${D_{{S^1}}}$重复上述步骤, 直至不存在1-频繁序列为止.

在车牌识别数据集R中, 任意车辆p_i的行驶轨迹都对应了一条交通摄像头序列${s_{{p_i}}} = \langle {c_{i, 1}}, {c_{i, 2}}, ..., {c_{i, n}}\rangle $:对任意元素c_{i, j}, 存在r_j∈R, r_j.p=p_i, r_j.c=c_{i, j}, 且元素c_{i, j}和c_{i, j+1}对应的车牌数据满足r_j.t < r_j+1.t.易知, c_{i, 1}, c_{i, 2}, …, c_{i, n}是车辆p_i依次经过的交通摄像头, r₁.t, r₂.t, …, r_n.t是经过时间.因此, 任意给定的车牌识别数据集R都可以映射成序列数据库$D = \{ {s_{{p_i}}}\} $, 车牌号码p_i是序列${s_{{p_i}}}$的SID.

基于上述分析, 本文将要求解的Platoon伴随模式发现问题映射为车牌识别数据流上的频繁序列挖掘问题.近年来, 频繁序列挖掘工作, 尤其是针对流数据的挖掘工作取得了许多进展^[38-41].然而, 现有的频繁序列挖掘算法并不能解决本文问题, 这是因为现有的频繁序列挖掘算法仅考虑了序列中元素的出现顺序, 而Platoon伴随模式则要求序列中元素要满足预定义的时空约束, 例如, 伴随车辆通过同一摄像头的时间应该足够接近.图 3直观地展示了这一区别.如图所示:从传统频繁序列的角度来看, 假设最小支持度为2, 则〈c₁, c₂, c₄, c₅〉和〈c₁, c₇, c₃, c₄〉都是频繁序列.而Platoon伴随模式的约束更为复杂:如图 3所示的Platoon伴随模式, 当δ_veh=2, △t=30s, δ=2, δ_cam=4时, 模式(P₁, C₁, T₁), P₁={p₁, p₂}, C₁=〈c₁, c₂, c₄, c₅〉, T₁=〈09:30:01, 09:34:01, 09:42:01, 09:47:01〉是Platoon伴随模式, 而模式(P₂, C₂, T₂), P₂={p₃, p₄}, C₁=〈c₁, c₇, c₃, c₄〉, T₁=〈09:30:01, 09:35:00, 09:40:00, 09:51:00〉却不是.这是因为c₁, c₇和c₄出现在车辆p₃和p₄序列的时间差分别为59秒、59秒和8分59秒(小于△t=30s).实际上, 如果δ=3则模式(P₁, C₁, T₁)也不再是Platoon伴随模式.原因如下:根据图 3所示的交通摄像头的地理位置关系, 〈c₁, c₂〉和〈c₄, c₅〉是两条长度为2的相邻摄像头序列; 而δ=3约束了相邻摄像头序列的长度不小于3.

4.2 PlatoonFinder算法

为了简明清晰地阐述算法, 提前定义一些符号.记当前窗口内车牌识别数据产生的序列数据库为curD.当新数据(c₀, p₀, t₀)到达, 如果curD已有车辆p₀的序列, 则将新数据附加到该序列尾部; 否则, 在curD中创建车辆p₀的新的序列.记加入新数据r₀=(c₀, p₀, t₀)后的序列数据库为curD₊.记序列数据库:

$\begin{array}{l} D_ + ^{{r_0}} = \{ s|s \in cur{D_ + } \wedge \exists r, r.c = {c_0}, {t_0} - {\rm{\Delta }}t \le r.t \le {t_0}, r \in s \wedge |s| \ge {\delta _{cam}}\}, \\ {D_ + } = \bigcup {D_ + ^{{r_0}}} . \end{array}$

设△t=2s, δ=2, δ_cam=3, 图 4举例说明了上述符号指代的内容, 加粗的数据项是新到达的数据记录.

图 5描述了本文提出的PlatoonFinder伴随模式发现算法的基本原理.

算法利用滑动窗口接受实时到达的车牌识别数据, 并对数据进行预处理, 得到按交通摄像头聚类的车牌识别数据集.假设任意新到达的数据r₀产生了新点伴随MC₀.根据新点伴随MC₀, 生成对应的序列数据库$D_ + ^{{r_0}}$.在序列数据库$D_ + ^{{r_0}}$中挖掘带有时空约束的频繁序列.最后, 根据新旧数据的更替更新缓存的结果.在序列数据库$D_ + ^{{r_0}}$中挖掘带有时空约束的频繁序列的思路如下:首先, 按照从大到小的时间顺序找出序列数据库$D_ + ^{{r_0}}$中所有互不包含的点伴随, 对每个点伴随MC₀的子集按照时间顺序寻找包含它的点伴随, 当找到一个包含它的点伴随MC_i时, 判断上一个包含它的点伴随MC_i-1对应的元素与MC_i对应的元素是否相邻, 并根据判断结果更新结果; 然后继续寻找包含MC的点伴随.以图 4为例, r₁=(c₁₁, p₁, 09:45:01) 和r₂=(c₁₂, p₈, 09:45:01) 是新到达的数据, 并且产生了两组新的点伴随MC₁={p₁, p₄, p₅, p₆}和MC₂={p₃, p₈}, p₂由于轨迹长度小于δ_cam而被抛弃.MC₁对应的序列数据库$D_ + ^{{r_1}} = \{ {s_{{p_1}}}, {s_{{p_4}}}, {s_{{p_5}}}, {s_{{p_6}}}\} $.在$D_ + ^{{r_1}}$中挖掘带有时空约束的频繁序列过程如图 6所示.

前文叙述了挖掘带有自定义时空约束频繁序列的思路.为了保障PlatoonFinder算法能够高效处理流数据, 本文提出了以下3个定理并融合了伪投影技术以优化整个计算过程.

定理1.已知存在封闭Platoon伴随模式(P, C, T), 当新数据到达时, 如果∃C', T'使得C⊏C', T⊏T'且(P, C', T')是封闭Platoon伴随模式, 则(P, C, T)不再封闭, 也不会再成为封闭Platoon伴随模式.

根据定义4, 可容易推知定理成立.

定理2.序列数据库curD₊可以收缩至D₊, 包含的Platoon伴随模式不变.

证明:由定义3可知:当新数据NR={r|r.t=t_n}到达时, 对于每一个新产生的Platoon伴随模式(P, C, T), P={p₁, p₂, …, p_m}, C=〈c₁, c₂, …, c_n〉, T=〈t₁, t₂, …, t_n〉, 必须满足P⊆MC(c_n, t_n, △t).记P中任意车辆p_i在交通摄像头c_n下的经过时间为$t_i^n$, 则满足${t_n} - t_i^n \le \Delta t$.因此, 车辆p_i的序列包含于D₊.由此可知, 新的伴随模式(P, C, T)一定存在于D₊.

根据上述证明可知:只有当新数据r产生了新的点伴随MC(r.c, r.t, △t), 且|MC(r.c, r.t, △t)|≥δ_veh, 才有可能生成新的Platoon伴随模式.基于此, 本文提出了定理3.

定理3.已知点伴随MC(r.c, r.t, △t)是新数据r到达后产生的新点伴随, 且|MC(r.c, r.t, △t)|≥δ_veh, 该数据产生的新的Platoon伴随模式存在于序列数据库$D_ + ^r = \{ s|s \in {D_ + } \wedge s.sid \in MC(r.c, r.t, \Delta t)\} $中.

证明:设模式(P, C, T)是新数据r到达后产生的Platoon伴随模式, 不妨设P={p₁, p₂, …, p_m}, C=〈c₁, c₂, …, c_n〉, T= 〈t₁, t₂, …, t_n〉.根据定理2, (P, C, T)存在于序列数据库D₊.由于(P, C, T)是新数据r到达后产生的Platoon伴随模式, 故而P⊆MC(c_n, t_n, △t)且r.c=c_n, r.t=t_n.因此, (P, C, T)存在于$D_ + ^r = \{ s|s \in {D_ + } \wedge s.p \in MC(r.c, r.t, \Delta t)\} $中.

定理3阐明了如何进一步缩减关于新数据r的序列数据库, 以及如何基于点伴随的定义在构造序列数据库时考虑时间约束△t.

此外, 在构建序列数据库$D_ + ^r$时, 本文借鉴了频繁序列挖掘领域伪投影数据库构建原理.伪投影序列数据库是指当序列数据库在内存中时, 通过指针在已有序列数据库上确定投影序列数据库, 而非在内存中建立真实的投影序列数据库.如图 4所示:序列数据库D₊中, 每个数据项都具有SID和时间戳两个属性.借鉴伪投影数据库构建原理, 本文的算法利用SID和时间戳从D₊确定序列数据库$D_ + ^r$.

算法1是InsertData()的伪代码.InsertData()方法主要计算新数据产生的新点伴随, 并调用InitFreqMiner()进行下一步计算.具体过程是:InsertData()维护了一个以交通摄像头ID为key值的哈希表, 通过该哈希表, 对点伴随按交通摄像头进行聚类.该哈希表的value值按时间存储了该交通摄像头下互不包含的点伴随.当新数据到达时, InsertData()将新数据加到该哈希表中(第1行~第3行).根据前面的定理, InsertData()利用维护的哈希表找到新形成的点伴随, 则有可能生成新的Platoon伴随模式.因此, 对于每一个新生成的点伴随, InsertData()计算其包含的车辆集合P_r(第4行、第5行).接下来根据定理2和定理3, 针对新到达的数据r计算序列数据库$D_ + ^r$, 并启动线程调用FreqMiner()进行下一步计算.具体过程如下:利用伪投影技术得到序列数据库$D_ + ^r$(第6行).将序列数据库$D_ + ^r$中包含的时间戳按降序排列得到T(第7行).根据$D_ + ^r$得到根据T排序的的点伴随哈希表MCS(第8行).该哈希表的key值是时间, value值存储了该时间下的全部点伴随, 只保留超集点伴随(第9行).即:如果点伴随MC_i⊆MC_j, 去掉点伴随MC_i.调用方法FreqMiner()(第10行).最后, 根据定理1从结果集中删除不可能成为封闭Platoon伴随模式的已有模式(第12行).

算法1. InsertData(r, D₊, δ_veh, △t, δ, δ_cam).

Input: r, D₊, δ_veh, △t, δ, δ_cam;

Output: platMap, 更新的Platoon伴随模式集合;

1. for each新数据r

2. 将r按照交通摄像头聚类, 加入hash表CamMCs; //CamMCs数据结构:〈cameraID, 〈time, ANPRs〉〉

3. for end

4. for each CamMCs中修改过的value值

5. 得到新点伴随所包含的车辆集合P_r;

6. 利用指针构建$D_ + ^r = \{ \eta |\eta \in {D_ + } \wedge \eta .p \in {P_r}\} $; //即利用伪投影序列数据库构建原理确定$D_ + ^r$

7. 根据$D_ + ^r$得到降序排列的时间戳序列T;

8. 得到基于T和$D_ + ^r$的点伴随MCS=〈time, MCs〉 //time是T中的时间点, MCs是各交通摄像头在time时刻的点伴随集合, 点伴随包含的元素个数不小于δ_veh

9. MCS←MCS中全部的超集点伴随; //频繁序列时间约束

10. 调用FreqMiner(MCS, T);

11.  for end

12. 删除重复的Platoon伴随模式//定理1

算法2是方法FreqMiner()的伪代码.FreqMiner()主要负责在序列数据库$D_ + ^r$上挖掘封闭的Platoon伴随模式.具体过程是:FreqMiner()维护了一个保存挖掘结果的Map数据结构platMap以及一个用于判断是否满足δ的Map数据结构platIndex.platMap的key值是车辆集合; value值是该车辆集合一起经过的摄像头ID和时间. platIndex的key值是车牌集合, value是初始值为0的正整数, 用于存储该车辆集合最近驶过的相邻交通摄像头个数(如P={p₁, p₂}, P在交通摄像头〈c₃, c₄, c₆, c₇, c₈〉下伴随, 其中, c₃, c₄是相邻交通摄像头, c₆, c₇, c₈是相邻交通摄像头, 则value先等于2后等于3).首先, 记算法1得到按从大到小的时间顺序排列的点伴随集合MCS中最新的点伴随为MC_new.对MCS中任意点伴随MC_sub满足MC_sub⊆MC_new, 计算Platoon伴随模式(第1行).在platIndex中新加键值对〈MC_sub, 0〉(第2行).根据时间顺序, 依次比较MCS中每个点伴随MC与MC_sub的关系.对于每个MC_sub⊆MC, 如果platMap中key为MC_sub的value中最后一个点伴随对应的交通摄像头与该MC的交通摄像头相邻, 将MC对应的时间和摄像头加入platMap, platIndex中对应的length加1(第3行~第7行).否则, 对platMap关于键MC的值进行判断:如果上一组位置连续的摄像头数量不少于δ, 将MC对应的时间和摄像头加入platMap, 将platIndex中对应的length设为1(第8行~第11行); 否则删除上一组位置连续的摄像头, 并将MC对应的时间和摄像头加入platMap, 将platIndex中对应的length为设1(第12行~第15行).检查platIndex, 将length小于δ的点伴随在platMap的的最后一组相邻摄像头删除(第20行~第22行).检查platMap, 将value长度小于δ_cam的键值对从platMap中移除(第25行~第27行).返回platMap(第30行).

算法2. FreqMiner(MCS, T).

Input: MCS, T;

Output: platMap.

1. for each MCS中的点伴随MC_sub⊆MC_new //频繁序列空间约束

2. platIndex←〈MC_sub, 0〉;

3.  for each MCS中的点伴随MC

4. if MC_sub⊆MC

5. if MC对应的摄像头与上一个包含MC_sub的点伴随对应的摄像头相邻出现在序列数据库$D_ + ^r$

6. 将MC对应的时间和摄像头加入platMap;

7.  platIndex.put(MC_sub, platIndex.get(MC_sub)+1);

8. else

9.  if platIndex.get(MC_sub)≥δ

10. 将MC对应的时间和摄像头加入platMap;

11. platIndex.put(MC_sub, 1);

12. else

13.  删除platMap中key为MC_sub的值的最后一组相邻摄像头;

14.  将MC对应的时间和摄像头加入platMap;

15. platIndex.put(MC_sub, 1);

16.  if end

17. if end

18. if end

19. for end

20. for each platIndex中的〈MC, length〉

21.  if length < δ

22. 删除platMap中MC对应值的最后一组相邻摄像头;

23.  if end

24. for end

25. for each platMap的〈MC, value〉

26.  if value的长度小于δ_cam

27. 从platMap中删除该〈MC, value〉;

28.  if end

29.  for end

30. 返回platMap;

最后, PlatoonFinder算法调用了方法removeData.对于过期数据r, removeData先将r从窗口中移除.如果已发现的封闭Platoon伴随模式(P, C, T), P={p₁, …, p_m}, C=〈c₁, …, c_n〉, T={t₁, …, t_n}涉及该数据, 则有r.p∈{p₁, …, p_m}, r.c= c₁, r.t≤t₁.对r进行如下操作:将r加入封闭Platoon伴随模式(P, C, T)的过期数据集E; 如果(P, C, T)的过期数据集E满足E.P={p₁, …, p_m}, 且存在r₀∈E使得E⊆MC(r₀.c, r₀.t, △t), 清空E, 更新(P, C, T).

4.3 PlatoonFinder算法实现

本文将实现的算法嵌入了百度地图API, 可以在地图上实时呈现PlatoonFinder算法发现的伴随模式.用户界面提供了算法的参数输入, 分别包括点伴随时间阈值△t交通摄像头个数阈值δ及δ_cam.

用户调用PlatoonFinder算法后, 用户界面将发现的Platoon伴随模式以车辆组群行驶轨迹的形式在百度地图上展现给用户, 并将详细信息列在地图的右侧.

图 7是嵌入百度地图API后PlatoonFinder算法的实现效果图.图中的摄像头标识代表了分布在道路上的交通摄像头, 椭圆标识代表了交通摄像头下的点伴随, 箭头代表了车辆组群的行驶轨迹.图 7是在△t=60s, δ=2, δ_cam=4时发现的伴随模式.上述参数要求将一起驶过不少于4个交通摄像头, 且局部相邻的交通摄像头不少于2个的伴随车辆展现在百度地图上.

5 实验结果及分析 5.1 实验设置

本文的目标在于近实时地发现车牌识别流式大数据中的Platoon伴随模式.本节主要从有效性和效率方面对本文提出的PlatoonFinder算法进行验证.

● 参数设置

表 2列出了实验使用的参数, 其中, l代表伴随模式的实际交通摄像头个数.

● 对比算法

本文选取了Apriori算法和经典的基于投影的频繁序列挖掘算法PrefixSpan作为对比算法.我们在前期工作中, 通过借鉴频繁项集挖掘经典算法Apriori算法设计了基于Spark的并行伴随车辆发现算法.本文将该算法作为对比算法之一.此外, 本文将Spark Mlib自带的PrefixSpan(http://spark.apache.org/mllib/)算法作为另一个对比算法.本文利用滑动窗口机制, 将上述算法实现为基于Spark框架的处理流数据的实时算法.

● 环境配置

本节实验的硬件环境为一台独立的电脑以及一个5个节点的集群.独立电脑的CPU为四核Intel(R) Core(TM)i5-2400, 3.10GHz; 内存4GB; 硬盘500GB.集群上每个节点核数为2, 拥有4G内存150G硬盘.独立电脑的软件环境为Windows7操作系统, Eclipse4.4.0集成jdk1.8.0.集群的软件环境如下:所有节点均为装有CentOS-6.4的虚拟机, jdk版本为1.8.0.集群所使用的Spark版本为1.5.0, Hadoop版本为2.6.0.所有的结果存储在HDFS上.所有算法使用Java及Scala语言开发完成.

5.2 有效性验证

本节将对PlatoonFinder算法的有效性进行验证, 并对实验结果进行分析.由前文介绍可知, △t, δ和δ_cam是算法的主要参数, 不同的取值将会对算法结果产生不同的影响.为此, 本节首先测试了这些参数的取值将会对算法最终发现的伴随模式数量产生何种影响, 从而为算法的实际应用提供相应指导.下面介绍实验数据集和指标.

● 数据集

本节实验所用数据集是北京市真实车牌识别数据集, 该数据集包含了从2012-12-21 06:00:00到2012-12-30 20:00:00共10天的1 040个交通摄像头产生的车牌识别数据.这10天数据由8天工作日和2天周末组成.数据集共存储了54 316 820条数据记录, 包含了4 669 229辆车的相关信息.本文在该数据集上选取了若干子集进行实验.前期工作^[10]对车牌识别数据的分析结果显示, 每天的车牌识别数据可以分为4个部分:第1部分从00:00:00到07:00:00, 这一部分的数据量十分稀少; 第2部分从07:00:00到12:30:00, 这一部分包含了早高峰; 第3部分从12:30:00到19:30:00, 这一部分包含晚高峰, 第3部分与第2部分包含的数据量基本持平; 第4部分从19:30:00到23:59:59, 这一部分数据量介于第2部分(第3部分)与第1部分之间.不失一般性, 本文在10天真实车牌识别数据集的每个部分各选取了2小时的车牌识别数据, 共80个子数据集.并将选取的80个子数据集按原有速率还原为流数据接入PlatoonFinder算法.

定义5(平均数量).已知存在车牌识别数据集R₁, R₂, …, R_k.对每个数据集R_i, PlatoonFinder算法发现的Platoon伴随模式数量为n_i, 则PlatoonFinder算法在全部数据集R₁, R₂, …, R_k上发现的Platoon伴随模式平均数量为$\bar n = \sum\nolimits_{i = 1}^k {{n_i}/k} $.

本文所有实验(包括效率验证)均将窗口大小设置为30min.同时, 为了尽可能保障不丢失伴随模式, 本文的所有实验(包括效率验证)均将窗口的滑动距离设置为1s.对于每个选取的子数据集, 实验调用PlatoonFinder算法计算Platoon伴随模式.对结果四舍五入保留整数.

图 8是有效性实验结果柱状图.如图所示:在不同的δ取值下(δ=1, δ=2, δ=l), PlatoonFinder算法发现的Platoon伴随模式的平均数量随着δ_cam的增加都快速下降.图 8还显示:当δ_cam增加时, 不同的δ取值下, Platoon伴随模式的平均数量之间的差异也发生相应的变化.首先, δ=1时, 平均数量明显多于其他两种模式; 其次, 当δ_cam≤8时, δ=2较δ=l下的平均数量逐渐增加; 当8 < δ_cam≤10时, 两种δ取值下的平均数量又趋于相等.通过分析δ_cam=9, 10时, δ=l的详细实验结果发现, 造成这一现象的原因如下:当算法PlatoonFinder发现并保留了封闭Platoon伴随模式(P, C, T), 随着新数据的到达, 发现并保留了新的封闭Platoon伴随模式(P, C', T'), 且满足C⊏C', T⊏T'.根据定义4, 在对保留的实验结果进行检验时, (P, C, T)将被丢弃.而当δ=l时, 相同车辆组群产生的多个Platoon伴随模式不会合并.此外, 当δ_cam较大时, 在相同大小的窗口内包含的δ=l下的Platoon伴随模式会减少.以上两点导致了8 < δ_cam≤10时, δ=2和δ=l下的平均数量趋于相等.此外, 进一步观察图 8的实验结果, 在参数δ和△t固定的情况下, 随着δ_cam的增加, 本方法发现的伴随车辆数量呈指数型下降.对于每一组δ和△t在不同δ_cam取值下的伴随模式进行分析发现, 伴随车辆数量的下降规律如下:随着δ_cam的增加, 伴随模式数量的下降趋势呈现先减缓又加速再减缓的总体趋势.计算相邻δ_cam取值(例如δ_cam=2和δ_cam= 3) 下伴随模式数量的下降程度发现, 伴随模式数量的平均下降程度分别为77.67%, 67.60%, 68.83%, 80.45%, 87.354%, 78.20%, 80.03%和75.91%.推断在δ_cam取值较小时, 车辆偶然伴随的可能性较高, 因此, 下降程度的第1次减缓可能是由于偶然性因素降低而造成的.当δ_cam > 5, 模式数量的下降程度开始加速, 推断是由于伴随区间对伴随模式数量的影响超过了偶然性因素的影响.δ_cam从6增加到7时下降程度最大, 出现了拐点.当δ_cam > 7时, 模式数量的下降程度再次开始减缓, 推断当伴随区间足够长时, 车辆具有更高可能性继续保持这种伴随的状态.

本节实验得出了以下结论:

(1) PlatoonFinder算法发现的Platoon伴随模式数量与△t呈指数型上升;

(2) PlatoonFinder算法发现的Platoon伴随模式数量与δ_cam呈指数型下降.

5.3 效率验证

本节验证了PlatoonFinder算法的效率, 并对实验结果进行了分析, 测试了不同的阈值△t以及不同数据到达率对算法延时的影响.

定义6(流数据的到达速率).流数据的到达速率是指单位时间内的数据到达数量, 记为r_a.通常取1s为单位时间, 即为1s内到达的车牌识别数据数量.

定义7(平均延时).设当前的滑动窗口为curWin, 窗口的滑动距离为d_s.curWin滑动d_s的长度到达下一窗nextWin.算法在nextWin上计算得到伴随模式的时间为t_i.设窗口的数量为m, 则算法的平均延时定义为

$ {{\bar t}_{lat}} = \sum\nolimits_i {{t_i}/m.} $

首先, 本文在有效性验证使用的80组真实车牌识别数据子集上测试δ=1, δ_cam=2时, △t=20s, 40s, 60s, 80s, 100s, 120s下, 算法PlatoonFinder的平均延时, 并绘制成图 9.随后, 为了验证吞吐量对平均延时的影响, 本文在真实车牌识别数据的基础上共模拟了80组时长为2小时的数据集:数据到达率为10条/秒、100条/秒、1000条/秒、10000条/秒的数据集各20组.将这些数据集以流数据的形式接入算法, 计算平均延时并绘制成图 10.所有结果均保留两位小数.

图 9是在不同的△t取值下, PlatoonFinder算法平均延时实验结果柱状图.如图 9所示, 算法PlatoonFinder的平均延时随着△t的增加呈指数型上升.当△t≤100s时, 算法的平均延时保持在1 000ms以下.而当△t=100s时, 算法的平均延时达到1 528.57ms.由于车牌识别数据的最小间隔时间为1s, 图 9的实验结果证明了当△t≤100s时, 算法PlatoonFinder能够在车辆通过摄像头时即时发现Platoon伴随模式.在这种条件下, 算法对新到达的数据进行的Platoon伴随模式计算时不需要排队等待.而当△t≥120s时, 算法PlatoonFinder计算高峰时期(车牌识别数据到达率为每秒1条)的Platoon伴随模式时可能存在数据堆积现象.因此, 本文的未来工作将聚焦于算法的并行优化, 力求在△t≥120s的条件下即时发现的Platoon伴随模式.

图 10是在从10条/秒到10 000条/秒不同流数据到达速率下我们的算法和Apriori算法、PrefixSpan算法的平均延时对比.

随着数据到达速率的增加, 3种算法的平均延时均大幅上升.其中, 当到达速率为10条/时, 3种算法的延时均小于真实车牌数据的最小时间间隔1s, 在这种情况下, 3种算法都可以满足处理流数据的实时性要求.当到达速率上升至100条/秒时, 3种算法的平均延时都大幅上升.PlatoonFinder和PrefixSpan算法的平均延时仍然低于1s, 而Apriori算法的平均延时已经高达125s, 无法满足实时处理流数据的需求.当到达速率上升至1 000条/秒时, Apriori算法崩溃, 这是由Apriori算法十分消耗内存而Spark框架是基于内存的计算框架而导致的.同时, PrefixSpan算法的平均延时达到133s, 不足以处理流数据; 而本文算法的平均延时为384.76ms, 仍然小于真实车牌数据的最小时间间隔1s, 可以满足实时性需求.当到达速率到达10 000条/秒时, 本文算法崩溃, 意味着处于单机环境的本文算法无法处理如此高速率的流数据.同时, 基于Spark框架的PrefixSpan算法的平均延时却明显降低至97s.这证明了Spark并行框架提升了PrefixSpan算法面对高吞吐量流数据的处理能力.基于此实验结果, 在未来的工作中, 我们考虑将本文算法并行化, 以提升其面对高速流的处理能力.

6 总结

本文针对一种特殊的流式时空大数据——车牌识别流式大数据, 瞄准伴随车辆即时检测这一新兴的智能交通应用, 提出了伴随车辆检测的核心算法.本文将Platoon伴随模式发现问题映射为数据流上的带有时空约束的频繁序列挖掘问题.为了有效应对车牌识别流式大数据的速率和规模, 本文算法针对数据流的特点进行了性能优化, 并融入了伪投影等性能优化技术, 从而实现车辆Platoon伴随模式的即时发现.实验证明:在真实车牌识别数据集下, 本文算法有效地发现伴随车辆组及其移动模式; 然而当数据到达速率上升至10 000条/秒时, 我们的算法已经无法应对如此高速的流数据.因此在未来的工作中, 我们计划并行化本文的算法, 以保障高速率的流数据实时处理.