轨迹数据的多特征融合及检测方法

饶元淇，赵旭俊，蔡江辉

(太原科技大学 计算机科学与技术学院，太原 030024)

1 引 言

在如今智能化时代，随着定位设备、Wi-Fi网络、视频监控、以及无线传感器等设备的发展，产生越来越多的轨迹数据[1].同时，这些数据中又包含了大量的信息，在无人驾驶、导航系统、智能化的交通系统等领域有关轨迹数据的研究需求不断日益增长.传统的检测方法将轨迹视为一维序列，并在单一尺度下进行处理，无法挖掘不同特征尺度下丰富多样的信息[1].由于轨迹数据中隐藏着一系列影响用户出行行为的复杂特征，因此挖掘轨迹仍然具有一定的挑战性[2,3].例如，在气象台台风检测，可以探测到台风路径的变化，通过提前预测轨迹路径.对于可能造成的损失提前做好防护措施，以减少损失；在“网约车”软件使用过程中，系统检测到车辆异常轨迹时，对乘客发出安全性预警等，可以有效避免危险的发生.因此，在大规模轨迹数据集中挖掘轨迹具有很重要的现实意义和实用价值.如何从大规模的轨迹数据中挖掘出有用的知识，并且有效的发现许多隐藏在数据信息中的有价值的轨迹数据越来越受到人们的关注.

传统的轨迹检测方法是将轨迹数据进行切分为子段，综合考虑轨迹子段的比例和轨迹子段的密度，确定轨迹数据的划分[4-6].研究将轨迹数据直接以整条轨迹数据作为基本单元的轨迹检测的算法相对较少.因此，本文设计了一种基于图划分的轨迹聚类方法，首先使用核函数可以将轨迹数据映射到高维空间，使得数据线性可分[7].然后，通过构建轨迹数据无向加权图，使用核函数度量图中节点之间的相似度，通过谱聚类进行图划分得到的子图.最后，将轨迹数据划分到不同的类.由于轨迹数据存在更多的不确定性的形状，因此，采用谱聚类会得到更好的检测效果.

2 相关工作

轨迹数据检测技术可以分为监督、半监督、和非监督，主要包括的方法有基于分类的方法、基于聚类的方法、基于密度的方法、基于统计的方法等.

2.1 基于距离的轨迹检测方法

Knorr[8]等提出了基于距离的轨迹异常检测的概念,属于最早的轨迹异常数据检测研究.他将每个轨迹转转换一个组合的对象，组合的对象由4个关键的特征组成：位置、长度、方向和速度.然后采用传统的基于距离的异常点检测方法来发现异常轨迹.该方法的不足之处在于，其误差在整个轨迹平均之后，可能无法检测出异常子轨迹.为了克服这一问题，Lee[9]等人提出了一种分段检测框架，并且在这个框架的基础上提出了一种异常轨迹检测的方法TRAOD.TRAOD包括两个阶段：1)划分阶段;2)检测阶段.首先对于轨迹进行粗粒度划分，然后对轨迹进行细粒度划分.在检测阶段，采用基于距离的检测方法检测边远的轨迹片段.采用模式识别中的Hausdorff距离[10]来测量两个分段之间的距离.TRAOD中没有消除子轨迹之间的共同偏差.Liu[11]等提出一种新的距离函数，该函数有最小的Hausdorff距离推导而来.该距离函数以数量为k的连续点作为基本单元计算轨迹的局部异常点.基于局部异常点来检测两种轨迹是否具有全局相似性.当目标轨迹没有足够的相似轨迹时，将被视为异常轨迹.同时，为了提高算法性能引入R树.为了解决静态数据序列没有考虑有价值的特征问题，Yuan[12]等人提出了一种基于结构相似的轨迹异常检测算法(TOD-SS).TOD-SS考虑了更多的轨迹特征，每个特征的重要性可以根据权重进行调整.结构相似性不仅能更好地反应内部和外部特征的差异，而且还能增强分析效果.

2.2 基于密度的轨迹检测方法

为了克服距离方法在处理复杂分布特征数据集的方面存在不足，Liu等[13]提出了基于密度的轨迹异常检测方法DBTOD.DBTOD利用TRAOD引入了考虑邻域对象分布的轨迹密度概念.轨迹密度由两部分组成：子轨迹之间的距离和给定范围内子轨迹的数量.DBTOD算法充分利用了分区检测框架，由划分阶段和检测阶段组成.使用与TRAOD相同的轨迹划分算法，将每个轨迹划分成一组t分段，然后用基于密度的检测算法代替基于距离的检测算法来发现异常自轨迹.与基于距离的算法相比，该方法不仅能够检测异常轨迹数据和异常局部轨迹数据，还克服了基于距离的方法中参数敏感的问题.为了加快轨迹异常点检测的速度，刘等提出了用R-Tree数据结构来存储轨迹数据.

2.3 基于分类的轨迹检测方法

王[14]等提出了以运动方向为主导的轨迹相似性度量方法，运用聚类方法来分析轨迹数据.Li等人[15]提出了一种基于分类的轨迹异常检测算法Roam.该方法中常用的模式使用基序来表示轨迹.该框架由3个部分组成：1)基于单元的特征空间.将轨迹划分为基序，并在基序上构造一个具有相关属性的多维特征空间；2)自动提取层次结构.通过研究轨迹中的模式，得到特征空间中的层次结构；3)基于规则的分级分类器.基于规则的分级分类器可以对特征空间分层探索，找到有效的分类区域.Lee[16]使用基于层次聚类的方法分类轨迹数据.

综上所述，在传统的融合度量轨迹的检测算法是针对于数据位置信息的处理，仅仅在单一特征上评测轨迹的相似度，忽略了轨迹信息中的其他包含特征信息.对于交通轨迹的大数据的挖掘[17]忽略了速度信息等在内的其他特征.不同的观测对象感兴趣的轨迹特征也不尽相同.例如，在同一路段车辆轨迹位置信息相同，如果有远高于其他车辆轨迹的数据，有可能存在车辆超速或者紧急事件(消防车辆、救护车辆等).如果仅从位置信息一个特征上度量不能检测出此类信息.

基于上面描述的局限性，本文提出轨迹融合度量检测算法Trajectory Detection Based on Multi Feature Fusion(TD-MFF)，主要分为3个部分：1)运用相应核函数方法分别在轨迹的空间特征、速度特征和时间特征3个特征上对轨迹数据进行相似性度量；2)设计了一个融合多特征的核函数方法得到融合特征的相似性度量；3)通过谱聚类对图模型进行划分子图，最后在子图中搜索数据.最后，设计了一种异常轨迹的检测方法.

3 多特征融合的轨迹数据度量及检测

轨迹数据包含有不同特征信息，取任意两条数据，在不同特征描述下的相似度有所不同.针对这种在相同数据集中取不同特征情况下会产生不同的度量结果的问题，本文将轨迹数据抽象为无向图，其中每条数据用图中一个节点表示，用节点间的权值来表示轨迹数据间的相似度度量.在轨迹相似性度量过程中，直接度量整段轨迹数据相似度会产生：位置特征数据不能对齐计算，速度特征数据不能处理轨迹数据中速度信息包含的轨迹位置等问题.核函数是将数据样本空间映射到高维特征空间[18]，由于经过了核函数的映射,使原来没有显现的特征突现出来.

轨迹数据往往包含有不同的特征属性，不同特征属性的度量方式不能统一.例如：对于位置特征属性，由于不同的轨迹数据中包含点的数量不同，因此，我们需要通过对数据的拉伸或者伸缩目的是使得数据对齐；对于速度特征属性，我们需要考虑轨迹的速度信息带有位置属性，我们需要比较在不同位置的速度大小和方向.因此，不同的特征使用不同的核函数来度量.

由于轨迹数据被映射到高维空间通过核函数，我们很难判别映射后数据的分布情况.传统的聚类算法，例如K-means，很难适应这种现象.这里，我们采用谱聚类的方法.与传统的比较算法相比，通过特征融合度量后结合谱聚类的方法可以更好的辨别、提取并放大有用的特征，正确的聚类结果即使传统聚类算法不能得到很好的结果的情况下.

3.1 特征融合轨迹描述及特征信息建模

本文将轨迹数据抽象成为图中节点，轨迹数据形式化描述如下：

定义 1.定义一个轨迹数据X={x1,…,xk,…,xn,}T.其中，轨迹数据元素xk是由nk连续的点构成的元素，nk={sk,vk,ek}，sk表示位置特征信息，vk表示速度特征信息，ek表示时间戳的信息.

定义 2.给定N条轨迹数据，定义轨迹数据图为G，令N为图G的节点数量.其中，一个节点代表一条轨迹数据.轨迹数据图G是一个无向连通图，由G=(V,E,ω)表示.其中：

V={v1,v2,…,vn}是节点构成的集合表示N条轨迹数据；

E={e1,e2,…,en}是节点之间边的集合；

ω={ω1,ω2,…,ωn}是节点之间的边的权值表示两条轨迹的相似度.

轨迹数据图G中节点之间的相似度ω是通过多个信息属性度量后加权求和得到的融合了多个测量信息的权值.本文使用加权组合相似矩阵K(xk,xk′)来计算轨迹数据间的相似性，构造出相似矩阵K，我们令ω=K得出节点之间的相似度.每个元素K(xk,xk′)表示图中两个节点的相似度.本文定义K(xk,xk′):

(1)

其中，K(xk,xk)=1，k=1,2,…,N,K(xk,xk)=1表示一条轨迹与其自身的相似性最大，αm表示预先分配的权重.用来反映人们对于第m维的特征的感兴趣程度.

空间位置特征相似度量.在处理两条轨迹的位置信息时候，每条轨迹的位置信息随着时间的变化，因此，轨迹数据采取的信息通常存在数据点数量不同情况，在比较相似的过程中，必然出现不同数量的位置点进行匹配的情况.为了解决轨迹位置信息在度量过程中出现的这种不匹配的情况，the Global Alignment Kernel(GAK)[19]利用动态规划时间序列(DTW)思想构造核函数.但是，DTW算法复杂度高，需要遍历整个搜索范围.为了解决这一问题，本文搜索路径时增加了路径约束提高计算效率.如图1中所示，白色区域即为约简的空间，减少了寻找路径时候的搜索空间.

图1 粗粒度和细粒度Fig.1 Coarse-grained and fine-grained

cx(π1(i))和cy(π2(j))表示轨迹π1(i)和π2(j)的二维空间坐标.为了解决计算两段序列相似度存在序列长度不同的问题，采用了快速DTW思想：1)轨迹像素粗粒度化.从矩阵的左下角到右上角计算最短的欧式距离ei,j=‖π1(i)-π2(j)‖2确定路径di,j.公式(2)展示了计算最短路径的方法：从目标位置的右di-1,j、上di,j-1和斜对角向上di-1,j-1三个方向进行前进搜索，取三个方向之中的最小值.

di,j=eij+min(di-1,j,di,j-1,di-1,j-1)

(2)

其中，di,j表示当前需要计算的路径距离，eij表示当前两个位置点之间的欧式距离，min(di-1,j,di,j-1,di-1,j-1)表示从开始位置到该位置的最短距离.2)轨迹像素细粒度化.细粒度的像素是粗粒度的一半，在已经确定的粗粒度像素中重复第一步的操作确定路径.3)然后，重复前两步操作，直到确定最终路径.计算出两条路径的结束位置cx(π1(m)),cy(π2(n))的距离，记作φ(x,y)=dm,n.本文构造空间位置特征度量的核函数见公式(3)：

Kp(cx,cy)=e-φ(x,y)

(3)

速度特征相似度量.在分析真实的轨迹数据中，轨迹在不同位置的速度可能包含不同的意义，比如某一区域的瞬时速度相对集中于较小的区间，这个区域可能是十字路口或者学校路段；在某一区域车辆方向如果集中于一个较小的角度范围，那么这个路段可能禁止掉头等情况.如果出现异常的瞬时速度或者方向.从轨迹的位置这一个特征角度，不足以选取出有关的轨迹信息.同时，对于轨迹中的速度信息，由于轨迹数据的速度信息包含有：速度的大小，速度的方向并且需要考虑此时的速度位置.传统度量矢量数据的方法不能同时处理矢量速度和位置信息.本文这里使用图像处理中计算直方图的卡方的距离度量.

首先，粗粒度划分速度信息的大小和方向为L量级.类似于图像中的灰度值划分，标准化速度的大小和方向数据.同量级下，将相同的速度方向和速度大小的个数记录到不同的直方图，建立速度的直方图特征hk.然后，细粒度划分速度数据的大小和方向划分到L/2量级，重复上述操作，直到将数据划分到预期量级.最后，计算轨迹数据k和k′的直方图hk(i)和hk′(i)的卡方距离.速度特征的相似度度量Kh(k,k′)，如公式 (4)所示：

(4)

时间特征相似度量.由于轨迹带有的时间戳信息，本文使用t(0)表示轨迹的开始时间，t(1)表示轨迹的结束时间.将两条轨迹的开始时间t(0)和结束时间t(1)分别进行做差后，通过公式(5)t(k,k′)求和来比较轨迹在时间度量上的差异.最后，本文使用高斯核函数度量时间特征相似，通过Kh(k,k′)公式(6)计算度量相似度：

(5)

Kt(k,k′)=e-βt(k,k′)

(6)

给定有N条轨迹数据，则参数β=|n(k)-n(k′)|,每个轨迹数据时间数据数目不同，用两条轨迹中时间点个数差的作为参数，表示个数差值越小时间特征相似度越大.

对于同一个轨迹数据集来说，不同的观察者感兴趣的场景不同.例如，乘客在乘坐出租车时候，他关心的是司机师傅是否绕路；当私家车主在开车旅行时候，关心的是车辆是否超速；在当前时间段，对于应急车辆来说，它是很重要的对于是否可以避开拥挤路段.因此，与在单一的特征上进行度量的传统的度量方式不同，本文使用一个结合了公式(3)中的位置度量Kp(k,k′)，公式(4)中的速度度量Kh(k,k′)，公式(6)中的时间信息度量Kt(k,k′)的融合相似度量K(xk,xk′)，如公式(7)所示：

(7)

其中，αp代表的Kp(k,k′)权重值，αh代表的Kh(k,k′)权重值，αt代表Kt(k,k′)权重值.由于人们对于相同数据在不同场景下所关注的特征信息有所不同，可以通过调整公式(7)中不同特征度量的权重值来满足人们不同场景下的需求.例如，当我们想了解车辆是否绕路等信息时候，我们可以调整对于位置信息度量的权值αp；如果我们想了解车辆是否有超速情况的时候，我们可以调整对于速度信息度量的权值αh；如果我们想了解轨迹数据产生的时间段分布时候，可以增加时间信息度量的权值αt.最终，通过调整权值来搜寻出符合观察者的需求的数据信息.

3.2 基于谱聚类的轨迹异常检测

本文采用谱聚类的方法对轨迹数据的图模型中的节点对象进行划分.聚类的结果是使得组内的对象之间很相似，而组与组之间的对象不相似.在谱聚类的模型中，聚类将图划分为若干个子图，使得同一个子图中的对象很相似.但是,不同子图内的对象相似程度不高.

定义 3.给定图G=，图G′=.若集合V′⊆V，E′⊆E，ω′⊆ω,则称图G′是图G的一个子图,也称子图G′.

(8)

轨迹特征融合的相似度量.经过特征融合度量的数据分布很难判断，针对这一情况，本文采用谱聚类的方法将图的划分若干个子图，具体轨迹数据的检测方法步骤如下：

第1步.本文将每条轨迹抽象为图中的一个节点，运用公式K(xk,xk′)=αpKp(k,k′)+αhKh(k,k′)+αtKt(k,k′),来计算不同轨迹节点之间的相似度度量.

第2步.构建亲和矩阵W，将不同轨迹的相似度度量放到一个矩阵W中，其中wi,j=K(xk,xk′)，wkk′∈W.

第4步.求解矩阵L中的特征值k.本文计算特征值之间的差值K=ki+1-ki，如果Ki+1/Ki和Ki/Ki-1值出现了较大的变化，本文就将聚类簇的个数选取为K.

第5步.将特征向量使用K-means进行聚类，轨迹节点划分到各个子图G′中.最后，输出所有子图的划分.

4 算法描述

本文采用融合度量轨迹数据的方法，运用核函数和图分割方法对轨迹数据进行图划分为若干个子图，将轨迹数据划分到不同类别.

轨迹检测算法Trajectory Detection Based on Multi Feature Fusion(TD-MFF)算法具体步骤如下：首先，算法将每条轨迹抽象为一个节点对象，在轨迹融合度量fusion_metric()中运用核函数计算轨迹数据在空间特征，速度特征和时间特征上的相似度量.最后，在第22行构建了轨迹融合度量的方法.在轨迹融合度量TD-MFF算法中，构建轨迹数据的图模型，运用谱聚类进行图分割为子图，每个子图内的数据即为相似的轨迹数据.在异常检测算法中，设置阈值τ，通过搜索权值系数小于阈值τ的子图来判断轨迹数据的异常.

算法1.轨迹融合度量fusion_metric()

输入：轨迹数据xk，xk′

输出：融合轨迹度量

1.xk,xk′←轨迹k，k′中的轨迹信息

2.In Coarse-grained: //在粗粒度下计算

3. In Fine-grained://在细粒度下计算

4. shrink(xk) = reduce_by_half(xk)//

5. shrink(xk′) =reduce_by_half(xk′)

6. window =window(len(xk),len(xk′),radius)

7.fori in window{

8.forj in window{

9.di,j=eij+min(di-1,j,di,j-1,di-1,j-1)

10.}}//将计算window中的最短距离

11.dn1,n2←记录最短路径值

12.Kp(k,k′)←exp(-dn1,n2)//取DTW的最短距离计算得到位置相似度度量

13.hk(i),hk′(i)←xk,xk′//建立直方图

14.for(i =0;i

15.for(j=0; j

16.hk(i)←Bin 1//统计轨迹1中该区域的速度大小和速度方向的个数

17.hk′(i)←(dic2)//统计轨迹2中该区域的速度大小和速度方向的个数

20.β=|n(k)-n(k′)|

21.Kp(k,k′)←exp(-β·RBF)//计算时间特征的相似度量

22.K(xk,xk′)=αpKp(k,k′)+αhKh(k,k′)+αtKt(k,k′)

23.returnK(xk,xk′)//返回融合度量值

在fusion_metric()中，第2-第10行在粗粒度和细粒度约束下约简了搜索范围，获得最短路径距离.第12行中运用公式(3)计算出计算空间位置特征的相似度.第13-第17行构建了轨迹速度的直方图信息，第18行运用公式(4)计算了直方图距离，即为速度特征的相似度.第19-第21行用公式(5)和公式(6)计算了时间特征的相似度.最后，在第22行运用公式(7)将3种特征融合，构建了轨迹的融合度量.

算法2.融合度量TD-MFF算法：

输入：轨迹数据

输出：轨迹数据划分

1.for(i =0;i

2.for(j=0;j

3.K(xi,xj)=fusion_metric(xi,xj)

4.wi,j=K(xi,xj)

5.W←wi,j//构建亲和矩阵

6.}}

8.L=D-W//构建拉普拉斯矩阵

9.K-means(L) //划分子图G′

10.returnG′

TD-MFF算法通过谱聚类对轨迹数据进行分类.第1-第6行是计算轨迹间的特征融合相似度，第7行计算相似矩阵的度矩阵D，第7-第8行构建拉普拉斯矩阵L.第9行采用K-means算法聚类，将每个图模型中的节点划分到子图中.最后，输出划分好的轨迹分类.

算法3.异常检测

输入：图模型数据G

输出：异常轨迹

2. TR←V//记录子图的节点标号

3. outlier←transform(TR)//转化标号为轨迹数据

4.returnoutlier

在异常检测算法中，算法第1行是判断子图的稀疏系数，对于符合异常条件，即子图的稀疏系数小于阈值τ的子图在第3行进行转换数据.最后，输出符合稀疏系数M小于阈值τ的子图中的轨迹数据即为异常轨迹数据.

5 实验结果及分析

实验环境：Intel(R)Core(TM)i5-6640HQ CPU,8GB内存，Windows 10操作系统，PyCharm作为开发平台，采用Python语言实现算法的编程.

为了验证本文中算法的可行性，本文采用的数据集是2007年2月20日上海市出租车轨迹数据.数据集中包含了4000多辆出租车在24小时内的车辆行驶轨迹，车辆的行驶轨迹采样间隔为1min，其中，轨迹数据属性包括车辆的ID号，车辆的经度、维度信息，时间戳信息，瞬时速度的大小，车辆朝向(从顺时针方向与北方向的夹角).每条轨迹信息包含数据信息条数不相等，大约在1700～7000条数量不等的信息.本文中的将轨迹的属性处理为轨迹的位置特征(经度、纬度信息)，速度特征(经度、纬度信息，瞬时速度的大小，车辆朝向)，时间特征(时间戳)作为轨迹的位置特征.由于轨迹信息量大，本文每隔20次取一次点，进行实验.本文首先选取了划分两个数据集，每个数据集包含82条不同轨迹；文本采用2017-2018年飓风数据进行测试，数据包含了1131条轨迹的28798个数据点进行测试.为了更好展示实验结果，本节以数据可视化的方式展示了实验结果.

5.1 特征融合的聚类实验

上海出租车轨迹实验.实验测试了的出租车辆轨迹数据在不同参数下的聚类实验结果，其中设置实验参数为：k=5.图2展示了在单一特征下的轨迹聚类结果和融合度量的轨迹聚类结果的对比.

单一特征度量.图2(a)中展示了度量速度特征的相似度聚类结果，令αh=1.轨迹数据的速度特征带有位置属性，从数据聚类效果来看比较分散，效果较差；在图2(b)中展示了度量空间位置特征相似度的聚类结果，令αp=0.5.空间位置特征度量下的效果具有明显的区分效果.

融合特征度量.图2(c)展示了融合特征下的聚类效果，令αp=0.5，αh=0.5.直观的看，在融合特征下，TD-MFF算法对轨迹数据划分明显.

图2 特征融合度量聚类实验Fig.2 Result on measurement of position feature

图2(b)和图2(c)中实验结果的对比：图2(b)中的区域I有两个部分距离较远，在图2(c)中划分为两个类，明显的图2(c)的划分更为合理.同时，图2(c)中的区域V是两条数据偏离度大的轨迹数据，而其他区域的数据相对集中.因此，特征融合后的聚类效果更好.

直观地看出，使用特征融合后的度量检测的轨迹划分更有意义.这是由于使用DTW核函数度量是对于两条轨迹直接进行度量，很容易忽略掉局部数据.包含了位置特征和速度特征的融合度量有了局部调整，很好的弥补了直接度量位置特征时候的不足.这是因为速度特征同时带有位置标签，采用直方图核函数的匹配使得会检测到得局部的速度信息，这样可以对于位置度量进行一个局部调整，很好的弥补了位置特征在直接度量时候无法检测到局部检测的不足.TD-MFF算法实验测试了融合度量的表现更好的聚类效果，特征融合度量方法是十分有效的.

5.2 轨迹的异常检测

异常轨迹检测实验.实验测试了算法在异常轨迹场景下的性能.图3展示TD-MFF算法在异常检测中的实验结果.采用融合度量方式.实验中，令αp=0.5，αh=0.5；设置聚类个数k=3，阈值τ=0.

图3 轨迹异常检测实验Fig.3 Result on measurement of fusion feature

实验结果展示了TD-MFF有效地将数据在划分的3个区域中.其中，区域I部分是33条轨迹的聚合区域，区域II和III中分别包含了一条轨迹.异常检测算法输出了区域II和III中的轨迹数据.

实验结果表明，TD-MFF算法可以有效的检测出全局的异常轨迹，因此，TD-MFF算法可以有效地在异常检测场景下使用.但是，由于算法在度量数据相似方法上采用了全局度量，使得图4中区域I存在的局部异常现象无法检测出来.

图4 TD-MFF算法和TRAOD算法对比实验Fig.4 Experimental comparison between TD-MFF and TRAOD

5.3 算法比较

采用轨迹数404条，其中参数设置：D=15.0,P=1.0,F=0.1,WeightPar=5,WeightAngle=5 WeightPer=5；TD-MFF算法参数设置:k=35，τ=0.在算法的参数设置中，TD-MFF算法设置了2个参数，TRAOD算法在6个参数.在参数设置上，TD-MFF算法具有优势，更少的参数设置可以有效减少的人为因素的干扰，使得结果更加客观.

图4(a)中展示了TRAOD检测30条异常轨迹，图4(b)中展示了TD-MFF算法检测41条异常轨迹.从比较中可以看出两个算法找出的异常轨迹有许多明显的相同部分.从图4(a)中标注的记号I，II处可以看出，算法TD-MFF在记号I，II找出了在位置上偏出的异常数据，在记号3处多数轨迹方向为东西走势，而III处的走势为南北走向，是一处明显的异常数据.TRAOD在图中的左下方没有找到异常数据，说明TD-MFF算法搜索的异常轨迹数据.在实验过程中，当数据为1131条轨迹时，TRAOD算法由于内存原因无法计算，而TD-MFF算法可以检测出异常轨迹，因此，在处理大规模轨迹数据时候，TD-MFF是十分有效的.

在算法效率上.我们比较了TD-MFF、TPRO和TRAOD 3种算法在不同数目的数据下的时间.表1中展示了3种算法在比较时的参数设置.图5展示了算法在不同轨迹数据集上的时间消耗.由于TRAOD算法在大规模数据下会产生内存溢出错误，因此我们这里采用数据规模为100，200和400.

表1 参数设置Table 1 Parameter settings

图5中数据表明，3种算法的时间消耗与数据集的规模呈正相关.其中，TD-MFF算法在200和400条轨迹的数据集测试中明显优于TPRO和TRAOD.

图5 效率比较Fig.5 Efficiency comparison

实验中当轨迹数量达到1000条时候会TRAOD算法会产生内存溢出的错误.TRAOD算法是将轨迹切分为子段，然后比较子段之间的相似度.在大规模数据集中，轨迹子段的划分会消耗时间，同时，轨迹子段需要同轨迹集中所有的轨迹子段进行比较，消耗大量内存并且容易产生内存溢出.TPRO是将地图划分为网格，仅对于网格周围的数据进行比较，与TRAOD相比减少了计算成本.TD-MFF算法使用核函数将数据映射到一个图模型中，简化了数据模型，提高了计算效率.从实验结果来看，TD-MFF算法效率高于TPRO和TRAOD算法.

6 结束语

本文针对轨迹数据，给出了一种特征融合度量的轨迹数据挖掘算法TD-MFF.TD-MFF算法在多个特征上度量轨迹数据相似度，有效的解决了传统算法中的单一度量导致的挖掘数据不充分.从多个特征进行数据挖掘，更能发现在大量数据中存在的隐藏信息；同时，TD-MFF算法并且有效减少了传统方法中的多个参数设置问题，仅仅需要从观察者的角度出发，增加其感兴趣的特征的权值比重，更加倾向于可发现观察者所关注的问题；最后，采用真实数据进行验证.下一步将对于算法进行并行化设计，以便算法适应更加海量的轨迹数据.