數(shù)據(jù)庫(kù)模式的主動(dòng)在線匹配方法

莊 莉，陳又詠，黃雙雙，丁 陽(yáng)，張 照

（1.福建億榕信息技術(shù)有限公司，福建 福州 350003；2.西安交通大學(xué) 電子與信息學(xué)部，陜西 西安 710049；3.北京國(guó)網(wǎng)信通埃森哲信息技術(shù)有限公司，北京 102211；4.北京中電普華信息技術(shù)有限公司，北京 102211）

0 引 言

長(zhǎng)期以來(lái)，我國(guó)數(shù)據(jù)庫(kù)管理系統(tǒng)的市場(chǎng)主要被國(guó)外數(shù)據(jù)庫(kù)廠商占據(jù)。這種狀況既不利于我國(guó)信息產(chǎn)業(yè)的安全，更威脅我國(guó)基礎(chǔ)信息設(shè)施的可控權(quán)。為實(shí)現(xiàn)關(guān)鍵信息技術(shù)自主可控，研發(fā)并推廣應(yīng)用國(guó)產(chǎn)數(shù)據(jù)庫(kù)管理系統(tǒng)，已成為我國(guó)信創(chuàng)產(chǎn)業(yè)發(fā)展的戰(zhàn)略性任務(wù)之一。

為緊跟國(guó)家戰(zhàn)略、推動(dòng)信創(chuàng)生態(tài)體系建設(shè)，當(dāng)前國(guó)產(chǎn)數(shù)據(jù)庫(kù)迎來(lái)蓬勃發(fā)展時(shí)期，一大批優(yōu)秀的國(guó)產(chǎn)數(shù)據(jù)庫(kù)產(chǎn)品迅猛發(fā)展。雖然我國(guó)各機(jī)構(gòu)在信息化辦公過(guò)程中逐步采用國(guó)產(chǎn)數(shù)據(jù)庫(kù)進(jìn)行信息管理，但由于信息系統(tǒng)規(guī)模大、業(yè)務(wù)復(fù)雜性高，數(shù)據(jù)呈現(xiàn)出分布、海量、異構(gòu)等特點(diǎn)，且大量歷史數(shù)據(jù)通常同時(shí)使用國(guó)外數(shù)據(jù)庫(kù)平臺(tái)存儲(chǔ)。在這種條件下，為了實(shí)現(xiàn)數(shù)據(jù)從國(guó)外數(shù)據(jù)庫(kù)到國(guó)產(chǎn)數(shù)據(jù)庫(kù)的轉(zhuǎn)移，有數(shù)據(jù)轉(zhuǎn)移需求的數(shù)據(jù)庫(kù)使用者需要完成數(shù)據(jù)跨庫(kù)遷移工作。因此，當(dāng)前的重要任務(wù)是實(shí)現(xiàn)數(shù)據(jù)從國(guó)外數(shù)據(jù)庫(kù)到國(guó)產(chǎn)數(shù)據(jù)庫(kù)的遷移。

模式匹配是實(shí)現(xiàn)數(shù)據(jù)遷移任務(wù)的一項(xiàng)關(guān)鍵技術(shù)。圖1是一個(gè)模式匹配的示例，若要將源數(shù)據(jù)庫(kù)中的數(shù)據(jù)轉(zhuǎn)移到目標(biāo)數(shù)據(jù)庫(kù)中，需要對(duì)數(shù)據(jù)庫(kù)的子模式和字段分別建立匹配關(guān)系。圖1中源模式的項(xiàng)目信息子模式和目標(biāo)模式的交易信息模式建立匹配關(guān)系，源模式的單位信息子模式需要與目標(biāo)模式的單位信息子模式建立映射關(guān)系，建立映射的子模式的各個(gè)字段也需要建立映射關(guān)系。要將源數(shù)據(jù)庫(kù)中的數(shù)據(jù)轉(zhuǎn)換到目標(biāo)數(shù)據(jù)庫(kù)中，需要建立源數(shù)據(jù)庫(kù)子模式到目標(biāo)數(shù)據(jù)庫(kù)子模式的聯(lián)系，以及源數(shù)據(jù)庫(kù)模式字段和目標(biāo)數(shù)據(jù)庫(kù)模式字段之間的聯(lián)系。

圖1 模式匹配示例

現(xiàn)有研究一般使用批量學(xué)習(xí)實(shí)現(xiàn)數(shù)據(jù)庫(kù)的自動(dòng)模式匹配，但在實(shí)際應(yīng)用場(chǎng)景下，模式匹配任務(wù)具有時(shí)間順序性和經(jīng)驗(yàn)積累增量性，批量學(xué)習(xí)進(jìn)行模式匹配缺乏經(jīng)驗(yàn)累積學(xué)習(xí)的能力。本文提出將集成學(xué)習(xí)與增量式貝葉斯思想用于模式匹配，利用在模式匹配過(guò)程中已得到的匹配模式對(duì)優(yōu)化模式的匹配算法，通過(guò)擴(kuò)大訓(xùn)練集規(guī)模提高分類準(zhǔn)確率。

1 相關(guān)工作

目前有關(guān)自動(dòng)數(shù)據(jù)庫(kù)模式匹配的研究基于匹配知識(shí)的不同主要分為兩類：數(shù)據(jù)庫(kù)結(jié)構(gòu)層級(jí)的匹配和實(shí)例層級(jí)的匹配。

結(jié)構(gòu)層級(jí)的數(shù)據(jù)庫(kù)模式匹配利用模式字段名稱、字段類型、字段描述等模式級(jí)信息結(jié)構(gòu)相似程度進(jìn)行模式匹配。如文獻(xiàn)[3]利用模式映射的元映射以及模式名稱特征重用現(xiàn)有的模式映射，將元映射存儲(chǔ)在可搜索的存儲(chǔ)庫(kù)中，并建立索引以進(jìn)行快速檢索。文獻(xiàn)[4]使用圖匹配的思想提出一種簡(jiǎn)單的結(jié)構(gòu)算法用于模式匹配。

實(shí)例層級(jí)的模式匹配通過(guò)判別數(shù)據(jù)的分布、統(tǒng)計(jì)特性、數(shù)據(jù)相關(guān)性等數(shù)據(jù)庫(kù)實(shí)例級(jí)信息的相似程度進(jìn)行模式匹配。文獻(xiàn)[5]提出的統(tǒng)計(jì)數(shù)據(jù)模式中屬性列的概率分布，依據(jù)概率分布評(píng)估屬性列之間的相似性。文獻(xiàn)[6]提出了基于互信息的非透明列值數(shù)據(jù)模式匹配方法，能夠在不透明的列名和數(shù)據(jù)值的情況下實(shí)現(xiàn)數(shù)據(jù)庫(kù)的模式匹配。

本文針對(duì)現(xiàn)有模式匹配方法存在的主要問(wèn)題，通過(guò)對(duì)現(xiàn)存模式匹配信息的學(xué)習(xí)，能夠減少人工標(biāo)定樣本的工作量，在后續(xù)的增量模式匹配中提供完備的匹配信息。本文提出將集成學(xué)習(xí)與增量式貝葉斯思想用于模式匹配，利用在模式匹配過(guò)程中已經(jīng)得到的模式匹配關(guān)聯(lián)關(guān)系對(duì)模式匹配算法進(jìn)行優(yōu)化。

2 動(dòng)態(tài)模式匹配方法

2.1 方法概述

本文提出的動(dòng)態(tài)數(shù)據(jù)庫(kù)模式匹配算法如圖2所示（其中，為當(dāng)前子模式分類后驗(yàn)概率，為主動(dòng)選擇的置信度閾值），分為初始模型訓(xùn)練、模式分類、分類結(jié)果主動(dòng)選擇、增量學(xué)習(xí)四個(gè)部分。初始模型訓(xùn)練利用已有少量模式訓(xùn)練集訓(xùn)練一個(gè)初始模式匹配分類模型，用于后期增量學(xué)習(xí)過(guò)程中的模式分類；模式分類使用初始模式匹配分類器對(duì)增量集中沒(méi)有模式標(biāo)簽的未知模式分類；分類結(jié)果主動(dòng)選擇部分對(duì)增量集中的子模式樣本進(jìn)行篩選，選擇最有利于提高分類器性能的實(shí)例加入訓(xùn)練集；增量學(xué)習(xí)將滿足主動(dòng)選擇篩選條件的實(shí)例以及主動(dòng)在線模式匹配算法賦予該實(shí)例的模式標(biāo)簽加入反饋集中，使用增量學(xué)習(xí)的思想再次訓(xùn)練分類模型。

圖2 動(dòng)態(tài)數(shù)據(jù)庫(kù)模式匹配算法

本節(jié)提出利用樸素貝葉斯和隨機(jī)森林模型實(shí)現(xiàn)對(duì)模式進(jìn)行增量分類的算法，并詳細(xì)地介紹了子模式特征表示方法和主動(dòng)在線模式匹配算法設(shè)計(jì)。

2.2 子模式特征表示方法

樸素貝葉斯分類方法一般使用多維特征向量表示數(shù)據(jù)樣本。數(shù)據(jù)庫(kù)子模式信息包括名稱、類型、屬性描述等內(nèi)容，這些描述信息不易組織成維向量。因此，在提取子模式特征時(shí)將參考文獻(xiàn)[8]提出的模式特征表示方法，將多種描述信息組合成短文本，并對(duì)其進(jìn)行修改以適用于本文中的模式匹配場(chǎng)景。將子模式用文本表示后可使用TF?IDF生成子模式的特征向量，在本文中，子模式的單個(gè)信息出現(xiàn)頻率SF可以表示為：

式中：SF 表示子模式的信息在子模式S 中的信息頻率；N 表示子模式的信息在子模式S 中的出現(xiàn)次數(shù)；分母表示子模式S 所有信息總數(shù)。子模式單個(gè)信息的逆向模式頻率ISF 表示為：

式中：||表示子模式的總數(shù)；|{:N ∈S }|表示含有信息的子模式個(gè)數(shù)。由于本文將子模式各個(gè)字段的信息組織成文本，故可以采用此方法提取每個(gè)子模式的特征，經(jīng)TF?IDF處理后可以得到一個(gè)能夠表示子模式特征的稀疏矩陣，作為主動(dòng)在線模式匹配算法的輸入。

2.3 主動(dòng)在線模式匹配算法設(shè)計(jì)

本文選用樸素貝葉斯模型和隨機(jī)森林模型實(shí)現(xiàn)子模式的增量匹配。數(shù)據(jù)庫(kù)模式的貝葉斯分類是根據(jù)訓(xùn)練數(shù)據(jù)庫(kù)子模式的類先驗(yàn)概率和類條件概率，預(yù)測(cè)子模式是否屬于某一數(shù)據(jù)庫(kù)模式類別。在當(dāng)前模式匹配場(chǎng)景下，僅使用初始少量標(biāo)定子模式訓(xùn)練集顯然是片面且不合理的，需要使模式匹配的模式訓(xùn)練集隨著模型訓(xùn)練逐漸更完備，從而優(yōu)化數(shù)據(jù)庫(kù)模式匹配分類器。在數(shù)據(jù)庫(kù)模式匹配過(guò)程中使用增量學(xué)習(xí)可以解決此矛盾。挑選測(cè)試過(guò)程中的模式匹配實(shí)例，重新作為模式匹配的訓(xùn)練集，順應(yīng)數(shù)據(jù)增長(zhǎng)變化趨勢(shì)，從而優(yōu)化匹配效果。

本文模式匹配增量方法假設(shè)為隨機(jī)變量，是先驗(yàn)信息。如果有新增模式匹配樣本加入，計(jì)算(|,)的公式如下：

由上式可見(jiàn)，隨著樣本的加入，先驗(yàn)信息由(|)變?yōu)?|,)，先驗(yàn)信息是貝葉斯增量學(xué)習(xí)模型的基礎(chǔ)。在增量模式匹配過(guò)程中，當(dāng)新的子模式到來(lái)，之前的子模式匹配信息可以作為模型訓(xùn)練的新樣本，這種迭代訓(xùn)練方法利用測(cè)試子模式實(shí)例信息，是一個(gè)逐漸改進(jìn)先前模式匹配模型的增量過(guò)程。

子模式增量學(xué)習(xí)模型構(gòu)建的偽代碼如算法1所示。假定子模式類別為={,，…，C }，子模式特征向量為F ={, ，…， }，是特征數(shù)量，子模式類別的先驗(yàn)概率(C ）抽象為參數(shù)θ，特征的類條件概率(q | C )抽象為參數(shù)θ 。參數(shù)θ和θ 的值為：

式中：| |表示訓(xùn)練集中類別C 的訓(xùn)練子模式數(shù)量；||表示子模式類別總數(shù)；||為子模式總數(shù)；| ,C |表示子模式類別C 的特征q 的頻率；||表示子模式中特征q 出現(xiàn)的頻率。

根據(jù)θ和θ 可以得到子模式樸素貝葉斯分類器的初始分類模型NBM：

子模式增量修正模型是對(duì)子模式增量集中的實(shí)例選擇，根據(jù)新增子模式調(diào)整模型參數(shù)的動(dòng)態(tài)過(guò)程，θ和θ 增量調(diào)整為：

具體算法流程如算法1所示。

算法1：主動(dòng)在線模式匹配算法

輸入：模式匹配初始訓(xùn)練集，模式匹配增量集，模式匹配反饋集，模式匹配置信度閾值

輸出：模式匹配分類模型

1：function OBSMMODEL（，，，）

2：←length（）

3：NBM←InitialBayesTrain（）

4：RFM←InitialRFTrain（）

5：while<=do

6： if RFM（[]）==NBM（[]）then

7： if P_voting（RFM（[]））>then

8：←+[]

9： end if

10： end if

11：end while

12：NBM←IncreBayesTrain（NBM，）

13：return NBM

14：end function

基于增量學(xué)習(xí)進(jìn)行子模式匹配算法，其要點(diǎn)是從大量子模式樣本中選擇最適合模式匹配模型的模式實(shí)例，加入模式匹配訓(xùn)練集，從而達(dá)到優(yōu)化子模式分類器分類性能的目的。通常有兩種實(shí)例選擇方法：被動(dòng)選擇方法和主動(dòng)選擇方法。

數(shù)據(jù)庫(kù)模式匹配模型增量訓(xùn)練過(guò)程中，被動(dòng)選擇策略對(duì)測(cè)試子模式實(shí)例的選擇具有隨機(jī)性，該策略下，模式匹配模型會(huì)被動(dòng)地接收新信息。但是在模式匹配過(guò)程中使用被動(dòng)選擇策略不適用于本文的模式匹配場(chǎng)景，在動(dòng)態(tài)修正模式匹配的過(guò)程中，被動(dòng)選擇策略就表現(xiàn)出明顯的不足，因?yàn)榘凑漳骋环N單一沒(méi)有依據(jù)的篩選規(guī)則會(huì)使學(xué)習(xí)的分類器具有順序相關(guān)性，使得模式匹配模型對(duì)數(shù)據(jù)較為敏感。此外，如模式匹配過(guò)程中遇到噪音數(shù)據(jù)，這種噪音持續(xù)下去會(huì)嚴(yán)重影響模式匹配結(jié)果。

相較而言，在本文的場(chǎng)景下采用主動(dòng)選擇策略對(duì)子模式實(shí)例的選擇具有可控性，該策略會(huì)選擇最有利于子模式分類器性能提高的測(cè)試子模式實(shí)例，更智能也更適用于本文中的模式匹配場(chǎng)景。

本文主動(dòng)選擇使用集成學(xué)習(xí)的思想主動(dòng)選擇樣本。具體地，本文使用隨機(jī)森林算法對(duì)增量集中的樣本進(jìn)行分類，能夠得到當(dāng)前隨機(jī)森林中每一棵決策樹(shù)的分類結(jié)果，多個(gè)學(xué)習(xí)器的集成結(jié)果和投票分類結(jié)果更具有說(shuō)服力，能夠和樸素貝葉斯的分類結(jié)果相互驗(yàn)證。

其中，子模式增量集中的單個(gè)子模式樣本的主動(dòng)選擇過(guò)程如圖3所示，本文將子模式增量集中的樣本實(shí)例輸入具有多棵決策樹(shù)的隨機(jī)森林中，每一棵決策樹(shù)的分類結(jié)果用T ()(1≤≤)表示，經(jīng)過(guò)決策樹(shù)投票，可以得出每種子模式類別C (1≤≤)的投票計(jì)數(shù)為(C )，則每個(gè)類別C 的投票占比可以表示為：

圖3 主動(dòng)在線模式匹配算法主動(dòng)選擇策略

計(jì)算每個(gè)類別的投票占比后選擇投票占比最高的類別滿足以下條件：

作為多棵決策樹(shù)的子模式分類類別，把投票占比()作為該類別的置信度，如果與初始貝葉斯模式分類模型的分類結(jié)果Bayes（）的結(jié)果一致且置信度滿足閾值要求，即：

將子模式樣本實(shí)例以及對(duì)應(yīng)分類標(biāo)簽(,)加入子模式增量集中，完成單個(gè)樣本的主動(dòng)選擇。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)和方法

本文實(shí)驗(yàn)需使用中文異構(gòu)數(shù)據(jù)庫(kù)的遷移數(shù)據(jù)測(cè)試本文中的增量貝葉斯模式匹配模型，但由于目前沒(méi)有適用于本文的公開(kāi)中文異構(gòu)數(shù)據(jù)庫(kù)遷移數(shù)據(jù)集，本文選用公開(kāi)中文文本分類sms數(shù)據(jù)集，對(duì)該數(shù)據(jù)集進(jìn)行改造，經(jīng)改造的數(shù)據(jù)集與本文所需的國(guó)產(chǎn)數(shù)據(jù)庫(kù)遷移數(shù)據(jù)邏輯等價(jià)。實(shí)驗(yàn)數(shù)據(jù)信息如表1所示，在實(shí)驗(yàn)過(guò)程中，將數(shù)據(jù)集劃分成模式匹配初始訓(xùn)練集、模式匹配增量集、模式匹配測(cè)試集。

表1 實(shí)驗(yàn)數(shù)據(jù)集

本文中模式匹配的目標(biāo)是尋找源數(shù)據(jù)庫(kù)子模式和目標(biāo)數(shù)據(jù)庫(kù)子模式的匹配關(guān)系，為驗(yàn)證動(dòng)態(tài)模式匹配方案的有效性，分別使用批量學(xué)習(xí)和主動(dòng)在線模式匹配算法使用相同初始訓(xùn)練集訓(xùn)練模型。此外，本文將模式匹配增量集劃分為10等份用于觀察本文所提方法隨模式匹配增量學(xué)習(xí)的表現(xiàn)，使用同一測(cè)試集評(píng)估模式匹配模型的匹配效能。最后，為觀察本文所提方法對(duì)于置信度閾值的敏感性，通過(guò)設(shè)置多種閾值，記錄本文方法在不同置信度閾值時(shí)的模式匹配效能。

3.2 評(píng)估指標(biāo)

為了評(píng)估匹配質(zhì)量，采用以下三個(gè)通用指標(biāo)：

1）準(zhǔn)確率：子模式測(cè)試實(shí)例中正確分類的數(shù)量占測(cè)試子模式實(shí)例總數(shù)的比例。計(jì)算公式為：

2）召回率：被正確分類的子模式正例個(gè)數(shù)占實(shí)際正例個(gè)數(shù)的比例。計(jì)算公式為：

3）全面性：

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

圖4為使用批量模式匹配算法和主動(dòng)在線模式匹配算法在相同數(shù)據(jù)集上的模式匹配對(duì)比。

圖4 批量模式匹配與主動(dòng)在線模式匹配對(duì)比

其中，批量模式匹配算法包括決策樹(shù)模式匹配算法、KNN模式匹配算法、批量貝葉斯模式匹配算法。相較于傳統(tǒng)的批量模式匹配方法，本文提出的動(dòng)態(tài)模式分類匹配方法將模式匹配全面性提高了5%~33%。表2為本實(shí)驗(yàn)中各類子模式的匹配情況。實(shí)驗(yàn)結(jié)果顯示，各類別使用動(dòng)態(tài)模式匹配方法表現(xiàn)明顯優(yōu)于傳統(tǒng)方法。

表2 批量貝葉斯模式匹配與主動(dòng)在線模式匹配算法效果詳細(xì)對(duì)比

此外，為測(cè)試本文所提主動(dòng)在線模式匹配算法在經(jīng)驗(yàn)累積過(guò)程中的模式匹配效能，將子模式增量集劃分為10等份，每次增量訓(xùn)練的數(shù)據(jù)為增量集的1 10，主動(dòng)在線模式匹配算法增量學(xué)習(xí)表現(xiàn)如圖5所示。

圖5 主動(dòng)在線模式匹配算法增量學(xué)習(xí)表現(xiàn)

根據(jù)圖5可知，在模式匹配信息增量的累積過(guò)程中，主動(dòng)在線模式匹配算法增量學(xué)習(xí)表現(xiàn)總體呈上升趨勢(shì)。預(yù)計(jì)隨著模式匹配信息不斷增加，匹配效能將會(huì)不斷上升。

在使用模式匹配主動(dòng)選擇策略時(shí)，模式匹配置信度的閾值設(shè)定是影響模式匹配效果的重要因素。為觀察不同模式匹配置信度閾值對(duì)主動(dòng)在線增量學(xué)習(xí)的影響，本實(shí)驗(yàn)設(shè)定不同的模式匹配置信度閾值，在同一模式匹配測(cè)試集上測(cè)試。

本實(shí)驗(yàn)測(cè)試的主動(dòng)在線模式匹配算法對(duì)置信度閾值的敏感情況如圖6所示，不同的模式匹配置信度概率閾值的設(shè)定對(duì)算法的效果有所影響。

圖6 置信度閾值敏感分析

圖6中主動(dòng)在線模式匹配算法在部分模式匹配置信度閾值的表現(xiàn)呈現(xiàn)平臺(tái)趨勢(shì)，是因?yàn)椴糠衷隽考械臉颖驹谝欢Ｊ狡ヅ溟撝捣秶鷥?nèi)沒(méi)有滿足條件的樣本。在針對(duì)不同的應(yīng)用場(chǎng)景時(shí)，需要根據(jù)增量模型的測(cè)試指標(biāo)反向調(diào)整模式匹配置信度閾值。

4 結(jié) 論

本文介紹了一種主動(dòng)在線的模式匹配方法，能夠有效減少模式匹配算法的搜索空間，并且相比傳統(tǒng)的復(fù)雜模式匹配算法，本文方法能夠充分利用已有模式匹配信息，為后續(xù)模式匹配提供更完備的匹配知識(shí)。在未來(lái)，本研究將準(zhǔn)確定位源模式中子模式和目標(biāo)子模式的匹配關(guān)系，并且把子模式匹配和子模式字段匹配有效結(jié)合，從而實(shí)現(xiàn)一套完整的模式匹配體系。