蔣存鋒，趙川

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

0 引言

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

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

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

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

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

●實體引用識別：確定引用是否對應(yīng)同一個實體；

●實體身份管理：建立和維護一個長久的實體身份信息記錄；

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

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

1 方法概述

1.1 常用方法

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

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

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

1.2 改進的方法

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

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

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

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

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

1.3 主要貢獻(xiàn)

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

●我們將原方法[5]擴展成了一個通用的框架；

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

●我們設(shè)計了不一致性消除方法來消除匹配結(jié)果中的不一致性，同時提高匹配的精確度。

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

2 方法框架

圖1 方法框架

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

3 實驗結(jié)果

3.1 實驗環(huán)境

所有實驗在一臺PC上進行，配置如下：

●CPU：AMD Phenom II 2.9G Hz；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

雖然我們已經(jīng)在很大程度上改進了原來的方法，但是依然有很多改進的空間。方法中使用的直接相似性和間接相似性有圖形的解釋，但是它們還可以集成地更好。CDDB數(shù)據(jù)集的實驗結(jié)果比Cora要差一點，也是有改進的余地。盡管我們使用了數(shù)據(jù)過濾方法來大大降低候選記錄對的數(shù)量，對于非常大的數(shù)據(jù)集來說，成對的記錄匹配的效率依然可能會是一個問題。