基于詞頻加權(quán)和余弦相似度的模糊匹配算法

李 彤，崔琪偉，李 夏

（航空工業(yè)西安航空計算技術(shù)研究所，陜西 西安 710065）

0 引言

電子元器件是武器裝備的基礎(chǔ)與核心，其研制水平的高低對武器裝備發(fā)展的影響與日俱增。規(guī)范化的元器件數(shù)據(jù)信息管理以及快捷式的匹配流程等會大大促進國產(chǎn)電子元器件的普及與選用，在保障武器裝備國產(chǎn)化需求的同時，也會激發(fā)國內(nèi)元器件廠家自主、高質(zhì)量研發(fā)的熱情，形成正循環(huán)產(chǎn)業(yè)鏈，有利于促進國內(nèi)元器件產(chǎn)業(yè)的良性發(fā)展，故各方都對快速地進行元器件信息匹配、查詢等提出了迫切的需求。

但是由于型號元器件數(shù)量龐大、來源不一，往往會出于主觀性差異、數(shù)據(jù)錄入錯誤、異源融合[1]等因素導(dǎo)致收集到的元器件數(shù)據(jù)質(zhì)量差，直接通過EXCEL進行數(shù)據(jù)處理效率低下，且當處理的數(shù)據(jù)量較大時會出現(xiàn)運行崩潰的現(xiàn)象，而傳統(tǒng)的基于編輯距離[2]（EditDistance，ED）的模糊匹配方法耗時長，且其基于動態(tài)規(guī)劃計算時使用的矩陣也會增加不少空間復(fù)雜度，導(dǎo)致項目進度緩慢。為了解決這一問題，我們基于改進的詞頻加權(quán)和余弦相似度，提出一種模糊匹配算法，該算法首先根據(jù)建立的多個數(shù)據(jù)庫，包括元器件廠家規(guī)范庫、元器件封裝庫、元器件型號特殊字符庫等，快速地對原始元器件數(shù)據(jù)進行清洗和歸一化，接著基于TF-IDF、特征加權(quán)、余弦相似度等開展模糊匹配，根據(jù)元器件型號信息快速計算出量化的相似度，根據(jù)相似度排序，并篩選數(shù)據(jù)，生成匹配數(shù)據(jù)表，再人工核查匹配數(shù)據(jù)表，最終完成元器件信息的匹配、查詢和管理等。將該算法與傳統(tǒng)的EXCEL工具、編輯距離算法、Jaccard相似度匹配算法[3]以及Sorensen Dice相似度匹配算法等進行實驗對比，保證其匹配效率及準確度均最優(yōu)。

1 相關(guān)研究

1.1 編輯距離算法

編輯距離（Minimum Edit Distance，MED），也稱萊文斯坦距離（LevenshteinDistance），通常用來度量兩個字符串的相似程度，例如在兩個序列之間，編輯距離即為序列w1轉(zhuǎn)換為另一個序列w2所需要的最少的單字符操作次數(shù)，該操作有且僅有3種：插入、刪除和替換。

1.2 Jaccard相似度匹配算法

Jaccard相似度主要用于衡量兩個集合的相似程度，其定義為給定兩個集合A、B，其Jaccard系數(shù)為集合A、B交集大小與并集大小的比值。Jaccard系數(shù)取值區(qū)間為[0，1]，Jaccard系數(shù)值越大，則認為兩集合相似度越高，但該方法的缺點是其受數(shù)據(jù)規(guī)模的影響較大。

1.3 Sorensen Dice相似度匹配算法

與Jaccard類似，Sorensen Dice系數(shù)也是一種簡單集合之間相似度的計算方法，也可用來衡量字符串間的相似性，但其計算方式與Jaccard系數(shù)略有不同，Sorensen Dice系數(shù)是兩個集合交集的2倍除以兩集合相加，而非并集，其取值范圍為[0，1]。同樣，Sorensen Dice系數(shù)值越大，認為兩集合相似度越高。相較于Jaccard系數(shù)，該方法更為直觀展示了字符串間的重疊百分比，但其也受數(shù)據(jù)集規(guī)模的影響較大。

1.4 TF-IDF

TF-IDF（Term Frequency-Inverse Document Frequency，詞頻-逆文件頻率），是一種常用的文本特征選擇方式，常用于信息檢索與文本挖掘的加權(quán)。其中，TF（Term Frequency）表示關(guān)鍵詞在文章中出現(xiàn)的頻率，該關(guān)鍵詞在文章中出現(xiàn)的次數(shù)越多，則越重要；IDF（Inverse Document Frequency）表示逆文件頻率，意味著該關(guān)鍵詞在文檔集中出現(xiàn)越頻繁，對于文檔的區(qū)分能力就越小，其重要性隨之下降。Gu Y H等[4]提出，當前對文本中關(guān)鍵詞的權(quán)值計算主要采用TF-IDF方法。周麗杰等[5]認為，TF-IDF值是NLP（Natural Language Processing，自然語言處理）中普遍應(yīng)用的關(guān)鍵詞權(quán)重計算方法。其主要思想是，文本的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在語料庫中出現(xiàn)的頻率成反比下降。即如果一個詞語在某篇文章中出現(xiàn)的頻率TF較高，且在其他文章中很少出現(xiàn)，則認為該詞語具有很好的類別區(qū)分能力。

1.5 余弦相似度

余弦相似度（cosinesimilarity），又稱余弦相似性，是通過計算兩個向量的夾角余弦值來評估他們的相似度，其只與向量的方向有關(guān)，與其幅值無關(guān)。一個向量空間中兩個向量夾角間的余弦值越接近1，表明這兩個向量越相似。在度量一對文本的相似度時，將文本矢量化后，就可將兩個向量夾角的余弦值作為兩個文本的相似度評估標準。

陳仕鴻等[6]指出，計算兩個文本余弦相似度的方法分為四個步驟：文本分詞、刪去停用詞、文本矢量化、計算余弦相似度。同時，李鯤程等[7]指出，根據(jù)TF-IDF的原理，一個單詞出現(xiàn)的頻率越高，說明這個單詞就越重要，因此生成文本矢量時，可以用詞頻來代替該文本矢量每個維度的值。當兩個文本長度差距很大，但內(nèi)容相近時，如果使用詞頻或詞向量作為特征，它們在特征空間的歐式距離可能會很大，但是其向量夾角可能會相對較小，因而余弦相似度較高。此外，相較于歐氏距離易受特征向量維度影響的特性，余弦相似度在特征維度較高時取值仍保持[-1，1]，較為穩(wěn)定。

2 基于詞頻加權(quán)和余弦相似度的匹配算法

元器件型號數(shù)據(jù)有很強的規(guī)范性，其大多是以字母加數(shù)字組合構(gòu)建而成，與傳統(tǒng)的編輯距離方法、Jaccard相似度匹配算法、Sorensen Dice相似度匹配算法等不同，我們針對這種規(guī)范性較強的數(shù)據(jù)，提出基于詞頻加權(quán)和余弦相似度的模糊匹配算法，其核心思想是通過TF-IDF的詞頻分析，將元器件型號數(shù)據(jù)映射到固定特征的一維向量中，同時根據(jù)元器件型號數(shù)據(jù)的長度和字符特征對該向量進行加權(quán)，最后通過余弦相似度進行相似度計算，返回相似度值最大的向量所對應(yīng)的元器件型號數(shù)據(jù)。

2.1 元器件型號數(shù)據(jù)向量化

元器件型號數(shù)據(jù)是一類規(guī)范性較強的數(shù)據(jù)，通常以字母和數(shù)字組合的方式構(gòu)成，當然很多元器件型號數(shù)據(jù)會添加很多額外信息，例如封裝、元器件類型、質(zhì)量等級、顏色等，所以需要對元器件型號進行預(yù)處理，刪除不需要參與匹配的冗余信息。根據(jù)TF-IDF算法思想，對元器件型號數(shù)據(jù)進行“詞頻”統(tǒng)計，詞頻是一個相對概念，對于元器件型號數(shù)據(jù)而言，字符之間并沒有強相關(guān)含義聯(lián)系，所以可以將每個字符看作一個詞進行詞頻統(tǒng)計，且元器件型號數(shù)據(jù)的長度不統(tǒng)一，導(dǎo)致向量空間不統(tǒng)一，詞頻統(tǒng)計結(jié)果不能作為輸入直接運算，為了將所有元器件型號數(shù)據(jù)統(tǒng)一到同一個向量空間中，同時為了方便計算，設(shè)計固定的映射關(guān)系，可將所有型號數(shù)據(jù)映射到統(tǒng)一的向量空間。且以經(jīng)驗看來，當兩個元器件型號規(guī)格的字符串長度相差較大時，極大概率不是同一個元器件，故將元器件型號長度作為文本向量的第一維。向量空間如下：

2.2 元器件型號數(shù)據(jù)特征及向量加權(quán)

元器件型號數(shù)據(jù)的詞頻分析，不僅對于型號數(shù)據(jù)的位置信息敏感，同時其對字符間的相對順序是敏感的，相同的詞頻向量對應(yīng)的原始元器件型號數(shù)據(jù)可能截然不同，具體的表現(xiàn)為某兩個型號例如為“GHYHY27395”“GHYYH27395”在詞頻角度去看這兩個數(shù)據(jù)的向量是相同的，但卻是兩種完全不同的元器件，所以針對這種情況，提出對基于詞頻統(tǒng)計的元器件型號數(shù)據(jù)向量進行加權(quán)，權(quán)重與元器件型號數(shù)據(jù)字符的位置相關(guān)，位置越靠前的字符，其權(quán)重越高。到了一定位置后，后續(xù)的字符不需要再加權(quán)，這一點是由元器件型號數(shù)據(jù)的屬性帶來的。元器件型號靠前部分的數(shù)據(jù)通常表示該元器件的系列、種類等，靠后的部分通常代表元器件數(shù)據(jù)的細節(jié)信息，例如內(nèi)存大小，管腳數(shù)量等，所以在元器件前端部分相同的情況下，代表著兩種元器件屬于一個系列，核心功能等方面大致相同，故只需要給元器件型號數(shù)據(jù)位置靠前的部分進行加權(quán)即可。權(quán)重向量如下：

向量加權(quán)：

2.3 數(shù)據(jù)向量化余弦相似度計算

兩條數(shù)據(jù)分別為D1、D2，經(jīng)過詞頻統(tǒng)計后由元器件型號數(shù)據(jù)轉(zhuǎn)化為詞頻向量，經(jīng)過加權(quán)后得到基于詞頻加權(quán)的向量，它們之間的余弦相似度計為cosθ12。余弦相似度：

3 實驗結(jié)果

3.1 實驗環(huán)境及數(shù)據(jù)集

計算機配置：Win11系統(tǒng)、16G內(nèi)存、i7-12700 CPU、python3.9。實驗數(shù)據(jù)集選擇進口元器件型號數(shù)據(jù)，元器件信息均來自互聯(lián)網(wǎng)，目前國內(nèi)外無相關(guān)領(lǐng)域的開源數(shù)據(jù)集。

實驗內(nèi)容主要是對基于詞頻分析和余弦相似度的模糊匹配算法與EXCEL工具、編輯距離算法、Jaccard相似度匹配算法、Sorensen Dice相似度匹配算法就匹配準確度和運行效率進行對比分析，選擇3 000條數(shù)據(jù)作為原始數(shù)據(jù)，3000條數(shù)據(jù)作為知識庫數(shù)據(jù)進行匹配。

3.2 實驗結(jié)果分析

在同樣的數(shù)據(jù)集中，通過多種匹配算法計算得到結(jié)果比對見表1。

表1 各算法匹配結(jié)果對比

從表1可以看出在同樣的數(shù)據(jù)集下基于詞頻加權(quán)和余弦相似度的模糊匹配算法在準確率和運行時間方面明顯優(yōu)于其他方法。傳統(tǒng)的EXCEL工具無論是在準確率還是運行時間方面均不占優(yōu)勢，且其在處理海量數(shù)據(jù)時，往往會因為計算量過大出現(xiàn)“卡死”現(xiàn)象，大大影響了工作效率；而單純用余弦相似度的方法由于忽略了字符的位置加權(quán)信息，準確率有一定幅度地降低；基于動態(tài)規(guī)劃的匹配算法如編輯距離等由于時間復(fù)雜度過高，當數(shù)據(jù)量較大時，運行時間會較長，同時匹配準確率也會下降；而利用“交集”除以“并集”思想的Jaccard算法和Sorensen Dice算法在處理特定任務(wù)時可以在低時間復(fù)雜度的前提下做到匹配準確率較高，但是由于元器件型號規(guī)格數(shù)據(jù)寫法多樣，不能進行去重操作，當數(shù)據(jù)量較大時，這兩種方法的匹配準確率會顯著降低。而提出的基于詞頻加權(quán)和余弦相似度的模糊匹配算法充分考慮到電子元器件型號規(guī)格的組成特點及字符特性，對詞頻向量進行加權(quán)，再計算待匹配向量和庫向量間的余弦相似度，大大提高了匹配準確率。而且該算法在對數(shù)據(jù)庫進行一次計算后就將其向量存儲起來，后續(xù)匹配時可直接將待匹配向量與存儲起來的庫向量進行匹配，提高工作效率。

4 結(jié)論

隨著電子元器件產(chǎn)業(yè)的蓬勃發(fā)展，快速且準確地進行元器件模糊匹配能有效提升各方工作效率，在以往的匹配算法基礎(chǔ)上，提出一種基于詞頻加權(quán)和余弦相似度的模糊匹配算法。經(jīng)多個對比實驗驗證，算法在準確率和運行時間兩個主要方面均有較大改善，提升匹配準確率的同時，縮短運行時間，可用于電子元器件領(lǐng)域型號規(guī)格的模糊匹配，有效解決當前電子元器件數(shù)量龐大、信息模糊、處理效率低下等問題。