陈 刚，钱 猛，刘 金

中国工程物理研究院 计算机应用研究所，四川 绵阳 621900

基于划分的高效异常轨迹检测

陈 刚，钱 猛，刘 金

中国工程物理研究院 计算机应用研究所，四川 绵阳 621900

1 引言

随着多种移动定位、传感器网络和无线通信技术的发展，人们可以收集和存储越来越多的轨迹数据[1]，如何从这些数据中发现异常模式引起了许多研究人员的注意[2-4]。然而，现存的方法由于采用的轨迹描述方法和匹配（距离）函数的不同，导致挖掘算法在检测结果和检测效率方面存在诸多不同。

Knorr等人利用传统的基于距离的异常挖掘方法检测数据集中的异常轨迹[5-7]。由于该方法利用的都是轨迹的全局属性，它忽略了轨迹间的局部差异，因此，该算法只能应用于长度较短且较为简单的轨迹。

Li等人提出了基于轨迹代表模式motifs的异常轨迹检测算法[8]，它使用聚类方法从滑动窗口中收集motif，然后用分类的思想过滤异常轨迹。该算法由于采用了分类的思想，因此在实际应用中需要寻找较为标准的训练集。

J.-G Lee等人提出基于二阶段划分思想的异常轨迹处理算法TRAOD[9]，它首先将每条轨迹划分为多个连续线段的组合，然后采用Hausdorff距离[10-12]来计算任意两个线段之间的距离，从而挖掘出异常轨迹片段。TRAOD算法较好地解决了长轨迹间的匹配问题，但它同时存在以下几个问题：首先，使用近似方法获得的线段同样会隐藏轨迹的部分局部特征；其次，Hausdorff距离这种度量方法并不符合欧式空间的标准，进而无法使用传统的索引方法来提高计算效率；……