基于距離度量的實體識別算法

黎玲利　高宏

摘 要：傳統的實體識別中，往往是利用字符串相似性函數來計算元組對在每個屬性值上的相似度從而來判斷它們總的相似性（例如，元組對的相似性等于每個屬性值上的相似度的加權求和）。然而這一類相似性測度不能夠反映屬性值內部不同的詞在元組對相似性計算中的不同重要性。由于不能區分哪些詞對元組對匹配更重要，就導致仍然存在某些匹配的元組相似性不高，而不匹配的元組相似性高的情況，故很難將匹配元組對和不匹配元組對有效區分開。為了解決這個問題，我們提出了以詞為特征的距離度量函數，設計了基于詞特征的距離度量學習算法，和基于距離度量的實體識別算法。擴展性實驗對我們所提出的算法的有效性進行了驗證。

關鍵詞：實體識別；相似性測度；距離度量；度量學習

中圖分類號：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.