王 豐,王亞沙,趙俊峰,4,崔 達(dá)

1(高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(北京大學(xué)),北京 100871)

2(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院,北京 100871)

3(軟件工程國家工程中心(北京大學(xué)),北京 100871)

4(北京大學(xué)(天津?yàn)I海)新一代信息技術(shù)研究院,天津 300450)

語義網(wǎng)(semantic Web)作為下一代互聯(lián)網(wǎng)規(guī)范,在促進(jìn)數(shù)據(jù)交互和知識(shí)共享等方面具有重大意義.本體是語義網(wǎng)的核心,是特定領(lǐng)域共享概念模型的形式化規(guī)范說明,被廣泛地用于刻畫特定領(lǐng)域的知識(shí)模型[1,2].但是在實(shí)際的語義網(wǎng)應(yīng)用中,常常面臨本體實(shí)例匱乏的問題,考慮到現(xiàn)有的城市系統(tǒng)中,大量的實(shí)例數(shù)據(jù)的主流存儲(chǔ)方式仍然是關(guān)系型數(shù)據(jù)庫[3],將關(guān)系數(shù)據(jù)庫中結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)化為本體實(shí)例能夠有效地對(duì)領(lǐng)域本體實(shí)例進(jìn)行擴(kuò)充.為了實(shí)現(xiàn)這種轉(zhuǎn)化,首要任務(wù)是建立關(guān)系數(shù)據(jù)源中的模式到本體中概念的映射關(guān)系;此外,建立這種映射關(guān)系的需求,還廣泛存在于數(shù)據(jù)集成、數(shù)據(jù)語義標(biāo)注、基于本體的數(shù)據(jù)訪問等多個(gè)與本體密切相關(guān)的領(lǐng)域.

關(guān)系數(shù)據(jù)模式到本體映射關(guān)系的建立,是一類典型的模式匹配問題[4-6].所謂模式匹配問題,指的是在不同的數(shù)據(jù)模式中找出語義相同或相似的元素對(duì),并構(gòu)造映射關(guān)系的一類問題[7,8],即建立數(shù)據(jù)庫表到本體中類的映射以及數(shù)據(jù)庫表中字段到本體類的屬性的映射.圖1所示是一個(gè)關(guān)系數(shù)據(jù)庫模式到本體的模式匹配示例.

Fig.1 Example of schema matching圖1 模式匹配示例

人工地進(jìn)行模式匹配工作過于費(fèi)時(shí)費(fèi)力,且容易出現(xiàn)誤差.為了降低人力成本,提高模式匹配的準(zhǔn)確率,研究者們提出了許多自動(dòng)化方法和框架,通過利用模式本身的元信息或者元素所含實(shí)例特征等信息,計(jì)算得到不同模式之間元素對(duì)的相似度,來輔助人工來進(jìn)行模式匹配.根據(jù)所利用的信息的不同,可以劃分為若干種基本模式匹配算法,例如使用元素標(biāo)簽信息的基于字符串的匹配算法、使用實(shí)例統(tǒng)計(jì)特征的基于統(tǒng)計(jì)的匹配算法等.單一的模式匹配算法只考慮元素在某個(gè)特征上的相似度,在應(yīng)用時(shí)可能會(huì)出現(xiàn)匹配不準(zhǔn)確的情況,所以現(xiàn)有的模式匹配框架往往會(huì)使用多種模式匹配算法,綜合考慮元素對(duì)在多個(gè)特征上的相似性,來獲得更為全面準(zhǔn)確的結(jié)果,然而,這種做法并未從本質(zhì)上分析導(dǎo)致匹配準(zhǔn)確率不高的原因,當(dāng)多種模式匹配算法均存在較大偏差時(shí),仍然無法得到準(zhǔn)確的綜合結(jié)果.

針對(duì)以上問題,本文從數(shù)據(jù)源本地化特征的角度分析了單一模式匹配算法匹配不準(zhǔn)的原因.數(shù)據(jù)源的本地化特征,主要體現(xiàn)在兩個(gè)方面.

· 一方面是由各數(shù)據(jù)源模式獨(dú)立、自主設(shè)計(jì)而導(dǎo)致的模式結(jié)構(gòu)的本地化.

例如在關(guān)系數(shù)據(jù)庫模式設(shè)計(jì)時(shí),設(shè)計(jì)者一般不會(huì)參照同領(lǐng)域中其他數(shù)據(jù)源的模式,也不會(huì)刻意使用領(lǐng)域中標(biāo)準(zhǔn)化的專業(yè)術(shù)語來建立數(shù)據(jù)字典,而是根據(jù)其對(duì)業(yè)務(wù)的理解獨(dú)立完成數(shù)據(jù)庫模式設(shè)計(jì).而本體與某個(gè)特定的數(shù)據(jù)庫模式不同,是表達(dá)了領(lǐng)域共性知識(shí)的規(guī)范化說明.數(shù)據(jù)庫模式與本體這一本質(zhì)區(qū)別,必然導(dǎo)致了本體和實(shí)際的關(guān)系數(shù)據(jù)模式存在差別,而在術(shù)語的使用上體現(xiàn)得尤為明顯.為了解決術(shù)語使用的差異化問題,現(xiàn)有的基于字符串的模式匹配算法常常需要同義詞詞典來解決這個(gè)問題.而特定業(yè)務(wù)領(lǐng)域的術(shù)語和同義詞,并不一定包含在已有的通用的同義詞詞典中,故而匹配準(zhǔn)確率低.

· 本地化特征的另一方面是由于業(yè)務(wù)特征差異導(dǎo)致的數(shù)據(jù)實(shí)體統(tǒng)計(jì)特征的本地化.

真實(shí)數(shù)據(jù)源中,其實(shí)例的統(tǒng)計(jì)特征往往與其服務(wù)的業(yè)務(wù)相關(guān).以餐飲領(lǐng)域的收銀管理相關(guān)數(shù)據(jù)為例,主營商務(wù)宴會(huì)的餐飲品牌,其每單金額的均值和方差都遠(yuǎn)遠(yuǎn)高于主營地方小吃的餐飲品牌.本體模型中包含的實(shí)例,往往是由多個(gè)數(shù)據(jù)源中的數(shù)據(jù)轉(zhuǎn)化而來,其實(shí)例數(shù)據(jù)的統(tǒng)計(jì)特征反應(yīng)了不同餐飲品牌的綜合平均值,與主營商務(wù)宴會(huì)或地方小吃的餐飲品牌的實(shí)際數(shù)據(jù),其實(shí)例統(tǒng)計(jì)特征都存在存在較大差異,從而導(dǎo)致基于數(shù)據(jù)實(shí)例統(tǒng)計(jì)特征的匹配算法失效.

綜上所述,數(shù)據(jù)源的本地化特征是導(dǎo)致數(shù)據(jù)源在模式和實(shí)例上與本體存在較大差異的重要原因,而由于在進(jìn)行模式匹配前無法預(yù)先確悉數(shù)據(jù)源的本地化特征,直接應(yīng)用模式匹配算法時(shí)則必然導(dǎo)致匹配不準(zhǔn)確的情況.

針對(duì)數(shù)據(jù)源存在的本地化特征的客觀情況,本文提出一種迭代優(yōu)化的模式匹配方案,其基本思想是:利用在模式匹配過程中得到的一部分匹配的元素對(duì)來對(duì)各單一模式匹配算法進(jìn)行優(yōu)化,從而提高單一算法的準(zhǔn)確性,最終提高整個(gè)模式匹配過程的準(zhǔn)確率.具體地,本文對(duì)兩種典型的模式匹配算法——基于字符串的模式匹配算法以及基于實(shí)例的模式匹配算法進(jìn)行優(yōu)化.對(duì)于已經(jīng)得到匹配的元素對(duì),其標(biāo)簽可以看作是一對(duì)同義詞,自動(dòng)加入到同義詞詞典中,基于字符串的模式匹配算法利用該自動(dòng)生成的同義詞詞典,就能夠兼容數(shù)據(jù)源在術(shù)語使用上的本地化;已經(jīng)得到匹配的元素對(duì),其實(shí)例統(tǒng)計(jì)特征可以作為一種匹配知識(shí),作為訓(xùn)練集進(jìn)行訓(xùn)練,得到一個(gè)分類模型,該分類模型由于吸納了先前匹配的經(jīng)驗(yàn),故而可以很好地兼容數(shù)據(jù)源在實(shí)例上的本地化特征.

本文以餐飲信息管理領(lǐng)域的一個(gè)實(shí)際案例開展模式匹配實(shí)驗(yàn),并與現(xiàn)有的相關(guān)工作進(jìn)行對(duì)比,證明了本文模式匹配算法的有效性和準(zhǔn)確性.本文的主要貢獻(xiàn)如下.

(1) 以餐飲系統(tǒng)為例對(duì)數(shù)據(jù)源的本地化特征進(jìn)行了分析,分析了本地化特征的種類與其產(chǎn)生的原因.

(2) 提出一種迭代優(yōu)化的模式匹配方法IOSMA(iterative optimization schema matching algorithm),算法在迭代過程中,利用已經(jīng)匹配成功的元素對(duì)優(yōu)化模式匹配算法,使模式匹配算法隨著迭代可以逐漸取得更好的匹配效果.

(3) 在餐飲數(shù)據(jù)集上進(jìn)行了測(cè)試,結(jié)果顯示,本文提出的迭代優(yōu)化的模式匹配算法效果優(yōu)于基線算法.

本文第1節(jié)介紹現(xiàn)有的模式匹配算法與模式匹配框架.第2節(jié)詳細(xì)分析數(shù)據(jù)源本地化特征的原因和對(duì)模式匹配算法的影響.第 3節(jié)詳細(xì)介紹本文的模式匹配方案.第 4節(jié)介紹實(shí)驗(yàn)設(shè)計(jì)和實(shí)驗(yàn)結(jié)果.第 5節(jié)對(duì)本文進(jìn)行總結(jié).

1 相關(guān)工作

1.1 模式匹配算法

模式匹配算法衡量不同數(shù)據(jù)模式的元素對(duì)在某種特征上的相似性,對(duì)輸入的兩個(gè)來自不同數(shù)據(jù)模式中的元素,輸出一個(gè)[0,1]區(qū)間上的實(shí)數(shù)值作為相似程度.經(jīng)過調(diào)研,本文對(duì)基本的模式匹配算法的分類進(jìn)行總結(jié),如圖2所示.

模式匹配算法按照所利用的信息的不同,可以分為基于模式信息的模式匹配算法和基于實(shí)例的模式匹配算法兩個(gè)大類.

· 基于模式信息的模式匹配算法關(guān)注于數(shù)據(jù)模式的元信息,數(shù)據(jù)模式的元信息包括組成數(shù)據(jù)模式的基本元素以及這些基本元素之間的關(guān)系.基于元素的模式匹配算法利用元素本身的信息來判斷元素的相似性,例如通過字符串的編輯距離來計(jì)算元素標(biāo)簽的相似性[9,10],通過數(shù)據(jù)類型的兼容性判斷元素對(duì)匹配的可能性.基于結(jié)構(gòu)的模式匹配算法利用數(shù)據(jù)模式中元素之間的關(guān)系來判斷元素的相似性,例如通過子節(jié)點(diǎn)相似度計(jì)算父節(jié)點(diǎn)相似度的子節(jié)點(diǎn)匹配算法[9,10],或者將輸入的源模式轉(zhuǎn)換為有向圖或者樹的形式,然后利用路徑匹配[11]、圖匹配[12-14]等已經(jīng)成熟的圖算法計(jì)算元素對(duì)的相似度.

· 基于實(shí)例的模式匹配算法關(guān)注元素所含實(shí)例的特征,分為基于語言學(xué)的實(shí)例匹配算法和基于統(tǒng)計(jì)的實(shí)例匹配算法.

? 基于語言學(xué)的實(shí)例匹配算法主要面向數(shù)據(jù)類型為字符串的元素,通過抽取實(shí)例文本的關(guān)鍵詞[9,10,15],然后比較關(guān)鍵詞的相似性;或者以一個(gè)現(xiàn)有的知識(shí)庫為基礎(chǔ),在其中尋找與該元素最符合的概念作為映射[15],然后比較元素對(duì)所映射概念之間的相似性.

? 基于統(tǒng)計(jì)的實(shí)例匹配算法主要有兩種:一種利用兩個(gè)元素實(shí)例上的重合度作為相似度,極易造成漏判;另一種更為主流,主要通過實(shí)例的各種統(tǒng)計(jì)量上的相似度,例如平均值、最大值、最小值、方差等,來計(jì)算元素對(duì)的相似度[16,17].

Fig.2 Classification of schema matching algorithm圖2 模式匹配算法分類

由于用于匹配的數(shù)據(jù)源在模式信息和實(shí)例上存在一定程度的本地化特征,單一地利用模式信息或者實(shí)例來進(jìn)行相似度的計(jì)算必然會(huì)出現(xiàn)匹配不準(zhǔn)確的情況.此外,這些模式匹配算法雖然具有一定程度上的通用性,但是不具備自學(xué)習(xí)能力,且難以兼容數(shù)據(jù)源的本地化特征.本文借鑒了傳統(tǒng)的模式匹配算法,綜合并優(yōu)化了多種已有的模式匹配算法,在迭代的過程中,利用已匹配的信息來優(yōu)化傳統(tǒng)的模式匹配算法,在不斷的迭代中,提高傳統(tǒng)匹配算法在具有本地化特征的數(shù)據(jù)上的正確率.

1.2 模式匹配框架

上一節(jié)討論了多種利用單一特征的模式匹配算法,這些模式匹配算法單獨(dú)使用極易引起誤差,因而現(xiàn)有的模式匹配框架往往采用多種模式匹配算法相結(jié)合的方式,例如 SEMINT[17]、COMA++[9]、RONTO[3]等,其中,COMA++、RONTO支持關(guān)系模型到本體模型的匹配.本文對(duì)一般的關(guān)系模型到本體模型的模式匹配框架進(jìn)行總結(jié),其一般流程如圖3所示.該流程對(duì)于輸入的兩個(gè)異構(gòu)數(shù)據(jù)模式中的元素對(duì)的處理,主要包含3個(gè)階段.

(1) 相似度計(jì)算階段:在這一階段,調(diào)用多種模式匹配算法,對(duì)輸入的來自于兩個(gè)不同數(shù)據(jù)模式的元素對(duì),計(jì)算其在多個(gè)特征維度上的相似度.所選的模式匹配算法和執(zhí)行的先后順序可以由人工來進(jìn)行配置.

(2) 相似度綜合階段:上一階段得到了一個(gè)元素對(duì)的多種相似度,分別來自于所使用的各個(gè)模式匹配算法,為了對(duì)元素對(duì)的匹配進(jìn)行排序、判定、篩選,還需要對(duì)這些相似度進(jìn)行綜合,具體的綜合方式可以是加權(quán)平均,也可以是人工定義的其他規(guī)則.

(3) 相似度判定階段:在這一階段,兩個(gè)異構(gòu)模式中各個(gè)元素對(duì)的綜合相似度已然計(jì)算完畢,按照一定的規(guī)則對(duì)這些元素對(duì)進(jìn)行是否匹配的事實(shí)判定,可以人工地按相似度大小排序后審閱并選擇,也可以根據(jù)人工設(shè)定的規(guī)則,例如閾值,來自動(dòng)地加以判定.

Fig.3 General process of schema matching framework圖3 模式匹配框架的一般流程

現(xiàn)有的模式匹配框架通過綜合利用多種模式匹配算法的結(jié)果來緩解單一模式匹配算法匹配不準(zhǔn)確所產(chǎn)生的誤差,但它們沒有對(duì)單一模式匹配算法匹配不準(zhǔn)確的問題進(jìn)行分析與解決,因而仍然存在匹配準(zhǔn)確率低下、需要較多人工參與等問題.本文算法利用迭代的方法對(duì)元素對(duì)進(jìn)行匹配,每一輪匹配借鑒了現(xiàn)有的模式匹配框架的思路,在每一輪匹配完成后,部分元素得到匹配,利用已匹配的元素對(duì)可以優(yōu)化模式匹配算法,通過迭代可以自動(dòng)地使模式匹配框架適應(yīng)具有本地化特征的數(shù)據(jù),使一些難以匹配的元素對(duì)在迭代過程中得到匹配.

2 數(shù)據(jù)源本地化特征分析

本體被設(shè)計(jì)用于規(guī)范化地表達(dá)領(lǐng)域的知識(shí)模型,包含領(lǐng)域中概念以及概念之間的關(guān)系.由于語義網(wǎng)仍然處在發(fā)展階段,在很多領(lǐng)域中只有本體的定義而缺乏本體的實(shí)例.而真實(shí)存在的數(shù)據(jù)源往往用來為特定的應(yīng)用提供數(shù)據(jù),對(duì)于數(shù)據(jù)存取性能方面要求較高,大多采用關(guān)系數(shù)據(jù)模型作為存儲(chǔ)方式.

根據(jù)應(yīng)用環(huán)境的不同,實(shí)際的數(shù)據(jù)源可以按照應(yīng)用場景、應(yīng)用系統(tǒng)這兩個(gè)維度進(jìn)行劃分,見表1.

Table 1 Partition of data sources表1 數(shù)據(jù)源的劃分

如表1所示,A,B,C,D分別是4個(gè)數(shù)據(jù)源,它們均屬于某個(gè)特定的應(yīng)用場景,例如在餐飲信息管理領(lǐng)域,應(yīng)用場景可以是“宴會(huì)”“特色小吃”“自助”等,屬于同一個(gè)應(yīng)用場景的這些數(shù)據(jù)源,表達(dá)相同概念的元素,其實(shí)例特征具有高度的相似性.而屬于不同應(yīng)用場景的數(shù)據(jù)源,語義相同的元素,其實(shí)例特征可能差別很大,如圖4所示,左側(cè)是主營宴會(huì)餐飲的北京宴品牌,其某個(gè)門店數(shù)據(jù)源中訂單應(yīng)收金額和訂單應(yīng)收服務(wù)費(fèi)的平均值(單位:元),右側(cè)是主營特色小吃的熱河食府品牌,其某個(gè)門店數(shù)據(jù)源中訂單應(yīng)收金額和服務(wù)費(fèi)的平均值(單位:元).通過比較我們發(fā)現(xiàn):這兩個(gè)數(shù)據(jù)源中同為表示應(yīng)收金額的數(shù)據(jù)元素,其平均值相差 10倍以上.這種不同應(yīng)用場景下實(shí)例特征上的差異,本文稱之為實(shí)例的本地化特征.

同樣地,領(lǐng)域中存在多個(gè)不同的應(yīng)用系統(tǒng),例如在餐飲信息管理領(lǐng)域,有“餐行健”“品智”“軒亞”等多個(gè)餐飲信息管理系統(tǒng),屬于同一應(yīng)用系統(tǒng)的這些數(shù)據(jù)源,由于采用相同的數(shù)據(jù)定義,所以表達(dá)相同概念的元素,無論是元素的標(biāo)簽還是元素的組成結(jié)構(gòu),都完全相同.而術(shù)語不同應(yīng)用系統(tǒng)的數(shù)據(jù)源,其所使用的數(shù)據(jù)定義可能差別很大,如圖5所示,左側(cè)是餐行健餐飲信息管理系統(tǒng),關(guān)于“用餐區(qū)域”這一概念,其使用“section(英文)/桌臺(tái)區(qū)(中文注釋)”這樣的術(shù)語;而右側(cè)的品智餐飲信息管理系統(tǒng),同樣的概念,使用“business_loc(英文)/營業(yè)區(qū)(中文注釋)”這樣的術(shù)語.在預(yù)先不知道它們描述的均是“用餐區(qū)域”這一概念的條件下,機(jī)器甚至人都無法僅憑字符串判斷出“section”和“business_loc”“桌臺(tái)區(qū)”和“營業(yè)區(qū)”表達(dá)的含義相同這一結(jié)論.這種不同應(yīng)用系統(tǒng)下使用術(shù)語上的差異,本文稱其為術(shù)語的本地化特征.

Fig.4 Instance feature under different application scenarios圖4 不同應(yīng)用場景下的實(shí)例特征

Fig.5 Concept definition under different application systems圖5 不同應(yīng)用系統(tǒng)下概念定義

實(shí)例和術(shù)語的本地化特征,其根源來自于不同數(shù)據(jù)源在應(yīng)用場景和應(yīng)用系統(tǒng)上的劃分不同,而這種本地化特征會(huì)導(dǎo)致通用的模式匹配算法——基于實(shí)例統(tǒng)計(jì)特征的模式匹配算法和基于字符串的模式匹配算法出現(xiàn)匹配不準(zhǔn)的情況.如何在領(lǐng)域知識(shí)本體模型無法預(yù)先明晰這種本地化特征的情況下,兼容關(guān)系型數(shù)據(jù)源所存在的本地化特征,提高模式匹配的準(zhǔn)確度,是本文所需要解決的主要問題.

3 迭代優(yōu)化的模式匹配算法

3.1 方案概述

本文針對(duì)現(xiàn)有的關(guān)系模型到本體模型的模式匹配框架在處理數(shù)據(jù)源的本地化特征時(shí)存在的不足,提出了一種迭代優(yōu)化的模式匹配方法IOSMA,如圖6所示.

Fig.6 Iterative optimization schema matching algorithm圖6 迭代優(yōu)化的模式匹配算法

算法對(duì)于異構(gòu)的元素對(duì)的基本匹配流程和現(xiàn)有的模式匹配框架相似,包含了相似度計(jì)算、相似度綜合和相似度判定這 3個(gè)階段:在相似度計(jì)算階段,本文采用了包含基于模式的相似度計(jì)算和基于實(shí)例的相似度計(jì)算,可以計(jì)算得到表與本體中類的相似度以及列與本體中的屬性的相似度;在相似度綜合階段,也分為表相似度綜合和列相似度綜合,即對(duì)前一步得到的多種相似度進(jìn)行加權(quán)平均,可以得到每個(gè)元素對(duì)之間的綜合相似度;在相似度判定階段,對(duì)與一個(gè)待匹配的數(shù)據(jù)庫模式信息,會(huì)利用其和本體中所有待匹配的類或?qū)傩灾g的相似度計(jì)算信息熵,利用熵來衡量匹配的不確定性,這里,人工可以設(shè)置閾值,當(dāng)不確定性小于閾值,即認(rèn)為匹配成功,選擇相似度最高的一組匹配作為匹配結(jié)果.當(dāng)一輪匹配結(jié)束后,算法會(huì)得到匹配的元素對(duì)和不匹配的元素對(duì).

與現(xiàn)有模式匹配框架不同的是,本文在相似度判定環(huán)節(jié)后引入了算法優(yōu)化,并將算法流程改為迭代式的.本文方案的主要思想是:利用模式匹配過程中已經(jīng)判定匹配的元素對(duì),對(duì)原有的模式匹配算法進(jìn)行優(yōu)化,從而達(dá)到提高單一模式匹配算法準(zhǔn)確率,進(jìn)而提升整體的匹配準(zhǔn)確率.原有的低于相似度閾值而無法得到匹配的元素對(duì),重新進(jìn)入匹配流程.由于模式匹配算法的改進(jìn),可以正確地得到匹配,因而得到了更多的匹配元素對(duì)用于算法優(yōu)化,形成一個(gè)良性循環(huán).而已經(jīng)判定匹配的元素對(duì)能夠?qū)υ械哪Ｊ狡ヅ渌惴ㄟM(jìn)行優(yōu)化的原因在于:該元素對(duì)蘊(yùn)含了本體概念和數(shù)據(jù)源元素的等價(jià)關(guān)系,數(shù)據(jù)源元素具有的本地化特征可以用本體進(jìn)行標(biāo)注與衡量,之后遇到具備相似本地化特征的元素時(shí),能夠更好地加以判斷.

具體地,為了兼容數(shù)據(jù)源術(shù)語的本地化特征和在實(shí)例的本地化特征,本文利用已匹配的元素對(duì),對(duì)基于字符串的模式匹配算法以及基于實(shí)例的模式匹配算法進(jìn)行一定的優(yōu)化.

3.2 優(yōu)化:基于字符串的模式匹配算法

已經(jīng)形成匹配的元素對(duì),其語義是相同的,故而其元素標(biāo)簽是同義的,而同一種應(yīng)用系統(tǒng)中,為了避免混亂,對(duì)于同一個(gè)概念,往往傾向于使用相同的標(biāo)簽進(jìn)行表述.因而一旦能夠獲得一組同義詞,就意味著所有包含該同義詞所含字符串的元素對(duì)的相似度可以進(jìn)一步優(yōu)化.如圖5所示,關(guān)于用餐區(qū)域的表述,如果在綜合了多種模式匹配算法之后,能夠得出兩個(gè)系統(tǒng)中以section為標(biāo)簽的節(jié)點(diǎn)和以bussiness_loc為標(biāo)簽的節(jié)點(diǎn)表達(dá)相同含義的話,則可以將“section”和“bussiness_loc”作為一組同義詞,添加到同義詞詞典中.之后,在進(jìn)行“section_id”和“bussiness_loc_id”的匹配時(shí),基于字符串的模式匹配算法能夠給出更為準(zhǔn)確的結(jié)果.

傳統(tǒng)的針對(duì)英文字符串的模式匹配算法有編輯距離法、詞向量距離法等方法.本文在傳統(tǒng)的編輯距離法上結(jié)合了同義詞詞典,首先利用詞典對(duì)字符串進(jìn)行同義替換,然后消除標(biāo)簽對(duì)的同義部分,最后計(jì)算剩余部分的編輯距離,得出字符串的相似度.

編輯距離指的是兩個(gè)字符串之間由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯次數(shù),編輯操作包括增加、刪除、替換.與傳統(tǒng)的編輯距離計(jì)算不同的是,對(duì)于替換操作,除了原本的字符替代以外,本文系統(tǒng)還允許代價(jià)為0的同義詞替換.顯然,兩個(gè)字符串的編輯距離最大值即為二者長度的最大值.根據(jù)編輯距離,可以計(jì)算出兩個(gè)字符串的相似度.例如,對(duì)于字符串“bill_tabls”和“order_table_cnt”,已知 bill和 order是同義詞,將 bill替換為 order,并且添加4個(gè)字符_cnt,所以編輯距離為4,而最大編輯距離為較長字符串的長度,即 order_table_cnt的長度 15,那么字符串的相似度為1-5/15=0.66.

算法1.考慮同義詞的英文字符串匹配算法.

對(duì)于中文字符串的匹配,不能使用類似英文字符串中求編輯距離的辦法,因?yàn)楸磉_(dá)同樣信息的中文字符串長度遠(yuǎn)小于英文,稍有偏差就會(huì)差距很大.本文使用 Word2Vec訓(xùn)練出領(lǐng)域相關(guān)的詞向量模型,詞向量的夾角即為兩個(gè)詞的相似度,夾角的大小通常使用余弦函數(shù)來衡量.

兩個(gè)單詞Wi和Wj,其對(duì)應(yīng)的詞向量分別為Vi=〈vi1,vi2,…,vin〉和Vj=〈vj1,vj2,…,vjn〉,則單詞Wi和Wj的相似度為

為了衡量任意兩個(gè)中文字符串的相似度,首先要將兩個(gè)字符串切分成一個(gè)個(gè)單詞,通過計(jì)算單詞間的相似度,得到整體字符串的相似度.分詞工具切分出的兩個(gè)單詞集合分別為TokenList1和TokenList2,對(duì)于TokenList1中的每個(gè)單詞,在TokenList2中找相似度最大的那個(gè)單詞,將該相似度進(jìn)行累計(jì),最終除以TokenList1集合的大小,即得到字符串相似度大小.

算法2.考慮同義詞的中文字符串匹配算法.

3.3 優(yōu)化:基于實(shí)例的模式匹配算法

傳統(tǒng)的基于實(shí)例的模式匹配算法常常假設(shè)兩個(gè)具有相同語義的元素,在實(shí)例的統(tǒng)計(jì)特征上具有較高的相似性,例如平均值、方差、中位數(shù)等數(shù)學(xué)統(tǒng)計(jì)量,對(duì)于兩個(gè)待匹配的元素,計(jì)算各個(gè)數(shù)學(xué)統(tǒng)計(jì)量的值,為每個(gè)元素生成統(tǒng)計(jì)特征向量,然后比較統(tǒng)計(jì)特征向量之間的距離,作為衡量相似度的標(biāo)準(zhǔn).

本文主要關(guān)注了最大值、最小值、中位數(shù)、平均數(shù)、區(qū)間范圍、DC(distinct count:不同值數(shù)量)、變異系數(shù)、DC占比、非空值占比,這些信息可以作為區(qū)分不同列的統(tǒng)計(jì)特征.

以M種不同類型的統(tǒng)計(jì)量作為不同的特征維度,為數(shù)據(jù)庫中的每個(gè)表列,生成M維的向量,記為實(shí)例統(tǒng)計(jì)向量,由于本體中的每一個(gè)屬性都會(huì)映射到至少 1個(gè)數(shù)據(jù)庫中的表列,因此其實(shí)例統(tǒng)計(jì)向量的計(jì)算方法與數(shù)據(jù)庫表列相同.

在計(jì)算得到實(shí)例統(tǒng)計(jì)向量之后,一種直觀的相似度計(jì)算方法是使用向量間的歐氏距離衡量元素對(duì)實(shí)例層次上的相似度,對(duì)于兩個(gè)向量Vi=〈vi1,vi2,…,vin〉和Vj=〈vj1,vj2,…,vjn〉,歐氏距離為

n維向量的歐氏距離最大值為,使用線性映射法將歐氏距離映射到[0,1]區(qū)間上作為相似度.因此對(duì)于兩個(gè)數(shù)據(jù)庫列Ai和Aj,其對(duì)應(yīng)的向量分別為Vi和Vj,得到它們的相似度:

根據(jù)第 2節(jié)的分析,實(shí)際的數(shù)據(jù)源可能存在實(shí)例本地化特征,即其數(shù)學(xué)統(tǒng)計(jì)量可能明顯偏離于其他數(shù)據(jù)源或者本體實(shí)例相對(duì)應(yīng)元素的統(tǒng)計(jì)量,這時(shí),應(yīng)用上述方法得到的相似度是不準(zhǔn)確的.

本文利用已經(jīng)形成匹配的元素對(duì),加上由匹配排他性所推導(dǎo)出的不匹配元素對(duì)作為訓(xùn)練數(shù)據(jù),生成一個(gè)分類模型,分類模型的輸入是兩個(gè)元素的統(tǒng)計(jì)特征向量,輸出是這兩個(gè)元素是否形成匹配的概率.分類模型隨著已匹配元素的增多,訓(xùn)練集也不斷增加,分類效果也不斷增強(qiáng),對(duì)實(shí)例本地化特征的兼容性也越來越好,其基本思想如圖7所示.

Fig.7 Classifier-based instance schema matching algorithm圖7 基于分類器的實(shí)例模式匹配算法

但模式匹配的前期沒有足夠的訓(xùn)練集可用,因此前期主要依賴歐氏距離計(jì)算實(shí)例相似度,大致能夠區(qū)分不同列即可;在匹配的過程中,元素對(duì)不斷得到匹配,也給分類器提供了訓(xùn)練數(shù)據(jù).匹配的后期由于擁有大量的訓(xùn)練數(shù)據(jù),分類模型的準(zhǔn)確度也得到了提升,因此得到的相似度也更為可信.因此,我們?cè)O(shè)置了參數(shù)δ來調(diào)整兩種算法得到的相似度的比例.假設(shè)當(dāng)前有δ比例的列得到了匹配,EuclideanSim表示歐拉距離給出的相似度,MLSim表示分類器給出的相似度,則最終的實(shí)例相似度為

以餐飲信息管理為例,假設(shè)當(dāng)前本體中的實(shí)例數(shù)據(jù)來自于某些特色小吃餐飲品牌,而待匹配數(shù)據(jù)源的數(shù)據(jù)來源于主營宴會(huì)的餐飲品牌,起初,基于實(shí)例的模式匹配算法并不能反映出這種差異,但隨著匹配元素對(duì)越來越多,分類模型獲取足夠多的訓(xùn)練數(shù)據(jù)之后,就能夠?qū)蓚€(gè)數(shù)據(jù)模式之間存在的差異進(jìn)行學(xué)習(xí),之后,在利用實(shí)例統(tǒng)計(jì)特征進(jìn)行相似度判定時(shí),就會(huì)變得更加準(zhǔn)確.

4 實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)設(shè)定

本節(jié)對(duì)本文迭代優(yōu)化的模式匹配算法進(jìn)行實(shí)驗(yàn)驗(yàn)證,本體選用的是基于餐行健餐飲信息管理系統(tǒng)構(gòu)造出的本體模型,待匹配數(shù)據(jù)源為品智餐飲信息管理系統(tǒng),本體模型和關(guān)系模型中所含元素?cái)?shù)量的統(tǒng)計(jì)見表2.

模式匹配的主要目標(biāo)是尋找本體中的類和關(guān)系模式中表的映射關(guān)系、本體中的數(shù)據(jù)屬性和關(guān)系模式中列的映射關(guān)系.本文的評(píng)估標(biāo)準(zhǔn)采用精確率(precision)、召回率(recall)、F值(F-measure),其中,F值為精確率與召回率的調(diào)和平均值,統(tǒng)一度量精確率與召回率.記TP為判斷正確的匹配,FP為判斷錯(cuò)誤的匹配,FN為沒有判斷出來的正確匹配.3個(gè)評(píng)估標(biāo)準(zhǔn)的計(jì)算方法如下:

Table 2 Statistics of schema elements表2 待匹配模式元素統(tǒng)計(jì)

實(shí)驗(yàn)分為 3組:第 1組是現(xiàn)有的模式匹配框架 COMA++,第 2組是未進(jìn)行迭代的本文算法 NSMA(noniterative schema matching algorithm),第3組是本文的迭代優(yōu)化的模式匹配算法IOSMA.在模式匹配的過程中,完全依靠機(jī)器自動(dòng)完成,無任何專家參與.

4.2 匹配結(jié)果

實(shí)驗(yàn)結(jié)果如圖8所示.由于沒有利用已匹配元素對(duì)來對(duì)模式匹配算法進(jìn)行優(yōu)化,COMA++無法很好地兼容數(shù)據(jù)源的本地化特征.COMA++使用的不帶優(yōu)化的字符串匹配算法,沒有根據(jù)已形成匹配的元素對(duì)對(duì)其自身進(jìn)行改進(jìn),從而導(dǎo)致很多原本可以借助同義詞轉(zhuǎn)化提高相似度的元素對(duì),達(dá)不到匹配閾值,從而得不到匹配.COMA++使用的基于實(shí)例的匹配算法單一地考慮統(tǒng)計(jì)量上的近似程度,而沒有利用已經(jīng)匹配的元素對(duì)所提供的知識(shí),訓(xùn)練分類模型,無法很好地應(yīng)對(duì)相同語義的元素對(duì),其實(shí)例特征有較大差異的情況.相反地,IOSMA 較好地考慮了數(shù)據(jù)源的本地化特征,并對(duì)匹配算法進(jìn)行迭代式的改進(jìn),ISOMA利用已匹配的元素對(duì)在迭代過程中可以不斷提高匹配效果,在實(shí)驗(yàn)數(shù)據(jù)集上達(dá)到了 91%的精確率、83%的召回率和 87%的F值.相對(duì)于 COMA++,分別取得了 39.8%、59.6%、50.1%的提升;相對(duì)于非迭代版本的算法,分別取得了 24.7%、33.9%、29.9%的提升.

Fig.8 Result of schema matching experiments圖8 模式匹配實(shí)驗(yàn)結(jié)果

4.3 案例分析

為了更好地展示本文的匹配效果,表3展示了利用ISOMA得到的已匹配的數(shù)據(jù)庫表名和本體類名.在這些已匹配的元素對(duì)中,某些字段具有顯著的本地化特征,在迭代過程中,這些元素對(duì)也得到了匹配.本節(jié)通過兩個(gè)方面分別舉例說明ISOMA在迭代過程中兼容數(shù)據(jù)源本地化特征的做法.

Table 3 Schema maching instance表3 模式匹配示例

4.3.1 處理模式結(jié)構(gòu)的本地化特征

在第1輪匹配過程中,商戶賬單表得到匹配,算法可以提取出order和bill的同義詞關(guān)系,形成該數(shù)據(jù)源的同義詞典.同義詞典可以有效地改善基于字符串的模式匹配算.例如數(shù)據(jù)庫中的訂單金額的名稱是 bill_total,本體中的訂單金額為order_total_amount,在確定bill和order為同義詞后,訂單金額的相似度會(huì)得到明顯的提升.從而使訂單金額字段得到匹配.

4.3.2 處理實(shí)例信息的本地化特征

數(shù)據(jù)庫和本體中相同含義數(shù)據(jù)的統(tǒng)計(jì)特征也存在一定的差異,在實(shí)驗(yàn)中,基于餐行健系統(tǒng)生成的本體模型中多為高端餐飲企業(yè),而品智餐飲系統(tǒng)中則是中小餐館居多,因此兩個(gè)系統(tǒng)中表述相同含義的元素的統(tǒng)計(jì)特征(最大值、平均值、標(biāo)準(zhǔn)差等)存在較大差異(見表4).在匹配過程中,商戶賬單支付表在兩個(gè)系統(tǒng)中模式結(jié)構(gòu)相似度較高,得到了匹配,利用這個(gè)信息可以得到很多匹配的元素對(duì),利用已匹配的元素對(duì)的統(tǒng)計(jì)特征生成樣本并訓(xùn)練分類器.隨著分類器的訓(xùn)練樣本增加,分類器更容易識(shí)別出數(shù)據(jù)庫和本體中的統(tǒng)計(jì)特征差異,可以把具有類似差異的相同概念進(jìn)行匹配.在本例中,商戶賬單明細(xì)表數(shù)據(jù)庫和本體的匹配通過這種方式得到了提升.也體現(xiàn)ISOMA基于迭代更好地兼容了數(shù)據(jù)源的本地化特征.

Table 4 Difference of statistical features表4 統(tǒng)計(jì)特征差異

5 結(jié) 論

本文研究一類關(guān)系模型到本體模型的模式匹配問題,在充分調(diào)研了現(xiàn)有模式匹配相關(guān)研究工作的前提下,對(duì)實(shí)際數(shù)據(jù)源具有的本地化特征進(jìn)行了深入分析和論證,并指出本地化特征是導(dǎo)致現(xiàn)有模式匹配框架中單一模式匹配算法匹配失效的深層次原因;然后提出一種迭代優(yōu)化的模式匹配算法,該算法利用已經(jīng)得到匹配的元素對(duì),對(duì)傳統(tǒng)的基于字符串的模式匹配算法和基于實(shí)例的模式匹配算法進(jìn)行優(yōu)化,使之更好地兼容數(shù)據(jù)源的本地化特征,從而提高了模式匹配的準(zhǔn)確率;最后,以餐飲信息管理領(lǐng)域的一個(gè)實(shí)際案例開展相關(guān)實(shí)驗(yàn),證明本文算法的有效性和準(zhǔn)確性.

本文未來有以下研究方向.首先,探究如何更加科學(xué)地綜合不同匹配算法的結(jié)果.目前主流的方式都是由用戶來制定相似度的綜合方式,然而在很多情況下,用戶也很難給出一個(gè)準(zhǔn)確的綜合相似度計(jì)算公式.為此,需要分析不同模式匹配算法的特性,例如基于實(shí)例的模式匹配算法的可信度是否高于基于字符串的模式匹配算法的可信度,根據(jù)匹配算法的可信度為其賦予相應(yīng)的權(quán)重是一種簡單的解決方法.而根據(jù)已經(jīng)得到匹配的元素對(duì)來進(jìn)行學(xué)習(xí),利用表示學(xué)習(xí)的方式挖掘匹配元素對(duì)的深層次特征,可以得到更好的匹配結(jié)果.其次,對(duì)于匹配錯(cuò)誤的元素對(duì)的糾錯(cuò)機(jī)制也是一個(gè)值得探討的方向,首先需要進(jìn)一步提高模型的準(zhǔn)確率,其次可以加入群智,利用人機(jī)協(xié)作來對(duì)機(jī)器出現(xiàn)的錯(cuò)誤進(jìn)行糾正.