推荐算法的船舶电子海图数据相似性检索方法

0 引言

电子海图是确保船舶航行安全的基础。船舶航行过程中，需要在海量船舶电子海图数据库内实时调取电子海图数据，为制定航行方案提供参考[1]。在海量电子海图数据内，精准检索到与检索目标相似性最高的电子海图数据[2]，可有效剔除无效的电子海图数据，为船员精准提供其需要的电子海图数据，制定安全的船舶导航路线[3]。李志欣等[4]通过自注意力方法增强电子海图数据特征，通过增强特征与哈希特征建立新的电子海图数据融合特征，以加权组合方式，处理新的电子海图数据融合特征，得到电子海图数据相似度矩阵。根据相似度矩阵，输出电子海图数据相似性检索结果。该方法具备较优的电子海图数据相似性检索有效性与鲁棒性。王宏志等[5]通过深度学习在电子海图数据库内提取电子海图数据相似性特征，按照条件熵与交叉熵的原理，设计多标签电子海图数据相似性检索方法，在该方法内输入提取的相似性特征，输出电子海图数据相似性检索结果。该方法的电子海图数据相似性检索精度较高，相比传统手工检索方法精度提升了10%左右。但这2 种方法在电子海图数据稀疏情况下，其电子海图数据相似性检索质量较低，且这2 种方法缺乏动态调整能力。推荐算法能够实时计算项目间的相似性，根据相似性计算结果生成推荐列表，具备较优的推荐效果，且推荐结果的动态调整能力较优。为此，研究推荐算法的船舶电子海图数据相似性检索方法，精准检索船舶电子海图数据，确保船舶航行安全。

1 船舶电子海图数据相似性检索

1.1 船舶电子海图数据稀疏评分矩阵填充

利用协同过滤推荐算法，检索船舶电子海图数据过程中，需要根据船舶电子海图数据评分矩阵，计算船舶电子海图数据与检索目标间的评分相似性。为充分利用船舶电子海图数据评分矩阵内的评分特征信息，需对稀疏评分矩阵进行填充，提升船舶电子海图数据评分矩阵内评分特征信息的利用率。为此，通过加权核范数算法，填充电子海图数据项目稀疏评分矩阵。利用核范数去松弛秩函数过程中，电子海图数据稀疏评分矩阵填充问题为：

其中：M为船舶电子海图数据稀疏评分矩阵；Y为近似填充矩阵；AΩ为正交投影算子；Ω为船舶电子海图数据的位置；‖·‖F为F范数；λ为正则化参数；‖·‖*为核范数；θ为秩函数。

‖Y‖*的计算公式如下：

其中：σi(Y)为Y内第i个奇异值；r为Y内奇异值数量。

利用奇异值分解算法求解式(1)时，奇异值阈值算子为：

其中：Sλ(M)为软阈值函数；M为奇异值分解，M=，U，V为船舶电子海图数据稀疏评分矩阵的m×m，n×n阶正交矩阵。式(3)的最佳解为：

为让奇异值分解算法，适合求解大规模船舶电子海图数据稀疏评分矩阵的填充问题，令

其中：Yk为k次迭代后的船舶电子海图数据稀疏评分矩阵的近似填充矩阵；AΩ⊥为 Ω补集内船舶电子海图数据位置信息。

通过奇异值分解算法得到k+1次迭代后的电子海图数据稀疏评分矩阵的近似填充矩阵为：

为提升数据稀疏评分矩阵的填充效果，利用加权核范数替换核范数，变更后的数据稀疏评分矩阵的填充问题为：

其中，w为非负加权。

加权核范数的计算公式如下：

通过奇异值分解算法求解式(7)，获取船舶电子海图数据稀疏评分矩阵的近似填充矩阵Y，即完整的船舶电子海图数据评分矩阵。

1.2 基于协同过滤推荐算法的海图数据相似性计算

在船舶电子海图数据近似填充矩阵Y的基础上，利用协同过滤推荐算法，计算船舶电子海图数据与检索目标u的评分相似性，公式如下：

其中：Y内第i′次检索时，第l个船舶电子海图数据的评分是yl,i′；X内船舶电子海图数据的数量是L；Y内船舶电子海图数据评分均值是；Y内第i′次检索时，船舶电子海图数据检索目标的评分元素是yu,i′。

利用协同过滤推荐算法，计算船舶电子海图数据与检索目标u的类别相似性。实际船舶电子海图数据库内，全部电子海图数据项均可划分至不同类别内，各大类内均包含数个小类，为此，可将船舶电子海图数据库看成一棵倒立的树，记作船舶电子海图数据类别树。船舶电子海图数据类别树的层数是类别树的高度H；电子海图数据l与检索目标u共同所处的类别为l与u的公共类。l，u间可能存在数个公共类，同时最少包含一个公共类，就是电子海图数据类别树的根节点。l、u的公共类集合内，距离电子海图数据类别树根节点层数最多的公共类，叫做l，u的最近公共类。l与u的最近公共类只有一个。l与u在类别树内所处的层数是最近公共类高度H′(l,u)，在H′(l,u)=1情况下，l与u的最近公共类，便是船舶电子海图数据类别树的根节点。l与u间的类别相似性为：

1.3 海图数据相似性检索的实现

依电子海图数据与检索目标间的评分相似性，根据相似性推荐的预测评分，依据船舶电子海图数据与检索目标间的类别相似性，计算电子海图数据相似性推荐的预测评分，公式如下：

通过动态加权的方式，融合Ql,i′与，得到最终的船舶电子海图数据相似性推荐的预测评分，降序排列船舶电子海图数据相似性推荐的预测评分，生成推荐列表，即船舶电子海图数据相似性检索结果。

利用协同过滤推荐算法，完成船舶电子海图数据相似性检索的具体步骤如下：

步骤1输入船舶电子海图数据检索目标u；

步骤2填充船舶电子海图数据稀疏评分矩阵，得到Y；

步骤3在Y的基础上，计算船舶电子海图数据与u间的评分相似性ζ(u,l)；

步骤4计算船舶电子海图数据与u间的类别相似性ζ′(l,u)；

步骤5根据评分相似性与类别相似性，计算u与电子海图数据相似性推荐的预测评分Ql,i′，；

步骤6以动态加权的方式，融合Ql,i′与，得到Qˆ(u,l)，降序排列Qˆ(u,l)，生成与u最为相似的船舶电子海图数据推荐列表，即船舶电子海图数据相似性检索结果。

2 实验结果分析

以某船舶公司为实验对象，该公司使用的船舶电子海图数据库格式为THOS-57，数据库内包含将近9 000幅电子海图，平均每年递增500 幅新电子海图。利用本文方法在该数据库内，完成电子海图数据相似性检索，为船员精准提供其需要的电子海图数据，保障船舶安全航行。

利用本文方法在数据库内随机选择10 个电子海图数据，电子海图数据内检索包含危险物标超过20 个，且双向航行安全的目标电子海图数据。先利用本文方法计算这10 个船舶电子海图数据与检索目标间的相似性与推荐预测评分，推荐预测评分计算结果如图1 所示。根据图1 可知，本文方法可有效计算电子海图数据相似性推荐预测评分，其中，编号为4 的船舶电子海图数据推荐预测评分最高，说明该船舶电子海图数据与检索目标间的相似性最高。

图1 电子海图数据相似性推荐预测评分计算结果Fig.1 Calculation results of the recommended prediction score for the similarity of electronic chart data

船舶电子海图数据相似性检索结果如图2 所示。可知，本文方法可有效检索到与检索目标最为相似的电子海图数据，电子海图数据内共包含24 个危险物标，航线属于双向航线，且航线内无危险物标，即双向航行安全，与检索目标非常相似。实验证明：本文方法具备船舶电子海图数据相似性检索的可行性，且检索到的电子海图数据与检索目标相似度较高。

图2 舰船电子海图数据相似性检索结果Fig.2 Similar retrieval results of ship electronic chart data

利用归一化折损累积增益(normalized discounter cumulative gain，NDCG)，衡量本文方法船舶电子海图数据相似性的检索效果，NDCG 值越高，检索精度越高。分析不同电子海图数据评分矩阵稀疏度，以及不同检索目标时，本文方法电子海图数据相似性检索的NDCG，分析结果如图3 所示。可知，随着稀疏度的提升，本文方法在检索2 个检索目标时的NDCG 均不断下降，当稀疏度为0.40 时，检索目标1 的NDCG 降至最低，在0.86 左右，检索目标2 的最低NDCG 在0.84 左右，均高于设置阈值。实验证明，在不同电子海图数据评分矩阵稀疏度时，本文方法检索电子海图数据的NDCG 值均较高，即电子海图数据相似性检索精度较高。