邵秀麗， 孫 杰， 侯樂彩

(南開大學信息技術科學學院，天津300071)

0 引 言

Deep Web研究目的是為用戶提供一個統(tǒng)一的訪問途徑以自動獲取和利用分布在Web上的一些Deep Web的信息。盡管DeepWeb中幾乎包含了所有我們需要的信息，但是要想以人工方式利用這些信息實際上是一件非常困難的事情，而Deep Web數據集成正是為了以盡可能自動的方式來達到對Web數據庫中信息有效利用的目的[1-2]。因此，具有很好的研究和應用價值。

本文研究并設計實現了DeepWeb集成系統(tǒng)，以通過一個統(tǒng)一的接口訪問所有分布的Web數據源，獲得質量優(yōu)結構好的信息[3]。其中，DeepWeb查詢接口模式抽取部分本文采用了人工介入配置形成所需信息，從而保證基礎研究的模式信息的準確性。模式匹配部分是DeepWeb信息集成的基本問題，本文提出了新相關度度量標準 S-measure進行數據挖掘的整體性模式匹配方法[4-6]，利用整體性方法進行的模式匹配有別于傳統(tǒng)1:1的匹配，不僅可以發(fā)現簡單的1:1匹配，還可以發(fā)現m:n的復雜匹配，匹配精確度和效率均很高。它可以在兩個模式之外挖掘上下文信息，比如，跨多源的相似屬性，屬性間的共存模式等。在完成了模式匹配給出輸入模式集的屬性間的同義匹配結果的基礎上，本文設計實現了面向Deep Web對象的查詢接口集成系統(tǒng)。根據源查詢接口的屬性出現頻率和屬性模式匹配結果，選擇全局查詢接口的屬性，然后生成屬性對應的表單元素，主要是基于屬性在模式中出現的頻數和屬性間的同義信息，最終提交集成的全局模式給用戶，從而生成全局的查詢接口，方便用戶實現查詢。

1 集成系統(tǒng)的架構設計

本文將特定領域(如圖書領域)的多個Web查詢接口頁面作為輸入，從查詢接口中抽取模式信息；然后通過數據挖掘的方式進行模式間的復雜匹配，這部分處理功能主要包含：數據預處理、匹配發(fā)現和匹配構建；基于匹配結果生成全局的查詢接口，從而完成查詢接口集成。系統(tǒng)的架構如圖1所示，其中：

(1)查詢接口模式抽取：主要完成從Html格式的Web查詢接口中抽取模式信息的功能。由于作為系統(tǒng)輸入的Web查詢接口頁面是Html格式的，而且包含許多接口外的無用信息，所以在進行模式匹配之前，需要設計一個接口抽取器，用于實現從各個參與Deep Web的接口中抽取模式信息。本文在設計的DeepWeb搜索原型系統(tǒng)中，采用了人工獲取這些接口信息，以避免因模式數據的錯誤而引起的匹配錯誤。并配置各種所需要抽取的模式信息，包括屬性信息、元素信息、元素值域、查詢接口網址。

(2)查詢接口模式匹配：對于人工抽取出的原始模式數據(其中的接口模式包含屬性信息為商品名、著譯者等)進行模式匹配。方法是：先對這些模式數據(主要屬性名)進行預處理，使它們適于數據挖掘。而后是對這些人工采集的模式進行匹配發(fā)現，該部分工作是模式匹配的核心部分。為發(fā)現可能的匹配，本文提出了一種相關性挖掘算法——整體模式匹配算法，算法實現的思想是：首先使用正相關挖掘挖掘出可能的成組屬性；然后使用負相關挖掘出可能的匹配(即同義屬性)；最后進行匹配構建工作，首先按照匹配的相關度排列發(fā)現的匹配，然后采用一致性約束策略篩選出最可信、最一致的匹配。

(3)查詢接口集成：本文基于模式匹配的結果和源Web查詢接口的屬性信息共同選擇全局查詢接口的屬性。具體做法是選擇在源查詢接口中出現次數較多的屬性，每組同義屬性(即每個匹配)中選擇一個代表性的屬性，且盡量選擇包含屬性多的成組屬性。然后再生成屬性對應的表單元素及其對應的元素值域。

圖1 系統(tǒng)工作流程

2 人工接口模式抽取

在模式匹配之前，需要得到一個帶有屬性信息的模式集。這就需要對同一領域(如圖書)的查詢接口進行模式抽取，可以進行人工抽取[7]，也可使用成熟的數據抽取工具自動抽取[8-9]。本文采用人工抽取的方法，對查詢接口的屬性信息進行配置。

為更好地開展模式抽取工作，首先要清楚需要抽取哪些信息。分為3塊工作：首先，為了進行模式匹配，必須抽取屬性信息及屬性與接口模式的對應信息；其次，為了生成統(tǒng)一的查詢接口，進而將用戶查詢轉換為到各個數據源的查詢，必須抽取屬性對應的表單元素信息，包括元素類型、元素名稱、元素值域等；最后，為了提交查詢從而得到結果數據，必須抽取接口的網址信息和提交方法信息。

2.1 配置接口信息

由于一個查詢接口包含多個屬性，一個屬性可能包含多個元素，一個元素包含一個表單控件和相關的描述信息，一個元素可能對應多個候選值，所以采用查詢接口、屬性、元素、元素值4級表結構來存儲接口信息。

首先配置查詢接口基本信息，包括站點名稱、網址、提交action、提交方法、所屬領域等，如圖2所示。存儲網址、方法信息是為了完成統(tǒng)一查詢接口到Web查詢接口的映射，向Web查詢接口提交查詢請求，并得到返回的結果。

圖2 配置接口信息

然后為每一個查詢接口配置對應的屬性信息，主要包括屬性名稱，如圖3所示。為了更適合于后續(xù)的模式匹配挖掘算法，這里對屬性標簽做一些處理，使屬性名稱盡量簡化：例如：①去除一般意義上的常用詞，如“的”、“了”和英語中的“on”、“of”、“the”等；②去除 Web常用詞，如“搜索”、“頁面”、“查詢”等；③去除網站名稱詞，如“卓越”、“當當”等；④去除領域詞，如“圖書”、“中藥”等。

圖3 屬性配置

接著配置屬性對應的元素信息，包括元素標簽、表單名稱、表單Id、表單類型、表單值數據類型、默認值等，如圖4所示。

圖4 元素配置

最后配置元素對應的值域，如圖5所示。

圖5 元素值域配置

配置元素信息是為了轉換生成Web查詢接口的查詢串，完成全局查詢接口元素到Web源查詢接口元素的匹配，從而在后續(xù)的查詢轉換時獲得查詢串的參數名稱，值域對應查詢串的參數值。

2.2 數據預處理

上面在配置屬性信息時，已做了初步的簡化工作，下面在此基礎上繼續(xù)對屬性信息進行句法合并處理：通過衡量屬性名稱和屬性值域的句法相似性合并屬性實體，例如可通過名稱相似性將“title of book”合并到“title”。

通過考察語言相似度來合并句法相似的實體是一種常見的數據清洗技術[10-11]。本文通過分別衡量屬性名稱和屬性值的句法相似性設計了基于名稱的合并和基于值域的合并。句法合并將會減少屬性實體的數目，增加單個的屬性實體在不同模式中出現的頻數，從而可以增強相關挖掘的效果。

(1)基于名稱的合并

如果兩個屬性的名稱相似，則合并它們。觀察發(fā)現大多數DeepWeb數據源使用簡潔的核心的屬性名稱(如title)，而其它的數據源使用這些核心詞匯的變形(如titleofbook)。因此，如果屬性Ap的名稱包含屬性Aq的名稱 (即Ap的名稱是Aq的名稱的變形)而且Aq比Ap更常出現(即Aq是大多數)，則認為Ap是與 Aq名稱相似的。這種基于頻率的策略可以避免絕對合并。例如，在Books領域，lastname就不會被合并到name中，這是因為lastname比name更常出現，這種情況下本文認為它們是兩個不同的屬性實體。

(2)基于值域的合并

如果兩個屬性的元素的值域相似，則合并它們。對查詢接口來說，本文認為屬性的元素值域是其可選擇的值的集合。這些值在Web表單中經常以select控件選項或radio button的形式出現。本文只考慮帶有string類型值的屬性，因為對于其它數據類型的值來說，值相似通常并不意味著屬性相似。例如，在機票領域，passengers的整型數值與connections的整型數值非常相似，但事實上它們表示不同的意思。

將屬性的元素可選值看作單詞包(即，單詞頻數的計數)，稱為集合值，屬性A的集合值記作VA。對于單詞w，其在VA中的頻率記作。屬性Ap和Aq的值域相似性即和的相似性。理論上，任何合理的相似度函數在此都適用。本文特別選擇作為相似度函數。

例如：假設機票領域的 3 個模式：S1、S2、S3，S1的包含的屬性實體為，S2包含的屬性實體為，S3包含的屬性實體為。

屬性實體triptype出現在S1和S2中，所以其集合值為Vtrip type={round:2,trip:2,one:2,way:2,multi:1,city:1}，其中每個單詞后面標著它的頻數。特別地，Vtriptype(round)=2，因為round在兩個模式中都出現了。類似的Vtickettype={round:1,trip:1,one:1,way:1}。所以根據上面的相似度函數可以得到

由于相似度數相當大，因此兩個屬性是相似的，可以合并為一個屬性實體trip type。

3 查詢接口模式匹配

本文的模式匹配工作由匹配發(fā)現和匹配構建這兩個前后相連的步驟組成。將模式匹配問題分成上述兩個處理功能模塊，明確定義兩個模塊之間的接口，這樣就可以建立模塊化的解決方案。在匹配發(fā)現和構建匹配之前，需要對輸入的模式數據進行數據預處理工作，即將輸入的模式數據屬性名盡量簡化，使其容易被挖掘。

3.1 匹配發(fā)現

匹配發(fā)現工作的目的是在屬性信息的基礎上應用本文的整體模式匹配算法來發(fā)現所有候選匹配，此候選匹配集中即包含簡單的1:1匹配，也包含復雜的m:n匹配，而且可能包含n元復雜匹配。這些候選匹配可能是正確匹配也可能是錯誤匹配，這一步是模式匹配工作的重點，目的是從特定領域的多個接口模式中獲得不同屬性間的所有可能的語義同義信息[12-13]。工作流程是首先在屬性上進行正相關挖掘，以發(fā)現可能的成組屬性，然后將成組屬性加入源模式信息，在此基礎上再進行負相關挖掘，發(fā)現可能的同義屬性。

本文將查詢接口看作一個包含一系列屬性實體的扁平模式。屬性實體定義為屬性名稱和屬性元素。每個屬性實體被賦予一個唯一的屬性標識(簡稱為屬性)。為方便描述，在屬性實體上進行匹配時，使用屬性名稱作為屬性標識。

匹配發(fā)現步驟的形式化描述為：給定一個同一領域的模式集I={Q1,Q2,…,QN}作為輸入(其中Qi為一個屬性集)，發(fā)現所有的候選匹配R={M1,…,MV}，其中Mj為一個候選的n元的復雜匹配，其中是一個屬性組(即語義上等價于另一個屬性或另一個屬性組的一組屬性)，而且。每個Mj表示屬性組間的語義同義關系，而每個表示中屬性間的成組關系。

相關挖掘的一個關鍵問題是相關度的度量方法，即如何計算多個屬性的正相關度和如何計算多個屬性、屬性組的負相關度。為解決這個問題，本文設計了一個具有Apriori特征的度量方法，由計算兩個數據項的相關度開始，逐步計算3項、4項、……數據的相關度。

3.2 匹配構建

匹配構建的工作重點是從候選匹配集中采用一致性約束策略選擇語義上最可信、最一致的子集作為最終的匹配結果，這步工作就是對匹配結果的優(yōu)化，本文使用基于相關度分值的匹配排列和基于一致性約束的選擇策略。

匹配構建工作的主要目的是在候選匹配集中選擇可信度高的、不互相沖突的匹配。

給定發(fā)現的候選匹配集R={M1,…,MV}，匹配構建工作包括：匹配排列和匹配篩選。

在匹配排列階段，按照特定的排列標準C給所有的候選匹配排序，排序后用RC={}表示。以往的模式匹配算法幾乎都是以發(fā)現成對語義相關匹配為目的的，在此類模式匹配算法中，匹配排列階段都非常簡單，直接根據匹配發(fā)現步驟計算出的分值排列候選匹配。然而，在本文的尋找n元復雜匹配的方案框架下，這種簡單的排列策略就不再適用了，所以開發(fā)出了一種不同評分策略Cmax。

匹配篩選階段，選出RC的一個子集作為最后的匹配進程的輸出。大多數模式匹配方案都基于一致性約束選擇候選匹配，比如兩個覆蓋同一個屬性(本文稱之為沖突)的匹配不能同時被選中，本文也采用這樣的一致性策略來篩選候選匹配。

4 查詢接口的集成

Deep Web數據集成的核心即是形成統(tǒng)一的查詢接口界面，即查詢接口的集成。查詢接口集成的目的是為用戶提供統(tǒng)一的全局查詢接口，用戶在此接口界面上輸入查詢信息，點擊查詢后即可獲得多個Web源的查詢結果[14-15]。

本文基于模式匹配的結果和源Web查詢接口的屬性信息共同選擇全局查詢接口的屬性。方法是選擇在源查詢接口中出現次數較多的屬性，每組同義屬性(即每個匹配)中選擇一個代表性的屬性，且盡量選擇包含屬性多的成組屬性。然后再生成屬性對應的表單元素及其對應的元素值域。最后基于接口模式和模式匹配結果形成一個全局的查詢接口。查詢接口集成包括屬性選擇，表單元素生成和元素值域生成3部分工作。

4.1 屬性選擇

首先統(tǒng)計各屬性和屬性組在接口中出現的概率，存入數據庫相應字段。研究表明，出現概率在20%以上的屬性占領域內所有屬性的80%，據此選擇出現概率20%以上的屬性和屬性組作為候選屬性(組)。

考慮到后續(xù)的查詢轉換步驟，知道從屬性組到單個屬性的轉換要比從單個屬性到屬性組轉換更容易，前者只需要簡單的將各個屬性對應的元素值組合起來，而后者需要對屬性的元素值進行拆分。所以在進行屬性選擇時優(yōu)先選擇屬性組，而且優(yōu)先選擇包含屬性較多的屬性組。綜合以上分析，屬性選擇規(guī)則如下：

第一步，對于在同義屬性Mj：Gj1=Gj2=…=Gjw中出現的候選屬性(組)，按以下規(guī)則選擇一個Gjk代表此同義概念出現在最終的查詢接口中：

(1)若Mj包含成組屬性，且成組屬性出現概率在20%以上，優(yōu)先選擇成組屬性；若無成組屬性，再選單個屬性；

(2)選擇成組屬性時，優(yōu)先選擇包含屬性多、出現次數多的組，相同時，任選其一；

(3)選擇單個屬性時，優(yōu)先選擇出現次數多的屬性，次數一樣多時，任選其一。

第二步，對于不在同義屬性中出現的候選屬性Ai，此屬性需出現在最終的查詢接口中。

將選出的屬性和成組屬性存入新的數據庫表 generalAttribute和 GeneralGroup。

4.2 表單元素生成

統(tǒng)一查詢接口的屬性確定之后，就需要為各個屬性生成表單控件[10]。通過4.1知道，查詢接口中的表單控件類型一般有text、radio、checkbox、select、textarea這5種，其中radio和select都是單選，其效果是相同的；text和textarea都是文本輸入框，也認為其作用是相似的。因此，出現在最終的統(tǒng)一查詢接口中的表單控件類型可以簡化為text、select、checkbox這3種。

考慮到后續(xù)的查詢轉換步驟，很明顯將select的值轉換為text的值要比從后者到前者的轉換容易得多，因為text的值是用戶輸入的，很難保證其在select中有對等的值。因此，系統(tǒng)更傾向于使用select控件。類似的，當select和checkbox比較時，傾向于使用select控件，這是因為單選到多選的轉換比多選到單選的轉換相對容易得多。當checkbox和text比較時，傾向于使用checkbox控件。綜合以上分析，為屬性生成表單控件時，具體做法如下：

對于上文選出的屬性，考察它即其同義屬性在原始查詢接口中包含的表單元素的元素類型、元素數目及其出現的次數。

式中：C(n)select——對應n個select元素的屬性出現的次數，其它類似。

GmaxSelect=max(G(n1)select,G(n2)select,…,G(nm)select)，GnumberSelect為取到最大值的G(n)select對應的nj。

GmaxCheck、GnumberCheck與 GmaxText、GnumberText也作類似定義。

比較 GmaxSelect、GmaxCheck、GmaxText的大小，可得：

(1)若 GmaxSelect>=GmaxCheck且 GmaxSelect>=GmaxText，則屬性對應的表單控件是GnumberSelect個select列表，元素名稱為select1、select2、…；

(2)若 GmaxCheck>GmaxSelect且 GmaxCheck>=GmaxText，則屬性對應的表單控件是GnumberCheck個checkbox，元素名稱為check1、check2、…；

(3)若GmaxText>GmaxSelect且GmaxText>GmaxCheck，則屬性對應的表單元素是 GnumberText個 text，元素名稱為 text1、text2、…。

4.3 值域生成

設置select控件、checkbox控件的值域。

select控件：若GnumberSelect=1，對于可選值較少且比較固定的值域，如折扣，在人工抽取階段統(tǒng)一處理，如30折以下錄入時改為3折以下。對可選值較多且不同接口的相應元素間差別較大的值域，如圖書類型，選擇對應元素的值域的并集作為統(tǒng)一接口中對應元素的值域；若GnumberSelect>1，選擇一個元素類型為select、元素數目為GnumberSelect的對應屬性的元素值域，直接一一對應賦值給各個select元素。Post值與顯示值相同。

checkbox控件：若GnumberCheck=1，選擇對應元素的值域的并集作為統(tǒng)一接口中對應元素的值域；若GnumberCheck>1，選擇一個元素類型為checkbox、元素數目為GnumberCheck的對應屬性的元素值域，直接一一對應賦值給各個checkbox元素。

4.4 集成接口

選擇出屬性、生成屬性對應的表單元素及其值域之后，就可以生成全局的查詢接口[11]。將選擇出來的屬性和生成的表單元素布局到同一個頁面，為了界面的友好性和易用性，采用如下規(guī)則：

(1)每個屬性的屬性名及其對應的元素布局到同一行；不同的屬性布局在不同行。

(2)根據元素類型動態(tài)生成對應類型的元素，對于text類型的元素，直接布局與對應屬性的后面；對于和checkbox類型的元素和select類型的元素，通過查詢值域表得到選項值。

(3)最后加入搜索按鈕，形成全局查詢接口。

5 Deep Web圖書搜索系統(tǒng)實際應用情況

DeepWeb圖書搜索系統(tǒng)試圖建立一個全局的圖書搜索界面，用戶只需要在這個界面中輸入一次查詢信息，即可在互聯網上眾多的網上書店站點中查詢相應的圖書信息，減輕用戶的搜索負擔和輸入負擔。

該系統(tǒng)主要功能模塊包括抽取多個網上書店的查詢接口信息，在抽取的模式信息上進行模式匹配，利用源模式屬性信息和模式匹配的結果3部分。抽取出的模式信息存入關系數據庫中，顯示、配置效果如圖6所示。

圖6 Deep Web圖書搜索系統(tǒng)接口配置界面

抽取的模式信息中，共有32個屬性實體，屬性實體及其出現頻數，例如出現概率在20%以上的屬性有：出版社(頻數14)，ISBN(頻數 12)，作者(頻數 11)，書名(頻數 10)，售價(頻數 9)等。在這些接口信息上進行模式匹配，發(fā)現接口間屬性信息的同義匹配關系有{出版日期}={出版時間}(排列分值為0.765625)、{分類}={類別}(排列分值為 0.70000)、{名稱}={書名}(排列分值為0.757575)、{著譯者}={作者 (排列分值為0.733333)}。結果表明模式匹配的結果是具有很高的準確率和有效性。最后綜合源模式的屬性信息和模式匹配結果自動生成統(tǒng)一的全局網上圖書查詢界面如圖7所示，該界面包括了網上書店查詢接口的絕大部分意義相當的查詢條件，取得了良好的準確性、友好性、易用性。

圖7 Deep Web圖書搜索查詢接口

6 結束語

本文對Deep Web查詢接口模式抽取、Deep Web查詢接口模式匹配及查詢接口的集成進行了研究，并在這些研究基礎上建立了一個面向Deep Web對象的查詢接口集成系統(tǒng)，達到了對Deep Web關鍵技術的探討和實踐的目的。但仍然處于探索性的工作，要實現一個真正可用的自動集成系統(tǒng)仍然有許多的問題，例如：接口模式的自動獲取等有待更深入的研究。

[1]Kabra G,Zhang Z.Dewex an exploration facility for enabling the deep web integaration[C].Proceedings of 23rd International Conference on Data Engineering,2007:1511-1512.

[2]Liu W,Meng X F,Meng W Y.A survey of deep web data integration[J].Chinese Journal of Computers,2007,30(9):1475-1489.

[3]劉偉,孟小峰,孟衛(wèi)一.Deep Web數據集成研究綜述[J].計算機學報,2007,30(9):1475-1489.

[4]Avigdor Gal.Interpreting similarity measures:bridging the gap between schema matching and data integration[C].International Conference on Data Engineering,2008:278-285.

[5]Chuang S L,Chang K C.Integrating web query results:holistic schema matching[C].Proceeding of the 17th ACM Conference on Information and Knowledge Management.New York,USA:ACM Press,2008:33-42.

[6]Zhontian He,Jun Hong,David Bill.Schema matching across query interfaces on the deep web[C].Proceedings of the 25th British National Conference on Databases,2008:51-62.

[7]Chang K C C,He Bin,Li Cengkai,et al.The UIUC web integration repository[EB/OL].http://metaquerier.cs.uiuc.edu/repository/datasets/tel-8/browsable.html.2007-10-21.

[8]Zhang Z,He B,Chang K C C.Understanding web query interfaces:Best-effort parsing with hidden syntax[C].Proc of the ACM SIGMOD Conference.New York,USA:ACM Press,2004:107-118.

[9]Qian L H,Zhou GD,Zhu QM,et al.Exploiting constituentdependencies for tree kernel-based semantic relation extraction[C].Proceedings of the 22nd International Conference on Computational Linguistics,2008:696-704.

[10]劉玉,陳金雄.數據倉庫中的數據清洗[J].醫(yī)學信息,2008(11):55-71.

[11]王詠梅,嵇曉,汪恒杰,等.面向多數據源的數據清洗關鍵技術的研究[J].科技資訊,2009(1):35-43.

[12]He B,Chang K C.Making holistic schema matching robust:An ensemble approach[C].Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.Chicago,USA:ACM Press,2005:429-438.

[13]Evermann J.Theries of meaning in schema matching:an exploratory study[J].Information Systems,2009,34(1):28-44.

[14]Liu Wei,Li Xian,Ling Yanyan,et al.A deep web data integration system for job search[J].Wuhan University Journal of Natural Sciences,2006,11(5):34-40.

[15]Jiang Fangjiao,Jia Linlin,Meng Xiaofeng.Query translation on the fly in deep web integration[J].Wuhan University Journal of Natural Sciences,2007,12(5):29-34.