姚曉鵬　高圣興　薛君志　陸敏超

1(上海申騰信息技術(shù)有限公司　上海 200040)2(上海市計算技術(shù)研究所　上海 200040)3(浙江工商大學統(tǒng)計與數(shù)學學院　浙江 杭州 310018)

0　引　言

深網(wǎng)是相對于表層網(wǎng)絡(luò)而言的，不能被傳統(tǒng)的搜索引擎索引到信息資源的，指的是互聯(lián)網(wǎng)中可訪問的在線數(shù)據(jù)庫。其內(nèi)容存儲在真正的數(shù)據(jù)庫中，但這些內(nèi)容只有在遞交查詢后才會由Web服務(wù)器動態(tài)生成頁面把結(jié)果返回給訪問者的網(wǎng)站。

深網(wǎng)的研究目前主要分為兩個方面：(1) 深網(wǎng)的規(guī)模、分布和結(jié)構(gòu)的研究。美國Bright Planet公司，專門從事數(shù)據(jù)整合和企業(yè)信息分析，開發(fā)了深網(wǎng)檢索平臺工具DQM。此外，還對深網(wǎng)的規(guī)模和相關(guān)性進行了研究，并發(fā)布了調(diào)查白皮書。(2) 深網(wǎng)信息搜索中的關(guān)鍵技術(shù)的研究。目前主要的關(guān)鍵技術(shù)有Deep Web接口識別方法、信息提取算法、數(shù)據(jù)庫選擇算法、Deep Web集成查詢接口生成方法等。

而深網(wǎng)的信息資源具有以下三個特點：(1) 信息資源量巨大。深網(wǎng)是Internet中信息最快的增長點，并且隨著時間的推移，深網(wǎng)的信息量會越來越大。(2) 信息質(zhì)量高。它與表層的一般網(wǎng)頁相比，深網(wǎng)的內(nèi)容都更加的專業(yè)和有深度，信息間的相關(guān)度也比較高，具有巨大的商業(yè)價值和潛在信息。(3) 信息便于處理。深網(wǎng)的信息多數(shù)容易使用一些統(tǒng)計軟件處理，格式相對整齊。因此解析深網(wǎng)主要功能并研究其關(guān)鍵技術(shù)，從而采集深網(wǎng)的巨大信息資源，具有重要意義。

在深網(wǎng)的信息數(shù)據(jù)搜索中，用戶可以按照自己的需求進行搜索，網(wǎng)絡(luò)服務(wù)器將會自動檢索后臺數(shù)據(jù)庫，生成滿足條件的結(jié)果頁面。該頁面通常包含一個或幾個數(shù)據(jù)區(qū)，每個數(shù)據(jù)區(qū)又包括若干數(shù)據(jù)記錄，而這是一般的搜索引擎所做不到的。

如果能從結(jié)果頁面中抽取出數(shù)據(jù)，進而通過數(shù)據(jù)挖掘發(fā)現(xiàn)其潛在的關(guān)聯(lián)并整合，則可以為用戶提供寶貴的信息。

由于從深網(wǎng)上搜索得到的數(shù)據(jù)是動態(tài)的，并不能被直接利用，所以必須把數(shù)據(jù)抽取到本地?；谏鲜鰡栴}，可建立一個包含各個概念的全局模式，并且搜索的屬性與全局模式的概念一一對應(yīng)。然后根據(jù)用戶的需求動態(tài)地生成全局模式，從而有效地抽取用戶所需的信息。最后進行數(shù)據(jù)挖掘，整合數(shù)據(jù)項，得到有效的數(shù)據(jù)集，避免冗余。

1　深網(wǎng)數(shù)據(jù)抽取方法研究

深網(wǎng)在本質(zhì)上與一般的網(wǎng)絡(luò)不一樣，從深網(wǎng)中抽取數(shù)據(jù)有以下幾個制約因素：(1) 技術(shù)因素。深網(wǎng)多以數(shù)據(jù)庫的形式貯存信息，根據(jù)用戶的需求來動態(tài)的返回和庫入口處設(shè)置的賬號密碼是一般搜索方法無法搜索的主要原因。(2) 利益因素。由于利益關(guān)系，一般的搜索引擎為了節(jié)約成本和時間，只對相對集中的網(wǎng)頁進行搜索，而不會對每個網(wǎng)頁進行深度搜索。(3) 法律因素。許多網(wǎng)站為了保護用戶的隱私，設(shè)置成只對該網(wǎng)站的注冊用戶開放，因此使得一般的搜索引擎難以搜到相關(guān)的數(shù)據(jù)。

目前來看，從深網(wǎng)頁面中抽取數(shù)據(jù)的方法主要有以下幾種：(1) 手動抽取法。由工作人員根據(jù)網(wǎng)站屬性一步步分類進去抽取。抽取規(guī)則由人工定義，時間比較久。(2) 封裝器歸納法。一種由歸納式學習方法自動構(gòu)造封裝器的技術(shù)。用戶在網(wǎng)站中標記出需要抽取的數(shù)據(jù)，再在這些例子上歸納出基于界定符的抽取規(guī)則。這是一種基于實例的方法，通過比較每一個新實例，抽取數(shù)據(jù)記錄。(3) 自動抽取法?，F(xiàn)在許多商用系統(tǒng)采用基于HTML的數(shù)據(jù)抽取方法。通過比較相似的網(wǎng)頁歸納出使用正則表達式描述的網(wǎng)頁模板，而該模板就是抽取規(guī)則。表1為上述3種網(wǎng)頁數(shù)據(jù)抽取方法比較。

表1　數(shù)據(jù)抽取方法比較

在表1所示的幾種數(shù)據(jù)抽取技術(shù)中，可以看出，性能較好的效率低(如手動方法，雖然準確率高，但是耗時很久，不適合目前信息量劇增的深網(wǎng))，而效率高的準確率和實用性又較差或是難以定義規(guī)則。故本文提出了一種新的全局模式下的深網(wǎng)數(shù)據(jù)抽取與挖掘方法。整體數(shù)據(jù)抽取流程分為兩個模塊：(1) 全局模式的生成。(2) 通過全局模式來進行數(shù)據(jù)抽取。圖1是數(shù)據(jù)抽取的流程圖。

圖1　全局模式下的數(shù)據(jù)抽取流程圖

如圖1所示，首先通過觀察實體模型(實際例子)得到一個全局模式，再將全局模式的實體做成數(shù)據(jù)庫表以便于數(shù)據(jù)的存儲。而數(shù)據(jù)抽取模塊也包含了兩個部分內(nèi)容：數(shù)據(jù)的挖掘、抽取和識別數(shù)據(jù)記錄。

此外，對于一個網(wǎng)頁尤其是未知的網(wǎng)頁，還需考慮如何確保創(chuàng)建出全局模式。因此，在創(chuàng)建全局模式前，采用改進之后的貝葉斯信念網(wǎng)絡(luò)對整個網(wǎng)頁預(yù)先抽取重要的屬性，再根據(jù)相應(yīng)屬性創(chuàng)建全局模式。

2　全局模式

2.1　改進貝葉斯信念網(wǎng)絡(luò)

全局模式創(chuàng)建的好壞直接影響到最終的數(shù)據(jù)抽取的效果，而其中屬性的數(shù)量又非常重要，過少的屬性容易造成信息的不完整，會使得有用信息的丟失；而過多的屬性，則會收集太多無意義的信息，造成冗余。因此可以運用貝葉斯信念網(wǎng)絡(luò)的思路，對其進行改進，然后預(yù)先對網(wǎng)頁抽取出重要的屬性或概念，以確保做到全局模式。

首先，貝葉斯公式：

(1)

式中：X,Y是一對隨機變量。

式(1)定理允許我們使用先驗概率、類條件概率和證據(jù)概率來表示后驗概率。

貝葉斯信念網(wǎng)絡(luò)是聯(lián)合概率分布，它提供一種因果關(guān)系的結(jié)構(gòu)，并可以在此基礎(chǔ)上進行學習。如果其網(wǎng)絡(luò)結(jié)構(gòu)和所有數(shù)值都是給定的，那可以直接進行計算。但如果數(shù)據(jù)是隱藏的，只是知道存在這樣的依存關(guān)系，此時就需要進行條件概率的估算。

我們知道一個網(wǎng)頁上會有許許多多的屬性或概念，有許多屬性之間相互存在關(guān)聯(lián)，而且有的屬性是出現(xiàn)頻率較高，因此可以改進貝葉斯網(wǎng)絡(luò)算出其概率。以下是改進貝葉斯信念網(wǎng)絡(luò)的算法：

{(C1，C2,…,Cd)代表所有變量}

forj=1 toddo

令CG(j)表示G中第j個次序最高的變量；

令π(CG(j))={CG(1),…,CG(j-1)}是排在CG(j)前面的變量的集合；

從π(CG(j))中去除對Cj沒有影響的變量(使用先驗知識)；

再計算概率公式，得出第j個變量的概率P(Cj)，并以此抽取出作為全局模式的變量。

end for

然后根據(jù)

(2)

計算出最小支持概率Pmin。若所有變量相互間均沒有任何聯(lián)系影響，該值為0。

依據(jù)上述算法所得結(jié)果，保留相互聯(lián)系緊密，即概率大于Pmin的屬性變量，記為G= {(C1,C2,…,Ci,…,Cn}。然后我們從G中選取那些是先驗概率的變量作為查詢的屬性，記為Q={A1,A2,…,Ai,…,An}。

2.2　全局模式的創(chuàng)建

通過上述方法預(yù)處理之后，我們還為每個實體的屬性設(shè)置一定的權(quán)限，使得用戶可以根據(jù)自身的需求，動態(tài)地實時生成全局模式。比如全局模式的屬性個數(shù)并不固定，在通過算法得出相應(yīng)的屬性變量后，用戶仍然可以根據(jù)自己需求人為的添加其他屬性。

創(chuàng)建全局模式的過程如圖2所示。

圖2　創(chuàng)建全局模式流程圖

從圖2中可以看出，先要初始化4個集合L、I、P、M，令它們都為空。再創(chuàng)建一個查詢集合，把輸入的屬性放入集合L中，把查詢集里的元素放入輸入屬性中。接著把實體E放入集合I中。然后把所有相同屬性的數(shù)據(jù)放入L中，并記錄。依次重復(fù)上述步驟，直到得到一個全局模式。

其中,實體E={Et,(t1,v1),(t2,v2),…,(ti,vi),…,(tn,vn)}，其中Et是實體類型，ti和vi分別表示第i個屬性的類型和值。

實體模型M={Et,L1,L2,…,Li,…,Ln}，其中Et實體類型，Li是對應(yīng)每一類型屬性的一組標簽。

全局變量G={(C1,C2,…,Ci,…,Cn}，其中Ci是全局模式的概念；Q={A1,A2,…,Ai,…,An}，其中Ai是查詢接口待輸入的屬性。

輸入屬性Ai=(Ni,T)，其中Ni是輸入屬性Ai的名稱，T是Ai的數(shù)據(jù)類型。G和Q的映射關(guān)系f(C,A)。

結(jié)果模式R={(C1,P1),(C2,P2),…,(Ci,Pi),…,(Cn,Pn)}，其中Ci是G的屬性。

3　數(shù)據(jù)抽取與數(shù)據(jù)挖掘

3.1　數(shù)據(jù)抽取

在抽取數(shù)據(jù)之前，首先要對文檔進行適當?shù)恼?，比如剔除無效的頁面，通過使用jTidy工具對不標準的文檔進行初步修正，確保其符合W3C DOM規(guī)范。接著創(chuàng)建HTML Dom樹,其中包括：HTML標簽，屬性和文本。網(wǎng)頁由標簽樹T表示，t是樹T的根節(jié)點，Sub(t)表示一個樹的子樹。

因為結(jié)果頁面一般是基于模板自動生成的，并且一個結(jié)果頁面包含若干個相互獨立的數(shù)據(jù)塊。所以一個網(wǎng)頁的抽取模式是相對固定的，只要創(chuàng)建了一個網(wǎng)頁的抽取模式，其他網(wǎng)頁就可以采取相同抽取模式。若現(xiàn)存的全局模式無法抽取到所需數(shù)據(jù)，則需生成新的模式。圖3是數(shù)據(jù)抽取算法的整體流程。

圖3中，以提取的結(jié)果模式的數(shù)量變化作為標志，若數(shù)量減少則說明已提取到所需的數(shù)據(jù)，則產(chǎn)生結(jié)果頁面，并停止抽??；反之，說明還沒有完全提取數(shù)據(jù)，則繼續(xù)提取。

通過全局模式抽取的數(shù)據(jù)，還需要進行數(shù)據(jù)的識別。我們首先從結(jié)果頁面的標簽，把概率值最高的作為第一個已知屬性，再運用改進多重比較法判斷，并將結(jié)果頁面的全部屬性分為已知和未知的屬性。

(3)

式中：ni,nj分別為第i、j個屬性，Yi,Yj分別為第i、j個屬性的概率，Sp為兩個屬性的標準差。若n1為已知屬性，與n2去比較，若所求得的Q小于0.9，則n2為未知屬性；反之n2為已知屬性。然后對所有結(jié)果頁面的屬性進行比較，即可將結(jié)果頁面的屬性分為已知和未知的屬性。

3.2　數(shù)據(jù)挖掘

通過全局模式直接抽取得到的數(shù)據(jù)中包含了許多無用、重復(fù)的信息，因此還要進行數(shù)據(jù)挖掘。

首先，遍歷整個HTML Dom樹找到之前輸入的屬性的關(guān)鍵詞所在的節(jié)點，然后根據(jù)節(jié)點的特征，判斷該節(jié)點是否有效。比如樹的深度很小，那么該節(jié)點就很有可能是無效的；若節(jié)點附近的區(qū)域數(shù)據(jù)量較小，那么該節(jié)點也可能是無效的。

在剩余的節(jié)點中，再根據(jù)基于密度的離群點來檢測并剔除其中的無效信息。

基于密度的離群點指的是一個對象的離群點得分是該對象周圍密度的逆，其逆距離表達式為：

(4)

式中：N(x,k)是包含x的k-最近鄰的集合，|N(x,k)|是該集合的大小，而y是一個最近鄰。

基于密度的離群點檢測與基于鄰近度的離群點檢測密切相關(guān)，所以密度通常用鄰近度定義。

以下是基于密度的離群點的算法：

{k是最近鄰的個數(shù)}

需要標明的是，這一點極其重要，他在一定程度上回應(yīng)了上一個部分提出的必然性難題。對人類理性來說，因果性存在于時間序列當中，囿于這一點，自由意志才是與上帝預(yù)知相矛盾。實際上，神的領(lǐng)域在永恒當中，所以神意根本不像人一樣被限定在時間序列。既然“永恒當下”敉平了人類時間的三個向度——過去現(xiàn)在未來，那么因果序列在神意那里便完全失效。這也呼應(yīng)到前文對神意與命運關(guān)系的辨析，整個邏輯顯得十分縝密。

for all對象xdo

確定x的k-最近鄰N(x,k)

使用x的最近鄰(即N(x,k)中的對象)

確定x的密度density(x,k)

end for

for all 對象xdo

若結(jié)果大于1，則視為無效信息并剔除x

end for

接著用Fk-1×Fk-1方法進行關(guān)聯(lián)挖掘，用函數(shù)apriori-gen(挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法)候選過程合并一對頻繁(k-1)-項集的時候，所需要滿足條件——僅當它們的前k-2項集相同。

令A(yù)={a1,a2,…,ak-1}和B={b1,b2,…,bk-1}是一對頻繁集，若它們滿足：

ai=bi(i=1,2,…,k-2)且ak-1≠bk-1

則可合并A與B。

如果都是在最好的情況下，那么每一次合并都可以產(chǎn)生一個可行的候選k-項集；如果每一次都是最壞的情況下，則每一次都必須合并前一次迭代發(fā)現(xiàn)的每一對頻繁(k-1)-項集。

因此，合并頻繁項集的總開銷為：

(5)

所花費的時間是：

(6)

式中：w為頻繁項集總數(shù)，k等于樹的最大的深度。

最終，通過該方法合并所得到的數(shù)據(jù)內(nèi)部存在一定關(guān)聯(lián)，即結(jié)果滿足大于或等于最小置信度閾值(該值默認75%，也可以人為取值)，并且可以使得最后結(jié)果的數(shù)據(jù)項更加簡潔。

4　實驗驗證與結(jié)果

為了驗證該深網(wǎng)數(shù)據(jù)抽取與挖掘方法的實際效果，本文選取了多個網(wǎng)站作為實踐對象來驗證該方法的通用性。由于受限于篇幅，故這里僅以抽取http:// thebookery.com/網(wǎng)站的結(jié)果進行效果展示。

進入該網(wǎng)站，運用改進貝葉斯信念網(wǎng)絡(luò)的算法，計算出Pmin=0.3，得出查詢的屬性為4個：Author、Title、Keyword、ISBN，記為Q={A1,A2,A3,A4}，然后輸入相應(yīng)的查詢屬性，并獲得返回結(jié)果。

通過比較幾種不同的方法的時間、正確率等，得到的實驗結(jié)果如表2所示。

表2　數(shù)據(jù)抽取方法實驗對比

由表2可知，耗時從級別1到級別10，所用時間越來越多，尤其是手動方法需要幾小時甚至幾天才能全部收取數(shù)據(jù)，并且手動抽取方法因人而異，有的人正確率可以達到100%，而有的的卻低于80%，因此在實際抽取中不適用。全局模式抽取相對于自動抽取耗時更少。封裝器歸納法由于規(guī)則難以定義，使得抽取到的數(shù)據(jù)的正確率相對較低。因此全局模式下的數(shù)據(jù)抽取方法相對于其他方法最省時，正確率又相對較高。

接著，對抽取好之后的數(shù)據(jù)運用統(tǒng)計學關(guān)聯(lián)分析的方法進行數(shù)據(jù)關(guān)聯(lián)挖掘，并且取最小置信度閾值為75%，得到數(shù)據(jù)挖掘后的樹狀圖如圖4所示。

圖4　數(shù)據(jù)合并樹狀圖

由圖4可知，27項數(shù)據(jù)項經(jīng)過1次關(guān)聯(lián)挖掘后變成了7項數(shù)據(jù)項，大大簡化了原有的數(shù)據(jù)量，使得原有數(shù)據(jù)項中的無效信息減少。

5　結(jié)　語

深網(wǎng)中數(shù)據(jù)的抽取，不同于一般搜索引擎的搜索。本文提出了一種全局模式下的深網(wǎng)數(shù)據(jù)抽取和數(shù)據(jù)挖掘方法。該方法首先分析實際例子的屬性，運用改進貝葉斯信念網(wǎng)絡(luò)算法，確定相應(yīng)的屬性標簽，構(gòu)建一個動態(tài)的全局模式。接著抽取并識別結(jié)果頁面中的數(shù)據(jù)，根據(jù)基于密度的離群點來檢測并剔除其中的無用信息。最后運用挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法進行關(guān)聯(lián)挖掘，整合數(shù)據(jù)項。實驗結(jié)果表明：該方法相對于其他幾種數(shù)據(jù)抽取方法,可以快速、有效、正確地抽取數(shù)據(jù)，并且通過數(shù)據(jù)挖掘后的數(shù)據(jù)項更簡潔，無效信息更少。

[1] 范明,范宏建.數(shù)據(jù)挖掘?qū)д?完整版)[M].北京:人民郵電出版社,2011.

[2] 楊道玲.深網(wǎng)信息資源采集初探[J].圖書館雜志,2006,25(12):19-22.

[3] 束長波,施化吉.基于動態(tài)數(shù)據(jù)源的DeepWeb信息集成框架研究[J].無線通信技術(shù),2015,24(1):48-52.

[4] 張忠占,傅鶯鶯.統(tǒng)計推斷(翻譯版)[M].北京:機械工業(yè)出版社,2010.

[5] 何廣達.DeepWeb查詢表單屬性模式匹配的研究[J].數(shù)字技術(shù)與應(yīng)用,2015(6):104-104.

[6] 顧韻華,高原,高寶,等.基于模板和領(lǐng)域本體的Deep Web信息抽取研究[J].計算機工程與設(shè)計,2014,35(1):327-332.

[7] 杰夫·霍金斯.智能時代[M].北京:中信出版社,2015.

[8] 王喜平,于國槐,宋晶.ASP.NET程序開發(fā)范例寶典[M].北京:人民郵電出版社,2015.

[9] Ozsu M T,Valduriez P.分布式數(shù)據(jù)庫系統(tǒng)原理[M].周立柱,范舉,吳昊,等譯.北京:清華大學出版社,2015.

[10] Wang Qiuyue,Cao Wei,Shi Shaochen.Deep Web resource selection using topic model[J].Journal of Computer Applications,2015,35(9):2553-2559.

[11] Saissi Y,Zellou A,Idri A.Extraction of relational schema from deep web sources:a form driven approach[C]//2014 Second World Conference on Complex Systems (WCCS).IEEE,2015:178-182.

[12] Barrio P,Gravano L,Develder C.Ranking Deep Web Text Collections for Scalable Information Extraction[C]//ACM International on Conference on Information and Knowledge Management.ACM,2015:153-162.

[13] Witten I H,Frank E.Data Mining:Pratical Machine Learning Tools and Techniques[J].Acm Sigmod Record,2005,31(1):76-77.