郭樂(lè)樂(lè)，林友芳，韓 升

北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044

利用有序互信息匹配包含非透明列的數(shù)據(jù)模式*

郭樂(lè)樂(lè)+，林友芳，韓 升

北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044

數(shù)據(jù)模式匹配是異構(gòu)數(shù)據(jù)源數(shù)據(jù)合并過(guò)程中的核心環(huán)節(jié)，屬于數(shù)據(jù)集成中的關(guān)鍵問(wèn)題。目前已有許多數(shù)據(jù)模式匹配方法，但其中很大一部分方法由于過(guò)多依賴數(shù)據(jù)模式描述信息，導(dǎo)致通用性不足，很難應(yīng)用于其他場(chǎng)景中。為此，提出了一種利用有序互信息的匹配包含非透明列名和列數(shù)據(jù)值的數(shù)據(jù)模式。該方法不依賴諸如列名、列類型、主外鍵依賴等數(shù)據(jù)模式描述信息，因此具有很強(qiáng)的通用性。在多個(gè)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明，該方法能夠在大幅降低匹配花費(fèi)時(shí)間的同時(shí)提高匹配結(jié)果的準(zhǔn)確率。

數(shù)據(jù)模式匹配；非透明條件；互信息；無(wú)向圖匹配

1 引言

從最基本的層面講，數(shù)據(jù)模式匹配就是尋找從一個(gè)信息庫(kù)的元素到另一個(gè)信息庫(kù)的元素上的映射問(wèn)題。對(duì)于關(guān)系型數(shù)據(jù)庫(kù)來(lái)說(shuō)，這里信息庫(kù)中的元素指的就是屬性列。模式匹配問(wèn)題經(jīng)常出現(xiàn)在企業(yè)兼并重組帶來(lái)的數(shù)據(jù)庫(kù)合并過(guò)程或多數(shù)據(jù)源數(shù)據(jù)集成過(guò)程中，而且隨著數(shù)據(jù)規(guī)模不斷擴(kuò)大，該問(wèn)題也變得日益突出。顯然使用人工方法解決模式匹配問(wèn)題會(huì)給數(shù)據(jù)管理人員帶來(lái)沉重的工作負(fù)擔(dān)，因此迫切需要解決該問(wèn)題的自動(dòng)化方法。經(jīng)過(guò)十多年研究，許多研究者發(fā)現(xiàn)數(shù)據(jù)模式匹配問(wèn)題會(huì)隨著約束的不同而帶來(lái)復(fù)雜程度方面的巨大差異，很難找到一種適用于所有領(lǐng)域數(shù)據(jù)的匹配方法。目前已經(jīng)提出了許多數(shù)據(jù)模式匹配方法，根據(jù)研究方法的不同可以概括為以下幾大類：

（1）基于模式描述信息的匹配方法。之前已經(jīng)提出了很多基于模式描述信息的方法[1]，如根據(jù)列名[2]、列名同義詞[3]，或者其他語(yǔ)言學(xué)[4]的列名相似性描述方法，但基于列名相似的方法都無(wú)法解決“同名異義”和“同義異名”的問(wèn)題。此外，也有基于字段類型或主外鍵等信息的模式匹配方法。這些方法大多出現(xiàn)在早期研究中，由于使用或部分使用模式信息，導(dǎo)致這類方法通用性不足。

（2）基于機(jī)器學(xué)習(xí)的模式匹配方法。早年有Li和Clifton提出的基于BP（back propagation）神經(jīng)網(wǎng)絡(luò)的原型系統(tǒng)SemInt[5],也有Berlin和Motro提出的利用特征選擇減少了參加匹配的模式中的屬性列數(shù)目的方法[6]。近些年隨著新的機(jī)器學(xué)習(xí)理論的不斷涌現(xiàn)，有不少研究者受這些理論的啟發(fā)提出了一些新的模式匹配方法。其中，將多種學(xué)習(xí)器結(jié)合到一起就是一種重要的思路[7-8]。比如Do和Rahm提出的COMA（combining match）系統(tǒng)通過(guò)分析屬性列最大、最小值提供候選匹配結(jié)點(diǎn)，集成多種學(xué)習(xí)器進(jìn)行匹配[9]。Algergawy等人使用聚類方法改進(jìn)了COMA算法，也取得了不錯(cuò)的效果[10]。Rodrigues等人提出了基于主動(dòng)學(xué)習(xí)的方法減少了需要領(lǐng)域?qū)＜姨峁┑挠?xùn)練樣本數(shù)量[11]。Ferragut和Laska提出了離散取值模型、字符位置模型以及原子型字符位置模式，結(jié)合非參貝葉斯方法計(jì)算模式中列之間相似度[12]，為模式匹配研究提供了新的思路。這類方法要么直接選取模式描述信息作為特征，利用樣本訓(xùn)練學(xué)習(xí)器，要么學(xué)習(xí)器集合中包含基于模式描述信息的學(xué)習(xí)器，有的方法甚至需要領(lǐng)域?qū)＜医?jīng)驗(yàn)，因此局限性也很大。

（3）不依賴模式描述信息，基于非表達(dá)信息的模式匹配方法。比如Kang和Naughton提出了基于互信息（mutual information，MI）的模式匹配方法[13]，并在文中首次將數(shù)據(jù)模式匹配問(wèn)題分為one-to-one mapping、onto mapping和partial mapping這3種情形，同時(shí)提出了歐式距離和規(guī)范化距離兩種量度計(jì)算模式之間的相似性，后來(lái)又提出了適用于該方法的無(wú)監(jiān)督值映射方案[14]。Jaiswal等人提出了計(jì)算有序列取值分布PMF（probability mass function）的模式匹配方法[15]，雖然給出了基于有序PMF的值映射方法，但當(dāng)遇到速度、稅率等實(shí)數(shù)取值的列之間匹配問(wèn)題時(shí)，由于PMF趨近均勻分布，會(huì)出現(xiàn)準(zhǔn)確率大幅下降的問(wèn)題。

本文正是在Kang和Naughton提出的基于互信息匹配方法的基礎(chǔ)上，提出了一種全新的互信息無(wú)向圖結(jié)點(diǎn)匹配方法。實(shí)驗(yàn)結(jié)果表明，本文方法能夠顯著提高模式匹配的準(zhǔn)確率，并能夠降低匹配花費(fèi)時(shí)間。本文的主要貢獻(xiàn)有：

（1）結(jié)合互信息依賴矩陣，提出了一種基于有序互信息的無(wú)向圖結(jié)點(diǎn)匹配方法。

（2）改進(jìn)了文獻(xiàn)[12]提出的基于有序PMF的匹配方法，并用于解決無(wú)向圖結(jié)點(diǎn)匹配過(guò)程中出現(xiàn)的互信息量度失效問(wèn)題。

2 相關(guān)概念

2.1 可表達(dá)匹配和不可表達(dá)匹配

Kang和Naughton給出了可表達(dá)（interpreted）和不可表達(dá)（un-interpreted）信息匹配的基本概念。假定源模式S(s1,s2,…,sm)和目標(biāo)模式T(t1,t2,…,tn)是分別包含m個(gè)元素的數(shù)據(jù)模式和n個(gè)元素的數(shù)據(jù)模式，映射M1和M2是定義在模式S和模式T上的同一個(gè)模式匹配算法的兩個(gè)匹配結(jié)果，匹配算法的定義如下，假定：

式中，fi是任意應(yīng)用到目標(biāo)模式T的第i列所有值上的一個(gè)一對(duì)一函數(shù)，那么當(dāng)且僅當(dāng)無(wú)論 fi的定義如何，M1與M2都完全相同時(shí)，稱該匹配算法match是一個(gè)不可表達(dá)匹配方法。反之，稱該算法是一個(gè)可表達(dá)匹配方法。

2.2 元素匹配與結(jié)構(gòu)匹配

元素匹配考慮的是單個(gè)列的特征，如列名、類型、取值分布、信息熵等。結(jié)構(gòu)匹配在設(shè)計(jì)相似度時(shí)優(yōu)先考慮列之間的關(guān)系特征，比如外鍵依賴、互信息等。

2.3 模式匹配算法分類

根據(jù)匹配信息是否可表達(dá)以及設(shè)計(jì)相似度目標(biāo)函數(shù)時(shí)考慮的粒度，可以將當(dāng)前的匹配算法分為4個(gè)類型，每個(gè)類型都有一些已經(jīng)提出的典型的數(shù)據(jù)模式匹配算法。匹配算法分類如圖1所示。

非可表達(dá)的結(jié)構(gòu)匹配方法由于特征直接從數(shù)據(jù)樣本中提取，且在尋找模式的元素之間匹配關(guān)系時(shí)除了考慮單個(gè)列的特征外，還考慮了模式內(nèi)元素間關(guān)系，因此這類算法能夠適應(yīng)多種場(chǎng)景，并且一般能獲得較高的匹配準(zhǔn)確率。Kang和Naughton提出的方法[10]就屬于基于非可表達(dá)信息的結(jié)構(gòu)匹配方法的一種。本文提出的方法也屬于這一類。

Fig.1 Classification of schema matching algorithms圖1 數(shù)據(jù)模式匹配算法分類

3 基于有序互信息的模式匹配算法

3.1 算法主要流程

基于互信息的模式匹配算法主要分為兩步：

步驟1根據(jù)源模式S和目標(biāo)模式T的數(shù)據(jù)樣本求出兩個(gè)互信息依賴矩陣MS和MT。

步驟2將互信息矩陣MS和MT分別看作帶權(quán)無(wú)向圖G1和G2的鄰接矩陣，從而將模式匹配問(wèn)題轉(zhuǎn)化為尋找G1和G2中各個(gè)結(jié)點(diǎn)的最佳映射關(guān)系問(wèn)題。

互信息矩陣的計(jì)算方法和尋找互信息無(wú)向圖中結(jié)點(diǎn)的最佳映射的方法將在后面的章節(jié)中詳細(xì)介紹。

3.2 互信息矩陣的計(jì)算方法

對(duì)于待匹配的兩個(gè)數(shù)據(jù)模式S(s1,s2,…,sm)和T(t1,t2,…,tn)來(lái)說(shuō)，根據(jù)上式求得的MI(si,sj)將作為數(shù)據(jù)模式S對(duì)應(yīng)的互信息矩陣MS第i行第 j列的元素pij，求解完成后將會(huì)得到一個(gè)m維對(duì)稱矩陣，如下所示：

假定屬性列X和Y包含在任意一個(gè)模式S中，其中模式S的數(shù)據(jù)樣本sampleS中屬性列X和Y的獨(dú)立取值集合分別為X和Y，那么依據(jù)樣本sampleS可以求得列X與列Y之間的互信息為MI(X,Y)，其中：

用同樣的方法也可以求得數(shù)據(jù)模式T對(duì)應(yīng)的互信息矩陣MT。

3.3 基于有序互信息的無(wú)向圖匹配

按照3.2節(jié)提到的方法可以分別求得源模式S和目標(biāo)模式T對(duì)應(yīng)的互信息矩陣MS和MT，將MS和MT分別視為帶權(quán)無(wú)向圖G1和G2的鄰接矩陣，此時(shí)基于互信息的模式匹配問(wèn)題轉(zhuǎn)換為求兩個(gè)帶權(quán)無(wú)向圖結(jié)點(diǎn)最佳匹配問(wèn)題。若假定m＜n，匹配兩個(gè)分別包含m個(gè)結(jié)點(diǎn)和n個(gè)結(jié)點(diǎn)的帶權(quán)無(wú)向圖，則該問(wèn)題屬于onto mapping問(wèn)題，搜索空間大小為O(m!/(n-m)!)。同樣地，若假定m=n,那么該問(wèn)題就屬于one-to-one mapping問(wèn)題，搜索空間大小是O(n!)。由于one-toone mapping是onto mapping模式匹配問(wèn)題的常見(jiàn)情形，并且前者是后者的子問(wèn)題，故本文只針對(duì)one-toone mapping問(wèn)題給出一種全新的無(wú)向圖結(jié)點(diǎn)匹配方法。若解決了one-to-one mapping問(wèn)題，onto mapping問(wèn)題可以通過(guò)先在屬性列個(gè)數(shù)較多的數(shù)據(jù)模式中確定一個(gè)和另一個(gè)數(shù)據(jù)模式屬性列數(shù)目相等的屬性子集，然后將問(wèn)題轉(zhuǎn)化為one-to-onemapping問(wèn)題來(lái)解決。

3.3.1 基于互信息啟發(fā)式無(wú)向圖結(jié)點(diǎn)匹配算法

Kang和Naughton在實(shí)驗(yàn)中使用了窮舉搜索算法，同時(shí)使用啟發(fā)信息減少搜索空間。這種方法實(shí)質(zhì)就是根據(jù)信息熵從無(wú)向圖G2中篩選出一個(gè)包含k個(gè)結(jié)點(diǎn)的候選子集作為無(wú)向圖G1中結(jié)點(diǎn)i的候選匹配結(jié)點(diǎn)。這樣的思路很容易理解，通過(guò)信息熵可以過(guò)濾掉那些與無(wú)向圖G1中結(jié)點(diǎn)i信息熵差距較大的結(jié)點(diǎn)，從而在一定程度上減少了搜索空間。

這樣的方法雖然思路比較簡(jiǎn)單，但缺點(diǎn)也是顯而易見(jiàn)的。首先，盡管限定了搜索空間，但該方法的搜索空間依然很大，以k=3且n=20為例，此時(shí)整個(gè)匹配算法搜索空間仍然約達(dá)到，因此采用這種方法匹配結(jié)點(diǎn)依然需要花費(fèi)很長(zhǎng)時(shí)間[12]。當(dāng)數(shù)據(jù)模式中包含的屬性列數(shù)目增加時(shí)，該方法的搜索空間變得非常龐大，得出匹配結(jié)果花費(fèi)的時(shí)間將變得不可接受。其次，啟發(fā)信息的獲得需要建立在對(duì)特定領(lǐng)域數(shù)據(jù)特征有充分了解的基礎(chǔ)上，需要一定的專業(yè)知識(shí)。最后，由于該方法使用信息熵過(guò)濾掉與匹配目標(biāo)熵值差異較大的結(jié)點(diǎn)，在數(shù)據(jù)模式中各個(gè)列在樣本信息熵分布比較稀疏時(shí)是有效的，但是考慮一些極端情況，比如當(dāng)數(shù)據(jù)模式中各個(gè)屬性列樣本信息熵分布比較密集時(shí)，所有屬性列的信息熵分布在一個(gè)較狹窄的區(qū)間內(nèi)，此時(shí)采用信息熵過(guò)濾機(jī)制出錯(cuò)的概率將急劇增大，從而匹配準(zhǔn)確率出現(xiàn)明顯下降。

3.3.2 基于有序互信息無(wú)向圖結(jié)點(diǎn)匹配算法

正因?yàn)榛趩l(fā)信息匹配方法存在性能和準(zhǔn)確率方面的問(wèn)題，本文給出一種基于有序互信息的無(wú)向圖結(jié)點(diǎn)匹配算法（ordered mutual information graph match algorithm，OMIGM）。

算法1OMIGM(MS,MT)算法

輸入：兩個(gè)無(wú)向圖G1和G2分別對(duì)應(yīng)的兩個(gè)互信息依賴矩陣MS和MT。

輸出：圖G1和G2結(jié)點(diǎn)之間的最佳對(duì)應(yīng)關(guān)系。1.分別篩選出圖G1和G2中剩余待匹配結(jié)點(diǎn)

2.以有序互信息歐式距離作為相似量度，依次尋找圖G1中各個(gè)待匹配結(jié)點(diǎn)在圖G2的待匹配結(jié)點(diǎn)中的最相似的結(jié)點(diǎn)，將單向相似關(guān)系存入關(guān)系集R1中

3.用步驟2中的方法，可以依次求得圖G2中各個(gè)待匹配結(jié)點(diǎn)在圖G1待匹配結(jié)點(diǎn)中的最相似結(jié)點(diǎn)，將單向相似關(guān)系存入關(guān)系集R2中

4.合并R1和R2，得到雙向相似關(guān)系集Rdouble，在Rdouble中每個(gè)雙向關(guān)系表示產(chǎn)生了一對(duì)新的雙向相似關(guān)系，并分別從圖G1和圖G2中移除雙向相似關(guān)系的關(guān)聯(lián)結(jié)點(diǎn)

5.If步驟4中是否產(chǎn)生新的雙向相似關(guān)系

Then跳到步驟1繼續(xù)匹配

Else

利用改進(jìn)的有序PMF方法匹配G1和G2中剩余的未匹配結(jié)點(diǎn)

End if

3.3.3 OMIGM算法中使用的相似量度

本小節(jié)主要介紹本文提出的基于互信息的無(wú)向圖結(jié)點(diǎn)間相似度的度量方法。在上文介紹的OMIGM(MS,MT)算法中提到了需要根據(jù)有序互信息歐式距離在G2中尋找與G1最相似的結(jié)點(diǎn)的方法。假定要計(jì)算G1中結(jié)點(diǎn)n1和G2中結(jié)點(diǎn)n2之間的相似度，可以從互信息矩陣中很容易發(fā)現(xiàn)以下兩點(diǎn)知識(shí)：

首先，G1中結(jié)點(diǎn)n1與G1中的其他結(jié)點(diǎn)之間的互信息對(duì)應(yīng)于互信息依賴矩陣MS的第n1行各元素，記作向量MS,n1。

其次，G1中結(jié)點(diǎn)n1與G2中結(jié)點(diǎn)n2之間的相似度

可以用向量MS,n1與MT,n2之間的歐式距離來(lái)表示。

記G1中結(jié)點(diǎn)n1與G2中結(jié)點(diǎn)n2之間的相似度為Simn1,n2，那么有：

其中，Simn1,n2是一個(gè)非負(fù)數(shù)，用它可以作為圖G1中的結(jié)點(diǎn)n1與圖G2中的結(jié)點(diǎn)n2之間的相似度。

3.3.4 基于有序互信息的無(wú)向圖結(jié)點(diǎn)匹配中發(fā)生的“死鎖”問(wèn)題

OMIGM算法的詳細(xì)流程，其本身并不復(fù)雜，但仍有一些細(xì)節(jié)值得分析。在該匹配算法中當(dāng)沒(méi)有找到G1和G2新的結(jié)點(diǎn)匹配對(duì)時(shí)會(huì)跳出匹配過(guò)程，執(zhí)行下面改進(jìn)的有序PMF方法來(lái)匹配G1和G2中剩余的未匹配結(jié)點(diǎn)。之所以這么做，是因?yàn)樵谄ヅ溥^(guò)程中可能會(huì)出現(xiàn)以下4種情形，如圖2所示。圖中，橙色代表G1→G2方向的單向映射；黑色代表G2→G1方向的單向映射；綠色代表G1?G2雙向映射。

Fig.2 “Deadlock”state in nodes matching process圖2 圖結(jié)點(diǎn)匹配中出現(xiàn)的“死鎖”狀態(tài)

在采用有序互信息方法進(jìn)行無(wú)向圖匹配中可能會(huì)出現(xiàn)4種情況，即正常狀態(tài)、可優(yōu)化狀態(tài)、部分“死鎖”狀態(tài)和完全“死鎖”狀態(tài)。正常狀態(tài)是指G1中的結(jié)點(diǎn)和G2中的結(jié)點(diǎn)之間互為最近結(jié)點(diǎn)，所有結(jié)點(diǎn)間呈現(xiàn)一一對(duì)應(yīng)關(guān)系，如圖2（a）所示?？蓛?yōu)化狀態(tài)是指在某一確定方法的單向映射關(guān)系中，存在一對(duì)多映射的情形，如圖2（b）所示，由于這種情況重新指派映射關(guān)系解決，故稱為可優(yōu)化狀態(tài)。如在圖2（b）中可以將結(jié)點(diǎn)s2到t2的映射重新指派為s2到t3。在OMIGM算法中通過(guò)繼續(xù)迭代使處于可優(yōu)化狀態(tài)的結(jié)點(diǎn)繼續(xù)進(jìn)行下一次迭代過(guò)程。部分“死鎖”和完全“死鎖”狀態(tài)是指在無(wú)向圖結(jié)點(diǎn)過(guò)程中出現(xiàn)G1和G2中兩個(gè)結(jié)點(diǎn)子集之間的所有映射構(gòu)成一個(gè)環(huán)形回路，此時(shí)基于互信息的量度已經(jīng)失效，需要重新考慮其他特征匹配模式G1中剩余結(jié)點(diǎn)和模式G2中剩余結(jié)點(diǎn)，如圖2（c）和圖2（d）所示。

3.3.5 圖結(jié)點(diǎn)匹配過(guò)程“死鎖”問(wèn)題的解決辦法

本小節(jié)介紹一種基于改進(jìn)的有序PMF方法解決上文提到的“死鎖”問(wèn)題。Jaiswal等人提出了基于有序列取值分布PMF的模式匹配方法[12]，該方法能夠在模式匹配中同時(shí)完成列匹配和列值映射過(guò)程，給不同編碼的數(shù)據(jù)源集成提供了全新思路。但該方法也存在明顯的缺陷，比如通過(guò)比較兩個(gè)列取值的PMF獲得兩列相似性的方法，其實(shí)質(zhì)是計(jì)算兩個(gè)向量歐式距離，因此當(dāng)取值較多的列匹配時(shí)難免會(huì)出現(xiàn)高維向量間歐式距離失效問(wèn)題，影響匹配準(zhǔn)確率。

針對(duì)上述問(wèn)題，本文對(duì)Jaiswal等人提出的基于有序列取值分布PMF匹配方法進(jìn)行了改進(jìn)，按照樣本中屬性列的獨(dú)立取值的個(gè)數(shù)占總樣本個(gè)數(shù)的比例min_percent，將數(shù)據(jù)模式中的所有屬性分為兩大類，即離散型屬性列和連續(xù)型屬性列，兩種類型的屬性采用了不同的匹配方法。對(duì)于獨(dú)立取值較少的離散型屬性列，如性別、年齡等，采用Jaiswal等人提出的方法進(jìn)行匹配；對(duì)于連續(xù)型屬性，如取值為實(shí)數(shù)的速度、高度等屬性，假定這些列的樣本取值服從高斯分布，利用極大似然方法估計(jì)分布均值和方差，利用分布參數(shù)相似性來(lái)表達(dá)連續(xù)型屬性列之間的相似程度。一般將min_percent設(shè)置為30%即可。

4 驗(yàn)證分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了計(jì)算數(shù)據(jù)模式匹配算法的準(zhǔn)確性，本文從數(shù)據(jù)集中依次抽取k個(gè)屬性，并將第k次抽取的屬性記作 ck，由 c1、c2直到ck構(gòu)成數(shù)據(jù)模式 S(c1,c2,…,ck),將數(shù)據(jù)模式S中各個(gè)屬性列次序隨機(jī)打亂構(gòu)成模式T(cq1,cq2,…,cqk)，其中序列 q1,q2,…,qk是隨機(jī)打亂后的次序。從數(shù)據(jù)集兩個(gè)模式的樣本中抽取兩個(gè)相同數(shù)量的樣本作為輸入，在假定不知道列名的情況下，尋找模式S和T的列之間的最佳對(duì)應(yīng)關(guān)系，最后通過(guò)驗(yàn)證S和T中存在對(duì)應(yīng)關(guān)系的屬性列的列名是否相同，從而統(tǒng)計(jì)出匹配的準(zhǔn)確率。在實(shí)驗(yàn)中數(shù)據(jù)模式大小（即包含在數(shù)據(jù)模式中的屬性列數(shù)目）從2依次增加到30，同一數(shù)據(jù)模式大小的匹配實(shí)驗(yàn)重復(fù)50次，求得平均準(zhǔn)確率。為證明本文提出的基于有序互信息的模式匹配算法（OMIGM）的有效性，將該算法實(shí)驗(yàn)結(jié)果與Kang和Naughton提出的方法（MI-Heuristic）在兩個(gè)數(shù)據(jù)集上進(jìn)行比較。

4.2 相關(guān)數(shù)據(jù)集

本文在實(shí)驗(yàn)中使用了Census2000數(shù)據(jù)集（ftp://ftp2.census.gov/census_2000/datasets/）和 Loans數(shù)據(jù)集（https://www.lendingclub.com/info/download-data.action）作為測(cè)試數(shù)據(jù)集。Census2000數(shù)據(jù)集是美國(guó)聯(lián)邦統(tǒng)計(jì)局2000年的全美人口信息統(tǒng)計(jì)結(jié)果，按照各州進(jìn)行組織，本實(shí)驗(yàn)中用到了加州和紐約的統(tǒng)計(jì)數(shù)據(jù)，即CensusCA和CensusYK部分的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，其中包含112個(gè)屬性，共計(jì)13 696條記錄。實(shí)驗(yàn)中使用到的另一個(gè)數(shù)據(jù)集是Loans數(shù)據(jù)集，它來(lái)自美國(guó)在線個(gè)人信貸網(wǎng)站Lending Club 2015年的全年數(shù)據(jù)，其中包含賬戶信息、借貸信息等105個(gè)屬性，共計(jì)421 094條記錄。由于這些樣本中存在不少缺值情況非常嚴(yán)重的屬性列，需要根據(jù)信息熵過(guò)濾掉部分熵值過(guò)低（熵值不超過(guò)1）的屬性列。過(guò)濾后的結(jié)果如表1所示。

Table 1 Size of datasets表1 數(shù)據(jù)集的大小

4.3 實(shí)驗(yàn)結(jié)果及分析

4.3.1 在不同樣本集上的實(shí)驗(yàn)結(jié)果

當(dāng)樣本數(shù)目為10 000，實(shí)驗(yàn)次數(shù)為50時(shí)，本文提出的有序互信息圖結(jié)點(diǎn)匹配方法（OMIGM）與之前提出的基于互信息啟發(fā)式無(wú)向圖結(jié)點(diǎn)匹配方法（每步匹配候選結(jié)點(diǎn)數(shù)為3）分別在Census2000數(shù)據(jù)集和Loans數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比如圖3和圖4所示。

Fig.3 Experiment result in Census2000 dataset圖3 在數(shù)據(jù)集Census2000上的實(shí)驗(yàn)結(jié)果

Fig.4 Experiment result in Loans dataset圖4 在數(shù)據(jù)集Loans上的實(shí)驗(yàn)結(jié)果

從圖3和圖4中可以看出，在兩個(gè)數(shù)據(jù)集上，基于有序互信息圖匹配方法不僅在準(zhǔn)確率方面較基于互信息歐式距離啟發(fā)式匹配方法有比較明顯的提高，而且在識(shí)別的穩(wěn)定性方面也優(yōu)于后者，即使在屬性數(shù)目增加到20個(gè)時(shí)仍有接近94%的準(zhǔn)確率。基于互信息的歐式距離啟發(fā)式匹配方法中匹配的準(zhǔn)確率在很大程度上依賴于每步匹配時(shí)考慮的候選匹配列的數(shù)目k（與當(dāng)前結(jié)點(diǎn)信息熵最接近的k個(gè)屬性列作為候選匹配列），極端情況下當(dāng)數(shù)據(jù)模式的所有屬性列在樣本中信息熵分布比較接近時(shí)，準(zhǔn)確地使候選列集合中包含正確的匹配列將變得愈發(fā)困難，故當(dāng)數(shù)據(jù)模式中包含的屬性列數(shù)目增加時(shí)，匹配準(zhǔn)確率呈現(xiàn)比較明顯的下降趨勢(shì)。本文方法由于在考慮候選列時(shí)不只依賴信息熵，還依賴于當(dāng)前列與模式中其他列之間的依賴關(guān)系，即使遇到屬性列多且信息熵分布比較密集的情況下仍能找到正確的匹配列，即使數(shù)據(jù)模式中的屬性列數(shù)目增加，本文方法的匹配準(zhǔn)確率也沒(méi)有出現(xiàn)明顯的下降趨勢(shì)。

4.3.2 算法的運(yùn)行時(shí)間比較

為比較本文提出的有序互信息無(wú)向圖結(jié)點(diǎn)匹配方法（OMIGM）與之前提出的基于互信息啟發(fā)式無(wú)向圖結(jié)點(diǎn)匹配方法在運(yùn)行時(shí)間方面的差異，在同一數(shù)據(jù)集Census2000上對(duì)兩種方法的運(yùn)行時(shí)間進(jìn)行了統(tǒng)計(jì)，數(shù)據(jù)模式大小從2依次增加到14，每個(gè)數(shù)據(jù)模式大小做20次實(shí)驗(yàn)求得平均運(yùn)行時(shí)間。但考慮到單機(jī)環(huán)境下啟發(fā)式匹配方法在屬性個(gè)數(shù)增加到14時(shí)運(yùn)行時(shí)間已經(jīng)變得無(wú)法接受，故將數(shù)據(jù)模式大小增加到14時(shí)終止。統(tǒng)計(jì)結(jié)果如圖5所示。

Fig.5 Statistical result of running time圖5 運(yùn)行時(shí)間統(tǒng)計(jì)結(jié)果

從圖5中可以看出，當(dāng)數(shù)據(jù)模式中屬性列個(gè)數(shù)超過(guò)10后，啟發(fā)式算法匹配需要花費(fèi)的時(shí)間呈現(xiàn)出指數(shù)增長(zhǎng)，而本文方法花費(fèi)的時(shí)間比前者少得多，而且隨著屬性個(gè)數(shù)增加，運(yùn)行時(shí)間并沒(méi)有出現(xiàn)較大增長(zhǎng)。事實(shí)上，當(dāng)屬性個(gè)數(shù)超過(guò)50時(shí)，本文基于有序互信息的匹配方法的運(yùn)行時(shí)間也是小時(shí)級(jí)。

4.3.3 數(shù)據(jù)集中信息熵分布對(duì)結(jié)果的影響

為了分析不同樣本對(duì)本文提出的基于有序互信息無(wú)向圖結(jié)點(diǎn)匹配準(zhǔn)確率的影響，在實(shí)驗(yàn)中統(tǒng)計(jì)了Census2000和Loans兩個(gè)數(shù)據(jù)集在經(jīng)過(guò)過(guò)濾后剩余所有屬性的信息熵。統(tǒng)計(jì)結(jié)果如圖6和圖7所示。

Fig.6 Statistical result of information entropy in Census2000 dataset圖6 Census2000數(shù)據(jù)集信息熵統(tǒng)計(jì)結(jié)果

通過(guò)對(duì)比圖6和圖7中的統(tǒng)計(jì)結(jié)果可以看出，Loans數(shù)據(jù)集中所有屬性列的信息熵分布比Census-2000數(shù)據(jù)集分布更加分散。從統(tǒng)計(jì)圖中可以明顯看出，Census2000數(shù)據(jù)集中大部分屬性列的信息熵集中在區(qū)間6到8之間，反觀Loans數(shù)據(jù)集中有接近一半的屬性列的信息熵集中在4到6之間。信息熵反映的是屬性列中蘊(yùn)含的信息量大小，由此可見(jiàn)Loans數(shù)據(jù)集中信息總量要明顯少于Census2000數(shù)據(jù)集，這就解釋了兩種匹配方法在Loans數(shù)據(jù)集上的匹配準(zhǔn)確率明顯低于其在Census2000數(shù)據(jù)集上的準(zhǔn)確率，這點(diǎn)從圖3和圖4的結(jié)果中可以看出。

4.3.4 樣本數(shù)量對(duì)結(jié)果的影響

為了評(píng)估樣本大小對(duì)實(shí)驗(yàn)結(jié)果的影響，本文從Loans數(shù)據(jù)集中抽取3個(gè)樣本數(shù)量分別為1 000、5 000和10 000的樣本。數(shù)據(jù)模式中屬性列數(shù)目從2增加到10，每個(gè)數(shù)據(jù)模式大小樣本各抽樣10次，求樣本的平均差異度。樣本的差異度是指每次抽取的模式數(shù)據(jù)樣本統(tǒng)計(jì)得來(lái)的兩個(gè)互信息依賴矩陣中所有元素的差的平方和。統(tǒng)計(jì)后的結(jié)果如圖8所示。

Fig.7 Statistical result of information entropy in Loans dataset圖7 Loans數(shù)據(jù)集信息熵統(tǒng)計(jì)結(jié)果

Fig.8 Statistical result of average diversity圖8 樣本平均差異度統(tǒng)計(jì)結(jié)果

從圖8中的統(tǒng)計(jì)結(jié)果可以看出，隨著模式中屬性數(shù)量的增加，平均樣本差異度也呈現(xiàn)很明顯的上升趨勢(shì)。但是顯然當(dāng)樣本數(shù)量為10 000時(shí)，平均差異度的上升趨勢(shì)較為平緩，這就表明在進(jìn)行模式匹配時(shí)，模式S和模式T各自對(duì)應(yīng)的互信息矩陣MS和MT之間的差異相較于1 000和5 000樣本時(shí)的差異要小一些，從而減少了因樣本差異引起的錯(cuò)誤匹配情況的發(fā)生。當(dāng)然，樣本數(shù)量越大平均差異度越小，但同樣會(huì)導(dǎo)致計(jì)算互信息依賴矩陣時(shí)花費(fèi)的時(shí)間變長(zhǎng)。綜合考慮以上因素后，在本文的實(shí)驗(yàn)中采用10 000作為樣本大小進(jìn)行模式匹配。

5 結(jié)論

本文提出了一種基于有序互信息的數(shù)據(jù)模式匹配方法，其通過(guò)對(duì)列之間的互信息進(jìn)行排序?qū)⑷謨?yōu)化問(wèn)題降為局部?jī)?yōu)化問(wèn)題，通過(guò)尋找雙向匹配提高了匹配結(jié)果的可靠性。當(dāng)出現(xiàn)“死鎖”情形時(shí)，利用改進(jìn)的有序PMF方法匹配發(fā)生“死鎖”后的剩余屬性列，進(jìn)一步提高了匹配的準(zhǔn)確率。通過(guò)在兩個(gè)數(shù)據(jù)集上對(duì)比基于有序互信息的圖匹配方法和基于互信息的啟發(fā)式匹配方法的實(shí)驗(yàn)結(jié)果，證明了本文方法不僅在匹配準(zhǔn)確率和算法耗時(shí)等方面都明顯優(yōu)于后者，而且具有更好的通用性。

[1]Bernstein PA,Madhavan J,Rahm E.Generic schema matching,ten years later[J].Proceedings of the VLDB Endowment,2011,4(11):695-701.

[2]Bilke A,Naumann F.Schema matching using duplicates[C]//Proceedings of the 2005 International Conference on Data Engineering,Tokyo,Apr 5-8,2005.Piscataway,USA:IEEE,2005:69-80.

[3]Embley D W,Jackman D,Li Xu.Multifaceted exploitation of metadata for attribute match discovery in information integration[C]//Proceedings of the 2001 International Workshop on Information Integration on the Web,Rio de Janeiro,Apr 9-11,2001:110-117.

[4]Madhavan J,Bernstein P A,Rahm E.Generic schema matching with cupid[C]//Proceedings of the 27th International Conference on Very Large Data Bases,Roma,Italy,Sep 11-14,2001.San Francisco,USA:Morgan Kaufmann Publishers Inc,2001:49-58.

[5]Li W S,Clifton C.SEMINT:a tool for identifying attribute correspondences in heterogeneous databases using neural networks[J].Data&Knowledge Engineering,2000,33(1):49-84.

[6]Berlin J,Motro A.Database schema matching using machine learning with feature selection[C]//LNCS 2348:Proceedings of the 2002 International Conference on Advanced Information Systems Engineering,Toronto,Canada,May 27-31,2002.Berlin,Heidelberg:Springer,2002:452-466.

[7]Bernstein P A,Melnik S,Petropoulos M,et al.Industrialstrength schema matching[J].ACM SIGMOD Record,2004,33(4):38-43.

[8]Drumm C,Schmitt M,Do H H,et al.Quickmig:automatic schema matching for data migration projects[C]//Proceedings of the 16th Conference on Information and Knowledge Management,Lisbon,Portugal,Nov 6-10,2007.New York:ACM,2007:107-116.

[9]Do H H,Rahm E.COMA:a system for flexible combination of schema matching approaches[C]//Proceedings of the 28th International Conference on Very Large Data Bases,Hong Kong,China,Aug 20-23,2002:610-621.

[10]Algergawy A,Massmann S,Rahm E.A clustering-based approach for large-scale ontology matching[C]//LNCS 6909:Proceedings of the 2011 East European Conference on Advances in Databases and Information Systems,Vienna,Austria,Sep 20-23,2011.Berlin,Heidelberg:Springer,2011:415-428.

[11]Rodrigues D,da Silva A S,Rodrigues R,et al.Using active learning techniques for improving database schema matching methods[C]//Proceedings of the 2015 International Joint Conference on Neural Networks,Killarney,Ireland,Jul 12-17,2015.Piscataway,USA:IEEE,2015:1-8.

[12]Ferragut E,Laska J.Nonparametric Bayesian modeling for automated database schema matching[C]//Proceedings of the 14th IEEE International Conference on Machine Learning and Applications,Miami,USA,Dec 9-11,2015.Piscataway,USA:IEEE,2015:82-88.

[13]Kang J,Naughton J F.On schema matching with opaque column names and data values[C]//Proceedings of the 2003 International Conference on Management of Data,San Diego,USA,Jun 9-12,2003.New York:ACM,2003:205-216.

[14]Kang J,Lee D,Mitra P.Identifying value mappings for data integration:an unsupervised approach[C]//Proceedings of the 2005 International Conference on Web Information Systems Engineering,New York,Nov 20-22,2005.Berlin,Heidelberg:Springer,2005:544-551.

[15]JaiswalA,Miller D J,Mitra P.Un-interpreted schema matching with embedded value mapping under opaque column names and data values[J].IEEE Transactions on Knowledge&Data Engineering,2009,22(2):291-304.

GUO Lele was born in 1990.He is an M.S.candidate at School of Computer and Information Technology,Beijing Jiaotong University.His research interests include algorithm design and data integration,etc.

郭樂(lè)樂(lè)（1990—），男，陜西西安人，北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)樗惴ㄔO(shè)計(jì)與分析，數(shù)據(jù)集成等。

林友芳（1971—），男，福建武平人，北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院副院長(zhǎng)、教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)技術(shù)，商業(yè)智能等。

HAN Sheng was born in 1980.He received the M.S.degree from Beijing Jiaotong University in 2005.Now he is a lecturer at School of Computer and Information Technology,Beijing Jiaotong University.His research interests include software engineering and data housing,etc.

韓升（1980—）男，山西長(zhǎng)治人，2005年于北京交通大學(xué)獲得碩士學(xué)位，現(xiàn)為北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院講師，主要研究領(lǐng)域?yàn)檐浖こ?，?shù)據(jù)倉(cāng)庫(kù)等。

Using Ordered Mutual Information to Match Schema with Opaque Column Names and Data Values*

GUO Lele+,LIN Youfang,HAN Sheng
Beijing Key Laboratory of Traffic Data Analysis and Mining,School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China

As a key issue of data integration,schema matching is the core task in data merging process of heterogeneous data sources.At present,a mass of schema matching methods have been proposed.However,most of them are lack of universality since they depend on the description information of schema heavily.Therefore,it is difficult to apply these approaches to other scenarios.To solve the problem,this paper proposes a novel schema matching method which uses ordered mutual information and does not rely on any description information of schema,such as column name,column type and foreign constraints,which make it own a strong universality.Furthermore,extensive experiments on various datasets indicate that the proposed technique outperforms earlier schema matching methods in terms of efficiency and accuracy.

schema matching;opaque conditions;mutual information;undirected graph matching

the Ph.D.degree from Beijing Jiaotong University.He is a professor and Ph.D.supervisor at School of Computer and Information Technology,Beijing Jiaotong University.His research interests include big data technology and business intelligence,etc.

2016-08, Accepted 2016-10.

A

TP391.4

+Corresponding author:E-mail:guolele@bjtu.edu.cn

GUO Lele,LIN Youfang,HAN Sheng.Using ordered mutual information to match schema with opaque column names and data values.Journal of Frontiers of Computer Science and Technology,2017,11(9)：1389-1397.

10.3778/j.issn.1673-9418.1609004

*The National Natural Science Foundation of China under Grant Nos.61403023,61603029(國(guó)家自然科學(xué)基金);the Research Fund of Ministry of Education-China Mobile under Grant No.MCM20150513(教育部-中國(guó)移動(dòng)科研基金);the Fundamental Research Funds for the Central Universities of China(中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金).

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2016-10-31, http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.016.html