利用二次歸并的Deep Web實(shí)體匹配方法

摘要：針對(duì)權(quán)重邊剪枝（WEP）方法在準(zhǔn)確率和匹配效率等方面的不足，通過引入自匹配和歸并概念，提出一種基于二次歸并的Deep Web實(shí)體匹配方法。首先，提取各對(duì)象的屬性值，并按屬性值重組對(duì)象，使具有相同屬性值的對(duì)象聚集在一起，實(shí)現(xiàn)塊的有效劃分；其次，計(jì)算塊內(nèi)各對(duì)象間的匹配度，并據(jù)此進(jìn)行剪枝、自匹配檢測(cè)、歸并，輸出初步類簇；最后，以初步類簇為基礎(chǔ)，利用簇內(nèi)對(duì)象間傳遞的消息以及對(duì)象屬性相似值，進(jìn)一步挖掘匹配關(guān)系，觸發(fā)新一輪的類簇歸并與更新。實(shí)驗(yàn)結(jié)果表明，與WEP方法相比，所提方法通過自匹配檢測(cè)，自動(dòng)區(qū)分匹配關(guān)系并采取合適的匹配策略，使歸并過程逐漸精化，提高了匹配準(zhǔn)確率；通過分塊、剪枝，有效縮減了匹配空間，提高了系統(tǒng)運(yùn)行效率。

關(guān)鍵詞：二次歸并；Deep Web；實(shí)體匹配； 類簇；相似值

中圖分類號(hào)：TP391； TP311

文獻(xiàn)標(biāo)志碼：A

0引言

與Surface Web相比，Deep Web資源具有數(shù)量更大、質(zhì)量更優(yōu)、內(nèi)容更精確、使用價(jià)值更高、增長(zhǎng)迅速等特點(diǎn)。接口集成是訪問Deep Web資源的主要途徑，但由于Web的自治性和動(dòng)態(tài)性，使得Web數(shù)據(jù)庫(kù)的數(shù)據(jù)冗余度高，異構(gòu)現(xiàn)象嚴(yán)重，給接口集成造成較大困擾。實(shí)體匹配（也稱實(shí)體識(shí)別、記錄匹配等）是一種在數(shù)據(jù)集合中發(fā)現(xiàn)同一實(shí)體不同描述的技術(shù)，可用于數(shù)據(jù)庫(kù)記錄的錯(cuò)誤檢測(cè)、重復(fù)檢測(cè)、不一致數(shù)據(jù)發(fā)現(xiàn)等，以消除數(shù)據(jù)重復(fù)、數(shù)據(jù)不一致等異構(gòu)現(xiàn)象。

與模式匹配類似，實(shí)體匹配的關(guān)鍵要做好兩項(xiàng)工作：評(píng)判依據(jù)的選擇和匹配方法的運(yùn)用[1]；同時(shí)，鑒于Deep Web的海量數(shù)據(jù)，有效的匹配空間縮減策略也非常重要。早期的實(shí)體匹配主要專注于實(shí)體對(duì)間的匹配（見文獻(xiàn)[2]），近年來已逐漸發(fā)展為實(shí)體集間的匹配（collective entity matching）[3-6]，相關(guān)技術(shù)研究應(yīng)用也延伸到了知識(shí)庫(kù)、全球信息庫(kù)自動(dòng)構(gòu)建等眾多領(lǐng)域。評(píng)判依據(jù)方面，目前主要還是選用實(shí)體對(duì)象的屬性，并以自動(dòng)或半自動(dòng)方式迭代計(jì)算各屬性的權(quán)重[7-8]。匹配方法主要涉及機(jī)器學(xué)習(xí)、圖理論和啟發(fā)式思想等，如徐紅艷等[9]利用反向傳播（Back Propagation， BP）神經(jīng)網(wǎng)絡(luò)的自主學(xué)習(xí)特性，將語義塊相似度值作為輸入，訓(xùn)練習(xí)得實(shí)體匹配模型；Liu等[10]基于馬爾可夫邏輯網(wǎng)絡(luò)推理來發(fā)現(xiàn)屬性間內(nèi)在的相似依賴關(guān)系，以此提升記錄相似性判斷。匹配空間縮減主要有分塊和剪枝兩種方法，如李亞坤等[11]通過構(gòu)建屬性節(jié)點(diǎn)表實(shí)現(xiàn)塊的劃分，再用Max-Merge算法進(jìn)行聚類；Efthymiou等[12]設(shè)計(jì)了權(quán)重邊剪枝方法（Weighted Edge Pruning， WEP）

，其基于MapReduce思想，多次映射重構(gòu)塊圖以刪減冗余邊，再計(jì)算邊權(quán)重并以平均邊權(quán)重為閾值，對(duì)塊圖進(jìn)行剪枝。另外，寇月等[13]則利用文本屬性特征、語義信息、約束規(guī)則等多種信息，以逐步求精的方式進(jìn)行Deep Web實(shí)體匹配。

綜觀現(xiàn)有實(shí)體匹配方法，仍存在人工干預(yù)較多、匹配效率不高等問題。本文借鑒前人研究思路并結(jié)合聚類思想與WEP方法，

提出一種利用二次歸并進(jìn)行Deep Web實(shí)體匹配的方法（Deep Web Entity Matching Method based on Twice-Merging， DWEMM-TM）。

提出一種利用二次歸并技術(shù)進(jìn)行Deep Web實(shí)體匹配的方法TMM（【deep Web entity matching based on Twice-Merging Method）。

1.2基本思想

DWEMM-TM模型借鑒聚類思想，將實(shí)體匹配過程看作類簇歸并的過程，同時(shí)，綜合考慮以下研究發(fā)現(xiàn)而提出：

1）匹配關(guān)系可以分為三種：匹配（Y）、不匹配（N）和可能匹配（P）（以下分別簡(jiǎn)稱為Y匹配、N匹配和P匹配），而前兩者往往可以通過一些有效且高效的方法快速判定。

2）描述現(xiàn)實(shí)世界中同一個(gè)實(shí)體的不同數(shù)據(jù)對(duì)象很難在所有屬性上的取值都不同[11]。

3）如果將對(duì)象間相似值參照tf-idf（term frequency-inverse document frequency）思想進(jìn)行計(jì)算并排序，那么匹配對(duì)象和不匹配對(duì)象往往分布于該排序的兩端[8]。

4）通過對(duì)象間的消息傳遞機(jī)制能有效提高實(shí)體匹配的查全率[4]。

因此，從實(shí)現(xiàn)目標(biāo)上可以將DWEMM-TM模型分成兩個(gè)階段：第一階段，利用簡(jiǎn)單有效的方法，快速找出對(duì)象間的Y匹配和N匹配，歸并Y匹配關(guān)系，刪除N匹配關(guān)系，形成簇內(nèi)相似值極高的小型類簇集，其目標(biāo)是準(zhǔn)確、高效；第二階段，利用簇內(nèi)對(duì)象間的消息傳遞以及對(duì)象間屬性相似值的計(jì)算，進(jìn)一步確定P匹配關(guān)系的最終結(jié)果并更新類簇集，其目標(biāo)是提高系統(tǒng)的查全率。

1.3系統(tǒng)框架

DWEMM-TM模型的系統(tǒng)框架如圖1所示，由結(jié)構(gòu)轉(zhuǎn)換器（Structure Converter，SC）、關(guān)系識(shí)別器（Matching Identifier，MI）和屬性匹配器（Attribute Matcher，AM）三部分組成。DWEMM-TM模型的輸入為按實(shí)體對(duì)象組織的對(duì)象集R（O），經(jīng)結(jié)構(gòu)轉(zhuǎn)換器SC轉(zhuǎn)換后，輸出按對(duì)象屬性組織的屬性集R（A），由此，具有相同屬性值的對(duì)象就被聚集到同一個(gè)對(duì)象列表Ai里；隨后關(guān)系識(shí)別器MI通過掃描對(duì)象屬性集R（A）中的每個(gè)對(duì)象列表Ai，統(tǒng)計(jì)計(jì)算對(duì)象間的匹配度，獲得初步匹配關(guān)系，并濾除N匹配，歸并Y匹配，從而產(chǎn)生實(shí)體類簇集R（C）；屬性匹配器AM則對(duì)P匹配關(guān)系進(jìn)行判斷，借助于類簇集R（C）內(nèi)部的消息傳遞，以及對(duì)象屬性值間的相似值，重新確立P匹配關(guān)系的最終取值，同時(shí)更新類簇集R（C），當(dāng)判斷完所有P匹配關(guān)系后便可獲得模型的最終輸出，即實(shí)體類集R（E）。

2結(jié)構(gòu)轉(zhuǎn)換器

在Deep Web中，一個(gè)實(shí)體往往用有限的屬性，并以結(jié)構(gòu)化的形式進(jìn)行描述。例如，要描述一篇論文，通常會(huì)用到標(biāo)題、作者、日期等屬性。結(jié)合文獻(xiàn)[11]的觀察，代表相同實(shí)體的對(duì)象在屬性取值上也容易趨向相同，因此，具有相同屬性取值的對(duì)象，就更有可能描述著同一個(gè)實(shí)體。結(jié)構(gòu)轉(zhuǎn)換器的作用是把按對(duì)象組織的集合轉(zhuǎn)變?yōu)榘磳傩越M織，以使具有相同屬性值的對(duì)象聚合在一起，其目標(biāo)是讓匹配計(jì)算只在潛在的對(duì)象間進(jìn)行，有效降低時(shí)間復(fù)雜度。

不難看出，結(jié)構(gòu)轉(zhuǎn)換器實(shí)質(zhì)上是將R（O）中的對(duì)象進(jìn)行分塊，一個(gè)對(duì)象Oi可以被分到多個(gè)塊（也就是對(duì)象列表Ai）中。同時(shí)，分塊處理只需判斷屬性值是否相同，不涉及到屬性間的模式匹配問題，大大降低了計(jì)算復(fù)雜度。

3關(guān)系識(shí)別器

關(guān)系識(shí)別器的作用是通過計(jì)算對(duì)象間相同屬性值的相對(duì)共現(xiàn)次數(shù)獲取匹配度，并依此劃分匹配關(guān)系，將取值較低的N匹配關(guān)系濾除，取值較高的Y匹配關(guān)系進(jìn)行初步歸并，形成模型的粗略類簇集，其目標(biāo)是通過簡(jiǎn)單、高效的方式快速區(qū)分匹配關(guān)系，收縮匹配空間，提高系統(tǒng)的運(yùn)行效率。

關(guān)系識(shí)別器的處理可以分為匹配度計(jì)算、剪枝、初步歸并三個(gè)過程。

3.2剪枝

如前所述，一個(gè)對(duì)象雖然具有與其他對(duì)象共現(xiàn)的屬性值，但卻有可能并不代表同一個(gè)實(shí)體，比如，一篇論文的刊出年份、出版單位可能與其他論文相同，但它們有可能并不指向同一篇論文；同時(shí)，這些對(duì)象間的匹配度往往很低，通常也都屬于N匹配關(guān)系，為此，在計(jì)算完匹配度值后，用閾值θ對(duì)匹配度列表進(jìn)行剪枝，以刪減N匹配關(guān)系。剪枝閾值θ的值由實(shí)驗(yàn)最終確定為0.2。

3.3初步歸并

剪枝環(huán)節(jié)處理的是N匹配關(guān)系，初步歸并環(huán)節(jié)處理的則是Y匹配關(guān)系，基本思想是：對(duì)象間匹配度高的往往屬于Y匹配關(guān)系；當(dāng)匹配度值低于一個(gè)對(duì)象與一個(gè)已經(jīng)自匹配對(duì)象的匹配度值時(shí)，匹配關(guān)系會(huì)變得不確定起來，也即匹配關(guān)系進(jìn)入P匹配區(qū)域，還需要獲取更多的信息來進(jìn)一步分析判斷。

關(guān)系識(shí)別器的輸入是結(jié)構(gòu)轉(zhuǎn)換器的輸出，即對(duì)象屬性集R（A），其輸出為實(shí)體類簇集R（C）={C1，C2，…，Cn}，每一個(gè)類簇Ci={O1，O2，…，Om}代表著一個(gè)初步的實(shí)體類，其中包含著已匹配且指向同一個(gè)實(shí)體的對(duì)象Oi，|Ci|表示該類簇所匹配到的對(duì)象個(gè)數(shù)。

初步歸并算法roughMerge通過引入自匹配概念實(shí)現(xiàn)Y匹配與P匹配的自動(dòng)劃分，同時(shí)達(dá)成與后續(xù)類簇歸并環(huán)節(jié)的自動(dòng)轉(zhuǎn)接；其輸出R（C）僅包含已經(jīng)匹配的對(duì)象，其他未匹配對(duì)象將通過數(shù)據(jù)列表共享方式傳遞給屬性匹配器作進(jìn)一步判斷處理。

4屬性匹配器

關(guān)系識(shí)別器的輸出是一個(gè)粗略的實(shí)體類集，包含著還未充分歸并的類簇，需要屬性匹配器的再次歸并。屬性匹配器主要處理P匹配關(guān)系，其通過對(duì)象各相應(yīng)屬性相似值的計(jì)算，以及類簇內(nèi)的消息傳遞，進(jìn)一步挖掘潛在匹配對(duì)象，聚合相同的類簇，形成最終的匹配結(jié)果R（E）輸出，其目標(biāo)在于提高匹配的查全率。

4.1屬性權(quán)重計(jì)算

一個(gè)實(shí)體通常由多個(gè)屬性描述，不同屬性的辨識(shí)區(qū)分能力也不盡相同，越常見的屬性往往區(qū)分能力越強(qiáng)，應(yīng)該賦予更高的權(quán)重。為此，先統(tǒng)計(jì)每個(gè)屬性的出現(xiàn)頻率ti，再選取其中的最高頻率tmax進(jìn)行歸一化處理，可得每個(gè)屬性的權(quán)重：

在算法3的輸入?yún)?shù)中，limit是一個(gè)用來判斷兩個(gè)比較對(duì)象是否相匹配的閾值（其值由實(shí)驗(yàn)經(jīng)驗(yàn)確定），當(dāng)對(duì)象間的相似值超過該閾值時(shí)，則認(rèn)為匹配，并進(jìn)入相應(yīng)的歸并環(huán)節(jié)。在算法3的返回結(jié)果中，Clusters是由多個(gè)對(duì)象構(gòu)成一個(gè)類簇的類簇集，selfCluster則表示只有一個(gè)對(duì)象的類簇集（即自匹配集），兩者共同組成實(shí)體集R（E）。

5實(shí)驗(yàn)結(jié)果與分析

采用實(shí)體匹配常用的Cora數(shù)據(jù)集[14]作為實(shí)驗(yàn)測(cè)試數(shù)據(jù)。Cora是一個(gè)描述論文引用的數(shù)據(jù)集，其中含有utgo-labeled、kibl-labeled、fahl-labled三個(gè)子集數(shù)據(jù)文件，共計(jì)1882條記錄。每個(gè)文件記錄著論文的author、title、date等信息，并已做好是否為相同論文的標(biāo)注，共計(jì)有203篇論文。評(píng)價(jià)指標(biāo)采用信息檢索領(lǐng)域的查準(zhǔn)率、查全率和F值。

5.1閾值limit對(duì)DWEMM-TM的影響

類簇歸并中判斷對(duì)象相似性的閾值limit對(duì)系統(tǒng)性能有重要影響。直覺上，閾值越高，要求越嚴(yán)，性能會(huì)更好。圖2顯示了不同閾值對(duì)DWEMM-TM性能的影響。

從圖2可以看出，隨著limit取值的增大，查準(zhǔn)率逐漸上升，查全率有所下降；當(dāng)limit=0.85時(shí)，兩者有較好的平衡，F(xiàn)值最大，DWEMM-TM性能最優(yōu)；當(dāng)limit=1時(shí)，由于閾值過高，原本匹配的對(duì)象未能匹配，導(dǎo)致查全率有明顯下降。

5.2DWEMM-TM性能評(píng)測(cè)

1）初步歸并：初步歸并的目標(biāo)是快速、精準(zhǔn)。在完成匹配度值計(jì)算以后，需要對(duì)匹配度值較小的N匹配關(guān)系進(jìn)行剪枝，剪枝閾值θ的選取原則是：能加快匹配速度且又不太會(huì)降低查全率和查準(zhǔn)率。實(shí)驗(yàn)最終確定θ的值為0.2，相應(yīng)地，fahl、kibl、utgo三個(gè)數(shù)據(jù)子集的剪枝率（=剪掉的枝數(shù)/剪枝前的總枝數(shù)）分別為59%、54.7%和63.3%。各數(shù)據(jù)子集經(jīng)初步歸并后的查準(zhǔn)率、查全率和F值如表1所示。

2）類簇歸并：類簇歸并的目標(biāo)是提高系統(tǒng)的查全率。fahl、kibl、utgo三個(gè)數(shù)據(jù)子集中出現(xiàn)頻率最高的3個(gè)屬性分別是date、author和title，它們的出現(xiàn)頻率值將作為相應(yīng)子集屬性權(quán)重歸一化的標(biāo)準(zhǔn)；而算法3中所涉及的相似性判斷閾值limit，根據(jù)對(duì)圖2的分析，最終設(shè)置為0.85。各數(shù)據(jù)子集的評(píng)測(cè)結(jié)果如表2所示。

從表1、2可以看出，負(fù)責(zé)初步歸并的關(guān)系識(shí)別器MI具有很高的查準(zhǔn)率，但查全率卻不夠理想；其結(jié)果經(jīng)運(yùn)行類簇歸并的屬性匹配器AM處理后，查全率有較大提高，但查準(zhǔn)率有所下降。進(jìn)一步深入分析可知：1）MI的查準(zhǔn)率并沒有達(dá)到100%，這是因?yàn)闇y(cè)試數(shù)據(jù)集本身含有臟數(shù)據(jù)，仍存在一小部分實(shí)際為同一個(gè)實(shí)體，卻被標(biāo)注為不同實(shí)體的情況；2）有部分?jǐn)?shù)據(jù)雖然描述著不同實(shí)體，但其相似值極高，給利用屬性相似值進(jìn)行匹配的AM帶來明顯干擾，降低了查準(zhǔn)率；3）fahl數(shù)據(jù)子集的整體性能要低于其他兩個(gè)，原因是其中的〈date〉屬性出現(xiàn)頻率較高，部分對(duì)象的年和月份分成兩次出現(xiàn)，根據(jù)式（3）的計(jì)算會(huì)降低其他重要屬性的權(quán)重值，導(dǎo)致部分匹配關(guān)系誤判，從而影響了整體性能。

5.3DWEMM-TM與WEP方法的比較

為了驗(yàn)證DWEMM-TM方法的有效性，將其與文獻(xiàn)[12]中的WEP方法進(jìn)行比較，WEP方法的邊權(quán)重采用JS（Jaccard Scheme）計(jì)算方式。

DWEMM-TM與WEP的查準(zhǔn)率、查全率和F值如表3所示。從表3可以看出，DWEMM-TM模型的查全率不及WEP方法，但查準(zhǔn)率明顯高于WEP方法，從綜合指標(biāo)F值來看，DWEMM-TM仍然優(yōu)于WEP方法。

DWEMM-TM與WEP的CPU執(zhí)行時(shí)間如圖3所示。從圖3可以發(fā)現(xiàn)，DWEMM-TM和WEP均隨著匹配對(duì)象數(shù)量規(guī)模的擴(kuò)大而呈線性增長(zhǎng)，但DWEMM-TM模型的增長(zhǎng)速度更加緩慢一些，其原因主要是由于DWEMM-TM模型的關(guān)系識(shí)別器MI采用了高效的刪減策略與匹配方法，有效地縮減了匹配空間，大大減少執(zhí)行代價(jià)相對(duì)較高的屬性匹配器AM需要處理的數(shù)據(jù)量，從而獲得了較好的運(yùn)行效率。

6結(jié)語

Deep Web數(shù)據(jù)的迅速增長(zhǎng)對(duì)實(shí)體匹配的效率和性能提出了更高要求。本文借鑒聚類思想，將實(shí)體匹配看作類簇歸并過程，提出基于二次歸并的Deep Web實(shí)體匹配方法DWEMM-TM，將不同的匹配關(guān)系分階段交予不同的處理模塊，使匹配逐漸精化，并通過引入自匹配，實(shí)現(xiàn)兩次歸并間的自動(dòng)轉(zhuǎn)接和不同匹配策略的自動(dòng)選擇。實(shí)驗(yàn)結(jié)果表明，DWEMM-TM方法在縮減匹配空間、降低復(fù)雜數(shù)據(jù)處理量和提高匹配精度方面有不錯(cuò)表現(xiàn)，達(dá)到了性能與效率的雙重提高。

參考文獻(xiàn)：

[1]陳麗君，林懷忠.一種用于深層網(wǎng)接口集成的模式匹配方法[J].計(jì)算機(jī)工程，2012，38（12）：42-44. （CHEN L J， LIN H Z. Pattern matching method for Deep Web interface integration [J]. Computer Engineering， 2012， 38（12）： 42-44.）

[2]KPCKE H， RAHM E. Frameworks for entity matching： a comparison [J]. Data & Knowledge Engineering， 2010， 69（2）： 197-210.

[3]HAN X， SUN L， ZHAO J. Collective entity linking in Web text： a graph-based method [C]// SIGIR 11： Proceedings of the 34th Annual ACM SIGIR Conference on Research and development in Information Retrieval. New York： ACM， 2011： 765-774.

[4]RASTOGI V， DALVI N， GAROFALAKIS M. Large-scale collective entity matching [J]. Proceedings of the VLDB Endowment， 2011， 4（4）： 208-218.

[5]WANG Z， LI J， WANG Z， et al. Cross-lingual knowledge linking across Wiki knowledge bases [C]// WWW 12： Proceedings of the 21st International Conference on Word Wide Web. New York： ACM， 2012： 459-468.

[6]FAN J， LU M， OOI B C， et al. A hybrid machine-crowdsourcing system for matching Web tables [C]// Proceedings of the 2014 IEEE 30th International Conference on Data engineering. Washington， DC： IEEE Computer Society， 2014： 976-987.

[7]崔曉軍，肖紅宇，丁立新.基于距離的自適應(yīng)Web數(shù)據(jù)庫(kù)記錄匹配方法[J].武漢大學(xué)學(xué)報(bào)（理學(xué)版），2012，58（1）：89-94. （CUI X J， XIAO H Y， DING L X. Distance-based adaptive record matching for Web database [J]. Journal of Wuhan University （Science Edition）， 2012， 58（1）： 89-94.）

[8]LIU W， MENG X. A holistic solution for duplicate entity identification in deep Web data integration [C]// SKG 10： Proceedings of the 2010 Sixth International Conference on Semantics， Knowledge and Grids. Washington， DC： IEEE Computer Society， 2010： 267-274.

[9]徐紅艷，黨曉婉，馮勇，等.基于BP神經(jīng)網(wǎng)絡(luò)的Deep Web實(shí)體識(shí)別方法[J].計(jì)算機(jī)應(yīng)用，2013，33（3）：776-779. （XU H Y， DANG X W， FENG Y， et al. Method of Deep Web entities identification based on BP network [J]. Journal of Computer Applications， 2013， 33（3）： 776-779.）

[10]LIU W， MENG X， YANG J， et al. Duplicate identification in Deep Web data integration [C]// WAIM 10： Proceedings of the 11th International Conference on Web-age Information Management， LNCS 6184. Berlin： Springer-Verlag， 2010： 5-17.

[11]李亞坤，王宏志，高宏，等.基于實(shí)體描述屬性技術(shù)的XML重復(fù)對(duì)象檢測(cè)方法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（11）：2131-2141. （LI Y K， WANG H Z， GAO H， et al. Efficient entity resolution on XML data based on entity-describe-attribute [J]. Chinese Journal of Computers， 2011， 34（11）： 2131-2141.）

[12]EFTHYMIOU V， PAPADAKIS G A， PAPASTEFANATOS G， et al. Parallel meta-blocking： realizing scalable entity resolution over large， heterogeneous data [C]// Proceedings of the IEEE 2015 4th International Conference on Big Data. Piscataway， NJ： IEEE， 2015： 411-420.

[13]寇月，申德榮，李冬，等.一種基于語義及統(tǒng)計(jì)分析的Deep Web實(shí)體識(shí)別機(jī)制[J].軟件學(xué)報(bào)，2008，19（2）：194-208. （KOU Y， SHEN D R， LI D， et al. A Deep Web entity identification mechanism based on semantics and statistical analysis [J]. Journal of Software， 2008， 19（2）： 194-208.）

[14]MCCALLUM A. Cora citation matching [EB/OL]. （2004-02-09） [2015-08-22]. http：//www.cs.umass.edu/～mccallum/data/cora-refs.tar.gz.