基于频繁项集的海上目标编组挖掘

2023-11-20 10:59袁昱纬
火力与指挥控制 2023年10期
关键词:分片编组项集

卫 强,袁昱纬,邓 勇

(1.解放军91977 部队,北京 102200;2.中国科学院自动化研究所,北京 100190)

0 引言

随着各个国家对海洋安全的需求日益增加,基于多种数据来源的、综合的海上目标监视技术研究已成为海洋领域研究的热点之一[1-2]。海上目标编组是在一定海区实行同一任务而组成的群体。通过分析海量目标数据,找出可能的编组目标,并对其进行任务能力评估,形成海上目标编组模型,对海上目标特性刻画有着重要意义[3-4]。

由于海上目标信息数据具有时空连续性,粗颗粒度的时空抽取不能满足时空轨迹的相似性挖掘;而采用精细颗粒度对数据进行时空对准并采用传统的轨迹相似度算法对轨迹进行聚类,计算成本将变得无法承受,对编组模型的确定复杂而耗时[5-6]。因此,如何对数据进行建模、采用何种挖掘算法至关重要[7-9]。在轨迹相似理论及轨迹聚类理论的基础上,本文探讨了目标编组挖掘中的应用模式,提出并设计研究基于频繁项集的目标编组高速发现算法,实现可应用于海量数据的目标轨迹编组模型挖掘。

1 编组模型挖掘方法

1.1 算法思路

首先选定目标区域和时段,并对其中的全部目标数据按照空间和时间进行划分和切片,形成离散化的数据。一个时空区域可比作具有时间维度的时空立方体,在时间维度上进行切片,每一个时间切片则为一个二维空间的投影。在这个时间切片上,再进一步对目标区域进行地理网格划分。参照频繁项集的处理方式[1],针对N 个网格的区域内的目标及其对应的M 个时间序列,在空间、时间上分别进行切片,获得离散化的划分,得到N×M 组事务,目标编组事物表如表1 所示。每个项集中包含当前时间分片、当前区域网格中出现的目标编号集合。

在针对船舶编组模型的关联规则研究中,与经典关联规则算法有以下的对应关系,如表2 所示。船舶的航运行为可以模拟顾客的购物行为,船舶的运行状态可以模拟购物篮中的商品。每艘船的航次可以模拟购物数据中的每一个事务。由一系列船舶的状态组成的船舶的行为,可以模拟每次事务中的商品。

与关联规则中的经典购物分析相比,设计的船舶行为分析输入如表3 所示。船舶连续的航迹状态用数字序号来表示。

表3 与关联规则中的经典购物分析对比Table 3 Comparison with classic shopping analysis in the association rules

本文为解决在海量船舶数据中的船舶航迹关联关系问题,分别定义关联关系和规则置信度。

定义1 关联规则:设船舶运行的状态S1和S2,其中有S1∩S2=∅,那么S1⇒S2被称为关联规则,其中S1被称为规则的前提,S2被称为规则的结论。规则S1⇒S2的意义为:当监测到船舶出现S1时,会规律性地出现S2,对船舶航迹状态进行关联分析,并根据状态的时间标志判定前提,可以生成知识库,为监测水面船舶的情况提供依据。此外,利用学习到的同一类船舶的规则,可以对有相同特征的船舶进行异常检测,满足关联规则条件的就认定为正常,否则为异常。

定义2 规则置信度:规则S1⇒S2的置信度为当检测到船舶出现状态S1时,其后续会出现状态S2的概率。利用公式表示为:

利用船舶航迹关联规则的置信度,可以筛选出每个频繁项集所对应的置信度较高的规则,从而有针对性地监测船舶的运行状态。

1.2 区域网格索引划分

区域网格索引的划分首先要解决划分的尺度。若网格的划分尺度过大,较多的移动船舶目标将会划分至同一网格,虽然能够减少漏判,但是由于单个网格的空间区域较大,可能造成误判的情况。相反,若网格的划分尺度过小,虽然能够减少误判,但是会导致较多的本是同一编组的船舶目标被划分为不同编组,正确性大大降低,造成漏判。

因此,网格划分应充分考虑时间尺度上不同目标可能的移动范围,例如渔船平均航速在3~5 kn,而货船、油轮则可以达到12~15 kn 左右,不同类型的目标在同一时间尺度上的移动范围不尽相同。因此,网格划分不仅要考虑时间分片的尺度,还应考虑目标运动特性。

根据船舶目标基本特征分析,针对不同类型船只,采用不同的经验值,结合时间参数,依据如下规则构建网格划分:

其中,Δt 表示时间划分尺度,Si表示目标速度参数。在以上范围内适当调整网格尺度Gridw,对目标区域进行划分。

同时,时间切片也应遵循不同目标的运动规律。例如,渔船作业规律一般以24 h 为周期,而货船或油轮的一次作业则可能长达数天甚至一个月,针对不同类型目标的时间切片尺度显然应有所不同。本文对渔船进行编组挖掘时以1 h 作为时间切片尺度,对油轮、货轮等开放海域航道作业的船只采用1 d 作为时间切片尺度。

网格索引中共存储4 个属性:网格中移动对象数量、移动对象列表、网格中心经度和纬度。通过索引直接读取每个网格中所有移动目标数量以及移动对象集合,提高了算法搜索候选对象集合的效率,从而提高算法的时间效率。

1.3 基于划分方法的频繁项集生成

面向海量的海上目标信息,即使将重点区域划分在很小的范围内,在长时间段的离散化中也会产生大量的项集,故采用普通的频繁项集挖掘算法根本无法将整个分片放入内存。而本文使用基于划分方法的频繁项集生成方法,先把数据集按照网格索引进行划分,并针对每个格网分块进行处理,分别生成对应的所有频集,然后将生成的频集进行合并,生成所有可能的频集,并计算项集的支持度。

使用上一步形成的项集划分,本文采用基于划分方法的FP-Growth 算法进行关联分析,并对频繁项集进行分析。若频繁项集的支持度满足一定的阈值,则该频繁项集为可能的船舶编组组合。其执行的主要步骤如图1 所示。

1)扫描原始的数据集:扫描数据集,计算数据项的支持度,构建频繁1 项集F,将F 中元素按支持度递减排序,F 作为项头表,建立指向FP-Tree 对应元素的引用。

2)构建FP-Tree:创建根节点为空的FP-Tree,再次扫描数据集,对事务中的数据按照F 序,将事务项中的数据挂载到FP-Tree 上,FP-Tree 的每个路径分支。记录每个节点出现的次数。

3)生成频繁模式基:逆序遍历F,根据其提供的引用指针,找出FP-Tree 中由该节点到根节点的路径,即生成每个频繁元素的条件模式基。

4)生成条件FP-Tree:根据每个频繁元素对应的条件模式基,生成其对应的条件FP-Tree,并删除路径中小于最小支持度的节点。

5)生成频繁项集之间的关联规则:对于每一颗条件FP-Tree,生成所有的从根节点到叶子节点的路径,生成路径中所有的非空子集,该子集和相应的频繁1 项集中的元素共同构成了含有该项数据集合的关联规则。

在初始扫描数据库,以及构建条件FP-Tree 的过程中,改进的FP-Growth 算法之前的执行流程和传统方式是一样的。不同之处在于最后生成关联规则时,针对添加的时间标志进行规则的判定,只保留符合时间标志位的频繁项集序列。

改进的FP-Growth 算法的执行过程如表4所示。

表4 改进的FP-Growth 算法过程Table 4 Process of the improved FP-Growth algorithm

通过以上步骤,可以从海量、碎片化的历史数据中,尽其所能挖掘出潜在的编组目标。算法适用于以海量碎片化数据描述的海上目标编组挖掘需求,可以从大量、混杂、时间空间跨度巨大的复杂场景中快速识别出可能的编组集合,也就是可能性较大的频繁项集,并找到其中的关联规则,以实现对海上态势的快速掌握。

2 海上目标编组模型

编组一般指的是把分散的人、交通工具等安排成一定形式的单位或单元,在这里,海上目标编组指的是若干海上目标组织成一定形式的单位或单元结队行动,在一定时空范围内,船只轨迹相似度较高。

有两种方式可以解决如下问题:1)求轨迹相似度,去掉轨迹相似度较低的;然后,对时空进行分析,找出时间交集大于某一阈值的。2)将问题转化为概率形式,经常(大于某一概率)出现在同一时间的同一地方。同一时间,对时间进行切片;同一地方,要求对地图切片;设定一个频率阈值,同一时间同一地点的频率大于设定阈值。

由于海上目标信息数据具有时空连续性,对其编组模型的确定将变得复杂而耗时,首先应对海量数据进行清洗、压缩、离散化等前期处理,减少海量数据带来的处理压力。尽管目前聚类算法已经很多,但每一个都有自身的优势和局限性。而海上目标信息数据与其他数据最显著的区别,在于其同时具备时间和空间特性。常用的经典聚类方法不能满足时空轨迹的相似性挖掘,所以如何对数据进行建模,采用何种挖掘算法至关重要。轨迹相似性挖掘关键在于,根据时空轨迹数据的特点,对不同轨迹之间相似度计算的方法进行设计至关重要。因此,本文研究并提出面向海量海上目标信息数据的频繁项集关联规则分类方法,并对船舶目标的编组关系进行挖掘,是一种海上目标编组算法模型。

算法步骤:

1)筛选区域内的航迹线:如舟山区域。

2)选取一段时间范围的数据:如1 d。

3)筛选采样点数量足够的船只:大于等于200个采样点。

4)对数据进行时间维度的切片:如1 h(24 个切片)。

5)对每个时间维度的切片进行地理区域离散化:如5 n mile/10 n mile。

6)对每张时间片上的每个地理网格内的船只目标出现情况进行统计,形成目标集合列表。

7)对生成的集合数据集,进行频繁项集挖掘,找出频繁项集。

8)通过关联分析,从频繁项集中提取出符合一定置信度的关联规则。

3 实验设计与结果

实验基于Proxmox 构建云平台实验环境,云平台由5 台计算机构成,实验用AIS 数据库部署于1台虚拟机,ES 服务部署于5 台虚拟机,对云平台的集群管理和程序调试采用2 台客户机。

3.1 数据准备

采用舟山区域的船舶数据,区域范围如图2 所示,经度范围121°38.438'E~124°02.303'E,纬度范围29°13.733'N~30°57.102'N。

图2 舟山区域Fig.2 Area of Zhoushan

3.2 数据预处理

1)选取数据:选取一天的船舶AIS 数据(2016年10 月1 日)

该数据集中总共包含3 341 条船,选取样本点超过200 的船只数据,最后获得67 条船的数据。轨迹运动的示意图如图3 所示。

图3 舟山地区10 月1 日的船舶轨迹Fig.3 Ship track in Zhoushan area on Oct.1st

2)对地域进行分片:切片划分

一般每5 n mile/10 n mile 一个切片。取5 n mile做切片,经度每5 n mile 一个区域,经度有17 个分片;纬度每5 n mile 一个区域,维度21 个分片;舟山区域总共被分割为1 721 块区域,如图4 所示。

图4 船舶轨迹分片示意图Fig.4 Schematic diagram of ship track segmentation

3)对时间进行分片:时间分片采用每小时一个分片策略,一天为24 分片。

4)数据映射(离散化):将每个小时内数据依次映射到区域分片中,达到连续数据离散化,以便进行频繁项集的挖掘,如图5 所示。

图5 舟山数据区域图Fig.5 Data area of Zhoushan

3.3 数据挖掘

1)把每个时间分片下的每个地理分片看作一个事件集。时间按1 h 进行分片,共计24 个分片。区域按照5 n mile×5 n mile 分片,共计17×21=357 个分片。完成时间-区域分片后,共产生17×21×24=8 568 个分片,也就是8 568 个事件集。

2)采用频繁项集算法对生成的数据集进行挖掘,频繁项集的最小支持度为0.04,挖掘出的频繁项集如表5 所示。

3)在上述频繁项集中只给出了频繁项,还需要通过关联分析,提取出符合一定置信度的船舶关联关系。选取最小置信度为0.8 进行关联分析,最后的结果如表6 所示。

表6 关联分析结果Table 6 Results of correlation analysis

3.4 结果及验证

通过实验,可以得到几组轨迹。置信度为1 的3组船舶轨迹数据(412 412 504-->412 498 888),绘制如图6 所示。

图6 置信度为1 的三组轨迹Fig.6 Three sets of tracks with a confidence of 1

图7 置信度为0.8 的一组轨迹Fig.7 A set of tracks with a confidence of 0.8

可以看出,置信度越高,船只的轨迹吻合度越高,当置信度为1 时,同组内的船只运行轨迹几乎完全吻合,可认定为一个编组。随着置信度的降低,轨迹吻合程度也开始降低。选取一定阈值以上的数据,可找出一个编组的数据。

为了进一步验证算法的有效性,本文采用模拟数据的方法。具体方法如下:

1)构建模拟轨迹,来测试模型的鲁棒性。该模拟轨迹采用两种方法来获取:a)利用数据集中某条真实轨迹的真实序列点增加一个偏移量得到,即把该条真实轨迹的所有轨迹点经纬度坐标向某一方向移动一段距离;b)在真实轨迹的基础上增加一个高斯噪声作为虚拟轨迹。

2)将得到的模拟轨迹放回到数据集中,重新使用该方法进行编组挖掘。

3)航迹比对,如算法能够找出此编组轨迹,表明算法具有较好有效性。

如图8 所示,将MMSI 号为412 441 615 的轨迹经度向东移动1 mile,构建后的轨迹MMSI 编为412 441 615(1),将此组轨迹标记为一个有效编组,并将构建的轨迹组放回到轨迹数据集中,进行编组挖掘,结果如图8(a),得到412 441 615->412 441 615(1)的支持度为0.97。

图8 轨迹验证Fig.8 Track verification

将MMSI 号为412 441 615 的轨迹经度加入均值为0 方差为1 mile 的高斯噪声,构建后的轨迹MMSI编为412 441 615(2),将此组轨迹标记为一个有效编组,并将构建的轨迹组放回到轨迹数据集中,进行编组挖掘,结果如图8(b),得到412 441 615->412 441 615(2)的支持度为0.98。

由此可见,能够从数据中找出标记过的模拟编组模型,可以说明挖掘算法具有较好有效性。

4 结论

从现实意义来说,在海量的数据中,信息的“发现”本身是一种探索行为,“发现”得到的结论是否正确,很大程度上还需要依赖人的经验进行判断。本文首先探讨了轨迹相似理论及轨迹聚类理论在目标编组挖掘中的应用模式,进而提出并设计了基于频繁项集的目标编组快速挖掘算法,实现可应用于海量船舶AIS 数据的目标轨迹编组模型挖掘,完成海上目标编组的自动识别算法,并通过验证说明方法的有效性,能够从大量杂乱的目标轨迹数据中得到海上目标的典型编组模型。在海上舰船监视、异常行为分析等方面具有良好的应用前景。

猜你喜欢
分片编组项集
上下分片與詞的時空佈局
分片光滑边值问题的再生核方法
CDN存量MP4视频播放优化方法
基于灵活编组的互联互通车载电子地图设计及动态加载
基于模糊二分查找的帧分片算法设计与实现
表观对称的轮廓编组算法
集中管理模式下编组场无线通信方案的选择
一种频繁核心项集的快速挖掘算法
重庆轨道2号线将换成6辆编组
一种新的改进Apriori算法*