基于混合相似度度量的跨语言舰船实体匹配算法

孟卓鹏，吴继冰，刘丽华，王 懋，邓 苏，黄宏斌

(国防科技大学 系统工程学院 湖南 长沙 410073)

0 引言

实体匹配作为数据集成的关键任务，目标是寻找同个数据源或多个数据源中指代现实世界中同一事物的实体。但现实中的数据源不可能都使用同一种语言，想要融合这些数据源的信息，必须克服语言的障碍，解决跨语言实体匹配问题。例如，英文维基百科与百度百科的知识融合是很多学者的关注点。

类似的问题在军事领域也存在，指挥员在处置突发事件时，需要了解事件中外军装备的丰富信息来支撑决策，然而外军装备信息往往使用不同语言表示。本文试图解决中英文舰船装备跨语言的实体匹配问题，主要挑战如下。

1) 事件中有关舰船的信息十分有限，仅包括名称、国家和舷号，而且由于信息的敏感性，大部分舰船装备缺乏开源的数据来源，难以形成双语平行语料。

2) 同一舰船装备在不同数据源中由不同的语言描述，处于不同的词空间中，无法直接计算它们之间的相似度。而且不同语言之间的转换不是一一映射的关系，如何确定最好的转换结果也是一个难点。

3) 面对体量较大的数据源时，如果直接遍历所有的实体对，时间复杂度将正比于各数据源元素个数的笛卡尔积，效率较低。

为了应对上述挑战，本文提出了跨语言舰船实体匹配框架，主要贡献如下。

1) 根据军事领域知识归纳出匹配规则，并设计了跨语言舰船实体匹配框架。

2) 利用谷歌翻译API和有道词典短语释义取得语言转换结果，并设计了能够捕捉字符和发音特征的混合相似度度量MixSim。

3) 设计了检测后缀相同字符串的相似度度量suffix-matter，并根据国家和舰船类型生成高质量的候选集，大大降低了复杂度。

1 相关工作

1.1 相似度度量

本文提及的相似度度量均指基于实体字符串信息的相似度度量，其将实体间的相似度映射为[0,1]区间内的一个数值，这个数值越高意味着实体越相似，目前的工作可归纳为三类。

基于序列的相似度度量将字符串看作是字符的序列，计算字符串间转换的代价。编辑距离[1]是最基本的度量方法，Needleman-Wunch度量[2]、AffineGap度量[3]在其基础之上逐渐一般化，能够更好处理字符串中有空格的情况。Jaro度量[4]主要用来比对短字符串，例如人名。Jaro-Winkler度量[4]对Jaro度量进行了改进，解决了两个具有相同前缀、很有可能匹配的字符串在Jaro度量下得分较低的问题。

基于集合的相似度度量将字符串看作词项的集合，并使用集合有关的性质计算相似度得分。主要包括Dice度量[5]、Jaccard度量[5]、TF/IDF度量[6]等方法。

基于向量空间的相似度度量先将字符串转换为维度相同的向量，再计算向量之间的距离。欧氏距离[7]、余弦相似度[5]是经典的度量方法。

以上相似度度量在处理拉丁文字的字符串时，都有不错的效果，但处理中文这种象形文字显得捉襟见肘。陈鸣等[8]将汉字编码为10位的音形码(前4位为音码，后6位为形码)并设计了一种汉字相似度度量。音形码能够捕捉汉字字形和发音上的特征，很好地度量单个字符间的相似度，但还未被应用在中文字符串间的相似度度量。

1.2 实体匹配

实体匹配(实体对齐)旨在发现指代现实中相同实体的数据实例，是数据集成、数据清洗的关键任务，在数据库、人工智能等领域得到了广泛研究[9]。

在数据源的语言不同时，实体匹配面临着跨语言的挑战。现有的方法主要分为两类，一类是基于机器翻译的方法[10-11]，利用机器翻译工具将多种语言转换至一种语言，再应用单语言的实体匹配方法，但是此类方法的效果很大程度上依赖机器翻译的质量。

另一类是基于词向量表示的方法，思路是基于标注的多语言平行语料库，将实体属性信息嵌入至向量空间，构建多语言词向量表示模型[12-14]。除了实体属性信息，很多方法通过融合结构信息[15]或者语义信息[16-17]来提升实体匹配的表现。但是，此类方法依赖于标注的多语言语料以及实体属性信息，或是实体间的关系信息。

本文的研究面向军事领域，缺乏开源的舰船装备数据，指挥员接收的事件情况报告中有关舰船的信息也十分有限，仅有名称、国家、舷号，因此基于词向量表示的算法难以适用。

2 问题定义

定义1舰船实体：数据源中抽取的舰船记录，指代现实世界中的舰船装备。

本研究涉及两个数据源，S1为在互联网上爬取的外军舰船军事活动的新闻报道，作为中文表述的非结构化文本数据源。S2为简氏数据库的战舰年鉴，存储英文表述的结构化舰船实体数据。

从S1中抽取的舰船实体表示为e1={舷号，名称，类型，国家}。如e1i={DDG 56，麦凯恩，驱逐舰，美国}。从S2抽取的舰船实体表示为e2={number,name,type,country}。如e2i={DDG 56,John S McCain, DDGHM,United States}。另外，本文中舰船实体e1i的字段用e1i“字段名称”的形式表示，舰船实体e2j的字段用e2j“fieldname”的形式表示。

定义2舰船实体等价:如果舰船实体e1i和e2j都指向现实世界中相同的舰船装备，则它们是等价的，表示为e1i≐e2j。

问题舰船实体匹配给定数据源S1、S2，分别抽取舰船实体,形成舰船实体集合E1={e11,e12,…,e1n}，E2={e21,e22,…,e2k}。E1为源集合，E2为目标集合，对于∀e1i∈E1，寻找e2j∈E2，使得e1i≐e2j。

3 舰船实体匹配算法框架

根据领域知识,每个国家的舰船舷号是唯一的。舰船命名有明确的结构，为舰船名称+舰船类型的形式，归纳出以下规则并设计舰船实体匹配算法框架，如图1所示。

图1 舰船实体匹配算法Figure 1 Entity matching algorithm for fighting ships

规则1e1i“国家”与e2j“country”指向真实世界中同一个国家∧e1i“舷号”=e2j“number”⟺e1i≐e2j。

规则2a)e1i“国家”与e2j“country”指向现实中同一个国家∧e1i“类型”；b)e2j“type”指向同一舰船类型∧e1i“名称”；c)e2j“name”指代现实中同一舰船装备的名称。若a)、b)、c)同时存在⟺e1i≐e2j。

在执行算法前首先进行数据预处理，形成源集合E1和目标集合E2。通过建立映射表(表1)判断e1i“国家”与e2j“country”是否指向现实世界中同一个国家。将满足要求的e2j纳入e1i的候选集C1中，若不存在e2j∈C1使得e1i“舷号”=e2j“number”，则E2中不存在与e1i等价的实体。

表1 “国家”和“country”映射表Table 1 Mapping table of “国家” and “country”

当e1i“舷号”为空值时，利用规则2来判断。首先基于舰船类型进一步优化候选集，记为C2。在判断e1i“名称”与e2j“name”是否指向同一舰船装备时，将e2j“name”转换为中文，再计算与e1i“名称”的相似度。

为防止机器翻译工具只将单一的翻译结果作为候选项而错过等价实体，融合机器翻译结果和词典短语释义作为转换结果的候选集。

由于e2j与现实中的舰船装备是一一映射，对于∀e1i∈E1，至多存在一个e2j与e1i等价，因此返回相似度Top1的e2j作为匹配结果。且若Top1的相似度为0，则E2中不存在与e1i等价的实体。

4 基于舰船类型优化候选集

首先对e1i“类型”与e2j“type”进行简述。由于不同网站对舰船装备的表述通常存在差别，因此S1中针对同种舰船类型存在不同表述。例如对于补给舰，有“补给舰”、“干货补给舰”、“综合补给舰”等多种表述。S2为关系型数据库，数据质量较高，对舰船类型进行了细致的划分，并将“type”字段进行了编码，表2展示了部分舰船类型的编码。

表2 舰船类型编码表Table 2 Coding for ships′ types

可以看出，S2对舰船类型的表述是精准而规范的，是对舰船细粒度的分类。S1对于舰船类型的表述是简略而不规范的，可以看作是舰船的大类。因此，将e1i“类型”模糊匹配多个e2j“type”，保证不漏掉等价的实体。例如，e1i={-，威廉·P·劳伦斯，导弹驱逐舰，美国}，计算“导弹驱逐舰”与“type”映射结果之间的相似度，模糊匹配到DD(驱逐舰)、DDGM(导弹驱逐舰)、DDGHM(带有直升机的导弹驱逐舰)三个“type”，将C1中满足“type”=DD、DDGM、DDGHM的e2j作为e1i最终候选集C2。

“类型”字段值与“type”映射结果中后缀字符在表达舰船类型含义上起主要作用，前缀字符主要起进一步限定作用。这里，字符串的前缀是指字符串的任意首部，后缀指字符串的任意尾部。例如字符串abc的前缀有a、ab、abc，后缀有c、bc、abc。因此，设计一种便于检测具有相同后缀字符串的度量suffix-matter，计算e1i“类型”与“type”映射结果的相似度。定义为

suffix-matter(x,y)=

(1)

其中：c为字符串x、y公共字符个数；|x|、|y|分别表示x、y的长度；s表示x、y公共后缀的长度。

5 混合相似度度量

舰船的命名方式可以归纳为两种：第一种使用人名或地名，如“伊利湖”号导弹巡洋舰、“柯蒂斯·威尔伯”号导弹驱逐舰。第二种使用表达具体含义的词语，如“调查者号测量船”。在使用机器翻译工具进行语言转换时，也相应带来两个问题。

1) 机器翻译工具在翻译人名和地名时采用音译的方式，很可能e2j“name”转换的结果与e1i“名称”字符相似度很低。例如，已知e1i={-，马斯廷，导弹驱逐舰，美国}与e2j={DDG 89,Mustin,DDGHM, United States}等价，但谷歌翻译将“Mustin”字段翻译为“穆斯丁”，与“马斯廷”相似度较低，但从发音的角度考虑，两者比较相似。

2) 机器翻译工具只返回其认定最恰当的翻译结果，但是这个结果未必会是e1i的名称。这个问题通过融合机器翻译结果和词典短语释义来解决。

综上，采用音译方式得到的“name” 转换结果发音特征更为重要，采用意译方式得到的“name” 转换结果字符特征更为重要。因此设计了混合相似度度量MixSim，主要包括两部分，度量字符相似度的CharSim和度量发音相似度的SoundSim。

5.1 字符相似度度量CharSim

考虑到基于集合的相似度度量在面对具有公共子串的字符串，会给出较高的相似度，且由于前缀或者后缀导致表述不同的情况在舰船名称中普遍存在。因此，CharSim采用Jaccard度量作为基础。同时为应对字符相同而顺序不同的情况，借助N-gram[18]模型将字符串表示为长度为N的短字符串集合。将CharSim定义为

(2)

其中：Bx、By分别表示字符串x和y的2-gram集合。这里需要说明，若N的取值大于字符本身的长度，则相似度取值为0或1，难以捕捉短字符串之间的相似度，而大量舰船装备的名称长度较短，仅为2或3，因此N取2。

5.2 发音相似度度量SoundSim

汉字的发音是通过汉语拼音来实现，想要捕捉中文字符串之间的发音相似度，一个很自然的想法是将汉字的汉语拼音进行编码，将音码间的相似度作为发音的相似度。每个汉字的拼音包括韵母、声母和辅音，图2为汉字“舰”的拼音示例。

图2 汉字拼音示例Figure 2 Example of Chinese Pinyin

这里采用音形码的编码方式来编码汉语拼音。音码第一位是韵母位，汉语拼音中一共有24个韵母，通过简单的替代规则将汉字韵母编码为一个新的字符，如图3所示。这里，ang和an、en和eng、in和ing都采用了同一种编码，因为这些韵母在发音上本身就很相似，且同时也希望弱化音译过程中它们的差异。第二位是声母位，同样进行编码，如图4所示。

图3 韵母编码Figure 3 Coding of Finals

图4 声母编码Figure 4 Coding of Initials

第三位是辅音位，当韵母和声母之间存在辅音时，按照韵母编码表编码；当韵母和声母间不存在辅音时，编码为0。通过以上编码方式可以将每个汉字都转化为三位音码，如“温”的音码为GJ5，“文”的音码也为GJ5。字符串的音码按字符顺序拼接，如“文森号航空母舰”的名称为“文森”，其音码为GJ5GG0。

但是，这样会导致越长的字符串其音码也会越长，不同舰船名称音码之间的字符长度差也会比其本身的字符长度差大很多。基于序列的相似度度量在面对长度差异大的字符串表现较差，因此SoundSim也采用Jaccard度量与N-gram相结合的方式，定义为

(3)

其中：x.scs和y.scs分别表示给定字符串x和y的音码；Bx.scs和By.scs分别表示x.scs和y.scs的3-gram集合。因为单个汉字的音码长度为3，为捕捉到每个汉字的发音特征，这里N取3。

综合考虑CharSim与SoundSim两种度量，采用线性加权的方式融合字符和发音上的特征，将混合相似度度量MixSim定义为

MixSim(x,y)=αCharSim(x,y)+

(1-α)SoundSim(x,y)，

(4)

其中：x、y为给定的字符串；α为特征权重参数，α∈[0,1]。

舰船实体匹配算法伪代码如算法1所示，在基于舰船类型优化候选集和舰船名称匹配两个关键步骤分别应用suffix-matter度量和MixSim度量。

算法1舰船实体匹配算法

输入：新闻报道数据S1，简氏舰船装备数据S2。

输出：等价实体对集合E≐={(e1i,e2j)}，不存在等价实体的集合E≠={e1i}。

1 对S1、S2进行实体抽取形成E1、E2

2 for eache1i∈E1do

3 根据表1生成候选集C1

4 ife1i“舷号”存在

5 for eache2j∈C1do

6 ife2j“number”==

7e1i“舷号” (e1i,e2j)∈E≐

8 end for

9 if不存在e2j∈C1，e2j“number” ==

e1i“舷号”

10e1i∈E≠

11 else

12 计算e1i“类型”与e2j“type”的suffix-matter相似度(公式(1))，生成C2

13 for eache2j∈C2

14 计算e1i“名称”与e2j“name”转换结果的MixSim相似度(公式(4))

15 end for

16 if Top1MixSim相似度==0：

17e1i∈E≠

18 else

19MixSim相似度Top1的e2j满足：

(e1i,e2j)∈E≐

20 end for

根据算法的前10步进行实体匹配，时间复杂度为O(|E1||C1|)，其中|E1|和|C1|分别表示E1和C1中实体个数。若e1i“舷号”不存在，则根据算法的余下步骤进行实体匹配，时间复杂度为O(|E1||C2|)。其中|C2|为C2中实体的个数。因此，舰船实体匹配算法整体的时间复杂度为O(|E1||C1|+|E1||C2|)。

6 实验

6.1 实验环境

CPU：Intel (R) Core (TM) i5-4200M 2.50 GHz。RAM:16 GB。利用Python 3.8进行。

6.2 对比方法

分别从基于序列、集合和向量空间的相似度度量中选取Jaro度量、Jaccard度量、Cosine相似度。

1)Jaro度量常用来比对短字符串，给定字符串x和y，Jaro定义为

字符距离不超过 max(|x|,|y|)/2 ]-1即为位置相近。公共字符为x和y中相同且位置相近的字符。r为公共字符数，公共字符中相同位置但字符不同的字符数为t。

2)Jaccard度量本质上是衡量集合相似度的一种指标，定义为

其中：X和Y分别表示给定字符串x和y的1-gram集合；||表示集合中元素个数。

3)Cosine相似度最初用于计算高维空间中两个向量之间的夹角，定义为

6.3 实验数据

S1为从互联网上爬取的外军舰船军事活动的新闻报道,利用自然语言处理工具NLTK(https:∥github.com/nltk/nltk)进行实体抽取和分词处理，形成源集合E1。

S2为简氏(Jane′s)数据库的战舰年鉴(《Jane′s Fighting Ships》)2017年版。简氏信息集团是当今世界各国公认的军事权威，其数据存储在关系型数据库中，每条记录与现实中的舰船装备一一对应，包括尺寸、速度、航程及武器系统等字段。对其抽取number、name、type及country等字段，形成目标集合E2。具体信息如表3所示。

表3 实验数据统计信息Table 3 Statistical information of experimental data

6.4 评价指标与参数选取

实体匹配常用的评价指标有：精确率、召回率和F值。本文舰船实体匹配算法针对e1i∈E1会返回两种结果，一是与其等价的实体e2j，二是e1i不存在等价实体。

但以上指标未考虑E2中不存在e2j与e1i等价的情况。因此使用正确率(acc)作为评价指标，将E1中舰船实体个数记为|E1|，结果正确的个数记为Na，则acc=Na/|E1|。

算法中需要确定的参数是MixSim中字符特征和发音特征的权重。为获取最佳参数，首先将E1中所有实体的舷号均设为空值，再将α以0.1的步长遍历[0,1]后进行实验，结果如图5所示。

图5 不同参数实验结果Figure 5 Results of different parameters

当α=0时，MixSim=SoundSim，此时MixSim只捕捉了发音特征，正确率是最低的。当α=1时，MixSim=CharSim，此时MixSim只捕捉了字符特征，正确率虽然比α=0时高，但比其余取值时都要低。

此外，随着α的增长，正确率先增后减，在α=0.5时取得最大值。说明将字符特征和发音特征恰当地融合起来，才有较好的度量效果。因此，MixSim取α=0.5。

6.5 对比实验结果

将6.2节介绍的3种度量方法分别应用在算法的第14步，实验结果如表4所示。结果显示MixSim度量有着最高的正确率97.23%，而且即便是Jaccard、Jaro、Cosine这些传统的相似度度量，也可以正确匹配绝大部分等价的舰船实体，这也证明了舰船实体匹配算法的有效性。

表4 不同度量实验结果Table 4 Results of different measures

为进一步检验MixSim度量的有效性，将E1中所有实体的舷号均设为空值进行实验，结果如表5所示。相比于其他相似度度量，MixSim度量的正确率下降的最少，仅有3.60%。说明其对舷号信息的依赖最小，在进行字符串相似度计算时有更好的表现。

表5 去舷号对比实验结果Table 5 Results of contrastive experiment without number

通过列举部分舰船实体的匹配结果，如表6所示，来解释MixSim度量表现更好的原因。传统的相似度度量只考虑了字符特征。因此在面对发音相似，字符差异较大的中文字符串对时，会给出较低的相似度。而MixSim对中文字符串的字符和发音特征都有较强的捕捉能力。在面对“露温(Leeuwin)”、“苏家他(Sujata)”此类采用音译方式转换的舰船名称时，MixSim有着更强的应对能力。

表6 部分舰船实体匹配结果Table 6 Partial results of entity matching for fighting ships

6.6 候选集质量分析

如第4节所述，E2中e2j“type”是根据舰船动力、武器系统等属性划分的更为细致的类型，通过归纳可知，每个国家属于一个大类的“type”不超过3个，因此在寻找e1i“类型”的模糊匹配结果时，返回相似度Top3的“type”。

人工校准实验结果显示，没有出现因为漏掉正确的候选项而造成匹配错误。为进一步验证suffix-matter捕捉字符串后缀特征的能力，将E1中51个舰船类型与E2中109个舰船类型进行模糊匹配。由于E2中属于一个大类的“type”不超过5，因此返回的相似度Top5的“type”作为模糊匹配的结果。

按照表7的方式对结果进行人工标注并检查，加粗字体为与“类型”属于同一舰船类型的“type”。对于给定的51个e1i“类型”，均可以完整得到与其同类型的“type”。

表7 类型相似度Top5结果Table 7 Top5 results of “type” similarity

7 结论

本文面向军事领域的舰船装备数据，针对信息有限、跨语言的特点，提出了一种基于混合相似度度量的跨语言舰船实体匹配算法。针对性地设计了检测字符串后缀的相似度度量suffix-matter与捕捉字符串字形与发音特征的混合相似度度量MixSim。实验结果表明，算法有着较高的正确率与较强的适用性，而且MixSim能够有效应对中文字符串的比对，suffix-matter可以广泛应用于判断具有共同后缀的字符串。

此外，本文舰船实体匹配的跨语言环境为中英文，但是算法不依赖标注好的多语言平行语料，加之MixSim能够有效应对其他语言转换为中文的字符串比对，算法可以适用于中文与其他任何语言的环境。未来将探索更复杂语言环境下的舰船实体匹配任务。