推薦算法的船舶電子海圖數(shù)據(jù)相似性檢索方法

金仕奇

(江西工程學(xué)院 大數(shù)據(jù)與計(jì)算機(jī)學(xué)院，江西 新余 338000)

0 引 言

電子海圖是確保船舶航行安全的基礎(chǔ)。船舶航行過(guò)程中，需要在海量船舶電子海圖數(shù)據(jù)庫(kù)內(nèi)實(shí)時(shí)調(diào)取電子海圖數(shù)據(jù)，為制定航行方案提供參考[1]。在海量電子海圖數(shù)據(jù)內(nèi)，精準(zhǔn)檢索到與檢索目標(biāo)相似性最高的電子海圖數(shù)據(jù)[2]，可有效剔除無(wú)效的電子海圖數(shù)據(jù)，為船員精準(zhǔn)提供其需要的電子海圖數(shù)據(jù)，制定安全的船舶導(dǎo)航路線[3]。李志欣等[4]通過(guò)自注意力方法增強(qiáng)電子海圖數(shù)據(jù)特征，通過(guò)增強(qiáng)特征與哈希特征建立新的電子海圖數(shù)據(jù)融合特征，以加權(quán)組合方式，處理新的電子海圖數(shù)據(jù)融合特征，得到電子海圖數(shù)據(jù)相似度矩陣。根據(jù)相似度矩陣，輸出電子海圖數(shù)據(jù)相似性檢索結(jié)果。該方法具備較優(yōu)的電子海圖數(shù)據(jù)相似性檢索有效性與魯棒性。王宏志等[5]通過(guò)深度學(xué)習(xí)在電子海圖數(shù)據(jù)庫(kù)內(nèi)提取電子海圖數(shù)據(jù)相似性特征，按照條件熵與交叉熵的原理，設(shè)計(jì)多標(biāo)簽電子海圖數(shù)據(jù)相似性檢索方法，在該方法內(nèi)輸入提取的相似性特征，輸出電子海圖數(shù)據(jù)相似性檢索結(jié)果。該方法的電子海圖數(shù)據(jù)相似性檢索精度較高，相比傳統(tǒng)手工檢索方法精度提升了10%左右。但這2 種方法在電子海圖數(shù)據(jù)稀疏情況下，其電子海圖數(shù)據(jù)相似性檢索質(zhì)量較低，且這2 種方法缺乏動(dòng)態(tài)調(diào)整能力。推薦算法能夠?qū)崟r(shí)計(jì)算項(xiàng)目間的相似性，根據(jù)相似性計(jì)算結(jié)果生成推薦列表，具備較優(yōu)的推薦效果，且推薦結(jié)果的動(dòng)態(tài)調(diào)整能力較優(yōu)。為此，研究推薦算法的船舶電子海圖數(shù)據(jù)相似性檢索方法，精準(zhǔn)檢索船舶電子海圖數(shù)據(jù)，確保船舶航行安全。

1 船舶電子海圖數(shù)據(jù)相似性檢索

1.1 船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣填充

利用協(xié)同過(guò)濾推薦算法，檢索船舶電子海圖數(shù)據(jù)過(guò)程中，需要根據(jù)船舶電子海圖數(shù)據(jù)評(píng)分矩陣，計(jì)算船舶電子海圖數(shù)據(jù)與檢索目標(biāo)間的評(píng)分相似性。為充分利用船舶電子海圖數(shù)據(jù)評(píng)分矩陣內(nèi)的評(píng)分特征信息，需對(duì)稀疏評(píng)分矩陣進(jìn)行填充，提升船舶電子海圖數(shù)據(jù)評(píng)分矩陣內(nèi)評(píng)分特征信息的利用率。為此，通過(guò)加權(quán)核范數(shù)算法，填充電子海圖數(shù)據(jù)項(xiàng)目稀疏評(píng)分矩陣。利用核范數(shù)去松弛秩函數(shù)過(guò)程中，電子海圖數(shù)據(jù)稀疏評(píng)分矩陣填充問(wèn)題為：

其中：M為船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣；Y為近似填充矩陣；AΩ為正交投影算子；Ω為船舶電子海圖數(shù)據(jù)的位置；‖·‖F(xiàn)為F范數(shù)；λ為正則化參數(shù)；‖·‖*為核范數(shù)；θ為秩函數(shù)。

‖Y‖*的計(jì)算公式如下：

其中：σi(Y)為Y內(nèi)第i個(gè)奇異值；r為Y內(nèi)奇異值數(shù)量。

利用奇異值分解算法求解式(1)時(shí)，奇異值閾值算子為：

其中：Sλ(M)為軟閾值函數(shù)；M為奇異值分解，M=，U，V為船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣的m×m，n×n階正交矩陣。式(3)的最佳解為：

為讓奇異值分解算法，適合求解大規(guī)模船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣的填充問(wèn)題，令

其中：Yk為k次迭代后的船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣的近似填充矩陣；AΩ⊥為 Ω補(bǔ)集內(nèi)船舶電子海圖數(shù)據(jù)位置信息。

通過(guò)奇異值分解算法得到k+1次迭代后的電子海圖數(shù)據(jù)稀疏評(píng)分矩陣的近似填充矩陣為：

為提升數(shù)據(jù)稀疏評(píng)分矩陣的填充效果，利用加權(quán)核范數(shù)替換核范數(shù)，變更后的數(shù)據(jù)稀疏評(píng)分矩陣的填充問(wèn)題為：

其中，w為非負(fù)加權(quán)。

加權(quán)核范數(shù)的計(jì)算公式如下：

通過(guò)奇異值分解算法求解式(7)，獲取船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣的近似填充矩陣Y，即完整的船舶電子海圖數(shù)據(jù)評(píng)分矩陣。

1.2 基于協(xié)同過(guò)濾推薦算法的海圖數(shù)據(jù)相似性計(jì)算

在船舶電子海圖數(shù)據(jù)近似填充矩陣Y的基礎(chǔ)上，利用協(xié)同過(guò)濾推薦算法，計(jì)算船舶電子海圖數(shù)據(jù)與檢索目標(biāo)u的評(píng)分相似性，公式如下：

其中：Y內(nèi)第i′次檢索時(shí)，第l個(gè)船舶電子海圖數(shù)據(jù)的評(píng)分是yl,i′；X內(nèi)船舶電子海圖數(shù)據(jù)的數(shù)量是L；Y內(nèi)船舶電子海圖數(shù)據(jù)評(píng)分均值是；Y內(nèi)第i′次檢索時(shí)，船舶電子海圖數(shù)據(jù)檢索目標(biāo)的評(píng)分元素是yu,i′。

利用協(xié)同過(guò)濾推薦算法，計(jì)算船舶電子海圖數(shù)據(jù)與檢索目標(biāo)u的類(lèi)別相似性。實(shí)際船舶電子海圖數(shù)據(jù)庫(kù)內(nèi)，全部電子海圖數(shù)據(jù)項(xiàng)均可劃分至不同類(lèi)別內(nèi)，各大類(lèi)內(nèi)均包含數(shù)個(gè)小類(lèi)，為此，可將船舶電子海圖數(shù)據(jù)庫(kù)看成一棵倒立的樹(shù)，記作船舶電子海圖數(shù)據(jù)類(lèi)別樹(shù)。船舶電子海圖數(shù)據(jù)類(lèi)別樹(shù)的層數(shù)是類(lèi)別樹(shù)的高度H；電子海圖數(shù)據(jù)l與檢索目標(biāo)u共同所處的類(lèi)別為l與u的公共類(lèi)。l，u間可能存在數(shù)個(gè)公共類(lèi)，同時(shí)最少包含一個(gè)公共類(lèi)，就是電子海圖數(shù)據(jù)類(lèi)別樹(shù)的根節(jié)點(diǎn)。l、u的公共類(lèi)集合內(nèi)，距離電子海圖數(shù)據(jù)類(lèi)別樹(shù)根節(jié)點(diǎn)層數(shù)最多的公共類(lèi)，叫做l，u的最近公共類(lèi)。l與u的最近公共類(lèi)只有一個(gè)。l與u在類(lèi)別樹(shù)內(nèi)所處的層數(shù)是最近公共類(lèi)高度H′(l,u)，在H′(l,u)=1情況下，l與u的最近公共類(lèi)，便是船舶電子海圖數(shù)據(jù)類(lèi)別樹(shù)的根節(jié)點(diǎn)。l與u間的類(lèi)別相似性為：

1.3 海圖數(shù)據(jù)相似性檢索的實(shí)現(xiàn)

依電子海圖數(shù)據(jù)與檢索目標(biāo)間的評(píng)分相似性，根據(jù)相似性推薦的預(yù)測(cè)評(píng)分，依據(jù)船舶電子海圖數(shù)據(jù)與檢索目標(biāo)間的類(lèi)別相似性，計(jì)算電子海圖數(shù)據(jù)相似性推薦的預(yù)測(cè)評(píng)分，公式如下：

通過(guò)動(dòng)態(tài)加權(quán)的方式，融合Ql,i′與，得到最終的船舶電子海圖數(shù)據(jù)相似性推薦的預(yù)測(cè)評(píng)分，降序排列船舶電子海圖數(shù)據(jù)相似性推薦的預(yù)測(cè)評(píng)分，生成推薦列表，即船舶電子海圖數(shù)據(jù)相似性檢索結(jié)果。

利用協(xié)同過(guò)濾推薦算法，完成船舶電子海圖數(shù)據(jù)相似性檢索的具體步驟如下：

步驟1輸入船舶電子海圖數(shù)據(jù)檢索目標(biāo)u；

步驟2填充船舶電子海圖數(shù)據(jù)稀疏評(píng)分矩陣，得到Y(jié)；

步驟3在Y的基礎(chǔ)上，計(jì)算船舶電子海圖數(shù)據(jù)與u間的評(píng)分相似性ζ(u,l)；

步驟4計(jì)算船舶電子海圖數(shù)據(jù)與u間的類(lèi)別相似性ζ′(l,u)；

步驟5根據(jù)評(píng)分相似性與類(lèi)別相似性，計(jì)算u與電子海圖數(shù)據(jù)相似性推薦的預(yù)測(cè)評(píng)分Ql,i′，；

步驟6以動(dòng)態(tài)加權(quán)的方式，融合Ql,i′與，得到Q?(u,l)，降序排列Q?(u,l)，生成與u最為相似的船舶電子海圖數(shù)據(jù)推薦列表，即船舶電子海圖數(shù)據(jù)相似性檢索結(jié)果。

2 實(shí)驗(yàn)結(jié)果分析

以某船舶公司為實(shí)驗(yàn)對(duì)象，該公司使用的船舶電子海圖數(shù)據(jù)庫(kù)格式為T(mén)HOS-57，數(shù)據(jù)庫(kù)內(nèi)包含將近9 000幅電子海圖，平均每年遞增500 幅新電子海圖。利用本文方法在該數(shù)據(jù)庫(kù)內(nèi)，完成電子海圖數(shù)據(jù)相似性檢索，為船員精準(zhǔn)提供其需要的電子海圖數(shù)據(jù)，保障船舶安全航行。

利用本文方法在數(shù)據(jù)庫(kù)內(nèi)隨機(jī)選擇10 個(gè)電子海圖數(shù)據(jù)，電子海圖數(shù)據(jù)內(nèi)檢索包含危險(xiǎn)物標(biāo)超過(guò)20 個(gè)，且雙向航行安全的目標(biāo)電子海圖數(shù)據(jù)。先利用本文方法計(jì)算這10 個(gè)船舶電子海圖數(shù)據(jù)與檢索目標(biāo)間的相似性與推薦預(yù)測(cè)評(píng)分，推薦預(yù)測(cè)評(píng)分計(jì)算結(jié)果如圖1 所示。根據(jù)圖1 可知，本文方法可有效計(jì)算電子海圖數(shù)據(jù)相似性推薦預(yù)測(cè)評(píng)分，其中，編號(hào)為4 的船舶電子海圖數(shù)據(jù)推薦預(yù)測(cè)評(píng)分最高，說(shuō)明該船舶電子海圖數(shù)據(jù)與檢索目標(biāo)間的相似性最高。

圖1 電子海圖數(shù)據(jù)相似性推薦預(yù)測(cè)評(píng)分計(jì)算結(jié)果Fig.1 Calculation results of the recommended prediction score for the similarity of electronic chart data

船舶電子海圖數(shù)據(jù)相似性檢索結(jié)果如圖2 所示。可知，本文方法可有效檢索到與檢索目標(biāo)最為相似的電子海圖數(shù)據(jù)，電子海圖數(shù)據(jù)內(nèi)共包含24 個(gè)危險(xiǎn)物標(biāo)，航線屬于雙向航線，且航線內(nèi)無(wú)危險(xiǎn)物標(biāo)，即雙向航行安全，與檢索目標(biāo)非常相似。實(shí)驗(yàn)證明：本文方法具備船舶電子海圖數(shù)據(jù)相似性檢索的可行性，且檢索到的電子海圖數(shù)據(jù)與檢索目標(biāo)相似度較高。

圖2 艦船電子海圖數(shù)據(jù)相似性檢索結(jié)果Fig.2 Similar retrieval results of ship electronic chart data

利用歸一化折損累積增益(normalized discounter cumulative gain，NDCG)，衡量本文方法船舶電子海圖數(shù)據(jù)相似性的檢索效果，NDCG 值越高，檢索精度越高。分析不同電子海圖數(shù)據(jù)評(píng)分矩陣稀疏度，以及不同檢索目標(biāo)時(shí)，本文方法電子海圖數(shù)據(jù)相似性檢索的NDCG，分析結(jié)果如圖3 所示。可知，隨著稀疏度的提升，本文方法在檢索2 個(gè)檢索目標(biāo)時(shí)的NDCG 均不斷下降，當(dāng)稀疏度為0.40 時(shí)，檢索目標(biāo)1 的NDCG 降至最低，在0.86 左右，檢索目標(biāo)2 的最低NDCG 在0.84 左右，均高于設(shè)置閾值。實(shí)驗(yàn)證明，在不同電子海圖數(shù)據(jù)評(píng)分矩陣稀疏度時(shí)，本文方法檢索電子海圖數(shù)據(jù)的NDCG 值均較高，即電子海圖數(shù)據(jù)相似性檢索精度較高。

圖3 電子海圖數(shù)據(jù)相似性檢索的NDCG 分析結(jié)果Fig.3 NDCG analysis results of similarity retrieval of electronic chart data

3 結(jié) 語(yǔ)

電子海圖數(shù)據(jù)負(fù)責(zé)為船員提供船舶航行過(guò)程中的全部信息，電子海圖數(shù)據(jù)的種類(lèi)較多，導(dǎo)致船員在海量電子海圖數(shù)據(jù)庫(kù)內(nèi)，檢索到其需要的目標(biāo)電子海圖數(shù)據(jù)難度較高。為此，研究推薦算法的船舶電子海圖數(shù)據(jù)相似性檢索方法，為船員提供與其設(shè)置檢索目標(biāo)相似性最高的電子海圖數(shù)據(jù)，提升船舶航行的穩(wěn)定性與安全性。