基于RFID的电动车运行轨迹频繁模式挖掘算法研究

鄢团军，吕 军，齐国强

（浙江海康科技有限公司，浙江 杭州 310012）

0 引言

射频识别即RFID（Radio Frequency Identification）技术，是自动识别技术在无线电技术方面的具体应用与发展，其利用射频信号通过空间耦合实现无接触信息传递，并通过所传递的信息识别目标[1]，无需识别系统与特定目标之间建立机械或光学接触。该技术已被广泛应用于安防、仓储、物流、追溯、防伪、旅游、医疗、教育等不同领域。

运用有源RFID技术，构建射频网，管控网内所有的电动自行车，可以实现车辆被盗能及时发现，及时寻回。电动车防盗系统也可以对车主在通勤中的违章情况进行善意提示，逐步提高车主交通安全意识。该系统对于建设智慧城市、提升城市公共服务质量具有较为深远的意义。

在系统运行过程中，会累积海量的过车数据，将过车数据按时间和空间维度表示，可以形成车辆的运行轨迹。在大量的车辆位置和运行轨迹数据背后，隐含了丰富的空间结构信息和用户行为规律。对这些信息进行深入的挖掘，不仅可以发现个体用户的日常行为规律和群体用户的共性行为特征，甚至还有可能掌握他们的社交关系信息，这对城市规划、智能交通甚至广告推荐等应用都具有非常重要的意义。

本文首先描述有关轨迹数据的来源及结构，然后给出频繁轨迹相关定义，最后提出基于带权无环图计算频繁轨迹的方法并验证可行性。

1 相关研究综述

轨迹数据挖掘是从大量的轨迹数据集里发现隐藏在数据背后、用户感兴趣且未知的信息。轨迹数据通常包含空间信息和时间信息，在进行轨迹数据挖掘时，通过对序列模式或位置序列增加时间维度的方法，将序列模式扩展成轨迹模式。

Agrawal[2]等首先介绍了序列模式挖掘问题，序列模式挖掘是找出所有的频繁子序列。Giannotti[3]给出了时间约束、滑动时间窗口、用户分类与序列模式挖掘相关的定义，并提出了一种基于先验的改进 算 法 GSP （Generalized Sequential Patterns）。Mannila[4]等提出了一个事件序列中频繁片断的挖掘问题，认为片断实质上是由一组事件组成的无环图，无环图的边表示事件发生的先后关系，该文没有考虑时间间隔的限制。Lu[5]等认为事物间的关联规则是一种隐含规则，其是完全受时间间隔限制的有序事件片断。Han[6]等开发了一种针对周期模式的频繁模式挖掘方法用于挖掘频繁最大模式，频繁最大模式中的每种模式满足固定的周期和固定的序列集及支持度。以上所有方法在挖掘序列模式和时间相关的频繁序列模式时均是类APRIORI[7]算法，如先验原理认为在关联挖掘中，候选集和测试范例生成时，任何非频繁模式的超模式都不可能是频繁的[8]。典型的APRIORI序列模式挖掘方法，如轨迹模式挖掘[3]，采用了多遍、候选生成和测试的方法。

轨迹的频繁模式挖掘可以形式化为频繁序列挖掘[9]，而轨迹数据频繁模式相比频繁序列，增加了空间维度、时间维度和语义维度[10]，所以简单地采用传统序列挖掘方法无法有效解决轨迹频繁模式挖掘问题。

Lu[5]等提出了用时空模式表示总体移动行为，称为轨迹模式，以描述个体的移动轨迹，这些轨迹具有相似移动时间和相同位置序列的属性。因此，有2个核心概念：第一，给定空间中的感兴趣区域；第二，移动对象从区域到区域的移动时间。在该方法中，轨迹模式是一系列空间区域的集合，这些空间区域是移动对象频繁地按特定顺序经过位置的集合。

Luo[11]等研究了一种基于时间周期的最频繁路径查询问题，主要目标是分析和研究大多数行人最频繁的道路选择情况，为了避免路径边数和非频繁路径对挖掘结果的影响，采用序列形式描述路径频数。Zhang[10]提出时空轨迹的细粒度序列模式挖掘问题，认为在连续空间中的位置点不适合进行序列模式挖掘，而由相同语义的位置点构成的区域更合适，故将位置的语义维度连同空间和时间维度一同加入到细粒度序列模式挖掘中。

2 轨迹数据的形式

根据采集移动对象移动数据不同的技术方法，轨迹数据有不同的形式。Spinsanti[12]等将轨迹数据分成基于差分GPS（全球定位系统）、GSM（全球移动通信系统）以及基于地理社交网络的轨迹数据。Pelekisan[13]等增加了另外2种形式：基于RFID和基于Wi-Fi的数据。基于GPS的数据由被采集对象携带的具有GPS功能的设备记录时间有序的地理坐标序列组成；基于GSM的轨迹数据，由按时间顺序通过GSM基站单元的标识符组成；基于地理社交网络的轨迹数据，是通过互联网上的内容媒体和地理坐标附加而成；基于RFID的数据由一系列移动对象通过的RFID阅读器的标识符组成；基于Wi-Fi的数据是一系列与之通信的接入点标识符。

本文以有源RFID防盗系统记录移动对象通过基站的序列来表示轨迹。对路网环境下的车辆运行轨迹而言，路口被当作是轨迹分段的划分点[14]，一段没有分岔的道路是一个轨迹分段的最小单位。本系统采用基于路网的关键点采样，通过控制有源RFID读写器（后文称基站）的采集范围来实现基站与基站间采集范围不重叠的同时，道路路口不留信号死角。如图1所示，若目标O经过路口A，被基站d1采集，系统认为O的位置在A附近，然后，若目标O被基站d3采集到，则可认为O的行动轨迹为从A到C。

图1 基站信号范围及部署节点示意图

电动自行车（后文称车辆）附着有射频标签，该射频标签的编号视为该车辆身份唯一标识，车辆进入射频网后，系统可以对车辆进行定位并记录车辆移动轨迹，如图2所示。

3 基于带权无环图的频繁轨迹挖掘算法

在城市道路环境下，轨迹数据无法离开道路，故两者必然匹配。理论上，车辆移动产生的轨迹数据根据采集频率，会产生大量的位置点数据。由于相邻的位置点冗余度较大，需要对原始的轨迹进行近似化表示[15]，一方面对挖掘效果无影响，另一方面提升计算的执行效率。本系统将轨迹点序列根据道路实际情况，近似地用线段序列来表示。

3.1 轨迹定义

定义1：轨迹点

车辆运动过程中在时间空间域中的坐标d=（x，y，t），其中（x，y）为空间坐标。 本文以有源 RFID防盗系统记录移动对象通过基站的序列来表示轨迹，所以轨迹点与RFID基站位置信息等价，t为车辆经过空间点（x，y）的时刻。

定义2：轨迹

车辆 Oi在时间区间Δt内，经过的轨迹点序列集合，表示为 D（Oi，Δt）=｛d0，d1，d2，…，dn｝，其中 di表示轨迹点，即 di=（xi，yi，ti）。

定义3：轨迹边序列

轨迹边是通过对轨迹点变换得来，表示车辆所经过的路径 E（Oi，Δt）=｛e0，e1，e2，…，en｝，其中 ei表示为[（xi-1，yi-1，ti-1），（xi，yi，ti）]，是从轨迹点 di-1到轨迹点di的路径。本文不考虑从di-1到di的轨迹边与从di到di-1的轨迹边的差异，认为两者的意义相同。

定义4：子轨迹

给定Oi某一时间区间Δt内的运行轨迹D（Oi，Δt）=｛d0，d1，d2，…，dn｝，按时间先后顺序取其中一部分连续基站组成的有序集合 D（Oi，Δt′）=｛dk，dk+1，…，dk+m｝，其中 k＞0，k+m≤n，则 D（Oi，Δt′）是轨迹 D（Oi，Δt）的子轨迹，记作 D（Oi，Δt′）⊆D（Oi，Δt），显然子轨迹 D（Oi，Δt′）经过的时间区间 Δt′是 Δt的子区间。

定义5：轨迹长度

轨迹包中轨迹点的个数。 如 D（Oi，Δt）=｛d0，d1，d2，…，dn｝的轨迹长度 l=n。

定义6：轨迹频次

图2 电动自行车运行轨迹

在给定的轨迹集合 S=｛D1，D2，…，Dn｝中，含有子轨迹 Dsub的轨迹的个数，记作 ｜｛D ｜Dsub⊆D，D⊆S｝ ｜。

定义7：轨迹频繁模式挖掘

给定 Oi的轨迹集合 S=｛D1，D2，…，Dn｝和最小支持度 Supportmin，Supportmin⊆[0，1]，找出所有轨迹Dsub，满足条件 Support（Dsub）≥Supportmin其中

显然，频繁轨迹的子轨迹也是频繁轨迹，所以只需找出每类轨迹长度最长的子轨迹即可。

3.2 频繁模式挖掘算法

（1）生成图

给定标签 Oi的轨迹集合 S=｛D1，D2，…，Dn｝，遍历轨迹集合，按照轨迹边构建带权图，权重为经过该轨迹边的轨迹数。

①从集合S中取中第一条轨迹，初始化图F，对两点的连接边记权值为1，增加虚拟节点起点和终点的权值为1，起点指向第一个点，终点指向最后一个点。

②For D1in S，其中 1＜i＜n，D1=｛di0，di1，…，dik｝

在Di中取出di0，在F中查找该di。如果找到，则在虚拟起点与该点间的边权值增加1；如果找不到，将di0加入图F，给di0增加虚拟起点，两点连接的边权值为1。

For di1IN ｛di1，di2，di3，…，dik-1｝

在 F中查找dij，如果已有点 dij，且与 dij-1有连接边，则给边的权值加1；如果没有连接边，则增加连接边给定权值为1。如果没有点dij，则将dij加入到图F，增加与dij-1连接边，给边的权值为1。

End for

在Di中取出dik，在F中查找dik，如果找到，且与dik-1有连接边，则给边的权值加1；如果没有连接边，则增加连接边，给定权值为1，将dik与虚拟终止点间的边加1。如果找不到，将dik加入到F，增加与dik-1连接边且设置权值为1，增加虚拟终点及其与dik的连接边设置权值为1。

End for

（2）给定最小支持度 Smin，根据轨迹总数 n，可算出频繁轨迹满足至少要有h条轨迹经过该轨迹段。按h进行减权后得到图F′。

①图F′中的边的权值W减去h，如果W＞h，则权值更新为W减去h。

②如果W≤h，将该权值更新为0。

（3）对图以虚拟起点为根进行深度遍历，将遍历过程中经过的点：如果权值大于0，将点加入到频繁轨迹候选表里，直到到达虚拟终点为止，记录整条链路上的最小权值Wmin，此候选轨迹的支持度为（Wmin+h）/n。由于有的点既是起始点又是终止点，那么可能存在两条轨迹序列点相同，只是序列点相互倒序，所以最后再对候选轨迹进行去重。

4 算法验证

从电动车防盗系统中，抽取出某车主近30天52条运行轨迹数据对算法可行性进行验证。每条轨迹数据包括多个通过基站的信息，包含基站ID、进入时间、停留时间。首先对数据进行预处理，将停留时间为1s的数据清理掉。生成的带权无环图如图3所示，其中数字编号为轨迹序列中的位置点，A、B、C表示起点或者终点（仅标识起点和终点，不作为轨迹的一部分）。通过计算后结果如表1所示。

图3 带权无环图

表1 挖掘结果

通过在地图上查看各位置点的坐标，可知：位置1，是某小区门前路口位置，而位置19是某写字楼附近路口，位置22是某综合体购物中心。结合图3与轨迹的起终点时间可知，该车主住在位置1，在位置19处上班，偶尔去综合体消费，表1的挖掘结果符合常理。

5 结语

实际应用中有很多领域可运用轨迹数据挖掘，通过分析历史轨迹，可以更好地理解活动对象行为。同时，轨迹数据挖掘为公众提供了很多便利，例如路线推荐、实时交通信息发布。对政府组织而言，轨迹数据挖掘有助于降低监督和管理成本。在城市区域，车辆轨迹数据挖掘为监测城市的交通状态提供了一种高效可扩展的方法。

本文论述了频繁轨迹的分析算法，以电动自行车防盗系统为例，从轨迹数据库中取出轨迹数据，结合车主的实际情况，验证了算法的有效性。本文只是对轨迹数据从频繁这一角度进行了分析，针对车主轨迹数据还有伴随车辆、热点路径等其它方面的分析角度，这将是后期研究的重点。另外如何利用挖掘出的信息，分析车主内在需求、发掘商业机会、改善城市公共服务质量、提升服务准确性和建设智慧城市也将是需要深入思考的问题。