本发明涉及一种基于主动预测的轨迹数据异常检测及修正方法，首先对已有的基于位置的轨迹数据根据K邻居信息进行主动预测，接着将预测产生的新数据和数据集中原有数据相减，构造差值矩阵，在此基础上进行移动轨迹数据异常的概率推断，然后在时间维度上进行时间窗口前向扫描，对每个窗口内的数据异常概率进行构造，寻找异常数据区域进行矩阵数据修补，最终修正完整个数据矩阵。本发明所述方法可以应用于包括智慧城市中普通道路、隧道与桥梁的交通监测中。
1.基于主动预测的轨迹数据异常检测及修正方法，其特征在于，包括：获取移动轨迹数据，并以时间片为列，位置信息为矩阵内容构建轨迹数据矩阵D；
轮询轨迹数据矩阵中D的列，主动清除单列时间片下的位置数据，结合被清除单列时间片前后相邻的K列时间片数据，利用矩阵分解的方法预测缺失值，包括：将轨迹数据矩阵分解为矩阵U和V；
随机初始化矩阵U和V，采用梯度下降算法更新U、V，使得 取得最小值；
其中，X为被清除单列时间片前后相邻的K列时间片中所有节点的轨迹数据矩阵，矩阵T是对矩阵X的预测，V 为V的转置矩阵，J为X和 之间误差的Frobenius范数的平方；
重复轮询、清除、预测，将预测所得的时间片列数据按时间片排列构建新矩阵D1；
将D1和D相减，构造差值矩阵，对获取的差值矩阵，取某一列对每个数据计算其异常概率，获得概率列向量；依次计算差值矩阵每一列的异常概率，获得若干个概率列向量；将所述概率列向量按照时间片先后顺序排列，构建得到全局移动轨迹数据异常概率矩阵P；
对于矩阵中某一数据dij，获取差值矩阵中数据相对其所在列所有数据平均值的偏移值；
获取dij所在列所有数据的偏移值，累加得到总偏移值；
dij的偏移值与总偏移值的比值即为dij的异常概率；
设定时间窗口，利用时间窗口扫描P，对每个窗口内的数据异常概率进行判别，寻找D1中对应的异常数据区域进行矩阵数据修补，最终修正完整个数据矩阵。
2.根据权利要求1所述的方法，其特征在于，所述偏移值采用 表征，其中 为dij所在列所有数据平均值。
3.根据权利要求1所述的方法，其特征在于，预设阈值ε，当差值矩阵中数据的异常概率超出预设阈值ε，判定当前轨迹数据异常。
4.根据权利要求1所述的方法，其特征在于，所述时间窗口的大小基于K值确定。
5.根据权利要求1或4所述的方法，其特征在于，所述时间窗口的大小为4K。
6.根据权利要求1所述的方法，其特征在于，所述对每个窗口内的数据异常概率进行判别，寻找D1中对应的异常数据区域进行矩阵数据修补的方式为：i. 预设阈值ε，利用时间窗口遍历矩阵P，扫描到异常概率高于ε的数据时，判定该数据为异常数据点，将以该异常数据点为中心，K为边长的正方形区域所涉及的概率数据对应的D1中的轨迹数据清除；
ii. 以该异常数据点所在列前后nK列时间片所有节点的轨迹数据矩阵对D1进行矩阵修补得到新的矩阵D2，n为正整数，n≥2；
iii. 将矩阵D与D2相减得到新的距离差值矩阵Δ1；
iv. 对Δ1中的每个数据计算其轨迹数据异常概率进而得到异常概率矩阵P1；
v. 利用时间窗口继续前向扫描出P1中下一个异常概率高于ε的数据，判定该数据为异常数据点，将以该异常数据点为中心，K为边长的正方形所涉及的概率数据对应的D1中的轨迹数据清除；
vi. 重复ii至v，直至扫描更新结束，最终所得的矩阵即为轨迹数据修正后矩阵。
7.根据权利要求6所述的方法，其特征在于，所述ii中，以所述预测缺失值的方式进行矩阵修补。
基于主动预测的轨迹数据异常检测及修正方法
技术领域
[0001] 本发明申请涉及轨迹数据检测技术领域，具体涉及一种基于主动预测的轨迹数据异常检测及修正方法。
背景技术
[0002] 随着定位技术和无线通信技术的发展和成熟，各种互联网应用数据的爆炸式增长给数据集的收集和分析带来了很大的挑战。带有位置信息数据集的收集对于节点移动轨迹的提取与分析至关重要，但是由于位置定位的误差与数据收集的不完备造成的部分轨迹数据异常和丢失对运用数据分析和挖掘工具/方法的移动行为建模和分析产生极大的干扰，损坏最终的结果。因此，如何从众多移动轨迹中检测出异常轨迹是一个热点问题。
[0003] 目前存在的轨迹数据异常检测的方法主要分为分类检测法、历史轨迹相似性检测法、距离检测法和网格划分检测法几种。张雷提出一种基于轨迹聚类的异常检测方法，先基于时空特征对每条轨迹中的轨迹点聚类，再根据得到的轨迹聚簇计算异常阈值进行检测，将轨迹异常分为多种情况。王伟等人采用历史轨迹相似性检测法，通过待检测轨迹每一个轨迹点与历史轨迹的对比，找出异常的轨迹点，再根据相关数据确定轨迹发生异常的片段和程度。但由于每一条轨迹都必须与整个轨迹数据库进行比较，此方法的算法空间和时间的复杂度都较高。CN107826118A提供了一种综合速度、加速度、车辆偏离距离、跟车间距、换道数据几个维度的数据信息判断异常驾驶行为的方法，重点在于根据历史轨迹数据，计算异常驾驶判别的综合函数。CN108710637A提供了一种基于出发点到当前点的直线距离与行驶距离和驾驶时间之间的关系，建立时空模型并进行训练的出租车异常轨迹实时检测方法。该方法可以准确地选择出正常轨迹中的异常轨迹，但十分依赖训练集，受影响的可能性很大。CN107316459A提供了一种将统计的各个时段内与待测车辆相同类型的相邻车辆总数与阈值相比判断异常的检测方法，该方法主要侧重于对时间段内车辆数量的分析。
发明内容
[0004] 本发明的目的在于克服上述现有技术的缺点，提供一种基于主动预测的轨迹数据异常检测及修正方法，该方法以每个移动节点在不同时间片的位置为输入，主动对其进行预测并计算异常概率，能够快速地根据局部信息检测出异常的移动轨迹数据。
[0005] 为实现上述发明目的，本发明采取如下技术方案：
[0006] 基于主动预测的轨迹数据异常检测及修正方法，包括：
[0007] 获取移动轨迹数据，并以时间片为列，位置信息为矩阵内容构建轨迹数据矩阵D；
[0008] 轮询轨迹数据矩阵中D的列，主动清除单列时间片下的位置数据，结合被清除单列时间片前后相邻的K列时间片数据，利用矩阵分解的方法预测缺失值；
[0009] 重复轮询、清除、预测，将预测所得的时间片列数据按时间片排列构建新矩阵D1；
[0010] 将D1和D相减，构造差值矩阵，对差值矩阵中的各数据计算异常概率，构建全局移动轨迹数据异常概率矩阵P；
[0011] 设定时间窗口，利用时间窗口扫描P，对每个窗口内的数据异常概率进行判别，寻找D1中对应的异常数据区域进行矩阵数据修补，最终修正完整个数据矩阵。
[0012] 本发明所指数据的清除，是指将矩阵点/行/列/区域数据清除，但位置保留。
[0013] 所指轨迹数据包括但不限于移动自组织网络中、群智感知中和移动边缘计算中节点的移动数据与车联网中车辆轨迹数据。
[0014] 作为一种优选的实施方式，所述利用矩阵分解的方法预测缺失值的方式为：
[0015] 将轨迹数据矩阵分解为矩阵U和V；
[0016] 随机初始化矩阵U和V，采用梯度下降算法更新U、V，使得 取得最小值；
[0017] 其中，X为被清除单列时间片前后相邻的K列时间片中所有节点的轨迹数据矩阵，T矩阵 是对矩阵X的预测，V为V的转置矩阵，J为X和 之间误差的Frobenius范数的平方。
[0018] 作为一种优选的实施方式，所述对差值矩阵中的数据计算异常概率，构建全局移动轨迹数据异常概率矩阵的方式为：
[0019] 对获取的差值矩阵，取某一列对每个数据计算其异常概率，获得概率列向量；
[0020] 依次计算差值矩阵每一列的异常概率，获得若干个概率列向量；
[0021] 将所述概率列向量按照时间片先后顺序排列，构建得到全局移动轨迹数据异常概率矩阵。
[0022] 作为一种优选的实施方式，所述对差值矩阵中的各数据计算异常概率的方式为：
[0023] 对于矩阵中某一数据dij，获取差值矩阵中数据相对其所在列所有数据平均值的偏移值；
[0024] 获取dij所在列所有数据的偏移值，累加得到总偏移值；
[0025] dij的偏移值与总偏移值的比值即为dij的异常概率。
[0026] 作为一种优选的实施方式，所述偏移值采用 表征，其中 为dij所在列所有数据平均值。
[0027] 作为一种优选的实施方式，预设阈值ε，当差值矩阵中数据的异常概率超出预设阈值ε，判定当前轨迹数据异常。
[0028] 作为一种优选的实施方式，所述时间窗口的大小基于K值确定。
[0029] 作为一种优选的实施方式，所述时间窗口的大小为4K。
[0030] 作为一种优选的实施方式，所述对每个窗口内的数据异常概率进行判别，寻找D1中对应的异常数据区域进行矩阵数据修补的方式为：
[0031] i. 预设阈值ε，时间窗口遍历矩阵P，扫描到异常概率高于ε的数据时，判定该数据为异常数据点，将以该异常数据点为中心，K为边长的正方形区域所涉及的概率数据对应的D1中的轨迹数据清除；
[0032] ii. 以该异常数据点所在列前后nK列时间片所有节点的轨迹数据矩阵对D1进行矩阵修补得到新的矩阵D2，n为正整数，n≥2；
[0033] iii. 将矩阵D与D2相减得到新的距离差值矩阵Δ1；
[0034] iv. 对Δ1中的每个数据计算其轨迹数据异常概率进而更新异常概率矩阵为 P1；
[0035] v. 时间窗口继续前向扫描出P1中下一个异常概率高于ε的数据，判定该数据为异常数据点，将以该异常数据点为中心，K为边长的正方形所涉及的概率数据对应的D1中的轨迹数据清除；
[0036] vi. 重复ii至v，直至扫描更新结束，最终所得的矩阵即为轨迹数据修正后矩阵。
[0037] 作为一种优选的实施方式，所述ii中，以所述预测缺失值的方式进行矩阵修补。
[0038] 本发明利用了距离检测法的原理，强调轨迹本身的异常行为，在认为与其他轨迹不同且距离较远的轨迹就是异常轨迹的判断基础上，将比较范围缩小在了K邻内以加快检测的速度，同时基于一个异常概率准则增加判断依据的可行性。本发明能够根据K邻信息对已有的基于位置的轨迹数据进行主动预测，并构造移动轨迹数据异常概率矩阵，根据阈值要求找到异常数据区域进行矩阵数据修补，能够发现大规模轨迹数据中的异常信息。所述方法可以应用于包括智慧城市中普通道路、隧道与桥梁的交通监测中。
附图说明
[0039] 图1是轨迹数据异常检测整体流程图。
[0040] 图2是对异常概率矩阵进行时间窗口前向扫描的示意图。
[0041] 图3是轨迹数据异常检测具体流程图。
具体实施方式
[0042] 下面以车联网中车辆轨迹数据集为例，结合附图和具体实施方式，进一步阐述本发明。
[0043] 图1描述了该轨迹数据异常检测方法的整体工作流程，此外，图3描述了应用该异常检测方法对移动轨迹数据进行检测的具体流程。在本实施方式中，具体以车辆行驶轨迹的异常检测为例进行说明，其他的场景也可以参照本实施方式来实施，可以应用于包括智慧城市中普通道路、隧道与桥梁的交通监测中。根据所收集到的车辆行驶轨迹数据，检测其中存在的移动轨迹数据异常情况的具体步骤如下：
[0044] 步骤1：根据K邻信息对已有的基于位置的轨迹数据进行主动预测；
[0045] 步骤1‑1：确定K的大小，K邻信息即与当前时间片前后相邻包含在内的K列时间片，对于前/后相邻时间片不足 的当前时间片，以后/前数据补足。
[0046] 步骤1‑2：轮询轨迹数据矩阵D中的列（即时间片），同时主动清除单列时间片下的位置数据。
[0047] 步骤1‑3：利用矩阵分解的方法快速预测缺失值，随机初始化矩阵U和V，采用梯度下降算法更新U、V，使得 取得最小值。其中，X为K邻信息内所有节点的T
轨迹数据矩阵，矩阵 是对矩阵X的预测，V 为V的转置矩阵，J为X和 之间误差的Frobenius范数的平方。
[0048] 步骤1‑4：对D中的时间片列数据完成轮询、主动清除与预测后，将预测所得的时间片列数据按时间片排列即可得到D1。
[0049] 步骤2：将预测产生的新数据D1和数据集中原有数据D相减，构造差值矩阵，在此基础上构造移动轨迹数据异常的概率P；
[0050] 步骤2‑1：将矩阵D与D1相减得到一个距离差值矩阵Δ。
[0051] 步骤2‑2：对Δ中列的每个数据dij计算其异常概率，计算公式如式（1）：
[0052] （1）
[0053] 其中，为dj列所有数据的平均值；分子表示dij偏离均值 的程度；分母为归一化因子，从而确保符合概率定义，表示dj列所有数据偏离均值 的程度累计；pij就是dj列每个数据对应的异常概率，当pij超过预设阈值ε（比如，ε=10%）时，可判定当前轨迹数据异常。
[0054] 步骤2‑3：将列向量p（j 对应某时间片下各节点位置数据异常的概率）按时间片先后顺序排列，即可得到全局移动轨迹数据异常概率矩阵P。
[0055] 步骤3：确定在时间维度上对P进行时间窗口前向扫描的窗口大小T；
[0056] 步骤4：对每个窗口内的数据异常概率进行判别，寻找D1中对应的异常数据区域进行矩阵数据修补，最终更新完整个数据矩阵。
[0057] 步骤4‑1：以大小为T的时间窗口前向扫描出P中第一个移动轨迹数据异常概率高于ε的数据，将以该异常数据点为中心，K为边长的正方形区域所涉及的概率数据对应的D1中的数据全部清除。
[0058] 步骤4‑2：利用步骤2所述缺失值预测的方法，以异常数据点所在列前后10K列时间片的所有节点的轨迹数据矩阵对D1进行矩阵修补得到新的矩阵D2。
[0059] 步骤4‑3：将矩阵D与D2相减得到一个新的距离差值矩阵Δ1。
[0060] 步骤4‑4：对Δ1中的每个数据计算其轨迹数据异常概率进而更新异常概率矩阵为 P1。
[0061] 步骤4‑5：窗口T继续前向扫描出P1中下一个异常概率高于ε的数据，将以该异常数据点为中心，K为边长的正方形区域所涉及的概率数据对应的D1中的数据全部清除。
[0062] 步骤4‑6：重复步骤4‑2至步骤4‑5，直至扫描更新结束，最终所得的矩阵即为原始数据不断修补后的数据矩阵。
