基于混合网格分层聚类的集群通信终端轨迹实时异常检测方法与系统

摘要

本发明涉及通信领域，提出一种基于混合网格分层聚类的集群通信终端轨迹实时异常检测方法，包括以下步骤：步骤1、构建基于网格的轨迹，确定最优网格大小；步骤2、计算Hausdroff距离矩阵，利用Hausdroff距离公式计算基于网格的轨迹集中所有轨迹之间的距离，生成轨迹集的距离矩阵；步骤3、分层聚类，即在轨迹集的Hausdroff距离矩阵的基础上应用自下而上的凝聚分层聚类算法，实现大规模轨迹的正常与异常轨迹的分类；步骤4、异常检测方法评估反馈，利用上述方法，对已经有轨迹分类标识的轨迹集的进行异常轨迹检测，得到异常分类结果，进行对比后评估模型参数是否合理并作出反馈。本发明的方法可实现对异常事件的在线实时检测，提高集群通信系统的上层调度指挥效率。

说明书

技术领域

本发明涉及通信技术领域，具体而言涉及一种基于混合网格分层聚类的集群通信终端轨迹实时异常检测方法与系统。

背景技术

随着GPS、RFID以及无线传感器等移动对象定位技术的迅速发展，越来越多的移动轨迹数据被收集和保存在应用服务器。如何快速的从这些轨迹数据集中发现有效信息日益成为一个令人关注的研究课题。因此，一系列基于位置信息的服务(LBS)相继出现，例如：出租车打车服务、小孩和老年人的位置监护以及重要设备的位置管理等。通过电信移动运营商的无线电通讯网络(如GSM网、CDMA网)或外部定位方式(如GPS)获取移动终端用户的位置信息(地理坐标或大地坐标)，在地理信息系统(GIS)平台的支持下，为用户提供相应服务的一种增值业务。用户可以实时查看自己关心的家人或车辆的位置信息，为人们的生活带来了极大的便利。在很多特定的场景下，人们需要识别场景中的人或物体的移动行为是否符合规范。因此，移动轨迹的异常检测成为了一项十分重要的应用。

随着集群通信系统的规模的迅猛发展、业务的爆炸式增长，集群通信系统的终端数量急剧增长。目前绝不多数集群通信系统中的终端都配有GPS或者北斗定位装置，位置采集技术的日益普及促进了人们对时间-空间数据的大规模采集，从而为发现珍贵的关于用户移动位置的信心带来了新的机遇。如何在海量的轨迹数据中发现终端的行为异常轨迹是目前很热门的课题。目前的异常轨迹检测方法在小规模的轨迹数据上表现良好，但是在处理海量数据时非常耗时，系统的时间复杂度随着数据的规模变得很大，大大降低了集群通信系统的调度效率。

发明内容

为解决上述问题，本发明旨在提供一种基于混合网格分层聚类的集群通信终端轨迹实时异常检测方法与系统，基于集群通信系统中移动终端的轨迹数据，利用数据挖掘技术发现终端异常轨迹的时空特点，并以此为依据实现对大规模轨迹数据的异常检测，实现对异常事件的在线实时检测，提高集群通信系统的上层调度指挥效率。

本发明的上述目的通过独立权利要求的技术特征实现，从属权利要求以另选或有利的方式发展独立权利要求的技术特征。

为达成上述目的，本发明提出一种基于混合网格分层聚类的集群通信终端轨迹实时异常检测方法，包括以下步骤：

步骤1、构建基于网格的轨迹，确定最优网格大小；

步骤2、计算Hausdroff距离矩阵，即利用Hausdroff距离公式计算基于网格的轨迹集中所有轨迹之间的距离，生成轨迹集的距离矩阵M；

步骤3、分层聚类，即在轨迹集的Hausdroff距离矩阵的基础上应用自下而上的凝聚分层聚类算法，实现大规模轨迹的正常与异常轨迹的分类；

步骤4、异常检测方法评估反馈，利用上述步骤1～3的方法，对已经有轨迹分类标识的轨迹集的进行异常轨迹检测，得到异常分类结果，并与真实分类情况进行对比，评估步骤1，3中模型参数是否合理，并作出反馈。

根据本发明的改进，还提出一种基于混合网格分层聚类的集群通信终端轨迹实时异常轨迹检测系统，该系统包括：服务调度中心、集群通信网络和移动定位终端，其中

服务调度中心包括：

轨迹文件数据库服务器，用于存储所有移动定位终端上传的位置信息；

异常轨迹检测程序服务器，用于移动定位终端的异常轨迹检测，优化集群通信的系统调度；

可视化Web服务器，用于动态展示移动定位终端的历史轨迹，并将异常轨迹检测程序服务器计算得到的异常轨迹显示在地图上；

轨迹分析程序服务器包括：

网格轨迹构建模块，Hausdroff距离矩阵计算模块、网格轨迹凝聚分层聚类模块以及异常检测方法评估反馈模块。

由以上技术方案可知，与现有技术相比，本发明的显著优点在于：

1、将原始GPS轨迹数据利用网格分割结构转化为网格序列，简化了聚类算法的输入，大大降低了异常轨迹检测算法的时间复杂度；

2、本发明利用基于Haversine公式的Hausdroff距离矩阵，可以有效表征网格序列之间的相似程度；

3、本发明提出的基于混合网格分层聚类的集群通信终端轨迹实时异常轨迹检测方法和系统，在现有集群通信系统中添加了智能服务中心，利用基于移动终端轨迹数据分析技术为集群通信智能调度和应急防范提供有效地决策。

应当理解，前述构思以及在下面更加详细地描述的额外构思的所有组合只要在这样的构思不相互矛盾的情况下都可以被视为本公开的发明主题的一部分。另外，所要求保护的主题的所有组合都被视为本公开的发明主题的一部分。

结合附图从下面的描述中可以更加全面地理解本发明教导的前述和其他方面、实施例和特征。本发明的其他附加方面例如示例性实施方式的特征和/或有益效果将在下面的描述中显见，或通过根据本发明教导的具体实施方式的实践中得知。

附图说明

附图不意在按比例绘制。在附图中，在各个图中示出的每个相同或近似相同的组成部分可以用相同的标号表示。为了清晰起见，在每个图中，并非每个组成部分均被标记。现在，将通过例子并参考附图来描述本发明的各个方面的实施例，其中：

图1是根据本发明某些实施例的基于混合网格分层聚类的集群通信终端轨迹实时异常轨迹检测方法的流程示意图。

图2是根据本发明某些实施例的GPS轨迹构建网格序列示例示意图。

图3是根据本发明某些实施例的网格尺寸与热点区域个数的关系曲线示意图。

图4是根据本发明某些实施例的网格尺寸与轨迹数据覆盖率的关系曲线示意图。

图5是根据本发明某些实施例的分层聚类树状图。

图6是根据本发明某些实施例的异常轨迹可视化结果示意图。

图7是移动定位终端与服务调度中心之间经过集群通信网络进行通信的示意图。

具体实施方式

为了更了解本发明的技术内容，特举具体实施例并配合所附图式说明如下。

在本公开中参照附图来描述本发明的各方面，附图中示出了许多说明的实施例。本公开的实施例不必定意在包括本发明的所有方面。应当理解，上面介绍的多种构思和实施例，以及下面更加详细地描述的那些构思和实施方式可以以很多方式中任意一种来实施，这是因为本发明所公开的构思和实施例并不限于任何实施方式。另外，本发明公开的一些方面可以单独使用，或者与本发明公开的其他方面的任何适当组合来使用。

结合图1所示，根据本发明的实施例，一种基于混合网格分层聚类的集群通信终端轨迹实时异常检测方法，包括以下步骤：步骤1、构建基于网格的轨迹，确定最优网格大小；步骤2、计算Hausdroff距离矩阵，即利用Hausdroff距离公式计算基于网格的轨迹集中所有轨迹之间的距离，生成轨迹集的距离矩阵M；步骤3、分层聚类，即在轨迹集的Hausdroff距离矩阵的基础上应用自下而上的凝聚分层聚类算法，实现大规模轨迹的正常与异常轨迹的分类；步骤4、异常检测方法评估反馈，利用上述步骤1～3的方法，对已经有轨迹分类标识的轨迹集的进行异常轨迹检测，得到异常分类结果，并与真实分类情况进行对比，评估步骤1、3中的参数是否合理，并作出反馈。

上述方案的检测方法，基于集群通信系统中移动终端的轨迹数据，利用数据挖掘技术发现终端异常轨迹的时空特点，并以此为依据实现对大规模轨迹数据的异常检测，实现对异常事件的在线实时检测，提高集群通信系统的上层调度指挥效率。

我们在以下内容中对前述步骤1-步骤4的实现做具体的说明。

步骤1、构建基于网格的轨迹，确定最优网格大小

传统分层聚类算法需要轨迹之间两两比较距离，假设轨迹数据规模为N，那么整个聚类算法的时间复杂度O(N²)。

为了克服传统算法的缺点，同时避免路网结构、地图匹配等因素的限制，本例中提出一种基于网格的聚类算法。该算法将整个目标区域划分为若干个小网格区域，并将终端移动轨迹映射为网格序列。

给定一条GPS轨迹数据T＝<(p₁,t₁),...,(p_i,t_i),...(p_n,t_n)>、一个网格分割结构和网格容量阈值MinPts，一个基于网格的轨迹定义为G＝<(g₁,t′₁),...,(g_j,t′_j),...(g_m,t′_m)>，其中g_j＝{(p_a,t_a),...,(p_e,t_e)}，t'_j＝t_a，网格容量满足g_j≥MinPts。

对于目标区域中一个轨迹点p(lat,lng)，该轨迹点对应的网格编号(t,s)由如下计算可得：

其中，lat_max和lng_max分别是目标区域经纬度坐标轴上的最大值；lat_min和lng_min分别是目标区域经纬度坐标轴上的最小值；n_lat和n_lng分别是经纬度坐标轴上的网格数。

不同的网格分割结构会对接下来的异常检测算法性能产生重要的影响。小的网格更能还原原始GPS轨迹的移动特性，但同时会使异常检测算法的时间复杂度大大增加；大的网格可以降低异常检测算法的时间复杂度，但由于网格粒度过大会丧失原始的移动特性。

因此，本发明在保持原始轨迹移动特性和算法时间复杂度之间做了权衡，获得最优的网格分割结构。

步骤2、计算Hausdroff距离矩阵

利用Hausdroff距离公式计算基于网格的轨迹集中所有轨迹之间的距离，生成轨迹集的距离矩阵M。

任意两条基于网格的轨迹之间的无向Hausdroff距离如下：

$>d_H(P,Q)=max\left\{\underset{p\in P}{\max }\right\{\underset{q\in Q}{\min }\left\{d(p,q)\right\}\},\underset{q\in Q}{\max }\{\underset{p\in P}{\min }\left\{d(p,q)\right\}\left\}\right\}$>

其中d(p,q)是haversine公式，如下：

d＝2Rarcsin(h)

其中：φ_p、φ_q和λ_p、λ_q分别是GPS轨迹点的经纬度，R＝6371km是地球的近似半径。

步骤3、网格轨迹凝聚分层聚类

在轨迹集的Hausdroff距离矩阵的基础上应用自下而上的凝聚分层聚类算法，实现大规模轨迹的正常与异常轨迹的分类。

具体地，分层聚类的过程包括：初始，将每条轨迹分配在不同的簇中，然后根据最大距离连接度量准则，逐步将相似轨迹合并到同一个簇中。簇合并过程反复进行，直到所有轨迹最终合并形成一个大簇。

使用聚类树状图的树形结构实现对层次聚类过程的可视化，并且实现最优轨迹分类距离阈值的确定。

本发明中，异常轨迹被定义为与绝大多数轨迹远离的小部分轨迹。因此，我们将远离绝大多数轨迹簇的轨迹簇中的轨迹判定为异常轨迹，不同的轨迹集需要根据聚类树状图确定合适的分类距离阈值。

步骤4、异常检测方法评估反馈

利用上述步骤1～3的方法，对已经有轨迹分类标识的轨迹集的进行异常轨迹检测，得到算法计算出来的异常分类结果，与真实分类情况进行对比。在本发明中，运用机器学习中常用的评价标准混淆矩阵、精确度、召回率、F分数，评估步骤1、3中模型参数是否合理，并作出正确的反馈，优化异常轨迹算法的正确性和鲁棒性。

下面结合附图1-附图6所示，更加具体地描述前述各个步骤的示例性实现。

步骤1：

将整个目标区域划分为若干个小网格区域，并将终端GPS轨迹映射为网格序列，如图2所示。

对于目标区域中一个轨迹点p(lat,lng)，该轨迹点对应的网格编号(t,s)由如下计算可得：

其中，lat_max和lng_max分别是目标区域经纬度坐标轴上的最大值；lat_min和lng_min分别是目标区域经纬度坐标轴上的最小值；n_lat和n_lng分别是经纬度坐标轴上的网格数。

定义网格中包含GPS轨迹点的个数为网格容量，保留满足网格容量大于MinPts的网格称为热点区域，由热点区域组成网格序列。定义网格序列中包含的GPS轨迹点数占原始GPS轨迹点总数的比率为轨迹数据覆盖率。不同的网格尺寸下的网格分割结构会导致热点区域个数和轨迹数据覆盖率的变化。根据计算网格尺寸与热点区域、轨迹数据覆盖率的关系曲线，最佳网格尺寸可以定为0.6×10^-3度。在网格尺寸确定为0.6×10^-3度的条件下，将G原始GPS轨迹转换为网格序列，如图3、图4所示。

步骤2：

在步骤1计算得到的网格序列集上，运用Hausdroff距离公式计算基于网格的轨迹集中所有轨迹之间的距离，生成轨迹集的距离矩阵M。任意两条基于网格的轨迹之间的无向Hausdroff距离如下：

$>d_H(P,Q)=max\left\{\underset{p\in P}{\max }\right\{\underset{q\in Q}{\min }\left\{d(p,q)\right\}\},\underset{q\in Q}{\max }\{\underset{p\in P}{\min }\left\{d(p,q)\right\}\left\}\right\}$>

其中d(p,q)是haversine公式，如下：

d＝2Rarcsin(h)

其中：φ_p、φ_q和λ_p、λ_q分别是GPS轨迹点的经纬度，R＝6371km是地球的近似半径。

表1网格序列的Hausdroff距离矩阵

12345678910101.58113.10661.13441.3630.68241.22621.14110.85731.444421.581103.44971.2361.41061.28011.02980.99991.14031.406933.10663.449703.22053.30872.74553.25743.21652.83793.396941.13441.2363.220501.46440.19690.49310.29510.42121.462751.3631.41063.30871.464401.79191.67980.44291.72240.197660.68241.28012.74550.19691.791900.76640.76640.58441.783871.22621.02983.25740.49311.67980.7664000.47511.658581.14110.99993.21650.29510.44290.7664000.47510.876490.85731.14032.83790.42121.72240.58440.47510.475101.715101.44441.40693.39691.46270.19761.78381.67350.87641.7150

步骤3：

凝聚分层聚类，轨迹类阈值设定

在轨迹集的Hausdroff距离矩阵的基础上应用自下而上的凝聚分层聚类算法，实现大规模轨迹的正常与异常轨迹的分类。初始，算法将每条轨迹分配在不同的簇中，然后根据最大距离连接度量准则，逐步将相似轨迹合并到同一个簇中。簇合并过程反复进行，直到所有轨迹最终合并形成一个大簇。使用聚类树状图的树形结构实现对层次聚类过程的可视化，并且实现最优轨迹分类距离阈值的确定，如图5所示为分层聚类树状图的示例。本发明中，异常轨迹被定义为与绝不多数轨迹远离的小部分轨迹。因此，我们将远离绝不多数轨迹簇的轨迹簇中轨迹判定为异常轨迹，不同的轨迹集需要根据聚类树状图确定合适的分类距离阈值。

根据示例树状图中的聚类结果，轨迹3位于远离其他轨迹的簇中，因此轨迹3被标记为异常轨迹，如图6所示。

步骤4：

异常检测方法评估反馈

利用上述步骤1～3的方法，对已经有轨迹分类标识的轨迹集的进行异常轨迹检测，得到算法计算出来的异常分类结果，与真实分类情况进行对比。在本发明中，运用机器学习中常用的评价标准混淆矩阵、精确度、召回率、F分数，评估步骤1、3中模型参数是否合理，并作出正确的反馈，优化异常轨迹算法的正确性和鲁棒性。

表2异常轨迹检测算法性能测试

轨迹簇的距离/km真正例真负例假正例假负例精确值召回率F分数140105250.890.620.7324496210.880.680.7735369120.850.820.8345641190.840.860.8556021350.820.920.87

结合图1、图7所示，根据本公开，还提出一种基于混合网格分层聚类的集群通信终端轨迹实时异常轨迹检测系统，该系统包括：服务调度中心、集群通信网络和移动定位终端。

移动定位终端与服务调度中心之间经过集群通信网络进行通信。

移动定位终端包括数据终端、车载终端、单模终端。

服务调度中心包括：

轨迹文件数据库服务器，用于存储所有移动定位终端上传的位置信息；

异常轨迹检测程序服务器，用于移动定位终端的异常轨迹检测，优化集群通信的系统调度；

可视化Web服务器，用于动态展示终端的历史轨迹，并将异常轨迹检测程序服务器计算得到的终端异常轨迹显示在地图上。

轨迹分析程序服务器包括：

网格轨迹构建模块，用于将整个目标区域划分为若干个小网格区域，并将终端移动轨迹映射为网格序列。给定一条GPS轨迹数据T＝<(p₁,t₁),...,(p_i,t_i),...(p_n,t_n)>和一个网格分割结构，一个基于网格的轨迹定义为G＝<(g₁,t′₁),...,(g_j,t'_j),...(g_m,t'_m)>，其中g_j＝{(p_a,t_a),...,(p_e,t_e)}，t'_j＝t_a。

对于目标区域中一个轨迹点p(lat,lng)，该轨迹点对应的网格编号(t,s)由如下计算可得：

其中，lat_max和lng_max分别是目标区域经纬度坐标轴上的最大值；lat_min和lng_min分别是目标区域经纬度坐标轴上的最小值；n_lat和n_lng分别是经纬度坐标轴上的网格数。不同的网格分割结构会对接下来的异常检测算法性能产生重要的影响。小的网格更能还原原始GPS轨迹的移动特性，但同时会使异常检测算法的时间复杂度大大增加；大的网格可以降低异常检测算法的时间复杂度，但由于网格粒度过大会丧失原始的移动特性。因此，本发明在保持原始轨迹移动特性和算法时间复杂度之间做了权衡，获得最优的网格分割结构。

Hausdroff距离矩阵计算模块，利用Hausdroff距离公式计算基于网格的轨迹集中所有轨迹之间的距离，生成轨迹集的距离矩阵M。任意两条基于网格的轨迹之间的无向Hausdroff距离如下：

$>d_H(P,Q)=max\left\{\underset{p\in P}{\max }\right\{\underset{q\in Q}{\min }\left\{d(p,q)\right\}\},\underset{q\in Q}{\max }\{\underset{p\in P}{\min }\left\{d(p,q)\right\}\left\}\right\}$>

其中d(p,q)是haversine公式，如下：

d＝2Rarcsin(h)

其中：φ_p、φ_q和λ_p、λ_q分别是GPS轨迹点的经纬度，R＝6371km是地球的近似半径。

网格轨迹凝聚分层聚类模块，初始，算法将每条轨迹分配在不同的簇中，然后根据最大距离连接度量准则，逐步将相似轨迹合并到同一个簇中。簇合并过程反复进行，直到所有轨迹最终合并形成一个大簇。使用聚类树状图的树形结构实现对层次聚类过程的可视化，并且实现最优轨迹分类距离阈值的确定。本发明中，异常轨迹被定义为与绝不多数轨迹远离的小部分轨迹。因此，我们将远离绝不多数轨迹簇的轨迹簇中轨迹判定为异常轨迹，不同的轨迹集需要根据聚类树状图确定合适的分类距离阈值。

异常检测评估反馈模块,利用上述三个模块，对已经有轨迹分类标识的轨迹集的进行异常轨迹检测，得到算法计算出来的异常分类结果，与真实分类情况进行对比。在本发明中，运用机器学习中常用的评价标准混淆矩阵、精确度、召回率、F分数，评估评估网格轨迹构建模块、网格轨迹凝聚分层聚类模块中模型参数是否合理，并作出正确的反馈，优化异常轨迹算法的正确性和鲁棒性。

虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明。本发明所属技术领域中具有通常知识者，在不脱离本发明的精神和范围内，当可作各种的更动与润饰。因此，本发明的保护范围当视权利要求书所界定者为准。