田燚林，王 勇

(北京工業(yè)大學 信息學部，北京 100124)

0 引言

健康數據呈現出很強的異構性，其由很多結構化數據與文檔數據組成。異構數據模式集成是解決大規(guī)模數據共享問題的一個較好方案，通過數據源集成平臺將結構化數據、文檔數據等整合起來，并提供統一的透明全局數據集成視圖，使其像在單系統中一樣進行實時業(yè)務數據處理與信息交換，從而很好地解決了健康領域數據的“信息孤島”問題，同時完成健康領域數據的統一查詢[1]。

模式集成一直以來都是研究的熱點與難點，傳統研究工作主要集中在模式集成理論與關系模式集成方面。但是隨著越來越多非結構化數據的不斷出現，研究重點則轉移到異構XML數據源的模式集成與沖突解決上。PORSCHE是一種混合模式集成算法[2]，其可以用于集成XML模式樹。它采用模式增長的方式解決多個數據源模式的集成工作，最終產生一個匯聚局部數據源所有概念的全局模式樹。當局部數據源模式較為相似時，PORSCHE可以產生很好的集成效果，但其不能較好地支持結構沖突的解決，在生成的全局模式樹中存在著很多冗余關系。本文的模式集成算法很好地定義與檢測了XML模式集成中的關系嵌套沖突、關系方向沖突及實體屬性沖突，減輕了模式集成后的冗余，具有更好的模式集成質量。

1 模式集成概述

在異構數據源集成系統中，各局部數據源的數據模式是由不同用戶、基于不同應用目的與數據結構原型設計的，它們之間存在著各種差異及沖突。為了實現對集成系統透明的統一訪問，需要研究一種方法屏蔽或解決局部數據源模式的差異及沖突。集成系統是在保證各局部數據源自治性的基礎上，集成各局部數據源，提供統一訪問接口，通常采用的辦法是在異構數據源集成系統中構造一個全局模式[3]。

全局模式的生成是一個模式集成過程。異構數據源的局部模式之間存在著語義差異、結構差異、表達格式差異、定義規(guī)范不一致等問題。模式集成的首要任務即消除各局部模式間的差異，生成全局模式供全局查詢使用，同時建立信息映射機制，并建立模式映射相關文檔，以便統一查詢時的查詢分解[4]。

構造全局模式的關鍵步驟是為異構數據源建立統一的數據模式，通過模式轉換算法將異構數據源模式統一到全局的公共數據模式上[5]。本文采用XML Schema作為全局模式的描述。因此，健康領域異構數據的模式集成工作可以轉化為XML Schema的模式集成方法。

2 XML Schema模式集成問題描述與研究現狀

語義與結構沖突是模式集成領域的兩大挑戰(zhàn)[6]。當不同數據源用不同元素名稱描述相同概念時，或者當不同數據源使用相同元素名稱描述不同概念時，則會發(fā)生語義沖突。如圖1所示，模式樹(a)表示醫(yī)院信息管理系統(HIS)中的病人信息結構，模式樹(b)表示健康檔案管理系統中的病人信息結構。同樣表示病人地址信息，在a模式中使用address名稱表示，在b模式中則使用location名稱表示。

圖1 病人信息兩種模式

當不同數據源使用不同結構表達相同關系時，則會發(fā)生結構沖突。常見的結構沖突有如下3種形式：①圖2(a)表示關系嵌套沖突，是指相似概念間關系被直接表達與間接表達的沖突。當相似概念之間表達相同關系，只是嵌套層次有所差異時，則會發(fā)生這種沖突，體現在XML節(jié)點樹中即是路徑長度差異；②圖2(b)表示關系方向沖突，是指相似概念之間關系在XML節(jié)點樹中的方向相反，但它們代表同一種關系；③圖2(c)表示實體屬性沖突[7]，這種沖突是最常見的沖突，在不同數據源模式中，表示同一概念的設計方法不同，有的用屬性表達，而有的用實體表達。

圖2 結構沖突形式

3 XML Schema模式集成關鍵問題解決

XML Schema模式集成分為3步，首先計算源模式之間的語義相似度與結構相似度，解決語義沖突，產生候選匹配映射，其次檢測與解決候選匹配映射集中的結構沖突，最后將未產生沖突的概念進行集成，生成全局模式。

3.1 模式集成中的語義沖突解決

3.1.1 語義相似度計算

語義分析作為自然語言處理技術的一個重要方面，其所依賴的語言知識表示中最重要的初始環(huán)節(jié)即是語義詞典。美國Princeton大學的WordNet[8]是語義詞典一個非常好的范例。目前，WordNet已成為一個事實上的國際標準，其框架的合理性已被詞匯語義學界與計算詞典學界所公認。

WordNet 是一個在線詞匯參照系統，其獨特之處在于其是依據詞義而不是詞形組織詞匯信息。WordNet使用同義詞集合(Synset)代表概念(Concept)，詞匯關系在詞語之間體現，語義關系在概念之間體現。WordNet 構造的核心是如何表示詞匯概念節(jié)點，以及在這些概念節(jié)點之間建立各種語義關系。WordNet 將英語詞匯組織為一個同義詞集合(Synset)，每個集合表明一個詞匯概念，同時力圖在概念間建立不同指針，表達上下位、同義反義等不同語義關系。

用以下公式計算語義相似度：

(1)

首先將屬性標簽進行分詞，通過WordNet獲得各個分詞含義[9]。其中|Ci|表示概念Ci通過WordNet獲得的含義數，SimSen(S1i,S2j)表示概念C1第i個含義與C2第j個含義之間的相似度。WordNet語義詞典將所有詞組織在樹狀的層次結構中。在一棵樹形圖中，任何兩個節(jié)點之間有且只有一條路徑。這條路徑的長度即可作為兩個概念語義距離的一種度量，可以利用 WordNet中詞節(jié)點之間上下位關系構成的最短路徑計算詞語之間的相似度，距離越小，相似度越大。計算公式如下：

(2)

其中，PathLength代表將S1與S2聯系起來的路徑長度。

3.1.2 結構相似度計算

針對語義沖突中不同數據源用不同元素名稱描述相同概念的問題，計算節(jié)點之間的語義相似度產生語義相似度矩陣，因而可以被很好地檢測出來。但是針對不同數據源使用相同元素名稱描述不同概念的問題，則需要綜合考慮元素節(jié)點的結構信息。

元素節(jié)點的結構信息主要包括兩部分內容：一是元素節(jié)點的屬性信息，表示為元素節(jié)點的葉子節(jié)點；另一部分是元素節(jié)點的父節(jié)點或子節(jié)點信息[10]，統稱為元素節(jié)點的上下文信息。假設A1代表源模式1中的一個元素節(jié)點，A2代表源模式2中的一個元素節(jié)點，則計算A1節(jié)點與A2節(jié)點之間的結構相似度即可轉換為計算A1節(jié)點與A2節(jié)點的葉節(jié)點相似度及上下文節(jié)點相似度。

設A1節(jié)點的葉子節(jié)點集合為|leaves(A1)|，A2節(jié)點的葉子節(jié)點集合為|leaves(A2)|，以A1節(jié)點作為基準，計算A1節(jié)點與A2節(jié)點之間的葉節(jié)點相似度公式如下[11]：

(3)

|leaves(A1)|代表A1節(jié)點的葉子節(jié)點個數，分子代表A1節(jié)點的葉子節(jié)點中與A2節(jié)點的葉子節(jié)點中語義相似度超過設定閾值的個數。取A1節(jié)點中的一個葉子節(jié)點，對A2節(jié)點的葉子節(jié)點進行遍歷，如果A2節(jié)點的葉子節(jié)點中存在與A1節(jié)點中該葉子節(jié)點的語義相似度大于設定閾值的情況，則保留該節(jié)點作為分子。

A1節(jié)點與A2節(jié)點之間的上下文節(jié)點相似度使用以下公式進行計算：

(4)

與葉節(jié)點的相似度計算類似，|ContextA1|代表A1節(jié)點的父節(jié)點與子節(jié)點個數，|{A1i|A1i∈ContextA1^?A2j∈ContextA2,lingSim(A1i,A2,i)≥threshold}|代表A1與A2節(jié)點上下文節(jié)點集合中語義相似度超過設定閾值的個數。

在語義相似度計算得出映射的基礎上，再進行計算得出映射的節(jié)點結構相似度。如果結構相似度也大于閾值，則宣布兩個節(jié)點之間存在映射關系。

3.2 模式集成中的結構沖突解決

上述部分描述了模式集成中存在的3種結構沖突，針對不同結構沖突設計了不同檢測方法，結構沖突的檢測基于上文生成的候選匹配集。

3.2.1 關系嵌套沖突

在XML模式轉換成的樹結構中，當相似概念之間的關系采用不同路徑長度或不同嵌套結構進行表達時，它們之間則會存在結構嵌套沖突[12]。如圖2(a)所示，medical_record//doctor和medical_record//department//doctor都表示病歷與醫(yī)生之間的關系，只是路徑長度不同。因此，結構嵌套沖突可以采用如下數學公式進行檢測：

len(x1//y1)≤maxlen

len(x2//y2)≤maxlen

|len(x1//y1)-len(x2//y2)|≤maxdis

(5)

x1、y1代表數據源1中的兩個節(jié)點，x2、y2代表數據源2中的兩個節(jié)點。(x1,x2)(y1,y2)是上文生成的候選匹配映射。len(x1//y1)代表x1節(jié)點到y1節(jié)點的路徑長度，由于關系型數據庫中的1∶1和1∶n關系都為直接關聯，而m∶n關系一般會用1∶n與m∶1進行描述。關系模式轉換到XML模式后，會以嵌套結構表示關系。因此，關系嵌套沖突只考慮嵌套層次相差一層的情況，即路徑長度相差不超過1。因此，maxlen取值為2，maxdis取值為1。針對關系嵌套沖突，在合并為全局模式時，只取路徑長度大的關系即可。

3.2.2 關系方向沖突

當相似概念之間的關系在XML模式樹中展示為不同路徑方向時，它們之間則存在關系方向沖突。如圖2(b)所示，medical_record//doctor和doctor//medical_record都代表病歷與醫(yī)生之間的關系，只是路徑方向不同。關系方向沖突可以采用以下數學公式進行檢測：

len(x1//y1)≤maxlen

len(y2//x2)≤maxlen

|len(x1//y1)-len(y2//x2)|≤maxdis

(6)

x1、y1代表數據源1中的兩個節(jié)點，x2、y2代表數據源2中的兩個節(jié)點。(x1,x2)(y1,y2)是上文生成的候選匹配映射。len(x1//y1)代表x1節(jié)點到y1節(jié)點的路徑長度。與結構嵌套沖突類似，maxlen取值為2，maxdis取值為1。針對關系方向沖突，在合并全局模式時，任取一個關系并入即可。

3.2.3 實體屬性沖突

當相同概念在一個數據源中被表示為屬性，在另一個數據源中被表示為實體jf ，則會存在實體屬性沖突[13]。如圖2(c)所示，location與adress都表示地址信息。針對實體屬性沖突的檢測規(guī)則如下：(x1,x2)為候選匹配映射，x1為葉子節(jié)點，x2為非葉子節(jié)點，同時x2節(jié)點到x2葉子節(jié)點的長度為1。針對實體屬性沖突，在生成全局模式時，將x1節(jié)點并入x2節(jié)點即可。

3.3 模式集成算法描述

(1)將各個局部數據源模式進行模式抽取與轉換，生成各個局部的XML Schema文件。

(2)對各局部的XML Schema文件進行模式編碼，轉換成模式樹結構。

(3)對各個局部的XML Schema模式樹進行語義相似度與結構相似度計算，生成節(jié)點之間的候選匹配映射。

(4)針對生成的候選匹配映射集進行結構沖突檢測，并解決結構沖突。

(5)將不產生沖突的節(jié)點并入全局模式樹中，生成全局XML Schema文件。

模式集成流程如圖3所示。

圖3 模式集成流程

4 實驗結果

4.1 評價標準

對于全局模式集成的有效性評估中，分別使用準確率 (Precision)、 召回率 (Recall) 與 F 值 (F-measure) 表示模式集成算法的正確程度、完善程度與權衡結果[14]，計算公式如下：

準確率：表示在模式集成中自動匹配的正確匹配占總自動匹配結果的比例。

(7)

召回率：表示在模式集成中自動匹配的正確匹配占應有正確匹配的比例。

(8)

F值：表示模式集成結果中錯誤匹配與丟失正確匹配的比值，可較為客觀、全面地評價最后的匹配質量。

(9)

4.2 實驗結果與分析

本文算法主要針對健康領域異構數據的模式集成，因此選取HL7官方提供的5個健康領域的XML Schemal作為實驗數據集進行模式集成，實驗結果如圖4所示。

圖4 模式集成匹配質量

由圖4可以看出，當語義相似度閾值設為0.9時，本算法具有較高的準確率、召回率與F值。因為健康領域數據具有較高相似度，因此相似度閾值設定得越高，算法集成質量越高。

取閾值為0.9時，比較本文算法與PORSCHE算法結果如圖5所示。

圖5 模式集成算法比較

從上述實驗結果可以看出，對于健康領域的異構數據，將本算法與PORSCHE算法進行模式集成都有著較高質量，但是PORSCHE算法無法解決關系方向型的結構沖突，因此生成的集成模式較為冗余。本文算法對模式集成中的結構沖突重新作了檢測，能較好地解決關系方向沖突問題，對于集成后的全局視圖，可以減少冗余。

5 結語

本文研究了XML模式集成中的相關理論與算法，借鑒PORSCHE算法的模式集成思路，設計了新的結構沖突檢測及解決方法，重點解決了PORSCHE算法沒有解決的關系反向型結構沖突。經過試驗證明，本算法完成的XML模式集成能夠很好地解決結構沖突問題，減少了全局模式中的冗余關系，精簡了全局模式，同時利用WordNet計算語義相似度，從而提升了模式集成后自動生成的匹配準確度，為健康領域數據的統一查詢工作打下了良好基礎。