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

摘要：由于網(wǎng)絡(luò)信息的分散性，基于不同數(shù)據(jù)源的數(shù)據(jù)集成是目前非常重要應(yīng)用領(lǐng)域。對(duì)象識(shí)別工作是與信息領(lǐng)域中的應(yīng)用密切相關(guān)的。不同的應(yīng)用系統(tǒng)會(huì)有不同的對(duì)象識(shí)別優(yōu)化工作。對(duì)象識(shí)別的有效程度決定了數(shù)據(jù)集成后形成的全局?jǐn)?shù)據(jù)庫(kù)的質(zhì)量。文中全面的介紹了目前比較經(jīng)典的幾種識(shí)別模型，并對(duì)其進(jìn)行了深入的分析。

關(guān)鍵詞:對(duì)象識(shí)別；上下文相關(guān)；多層聯(lián)系；依賴關(guān)系

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

Study of Object Identification Model

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

(1.Anshan Radio and Television Bureau, Anshan 114001, China; 2. Beijing Baidu Network Technology Co., Ltd.,Beijing 100080, China) Abstract：Because of the dispersion of the network information based on different data sources, integration is a very important application areas. Object recognition work is closely related to the application in the field of information. Different applications have different object recognition optimization task. The object identification determines the quality of the global database. Comprehensive introduction to sever? al classic recognition model, and conducted in-depth analysis have.

Key words：object identification; context-sensitive；multi-layer contact；dependencies

1概述

由于存在于網(wǎng)絡(luò)中的信息自身所具有的分散性，基于網(wǎng)絡(luò)信息的數(shù)據(jù)集成是基于WEB的一個(gè)非常重要的應(yīng)用。但是，不同的數(shù)據(jù)源對(duì)于對(duì)象的描述往往不盡相同，同一對(duì)象在不同時(shí)間段的屬性也會(huì)有不同。因此，基于不同數(shù)據(jù)源的數(shù)據(jù)集成中對(duì)象識(shí)別是目前的一個(gè)研究熱點(diǎn)。他所研究的主要問(wèn)題是如何判斷哪些記錄對(duì)應(yīng)著同一個(gè)對(duì)象。對(duì)象識(shí)別屬于數(shù)據(jù)清洗的過(guò)程，一個(gè)數(shù)據(jù)庫(kù)只有進(jìn)行完對(duì)象識(shí)別才能很好的進(jìn)行分析。在信息集成中構(gòu)建統(tǒng)一數(shù)據(jù)庫(kù)的過(guò)程尤其需要對(duì)象識(shí)別。最初也正是由于需要識(shí)別多個(gè)數(shù)據(jù)源中的數(shù)據(jù)的匹配問(wèn)題才提出了對(duì)象識(shí)別。

對(duì)象識(shí)別工作是與信息領(lǐng)域中的應(yīng)用密切相關(guān)的。不同的應(yīng)用系統(tǒng)會(huì)有不同的對(duì)象識(shí)別優(yōu)化工作。但是，從整體上來(lái)講，對(duì)象識(shí)別工作可以分成兩個(gè)部分：如何計(jì)算記錄間的相似度和如何減少比較的數(shù)量。在計(jì)算記錄間的相似度時(shí)，大量的研究工作集中在如何計(jì)算對(duì)應(yīng)屬性的相似度上，然后使用一定的公式合成各個(gè)屬性的相似度。減少比較的數(shù)量，可以加快對(duì)象識(shí)別的進(jìn)行。

2對(duì)象識(shí)別模型

隨著計(jì)算機(jī)的應(yīng)用越來(lái)越廣泛，信息集成也越來(lái)越多，導(dǎo)致在數(shù)據(jù)庫(kù)中進(jìn)行對(duì)象識(shí)別的需求也越來(lái)越多。因此近年來(lái)數(shù)據(jù)庫(kù)中進(jìn)行對(duì)象識(shí)別的技術(shù)收到研究人員的廣泛關(guān)注，已經(jīng)開(kāi)發(fā)出來(lái)了大量的系統(tǒng)，提出了大量的模型。

2.1上下文相關(guān)的對(duì)象識(shí)別

文獻(xiàn)[1]是新加坡國(guó)立大學(xué)的研究工作，提出采用作者表象的上下文屬性來(lái)進(jìn)行對(duì)象識(shí)別，判斷兩個(gè)不同名的表象是否對(duì)應(yīng)同一個(gè)人。在論文數(shù)據(jù)庫(kù)中，作者表象的信息非常有限，在大部分情況下只是一個(gè)名字，沒(méi)有郵箱，身份證號(hào)碼等區(qū)別信息。Mong Li Lee等人第一次提出了“上下文屬性”（context attributes）的概念，也就是在論文數(shù)據(jù)庫(kù)中，論文的標(biāo)題、發(fā)表時(shí)間，所屬國(guó)際會(huì)議（雜志）、作者、出版社等屬性中，到底哪些屬性和要識(shí)別的作者屬性是相關(guān)的。只有識(shí)別出相關(guān)的屬性后，才能利用這些相關(guān)屬性進(jìn)行對(duì)象識(shí)別。

論文中提出了采用關(guān)聯(lián)規(guī)則來(lái)查找屬性值之間的相關(guān)性：一個(gè)屬性的某個(gè)值與其他屬性的某個(gè)值是否經(jīng)常共同出現(xiàn)。在查找到的所有關(guān)聯(lián)規(guī)則中，如果某一個(gè)屬性的值和作者屬性的值會(huì)產(chǎn)生很多的關(guān)聯(lián)規(guī)則，那么這個(gè)屬性就是作者屬性的一個(gè)相關(guān)屬性。例如，作者A和作者B經(jīng)常一塊出現(xiàn)，作者C和作者D經(jīng)常一塊出現(xiàn)。這樣的規(guī)則頻繁出現(xiàn)，可以知道合作者就是作者的關(guān)聯(lián)屬性。在判斷過(guò)程中，由于一個(gè)作者通常會(huì)參加多個(gè)國(guó)際會(huì)議，作者和國(guó)際會(huì)議之間的支持度不是很高。例如，"Andrew McCallum"參加的國(guó)際會(huì)議包括"SIGKDD"，"ICML"和“NIPS”等。但是，"SIGKDD"、"ICML"和“NIPS”等國(guó)際會(huì)議都在相近的研究領(lǐng)域中。論文中提出由領(lǐng)域?qū)＜医o定國(guó)際會(huì)議對(duì)應(yīng)的研究領(lǐng)域概念層次樹(shù)，如圖1所示，然后判斷作者和研究領(lǐng)域之間是否存在關(guān)聯(lián)規(guī)則。

（2-8）

利用這樣的連通模型，以最大連通子圖為中心的眾多連通子圖構(gòu)成相關(guān)網(wǎng)頁(yè)的集合，而其他的網(wǎng)頁(yè)就可以認(rèn)為是不相關(guān)網(wǎng)頁(yè)。

除了利用頁(yè)面之間的超鏈接關(guān)系，作者提出利用BIB（Bootstrapped Information Bottleneck）聚類(lèi)方法對(duì)于眾多的網(wǎng)頁(yè)根據(jù)內(nèi)容進(jìn)行聚類(lèi)。在檢索出的網(wǎng)頁(yè)中，相似的文檔應(yīng)該具有類(lèi)似的關(guān)鍵詞，而類(lèi)似關(guān)鍵詞的文檔分布也大致相同。在計(jì)算網(wǎng)頁(yè)的聚類(lèi)時(shí)，首先把所有的關(guān)鍵詞放入一個(gè)大的聚類(lèi)中，同時(shí)每一篇文檔都作為一個(gè)獨(dú)立的聚類(lèi)。然后，關(guān)鍵詞的聚類(lèi)根據(jù)他們?cè)谖臋n中的分布進(jìn)行分裂，而文檔根據(jù)他們對(duì)應(yīng)關(guān)鍵詞的特點(diǎn)進(jìn)行合并。這樣，兩個(gè)聚類(lèi)方向互相進(jìn)行啟發(fā)，直到聚類(lèi)完成。

采用上面的兩種方法單獨(dú)建立的聚類(lèi)結(jié)果，可以進(jìn)行合并。在BIB聚類(lèi)方法中，選擇和超鏈接分析中的最大連通子圖大小最相似的聚類(lèi)C，利用和這個(gè)聚類(lèi)C存在覆蓋關(guān)系的鏈接分析中的聚類(lèi)，生成一個(gè)新的聚類(lèi)0*C作為最大連通子圖聚類(lèi)。使用0*C替換公式（2-8）中的0C，可以獲得更加準(zhǔn)確的相關(guān)網(wǎng)頁(yè)結(jié)果。

在大量的基于不同數(shù)據(jù)源的數(shù)據(jù)集成應(yīng)用中，對(duì)象識(shí)別的準(zhǔn)確性直接決定了集成后獲得的全局?jǐn)?shù)據(jù)庫(kù)的可用性。該文比較全面的介紹了目前對(duì)象識(shí)別問(wèn)題中研究人員提出的典型識(shí)別模型，包括：上下文相關(guān)的對(duì)象識(shí)別、基于多層聯(lián)系的對(duì)象識(shí)別、基于依賴關(guān)系的對(duì)象識(shí)別、利用基于輔助數(shù)據(jù)源的對(duì)象識(shí)別、利用網(wǎng)絡(luò)信息的對(duì)象識(shí)別模型。并對(duì)上述識(shí)別模型進(jìn)行了比較深入的分析。

[1] Lee M, Hsu W,Kothari V. Cleaning the spurious links in data[J]. IEEE Intelligent Systems, 2004.

[2] Glen Jeh,Widom J. SimRank: A measure of structural-context similarity[C].Proc. Of SIGKDD, 2010.

[3] Xi W, Fox E A, Fan W.SimFusion: Measuring Similarity using Unified Relationship Matrix[C]. Proc. of SIGIR, 2005.

[4] Xi W, Fox E A, Fan W.SimFusion: Measuring Similarity using Unified Relationship Matrix[C].Proc. of SIGIR, 2008.

[5] Dmitri V Kalashnikov,Sharad Mehrotra,Zhaoqi Chen.Exploiting relationships for domain-independent data cleaning[C].SIAM Internation? al Conference on Data Mining (SIAM SDM), 2005.

[6] Dong X, Halevy A, Madhavan J.Reference econciliation in Complex Information Spaces[C].Proc. Of SIGMOD, 2008.

[7] Michalowski M,Thakkar S,Knoblock C A..Exploiting secondary sources for unsupervised record linkage[C].IIWeb, 2008.

[8] Bekkerman R, McCallum A.Disambiguating Web Appearances of People in a Social Network. [C].Proc. of the WWW, 2005.