基于距离度量的实体识别算法

黎玲利　高宏

摘 要：传统的实体识别中，往往是利用字符串相似性函数来计算元组对在每个属性值上的相似度从而来判断它们总的相似性（例如，元组对的相似性等于每个属性值上的相似度的加权求和）。然而这一类相似性测度不能够反映属性值内部不同的词在元组对相似性计算中的不同重要性。由于不能区分哪些词对元组对匹配更重要，就导致仍然存在某些匹配的元组相似性不高，而不匹配的元组相似性高的情况，故很难将匹配元组对和不匹配元组对有效区分开。为了解决这个问题，我们提出了以词为特征的距离度量函数，设计了基于词特征的距离度量学习算法，和基于距离度量的实体识别算法。扩展性实验对我们所提出的算法的有效性进行了验证。

关键词：实体识别；相似性测度；距离度量；度量学习

中图分类号：TP704.25

Abstract： Traditional entity resolution methods always use string-based similarity functions to compute the similarities of attribute-values between records and then compute the similarity between records based on these similarities， i.e.， the similarity between records is the weighted sum of the similarities of all the attribute-values. However， these metrics cannot represent the importance of each word in attribute-values. Since they cannot distinguish which word is more important for record matching， there might be some matching records have low similarities while some non-matching records have high similarities. Therefore it is difficult to distinguish the matchings and the non-matchings effectively. To address this problem， the paper presents a distance metric based on word-feature， and proposes a distance metric learning algorithm and an entity resolution method based on the metric. Extensive experiments have verified the effectiveness of the proposed algorithms.

Keywords： Entity Resolution； Similarity Metrics； Distance Metric； Metric Learning

0 引 言

实体识别即是识别数据集中描述同一真实实体的元组，且是数据清洗领域的一个重要问题。在很多应用中，由于数据错误，表达不一致等原因，使得在不同数据源的指代同一实体的元组在同一属性上的描述存在不同，常常发生一些指代相同实体的元组对的相似度很低，而一些指代不同实体的元组对的相似性则很高的情况。如何定义元组之间的相似性测度即是识别实体的关键技术。传统的实体识别中，往往是利用字符串相似性函数来计算元组对在每个属性值上的相似度，以此来判断元组对的总体相似性。

在实际应用中，由于字符串中词和词的相关性，以及不同词所表达的实体特征信息的重要性不同，常常存在许多匹配的元组对的相似度很低，而不匹配的元组对的相似度却很高的情况，故利用传统的相似性度量函数很难将匹配元组对和不匹配元组对做到有效的区分。

为了解决这些问题，相应考察后得出如下结果：

（1） 字符串中词和词之间具有相关性。例如，一个品牌和商品种类往往是相关的，例如iphone6是apple公司推出的产品，因此iphone6和apple就是相关的。还有，一些商品描述则决定了其归属类型，例如 “quickbooks”是一种软件，即可知道，“quickbooks”和“software”也是相关的。因此，对字符串的相似度计算应该考虑词和词的相似性。

（2） 字符串中不同的词所具有的重要性并不相同。例如对于一件商品来说，商品号可以用来将该实体和其他所有实体进行明确的区分；商品的品牌也可以用来区分与其品牌不同的实体，类似的，商品颜色则可以用来区别与其颜色不同的实体，而与其相反的描述是，一些常见的词，例如“in”，“for”却不能有效地用于识别实体。

研究词之间的相关性以及不同词在实体识别中的重要性可有助于提升实体识别的精确度。而以此为契机，提出了实体识别上以词作为特征的距离度量。这即引发了如下课题方向的确立：

（1） 如何避免词之间的相关性对元组相似性计算的影响以及如何发现词在实体识别中的重要性？

（2） 如何定义适合于元组对上的实体识别和元组集合上的实体识别的距离度量函数以及如何学习度量？

本文旨在解决上述问题，且以词作为特征，提出了实体识别的度量学习算法。本文的后续内容结构安排如下：第1节提出了基于词特征的距离度量和度量学习的框架；第2节提出了基于距离度量的实体识别方法；第3节通过模拟实验验证了文中所提算法的有效性；第4节是相关工作，最后是总结。

1 实体识别的度量学习算法

在描述算法之前，先给出下列相关定义。

定义1 实体识别 给定一个元组集合U，实体识别输出U的一个划分R，R中在同一类中的元组被判定为指代同一实体，在不同类中的元组被判定为指代不同实体。4 相关工作

最初，实体识别问题是由文献[1]首度提出，并由于其重要性，一直以来即吸引了多个领域研究人员的广泛关注。文献[2-3]则是对其早期研究工作的综述。下面本文将介绍几种传统的相似性测度。

首先，基于编辑距离的近似字符串比较函数使得将一个字符串转化成另一个字符串所需要的编辑操作个数能够达到最少[4]。两个字符串之间的转化所需要的最小操作个数即可看作两个字符串的距离。

其次，基于q-gram的近似字符串比较的基本思想是将输入的两个字符串利用滑动窗口的方法分解为长度为q的子串，而后计算有多少q-gram出现在两个输入字符串中。q-gram也可称为n-gram[5]。

再次，由Jaro和Winkler所提出的近似字符串比较函数[6-7]专门用于人名的比较。Jaro比较函数是将编辑距离和基于q-gram的比较函数相结合而获得实现的。

还有，Monge-Elkan相似性测度[8-9]则是主要用于计算包含多个词的字符的相似度。这种字符串往往出现在商业名字，地址或者没有标准化的人名中。该方法的基本思想是首先将由空格符所分隔的词从两个输入的字符串中抽取出来，再利用第二个相似性函数找到两个字符串所对应的词集合的最优匹配。

最后，Cohen[10]也提出了一个名为WHIRL的系统，通过将信息检索中的cosine相似性测度和tf.idf权重模式相结合来计算两个字符串的相似度。

5 结束语

本文首次以词作为描述实体的特征，针对实体识别问题提出了一种度量学习算法。为了保证结果的有效性，又分别定义了特征向量和样本距离函数。实验验证了本文所提出的实体识别度量学习算法的有效性。

参考文献：

[1] H. Newcombe， J. Kennedy， S. Axford， et al. Automatic Linkage of Vital Records[M]. 1959.

[2] ELMAGARMID A K， IPEROTIS P G， VERYKIOS V S. Duplicate record detection： A survey[J]. Knowledge and Data Engineering， IEEE Transactions on， 2007， 19（1）： 1-16.

[3] KOUDAS N ， SARAWAGI S， SRIVASTAVA D. Record linkage： Similarity measures and algorithms[C]//Proceedings of the 2006 ACM SIGMOD international conference on Management of data. 2006：802–803.

[4] NAVARRO G. A guided tour to approximate String Matching[J]. ACM computing surveys （CSUR）， 2001， 33（1）：31–88.

[5] KUKICH K. Techniques for Automatically Correcting Words in Text[J]. ACM Computing Surveys， 1992， 24（4）：377-439.

[6] JARO M A. Advances in record-linkage methodology as applied to matching the 1985 Census of Tampa， Florida[J]. Journal of the American Statistical Association， 1989， 84（406）：414–420.

[7] WINKLER W E. String Comparator Metrics and Enhanced Decision Rules in the Fellegi-sunter Model of Record Linkage.[J]. 1990.

[8] MONGE A E， ELKAN C， et al. The field matching problem： algorithms and applications[C]//KDD， 1996：267–270.

[9] MOREAU E， YVON F， CAPPE O. Robust similarity measures for Named Entities Matching[C]//Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1. 2008：593–600.

[10] COHEN W W. Integration of heterogeneous databases without Common Domains using queries based on textual similarity[C]//ACM SIGMOD Record， 1998， 27：201–212.