利用二次歸并的Deep Web實體匹配方法

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

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

中圖分類號：TP391； TP311

文獻標志碼：A

0引言

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

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

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

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

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

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

1.2基本思想

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

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

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

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

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

因此，從實現目標上可以將DWEMM-TM模型分成兩個階段：第一階段，利用簡單有效的方法，快速找出對象間的Y匹配和N匹配，歸并Y匹配關系，刪除N匹配關系，形成簇內相似值極高的小型類簇集，其目標是準確、高效；第二階段，利用簇內對象間的消息傳遞以及對象間屬性相似值的計算，進一步確定P匹配關系的最終結果并更新類簇集，其目標是提高系統的查全率。

1.3系統框架

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

2結構轉換器

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

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

3關系識別器

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

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

3.2剪枝

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

3.3初步歸并

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

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

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

4屬性匹配器

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

4.1屬性權重計算

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

在算法3的輸入參數中，limit是一個用來判斷兩個比較對象是否相匹配的閾值（其值由實驗經驗確定），當對象間的相似值超過該閾值時，則認為匹配，并進入相應的歸并環節。在算法3的返回結果中，Clusters是由多個對象構成一個類簇的類簇集，selfCluster則表示只有一個對象的類簇集（即自匹配集），兩者共同組成實體集R（E）。

5實驗結果與分析

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

5.1閾值limit對DWEMM-TM的影響

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

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

5.2DWEMM-TM性能評測

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

2）類簇歸并：類簇歸并的目標是提高系統的查全率。fahl、kibl、utgo三個數據子集中出現頻率最高的3個屬性分別是date、author和title，它們的出現頻率值將作為相應子集屬性權重歸一化的標準；而算法3中所涉及的相似性判斷閾值limit，根據對圖2的分析，最終設置為0.85。各數據子集的評測結果如表2所示。

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

5.3DWEMM-TM與WEP方法的比較

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

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

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

6結語

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

參考文獻：

[1]陳麗君，林懷忠.一種用于深層網接口集成的模式匹配方法[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]崔曉軍，肖紅宇，丁立新.基于距離的自適應Web數據庫記錄匹配方法[J].武漢大學學報（理學版），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神經網絡的Deep Web實體識別方法[J].計算機應用，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]李亞坤，王宏志，高宏，等.基于實體描述屬性技術的XML重復對象檢測方法[J].計算機學報，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]寇月，申德榮，李冬，等.一種基于語義及統計分析的Deep Web實體識別機制[J].軟件學報，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.