一种目标航迹数据聚类挖掘分析方法

陈 勇

(中国电子科技集团公司第五十四研究所，河北石家庄050081)

0 引言

目标航迹数据聚类挖掘分析能够从纷杂的航迹数据中发现目标的潜在运动轨迹，可以用于态势数据挖掘、目标行为意图分析和空中交通流量分析等领域［1-5］。现有的航迹数据挖掘算法大多数是针对整个航迹设计的，但在实际数据中，整条航迹具有相似性的情况不多，大多数情况是不同航迹之间在部分航迹线段上具有相似性，以整条航迹为研究对象的聚类算法往往不能发现局部航迹线段的聚集特性［6，7］。本文给出一种新的目标航迹数据聚类分析算法，以航迹线段为对象设计聚类挖掘算法，并按照垂直距离、平行距离和角度距离计算航迹线段之间的距离，这种方法既能发现局部的航迹线段聚集特征，也能发现全局的航迹聚集特征。

1 问题描述

借助传感器侦察手段，能够获取受关注区域内移动目标运动轨迹的海量信息，这些信息中隐含着目标运动的特征规律，特征规律表现为相同或相似目标运动轨迹的反复出现，这些轨迹规律有助于推测目标的行为意图，但这些轨迹规律往往被淹没在大量的噪声航迹点数据中，不易被觉察发现，需要设计相关聚类分析算法帮助人们进行分析。

一组待聚类分析的航迹可以表示为T={t1，t2，…，tn}。Ti(1≤i≤n)表示一条航迹，ti=p1p2…pm，pi(1≤i≤m)表示一个航迹点。聚类结果表示为R={C1，C2，…CN}，R 中包含了若干个簇，一个簇表示为 Ci(1≤i≤N)，Ci={L1，L2，…Lo}，Ci中包含了若干个航迹线段，一个航迹线段表示为Li(1≤i≤o)，Li⊆ti。

2 算法分析

运动目标航迹聚类分析方法用于对一批累积目标航迹数据进行聚类分析，将相似航迹线段聚在一起，从杂乱无章的众多航迹线中发现目标运动潜在的运动模式。

本文提出了一种目标航迹聚类分析算法，其输入包括:

输入 1:航迹集合 T={t1，t2，t3，……tnum}，其中，ti(i=1，2，…，num)代表目标航迹;

输入2:指定ε(辐射距离)和support(辐射距离范围内的线段数)2个参数。

其输出为航迹(线段)聚类结果，算法具体执行步骤描述如下:

第1步:对T中整条航迹按照航迹点进行分割处理，航迹被分割成若干航迹线段，所有航迹线段组成集合D;

第2步:利用算法Line-Segment-Clustering算法对航迹段进行分析，得到航迹段聚类结果。其中，Line-Segment-Clustering算法描述为:

①设置变量clusterID初始值为0;

②初始时，将集合D中每条航迹线段都标记为“未分簇”，即未做归簇处理;

③对于集合D中的每一条航迹线段Li(Li∈D)逐个进行处理，首先判断航迹线段Li是否已被归到某个簇，具有了簇标识，若航迹线段已有了簇标识，则不做处理，若没有簇标识，则进行如下处理过程;

④计算航迹线段Li邻域范围内与其距离小于阈值ε的航迹线段的集合Nε(Li)所含航迹线段的数量，|Nε(Li)|={Lj∈D|dist(Li，Lj)≤ε};

⑤如果Li邻域范围的航迹线段数量大于或等于阈值support，则将集合Nε(Li)中的每一个线段都分配一个簇标识clusterID;否则，直接转到第⑨步;

⑥将Nε(Li)中的成员线段放入队列Q中;

⑦利用扩展处理函数(见表2的说明文字)对Q进行处理;

⑧让变量clusterID增加1;

⑨如果Li邻域范围的航迹线段数量小于阈值support，则将Li标记为噪声;

⑩经过上述步骤之后，集合D中的每一个元素都被赋予了簇标识;

[11] D中的航迹线段按照其簇标识分配到相应的簇中;

[12]对于每一个簇，通过线段与原始航迹之间的映射关系，找出cluster中包含的原始航迹数量，如果航迹数量大于某一个预定值，则保留这个簇，否则，删除这个簇。

算法的伪代码如表1所示。

表1 算法描述

扩展处理函数的算法描述为:

① 接收参数Q，clusterID，ε 和support，以循环方式对Q中的每一个成员航迹线段进行处理;

②计算Q中成员线段M的领域线段集合Nε(M);

③如果Nε(M)所含线段数量大于或等于support，则把集合Nε(M)中的每一个未分簇或噪声线段都标识为clusterID;否则，什么都不做，进入下一次循环，处理Q中的下一个成员线段。

扩展处理算法的伪代码如表2所示。

表2 扩展处理函数描述

3 实验计算结果分析

采用仿真数据对航迹聚类分析算法进行了测试，仿真数据分为6组，分别包含了2 000、4 000、6 000、8 000、15 000和25 000个航迹点，每个航迹点关联了目标出现时间、位置经度和位置纬度信息。

在一台配置为Pentium CPU 3.00 GHz、2 GB内存、250 GB硬盘的PC上开展了航迹聚类分析实验。聚类分析的执行时间如图1所示，聚类算法的执行时间随着航迹中所含航迹点的数量增大而增加。

图1 航迹聚类算法执行时间

航迹聚类结果如图2所示，图中浅灰色细线段是通过传感器观测到的飞机运动形成的航迹线段，黑色粗线段是聚类生成的航迹簇的标识性线段。实验结果表明算法能排除零星散布航迹线段的干扰，准确地将邻近密集分布的航迹线段归为一簇。

图2 航迹聚类结果

4 结束语

本文以运动目标航迹聚类为研究目标，针对航迹中的航迹线段设计了聚类算法，依据垂直距离、平行距离和角度距离量度线段之间的距离，通过对实际航迹数据的聚类分析试验，实验结果表明，该算法能够排除零散航迹的影响，从目标航迹数据中发现目标的运动轨迹特征。该算法可以应用到目标行为意图分析、目标行为异常检测等领域。

［1］ 王涛波，黄宝军.基于4D航迹的模糊聚类分析［J］.交通信息与安全，2013，31(180):38-42.

［2］ 王洁宁，孙 禾，赵元棣.基于时间—空间的进场航迹聚类分析［J］.科学技术与工程，2013，13(33):10 078-10 081.

［3］ 王 超，徐肖豪，王 飞.基于航迹聚类的终端区进场程序管制适用性分析［J］.南京航空航天大学学报，2013，45(1):130-139.

［4］ 王 超，王明明，王 飞.基于改进的模糊C-Means航迹聚类方法研究［J］.中国民航大学学报，2013，31(3):14-18.

［5］ 杨咏建，祝胜强.态势标绘系统设计分析［J］.无线电通信技术，2012，38(1):52-55.

［6］ 王增福，潘 泉，郎 林，等.基于减法聚类的动态航迹聚类算法［J］.系统仿真学报，2009，21(16):5 240-5 246.

［7］ ACHTERT E，BÄOHM C，KRIEGEL H-P，et al.Deriving Quantitative Models for Correlation Clusters［C］∥ 12th ACM SIGKDD Int'l Conf.on Knowledge Discovery and Data Mining，Philadelphia，Pennsylvania，2006:4-13.