在过去的十年里，随着移动设备的发展和普及，使全球范围内各种大小的移动对象都得到较准确的定位和有效的跟踪。用户不但可以通过定位技术方便地获取个人位置信息，而且信号接收设备可以从定位终端上采集到大量移动对象的轨迹数据。轨迹记录着用户在客观世界的活动，一定程度上体现了人们的意图、喜好和行为模式。如用户的活动规律、所经过的地点顺序和最常走的几条路线等。越来越多的科研人员开始投入到GPS轨迹的研究，希望可以从粗放时空数据中挖掘出有价值的信息。

频繁轨迹模式挖掘是轨迹研究中最流行的一种，可以建立在频繁模式挖掘的基础之上，所以本文研究了对频繁模式挖掘经典算法FP-growth的改进创新，从而能灵活高效地从大量轨迹数据流中提取所需的频繁轨迹模式。其研究成果可以为个性化推荐、交通、旅游等应用领域提供方便的服务。

1 研究背景

频繁模式挖掘是数据挖掘研究中的一个重要课题。文献[1, 2]提出的算法被视为频繁模式挖掘领域最基本的两大算法。文献[3]采用逐层迭代策略产生频繁项集，是一种自底向上的方法。为了提高其效率，研究人员提出了FP-growth算法，利用了一个特殊的存储结构FP-tree，能有效地提高挖掘效率。基于以上两大算法，研究人员提出了很多其他处理频繁模式挖掘的方法，如GSP^[3]算法在Apriori算法的基础上引入了时间约束、滑动时间窗以及分类层次技术。文献[4]提出了PrefixSpan算法，采用基于投影的分治法来减小数据。文献[5]提出SPADE算法采用基于序列格的搜索技术和连续操作，将原始问题分解为子问题。

以上算法都旨在挖掘事物数据库，并未同时考虑到时间和空间属性。但是时空属性对于轨迹挖掘来说至关重要，文献[6]首先将原始轨迹转换成有时间约束的时空地点序列，提出了prefix-projection的方法来提取频繁时空模式。文献[7, 8]定义了一个标有时态的轨迹序列模式Tpattern。文献[9]将分布式编程思想应用到频繁项集挖掘方法的MG-FSM^[10]算法。

但以上诸多算法都需要两次以上的数据库扫描，降低了算法执行效率，因此，文献[11]提出FARM算法，生成了一个不仅考虑了数据的时间属性，还能在一个紧凑的数据结构中存储大量数据的新型框架。此外，基于MASTER-M^[12]算法的数据估计框架还可以为MSN估算传感器丢失的数据。

由以上研究可以看出，对于频繁轨迹模式挖掘而言，目前最关键的两个研究点在于如何挖掘带有时空属性的轨迹和减少扫描数据库的次数^{[13, 14]}。本文针对这两个问题对FP-growth算法进行了改进：

1) 提出一种基于经纬度二维筛选和GPS格式过滤的轨迹预处理方法。

2) 改进FP-tree使其适用于轨迹处理，使用动态数组存储挖掘出的候选轨迹集。

3) 能根据用户的需要输出不同时间段和不同频率段的频繁轨迹。

2 问题描述

本文所研究的轨迹是带有时间属性的文本轨迹流，每条轨迹由多个地点串联而成，每两个地点之间还带有时间差。

定义 1 一个轨迹点v_i是由一个三元组(x_i,,y_i,t_i)构成的，x_i ,y_i是经度和纬度，t_i是时间戳。

定义 2 一条时空轨迹是由序列 S = v₀, v₁,…, v_n = (x₀, y₀, t₀),(x₁, y₁, t₁), …, (x_n, y_n, t_n)构成的，t_i(i =0…n)是时间戳，$\forall 0\le i < n,{{t}_{i}}<{{t}_{i+1}}$，(x_i,y_i)是轨迹中某一点的经纬度。

本文的轨迹流模式是在文献[7]上的扩展改进，原轨迹流模式定义如下：

$T={{v}_{0}}\xrightarrow{{{t}_{1}}}{{v}_{1}}\xrightarrow{{{t}_{2}}}\ldots \xrightarrow{{{t}_{3}}}{{v}_{n}}$

式中，v_n为地点；t_n为时间戳。但不能认为从某地到下一个地点所需的时间可以严格控制为某个具体的时间点，而应该用一个大致的时间段来描述。所以本文采用的轨迹流模式如下：

定义 3 本文所使用的轨迹模式为：

$T={{v}_{0}}\xrightarrow{t{{\alpha }_{1}}}{{v}_{1}}\xrightarrow{t{{\alpha }_{2}}}\cdots \xrightarrow{t{{\alpha }_{n}}}{{v}_{n}}$

式中，tα_n为一个时间区间(${{t}_{{{\min }_{n}}}}$～${{t}_{{{\max }_{n}}}}$)，表示从v_n-₁～v_n所花费的最短时间和最长时间分别是${{t}_{{{\min }_{n}}}}$和${{t}_{{{\max }_{n}}}}$。

定义 4 给定一个轨迹数据库D，共有n条轨迹，轨迹支持度support是轨迹序列S的数量占总数n的百分比。

定义 5 最小支持度阈值min_sup是挖掘过程中过滤轨迹点和过滤轨迹的衡量标准，最后加入到频繁轨迹集中的轨迹S的支持度support(S)> min_sup。

3 NFTM模型建立 3.1 模型综述

本文的算法由3个模块组成: 预处理模块、轨迹树构建模块和频繁轨迹模式挖掘模块。在预处理模块中，根据地点数据的经纬度进行异常和冗余数据的检测并删除。然后将数据输入到第2个频繁轨迹树生成模块中，通过一次数据库扫描，动态地搭建一棵频繁轨迹树，并生成相邻结点之间的时间差。进入第三个挖掘模块后，可以根据用户所要求的时间和频率段输出频繁路径，以及走完该路线所花费的最长时间和最短时间。该模型的整体框架如图 1所示。

3.2 预处理模块

本文提出一种基于经纬度和GPS数据格式^[15]的轨迹数据预处理方法。

轨迹模式挖掘所用到的是GPS轨迹数据集，设每个数据点由一个包含经度、纬度和时间的三元组item构成，而原始数据集非常庞大且格式不统一，所以首先检查每个数据点的数据格式是否符合要求，将不规则点从数据集中删去。设数组ft[ ]存储经格式匹配函数过滤后的数据。将所有数据按经度进行分类，设数组sl[m][ ]用来存储具有相同经度m的数据项，再将同一经度的item集按照不同的纬度进行划分，并统计每类的item个数，用number表示。将小于阈值(通过对大量数据的测试得到，设为T)的数据组删除。由于数据的采集间隔时间较短，造成了大量的冗余数据，严重浪费了处理时间。所以将相邻连续的同一地点合并成一个，到达时间为第一个地点的到达时间。设final[ ]存放预处理后剩余的数据项。伪代码如下：

输入: file directory (一个文件目录)

    For each file from 0 to k

        for each item from 0 to n

            if format(item_n)==true

                add item_n to ft[ ];

        Put the triples which have the same

  longitudeinto sl[m][ ];

        for sl[ ][ ] from sl^[0][ ] to sl[m][ ];

            for each item form sl[m][ ];

                 if number of item_n < T

            remove (item_n) from sl[m][ ];

                i=0;

                While sl[m][ ]!=null

                     If sl[m][i] ！= sl[m][i+1]

                        add sl[m][i] to final[ ];

  the final[ ] coverage the original file

3.3 频繁轨迹树生成模块

在频繁轨迹树生成模块中，通过建立一种紧凑的数据结构存储树节点的属性和相邻结点之间的时间差值，只需扫描一次数据库可动态的构建轨迹树。构建轨迹树部分的规则如下:

1) 如果多个路径都经过某点，那么这个点应被合并成一项存储在项头表中。把两条轨迹从头结点开始的前几个相同节点合并，从不同的节点开始分支。

2) 对频繁模式的挖掘加入时间限制，分别挖掘出不同时间段的频繁路径或地点。时间段的限制根据用户的输入来定。

3) 考虑到实际应用场景，所以在构建轨迹树时将各地点按真实轨迹顺序排列。

4) 新增了一个有效的数据结构，用来存储整条频繁路径的时间长度。

使用一个例子来描述如何应用以上规则构建一棵频繁轨迹树，首先定义了时间限定在(0～20)的6条简化轨迹如下：

1) (v₁,1)—(v₂,3)—(v₃,6)—(v₄,7)

2) (v₁,1)—(v₂,9)—(v₄,13)

3) (v₄,3)—(v₂,9)—(v₅,11)—(v₆,14)

4) (v₄,2)—(v₂,3)—(v₆,4)—(v₇,8)

5) (v₄,7)—(v₁,9)—(v₇,14)—(v₆,17)

v_i代表地点，数字n代表时间。将以上6条轨迹输入本模块后，开始进行频繁轨迹树的构建，具体步骤如下：

1) 首先输入时间限制，将预处理后的数据根据时间属性再进行一次过滤，只保留在规定时间段内的数据。建立树的根结点，设置为NULL。

2) 第一条轨迹输入后，生成如图 2所示的项头表，用来存储每个数据项的值、对应的支持度以及指向数据项在树中所处位置的指针。此外，在头结点下生成一条轨迹，构建频繁轨迹树的第一条分支。在树枝上即两个相邻的结点之间存储时间间隔。

3) 输入第二条轨迹，支持度改变。v₁和v₂的出现顺序与第一条轨迹相同，所以合并路线。由于第二条轨迹中v₁和v₂的时间差为8，所以时间差的最大值由2改为8。从v₄起在树中生成了另一条轨迹分支。v₄结点第二次出现，所以第一条轨迹中的v₄还需要具备一个指向第二条轨迹中v₄的指针，称为指向下一同名结点的指针。输入第三条轨迹之后，如图 3所示，由于新增了两个项头表中没有的地点v₅和v₆，所以将其加入项头表中，并添加指向它们的指针。

4) 输入第四条轨迹，v₄、v₂和第三条轨迹重合，它们之间时间差的最小值由6变为1。将第一次出现的v₇地点与支持度连同指向它的指针加入项头表中。输入第五条轨迹之后，如图 4所示，一颗完整轨迹树构建完成。

3.4 挖掘模块

在挖掘模块中，定义动态数组temp[]用来存放轨迹挖掘过程中的候选轨迹集，动态数组frequency[]用来存放轨迹的频率。初始化频繁轨迹集frequentSet[]和符合频率条件的轨迹集finalSet[]使其为空。伪代码如下：

输入：min_supp(最小支持度阈值)、start and end(需要挖掘的频率范围)

    for all locations l_i in the header table

      if support(l_i)< min_supp

        traverse the node-link containing l_i; remove all nodes have l_i from tree;

      for remaining items of header table

        for all items named l_i

       generate sub-tree with all paths ending by l_i; the same combined into one route, the route generating set S, placed in the temp[];

    Put the support_route into the frequency[];

        for all routes in temp[]

             if S.support >= min_supp；

                add S to frequentSet[];

                for all routes in frequentSet[ ]

              if S.support >=start &&

                S.support< = end

                    add S to finalSet[ ];

                output finalSet

从以上算法可以看出，本文相比于FP-growth算法的不同之处是：FP-growth算法在挖掘频繁模式时，需遍历FP树来递归的生成条件FP树，条件FP树的每一个结点至少需要3个指针，护起来要花费较多的动态空间。本文使用数组存储条件树，将遍历树得到的子路线存储在数组中，能有效地节约空间，提高时空效率。很多频繁轨迹模式挖掘的算法最终只输出最高频率的路径，这样极易造成对特定群体而言只输出一个地点，如对学生而言，最终可能只输出“学校”。所以经改进，可以根据用户的需求输出一定频率范围内的路径。

4 实验及其结果分析 4.1 数据集与环境

本文算法的测试部分所使用的是来自Geolife 项目的真实数据集[GSP code 2013]，使用的测试集为200 KB，约12 000个地点项。测试集中的每一条轨迹路线都是由一系列地点项组成，每个项都包含经纬度和时间戳。将该算法与两个经典频繁模式挖掘算法GSP和Prefixspan进行了对比。所有测试实验都在具有2.30 GHz速度的处理器以及4.00 GB主存的电脑上完成。代码使用JAVA语言编写。

4.2 测试结果和分析

本文从以下3个方面进行了对比。

1) 第一个对比如图 5所示。由图 5可以看出，3个算法的运行时间都随着最小支持度的增长而增长。特别是GSP算法，在支持度小于0.55时，增长趋势平滑，但之后迅速增长，时间趋近于无穷。由此可得，该算法的运行时间比其他两个算法更短，且随着支持度的变化增长趋势稳定。

2) 第二个对比将最小支持度统一为0.55，如图 6所示。从图中可看出，Prefixspan和该算法都是随着地点数量的不断增加，程序运行时间变长。不同的是前者的增长速度较快，而后者变化趋势平稳，说明该算法对于处理不同地点数量的轨迹数据具有较优的性能。GSP算法变化趋势并不平缓，这是因为轨迹数据增加并不表明得到的频繁轨迹增加。如一个含1 000数据点的轨迹集可能有100个频繁1项集，但是一个含500个数据点的轨迹集可能有200个频繁1项集。GSP算法需多次扫描数据库，扫描到的频繁1项集越多，程序运行时间越长。而该算法只需要扫描一次数据库，所以比GSP算法性能更稳定。

3) 第三个对比如图 7所示。最小支持度固定在0.55，使用了4 000条轨迹进行测试。可以看出随着轨迹平均长度增加，程序运行时间越来越短，且变化平稳。该算法的运行时间比另外两个更短。

4) 第四个对比如图 8所示，规定参与测试的轨迹平均长度为20，最小支持度阈值设为0.55。所使用的轨迹数量由500～2 500。程序运行时间随着轨迹数量的增长而增长。该算法比其余两个算法整体运行时间短，且增长趋势更为平缓，可见性能更优。

5 结束语

本文以FP-tree为模型，提出了一种更加优化且适用于处理轨迹数据的频繁轨迹模式挖掘算法NFTM。通过有针对性的预处理模块精简了轨迹数据。在构建轨迹树部分，只进行一次数据库扫描，并且生成按照真实顺序排列的同时具备时空属性的轨迹树。最后充分考虑各种现实因素，在挖掘部分使用数组作为存储结构，并加入了自主限定时间、频率的思想，使挖掘出的频繁轨迹更加人性化，符合实际应用需求。