基于正常行为的案例推理在伪装船只识别中的应用∗

2018-09-27 01:23邬鹏飞
舰船电子工程 2018年9期
关键词:约简案例库邻域

邬鹏飞 姚 路 曾 斌

(海军工程大学管理工程与装备经济系 武汉 430034)

1 引言

重点海域管控是维护我国海洋领土安全与海洋权的益重要环节。实现对海域的有效管控,船只身份的识别是其中一项重要的基础性工作。获取船只身份的最快速方法,无疑是通过接受船舶自动识别系统(AIS)数据来判断,但由于AIS身份数据由目标船只本身主动广播,比较便于造假,因此在军事领域,通过AIS获取船只身份的方法并不可靠。同时,随着海上斗争形势的日益复杂,敌对势力使用伪装为民船对我领海进行渗透侦察的方式变得越来越普遍,使得对船只身份的识别变得更加复杂。因此必须加强对伪装船只的识别研究,转变现有的依靠指挥员经验进行识别的传统做法,实现对伪装船只的快速准确识别,确保我海洋领土安全与海上权益不受侵害。

目前的针对船只识别的手段有很多,主要有红外成像、合成孔径雷达(SAR)成像和卫星遥感成像等方法,这些船只识别手段都有着不同的优点和局限性[1~4]。上述方法,本质都是从成像的角度出发,利用船只的外形特征来实现对船只身份的确定,而忽略了船只的行为因素。因此本文在上述研究的基础上,将船只行为引入船只身份的识别中,从对比正常船只与伪装船只在行为角度的差异出发,实现对船只目标身份的确定。船只行为特征是在一定自然条件下由于装备等条件限制而形成的固有特征,船只只要有不正常的动作,必然产生不正常的行为,相比船只外形等特征,更加难以伪装。随着在计算机技术的发展,对于行为研究也变得越来越深入。刘智[5]等利用卷积神经网络建立了一个人体行为识别模型;何传阳[6]等采用Vibe算法对群体行为进行检测,取得了较好效果;范菁[7]等利用聚类分析和HMM-RF模型对车辆行为检测进行了研究。在上述研究的基础上,通过采集船只行为案例,形成案例库,抽象概括正常行为。比对目标船只行为与正常船只行为的相似度,若相似度小于阈值,则判定该船只行为是异常行为,以此对伪装船只进行识别。

2 基于行为的船只身份识别基本原理

案例推理(Case-based Reasoning CBR),作为一种智能推理方法,它通过重用以往经验解决来新问题,已受到大量学者关注[8]。在其应用当中,案例推理常常与规则推理结合,但在实际应用中发现,推理规则往往难以获取,并且由于规则之间的相互依赖,导致对知识库的日常维护较困难。针对以上问题,本文采用单一的案例推理模式,并针对案例数据维数高且并不是同等重要且不相关属性容易影响推理结果这一现实情况,将邻域粗糙集引入案例推理中,利用其对船只行为特征属性进行约简,抽取出决定目标属性的关键属性,在提高推理效率的同时,提高推理的准确性;考虑到案例库的规模较大,为进一步提高推理效率,对案例库进行聚类处理,将案例库分为若干子案例库,当有新问题的时候首先比较其与个子案例库的聚类中心(特征案例)的相似度,优先搜索相似度较大的特征案例对应的子案例库,避免遍历整个案例库,以提高搜索效率。由于到异常行为样本的获取比较困难,因此本文采用反向推理的模式,通过对比与正常船只行为的差异来判断船只的可疑程度,认为与正常船只行为相似度较小的为伪装船只。本文采用案例推理结合邻域粗糙集来实现对伪装船只的检测,具体流程如图1所示。

图1 基于邻域粗糙集与案例推理船只身份识别流程

3 基于案例推理与邻域粗糙集的船只身份识别

3.1 船只行为描述

由于到船只行为是船只在一个时间段内产生的动作的集合,综合考虑船只在一段时间内的动作、船只本身特性和当时的自然条件,形成对于船只行为的描述,主要包括几个方面:

自然要素:风向,风力,浪高,浪向,流速,能见度;

船只基本要素:船只大小,最大观测航速;

航行动作要素:指各种机动动作的机动参数,包括航向改变次数、航速改变次数;

交互动作要素:指各种通信的通信参数,包括目标与其他实体通信次数、通信实体数和通信时间;

状态动作要素:包括与我方目标距离小于3海里时间和、与我方目标最小距离。

3.2 船只行为表示方法

案例表示是对船只行为案例的描述,将案例转化为计算机可存储和识别的数据结构。案例表示为两个部分。

第一个部分是对案例(船只行为)的描述,主要包括自然条件,船只基本属性,船只机动动作,舰船交互动作,船只状态动作。

第二个部分是对目标船只身份的描述,即:客船、货船、渔船、可疑船只。

根据以上的规则,我们可以用二元组的表达方式对案例进行描述,即 Case=(F,I),其中 F=(f1,f2,…,fn)为案例的各类属性;I为船只的身份。

3.3 基于邻域粗糙集的船只行为属性约简

基于粗糙集理论的属性约简,可以在保持决策表决策属性和条件属性之间的依赖关系不发生变化的前提下对决策表进行约简[9]。然而,经典的粗糙集只适合处理离散化变量,对于现实应用中广泛存在的数值型连续变量却不能直接处理。因此,在使用经典粗糙集进行属性约简之前,往往首先采用一定的方法对连续数据进行离散化处理,将连续变量转化为离散变量。在这一过程中将不可避免地带来一定的信息损失,约简的结果很大程度上依赖于数据离散的效果。针对这一问题,本文采用文献[10]提供的方法,利用邻域粗糙集对行为案例进行属性约简,以避免对数据进行离散化处理,从而最大程度保留原始数据的信息。

表1 船只行为属性表

定义1:在给定实数空间n上的非空有限集合,对于∀xi的邻域δ-定义为

δ(xi)={x|x∈U,Δ(x,xi)≤δ}δ≥0其中Δ是一个距离函数。

定义2:U为论域,N是U上的邻域关系,是邻域粒度的集合。则称(U,N)是一个近似邻域空间。

定义3:实数空间Ω上的非空有限集合U={x1,x2,...,xn} 及其上的邻域关系 N,即二元组 NS=(U,N),∀X⊆U 则X在邻域近似空间NS=(U,N)中的上近似和下近似分别为

定义4:给定邻域决策系统中,另B和D为U中的属性集合决策集,B的正域记为PosB(D),负域记为 NegB(D),则:

定义5:决策属性D对条件属性B的依赖度定义为

定义6:对于邻域决策系统 S=<U,C,D,V>,B⊆C,a∈B,属性a的重要度为

该方法从空集出发,每次循环都将重要度最大的属性添加到约简集中,然后计算剩余属性的属性重要度,继续选择重要度值最大的属性添加到约简集合中,直到所有剩余属性的重要度基本不发生变化。具体流程如下:

步骤1 确定邻域半径r和重要度下限阈值;步骤2 令约简集为空集;

步骤3 计算约简集之外的剩余属性的上近似集、下近似集、正域、依赖度和重要度;

步骤4 选择重要度最大的属性加入到约简集中;

步骤5 返回步骤3,直到所有剩余条件属性的重要度都低于阈值,算法停止,输出约简。

用上述方法对案例库中的案例进行处理后,提取案例的关键属性如表2所示。

表2 约简后的船只行为关键属性

3.4 船只行为案例相似度确定

3.4.1 案例属性相似度计算

案例X与案例Y的相似度定义如下:

显然,对于案例的推理过程中,相似度的计算至关重要。根据上述对案例属性体系的约简结果可知,案例的属性值全为数值型,考虑到各个指标之间量纲的差异,将所有的数值型数据统一为一个指标矩阵,采用如下方法来计算数值型属性间相似度:

通常与正常船只行为相似度较高的船只,我们认为它的可疑度较低,因此可疑船只的可疑度,可被定义为

max(sim(X,Yj))为目标船只行为案例与案例库中所有相似度的最大值。

3.4.2 案例属性权重分配

采用上述方法对各个类型的属性计算出相似度后,还需有各个属性的权重,才可以利用式(1)计算出两个案例的相似度。对于各个属性的权重的分配,可以采用专家打分或者层次分析(AHP)等方法,但这两种方法高度依赖专家的主观判断,有时候并不能完全客观地反映属性的重要程度。这里介绍一种结合遗传算法与自省学习的权重分配方法。该方法主要分为两个阶段,第一阶段使用遗传算法对权重进行初始分配,第二阶段采用内省学习对权重进行调整。

其基本思想是:在初次训练的过程中,利用遗传算法,将属性权重编码为染色体,以推理正确率为适应函数,优选到符合优化目标的案例属性初始权重。针对遗传算法易陷入局部最优的缺点,利用内省学,进行二次训练,在该训练过程中,对于推理正确的案例,增大高相似度属性的权重,减小低相似度属性的权重,对于推理失败的案例,则正好相反。内省学习,主要分为以下几个步骤:

1)高相似度与低相似度的定义

定 义 :案 例 X=(x1,x2,…,xn), Y=(y1,y2,…,yn),如果满足则称第i个属性为高相似属性;若满足,则称第i属性为低相似属性。

2)权重调整

对于权重的增加或减少有两种基本方法,第一种在所要调整的权重的原有基础上增加或减少某个固定值,第二种在所要调整的权重的原有基础上乘以或除以一个大于1的固定值。对于第一种方法,在权重的调整过程中,有可能会出现负权重的现象,因此本文采用第二种方法。

对于权重增加:

其中,ωi(t)为第i个特征属性第t次迭代的权重;ωi(t +1)是第i个特征属性第t+1次迭代的权重;本文k值取1.2。当权重调整完毕后,为保证,需要对其进行归一化处理,具体方法如

对于权重减少:下:

3.5 案例检索

3.5.1 案例聚类

为提高在大案例情况下的案例检索效率,本文采用聚类方法对案例库进行处理。聚类算法中,k均值聚类算法应用最为普遍,但其聚类效果与初始聚类中心的选择关系密切,初始聚类中心选择的好坏,很大程度上决定了聚类结果有效与否[11]。考虑到以上问题,使用如下方法获得初始聚类中心,具体流程如下:

第1步,按式(1)计算任意两个案例的相似度,从而找出相似度最小的两个(或多个)案例作为头两个(或多个)聚类中心。

第2步,计算出与已有聚类中心相似度最小的案例,并把它作为下一个聚类中心。

第3步,重复第2步,直到找到k(聚类总数)个聚类中心。

这样我们就找到了k个彼此间相似度最小的案例作为初始聚类中心。

案例归类过程中采用相似度最大原则,即将案例归类到与之相似度最大的案例类中,如果有多个最大相似类则将其归类到案例数目最少的案例类中,若此时案例数目最少的案例类也有多个则随机将其分配到其中一个案例类中。使同一类案例相似度高且各类案例的数量尽量相近,确保能快速找出新问题的相似案例与之匹配。

综上,案例聚类算法的步骤如下:

第1步,从案例库的m个案例中,按上述方法选取k个案例作为初始聚类中心。

第2步,按式(1)计算案例库中所有案例与各聚类中心的相似度。

第3步,根据最大相似度对案例库中每个案例进行归类。

第4步,重新计算聚类中心,即将每类所有案例的平均值作为新的聚类中心。

第5步,重复第2步到第4步直到不再有案例被重新归类。

第6步,结束聚类过程,输出聚类结果,并将各案例类的聚类中心构成特征案例集(作为子案例库的索引)。

3.5.2 搜索流程

在案例检索匹配过程中,最近邻方法(KNN)是一种应用较多的方法。常规情况下,最近邻方法将计算所有案例与新问题之间的相似度,找出与该问题最相近的一个或几个案例,在这种情况下,必须检索整个案例库,当案例库案例数量较多时,其检索效率并不高[12]。

针对船只行为案例库较大的现实状况,为实现对船只目标的快速识别,必须提高案例检索的速度。因此本文采用层次检索的策略,在成对案例库的聚类的基础上,当有新案例时,首先将新案例与每个子案例库的特征案例进行比较,筛选若干个相似度最大的特征案例(一级检索),然后再将新案例与特征案例所代表的子案例库中的所有案例进行比较,如果存在相似度大于阈值的案例,则认为新案例为正常,否则即判定其为伪装船只,并遍历整个案例库,得到其可疑度。检索流程图如图3所示。

1)一级检索

第1步,获得当前探测到的船只行为数据所描述的新问题X=(x1,x2,…,xn)。

第2步,按式(1)计算X与所有特征案例间的相似度。

第3步,找出与新问题案例相似度最大的特征案例所对应的所有子案例库(可能有一个,也可能有多个)。

2)二级检索

检索一级搜索筛选出的所有子案例库。如果这些案例库中存在与问题X相似度大于阈值b的案例,则将该案例作为X的匹配案例(即X为正常船只),否则X为伪装船只,同时遍历整个案例库,利用式(4)计算出船只的可疑程度。

4 实例验证

为验证方法的有效性,使用我国沿海某海域2017年3月16日至11月6日的AIS数据为样本。利用船舶自动识别系统(AIS)可以获得船只的船位、船速、改变航向率、航向、船名、呼号、船长、危险货物等数据[13],对这些数据进行简单处理后,结合当日气象就可以得到文中所需要的正常船只行为信息。通过对采集到的原始AIS数据进行预处理,得到了53246个正常船只行为案例。考虑到伪装船只行为案例较少(仅通过其他途径采集到5个),计算伪装船只案例属性值的均值和方差,再以5个原始伪装船只行为案例为基础,随机选取其一个或多个属性,加上或减去具有对应均值和方差的正态随机值,仿真出49个伪装船只案例,这样就获得了54个伪装船只行为案例。

其中部分船只行为案例如表3所示,其中船只类别项中,1表示可疑船只,0表示正常船只。

4.1 验证结果

使用53000个正常船只行为案例构建初始案例库,使用246个正常船只案例和54个伪装船只作为测试案例集,采用逐渐增加测试案例个数的策略,将本文方法与传统案例推理方法(不进行属性约简,采用KNN检索策略)进行对比,验证本文提出方法的检索时间效率,所得结果如图4所示。

由图4可以看出,当案例较少时,两种方法耗时均很小,随着案例库的增加传统案例推理方法的检索时间会近似的线性增长,而本文所提出方法的增长速率要明显小于传统案例推理方法,两种方法的搜索时间差异逐渐增大,相比于传统案例推理,本文的方法效率更高,当测试集的数量为300时,节省时间69%。

图4 推理时间图

为验证方法的有效性,将另测试案例的数量为300,通过取不同阈值,得到对应的虚警率和漏检率,如图5、图6所示。

图5 漏检率随阈值变化图

图6 虚警率随阈值变化图

可见,随着阈值的增加,本文的方法比传统方法漏检率增长缓慢,随着阈值的减小,虚警率增加相对也比较小,当阈值取0.86时,本文方法的推理正确达到最高,为91.2%,比传统方法高8.7%。

4.2 结果分析

4.2.1 算法的检索效率分析

对于船只身份推理问题,传统的案例推理方法,案例库中所有案例(假设有n个)都要参与案例检索过程。那么1个新案例所检索的次数为n次。而本文提出案例推理方法(假设分为m类,m<<n),在进行一级检索时,新案例只与特征案例比较,一级检索的次数为m次,在进行二级检索时,只需要案例库中一部分(通常为案例库的若干分之一,假设有p个),那么二次过程的搜索次数为p,总搜索次数为m+p≈p<<n。特别案例数量很大时,m+p≈p与n差距更大,本文方法与传统方法的检索时间差异将更大。

4.2.2 算法的精确度分析

由于邻域粗糙集的使用,原始案例中的非关键要素被去除,排除了不相关要素对推理结果的影响,有利于提高推理准确度;同时,由于在对案例库进行聚类处理的过程中,与特征案例具有较高的相似度的案例都被归到同一子案例库中,从而保证与X有较高相似度的案例几乎都包含由一级检索得到的子案例库中,使得在整个检索过程中,与X有匹配度较高的案例不会被遗漏。

5 结语

根据伪装舰船识别问题的实际,从舰船行为角度出发,利用邻域粗糙集、案例聚类等方法,提出了基于案例推理的识别方法。使用计算机仿真,得到不同相似度阈值情况下的预警率与漏检率,并将本文提出的方法与传统案例推理方法进行对比,实验结果表明,提出的方法在在不同阈值的情况下漏检率与虚警率均优于传统方法,同时能够避免传统案例推理方法随着案例数量增多,检索时间增长较快的缺点。尽管本方法在案例检索阶段具有较高的检索效率,但在前期的训练过程中,尤其是权重获取与案例聚类阶段耗费时间较多,如何提高前期训练与案例处理效率还需要进一步研究。

猜你喜欢
约简案例库邻域
心血管外科教学案例库的建设及应用研究
《宁夏大学学报(自然科学版)》入选2021年度中国高校科技期刊建设示范案例库
基于混合变邻域的自动化滴灌轮灌分组算法
《宁夏大学学报(自然科学版)》入选2021年度中国高校科技期刊建设示范案例库
国内首个海事司法案例库正式上线
含例邻域逻辑的萨奎斯特对应理论
融合t-分布随机邻域嵌入与自动谱聚类的脑功能精细分区方法
面向连续参数的多粒度属性约简方法研究
基于差别矩阵的区间值决策系统β分布约简
带权决策表的变精度约简算法