基于本體和貝葉斯網絡的Deep Web集成系統研究

朱國進， 黃琪琪

(東華大學 計算機科學與技術學院， 上海 201620)

引言

隨著互聯網技術的發展，網絡中出現了越來越多的在線數據庫。這些數據一般不被搜索引擎通過靜態鏈接而得到，而是需要通過HTML表單提交查詢，由服務器根據請求動態生成頁面。研究中通常把這些隱藏在后臺的在線數據庫稱為是Deep Web，也稱為Hidden Web。

根據Bergamn等人在2000年的研究表明，存儲在Deep Web中的數據量是表層Web的500倍[1]，在2014年“互聯網實時統計”[2]顯示，全球互聯網網站的數量已經超過了10.6億，而在2011年時，只有5.55億，這些數據說明互聯網網站的數量在急速增長，相對地Deep Web中隱藏的數據量也在大幅增加，所以業界對Deep Web的研究是極為重視的。然而這些數據隱藏在后端數據庫(即Deep Web數據源)中，無法被搜素引擎所查詢，只有在用戶提交查詢條件后通過Web服務器動態地生成結果頁面返回給客戶端[3]。在圖1中展示了用戶通過查詢接口而在Web數據庫中獲取信息的過程。

圖1 從Web數據庫中獲取數據庫信息

Fig.1ObtainingdatabaseinformationfromtheWebdatabase

1 Deep Web查詢接口集成系統構建

Deep Web研究的根本目的旨在同時訪問分布在互聯網中的同領域Deep Web數據庫中的信息資源。本文針對Deep Web集成系統的關鍵問題進行了研究，從Deep Web的入口查詢接口為主線，研究查詢接口的特征提取、領域分類和接口模式匹配。

在本文中，提出一種語義Deep Web方法，通過使用基于程序設計者視角和基于用戶視角的屬性提取方法，結合WordNet確定最終屬性，并通過WordNet自動構建領域語義本體樹，最后通過領域語義本體樹進行訓練得到分類器模型和查詢接口模式匹配，完成Deep Web查詢接口的集成生成模塊。設計流程如圖2所示。

圖2 Deep Web集成系統構建流程圖Fig. 2 The flow chart of Deep Web integrated system construction

1.1 Deep Web查詢接口屬性自動抽取

在論述本文工作原理前，需要探討解釋Deep Web中屬性的含義。在本文中，屬性指能夠表示控件的作用的特征詞，因此，對查詢接口屬性在本文中將給出如下定義。

定義1程序設計視角屬性(Programmer Viewpoint Attributes，簡稱PVAs): PVAs是從HTML標簽中的內部標識符提取，在本文中特指表單中控件的name屬性值。

定義2用戶視角屬性(User Viewpoint Attributes，簡稱UVAs): UVAs是Web表單中的文本，一般處在標簽之間，用戶可以在查詢接口頁面中直接觀看的文本信息，如圖3中Web網頁中的User Id:。

圖3DeepWeb接口示例

Fig.3DeepWebinterfaceexample

Deep Web接口HTML設計代碼展開如下：

▼

本文提取Deep Web接口的正確屬性方法如圖4所示。在圖4中，可以看到，UVA和PVA之間存在重疊區域，也就是說通過比較PVAs和UVAs的重疊部分來確定最終屬性。

圖4 Deep Web數據源信息處理方法Fig. 4 Deep Web data source information processing method

1.1.1 基于程序設計者視角屬性提取

HTML中內部標識符和表單中文本可以輕松地使用程序提取，然而并不能直接派作選擇使用，因此需要對其進行處理，進一步分成為多個獨立的單詞并生成備選屬性(CA:candidate attributes)。算法1展示了從一個Deep Web接口中分離出一組基于內部標識符的備選屬性CAi的步驟。其中，DSi是一組Web查詢接口，包含HTML的表單元素{HF1,HF2, …,HFn}，令IIi表示從DSi中提取的一組內部標識符，KW表示來自所在Web查詢接口中提取控件對應的文本標簽。算法1的基本設計代碼如下。

算法1提取備選屬性(CA)

for eachHFinDSi:

//從Web頁面中抽取表單元素

forIIiinHFi

//從表單元素中抽取內部標識符

ifIIicontains special symbols (.,_,:,@,+,=,-,*,,?, ,et)

separateIIiinto sub-strings//如果內部標識符有特殊符號，將其分隔成多個子字符串

ifIIicontains capital letters

separate each sub-strings into several sub-strings //如果分隔后的子字符串中包含大寫字母，依照大寫字母分隔開

ifIIicontains word inKW

separate it into sub-strings by the word

saveIIiand sub-strings asCAi//將提取的內部標識符和分隔后的字符串作為CAi

returnCAi

從所有的Deep Web數據源中得到備選屬性(CA)，PVA需要通過算法2從所有的CA中進行提取。算法2的運行代碼可表述如下。

算法2提取PVA

add allCAiinto PVA

for string in PVA

if string appear one time in PVA

//刪除只出現一次的字符串

remove it from PVA

if string appear several many times in PVA

//刪除重復項

save one and remove the duplicate ones

return PVA

圖5展示了獲取程序設計者視角(PVA)提取屬性特征的例子。假設具有2個Deep Web數據源DS1與DS2，通過提取得到2組內部標識符屬性II1和II2,通過算法1進行分隔處理，本文從2組內部標識符得到2組備選屬性CA1與CA2，將2組內部標識符通過算法2進行處理，最終得到PVA。

1.1.2 基于用戶視角屬性提取

用戶視角屬性用來確定Deep Web數據源的最終屬性，這是從查詢接口的文本中獲取的。在算法3中給出了在每個Deep Web數據源中獲取UVA的過程，可將HTML標簽之間的文本存儲在基于文本的備選屬性TCAi(text-based candidate attributes)。其中,標簽之間的文本是被忽略的，因為在這之間的文本表示的是實例，而不是描述屬性。

圖5 獲取PVA示例Fig. 5 The example of obtaining the PVA

算法3提取UVA

for eachHFi

obtain all the text asTCAi

for string inTCAi

if string is a sentence

//如果文本為句子，提取出內容關鍵字

extract import word asTCAi

if string contains special symbols (.,_,:,@,+,=,-,*,,?, ,et)

separate string into several sub-strings //如果文本有特殊符號，將其分隔成多個子字符串

if string contains capital letters

separate strings into several sub-strings

//如果分隔后的子字符串中包含大寫字母，依照大寫字母分隔開

remove the duplicated inTCAi, save it intoUVAi

returnUVAi

在算法3中提取UVA，和提取PVA的算法很相似。不過UVA中提取的基于文本的備選屬性是來自于控件對應的文本。同時，在部分Deep Web查詢接口控件對應的文本是一句完整的句子，需要提取出句子內容的關鍵字。隨后對提取屬性進行消除重復處理，得到UVA。

1.1.3 基于本體的屬性拓展

本文通過WordNet本體來獲得PVAs和UVAs的同義詞，并確定最終屬性。在本文只專注于名詞，因此，使用2個規則來過濾候選屬性：檢查候選屬性在WordNet中是否有名詞含義，如果在WordNet中至少有一個名詞含義，這個詞將被保留，否則丟棄；然而，一些候選屬性是由詞組組成，無法在WordNet查詢。為了解決這個問題，第二條規則用來保留這些重要的詞：如果一個候選屬性是由詞組構成，且構成詞組的單詞在WordNet中具有名詞含義，那么保留短語。

利用WordNet的詞匯關系，本文通過PVA或UVA得到了其中所有的候選屬性SOPVA、SOUVA，表1即為使用WordNet獲得同義詞的例子。

表1 獲得同義詞示例Tab. 1 The example of obtaining synonyms

1.1.4 最終屬性提取

最終屬性(Final Attribute，簡稱FA)必定是來自于SOUVA中的元素，相比較基于程序設計者視角提取出的屬性，基于用戶視角提取的屬性更為規范。來自SOUVA中的元素其字符串或者其同義詞之一的字符串與SOPVA中的一個元素相匹配，并且與UVA的該字符串元素的所有連續字符串塊的占有率大于α %(0<α<100)，α是影響最終屬性總數的因素，即α越小，最終屬性數越多。圖6即為獲取最終屬性示例。

圖6 獲取最終屬性示例Fig. 6 The example of obtaining final attribute

1.2 構建Deep Web領域本體

由于人類與程序之間的知識共享的目標，本體的構建將在語義網絡和Deep Web中發揮主導作用。為了支持語義網，構建領域的特定的本體是可取的，但是，手動構建本體是十分困難的，極其耗時且容易出錯[4-5]。

當下，自動構建領域本體的方面工作已經成為研究熱點，并且推出了可觀研究成果。OntoBuilder[6]通過將一個網站作為層次結構，在每個網站對應的本體之間進行匹配。DeepMiner[7]根據樹形結構中表單元素的相對位置提取概念和實例。在OntoMiner中IS-A關系通過網頁中XML樹中的父子頻率進行挖掘。綜上方法的共同特點是研究了從Web中提取出本體的方法，但是沒有提供最終的本體，無法應用在語義網絡中。

本文使用WordNet的語義關系上位詞(hypernym)將最后的屬性組合在一起，并根據其中的最近公共上位詞構成有向無環圖DAGs(directed acyclic graphs)。將這些最終屬性根據上位詞關系組合在一起的片段稱為DAG片段(small DAGs schema fragments，簡稱SFs)。當只有一個DAG或者達到最大迭代次數時，迭代終止。在圖7中展示了在Online Judge領域中的部分最終屬性通過最近公共上位詞構成SF的例子。

在圖7中，具有2個最終屬性(author, user)，通過WordNet來檢索對應的上位詞，最終發現，可以通過person來作為最近公共上位詞，可以用person來表示這2個最終屬性。在圖7(a)中顯示了2個最終屬性；圖7(b)中因為2個最終屬性沒有直接上下位關系，因此通過WordNet找到2個屬性的上位詞，虛線橢圓表示從WordNet派生出來的本體；圖7(c)繼續尋找上位詞，發現person為2個最終屬性的最近公共上位詞，將person作為該SF的根節點。

圖7 基于最近公共上位詞構成樹示例Fig. 7 The example of a recent common epistasis tree

獲得最終語義本體樹的步驟如算法4所示。

算法4構建領域語義本體樹

for all FA

ifFAiis a hypernym ofFAj//如果FAi是FAj的上位詞，建立IS-A連接

create DAG by inserting a new IS-A link betweenFAiandFAj

deleteFAi,FAjfrom FA

else ifFAjis a hypernym ofFAi

//如果FAj是FAi的上位詞，建立IS-A連接

create DAG by inserting a new IS-A link betweenFAiandFAj

deleteFAi,FAjfrom FA

While(just has only one DAG or iteration has been reached )

//到只有一個DAG時候或者迭代次數超過限制

for each DAG //對每個DAG的root節點在WordNet中尋找上位詞

add new root by inserting the IS-A link between DAG's old root and it's hypernym;

for all DAG //對DAG根節點尋找在其它DAG中節點是否有其上位詞

if find an IS-A link betweenDAGi's root andDAGj's node

inserting a new IS-A link betweenDAGi's andDAGj's node

領域本體樹構建完成后，對最終屬性進行拓展，尋找其同義詞集，添加進語義本體樹中，進一步消除查詢接口中屬性的詞形異構性。在WordNet中，所有名詞的最終祖先皆為entity，因此如果在算法3，最終只有一個DAG，可以將根結點替換成該領域名稱，如果有多個DAG，可以將該領域名稱作為最終根結點，并將各個DAG與該節點連接起來。圖8則為通過該方法得到的經過簡化的Online Judge領域語義樹。

圖8 Online Judge領域簡化語義樹Fig. 8 Online Judge domain simplified semantic tree

在得到Deep Web領域本體樹的時候，可以根據領域語義本體樹生成該領域Deep Web集成查詢接口。例如圖8的Online Judge領域語義本體樹，可以得到problem、person、result、language四個本體，生成如圖9所示集成查詢接口。

圖9OnlineJudge領域集成查詢接口

Fig.9OnlineJudgedomainintegratedqueryinterface

1.3 貝葉斯網絡分類器

本文在使用貝葉斯網絡算法時，通過領域語義本體樹，將測試集Deep Web查詢接口轉換成特征向量，進行訓練得到貝葉斯網絡分類器，如圖10所示。

圖10 貝葉斯網絡分類器訓練Fig. 10 Training of Bayesian network classifier

通過語義本體樹將每一個Deep Web數據樣本使用一個n維特征向量X= {x1,x2,x3,…,xn}(n的維度來自于各個語義樹根節點的直接相連節點數)表示，分別描述該Deep Web樣本具有的特征屬性：A1,A2,A3，…,An。研究步驟內容如下。

(1)對訓練樣本進行特征提取，將得到的特征與該領域語義本體樹進行匹配，通過統計，可以得到該領域貝葉斯網絡的條件概率表；

(2)貝葉斯網絡拓撲結構和條件概率表構成貝葉斯網絡分類器Hn；

(3)通過貝葉斯網絡分類器Hn對測試樣本進行分類，得到分類結果。

1.4 接口模式匹配

由于每一個查詢接口都具有自己的命名規則，導致查詢接口的屬性特征具備多樣性、異構性和欠完備性，因此需要進行預處理過程，根據一些規則將其標準化，獲得統一的表達方式再進行匹配。

根據查詢接口中表單模式信息的情況，通過2種匹配方式來進行模式匹配：直接模式匹配和間接模式匹配。其中，直接匹配是將表單的屬性和領域語義本體樹中的本體信息使用基于字符串的方式進行匹配，該字符串元素的連續字符串塊的占有率大于α% (0<α<100)，則匹配成功。而由于本體信息是有限的，有些可匹配的查詢接口屬性特征無法通過基于關鍵詞匹配的方法進行匹配，此時通過查詢接口屬性特征和領域語義本體樹中的本體進行語義相似度計算，來尋找匹配的本體信息，這就是間接匹配。模式匹配的整體流程如圖11所示。

圖11 模式匹配流程圖Fig. 11 The flow chart of pattern matching

本文中的領域的集成查詢接口是根據構建的領域語義本體樹的結構得到的，當匹配到處于領域語義本體樹中的相應本體后，可以通過領域語義本體樹找到集成查詢接口對應的本體，直至查詢接口模式集合匹配中為空，就完成一個該領域Deep Web查詢接口與集成查詢接口的模式匹配。

2 實驗與結果分析

本實驗采用了UIUC大學的Deep Web數據集合TEL-8數據集，分為8個領域： Airfare、Automobile、Book、Car Rentals、Hotels、Jobs、Movie、Music。考慮到TEL-8數據集中網頁信息年限較久，因此，本文在每個領域添加了20個通過手工收集的該領域的Deep Web網頁，并添加一個新領域Online Judge，總計9個領域，613個Deep Web查詢接口。

數據集分布如表2所示。本文采用隨機在其它領域查詢接口與非查詢接口中抽取400個樣本作為反例。

表2 Deep Web查詢接口數據集分布Tab. 2 Deep Web query interface data set distribution

在本節，展示了在特征屬性提取結果、貝葉斯分類判別、接口模式匹配的3個實驗結果，通過這3個實驗結果進行分析，證明了本文提出的方法的可行性。

2.1 特征屬性提取結果

一個特征屬性是包括其控件的屬性標簽和該控件對應的文本信息確定的。實驗結果如表3所示。

表3 屬性特征提取實驗結果Tab. 3 Experimental results of attribute feature extraction

在表3中詳細列出在各個領域中提取的最終屬性、DAG數量和通過WordNet得到的拓展詞。但是目前并沒有確定對本體構建的統一評價標準，因此無法對本文所得到的各個領域語義本體樹進行客觀評價。在本文中，根據應用在貝葉斯網絡分類和模式匹配實驗的結果來表現本文領域語義本體樹的性能。

2.2 貝葉斯網絡分類實驗結果

為了保證分類模型的準確性，同時也考慮到數據集規模偏小，因此采用5折交叉驗證方法來選擇和評估模型，將訓練結果取平均值作為最終結果。實驗結果如表4所示。

表4貝葉斯網絡分類實驗結果

Tab.4ExperimentalresultsofBayesiannetworkclassification%

將表4以直方圖形式展現，最終效果如圖12所示。可以發現，Online Judge領域表現結果最好，達到100%，其他領域的準確率、召回率和F1-measure基本保持在90%以上，說明本文提出的方法具有較好的可行性和適用性。

圖12 貝葉斯分類實驗結果Fig. 12 Experimental results of Bayesian classification

通過對比其它采用手工構建領域本體方法進行分類[8-9]得出的實驗結果再經討論總結和綜合分析后發現，采用數據集相同，試驗結果在查全率和準確率方面相差不大，證明了本文自動構建的領域語義本體樹的的合理性以及分類算法的適用性。

2.3 接口模式匹配結果

在接口模式匹配階段,采用的數據集為已經劃分好領域的Deep Web數據集，且所有查詢接口中屬性特征的匹配都是視作1∶1型匹配。各領域的匹配結果，如表5所示。

表5 模式匹配結果Tab. 5 Pattern matching results

將表5匹配結果以直方圖表示，可得結果如圖13所示。通過模式匹配過程，各個領域大部分的查詢接口特征屬性都可以成功完成匹配，通過對比其它通過手工或半手工構建領域語義本體方法進行模式匹配的結果[10-11]，在匹配準確度上相差不大，可以確定自動構建的領域語義本體樹的合理性和在查詢接口模式匹配方面的可行性與有效性。

圖13 模式匹配結果Fig. 13 Pattern matching results

3 結束語

隨著互聯網的高速進步，動態網站的技術的不斷進步，隱藏在這些Web中的Deep Web數據庫中的資源必定日益增加。但是Deep Web具有隱蔽性、動態性和異構性等特征，為獲取Deep Web中的海量資源帶來了嚴峻挑戰。本文中提出的方法提供了自動構建Deep Web查詢接口集成系統的解決方案，但是由于Deep Web自身具備特點，依舊需要更多工作的探索完善。在下一步工作中，將會在這方面繼續改進，提高查詢接口分類和模式匹配的準確性。互聯網的高速發展，必定使Deep Web數據集成收獲更多的研究和關注。在未來，Deep Web數據集成會如同傳統搜索引擎一般使用戶自由訪問Web數據庫中的數據，給信息檢索帶來飛躍的提升。

[1] Bergman M K. White paper: The deep web: Surfacing hidden value[J/OL]. Journal of electronic publishing, 2001, 7(1)[2001-09-24]. http://dx.doi.org/10.3998/3336451.0007.104.

[2] 中商情報網. 2013-2014年中國互聯網產業發展研究年度總報告[EB/OL]. [2014-03-03]. http://www.askci.com.

[3] 劉偉, 孟小峰. Deep Web 數據集成問題研究 [R]. 北京：WAMDM, 2006.

[4] 袁柳, 李戰懷, 陳世亮. 基于本體的 Deep Web 數據標注[J]. 軟件學報，2008， 19(2): 237-245.

[5] LIN Ling, ZHOU Lizhu. Web database schema identification through simple query interface[M]//LACROIX Z. RED 2009. Berlin/ Heidelberg: Springer·Verlag，2010,6162: 18-34.

[6] DOU D, MCDERMOTT D V, QI P. Ontology and translation on the semantic Web[M]//SPACCAPIETRA S. Journal on Data Semantics II. Berlin/ Heidelberg: Springer·Verlag，2004，3360: 35-57.

[7] ROITMAN H, GAL A. OntoBuilder: Fully automatic extraction and consolidation of ontologies from Web sources using sequence semantics[M]//GRUST T, et al. Current trends in database technology-EDBT 2006. EDBT 2006. Lecture Notes in Computer Science. Berlin/ Heidelberg: Springer, 2006,4254:573-576.

[8] 黃黎. 基于知識模型推理的 Deep Web 數據源分類研究[D]. 蘇州：蘇州大學, 2009.

[9] 牟曉偉. Deep Web 數據源發現與分類技術研究[D]. 長春：長春工業大學, 2015.

[10]蘇曉珂, 張勇敢, 黃青松. Deep Web 查詢接口的復雜模式匹配[J]. 石河子大學學報( 自然科學版), 2007, 25(1): 122-124.

[11]龔桂芬. 基于查詢接口的 Deep Web 模式匹配方法研究[D]. 蘇州：蘇州大學, 2011.