黎玲利　高宏

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

關(guān)鍵詞：實體識別；相似性測度；距離度量；度量學(xué)習(xí)

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

實體識別即是識別數(shù)據(jù)集中描述同一真實實體的元組，且是數(shù)據(jù)清洗領(lǐng)域的一個重要問題。在很多應(yīng)用中，由于數(shù)據(jù)錯誤，表達不一致等原因，使得在不同數(shù)據(jù)源的指代同一實體的元組在同一屬性上的描述存在不同，常常發(fā)生一些指代相同實體的元組對的相似度很低，而一些指代不同實體的元組對的相似性則很高的情況。如何定義元組之間的相似性測度即是識別實體的關(guān)鍵技術(shù)。傳統(tǒng)的實體識別中，往往是利用字符串相似性函數(shù)來計算元組對在每個屬性值上的相似度，以此來判斷元組對的總體相似性。

在實際應(yīng)用中，由于字符串中詞和詞的相關(guān)性，以及不同詞所表達的實體特征信息的重要性不同，常常存在許多匹配的元組對的相似度很低，而不匹配的元組對的相似度卻很高的情況，故利用傳統(tǒng)的相似性度量函數(shù)很難將匹配元組對和不匹配元組對做到有效的區(qū)分。

為了解決這些問題，相應(yīng)考察后得出如下結(jié)果：

（1） 字符串中詞和詞之間具有相關(guān)性。例如，一個品牌和商品種類往往是相關(guān)的，例如iphone6是apple公司推出的產(chǎn)品，因此iphone6和apple就是相關(guān)的。還有，一些商品描述則決定了其歸屬類型，例如 “quickbooks”是一種軟件，即可知道，“quickbooks”和“software”也是相關(guān)的。因此，對字符串的相似度計算應(yīng)該考慮詞和詞的相似性。

（2） 字符串中不同的詞所具有的重要性并不相同。例如對于一件商品來說，商品號可以用來將該實體和其他所有實體進行明確的區(qū)分；商品的品牌也可以用來區(qū)分與其品牌不同的實體，類似的，商品顏色則可以用來區(qū)別與其顏色不同的實體，而與其相反的描述是，一些常見的詞，例如“in”，“for”卻不能有效地用于識別實體。

研究詞之間的相關(guān)性以及不同詞在實體識別中的重要性可有助于提升實體識別的精確度。而以此為契機，提出了實體識別上以詞作為特征的距離度量。這即引發(fā)了如下課題方向的確立：

（1） 如何避免詞之間的相關(guān)性對元組相似性計算的影響以及如何發(fā)現(xiàn)詞在實體識別中的重要性？

（2） 如何定義適合于元組對上的實體識別和元組集合上的實體識別的距離度量函數(shù)以及如何學(xué)習(xí)度量？

本文旨在解決上述問題，且以詞作為特征，提出了實體識別的度量學(xué)習(xí)算法。本文的后續(xù)內(nèi)容結(jié)構(gòu)安排如下：第1節(jié)提出了基于詞特征的距離度量和度量學(xué)習(xí)的框架；第2節(jié)提出了基于距離度量的實體識別方法；第3節(jié)通過模擬實驗驗證了文中所提算法的有效性；第4節(jié)是相關(guān)工作，最后是總結(jié)。

1 實體識別的度量學(xué)習(xí)算法

在描述算法之前，先給出下列相關(guān)定義。

定義1 實體識別 給定一個元組集合U，實體識別輸出U的一個劃分R，R中在同一類中的元組被判定為指代同一實體，在不同類中的元組被判定為指代不同實體。4 相關(guān)工作

最初，實體識別問題是由文獻[1]首度提出，并由于其重要性，一直以來即吸引了多個領(lǐng)域研究人員的廣泛關(guān)注。文獻[2-3]則是對其早期研究工作的綜述。下面本文將介紹幾種傳統(tǒng)的相似性測度。

首先，基于編輯距離的近似字符串比較函數(shù)使得將一個字符串轉(zhuǎn)化成另一個字符串所需要的編輯操作個數(shù)能夠達到最少[4]。兩個字符串之間的轉(zhuǎn)化所需要的最小操作個數(shù)即可看作兩個字符串的距離。

其次，基于q-gram的近似字符串比較的基本思想是將輸入的兩個字符串利用滑動窗口的方法分解為長度為q的子串，而后計算有多少q-gram出現(xiàn)在兩個輸入字符串中。q-gram也可稱為n-gram[5]。

再次，由Jaro和Winkler所提出的近似字符串比較函數(shù)[6-7]專門用于人名的比較。Jaro比較函數(shù)是將編輯距離和基于q-gram的比較函數(shù)相結(jié)合而獲得實現(xiàn)的。

還有，Monge-Elkan相似性測度[8-9]則是主要用于計算包含多個詞的字符的相似度。這種字符串往往出現(xiàn)在商業(yè)名字，地址或者沒有標(biāo)準化的人名中。該方法的基本思想是首先將由空格符所分隔的詞從兩個輸入的字符串中抽取出來，再利用第二個相似性函數(shù)找到兩個字符串所對應(yīng)的詞集合的最優(yōu)匹配。

最后，Cohen[10]也提出了一個名為WHIRL的系統(tǒng)，通過將信息檢索中的cosine相似性測度和tf.idf權(quán)重模式相結(jié)合來計算兩個字符串的相似度。

5 結(jié)束語

本文首次以詞作為描述實體的特征，針對實體識別問題提出了一種度量學(xué)習(xí)算法。為了保證結(jié)果的有效性，又分別定義了特征向量和樣本距離函數(shù)。實驗驗證了本文所提出的實體識別度量學(xué)習(xí)算法的有效性。

參考文獻：

[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.