范紅杰，柳軍飛，周魯東，麻志毅.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京00872.北京大學(xué)軟件工程國家工程研究中心，北京0087

?

多策略相似度整合的XML模式匹配方法*

范紅杰1，柳軍飛2+，周魯東1，麻志毅1
1.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871
2.北京大學(xué)軟件工程國家工程研究中心，北京100871

* The National Natural Science Foundation of China under Grant No. 61272159 (國家自然科學(xué)基金).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-09-02, http://www.cnki.net/kcms/detail/11.5602.TP.20150902.1338.012.html

范紅杰，柳軍飛，周魯東，等.多策略相似度整合的XML模式匹配方法[J].計(jì)算機(jī)科學(xué)與探索，2016，10（1）：14-24.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0014-11

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：模式匹配用于發(fā)現(xiàn)不同數(shù)據(jù)源中概念之間的語義對應(yīng)關(guān)系，已成為數(shù)據(jù)集成、數(shù)據(jù)交換等領(lǐng)域的研究熱點(diǎn)。研究者提出了大量的基于XML模式匹配方法，從而可以識別XML中數(shù)據(jù)的語義對應(yīng)關(guān)系。XML模式匹配存在著一些挑戰(zhàn)，例如如何將節(jié)點(diǎn)和結(jié)構(gòu)匹配進(jìn)行綜合考慮，如何有效擬合多種相似度等。面對如上問題，針對XML節(jié)點(diǎn)和結(jié)構(gòu)兩方面進(jìn)行相似度計(jì)算，得到相似度矩陣后整合這兩個(gè)方面的相似度。隨后通過多種策略組合和優(yōu)化算法進(jìn)行擬合，以得到優(yōu)化的匹配結(jié)果。最后，通過基準(zhǔn)測試平臺對比，該方法相比于經(jīng)典的模式匹配方法具有較高的精確率和召回率。

關(guān)鍵詞：數(shù)據(jù)交換；模式匹配；可擴(kuò)展標(biāo)記語言（XML）；相似度度量；多策略組合

1　引言

可擴(kuò)展標(biāo)記語言（extensible markup language，XML）由于具有自描述能力和組織數(shù)據(jù)的靈活性，已經(jīng)成為信息表示和數(shù)據(jù)交換的標(biāo)準(zhǔn)[1]，努力開發(fā)高性能的技術(shù)來有效地管理大型XML數(shù)據(jù)變得尤為重要。開發(fā)這種技術(shù)的障礙之一是有效識別和匹配節(jié)點(diǎn)之間的語義對應(yīng)關(guān)系，這種語義識別和對應(yīng)過程被稱為模式匹配。模式匹配[2-3]不但在理論研究中已經(jīng)得到了廣泛的關(guān)注，而且在數(shù)據(jù)共享和數(shù)據(jù)交換的實(shí)際應(yīng)用中同樣起著核心作用。例如在數(shù)據(jù)集成中多個(gè)異構(gòu)模式之間的識別和表征模式之間的相互關(guān)系；在基于XML的數(shù)據(jù)轉(zhuǎn)換中來確定XML數(shù)據(jù)之間的語義對應(yīng)關(guān)系，將源對象映射到目標(biāo)對象。

隨著XML模式文件的不斷增多，XML模式匹配已經(jīng)成為一個(gè)亟待解決的問題。由于模式匹配固有的復(fù)雜性，目前模式匹配主要依靠領(lǐng)域?qū)＜襾硎止ぬ幚恚謩悠ヅ湫释容^低，尤其在面對大型和動態(tài)的模式匹配環(huán)境時(shí)更是如此。在這種情況下，有效、自動地實(shí)現(xiàn)匹配過程已成為必然趨勢。

自2001年開始，Rahm等人[4]將模式匹配作為特定領(lǐng)域加以研究，分析已經(jīng)存在的工作，并認(rèn)為可以將其他領(lǐng)域內(nèi)的工作尤其是相似度技術(shù)結(jié)合到模式匹配中。模式匹配的相關(guān)專著[5-6]和綜述[4，7]，就匹配框架、匹配方法等進(jìn)行了深入的討論。文獻(xiàn)[8]研究了XML樹和語法樹之間的編輯距離，并分析了算法執(zhí)行的效率；文獻(xiàn)[9]基于TF-IDF（term frequencyinverse document frequency）信息檢索方式，將所有需要匹配的模式元素整合到不同文檔中，通過文檔內(nèi)容相似度匹配方法來處理；文獻(xiàn)[10]將所有需要匹配的概念通過本體進(jìn)行映射，完成概念之間的相似度計(jì)算。人們已經(jīng)在相關(guān)系統(tǒng)或者平臺中提出了模式匹配算法，例如Similarity Flooding[9]、COMA++[11]等。這些系統(tǒng)的共同特點(diǎn)是它們不但考慮模式節(jié)點(diǎn)特征，還通過節(jié)點(diǎn)之間的關(guān)系來確定相似性，不同的是它們沒有利用多種組合策略來擬合已得到的相似度度量結(jié)果。模式匹配在匹配策略方面也各有不同。清華大學(xué)李涓子等人[12]使用自調(diào)整匹配策略選擇需要合并的匹配模塊，從而影響合并結(jié)果；文獻(xiàn)[13]將模式匹配轉(zhuǎn)換為多標(biāo)記圖匹配問題，提出多標(biāo)記圖的相似性度量方法；文獻(xiàn)[14]通過快速匹配策略消除已經(jīng)不可能進(jìn)行匹配的元素，從而縮小匹配搜索空間；文獻(xiàn)[15-16]使用先期匹配結(jié)果作為輔助信息，在后期的匹配中提高匹配效率。Algergawy等人[17]也通過不同的側(cè)面來計(jì)算相似度，例如計(jì)算文檔注釋、子孫節(jié)點(diǎn)等相似度，采用手工調(diào)整的方式來擬合相似度度量結(jié)果。

盡管如此，目前XML模式匹配中仍然存在著一些問題和挑戰(zhàn)[18]：首先大部分匹配算法主要考慮模式之間的整體相似度，忽略了獨(dú)立元素之間的相似度；其次擬合這些相似度是瑣碎的，目前幾乎所有現(xiàn)有的匹配系統(tǒng)通過簡單策略或者線性組合的方式合并，并不能充分考慮需要合并的相似度之間的相互依存關(guān)系。針對如上挑戰(zhàn)，本文的主要思路是首先通過不同的方式分別計(jì)算各節(jié)點(diǎn)和結(jié)構(gòu)的相似度，得到相似度矩陣后，通過多種策略組合和優(yōu)化算法進(jìn)行擬合，并采用啟發(fā)式隨機(jī)搜索算法來解決大規(guī)模解空間的組合優(yōu)化問題，以得到優(yōu)化的匹配結(jié)果。

本文的主要貢獻(xiàn)是：

（1）深入研究了XML模式匹配特征，展示了不同層面的XML相似度度量方法，包括基于節(jié)點(diǎn)名稱、類型等多種相似度度量方法。

（2）為避免單一相似度度量方法的局限性，采用多策略相似度整合方式擬合所得到的相似度矩陣，以提高匹配質(zhì)量。

（3）在整合策略中使用啟發(fā)式隨機(jī)搜索算法，解決大規(guī)模解空間的組合優(yōu)化，避免了人工擬合或窮舉所有權(quán)值。

（4）通過基準(zhǔn)測試平臺對比，相比于經(jīng)典的模式匹配工具，多策略的相似度整合方法具有較高的精確度和召回率。

2　相關(guān)定義

定義1（數(shù)據(jù)交換）數(shù)據(jù)交換[3]可以描述如下：對于給定有限源實(shí)例數(shù)據(jù)I，在有限的目標(biāo)實(shí)例數(shù)據(jù)J中查找的關(guān)系對滿足源對目標(biāo)的函數(shù)依賴，且J自身滿足目標(biāo)函數(shù)依賴，這樣的目標(biāo)實(shí)例數(shù)據(jù)J被稱為源實(shí)例數(shù)據(jù)I的匹配解。換言之，如圖1所示，所有對于目標(biāo)模式T的查詢都可以等價(jià)為對于源模式S的查詢。

Fig.1 General setting of data exchange圖1　數(shù)據(jù)交換通用表示

模式匹配作為數(shù)據(jù)交換的重要環(huán)節(jié)，其目的是為了確定數(shù)據(jù)交換場景中源對目標(biāo)的函數(shù)依賴。因此在模式匹配中，可以弱化J自身需要滿足目標(biāo)函數(shù)依賴。針對XML語境，將數(shù)據(jù)交換的雙方都替換成XML文檔，這些文檔格式可以是DTD/XSD或者其他格式。

定義2（XML模式匹配）給定三元組M＝(DS，DT，Σ)，DS為源文檔，DT為目標(biāo)文檔，Σ為一系列源對目標(biāo)函數(shù)依賴的集合，XML模式匹配就是在DS與DT中尋找所有相匹配的Σ。換言之，針對給定符合DS的樹t，模式匹配的解為樹t′，且t′符合如下要求：

（1）樹t′符合DT；

（2）＜t，t′＞滿足所有的源對目標(biāo)函數(shù)依賴Σ，可以形式化表示為＜t，t′＞?Σ。

3　相似度度量計(jì)算框架

基于相似度度量計(jì)算的匹配框架如圖2所示。

本文將針對XML模式匹配中的節(jié)點(diǎn)和結(jié)構(gòu)的相似度兩個(gè)方面進(jìn)行計(jì)算，得到相似度度量矩陣后，再進(jìn)行相似度擬合和優(yōu)化。

3.1基于節(jié)點(diǎn)名稱的相似度度量

在缺少實(shí)例數(shù)據(jù)的情況下，節(jié)點(diǎn)名稱在模式匹配中被認(rèn)為是一種重要的語義來源?；诠?jié)點(diǎn)名稱相似度度量算法有Q-gram算法[19]、Jaro-Winkler Similarity算法[20]、Smith-Waterman Similarity算法[21]、Monge-Elkan Similarity算法[22]，這些算法是基于字符相似度度量算法的典型代表。

Fig.2 Matching framework based on combining similarity measure圖2　基于相似度度量計(jì)算的匹配框架

（1）Q-gram算法

首先把要匹配的字符串分割為有許多連續(xù)N個(gè)字符組成的集合，通過找兩個(gè)字符串σ1和σ2中公共Q-gram串來計(jì)算相似性[19]。計(jì)算方法為：

（2）Jaro-Winkler Similarity算法

Jaro-Winkler Similarity算法主要是針對兩個(gè)短字符串的相似度距離計(jì)算[19]，是Jaro Similarity算法[23]的變種。計(jì)算公式為：

其中，simJaro(σ1，σ2)＝；M為σ1和 σ2匹配字符數(shù)；t為換位數(shù)目；pref(σ1，σ2)為兩個(gè)字符串σ1和σ2的最長公共前綴；參數(shù)?為常數(shù)，假定?為0.1。

（3）Smith-Waterman Similarity算法

Smith-Waterman Similarity為動態(tài)規(guī)劃算法，主要用以比較所有可能長度的字符串片段，并且對相似度進(jìn)行了優(yōu)化[21]。計(jì)算公式為：

其中，S1、S2為字符串，m＝|S1|，n＝|S2|；H(i，j)為S1第i個(gè)字符和S2第j個(gè)字符的最大相似度；w(x，y)代表間隙得分（gap scoring）。

（4）Monge-Elkan Similarity算法

Monge-Elkan Similarity度量算法作為混合相似度度量算法，結(jié)合了多種字符串相似度度量算法，該算法使用函數(shù)sim′(t1，t2)來計(jì)算[22]。計(jì)算公式為：

字符串相似性計(jì)算方法眾多，本文選擇以上4個(gè)作為節(jié)點(diǎn)名稱相似度計(jì)算方法，是因?yàn)閄ML文檔節(jié)點(diǎn)名稱多為短字符串。

根據(jù)上面所有基于節(jié)點(diǎn)名稱的相似度，結(jié)合決策樹算法思想，可以構(gòu)建相似度匹配決策子樹。決策樹算法是一種逼近離散函數(shù)值的方法，是一種典型的分類方法，本質(zhì)上是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程，它代表的是對象屬性與對象值之間的一種映射關(guān)系。

如圖3所示，通過構(gòu)建決策樹來處理相似度，是因?yàn)橐陨嫌?jì)算如果每個(gè)方法都要處理一遍，必然會增加計(jì)算時(shí)間，而且內(nèi)存等計(jì)算資源的使用也會增加。因此，使用決策樹方法計(jì)算相似度具有以下優(yōu)點(diǎn)：

（1）不會降低匹配質(zhì)量，相反在一定程度上可以提高匹配質(zhì)量；

（2）節(jié)省匹配時(shí)間，提高匹配效率。

Fig.3 Constructing decision tree of similarity matching圖3　相似度匹配決策子樹構(gòu)建

3.2基于節(jié)點(diǎn)類型的相似度度量

節(jié)點(diǎn)名稱的相似度雖然重要，但映射結(jié)果中可能會存在錯(cuò)誤的匹配，或者相似度結(jié)果不足以完全體現(xiàn)真實(shí)匹配。在此情況下，數(shù)據(jù)類型成為提高匹配質(zhì)量的另外一個(gè)可以考慮的方面[24]。

XML模式中具有原子類型和復(fù)雜類型兩種，其中原子類型包括string等基本數(shù)據(jù)類型，復(fù)雜類型為多個(gè)原子類型的組合。在此，可以通過如下相似度計(jì)算規(guī)則進(jìn)行處理：

（1）原子類型與復(fù)雜類型的相似度simdt＝0；

（2）復(fù)雜類型與復(fù)雜類型的相似度simdt＝1；

（3）原子類型與原子類型的相似度simdt可以參照約定的相似度度量表。

從表1中可以發(fā)現(xiàn)，如果兩者類型一致，那么simdt＝1；如果兩者類型不一致但可以相互轉(zhuǎn)換，那么simdt＝0.8；如果兩者類型不一致但可能相互轉(zhuǎn)換，那么simdt＝0.2；如果兩者類型不一致且不能相互轉(zhuǎn)換，那么simdt＝0。

Table 1 Similarity matching based on data type表1　數(shù)據(jù)類型相似度匹配

通過對照以上類型相似度匹配表的規(guī)則設(shè)置，可以得出兩個(gè)節(jié)點(diǎn)屬性的相似度。

3.3基于節(jié)點(diǎn)約束的相似度度量

XML模式使用minOccurs和maxOccurs定義了模式中節(jié)點(diǎn)的出現(xiàn)次數(shù)。因此，節(jié)點(diǎn)的基數(shù)約束信息可以成為節(jié)點(diǎn)相似度匹配中又一個(gè)重要的方面。

節(jié)點(diǎn)的基數(shù)表示方法有4種形式：“*”、“+”、“?”、“none”[24]。將4種表示之間的相似度約定為特定的相似度度量，如表2所示。

Table 2 Similarity matching based on data constraint表2　數(shù)據(jù)約束相似度匹配

在XML文檔中，并非所有的約束表示都如上，例如minOccurs＝2且maxOccurs＝5，在此情況下，可以通過如下方式來解決：

3.4基于節(jié)點(diǎn)結(jié)構(gòu)的相似度度量

XML文檔可以形式化地抽象為樹型結(jié)構(gòu)，因此在進(jìn)行相似度度量時(shí)可以考慮基于結(jié)構(gòu)的度量方法。

如圖4所示，在基于結(jié)構(gòu)的相似度度量方法中，主要是針對XML文檔樹中的祖先節(jié)點(diǎn)和兄弟節(jié)點(diǎn)兩個(gè)方面進(jìn)行考慮。為此，采用祖先相似度繼承映射（descendant’s similarity inheritance，DSI）方法[11]和兄弟相似度貢獻(xiàn)映射（sibling’s similarity contribution，SSC）方法[25]進(jìn)行處理。

Fig.4 Computing similarity between C and c圖4　計(jì)算節(jié)點(diǎn)C與c相似度

（1）DSI映射方法

DSI映射方法在基于語言分析的基礎(chǔ)上，將樹型結(jié)構(gòu)中的父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)信息納入到計(jì)算中。實(shí)現(xiàn)這種方法的前提是假設(shè)父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)能對該節(jié)點(diǎn)的相似度產(chǎn)生影響，就是說兩個(gè)節(jié)點(diǎn)的祖先節(jié)點(diǎn)相似度越大，這兩個(gè)節(jié)點(diǎn)的相似度也越接近。計(jì)算方式為：

節(jié)點(diǎn)無祖先節(jié)點(diǎn)時(shí)，simDSI(σ1，σ2)＝simling(σ1，σ2)。

（2）SSC映射方法

SSC映射方法也是基于語言分析的基礎(chǔ)，將樹型結(jié)構(gòu)中的兄弟節(jié)點(diǎn)信息納入到計(jì)算中。實(shí)現(xiàn)這種方法的前提假設(shè)是兄弟節(jié)點(diǎn)能對該節(jié)點(diǎn)的相似度產(chǎn)生影響，也就是說兩個(gè)節(jié)點(diǎn)的兄弟節(jié)點(diǎn)相似度越大，那么這兩個(gè)節(jié)點(diǎn)的相似度也越接近。計(jì)算公式為：

節(jié)點(diǎn)無兄弟節(jié)點(diǎn)時(shí)，simSSC(σ1，σ2)＝simling(σ1，σ2)。

4　多策略相似度整合

第3章已經(jīng)計(jì)算了所有種類的相似度，但在模式匹配中，上述的相似度度量算法并不能充分反映節(jié)點(diǎn)之間的相似性，例如基于節(jié)點(diǎn)名稱的相似度僅能反映節(jié)點(diǎn)之間的名稱特性。因此，有必要將多種策略應(yīng)用到以上所有計(jì)算得到的節(jié)點(diǎn)相似度矩陣中，通過多方面相似度矩陣整合，以得到優(yōu)化結(jié)果。基于多策略的相似度整合框架如圖5所示。

Fig.5 Combining similarity measures圖5　相似度度量整合

通過以下不同的合并策略來整合相似度度量，最后得到模式匹配的相似度立方體。

（1）Max合并策略

Max策略是一種積極的相似度合并策略，這種策略的核心思想就是在各個(gè)相似度矩陣中選擇最高的度量值，不考慮其他值的計(jì)算結(jié)果。這種合并策略簡單，在某些特定場景下可能會有較好的表現(xiàn)。計(jì)算公式為：

（2）Average合并策略

Average策略作為加權(quán)平均組合策略的特例，對所有參與組合的相似度給予相同權(quán)重。這種組合策略假設(shè)合并之前相似度普遍較高的節(jié)點(diǎn)在平均之后的效果也良好。計(jì)算公式為：

（3）Sigmoid合并策略

Sigmoid函數(shù)是一個(gè)良好的閾值函數(shù)，具有平滑連續(xù)、嚴(yán)格單調(diào)的特性，合并中權(quán)值的選擇可以使參與計(jì)算的相似度值緊密結(jié)合起來。計(jì)算公式為：

其中，a為傾斜參數(shù)，影響函數(shù)的形狀，文中可以設(shè)定為1。Sigmoid函數(shù)對應(yīng)幅值區(qū)間為（0，1）。因此，在合并相似度中，這種合并策略實(shí)際上將較高相似度賦予高權(quán)重比例，將較低相似度賦予低權(quán)重比例，實(shí)現(xiàn)相似度歸一化。結(jié)合Sigmoid函數(shù)，所有參與相似度組合的計(jì)算公式為：

（4）Nonlinear合并策略

Nonlinear相似度合并策略是擴(kuò)展了的加權(quán)組合策略，此策略的主要思想是將相似度之間的相互依賴關(guān)系合并到綜合計(jì)算中。計(jì)算公式為：

公式的第一部分是不同相似度擬合，第二部分反映的是節(jié)點(diǎn)和結(jié)構(gòu)之間相似度相互依賴關(guān)系，通過參數(shù)λ來合并這兩部分的計(jì)算結(jié)果。之所以使用Nonlinear相似度合并策略，是因?yàn)榛谶@樣的假設(shè)，即如果節(jié)點(diǎn)相似度越高，則節(jié)點(diǎn)越相似，從而不必要增加這兩部分之間的相互依賴關(guān)系；相反則需要減少這兩部分之間的依賴關(guān)系。第一部分和第二部分通過調(diào)整參數(shù)λ來擬合相似度，確保最后得到的相似度計(jì)算結(jié)果在[0，1]之間。

由于每一個(gè)相似度對于平均數(shù)的貢獻(xiàn)并不是相同的，其重要程度也是不同的，可以使用加權(quán)平均方法將計(jì)算后的不同相似度以一定權(quán)重進(jìn)行配比。例如在本文的場景中，基于節(jié)點(diǎn)名稱的相似度可能比基于節(jié)點(diǎn)類型的相似度貢獻(xiàn)更大，因此權(quán)重配比也可能更高。加權(quán)平均的計(jì)算方式為：

從上述公式不難發(fā)現(xiàn)，不同的權(quán)重會直接影響最后的相似度計(jì)算結(jié)果。而擬合這些權(quán)值工作又是瑣碎的，因此權(quán)重的具體計(jì)算可以采用模擬退火算法[26]思想進(jìn)行處理。模擬退火算法是一種隨機(jī)搜索算法，可以解決大規(guī)模解空間的組合優(yōu)化問題。算法對當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄新解”過程。算法除了接受較優(yōu)的解外，還以一定的概率來接受一個(gè)比當(dāng)前解要差的解，這樣有可能會跳出這個(gè)局部的最優(yōu)解，直至得到求解問題的全局最優(yōu)解。

Fig.6 Achieving global optimum圖6　尋找全局最優(yōu)解

如圖6所示，從A開始模擬退火算法得到局部最優(yōu)解B后，會以一定的概率接受到C的移動，經(jīng)過幾次不是局部最優(yōu)解的移動后會到達(dá)E點(diǎn)，這樣就跳出了局部最大值B。

模擬退火算法框架如圖7所示。

在此，狀態(tài)轉(zhuǎn)移概率（接受概率）通常采用Metropolis接受準(zhǔn)則，即：

準(zhǔn)則保證在高點(diǎn)時(shí)可接受與當(dāng)前態(tài)差值較大的新狀態(tài)，在低點(diǎn)時(shí)只接受與當(dāng)前態(tài)差值較小的新狀態(tài)。

基于上述思路，將退火算法應(yīng)用到Nonlinear相似度合并策略中擬合計(jì)算參數(shù)。算法描述：

Fig.7 Framework of simulated annealing algorithm圖7　模擬退火算法框架

使用模擬退火算法計(jì)算加權(quán)平均中的權(quán)值具有以下優(yōu)點(diǎn)：

（1）算法的解與初始解狀態(tài)無關(guān)；

（2）算法具有漸近收斂性，并已在理論上被證明以概率1收斂于全局最優(yōu)解；

（3）算法可以并行處理。

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

本文使用Java實(shí)現(xiàn)上述算法，實(shí)驗(yàn)硬件環(huán)境為2.93 GHz Intel Core 2 CPU，2 GB內(nèi)存；操作系統(tǒng)為Ubuntu 14.04 LTS（64位）。數(shù)據(jù)集采用XbenchMatch Benchmark[27]模式文件和Clio原型測試文件（http:// dblab.cs.toronto.edu/project/clio/），選擇以上數(shù)據(jù)集是因?yàn)樗鼈兎謩e來自不同的應(yīng)用領(lǐng)域。數(shù)據(jù)集的基本統(tǒng)計(jì)信息如表3所示。

Table 3　Data set details表3　數(shù)據(jù)集描述

模式匹配的有效性評估中，分別使用準(zhǔn)確率(P)、召回率(R)和F值(F-measure)表示匹配算法的正確程度、完善程度和權(quán)衡結(jié)果，計(jì)算公式表示為：

如圖8所示，在結(jié)合準(zhǔn)確率和召回率后得到F值，表示匹配結(jié)果中錯(cuò)誤匹配與丟失正確匹配的比值，較客觀、全面地評價(jià)了最后的匹配質(zhì)量。

Fig.8 Matching result statistic圖8　匹配結(jié)果統(tǒng)計(jì)

圖9是單一相似度度量算法的匹配結(jié)果，從實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)，匹配效果不是十分理想。這是因?yàn)閱我坏南嗨贫榷攘克惴?，并不能很好地體現(xiàn)模式匹配整體的相似性。匹配結(jié)果中，基于名稱的相似度度量算法表現(xiàn)良好，在個(gè)別數(shù)據(jù)集上的F值也可以達(dá)到0.7以上，但是畢竟沒有融合其他特征信息，總體效果不十分理想。單一的基于節(jié)點(diǎn)類型、基于約束的算法效果較差，其原因是兩個(gè)XML文檔中匹配的大部分節(jié)點(diǎn)的類型使用String類型，約束則使用常用的約束限制，minOccurs＝0且maxOccurs＝unbound，從而無法準(zhǔn)確區(qū)分哪些節(jié)點(diǎn)是精確匹配。

Fig.9 Matching results based on single similarity measure algorithms圖9　單一相似度度量算法結(jié)果

由此可以看出，基于節(jié)點(diǎn)名稱、基于節(jié)點(diǎn)類型、基于約束和基于結(jié)構(gòu)的相似度度量算法，它們僅僅反映了元素的內(nèi)部或外部特性，特征表現(xiàn)單一、模糊，不能全面體現(xiàn)元素節(jié)點(diǎn)的特征，最后結(jié)果表現(xiàn)一般。

本文采用的多策略相似度整合算法，彌補(bǔ)了單一匹配算法的局限性，并且在個(gè)別算法中采用了優(yōu)化方法，提高了相似度度量計(jì)算中的匹配效果。本文實(shí)驗(yàn)與經(jīng)典的模式匹配算法Similarity Flooding[9]和COMA++[11]進(jìn)行了對比。

圖10、圖11和圖12分別是基于多策略相似度整合的XML模式匹配方法與COMA++和Similarity Flooding模式匹配算法在準(zhǔn)確率、召回率和F值的實(shí)驗(yàn)對比。

Fig.10 Precision among all matching algorithms圖10　各匹配算法精確率比較

Fig.11 Recall among all matching algorithms圖11　各匹配算法召回率比較

通過圖10、圖11和圖12發(fā)現(xiàn)，基于多策略相似度整合的匹配算法中，Nonlinear合并策略整體表現(xiàn)良好。這是因?yàn)樵谠摵喜⒉呗灾?，?quán)重的計(jì)算采用了模擬退火算法思想進(jìn)行處理，可以解決大規(guī)模權(quán)值空間的組合優(yōu)化問題，從而尋找最適當(dāng)?shù)臄M合參數(shù)。Nonlinear合并策略也不是在所有數(shù)據(jù)集都十分出色，但總體而言，Nonlinear策略匹配性能良好，如圖12所示。在多策略匹配方法中，Average合并策略和Sigmoid合并策略的表現(xiàn)也較為突出，雖然整體效果比不上COMA++（如圖13所示），但在部分測試數(shù)據(jù)集中匹配效果不錯(cuò)。表現(xiàn)較差的是Max合并策略，盡管在部分?jǐn)?shù)據(jù)集上召回率較高，造成這種結(jié)果的原因是此策略作為一種積極的相似度合并策略，在各個(gè)相似度矩陣中選擇最高的度量值，并不考慮其他值的計(jì)算結(jié)果，在這種情況下，直接過濾了矩陣中相似度度量結(jié)果為Top-2至Top-k的匹配對。

Fig.12 F-measure among all matching algorithms圖12　各匹配算法F值比較

Fig.13 F-measure among all measure algorithms圖13　各度量算法平均F值比較

綜合以上各算法的平均F值，發(fā)現(xiàn)基于多種組合策略的相似度度量算法，其整體匹配質(zhì)量要比單一的相似度度量算法出色。Nonlinear合并策略和Average合并策略表現(xiàn)出色，Max策略簡單，展示結(jié)果遜于其他策略（與文獻(xiàn)[28]的結(jié)論相同），在某些場合中可能會有比較好的結(jié)果。當(dāng)然，針對不同的數(shù)據(jù)集，各種策略的表現(xiàn)也有差異，因此在模式匹配中，可以考慮結(jié)合多種匹配策略，得到合適的匹配結(jié)果。

6　結(jié)束語

模式匹配用于發(fā)現(xiàn)不同數(shù)據(jù)源中概念之間的語義對應(yīng)關(guān)系，成為數(shù)據(jù)集成、數(shù)據(jù)交換等領(lǐng)域的研究熱點(diǎn)。由于模式匹配存在固有的復(fù)雜性，目前模式匹配工作主要是依靠領(lǐng)域?qū)＜襾硎止ね瓿伞１疚尼槍δ壳癤ML模式匹配的挑戰(zhàn)，深入研究了XML模式匹配特征，展示了不同層面的XML相似度度量方法，包括基于節(jié)點(diǎn)名稱、類型等多種相似度度量方法，得到相似度度量矩陣。為避免單一相似度度量方法的局限性，采用多策略相似度整合方式擬合所得到的相似度矩陣，并且使用啟發(fā)式隨機(jī)搜索算法，避免人工擬合或窮舉所有參數(shù)。最后，通過基準(zhǔn)測試平臺對比，部分策略相比于經(jīng)典的模式匹配工具具有較高的精確度和召回率。

在未來工作中，考慮重用先期的匹配工作，避免在后續(xù)處理中重復(fù)計(jì)算相同內(nèi)容。在組合策略中，可以考慮使用機(jī)器學(xué)習(xí)或神經(jīng)網(wǎng)絡(luò)中更復(fù)雜的優(yōu)化策略，進(jìn)一步提高匹配質(zhì)量。

References:

[1] Gou Gang, Chirkova R. Efficiently querying large XML data repositories: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(10): 1381-1403.

[2] Fagin R, Kolaitis PG, Miller R J, et al. Data exchange: semantics and query answering[C]//LNCS 2572: Proceedings of the 9th International Conference on Database Theory, Siena, Italy, Jan 8-10, 2003. Berlin, Heidelberg: Springer, 2003: 207-224.

[3] Arenas M, Libkin L. XML data exchange: consistency and query answering[J]. Journal of the Association for Computing Machinery, 2008, 55(2): 13-24.

[4] Rahm E, Bernstein PA. A survey of approaches to automatic schema matching[J]. VLDB Journal, 2001, 10(4): 334-350.

[5] Bellahsene Z, Bonifati A, Rahm E. Schema matching and mapping[M]. Berlin, Heidelberg: Springer, 2011.

[6] Euzenat J, Shvaiko P. Ontology matching[M]. Berlin, Heidelberg: Springer, 2007.

[7] Shvaiko P, Euzenat J. Ontology matching: state of the art and future challenge[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 158-176.

[8] Xing Guangming. Approximate matching of XML documents with schemata using tree alignment[C]//Proceedings of the 2014 ACM Southeast Regional Conference, Kennesaw, USA, Mar 28-29, 2014. New York, USA:ACM, 2014: 43.

[9] Melnik S, Garcia-Molina H, Rahm E. Similarity flooding: a versatile graph matching algorithm and its application to schema matching[C]//Proceedings of the 18th International Conference on Data Engineering, San Jose, USA, Feb 26-Mar 1, 2002. Piscataway, USA: IEEE, 2002: 117-128.

[10] Lambrix P, Tan He, Xu Wei. Literature-based alignment of ontologies[C]//Proceedings of the 3rd International Workshop on Ontology Matching Collocated with the 7th International Semantic Web Conference, Karlsruhe, Germany, Oct 26, 2008.

[11] Peukert E, Massmann S, Konig K. Comparing similarity combination methods for schema matching[C]//LNI 175 Service Science: GI-Workshop, Informations Integration in Service-Architekturen, Leipzig, Germany, 2010: 692-701.

[12] Li Juanzi, Tang Jie, Li Yi, et al. RiMOM: a dynamic multistrategy ontology alignment framework[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(8): 1218-1232.

[13] Zhang Zhi, Shi Pengfei. An efficient greedy algorithm for schema matching[J]. Journal of Computer Research and Development, 2007, 44(11): 1903-1911.

[14] Ehrig M, Staab S. Quick ontology matching[C]//LNCS 3298: Proceedings of the 3rd International Semantic Web Conference, Hiroshima, Japan, Nov 7-11, 2004. Berlin, Heidelberg: Springer, 2004: 683-697.

[15] Do H H, Rahm E. Matching large schemas: approaches and evaluation[J]. Information System, 2007, 32(6): 857-885.

[16] Saha B, Stanoi I, Clarkson K. Schema covering: a step towards enabling reuse in information integration[C]//Proceedings of the 26th International Conference on Data Engineering, Long Beach, USA, Mar 1-6, 2010. Piscataway, USA: IEEE, 2010: 285-296.

[17] Algergawy A, Nayak R, Saake G. Element similarity measures in XML schema matching[J]. Information Sciences, 2010, 180(24): 4975-4998.

[18] Agreste S, De Meo P, Ferrarac E, et al. XML matchers: approaches and challenges[J]. Knowledge Based Systems, 2014, 66: 190-209.

[19] Ullmann J R. A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words[J]. Computer Journal, 1977, 20(2): 141-147.

[20] Winkler W E. String comparator metrics and enhanced decision rules in the Fellegi-Sunter model of record linkage[C]// Proceedings of the Section on Survey Research Methods, 1990: 354-359.

[21] Smith T F, Waterman M S. Identification of common molecular subsequences[J]. Journal of Molecular Biology, 1981, 147(1): 195-197.

[22] Monge A, Elkan C. The field matching problem: algorithms and applications[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Oregon, USA, 1996: 267-270.

[23] Jaro MA.Advances in record linkage methodology[J]. Journal of the American Statistical Association, 1989, 84(406): 414-420.

[24] Nayak R, Tran T. A progressive clustering algorithm to group the XML data by structural and semantic similarity[J]. Schema Recognition and Artificial Intelligence, 2007, 21(4): 723-743.

[25] Sunna W, Cruz I F. Structure-based methods to enhance geospatial ontology alignment[C]//LNCS 4853: Proceedings of the 2nd International Conference, Mexico City, Nov 29-30, 2007. Berlin, Heidelberg: Springer, 2007: 82-97.

[26] Kirkpatrick S,Gelatt C.Optimizationbysimulatedannealing[J]. Science, 1988, 220(4598): 671-680.

[27] Fabien D, Bellahsene Z, Hunt E. XBenchMatch：a benchmark for XML schema matching tools[C]//Proceedings of the 33rd International Conference on Very Large Data Bases, Vienna, Austria, Sep 23-27, 2007: 1318-1321.

[28] Do H H, Rahm E. Matching large schemas: approaches and evaluation[J]. Information Systems, 2007, 32(6): 857-885.

附中文參考文獻(xiàn)：

[13]張治,施鵬飛.一種有效的貪婪模式匹配算法[J].計(jì)算機(jī)研究與發(fā)展, 2007, 44(11): 1903-1911.

FAN Hongjie was born in 1984. He is a Ph.D. candidate at Peking University. His research interests include data exchange technology and schema matching, etc.

范紅杰（1984—），男，浙江湖州人，北京大學(xué)博士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)交換技術(shù)，模式匹配等。

LIU Junfei was born in 1965. He is a professor and Ph.D. supervisor at School of Electronics Engineering and Computer Science, Peking University. His research interests include software engineering, information exchange technology and smart city, etc.

柳軍飛（1965—），男，湖南人，北京大學(xué)信息科學(xué)技術(shù)學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)檐浖こ蹋畔⒔粨Q技術(shù)，智慧城市等。

ZHOU Ludong was born in 1991. He is an M.S. candidate at Peking University. His research interests include information exchange technology, software engineering and machine learning, etc.

周魯東（1991—），男，山東臨沂人，北京大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)樾畔⒔粨Q技術(shù)，軟件工程，機(jī)器學(xué)習(xí)等。

MA Zhiyi was born in 1963. He is an associate professor at Peking University. His research interests include software modeling technology and model driven development, etc.

麻志毅（1963—），男，內(nèi)蒙古赤峰人，北京大學(xué)信息科學(xué)技術(shù)學(xué)院副教授，主要研究領(lǐng)域?yàn)檐浖＜夹g(shù)，模型驅(qū)動開發(fā)方法等。

XMLSchema Matching Based on Multi-Strategy Similarity Integration*

FAN Hongjie1, LIU Junfei2+, ZHOU Ludong1, MAZhiyi1
1. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
2. National Engineering Research Center for Software Engineering, Peking University, Beijing 100871, China
+ Corresponding author: E-mail: liujunfei@pku.edu.cn

FAN Hongjie, LIU Junfei, ZHOU Ludong, et al. XMLschema matching based on multi-strategy similarity integration. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：14-24.

Abstract:Schema matching, as finding the semantic correspondence of concepts between different data sources, becomes the hot topic of data integration, data exchange and other areas. Researchers have proposed a number of matching methods, which make it possible to identify and discover the semantic correspondence between the XML data. But XML schema matching has some challenges, such as how to consider the variety of similarity, and how to integrate the similarity so as to make the optimum matching results. In order to improve the quality of XML matching, firstly this paper calculates the similarity of XML nodes and structure from the different levels, gets the similarity matrix, and integrates the similarity measure between these two aspects effectively. Then, this paper fits through a variety of strategies combination and optimization algorithms to make the final matching result achieve global optimum after the effective integration of these two aspects of similarity measure. Finally, compared with the classic schema matching tool, this method has a higher precision and recall rate through the benchmark platform.

Key words:data exchange; schema matching; extensible markup language（XML）; similarity measure; multi-strategy integration

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

中圖分類號：TP311

doi:10.3778/j.issn.1673-9418.1507071