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

蔣存鋒 趙 川

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

0 引 言

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

1 實(shí)體識(shí)別算法

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

對(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)[2-5]的方法來(lái)有效地選擇記錄對(duì)的一個(gè)子集來(lái)進(jìn)行相似度計(jì)算，而簡(jiǎn)單地忽略其他“不相似”的記錄對(duì)。本文設(shè)計(jì)了一個(gè)數(shù)據(jù)過(guò)濾方法，它和遮蔽有著類似的效果。此外，并行和分布式計(jì)算也是近年來(lái)一個(gè)比較受重視的加快實(shí)體識(shí)別速度的方法[7-8]。本文提出的方法和一些常見(jiàn)的大數(shù)據(jù)處理框架的結(jié)合將是我們下一步研究的重點(diǎn)。

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

2 不一致性消除

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

2.1 傳遞閉包(TC)

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

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

輸入： 分類后的候選記錄對(duì)。

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

循環(huán)開(kāi)始

change=0

對(duì)于每一個(gè)記錄a；

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

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

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

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

將非等價(jià)對(duì)變成等價(jià)對(duì);

change=change+1;

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

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

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

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

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

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

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

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

輸入： 分類后的候選記錄對(duì)。

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

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

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

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

4. 對(duì)于每個(gè)組，選擇不一致三角最少的那個(gè)組合。

算法2的效率并不是很好，因?yàn)閷?duì)于每一對(duì)組合我們必須檢查全局集合E中的每一個(gè)三角，而不是在一個(gè)局部的組里面，所以我們?cè)O(shè)計(jì)了下面的改進(jìn)算法。

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

輸入：分類后的候選記錄對(duì)。

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

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

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

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

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

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

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

2.3 非傳遞性方法(NT)

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

? 除了允許把非等價(jià)邊變成等價(jià)邊，還允許等價(jià)邊變成非等價(jià)邊；

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

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

和MT類似，因?yàn)榭梢栽诘葍r(jià)和非等價(jià)兩者之間轉(zhuǎn)變，NT也不能總是消除所有的不等價(jià)結(jié)果。

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

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

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

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

3 記錄更新及等價(jià)消除

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

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

輸入：所有候選記錄對(duì)中的記錄。

輸出：有“真實(shí)”屬性值和等價(jià)記錄的記錄。

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

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

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

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

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

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

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

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

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

(4) 對(duì)于k組交叉驗(yàn)證：在記錄更新和重新進(jìn)行數(shù)據(jù)過(guò)濾之后，我們把之前的候選記錄對(duì)保留在它們?cè)瓉?lái)的組中，這會(huì)使記錄更新的過(guò)程更加穩(wěn)定。

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

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

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

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

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

? CPU：AMD Phenom II 2.9 GHz；

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

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

本文去除了一些標(biāo)點(diǎn)符號(hào)。如果某個(gè)記錄的作者超過(guò)一個(gè)，則把該記錄的每一個(gè)作者單獨(dú)作為一個(gè)作者屬性值。

4.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é)果

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

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

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

5 結(jié) 語(yǔ)

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