基于距離度量的實(shí)體識別算法

黎玲利　高宏

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

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