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

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

中圖分類號：TP391； TP311

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

0引言

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

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

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

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

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

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

1.2基本思想

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

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

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

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

4）通過對象間的消息傳遞機制能有效提高實體匹配的查全率[4]。

因此，從實現(xiàn)目標(biāo)上可以將DWEMM-TM模型分成兩個階段：第一階段，利用簡單有效的方法，快速找出對象間的Y匹配和N匹配，歸并Y匹配關(guān)系，刪除N匹配關(guān)系，形成簇內(nèi)相似值極高的小型類簇集，其目標(biāo)是準(zhǔn)確、高效；第二階段，利用簇內(nèi)對象間的消息傳遞以及對象間屬性相似值的計算，進一步確定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)系識別器（Matching Identifier，MI）和屬性匹配器（Attribute Matcher，AM）三部分組成。DWEMM-TM模型的輸入為按實體對象組織的對象集R（O），經(jīng)結(jié)構(gòu)轉(zhuǎn)換器SC轉(zhuǎn)換后，輸出按對象屬性組織的屬性集R（A），由此，具有相同屬性值的對象就被聚集到同一個對象列表Ai里；隨后關(guān)系識別器MI通過掃描對象屬性集R（A）中的每個對象列表Ai，統(tǒng)計計算對象間的匹配度，獲得初步匹配關(guān)系，并濾除N匹配，歸并Y匹配，從而產(chǎn)生實體類簇集R（C）；屬性匹配器AM則對P匹配關(guān)系進行判斷，借助于類簇集R（C）內(nèi)部的消息傳遞，以及對象屬性值間的相似值，重新確立P匹配關(guān)系的最終取值，同時更新類簇集R（C），當(dāng)判斷完所有P匹配關(guān)系后便可獲得模型的最終輸出，即實體類集R（E）。

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

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

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

3關(guān)系識別器

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

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

3.2剪枝

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

3.3初步歸并

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

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

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

4屬性匹配器

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

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

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

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

5實驗結(jié)果與分析

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

5.1閾值limit對DWEMM-TM的影響

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

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

5.2DWEMM-TM性能評測

1）初步歸并：初步歸并的目標(biāo)是快速、精準(zhǔn)。在完成匹配度值計算以后，需要對匹配度值較小的N匹配關(guān)系進行剪枝，剪枝閾值θ的選取原則是：能加快匹配速度且又不太會降低查全率和查準(zhǔn)率。實驗最終確定θ的值為0.2，相應(yīng)地，fahl、kibl、utgo三個數(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三個數(shù)據(jù)子集中出現(xiàn)頻率最高的3個屬性分別是date、author和title，它們的出現(xiàn)頻率值將作為相應(yīng)子集屬性權(quán)重歸一化的標(biāo)準(zhǔn)；而算法3中所涉及的相似性判斷閾值limit，根據(jù)對圖2的分析，最終設(shè)置為0.85。各數(shù)據(jù)子集的評測結(jié)果如表2所示。

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

5.3DWEMM-TM與WEP方法的比較

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

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

6結(jié)語

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

參考文獻：

[1]陳麗君，林懷忠.一種用于深層網(wǎng)接口集成的模式匹配方法[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ù)庫記錄匹配方法[J].武漢大學(xué)學(xué)報（理學(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實體識別方法[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ù)的XML重復(fù)對象檢測方法[J].計算機學(xué)報，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)計分析的Deep Web實體識別機制[J].軟件學(xué)報，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.