基于詞頻加權和余弦相似度的模糊匹配算法

李 彤，崔琪偉，李 夏

（航空工業西安航空計算技術研究所，陜西 西安 710065）

0 引言

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

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

1 相關研究

1.1 編輯距離算法

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

1.2 Jaccard相似度匹配算法

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

1.3 Sorensen Dice相似度匹配算法

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

1.4 TF-IDF

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

1.5 余弦相似度

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

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

2 基于詞頻加權和余弦相似度的匹配算法

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

2.1 元器件型號數據向量化

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

2.2 元器件型號數據特征及向量加權

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

向量加權：

2.3 數據向量化余弦相似度計算

兩條數據分別為D1、D2，經過詞頻統計后由元器件型號數據轉化為詞頻向量，經過加權后得到基于詞頻加權的向量，它們之間的余弦相似度計為cosθ12。余弦相似度：

3 實驗結果

3.1 實驗環境及數據集

計算機配置：Win11系統、16G內存、i7-12700 CPU、python3.9。實驗數據集選擇進口元器件型號數據，元器件信息均來自互聯網，目前國內外無相關領域的開源數據集。

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

3.2 實驗結果分析

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

表1 各算法匹配結果對比

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

4 結論

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