一种基于数据挖掘的目标行为规律分析算法

高 轶，王 鹏

(1.海军装备部信息系统局，北京 100841；2.中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

0 引言

对于目标活动行为，传统的处理方法多注重于实时态势的展示[1]，用于目标行为信息的实时反映，保障信息数据处理的时效性，对于积累的大量目标活动历史信息数据并没有过多关注，而目标的行为规律则只有通过对长时间的历史数据进行分析才有可能获得。面向积累的海量目标活动数据，单凭人工方式来发现这些规律是不现实的，因此通过数据挖掘方法对海量数据进行挖掘，对于掌握目标行为规律具有非常重要的意义。目前，国内外已经展开了相关研究，如轨迹聚类[2-4]、活动规律分析[5-7]和轨迹相似性计算[8-9]。其中，文献[5]利用地理网格技术划分港口水域，并对每个地理单元格上的传播行为进行统计分析来揭示整个海域船舶行为规律，但并未考虑某船舶行为在时间维度上的连续性；文献[6]采用混合高斯模型和主成分分析模型对目标轨迹行为进行了分析，并对异常行为进行识别；文献[7]采用序列模式挖掘方法对潜在的多个目标间的出现规律进行了分析，但并非针对某个目标的活动规律进行挖掘。针对目标的行为规律发掘问题，本文提出了一种基于数据挖掘的目标行为规律分析算法，对目标轨迹进行预处理以提高数据质量，利用地理网格技术对感兴趣区域进行栅格化处理并利用栅格编号表示目标位置，利用目标多次运动轨迹按照时间排序构建观测序列，利用序列关联分析算法对观测序列进行挖掘和分析，用以提取一段时间内的目标行为规律，实现目标活动信息的掌握，达到有效支持辅助决策的目的。

1 数据挖掘概念

数据挖掘是指对大量的、不完全的、有噪声的、模糊的、随机的数据进行分析以提取隐含的、可信的、新颖的和有效的信息处理过程[10]。其意义在于能够从大量的数据中提取事先未知的、不可预料的知识和信息，这些信息对于决策人员可能是非常有用的。数据挖掘任务主要包括分类预测任务和描述任务两大类[11]，其中预测任务是指根据其他属性的值来预测特定属性的值，而描述任务的目标则是实现对数据中潜在联系的模式(相关、趋势、聚类、轨迹和异常)进行概括。本文所涉及的问题就属于描述任务的范畴，主要是通过对积累的历史数据进行分析，实现目标行为规律的挖掘，采用的数据挖掘方法主要涉及关联分析算法。

1.1 关联分析的概念

关联分析是数据挖掘的经典方法，用以描述一场交易中物品之间同时出现的规律的知识模式，并用关联规则或频繁项集的形式进行表示，用以揭示事物之间的联系，其基本概念和定义如下[12]：

设I={i1，i2，…，im}是项的集合，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标志的事务组成，事务ti={Ii1，Ii2，…，Iik}对应I上的一个子集，即ti⊆I。关联分析就是从大量的数据中发现项集之间的关联和相关关系，实现对项集中某些项同时出现规律或模式的发掘，获得形如X⟹Y的蕴涵式(关联规则)，其中，X、Y表示项集，且满足X⊆ti，Y⊆ti，X∩Y=∅。

在关联规则中，用支持度和置信度对关联规则的强度进行描述。在关联规则X⟹Y中，支持度是指事务数据库中包含X∪Y的事务占事务数据库D的百分比，用以描述当前项集的频繁程度，形式如下：

(1)

式中，n表示事务数据库D所包含事务的个数。置信度是指事务数据库中包含X∪Y的事务数与包含X的事务数之比，用于对当前规则的可靠性进行度量。置信度越高，则表明Y在包含X的事务中出现的可能性就越大，形式如下：

(2)

式中，σ(X)=|{ti|X⊆ti，ti∈T}|表示项集X的支持度计数，即当前数据库中包含特定项集的事务个数。

1.2 关联规则挖掘典型流程

目前，大多数关联规则挖掘算法采用的策略是将关联规则挖掘的任务分为以下2个步骤：

① 频繁项集的产生，其目标是发现满足设定的最小支持度阈值的所有项集，称之为频繁项集，常用的频繁项集挖掘算法包括Apriori[13]，FP-Growth[14]等算法；

② 规则的产生，其目标是从步骤①中发现的频繁项集中提取所有高置信度的规则，称之为强规则。

1.3 序列模式挖掘

轨迹数据存在固有的序列特征，而以上所讨论的关联规则都只强调同时发生，忽略了数据中的时间信息。在不同时间点上收集到的目标位置数据反映了目标随时间的变化状态，构成了轨迹数据，也称之为时间序列。若需要分析轨迹数据中的序列特征，就需要利用序列模式挖掘。通过序列模式挖掘可以发现时间序列数据之间的信息，获取蕴含在轨迹数据中的目标行为规律。

序列模式的发现就是在给定的序列数据集和设定的最小支持度阈值条件下，找出满足条件的所有序列，其步骤主要包括排序、频繁项集产生、转换和序列产生等阶段，常用的算法主要包括2类：一类是基于候选产生测试的Apriori算法以及衍生的如AprioriAll[15]，GSP[16]等相关算法；另一类是基于分而治之的数据库投影模式的PrefixSpan算法[17]以及相关类似算法。

2 目标行为规律分析算法

2.1 数据预处理

数据预处理的主要目的是提高数据集的质量和降低数据的复杂度。为提高数据集质量，本文采用去重、中值滤波、平滑滤波等方法对数据中存在的重复点、异常点进行剔除。为降低数据的复杂度并方便后续数据分析工作，本文采用地理网格技术对感兴趣区域进行栅格化处理，并利用栅格编号对目标位置进行表示。

2.1.1 异常点剔除

异常点也称离群点，是指属性值明显偏离期望的属性值。本文异常点是指由于受到被动侦测特点或其他环境因素影响所引起的明显偏离目标正常运动规律的轨迹点，可采用中值滤波、均值滤波[18]、卡尔曼滤波[19]和粒子滤波[20]等方法进行异常点过滤，每种算法都具有其适用性[21]。

本文采用中值滤波方法进行异常点去除的效果如图1所示。其中，图1(a)为原始目标轨迹，图1(b)为预处理后的目标轨迹。从图中可以发现，本文待处理的轨迹数据存在大量的异常点，经过预处理，可以有效剔除目标轨迹中的异常点，使得目标运动轨迹更加平滑，有效地提高了轨迹数据的质量。

图1 异常轨迹点剔除结果

2.1.2 轨迹拟合

未拟合的目标轨迹数据以及经过多项式拟合后的轨迹数据如图2所示。从图2中可以看出，未经拟合处理的轨迹数据存在明显的不连续处。而经过多项式拟合，可以有效补充轨迹点之间的缺失部分。此外，不同手段或同一手段不同时间获取的目标轨迹数据采样基准可能不一致，采用拟合方法还可以通过控制因变量实现采样基准的一致性。

受被动侦测以及其他环境因素影响，目标轨迹可能存在不连续的情况，如图2中原始轨迹点所示。此外，同一目标轨迹数据可能由多种手段获取，并不能保证其采样基准一致。为解决以上2个问题，本文对剔除异常点后的轨迹进行拟合，常用的拟合方法包括多项式拟合、三次样条插值等方法。

图2 轨迹拟合结果

2.1.3 目标位置栅格化

目标轨迹是目标位置按照时间排序的结果，其位置信息通常以经纬度的形式表示，因此，目标轨迹是时间—经度—纬度的三维表示，复杂度较高，并且不利于后续数据挖掘分析。为降低数据复杂度，并进一步消除测向定位引起的位置误差，本文对感兴趣区域运用地理网格技术进行栅格化处理，利用网格编号替代经纬度实现目标位置的唯一表示，将目标轨迹由时间—经度—纬度的三维表示简化为时间—网格编号的二维表示。本文对感兴趣区域进行栅格化处理的示意图如图3所示，每个网格的大小为0.1°×0.1°，网格的大小可以根据位置精度及其他需求进行综合考虑。

图3 目标位置栅格化示意

2.2 行为规律挖掘

对经过预处理的轨迹数据进行序列模式挖掘以得到该目标的行为规律，详细步骤如下：

① 构建目标行为序列数据：将经过预处理的一个目标的多次观测按照观测时间排序构造形成目标行为序列数据S={s1，s2，…，sm}，其中，si代表该目标的一次观测轨迹，m表示该目标观测轨迹的数量；

② 设定参数：设置频繁序列支持度为T，设置频繁序列的长度N；

③ 单元素频繁序列挖掘：对目标行为序列数据中的轨迹点位置编号进行去重得到序列中包含的元素，通过计算得到满足支持度T的单元素频繁序列C1；

④ 对得到的单元素频繁序列C1进行遍历，得到所有可能的两元素组合，计算判断满足频繁序列支持度T的两元素组合，得到两元素频繁序列C2；

⑤ 根据单元素频繁序列C1、两元素频繁序列C2，通过添加新的元素构建新的三元素备选序列，计算判断满足多元素频繁序列支持度T的三元素组合，得到三元素频繁序列C3；

⑥ 依此类推，重复步骤⑤，得到满足长度为N的频繁序列；若参数N为空，则得到所有长度的频繁序列，直至频繁序列集合不再增加为止；

⑦ 输出集合C1、C2，...，CN，至此得到满足参数T，N的所有频繁序列。

3 仿真实验

为验证所提算法的有效性，进行了计算机仿真实验。仿真实验数据共包含5组同一目标的真实轨迹观测数据，如图4所示。可以发现，虽然5次轨迹数据长度、运动方向等并不完全相同，但存在共同的运动趋势，并经过相同的位置，即该目标的行为存在一定的规律。

图4 目标轨迹数据

按照2.1节中方法进行预处理后，5条轨迹可以表示为：

s1={133，138，142，143，147，152，157，162，166，167，171，176，181}；

s2={19，24，29，34，39，49，53，54，59，64，73，78，83，88，93，98，103，108，113，118，123，128，133，137，138，142，147，152，157，162，166，167，171，176，181，186}；

s3={4，9，14，24，29，34，44，49，54，59，73，78，83，88，93，98，103，108，113，118，123，128，133，143，148，153，158，163，167，168，172，176，177，181，186}；

s4={34，44，49，54，59，64，69，74，78，79，83，88，103，108，113，118，123，128，133，138，143，148，153，158，162，167，172，176，181}；

s5={9，24，29，34，39，44，49，54，59，64，69，74，78，79，83，88，93，98，103，108，113，118，123，128，133，138，143，148，153，158，163，167，168，172，176，177，181}。

按照2.2节中目标行为规律挖掘方法对上述轨迹数据进行分析，设定频繁序列支持度T=4时，得到的频繁序列为{34，49，54，59，78，88，103，108，113，123，128，133，167，176，181}；而当设定多元素频繁序列支持度阈值为T=5时，得到的频繁序列为{133，167，176，181}。

上述挖掘得到的频繁序列的含义是，对当前积累的该目标的历史活动轨迹进行目标行为规律分析可得，有80%的概率按照支持度为4时的轨迹运动，而有100%的概率按照支持度为5时的轨迹运动。通过观察图4或者上文陈列的5条目标轨迹编号可以发现，支持度为4时的频繁序列出现在轨迹2、轨迹3、轨迹4和轨迹5中；而支持度为5的频繁序列出现在所有的轨迹中。这是因为轨迹1(图4箭头所指轨迹)并无其他目标轨迹数据的前半部分，与频繁序列挖掘结果相一致，说明了上述挖掘结果的正确性与有效性。

此外，通过对比挖掘的序列模式结果与预处理后的轨迹数据网格编号可以发现，挖掘得到的频繁序列在时间先后顺序上与原始轨迹相一致。这就说明，本文算法可以实现目标行为规律的发掘。

另一方面，为验证算法的有效性，同样采用上述轨迹数据，在配置为i7处理器、8 G内存的计算机上对不同参数下算法的运行时间进行了统计，结果如下：

当设定频繁序列支持度T=5、长度N缺省时，共挖掘得到该数据集的单元素频繁序列14项，多元素频繁序列4项，平均运行时间约为0.16 s(10次平均值)；

当设定频繁序列支持度T=4、长度N缺省时，共挖掘得到该数据集的单元素频繁序列19项，多元素频繁序列 86 924项，平均运行时间约为35.21 s(10次平均值)；

当设定频繁序列支持度T=3、长度N缺省时，共挖掘得到该数据集的单元素频繁序列30项，多元素频繁序列6 723 383项，平均运行时间约为4 800 s(10次平均值)。

通过以上结果可以看出，随着算法参数设置的不同，其运行时间发生急剧变化，说明频繁序列支持度需要根据当前数据情况进行设定，当目标的轨迹数据较为相似时，频繁序列支持度的阈值不宜过低，否则可能会带来维度灾难。

4 结束语

针对目标行为规律分析问题提出了一种基于序列模式挖掘的分析方法，并利用真实轨迹数据进行了异常点去除、轨迹拟合、行为规律挖掘等仿真实验，实现了目标活动规律的挖掘，对于目标异常行为识别、目标属性辅助判证等应用具有重要意义。

此外，在仿真实验中发现，数据的预处理效果直接影响后续分析算法的性能，需要设计能够适应更加复杂场景的预处理算法是后续研究的重点方向。