基于词频加权和余弦相似度的模糊匹配算法
2022-04-01崔琪伟
李 彤，崔琪伟，李 夏
（航空工业西安航空计算技术研究所，陕西 西安 710065）
0 引言
电子元器件是武器装备的基础与核心，其研制水平的高低对武器装备发展的影响与日俱增。规范化的元器件数据信息管理以及快捷式的匹配流程等会大大促进国产电子元器件的普及与选用，在保障武器装备国产化需求的同时，也会激发国内元器件厂家自主、高质量研发的热情，形成正循环产业链，有利于促进国内元器件产业的良性发展，故各方都对快速地进行元器件信息匹配、查询等提出了迫切的需求。
但是由于型号元器件数量庞大、来源不一，往往会出于主观性差异、数据录入错误、异源融合[1]等因素导致收集到的元器件数据质量差，直接通过EXCEL进行数据处理效率低下，且当处理的数据量较大时会出现运行崩溃的现象，而传统的基于编辑距离[2]（EditDistance，ED）的模糊匹配方法耗时长，且其基于动态规划计算时使用的矩阵也会增加不少空间复杂度，导致项目进度缓慢。为了解决这一问题，我们基于改进的词频加权和余弦相似度，提出一种模糊匹配算法，该算法首先根据建立的多个数据库，包括元器件厂家规范库、元器件封装库、元器件型号特殊字符库等，快速地对原始元器件数据进行清洗和归一化，接着基于TF-IDF、特征加权、余弦相似度等开展模糊匹配，根据元器件型号信息快速计算出量化的相似度，根据相似度排序，并筛选数据，生成匹配数据表，再人工核查匹配数据表，最终完成元器件信息的匹配、查询和管理等。将该算法与传统的EXCEL工具、编辑距离算法、Jaccard相似度匹配算法[3]以及Sorensen Dice相似度匹配算法等进行实验对比，保证其匹配效率及准确度均最优。
1 相关研究
1.1 编辑距离算法
编辑距离（Minimum Edit Distance，MED），也称莱文斯坦距离（LevenshteinDistance），通常用来度量两个字符串的相似程度，例如在两个序列
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 结论
随着电子元器件产业的蓬勃发展，快速且准确地进行元器件模糊匹配能有效提升各方工作效率，在以往的匹配算法基础上，提出一种基于词频加权和余弦相似度的模糊匹配算法。经多个对比实验验证，算法在准确率和运行时间两个主要方面均有较大改善，提升匹配准确率的同时，缩短运行时间，可用于电子元器件领域型号规格的模糊匹配，有效解决当前电子元器件数量庞大、信息模糊、处理效率低下等问题。
