一種實體識別的后期處理優(yōu)化算法

蔣存鋒 趙 川

1(上海計算機軟件技術(shù)開發(fā)中心 上海 201112)2(天睿公司 美國加利福尼亞洲 圣地亞哥 92127 )

0 引 言

在傳統(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 實體識別算法

本文改進了傳統(tǒng)實體識別算法中常用的兩種方法：基于概率模型的機器學(xué)習(xí)方法以及依靠領(lǐng)域知識作度量標(biāo)準(zhǔn)匹配的方法[1]。改進的算法提出一個既使用直接相似度又使用間接相似度的結(jié)構(gòu)化的相似度度量標(biāo)準(zhǔn)。該方法對于非監(jiān)督學(xué)習(xí)使用一個簡單的相似度模型，而對于監(jiān)督學(xué)習(xí)則提供了一個概率的分類模型以及估算概率的方法。此外，該算法提供了簡單的更新算法來消除分類匹配結(jié)果中的不一致性。本文沿用了該算法的相似度度量和概率模型，并在此基礎(chǔ)上做了較大的改進，不但進行實體的識別，還兼顧到對象的合并。增加了數(shù)據(jù)預(yù)處理的步驟，設(shè)計了一種數(shù)據(jù)過濾策略。在后期處理過程中，設(shè)計了幾種不一致性消除的方法，以及兩個有效的記錄更新算法。這些步驟都大大改進了計算效率和分類結(jié)果。而且，其中的記錄更新算法還可以找到“正確”的記錄，即擁有“真實”屬性值的記錄，并為非監(jiān)督學(xué)習(xí)找到一個好的匹配臨界值。

對于較大的數(shù)據(jù)集或者是計算起來比較耗費時間的相似度度量，整個實體識別過程的運行時間可能會是一個問題。為了解決這個問題，一般會使用分塊(blocking)或者遮蔽(canopy)[2-5]的方法來有效地選擇記錄對的一個子集來進行相似度計算，而簡單地忽略其他“不相似”的記錄對。本文設(shè)計了一個數(shù)據(jù)過濾方法，它和遮蔽有著類似的效果。此外，并行和分布式計算也是近年來一個比較受重視的加快實體識別速度的方法[7-8]。本文提出的方法和一些常見的大數(shù)據(jù)處理框架的結(jié)合將是我們下一步研究的重點。

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

2 不一致性消除

匹配結(jié)果中經(jīng)常會有不一致性出現(xiàn)，比如三個記錄a、b、c，a和b被認為是等價的，a和c也被認為是等價的，但是b和c卻被認為不等價。本文稱這樣的三元組為不一致的三角。對監(jiān)督學(xué)習(xí)中的一個不一致的三角來說，如果有記錄對是在學(xué)習(xí)數(shù)據(jù)集中，那我們可以用它(們)來更正測試數(shù)據(jù)集中的記錄對匹配結(jié)果，本文稱這種方法為MT。如果所有三個邊(記錄對)都在測試集中，那可以有更多的選擇來讓不一致的三角變得一致。這種情況下一般來說我們可以使用傳遞閉包。

2.1 傳遞閉包(TC)

一個常用的消除分類結(jié)果中不一致性的方法是使用傳遞閉包。本文設(shè)計了算法1來消除三個邊都在測試集中的不一致分類結(jié)果。在此算法中，S(x,y)是記錄x和y之間的直接相似度，P(x,y)是記錄x和y是等價記錄的概率，t是當(dāng)前的匹配臨界值。實驗表明該算法每一次都能消除分類匹配結(jié)果中的所有的三個邊都在測試集中的不一致三角形。

算法1用傳遞閉包(TC)消除不一致性

輸入： 分類后的候選記錄對。

輸出： 分類后的不一致結(jié)果被消除的候選記錄對。

循環(huán)開始

change=0

對于每一個記錄a；

對于每一個(a,b)在候選記錄對中的記錄b；

對于每一個(a,c)在候選記錄對中的記錄c；

如果(b,c)在候選記錄對中；

如果(a,b)、(a,c)、(b,c)都在測試集中并且其中兩對是等價對并且另外一對是非等價對；

將非等價對變成等價對;

change=change+1;

否則如果(a,b)、(a,c)都是等價對；

將(b,c)變?yōu)榈葍r對，并將(b,c)放入候選記錄對中，對于非監(jiān)督學(xué)習(xí)：S(b,c)=S(c,b)=max(S(b,c),t)；對于監(jiān)督學(xué)習(xí)：P(b,c)=P(c,b)=t；

如果change是0，退出循環(huán)；

循環(huán)結(jié)束

在施加TC算法后，測試集中不一致性都得以消除，但是可能會出現(xiàn)新的不一致三角，既有邊在學(xué)習(xí)集又有邊在測試集。實驗結(jié)果表明這種新的不一致三角通常很少，所以我們可以施加一些其他的后期處理方法來消除它們。

2.2 一般的不一致性消除算法(IE)

MT和TC都是比較特殊的不一致性消除算法，運用它們雖然能消除大部分不一致結(jié)果，但是常常不能完全消除。如果單獨施加MT，所有邊在測試集中的不一致三角經(jīng)常還會存在；而如果單獨施加TC，既有邊在學(xué)習(xí)集又有邊在測試集的不一致三角又經(jīng)常會留下來。如果兩個都用，取決于使用的順序，通常也會有類似的結(jié)果。因此，本文還設(shè)計了兩個一般的算法來消除使用MT和(或)TC后剩下的不一致結(jié)果。它們是算法2和算法3。

算法2IE(一般的不一致消除)

輸入： 分類后的候選記錄對。

輸出： 分類后的不一致性結(jié)果被消除的候選記錄對。

1. 收集所有的不一致三角在測試集里的邊(集合E)；

2. 將E分割為組，每組含有n個邊(比如n=10)；

3. 對于每個組，嘗試所有2n個可能的值的組合(每條邊可以取等價和非等價兩種值)，統(tǒng)計每個組合里不一致三角的個數(shù)；

4. 對于每個組，選擇不一致三角最少的那個組合。

算法2的效率并不是很好，因為對于每一對組合我們必須檢查全局集合E中的每一個三角，而不是在一個局部的組里面，所以我們設(shè)計了下面的改進算法。

算法3改進的IE(改進的不一致消除)

輸入：分類后的候選記錄對。

輸出：分類后的不一致性結(jié)果被消除的候選記錄對。

1. 構(gòu)建一個不一致三角和邊(在測試集里)之間的二部圖；

2. 獲得該二部圖里的所有最大連通子圖；

3. 將這些子圖分組，讓每個組的邊的個數(shù)盡量接近某個值t，比如10。邊的個數(shù)大于t的子圖自成一組；

4. 對于每個組，如果它的邊的個數(shù)大于t，把它分割成每個大小為t的子組。對于每一個子組，嘗試所有2t個不同的值的組合，然后選擇不一致三角最少的子組。如果組的大小不大于t，則嘗試所有2t個不同的值的組合，然后選擇不一致三角最少的組。

在算法3中，對于每一個局部組，不一致三角只會由組里的邊構(gòu)成。因此，對于每一個組合在重新計算不一致三角的個數(shù)的時候，我們只需要檢查所有邊都在這個組里面的三角。實驗結(jié)果表明算法3的速度比算法2要快很多，而不一致消除的結(jié)果卻達到了算法2的水平。

在算法3中，我們可以按照不同的順序來組合子圖：大的子圖優(yōu)先，或者小的子圖優(yōu)先，或者隨機。實驗結(jié)果表明優(yōu)先組合大的子圖可以獲得最好的結(jié)果。實驗結(jié)果還表明，不論是使用算法2還是算法3，絕大多數(shù)的不一致結(jié)果都能得到消除。

2.3 非傳遞性方法(NT)

除了傳遞閉包，我們也可以使用類似于MT的方法來消除測試集中的不一致三角。本文的方法是：

? 除了允許把非等價邊變成等價邊，還允許等價邊變成非等價邊；

? 當(dāng)三角中有超過一條邊需要改變時，選擇等價概率最接近匹配臨界值的那條邊；

? 如果三角中只有一條邊可以改變，則在改變后固定它的值(等價或者非等價)，或不改變。

和MT類似，因為可以在等價和非等價兩者之間轉(zhuǎn)變，NT也不能總是消除所有的不等價結(jié)果。

另一個非傳遞性方法類似于TC。不過，不是把非等價變成等價，我們把一條等價邊變成非等價。同樣的，本文仍然選擇等價概率最接近匹配臨界值的那條邊。類似于TC，該算法也可以消除測試集中的所有不一致性。

2.4 結(jié)合不同的不一致性消除方法

前面介紹的這些不一致性消除方法有時候?qū)ν粭l邊會產(chǎn)生不同的決策。我們可以結(jié)合使用這些方法來得到更好的結(jié)果。本文嘗試了一些不同的組合：沒有不一致性消除、MT、TC、MT+TC、TC+MT、MT+TC+MT、TC+MT+TC。這里“+”的意思是接著使用。每一種組合之后我們都再使用IE。實驗結(jié)果表明沒有不一致性消除、TC、TC+MT+TC總是會產(chǎn)生很多不一致結(jié)果，而另外4種組合則不會。其中TC+MT不太穩(wěn)定，有時候也會產(chǎn)生很多不一致結(jié)果。后面4種組合表現(xiàn)出了不同的不一致性能力。本文也嘗試了MT+NT+IE的組合。在第3節(jié)中本文提供了詳細的實驗結(jié)果。

我們相信不同的組合擁有不同的不一致性消除能力是因為不同的方法會產(chǎn)生不同類型的不一致三角。通過對實驗結(jié)果中不一致三角的觀察，我們發(fā)現(xiàn)如果使用MT+TC，結(jié)果中大部分不一致三角都由一條在學(xué)習(xí)集中的非等價邊和兩條在測試集中的等價邊構(gòu)成；而如果使用MT、TC+MT、MT+TC+MT，大部分不一致三角則由測試集中的兩條等價邊和一條非等價邊構(gòu)成；如果使用MT+NT，大部分不一致三角包含學(xué)習(xí)集中的一條等價邊和測試集中的一條等價邊及一條非等價邊。顯然，如果不一致三角的所有邊都在測試集中，不一致性會更容易消除。

3 記錄更新及等價消除

記錄更新算法的基本思想是通過更新某些記錄的屬性值來減少不同記錄的數(shù)量。針對非監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)，本文設(shè)計了不同的記錄更新算法。限于篇幅，本文只給出監(jiān)督學(xué)習(xí)的算法如算法4所示。其中，步驟1到步驟5可以反復(fù)迭代，但是對于最后一次迭代，步驟5不執(zhí)行。通常整個算法只需要執(zhí)行一次即可。

算法4監(jiān)督學(xué)習(xí)的記錄更新算法

輸入：所有候選記錄對中的記錄。

輸出：有“真實”屬性值和等價記錄的記錄。

步驟1： 初始化一個空的集群集合C。在記錄匹配后，對每個候選記錄對中的記錄r1，尋找一個和r1等價的概率最大的記錄r2。對某個匹配臨界值t，如果p不小于t，進入步驟2；否則跳過該記錄。

步驟2： 如果r1和r2都不在任何集群中，創(chuàng)建一個新的集群c，將r1和r2放入c中，將c加入C中；如果r1和r2都已經(jīng)在某個集群中，什么都不用做；如果兩者中的一個在某個集群c中，則將另一個也放入c中。

步驟3： 當(dāng)所有的輸入記錄都在步驟1和步驟2中處理過之后，對于C中的每一個集群，尋找它的中位記錄。中位記錄是和同一個集群中的其他記錄有最大直接相似度的和的記錄。然后根據(jù)每個集群的中位記錄和同集群其他記錄的平均直接相似度降序排序集群。如果兩個集群的中位記錄是等價的，則將兩者中在集群集合中索引較低的集群合并入索引較高的集群。然后重新計算合并后的集群的中位記錄。重復(fù)這一過程直到?jīng)]有集群的中位記錄之間是等價的。中位記錄和所有不在候選記錄對中的記錄合起來就形成了有“真實”屬性的記錄集合。

步驟4： 對于每一個集群，用中位記錄去更新同集群中的其他記錄。

步驟5： 重新做數(shù)據(jù)過濾，并重新計算每個候選記錄對的等價概率。

記錄更新算法的細節(jié)如下：

(1) 如何使用其他記錄的屬性值來更新某個記錄的屬性值：本文用更新記錄的屬性值來更新被更新記錄的所有屬性值，而不只是部分屬性。

(2) 對于記錄r1來說，如何確定一個記錄集從中選擇記錄r2：我們可以從所有候選記錄對中選擇r2，也可以從當(dāng)前迭代中還沒有被選擇作為r1的記錄中選擇。

(3) 如何選擇匹配臨界值t：簡單地說，我們用當(dāng)前的匹配臨界值。本文選擇在進行當(dāng)前這一步更新之前獲得最佳F1值的匹配臨界值。

(4) 對于k組交叉驗證：在記錄更新和重新進行數(shù)據(jù)過濾之后，我們把之前的候選記錄對保留在它們原來的組中，這會使記錄更新的過程更加穩(wěn)定。

(5) 如何獲得最終結(jié)果：記錄更新算法的結(jié)果收斂得很快，通常一輪更新即可獲得穩(wěn)定結(jié)果。

本文使用領(lǐng)導(dǎo)記錄(非監(jiān)督學(xué)習(xí)，是有真實屬性和等價記錄的記錄)或者中位記錄(監(jiān)督學(xué)習(xí))以及那些不屬于任何候選記錄對的記錄作為擁有“真實”屬性的記錄，稱為等價消除或?qū)嶓w身份確定。

4 實驗結(jié)果

4.1 實驗環(huán)境

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

? CPU：AMD Phenom II 2.9 GHz；

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

本文使用公共的數(shù)據(jù)集Cora。Cora是一個科學(xué)出版物參考文獻信息的數(shù)據(jù)集。我們從Weis等[9]處下載此數(shù)據(jù)集。它包含了1 878個引用，而這些引用實際上只對應(yīng)139個研究論文。它是McCallum[10]提供的數(shù)據(jù)集的擴展版本。Cora數(shù)據(jù)集中的記錄有五個屬性：標(biāo)題、作者、出處、卷號、日期。本文在數(shù)據(jù)預(yù)處理步驟中對該數(shù)據(jù)集進行了一些清洗工作。

本文去除了一些標(biāo)點符號。如果某個記錄的作者超過一個，則把該記錄的每一個作者單獨作為一個作者屬性值。

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

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

表1 Cora數(shù)據(jù)集不一致性消除實驗結(jié)果

表1中，“/”前后的數(shù)據(jù)表示施加IE算法前后的數(shù)據(jù)；“#”表示不一致三角的個數(shù)；“#r”的意思是去除等價記錄后的有等價記錄的記錄個數(shù)，也就是有“真實”屬性值的而且在數(shù)據(jù)集中有它的等價記錄的記錄個數(shù)。所有結(jié)果都是三次運行的平均結(jié)果。本文只使用了直接相似度，并使用算法3，設(shè)置t=5。首先，可以看到不一致性消除改進了分類匹配的精確度，而且基本上消除了不一致結(jié)果。其次，在記錄更新后，不一致三角的數(shù)量大大降低。再次，除了MT+TC+IE以外，所有的組合都表現(xiàn)出了良好的不一致性消除能力。MT+TC+MT+IE產(chǎn)生了最少的不一致三角以及最好的分類精確性。最后，所有的組合都得到了不錯的記錄個數(shù)，且是“真實”屬性值而且存在和其等價的記錄。

表2 Cora數(shù)據(jù)集結(jié)果和其他方法比較

表2中，“5組”和“3組”是指進行5組交叉驗證和3組交叉驗證，“25%”的意思是每次隨機選取25%的記錄對作為學(xué)習(xí)集，共進行4組交叉驗證。“/”前后的數(shù)據(jù)表示施加領(lǐng)域優(yōu)化的直接相似度計算前后的數(shù)據(jù)。表2中的數(shù)據(jù)表明本文的方法比其他的方法獲得了更好的結(jié)果。

5 結(jié) 語

本文主要通過一些后期處理算法改進了一個實體識別算法，該算法屬于傳統(tǒng)的混合-清除算法。后期處理過程主要包括不一致性消除、記錄更新以及等價消除，它們可以顯著提高實體識別的結(jié)果。本文針對不同情況提供了不同的不一致性消除算法。本文方法在兩種不同的數(shù)據(jù)集上都獲得了很好的實驗結(jié)果。