對(duì)象識(shí)別研究綜述

常明 倪德強(qiáng) 程濤遠(yuǎn)

摘要：數(shù)據(jù)的質(zhì)量直接決定著信息服務(wù)的質(zhì)量。在有關(guān)數(shù)據(jù)質(zhì)量的各種問(wèn)題中,識(shí)別出屬于同一個(gè)現(xiàn)實(shí)實(shí)體（對(duì)象）的多條記錄（表象）是最關(guān)鍵的問(wèn)題之一。我們把這樣的問(wèn)題稱(chēng)為是對(duì)象識(shí)別問(wèn)題。該文分析了近些年對(duì)象識(shí)別技術(shù)的發(fā)展，給出了在效率可擴(kuò)展性、屬性值相似度的判斷、記錄對(duì)相似性的判斷、集合模型相似性的判斷等方面相關(guān)的研究方法和存在的研究問(wèn)題。

關(guān)鍵詞:對(duì)象識(shí)別；可擴(kuò)展性；相似度；記錄對(duì)

中圖分類(lèi)號(hào)：TP399文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)21-5032-03

Review of Object Identification Research

CHANG Ming1，NI De-qiang1,CHENG Tao-yuan2

(1.Anshan Radio and Television Bureau,Anshan 114001,China; 2.Beijing Baidu Network Technology Co., Ltd., Beijing 100080, China)

Abstract：Data quality directly determines the quality of information service. About data quality problems, it is one of the most critical is sues to identify a number of records (representation) of the same real entities (objects). It is called object identification. This paper analyzed the recent technical development of object identification. give some recent research methods and problems about efficiency of scalability, at tribute value similarity judgments, record pairs similarity judgment, set model similarity judgment.

Key words：object identification; scalability; similarity; record pair

1959年H. Newcombe等人第一次提出了對(duì)象識(shí)別的概念[1]，文獻(xiàn)[2]則為對(duì)象識(shí)別提出了正式理論，并且提出了一整套的統(tǒng)計(jì)學(xué)方法來(lái)計(jì)算匹配的參數(shù)和錯(cuò)誤率。在傳統(tǒng)的對(duì)象識(shí)別研究中，人們主要在解決如下兩個(gè)問(wèn)題：1）如何計(jì)算記錄對(duì)的相似度；）如何減少需要進(jìn)行相似度計(jì)算的記錄對(duì)數(shù)目。W. E. Winkler在文獻(xiàn)[3]中綜述了當(dāng)時(shí)與對(duì)象識(shí)別相關(guān)的研究工作。幾年過(guò)去了，對(duì)象識(shí)別領(lǐng)域的研究又取得了很大的進(jìn)展，而且最近幾年出現(xiàn)了一些新的模型和方法，突破了傳統(tǒng)對(duì)象識(shí)別中基于兩條記錄計(jì)算相似度的思想。

很高，而且容易出錯(cuò)。

傳統(tǒng)的方法只是考慮如何利用本地?cái)?shù)據(jù)庫(kù)中的信息進(jìn)行對(duì)象識(shí)別，在很多情況下，僅僅利用本地?cái)?shù)據(jù)庫(kù)的信息無(wú)法獲得很好的對(duì)象識(shí)別結(jié)果。對(duì)象識(shí)別產(chǎn)生的很多模糊匹配，如果能夠找到一些其他的信息就可以判斷出來(lái)時(shí)匹配還是不匹配了。例如，對(duì)于兩個(gè)人名“Bob Smith”和“Robert Smith”，采用字符串相似度判斷時(shí)，由于他們的相似度沒(méi)有高于閾值，所以會(huì)被認(rèn)為是一個(gè)模糊匹配。但是在英文里作為人名的一部分時(shí)，“Bob”和“Robert”是一對(duì)可以互相交換的詞。如果有一個(gè)輔助數(shù)據(jù)源可以提供這樣的信息，那么就可以判斷這個(gè)模糊匹配“Bob Smith”和“Robert Smith”是相同的人名。提出了一種利用輔助數(shù)據(jù)源查找額外信息，結(jié)合已有得信息進(jìn)行判斷的方法。由于查詢輔助數(shù)據(jù)源會(huì)導(dǎo)致延遲，而且還可能會(huì)導(dǎo)入錯(cuò)誤等，系統(tǒng)只是在產(chǎn)生模糊匹配的時(shí)候才會(huì)去利用中間件進(jìn)行查詢。采用這樣的模型，可以提高基于網(wǎng)絡(luò)的對(duì)象識(shí)別的準(zhǔn)確率和查全率。但是，論文中的輔助數(shù)據(jù)源是一些特定的數(shù)據(jù)源，需要提前知道數(shù)據(jù)源的模式，獲得使用權(quán)限等。這樣的要求大大限制了模型的適用范圍，不能作為一種通用的模型進(jìn)行推廣。在不存在特定輔助數(shù)據(jù)源的情況下，研究中則提出了一種利用網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行相關(guān)人員判斷的方法。提出了一種利用網(wǎng)絡(luò)，通過(guò)無(wú)監(jiān)督學(xué)習(xí)解決“同名不同人”問(wèn)題的方法。這些研究工作都很好地解決了各自論文中提出的問(wèn)題。但是由于他們提出問(wèn)題或者帶有特殊的背景知識(shí)（需要知道多個(gè)人之間是熟人關(guān)系），或者要求提前知道查找出的網(wǎng)頁(yè)符合一定的模板，這些利用網(wǎng)絡(luò)識(shí)別同名不同人的系統(tǒng)通用性不強(qiáng)。

1.4集合模型的判斷

隨著應(yīng)用的發(fā)展，僅僅根據(jù)兩條記錄的信息已經(jīng)無(wú)法很好的判斷對(duì)應(yīng)表象是否匹配了。在數(shù)據(jù)庫(kù)中，一個(gè)表象不僅在需要進(jìn)行比較的記錄中有信息，還會(huì)存在一些其他的聯(lián)系信息。如何更好的利用這些聯(lián)系信息是最近的研究工作的重點(diǎn)。

由于論文數(shù)據(jù)庫(kù)的特點(diǎn)，作者名字的對(duì)象識(shí)別過(guò)程也就是盡量利用相關(guān)信息的過(guò)程。中最初提出了利用作者表象的上下文信息，也就是利用了和要識(shí)別的作者名字直接聯(lián)系的一層信息?？紤]到可能會(huì)存在的一個(gè)人名對(duì)應(yīng)多個(gè)作者對(duì)象的問(wèn)題，這樣的一層信息還是相對(duì)比較可靠的。等工作開(kāi)始利用表象的多層聯(lián)系進(jìn)行計(jì)算，雖然這樣的方法可以利用更多的信息，但是“同名不同人”問(wèn)題的存在會(huì)使得這些工作的準(zhǔn)確率很受影響。而且，這些工作都是基于SimRank或者SimFusion模型，算法的空間復(fù)雜度是O(n2)，運(yùn)行時(shí)間會(huì)較長(zhǎng)。而基于依賴(lài)關(guān)系的對(duì)象識(shí)別則考慮到了識(shí)別的先后順序，可以利用首先識(shí)別出來(lái)的對(duì)象輔助后面的模糊匹配的識(shí)別。與以前的工作相比，這樣的工作更加符合人的邏輯判斷過(guò)程。上面的工作只是簡(jiǎn)單的利用了多層關(guān)系。在論文數(shù)據(jù)庫(kù)中，對(duì)象之間會(huì)存在依賴(lài)關(guān)系，不僅記錄之間會(huì)存在依賴(lài)關(guān)系，不同的屬性值之間也會(huì)存在這樣的關(guān)系。進(jìn)行對(duì)象識(shí)別時(shí)，利用眾多表象之間的關(guān)系，首先識(shí)別出來(lái)的對(duì)象可以向正在識(shí)別的表象提供有用的信息，而傳統(tǒng)的對(duì)象識(shí)別工作沒(méi)有考慮這樣的依賴(lài)關(guān)系。提出基于依賴(lài)關(guān)系進(jìn)行對(duì)象識(shí)別的工作。在基于依賴(lài)關(guān)系進(jìn)行對(duì)象識(shí)別的工作中，一個(gè)模糊匹配的成功識(shí)別可以獲得一定的知識(shí)，利用這樣的知識(shí)可以輔助別的節(jié)點(diǎn)進(jìn)行識(shí)別。在利用依賴(lài)關(guān)系時(shí)，首先判斷容易判斷的對(duì)象，然后再來(lái)進(jìn)行更加模糊的對(duì)象判斷。

不僅在論文數(shù)據(jù)庫(kù)中可以使用集合模型，在其他的數(shù)據(jù)庫(kù)中只要記錄中間存在某些聯(lián)系，也可以使用這樣的模型。研究了在數(shù)據(jù)庫(kù)的各個(gè)表中間存在層次關(guān)系時(shí)，如何利用這些關(guān)系進(jìn)行對(duì)象識(shí)別的問(wèn)題。數(shù)據(jù)庫(kù)中多個(gè)表之間可能會(huì)存在一定的層次關(guān)系，例如表A是關(guān)于不同國(guó)家的數(shù)據(jù)，表B是不同國(guó)家中州（或者?。┑臄?shù)據(jù)。這樣的兩個(gè)表通過(guò)主外鍵關(guān)系就存在一個(gè)層次關(guān)系。在這樣的數(shù)據(jù)庫(kù)中進(jìn)行對(duì)象識(shí)別時(shí)，除了可以計(jì)算兩個(gè)表象的文本相似度之外，還可以利用兩個(gè)表象的孩子節(jié)點(diǎn)覆蓋（overlap）進(jìn)行判斷。一般說(shuō)來(lái)，如果兩個(gè)表象屬于同一個(gè)對(duì)象，它們的孩子節(jié)點(diǎn)會(huì)對(duì)應(yīng)較大的覆蓋。例如，country表中的“USA”和“United States of America”都在state表中對(duì)應(yīng)著“MO”，“CA”，“AL”等，那么在判斷“USA”和“United States of America”是否對(duì)應(yīng)同一對(duì)象時(shí)，雖然他們的文本相似度不是很高，但是由于他們下一級(jí)的state數(shù)據(jù)覆蓋很大，可以判斷它們是同一國(guó)家的名字。

利用集合模型進(jìn)行判斷是近幾年才出現(xiàn)的研究工作，主要集中在如何利用這樣的模型解決論文數(shù)據(jù)庫(kù)中的作者識(shí)別問(wèn)題。由于作者名字的特點(diǎn)，這些工作都沒(méi)有很好的研究如何生成需要比較的表象對(duì)。而這樣的工作對(duì)于一個(gè)成功的對(duì)象識(shí)別系統(tǒng)來(lái)說(shuō)是非常重要的。其實(shí)，不僅是論文數(shù)據(jù)庫(kù)，普通的數(shù)據(jù)庫(kù)中也會(huì)在表象之間存在一定的關(guān)系。在本地?cái)?shù)據(jù)庫(kù)中如何更好的利用這樣的關(guān)系應(yīng)該是下一步的研究工作。

如何提高對(duì)象識(shí)別的可擴(kuò)展性，減少需要比較的記錄對(duì)數(shù)目以及如何提高對(duì)象識(shí)別的準(zhǔn)確率，優(yōu)化兩條記錄相似度的計(jì)算公式是對(duì)象識(shí)別技術(shù)的主要研究?jī)?nèi)容。該文分析了近些年對(duì)象識(shí)別技術(shù)的發(fā)展，給出了在效率可擴(kuò)展性、屬性值相似度的判斷、記錄對(duì)相似性的判斷、集合模型相似性的判斷等方面相關(guān)的研究方法和存在的研究問(wèn)題。