全局模式下的深網數據抽取與挖掘

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

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

0　引　言

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

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

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

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

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

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

1　深網數據抽取方法研究

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

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

表1　數據抽取方法比較

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

圖1　全局模式下的數據抽取流程圖

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

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

2　全局模式

2.1　改進貝葉斯信念網絡

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

首先，貝葉斯公式：

(1)

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

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

貝葉斯信念網絡是聯合概率分布，它提供一種因果關系的結構，并可以在此基礎上進行學習。如果其網絡結構和所有數值都是給定的，那可以直接進行計算。但如果數據是隱藏的，只是知道存在這樣的依存關系，此時就需要進行條件概率的估算。

我們知道一個網頁上會有許許多多的屬性或概念，有許多屬性之間相互存在關聯，而且有的屬性是出現頻率較高，因此可以改進貝葉斯網絡算出其概率。以下是改進貝葉斯信念網絡的算法：

{(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

然后根據

(2)

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

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

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

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

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

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

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

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

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

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

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

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

3　數據抽取與數據挖掘

3.1　數據抽取

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

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

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

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

(3)

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

3.2　數據挖掘

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

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

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

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

(4)

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

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

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

{k是最近鄰的個數}

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

for all對象xdo

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

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

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

end for

for all 對象xdo

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

end for

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

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

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

則可合并A與B。

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

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

(5)

所花費的時間是：

(6)

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

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

4　實驗驗證與結果

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

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

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

表2　數據抽取方法實驗對比

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

接著，對抽取好之后的數據運用統計學關聯分析的方法進行數據關聯挖掘，并且取最小置信度閾值為75%，得到數據挖掘后的樹狀圖如圖4所示。

圖4　數據合并樹狀圖

由圖4可知，27項數據項經過1次關聯挖掘后變成了7項數據項，大大簡化了原有的數據量，使得原有數據項中的無效信息減少。

5　結　語

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

[1] 范明,范宏建.數據挖掘導論(完整版)[M].北京:人民郵電出版社,2011.

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

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

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

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

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

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

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

[9] Ozsu M T,Valduriez P.分布式數據庫系統原理[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.