蔣存鋒，趙川

（1.上海計(jì)算機(jī)軟件技術(shù)開(kāi)發(fā)中心，上海 200000；2.Teradata Corporation，圣地亞哥，美國(guó)）

0 引言

排序是計(jì)算機(jī)程序設(shè)計(jì)中一項(xiàng)基本的操作，在實(shí)際應(yīng)用中，有很多情況下需要對(duì)數(shù)據(jù)按照某種方式進(jìn)行排序后才能達(dá)到某種要求，因此，學(xué)習(xí)和研究各種排序方法是計(jì)算機(jī)工作者的重要課題之一。

實(shí)體識(shí)別也稱(chēng)為重復(fù)記錄去除、身份識(shí)別、對(duì)象識(shí)別、引用識(shí)別、記錄連接、混合-清除、數(shù)據(jù)關(guān)聯(lián)等。

實(shí)體是由屬性來(lái)描述的，屬性的值構(gòu)成了某個(gè)特定實(shí)體的信息。例如，一個(gè)人有諸如姓名、生日、指紋等屬性。因?yàn)閷?shí)體是真實(shí)世界的實(shí)體，所以屬性值的集合是獨(dú)一無(wú)二和真實(shí)存在的。我們可能知道一個(gè)實(shí)體的真實(shí)屬性值，也可能不知道。我們只有實(shí)體的引用，也就是實(shí)體屬性值的一個(gè)集合。對(duì)于某一個(gè)特定實(shí)體，我們可能有多個(gè)引用，每一個(gè)引用都有不同的屬性值集合。因?yàn)檫@些集合看上去不同，所以我們需要確定他們是否對(duì)應(yīng)的是同一個(gè)真實(shí)世界實(shí)體。從一個(gè)比較窄的意義上來(lái)說(shuō)，這也就是實(shí)體識(shí)別要做的事情。在更廣泛的意義上，實(shí)體識(shí)別還牽涉到更多的工作。有的數(shù)據(jù)也許是沒(méi)有結(jié)構(gòu)的，也沒(méi)有明顯的實(shí)體引用（屬性值集合）?；蛘哂袑?shí)體引用，但是缺乏統(tǒng)一的格式。Talburt[1]列出了實(shí)體識(shí)別在一個(gè)廣泛意義上所涉及的五個(gè)主要的工作：

●實(shí)體引用抽?。簭臒o(wú)結(jié)構(gòu)信息中定位和收集實(shí)體引用；

●實(shí)體引用準(zhǔn)備：在識(shí)別之前，對(duì)結(jié)構(gòu)化的實(shí)體引用施加標(biāo)準(zhǔn)化、數(shù)據(jù)清洗等技術(shù)；

●實(shí)體引用識(shí)別：確定引用是否對(duì)應(yīng)同一個(gè)實(shí)體；

●實(shí)體身份管理：建立和維護(hù)一個(gè)長(zhǎng)久的實(shí)體身份信息記錄；

●實(shí)體關(guān)系分析：開(kāi)拓不同的但是相關(guān)的實(shí)體之間的關(guān)聯(lián)網(wǎng)絡(luò)。

我們的研究工作主要涉及的是實(shí)體引用的準(zhǔn)備和識(shí)別。實(shí)驗(yàn)所使用的數(shù)據(jù)源是文本格式，并含有明顯的實(shí)體屬性和值，所以不需要進(jìn)行實(shí)體引用抽取的工作。不過(guò)我們做了一些實(shí)體引用的準(zhǔn)備工作來(lái)提高數(shù)據(jù)質(zhì)量，以便更好地比較它們。

1 方法概述

1.1 常用方法

一般地，進(jìn)行實(shí)體識(shí)別的技術(shù)需要在記錄對(duì)之間建立良好的匹配標(biāo)準(zhǔn)，這樣實(shí)體識(shí)別也可以看作是分類(lèi)問(wèn)題：對(duì)于兩個(gè)記錄的每一對(duì)對(duì)應(yīng)的屬性值之間的相似值構(gòu)成的一個(gè)向量，把它歸類(lèi)為“匹配（副本）”或者“不匹配（非副本）”。匹配標(biāo)準(zhǔn)可能涉及到一個(gè)度量標(biāo)準(zhǔn)和一個(gè)用戶(hù)定義的臨界值，用來(lái)確定區(qū)分匹配記錄和不匹配記錄的點(diǎn)。根據(jù)一些通常的定義[2]，匹配標(biāo)準(zhǔn)返回三個(gè)不同的值：匹配、不匹配、需要進(jìn)一步檢查。Brizan和Tansel[3]對(duì)不同的匹配技術(shù)做了一個(gè)簡(jiǎn)潔的描述。Elmagarmid等人[4]總結(jié)了檢測(cè)不相同但是等價(jià)的數(shù)據(jù)庫(kù)記錄的技術(shù)。

實(shí)體識(shí)別系統(tǒng)一般使用四種基本的技術(shù)來(lái)確定是否兩個(gè)引用是等價(jià)，或者稱(chēng)為對(duì)應(yīng)同一個(gè)真實(shí)實(shí)體。它們是直接匹配、傳遞等價(jià)、關(guān)聯(lián)分析、斷言等價(jià)[2]。在我們改進(jìn)的實(shí)體識(shí)別框架中我們使用了所有的四種技術(shù)。

傳統(tǒng)的實(shí)體識(shí)別方法經(jīng)常使用數(shù)據(jù)屬性值之間的文本相似性。一些比較新的方法則考慮由數(shù)據(jù)上下文導(dǎo)出的關(guān)系相似性作為附加的信息，還有一些方法是基于概率模型的。匹配含有多個(gè)屬性的記錄方法大致可以分為兩類(lèi)。一類(lèi)是依靠學(xué)習(xí)數(shù)據(jù)來(lái)“學(xué)習(xí)”如何匹配數(shù)據(jù)，這一類(lèi)方法通常使用概率的方法以及監(jiān)督的機(jī)器學(xué)習(xí)技術(shù)。另一類(lèi)方法依靠領(lǐng)域知識(shí)或者屬性距離度量標(biāo)準(zhǔn)來(lái)匹配記錄。

1.2 改進(jìn)的方法

通過(guò)研究，我們結(jié)合兩種匹配方法中有用的部分，并進(jìn)行改進(jìn)，得到一種更為有效的匹配方法[5]。該方法提出了一個(gè)既使用直接相似度又使用間接相似度的結(jié)構(gòu)化的相似度度量標(biāo)準(zhǔn)，并對(duì)非監(jiān)督學(xué)習(xí)使用一個(gè)簡(jiǎn)單的相似度模型，對(duì)監(jiān)督學(xué)習(xí)則提供了一個(gè)概率的分類(lèi)模型以及估算概率的方法。此外該方法提供了簡(jiǎn)單的更新算法來(lái)消除分類(lèi)匹配結(jié)果中的不一致性。

我們沿用了相似度度量和概率模型，并在此基礎(chǔ)上做了較大的改進(jìn)。不但進(jìn)行實(shí)體的識(shí)別，還兼顧到對(duì)象的合并。增加了數(shù)據(jù)預(yù)處理（pre-processing）的步驟，在其中設(shè)計(jì)了一種數(shù)據(jù)過(guò)濾策略。同時(shí)，還大大增強(qiáng)了后期處理過(guò)程（post-processing），設(shè)計(jì)了幾種不一致性消除的方法以及兩個(gè)有效的記錄更新算法。這些步驟都大大改進(jìn)了計(jì)算效率和分類(lèi)結(jié)果。另外，記錄更新算法還有兩個(gè)功能：一個(gè)是找到“正確”的記錄（擁有“真實(shí)”屬性值的記錄），另一個(gè)是為非監(jiān)督學(xué)習(xí)找到一個(gè)好的匹配臨界值。

我們?nèi)匀皇褂肍1（F度量中最常用的一種形式（Rijsbergen[6]））和AUC（Area Under precision-recall Curve）。實(shí)驗(yàn)結(jié)果表明我們的方法對(duì)非監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)都能夠獲得高質(zhì)量的實(shí)體識(shí)別結(jié)果。我們改進(jìn)后的方法包含了狹義上實(shí)體識(shí)別的整個(gè)過(guò)程，并且其中的某些步驟是比較通用的，能夠應(yīng)用到其他基于記錄對(duì)匹配的實(shí)體識(shí)別方法中。

對(duì)于較大的數(shù)據(jù)集或者是計(jì)算起來(lái)比較耗費(fèi)時(shí)間的相似度度量，整個(gè)實(shí)體識(shí)別過(guò)程的運(yùn)行時(shí)間可能會(huì)是一個(gè)問(wèn)題。為了解決這個(gè)問(wèn)題，一般會(huì)使用分塊（blocking）或者遮蔽（canopy）（Elmagarmid等[4]，Sarka等[7]）的方法來(lái)有效地選擇記錄對(duì)的一個(gè)子集來(lái)進(jìn)行相似度計(jì)算，而簡(jiǎn)單地忽略其他“不相似”的記錄對(duì)。在我們的研究中，我們?cè)O(shè)計(jì)了一個(gè)數(shù)據(jù)過(guò)濾方法，它和遮蔽有著類(lèi)似的效果。

我們的方法和經(jīng)典的FSM（Fellegi-Sunter Model）主要有兩點(diǎn)不同：首先，我們使用不同的概率匹配模型。FSM使用屬性值的模式，而我們的方法使用相似值的模式。其次，F(xiàn)SM只使用直接匹配，而我們的方法使用直接匹配、傳遞等價(jià)，以及斷言等價(jià)。此外，我們所改進(jìn)的方法使用的間接相似度度量是基于上下文的，這就提供了進(jìn)行關(guān)聯(lián)分析的好處，當(dāng)然我們并不做直接的集體匹配決策。

1.3 主要貢獻(xiàn)

我們實(shí)體識(shí)別的研究工作的主要貢獻(xiàn)有：

●我們將原方法[5]擴(kuò)展成了一個(gè)通用的框架；

●我們?cè)O(shè)計(jì)了兩個(gè)記錄更新算法來(lái)：改進(jìn)分類(lèi)結(jié)果，找到“正確”的記錄，以及為非監(jiān)督學(xué)習(xí)找到好的匹配臨界值；

●我們?cè)O(shè)計(jì)了不一致性消除方法來(lái)消除匹配結(jié)果中的不一致性，同時(shí)提高匹配的精確度。

我們把實(shí)驗(yàn)結(jié)果同幾個(gè)較新的實(shí)體識(shí)別方法（Sin?gla和Domingos[8]、Wick等[9]，以及Rendle和Thieme[10]）的結(jié)果進(jìn)行了比較（使用F1和AUC）。對(duì)于相同的數(shù)據(jù)集，我們的方法總體上要優(yōu)于其他方法。

2 方法框架

圖1 方法框架

我們的方法框架如圖1所示。在預(yù)處理步驟中，我們使用過(guò)濾來(lái)有效降低需要比較的記錄對(duì)的個(gè)數(shù)。接下來(lái)是匹配過(guò)程，我們對(duì)過(guò)濾后的每一對(duì)記錄對(duì)計(jì)算它們的相似度（對(duì)于非監(jiān)督學(xué)習(xí)）或者相似度和等價(jià)概率（對(duì)于監(jiān)督學(xué)習(xí)），以此來(lái)確定該記錄對(duì)是否是等價(jià)的。匹配過(guò)程經(jīng)常會(huì)產(chǎn)生一些不一致的結(jié)果，所以我們?cè)O(shè)計(jì)了消除不一致性的方法，經(jīng)過(guò)這一步，我們可以輸出關(guān)系集合（R），它是所有記錄對(duì)的關(guān)系（等價(jià)或者非等價(jià)）集合。在這一步后，我們還設(shè)計(jì)了記錄更新的算法。在記錄更新步驟中我們更新某些記錄的屬性值來(lái)提高識(shí)別的準(zhǔn)確性，同時(shí)會(huì)輸出“真實(shí)”記錄集合（T）。此外，對(duì)于非監(jiān)督學(xué)習(xí)，記錄更新步驟還能找到好的匹配臨界值。不一致性消除，記錄更新以及等價(jià)消除構(gòu)成了我們框架中的后期處理過(guò)程。后期處理過(guò)程結(jié)束后，我們可以完成任務(wù)輸出結(jié)果，也可以回到預(yù)處理步驟重復(fù)整個(gè)過(guò)程。一般情況下一遍過(guò)程就可以獲得很好的結(jié)果。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

所有實(shí)驗(yàn)在一臺(tái)PC上進(jìn)行，配置如下：

●CPU：AMD Phenom II 2.9G Hz；

●內(nèi)存：3.25GB。

我們使用兩個(gè)公共的數(shù)據(jù)集Cora和CDDB。

Cora是一個(gè)科學(xué)出版物參考文獻(xiàn)信息的數(shù)據(jù)集。我們從Weis等[11]處下載此數(shù)據(jù)集。它包含了1878個(gè)引用，而這些引用實(shí)際上只對(duì)應(yīng)139個(gè)研究論文。它是McCallum[12]提供的數(shù)據(jù)集的擴(kuò)展的版本。Cora數(shù)據(jù)集中的記錄有五個(gè)屬性：標(biāo)題、作者、出處、卷號(hào)，以及日期。我們?cè)跀?shù)據(jù)預(yù)處理步驟中對(duì)該數(shù)據(jù)集進(jìn)行了一些清洗工作，去除了一些標(biāo)點(diǎn)符號(hào)。如果某記錄的作者超過(guò)一個(gè)，我們把該記錄的每一個(gè)作者單獨(dú)作為一個(gè)作者屬性值。

CDDB數(shù)據(jù)集包含9763個(gè)從freeDB隨機(jī)抽取的音樂(lè)CD的信息。我們也是從Weis等[11]處下載此數(shù)據(jù)集。CDDB不像Cora數(shù)據(jù)集那樣有很多等價(jià)記錄，它的記錄對(duì)應(yīng)9388個(gè)不同的音樂(lè)CD，所以等價(jià)的記錄只是一少部分。每個(gè)音樂(lè)CD記錄有七個(gè)屬性：藝術(shù)家、標(biāo)題、分類(lèi)、流派、年份、額外信息，以及音軌標(biāo)題。類(lèi)似的，我們把一條記錄的每一個(gè)藝術(shù)家單獨(dú)作為一個(gè)藝術(shù)家屬性值。

3.2 監(jiān)督學(xué)習(xí)實(shí)驗(yàn)結(jié)果

因篇幅所限，我們略去非監(jiān)督學(xué)習(xí)的實(shí)驗(yàn)結(jié)果。

表1 Cora數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表2 CDDB數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表1和表2中，3組和5組是指3組交叉驗(yàn)證和5組交叉驗(yàn)證。從表1和表2來(lái)看，我們改進(jìn)后的方法比原方法除了一項(xiàng)結(jié)果有略微下降以外其他的都有明顯的提高。

4 有關(guān)研究工作

Chen等[13]提出了一種基于圖的實(shí)體識(shí)別方法。該方法分析由數(shù)據(jù)集構(gòu)建的實(shí)體關(guān)系圖，并度量不同節(jié)點(diǎn)對(duì)之間的互聯(lián)度。

Dong等[14]考慮復(fù)雜的信息空間來(lái)解決引用關(guān)系重建的問(wèn)題。該算法在決定合并兩個(gè)引用的時(shí)候，它會(huì)使用引用增強(qiáng)機(jī)制來(lái)利用上下文信息。他們的引用增強(qiáng)有一點(diǎn)類(lèi)似與我們的記錄更新。不過(guò)我們的記錄更新是有一些限制的更新記錄，而不是合并。

Singla和Domingos[8]提出了一個(gè)基于馬爾科夫邏輯的集成的實(shí)體識(shí)別方法。馬爾卡夫邏輯結(jié)合了一階邏輯和概率圖模型。我們把同一個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果和他們的進(jìn)行了比較。

Bhattacharya和Getoor[15]針對(duì)非監(jiān)督學(xué)習(xí)實(shí)體識(shí)別擴(kuò)展了隱含狄利克雷分布（Latent Dirichlet Allocation）模型，并且針對(duì)引用互相連接的關(guān)系領(lǐng)域的集體實(shí)體識(shí)別提出了一種概率模型。

Rendle和Thieme[10]提出了一個(gè)使用結(jié)構(gòu)化信息的模型來(lái)進(jìn)行集體的對(duì)象身份識(shí)別。我們把同一個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果和他們的進(jìn)行了比較。

Cong等[16]研究了有效的方法來(lái)改進(jìn)數(shù)據(jù)一致性和精確度。他們采用了一類(lèi)條件的功能依賴(lài)（Bohannon等[17]）來(lái)指定數(shù)據(jù)的一致性。他們?cè)O(shè)計(jì)了兩個(gè)算法來(lái)改進(jìn)數(shù)據(jù)的一致性。

Chaudhuri等[18]觀(guān)察到某些情況下數(shù)據(jù)中額外的約束可被用來(lái)評(píng)估重復(fù)數(shù)據(jù)去除的質(zhì)量。

Bilgic等[19]介紹了一個(gè)叫D-Dupe的交互工具。該工具結(jié)合了實(shí)體識(shí)別數(shù)據(jù)挖掘算法和網(wǎng)絡(luò)可視化來(lái)展現(xiàn)潛在的等價(jià)數(shù)據(jù)的協(xié)作上下文。

Arasu等[20]提出了一個(gè)在約束下的集體的重復(fù)實(shí)體引用去除的方法。該方法基于一個(gè)簡(jiǎn)單的具有精確語(yǔ)義的說(shuō)明性語(yǔ)言。

Wick等[9]提出了一種差異性學(xué)習(xí)模型來(lái)聯(lián)合進(jìn)行引用識(shí)別和規(guī)范化（生成實(shí)體穩(wěn)定表示的過(guò)程）。我們把同一個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果和他們的進(jìn)行了比較。

斯坦福SERF項(xiàng)目組（Benjelloun等[21]）開(kāi)發(fā)了一個(gè)叫Swoosh的一般的實(shí)體識(shí)別方法。他們確定了四個(gè)屬性，如果這些屬性被匹配和合并函數(shù)滿(mǎn)足的話(huà)將會(huì)使得實(shí)體識(shí)別算法更加有效。他們?yōu)檫@些屬性的不同情形開(kāi)發(fā)了不同的算法。他們并沒(méi)有研究這些匹配合并算法的內(nèi)部細(xì)節(jié)，而是把它們視為被實(shí)體識(shí)別引擎調(diào)用的黑盒子。

更全面的實(shí)體識(shí)別方法概覽可以參考Elmagarmid等[4]以及 Winkler[22]。

5 結(jié)語(yǔ)

雖然我們已經(jīng)在很大程度上改進(jìn)了原來(lái)的方法，但是依然有很多改進(jìn)的空間。方法中使用的直接相似性和間接相似性有圖形的解釋?zhuān)撬鼈冞€可以集成地更好。CDDB數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果比Cora要差一點(diǎn)，也是有改進(jìn)的余地。盡管我們使用了數(shù)據(jù)過(guò)濾方法來(lái)大大降低候選記錄對(duì)的數(shù)量，對(duì)于非常大的數(shù)據(jù)集來(lái)說(shuō)，成對(duì)的記錄匹配的效率依然可能會(huì)是一個(gè)問(wèn)題。