基于相似度的裝備數據聚合方法

楊 杉

(32683部隊,沈陽,110000)

信息融合和信息主導已成為現代戰爭體系作戰能力生成與發揮的重要機理[1],隨著裝備信息化建設的不斷深入,如何將多源異構的裝備數據進行有效的融合集成已經成為不可回避的問題[2]。裝備數據聚合的主要矛盾是異源數據裝備命名不唯一,該問題導致數據匯聚后難以直接使用,后期整編、維護、管理成本巨大,亟需尋找一種行之有效的裝備名稱匹配聚合方法。當前數據聚類、聚合的算法模型眾多,在不同應用中效果迥異[3],但在裝備數據聚合問題上尚無典型的研究案例和行之有效的實施方法。因此,本文針對裝備數據聚合進行研究,根據裝備名稱的特點設計了裝備數據的聚合模型和聚合流程,并嘗試為該模型提供一個適用性較強的相似度計算方法。

1 相關背景及概念

1.1 裝備數據問題分析

“裝備數據”沒有明確的定義,其內涵和外延存在較多解讀,有學者將“裝備數據”定義為“用于描述裝備自身特性和狀態的數據以及裝備全系統全壽命管理活動所涉及的數據的統稱”[4]。裝備數據涵蓋范圍寬泛,包含裝備屬性數據、裝備標準數據、裝備衍生數據、裝備數質量數據等。作為裝備數據的主體,這些數據都含有大量的裝備名稱,由于裝備迭代更新加快、信息系統不相兼容、采集任務標準不一、人工采報內容格式不規范等原因,當前裝備數據中存在大量裝備名稱不一致的情況,這為裝備數據融合帶來了困難,使裝備數據難以形成統一的數據資源。

裝備名稱不一致是指同一裝備因數據來源不同存在多種命名方式的現象,該現象會嚴重影響數據質量,導致融合后數據失準,造成數據分析偏差,甚至影響指揮決策。例如裝備A可能有A1、A2、A3等多個名稱,如果直接歸集使用,A的統計數量會有缺漏,A1等非標準名稱也將無法完成有效的信息關聯,引發后期數據應用結果的混亂。所以在數據融合過程中必須識別出相同型號的裝備并將其聚合。裝備名稱不一致問題產生原因多、發生頻率高,情況也較為復雜,當前主要通過人工整編的方式進行解決,但因數據體量巨大,匹配工作效率低、容易出錯。

1.2 數據聚合及模型選擇

數據聚合的本質是數據匹配和對齊,是判斷隸屬2個不同數據集合中的2個實體是否屬于同一個實體的過程[5]。對裝備數據聚合而言,其核心是對裝備名稱文本數據的聚合,目標是通過匹配對齊,消除數據的不一致性,提升數據的穩定性和準確性。為了有針對性地解決裝備數據的聚合問題,本文對當前的主流方法進行了研究分析。

數據聚合研究因數據時代的到來而備受關注[6-8],當前數據聚合的主流方法可分為3類:

1)基于概率的統計聚合模型。該模型是通過概率和權重的計算實現數據與主題詞的聚合;

2)監督聚合模型。此模型是依托構建的人工神經網絡模型實現數據聚合;

3)無監督聚合模型。該模型針對數據本身進行研究,主要通過文本相似度計算實現信息的聚類。

前2類模型針對的是長文本的數據聚類,主要應用于網絡信息的檢索,重點是對數據的數量和特征進行聚合。裝備數據聚合因裝備名稱較短,難以統計詞頻和提取特征,統計模型和機器學習模型并不適用。故本文首先鎖定無監督聚合模型作為解決方向。

無監督聚合模型又分為“計算字符距離”和“計算語義相似度”2類。前者是將文本數據作為字符序列進行量化分析,利用一些距離來衡量二者的相似度;后者一般需要依賴外部語義詞典進行知識匹配來完成相似度計算[9-10]。裝備的命名主要由阿拉伯數字、英文字母、漢字及少量羅馬字母組成,構成復雜、不易分詞且缺少專用的外部詞典;同時,裝備名稱特征具有稀疏性,容易對語義相似度計算的準確性造成較大的負面影響,所以不建議使用語義相似度進行聚合。綜上所述,本文在無監督聚合模型的基礎上,進一步確定采用基于字符距離計算相似度的方法解決裝備數據聚合問題。

2 裝備數據聚合模型及流程

2.1 裝備數據聚合模型

裝備數據聚合是指依據一定的規則將同一個裝備對象的多個名稱進行匹配對齊,根據匹配結果對待聚合數據集進行整合的過程。假定裝備數據集DB中的2條數據D1和D2,則D1和D2匹配可定義為:

(1)

式中:n為裝備實體名稱;Sim表示2條數據中裝備名稱的聚合相似程度,Sim值越大,n1和n2越相似。可根據聚合要求設定閾值δ,如果Sim>δ,則對2條數據進行聚合處理。

裝備名稱具有規范性,在聚合過程中應向標準名稱看齊,規范的裝備名稱來源于裝備字典,所以如果聚合任務明確了裝備字典DD,可先將DB中的具體裝備名稱ni與DD進行匹配,選取DD中與ni相似度最高的名稱作為匹配成功項,記為ADDi,即Sim(Di,ADDi)=SimMax。因該匹配結果僅取最大值,本文稱其為唯一性匹配。此時聚合的匹配定義由閾值判斷轉化為唯一性判別:

(2)

2.2 裝備數據聚合流程

裝備數據聚合流程因裝備數據種類不同而略有差異,但核心思想一致,本文將裝備數據聚合流程分為3個階段:

Step1裝備名稱的提取和預處理。將裝備名稱從所有需要聚合裝備數據集中全部提取出來,形成文本數據集,再對裝備名稱文本集進行剔重和清洗等預處理,以提升聚合的質量和效率;

Step2裝備名稱的匹配對齊。采用合適的相似度算法對裝備的名稱進行匹配計算,如果有明確裝備字典,應將裝備數據中的名稱嚴格與裝備字典進行唯一性匹配,否則通過設定相似度閾值δ完成匹配對齊;

Step3裝備數據整合。裝備名稱匹配對齊后,首先應按標準統一裝備名稱,使裝備名稱具備唯一性,如果在聚合任務中沒有明確的裝備字典,建議選取信息較為完整的裝備名稱作為聚類后統一的標準。然后根據裝備數據結構確定組合主鍵(一般包含裝備名稱,隸屬部門,裝備狀態等),對數據進行刪除重復項、整合同類數據等操作,進而得到最終聚合后的數據集合。

整個過程如圖1所示。

圖1 裝備數據的聚合流程

分析裝備數據聚合過程可知,其核心任務是對裝備名稱的匹配對齊,所以本文研究的重點是匹配所需的相似度算法。

3 裝備數據聚合相似度算法設計

基于字符距離的相似度算法有較為豐富的研究成果,當前的主流算法有歐氏距離、余弦距離[11]、最小編輯距離[12]、Jaro-Winkler距離[13]等。這些相似度算法各有特點,沒有明顯優劣。其中,最小編輯距離算法、余弦相似度等算法比較適合以分詞為單位的計算,Jaro-Winkler算法更適合以字符為單位的計算[14]。裝備名稱當前缺少專用“詞袋”難以分詞,故Jaro-Winkler算法相對更適用于裝備名稱的相似度計算,但其加強對相同前綴評估的權重不符合裝備名稱的特點需求,因此本文嘗試在該算法的基礎上進行改進。

裝備型號命名一般用字母、數字和文字的組合表示該裝備的基本性能、規格和產品種類。分析裝備數據名稱不一致現象,多數是由品牌、年代、型號、計量單位的不同寫法造成的。雖然這些具體標識不完全一致,但內容本質上是相同的,所構成的裝備名稱文本也分散存在大量共有子域,例如“1954年式7.62毫米手槍”“54式手槍”和“54式7.62 mm手槍”就擁有“54”“7.62”和“手槍”等相同子字符串。據此,本文在Jaro-Winkler的基礎上增加對最長公共子序列的度量,具體算法如下:

首先引入配窗口概念,對于字符串s1和s2,二者之間的匹配窗口記為MW(matching window):

(3)

式中:|s1|和|s2|表示2字符串的長度,當2個相同字符的距離不大于MW時認定該2個字符是匹配的,因此通過MW可過濾掉距離相對較遠的相同字符。過濾后得到新的字符串sn1和sn2,因匹配字符個數相同,將新字符串長度記為m:

m=|sn1|=|sn2|

(4)

此時sn1和sn2具有相同的字符集合,但部分字符位置不同。通過交換字符的方式將sn1轉變為sn2,將交換次數記為ts,則換位數目是發生換位次數的一半,記為t:

(5)

通過m和t可以計算得到Jaro距離dj:

(6)

Winkler在Jaro的基礎上,對算法進行了補充,增加了對2個字符串前綴相同部分的考量,相似度算法改進如下:

dw=dj+(lp(1-dj))

(7)

式中:p為常量,范圍為(0～0.25),根據實際情況進行調整,默認值通常設置為0.1;l為2個字符串的起始部分存在的相同字符個數,即相同最大前綴長度。

定義:對2個字符串A和B在不改變字符順序的基礎上進行字符刪減操作,將得到的長度最長的相同字符序列定義為A和B的最長公共子序列LCS(A,B),序列長度(字符個數)為LLCS,定義A和B公共子序列相似度系數為:

(8)

由LLCS≤Min(|SA|,|SB|)可知PLCS≤1,所以可以用PLCS代替式(7)中的l和p2個變量,將Jaro-Winkler 算法改進得到新的dAB:

dAB=dj+PLCS(1-dj)

(9)

考慮到2個系數疊加后相似度數值較大,比值結果差距較小,為了在應用中更容易設定相似度閾值,對結果進行差異放大處理,得到:

Sim(A,B)=2(dj+PLCS(1-dj))-1

(10)

如果Sim(A,B)<0,則認定A和B不具備匹配條件;如果Sim(A,B)= 1,則認定A和B相同。綜合公式(6)和(10),改進后A和B的相似度計算公式為:

(11)

改進后的算法與Jaro-Winkle算法相比,在規避前綴錯誤度量的同時,增強了對共有部分的評估的權重,更符合裝備名稱特性,理論上可以提高聚合匹配的準確度。

4 實驗結果與分析

為了驗證本文設計的算法在裝備名稱聚合上的匹配效果,實驗分別在典型數據集和較大規模數據集中應用了該算法,并與常用的字符距離相似度算法進行了比對分析。

4.1 典型數據集實驗分析

在單樣本比對實驗中,本文盡量選取有代表性的典型情況進行計算分析。數據集以字典中“1954年式7.62毫米手槍”為基礎進行擴展獲取,在裝備數據聚合過程中常見的裝備名稱不一致的情況有以下3種:

1)年代、口徑、型號等標識簡寫。擴展數據為“①54年式7.62毫米手槍”和“②54年式7.62手槍”;

2)計量單位標準不同。擴展數據為“③1954年式7.62 mm手槍”;

3)缺少部分前后綴標識。擴展數據為“④1954年式手槍”和“⑤7.62毫米手槍”。嚴格意義上缺少前后綴標識的裝備名稱很有可能產生歧義,例如“7.62毫米手槍”可能存在多個年代型號與之匹配,在數據量較大時,為了提升數據質量應修正補全這些數據,在典型數據集中因樣本數量較少,暫不考慮名稱歧義。

以上同一裝備的不同名稱,統稱為該裝備的正例。在裝備名稱匹配過程中,除了正例,裝備數據往往更多的是非同一裝備的名稱反例,為了實現裝備名稱的自動匹配,算法應能夠區分正例和反例,為了全面分析算法,在典型數據集中添加2個與正例相似的反例:“⑥1959年式9毫米手槍”和“⑦1954年式12.7毫米穿甲燃燒彈”,用于測試算法的反向匹配。現將7條數據分別與裝備字典中的對應的標準名稱進行比對,應用本文算法結果如圖2所示。

圖2 不同名稱相似度對比結果

從2個維度對圖2的實驗結果進行分析。維度1是匹配分析,將7個數據樣本分為3組,正例①～⑤為一組,該組數據與正例字典名稱的相似度明顯高于2個反例字典名稱,采用唯一性匹配原則,正例可以匹配到正例字典名稱;同樣⑥和⑦各為一組,與自身對應的字典名稱相似度最高,也能夠完成正確匹配。維度2是正反例區分情況分析,比較7個樣本與正例字典名稱相似度計算結果,正例均高于反例,但反例的相似度與正例⑤和④較為接近,反觀7個樣本與2個反例字典名稱,則明顯能夠進行正反例區分。綜合分析結果,在典型情況的數據樣本中,本文提出的算法可以實現將不一致的裝備名稱匹配到裝備字典中對應的標準名稱,也能夠一定程度區分正反例,但遇到過于簡單的正例和極易混淆的反例(如⑤和⑥),區分界限不明顯。

為了橫向對比本文算法與各主流算法,現采用不同算法對典型情況數據集進行計算,實驗結果如表1所示。

表1 6種相似度算法對比結果

對表1進行分析,因為歐氏距離和余弦距離主要考慮字符出現的頻率,所以這兩個算法對缺少標識的情況較為敏感,正例匹配的相似度范圍大,無裝備字典聚合時相似度閾值設定較為困難,而且二者不考慮字符的位序,簡化的正例和相近的反例相似度接近,容易錯誤匹配;最小編輯距離算法對字符串的長度和位序都較為敏感,正向匹配較為困難,甚至出現反例⑥的相似度高于正例⑤的相似度,也不符合裝備名稱聚合要求;Jaro相似度相比前3個算法較穩定,但對連續相同字符不敏感導致正例相似度區間偏大,Jaro-Winkle過于看重相同前綴導致⑦高于⑤,也不適用與裝備名稱的聚合;綜合比較,在典型數據集中本文算法較其他算法更為穩定,匹配準確率相對較高。

4.2 較大規模數據集算法對比分析

為了驗證本文算法的匹配準確率和魯棒性,將算法應用于較大規模的裝備數據集,數據集約30 000條裝備數據,提取裝備名稱實例1 221個。為了對算法的有效性進行分析,將匹配結果進行二元分類,建立混淆矩陣:

True Positive(真正,TP):同一裝備且名稱符合匹配;

True Negative(真負,TN):不是同一裝備且不符合匹配;

False Positive(假正,FP):不是同一裝備但符合匹配;

False Negative(假負,FN):是同一裝備但不符合匹配。

通過混淆矩陣可以得到算法的準確率ACC:

(12)

算法的精確率P和召回率R分別為:

(13)

其中精確率和召回率是2個不同角度對算法的分析,理想情況下,P和R同時越高越好,但現實情況中,準確率與召回率往往呈反比,根據裝備聚合的要求應保證盡量不錯漏正例,實驗的閾值確定原則為在保證召回率的前提下精確率最大化。同時為了全面分析算法的有效性,實驗中引用更為綜合的評價指標F-Measure[15],其定義為:

(14)

下面,針對裝備數據集中的裝備名稱實例分別采用Jaro-Winkle、最小編輯距離、余弦距離等相似度算法和本文算法進行計算,得到的準確率、精確率、召回率和F1(β=1)結果如圖3所示。

圖3 4種算法評價指標綜合對比

1)4種算法的ACC值較為接近,主要原因是數據集中的反例遠多于正例,所以ACC值參考意義不大;

2)各算法的P值都相對較低,表明符合匹配條件的反例較多,分析主要原因是部分裝備名稱相似度極高,橫向比較,本文算法的TP和FP相對較少;

3)通過對結果的綜合比較分析,本文算法的精確率、召回率、F1值相較其它3種算法都有較好的表現。

對匹配成功和失敗的數據樣本進一步觀察,可以總結出3點規律:一是裝備名稱包含的前后綴標識越多,本文算法的準確率越高,相較其它算法優勢越明顯;二是算法的有效性與數據質量有較大關聯性,裝備名稱過于簡單或存在歧義的數據樣本無論在那種算法中都難以匹配成功;三是文中的所有基于字符的相似度算法都是純文本分析,難以剔除極度相似的裝備名稱反例。

5 結語

本文在分析當前的主流的文本聚合算法的基礎上,針對裝備數據的特點,構建了裝備數據的聚合模型并提供了相應的相似度算法,經過實驗分析,該算法對裝備數據適配性較高,能夠一定程度上解決裝備名稱不一致帶來的數據聚合難題,但如果想從源頭上消除裝備名稱不一致現象仍需要在系統研發、數據采報等各個環節的工作中嚴格落實制度標準,確保裝備字典的統一。本文是對裝備數據聚合工作的初步探索,在未來的工作中可在以下2個方面做進一步研究:針對裝備名稱命名規范進行分析,尋求合適的分詞方法以進一步提升聚合效率;構建專用的外部詞典,嘗試將字符距離相似度計算與語義相似計算相結合,以剔除極度相似的反例,進一步提升匹配的精確率。