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

郭樂樂，林友芳，韓 升

北京交通大學 計算機與信息技術學院 交通數(shù)據(jù)分析與挖掘北京市重點實驗室，北京 100044

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

郭樂樂+，林友芳，韓 升

北京交通大學 計算機與信息技術學院 交通數(shù)據(jù)分析與挖掘北京市重點實驗室，北京 100044

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

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

1 引言

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

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

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

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

本文正是在Kang和Naughton提出的基于互信息匹配方法的基礎上，提出了一種全新的互信息無向圖結點匹配方法。實驗結果表明，本文方法能夠顯著提高模式匹配的準確率，并能夠降低匹配花費時間。本文的主要貢獻有：

（1）結合互信息依賴矩陣，提出了一種基于有序互信息的無向圖結點匹配方法。

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

2 相關概念

2.1 可表達匹配和不可表達匹配

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

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

2.2 元素匹配與結構匹配

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

2.3 模式匹配算法分類

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

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

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

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

3.1 算法主要流程

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

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

步驟2將互信息矩陣MS和MT分別看作帶權無向圖G1和G2的鄰接矩陣，從而將模式匹配問題轉化為尋找G1和G2中各個結點的最佳映射關系問題。

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

3.2 互信息矩陣的計算方法

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

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

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

3.3 基于有序互信息的無向圖匹配

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

3.3.1 基于互信息啟發(fā)式無向圖結點匹配算法

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

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

3.3.2 基于有序互信息無向圖結點匹配算法

正因為基于啟發(fā)信息匹配方法存在性能和準確率方面的問題，本文給出一種基于有序互信息的無向圖結點匹配算法（ordered mutual information graph match algorithm，OMIGM）。

算法1OMIGM(MS,MT)算法

輸入：兩個無向圖G1和G2分別對應的兩個互信息依賴矩陣MS和MT。

輸出：圖G1和G2結點之間的最佳對應關系。1.分別篩選出圖G1和G2中剩余待匹配結點

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

3.用步驟2中的方法，可以依次求得圖G2中各個待匹配結點在圖G1待匹配結點中的最相似結點，將單向相似關系存入關系集R2中

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

5.If步驟4中是否產生新的雙向相似關系

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

Else

利用改進的有序PMF方法匹配G1和G2中剩余的未匹配結點

End if

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

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

首先，G1中結點n1與G1中的其他結點之間的互信息對應于互信息依賴矩陣MS的第n1行各元素，記作向量MS,n1。

其次，G1中結點n1與G2中結點n2之間的相似度

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

記G1中結點n1與G2中結點n2之間的相似度為Simn1,n2，那么有：

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

3.3.4 基于有序互信息的無向圖結點匹配中發(fā)生的“死鎖”問題

OMIGM算法的詳細流程，其本身并不復雜，但仍有一些細節(jié)值得分析。在該匹配算法中當沒有找到G1和G2新的結點匹配對時會跳出匹配過程，執(zhí)行下面改進的有序PMF方法來匹配G1和G2中剩余的未匹配結點。之所以這么做，是因為在匹配過程中可能會出現(xiàn)以下4種情形，如圖2所示。圖中，橙色代表G1→G2方向的單向映射；黑色代表G2→G1方向的單向映射；綠色代表G1?G2雙向映射。

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

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

3.3.5 圖結點匹配過程“死鎖”問題的解決辦法

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

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

4 驗證分析

4.1 實驗設計

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

4.2 相關數(shù)據(jù)集

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

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

4.3 實驗結果及分析

4.3.1 在不同樣本集上的實驗結果

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

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

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

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

4.3.2 算法的運行時間比較

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

Fig.5 Statistical result of running time圖5 運行時間統(tǒng)計結果

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

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

為了分析不同樣本對本文提出的基于有序互信息無向圖結點匹配準確率的影響，在實驗中統(tǒng)計了Census2000和Loans兩個數(shù)據(jù)集在經過過濾后剩余所有屬性的信息熵。統(tǒng)計結果如圖6和圖7所示。

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

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

4.3.4 樣本數(shù)量對結果的影響

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

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

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

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

5 結論

本文提出了一種基于有序互信息的數(shù)據(jù)模式匹配方法，其通過對列之間的互信息進行排序將全局優(yōu)化問題降為局部優(yōu)化問題，通過尋找雙向匹配提高了匹配結果的可靠性。當出現(xiàn)“死鎖”情形時，利用改進的有序PMF方法匹配發(fā)生“死鎖”后的剩余屬性列，進一步提高了匹配的準確率。通過在兩個數(shù)據(jù)集上對比基于有序互信息的圖匹配方法和基于互信息的啟發(fā)式匹配方法的實驗結果，證明了本文方法不僅在匹配準確率和算法耗時等方面都明顯優(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.

郭樂樂（1990—），男，陜西西安人，北京交通大學計算機與信息技術學院碩士研究生，主要研究領域為算法設計與分析，數(shù)據(jù)集成等。

林友芳（1971—），男，福建武平人，北京交通大學計算機與信息技術學院副院長、教授、博士生導師，主要研究領域為大數(shù)據(jù)技術，商業(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—）男，山西長治人，2005年于北京交通大學獲得碩士學位，現(xiàn)為北京交通大學計算機與信息技術學院講師，主要研究領域為軟件工程，數(shù)據(jù)倉庫等。

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(國家自然科學基金);the Research Fund of Ministry of Education-China Mobile under Grant No.MCM20150513(教育部-中國移動科研基金);the Fundamental Research Funds for the Central Universities of China(中央高校基本科研業(yè)務費專項資金).

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