王 龍 陳曉雷 李曉光 宋寶燕

(遼寧大學信息學院 沈陽 110036)

?

自適應Web頁面數據抽取方法*

王 龍 陳曉雷 李曉光 宋寶燕

(遼寧大學信息學院 沈陽 110036)

針對Web頁面數據抽取問題,提出了一種基于抽取模板的自適應Web頁面數據抽取方法。給出了自適應web數據抽取的整體流程,詳細介紹了抽取模板中抽取規(guī)則和自適應搜索規(guī)則的定義方式,web頁面與抽取模板的匹配方法,以及抽取路徑失效后目標數據的搜索與抽取模板的自適應修改過程。實驗結果表明,基于抽取模板的自適應web頁面數據抽取方法的召回率和查準率都達到95%以上,方法中的自適應搜索規(guī)則有效地減少了抽取模板的制定數量。

自適應; 數據抽取; Web數據; 抽取模板; 匹配度

Class Number TP391.1

1 引言

Web數據抽取是Web數據挖掘工作中的一步重要的過程[1]。Web數據抽取就是將Web頁面上半結構化的數據按照一定的方法抽取出來,保存為結構化格式,如保存為XML文件或者存儲到數據庫中等[2～3]。傳統的Web數據抽取方法大多是針對某一類特定信息源的數據抽取,主要由一系列預先定義的抽取規(guī)則以及這些規(guī)則的執(zhí)行代碼組成,并沒有充分利用頁面數據的結構特征,且對頁面的結構有一定要求,若頁面結構是動態(tài)變化的便不能很準確的進行數據抽取,導致數據抽取失敗。

Web數據抽取技術可分為基于頁面DOM結構的數據抽取技術[4～9]、基于統計理論的數據抽取技術[10～12]和基于頁面視覺特征的數據抽取技術[13～15]。其中基于頁面DOM結構的數據抽取技術應用最為廣泛。

當前基于頁面DOM結構的研究大多集中在對特定的頁面進行推導,根據某類網頁特征生成樹中的數據對象的對應實例路徑,在網頁結構發(fā)生變化時無法自適應,即使發(fā)生的變化很小,仍然需要進行人工分析與修改。為減少人工干預,本文提出一種基于抽取模板的自適應Web頁面數據抽取方法。文中首先給出自適應Web數據抽取的整體流程,然后設計了一種基于模板的自適應數據抽取方法,最后進行了實驗討論與分析。

2 自適應Web數據抽取整體流程

基于模板的自適應數據抽取過程主要分為五個階段,分別為：初始準備階段、模板準備階段、模板匹配階段、數據抽取階段和自適應修改階段。根據待抽取頁面的性質不同,抽取過程可能含全部五個階段,也可能只包含其中的一部分,具體過程如圖1所示。

圖1 自適應數據抽取整體流程

自適應Web數據抽取方法的整體步驟如下：

Step1：抓取Web頁面HTML源代碼,規(guī)范化,并構建網頁DOM樹；

Step2：提取頁面URL,與抽取模板庫中的模板進行匹配,如果匹配成功,則按照匹配度由高到低的順序依次根據抽取模板中的抽取規(guī)則抽取目標數據,直到目標數據抽取成功。如果匹配不成功則制定新的抽取模板；

Step3：如果不存在目標數據抽取全部成功的模板,則提取錯誤項最少的模板進行自適應修改；

Step4：根據模板中的搜索規(guī)則按自底向上的順序計算DOM樹中節(jié)點的評價值；

Step5：如果遇到評價值大于搜索閾值的節(jié)點,則搜索成功,將節(jié)點數據作為目標數據,并將節(jié)點的XPath表達式加入模板對應數據項的XPath隊列中；否則制定新的抽取模板。

3 基于模板的自適應數據抽取方法

3.1 抽取模板定義

網頁數據抽取模板主要由地址塊和數據塊兩部分組成,數據塊中每條數據的定義除了包含數據的抽取規(guī)則以外,還包含了自適應修改規(guī)則,數據抽取模板的詳細信息如圖2所示。

圖2 網頁數據抽取模板

其中,〈site〉表示數據抽取的網站,〈url〉表示數據抽取的頁面網址,〈data〉表示需要抽取的數據,由多個〈node〉標簽構成?！磏ode〉標簽中,〈nodeId〉表示抽取數據的標識,〈title〉表示抽取數據的含義,〈xpaths〉表示需要抽取的頁面數據的XPath路徑表達式集合,〈rule〉表示數據搜索規(guī)則?！磖ule〉標簽中,〈keyword〉表示關鍵字規(guī)則；〈tag〉表示Html標簽規(guī)則；〈context〉表示上下文規(guī)則,包含〈content〉和〈distance〉兩個標簽,分別為上下文內容和與當前節(jié)點的距離；〈font〉包含〈color〉和〈size〉兩個標簽,分別為字體顏色和字體大小。

3.2 模板匹配

網站下的同類頁面通常是基于同一網頁模板生成,在外觀、內容布局和樣式結構上都非常相似,其特點是它們的DOM樹主干結構是相同的,只是葉子節(jié)點的填充數據不同。使用現有的判斷頁面相似性的算法效率較低,而且需要保存大量樣本。通過觀察發(fā)現,頁面相似的網頁,其url路徑也是相似的,因此本文通過計算待抽取網頁的url與抽取模板中的〈url〉標簽數據的相似程度來獲得待抽取網頁與抽取模板的匹配度,匹配度R(w,m)可定義為

其中w為待抽取網頁,m為抽取模板,urlw為待抽取網頁的url地址,urlm為抽取模板中〈url〉標簽的數據,S(url)表示將對應url以“/”分隔開的字符串集合,|S(urlw)∩S(urlm)|表示urlw和urlm中相同部分的字符串長度,|min(S(urlw),S(urlm))|表示urlw和urlm中較小的集合的長度。當待抽取網頁的url的域名與抽取模板中的〈site〉標簽數據相同,并且匹配度大于指定閾值t,即R(w,m)>t時,待抽取網頁與抽取模板匹配成功。

3.3 數據搜索規(guī)則

由于XPath路徑表達式對頁面結構的變化比較敏感,在頁面結構發(fā)生變化后,應用原有的XPath無法繼續(xù)抽取數據,針對這種情況,根據頁面目標數據的特征制定搜索規(guī)則。當頁面結構發(fā)生變化導致原XPath表達式無法抽取目標數據時,程序自動應用這些規(guī)則搜索目標數據,再根據目標數據生成XPath表達式加入原XPath隊列中,從而達到自適應Web頁面結構變化,減少人工干預的目的。

1) 關鍵字搜索規(guī)則

如果目標數據對應的文本信息在Web頁面中是惟一的,則在模板中的相應〈keyword〉標簽中加入該文本信息,作為關鍵字規(guī)則。例如要抽取電子商務網站中商品分類頁面中的“家用電器”類的URL信息,則可將“家用電器”作為該目標數據的關鍵字搜索規(guī)則。關鍵字相關度dkey(ntxt,mkey)可定義為：

其中ntxt為DOM樹中節(jié)點數據對應的文本信息,mkey為模板中對應的〈keyword〉標簽的值。

2) HTML標簽搜索規(guī)則

如果目標數據對應的HTML標簽信息在Web頁面中是特殊的,則在模板中的相應〈tag〉標簽中加入該HTML標簽信息,作為HTML標簽規(guī)則。例如要抽取新聞正文類頁面中的新聞標題信息,新聞標題信息在〈h1〉標簽中,則可將〈h1〉作為該目標數據的HTML標簽搜索規(guī)則。HTML標簽相關度dtag(ntag,mtag)可定義為：

其中ntag為DOM樹中節(jié)點數據對應的HTML標簽信息,|ntag|為ntag在DOM樹中出現的次數,mtag為模板中對應的〈tag〉標簽的值。

3) 上下文搜索規(guī)則

上下文表示頁面中目標數據附近的固定信息。根據Web頁面的視覺特征可以發(fā)現網頁中的信息根據語義分塊,語義相近的信息在頁面的視覺上距離較近。如果要抽取的數據不容易搜索,但它有容易搜索的上下文,那么對目標數據的搜索可以轉化為對其上下文的搜索。找到其上下文后,根據上下文的位置定位目標數據。例如文章的標題在作者、發(fā)表時間和正文等信息的上方,由于標題具有比較突出的特征,定位標題的位置后,根據標題的位置再尋找作者、發(fā)表時間等數據；商品價格的前面一般有“價格”兩個字,定位價格標簽,那么其后含有符合價格模式的字符串可認為是商品價格。設上下文數據與目標數據之間的同級及上級標簽數量為兩者之間的“距離”,若上下文數據在目標數據之前,“距離”為正值,否則為負值。上下文相關度可定義為

其中ndist為DOM樹中節(jié)點數據與對應上下文之間的距離,mdist為模板中對應的〈distance〉標簽的值。

4) 字體搜索規(guī)則

頁面中的某些數據為了吸引用戶注意,會在視覺特征上與其他數據加以區(qū)分,它們的字體顏色和字體大小跟普通文本有所區(qū)別。因此,在DOM樹的節(jié)點中按照字體的顏色和大小可以搜索目標數據。字體相關度可定義為

其中nfont,color為DOM樹中節(jié)點數據的字體顏色,mfont,color為模板中對應的〈color〉標簽的值,equal為判斷二者是否相同,相同返回1,否則返回0。nfont,size為DOM樹中節(jié)點數據的字體大小,mfont,size為模板中對應的〈size〉標簽的值。

根據以上規(guī)則,定義評價函數如下：

其中|dtag,dcont,dfont|表示dtag,dcont,dfont中值不為0的個數。當評價函數值大于搜索閾值時,搜索成功。

4 實驗分析

為了有效評估和分析本文方法在數據抽取上的性能,采用10個主流網站的300個主題型網頁作為實驗數據集。這些試驗網頁分屬于新聞類和論壇類。實驗結果如表1所示。

表1 性能測試結果

其中R為召回率、P為查準率,F為R和P的綜合效率[16]。

從表1中可以看出,對于所有數據集,基于本文提出的數據抽取方法的召回率、查準率和綜合效率始終保持在93%以上,平均分別達到95.76%、95.14%和95.11%。實驗結果表明,本文提出的方法具有較高的召回率、查準率和綜合效率,符合Web網頁數據抓取的實際需求。

為了測試本文方法的自適應能力,采用五個主流博客網站中的頁面作為實驗數據集。每個網站中的頁面由于采用的網頁模板不同,因此頁面的結構也不同,提取那些模板相似的網頁作為實驗數據,總共提取150個頁面。實驗結果如表2所示。

表2 自適應能力測試結果

從表2中可以看出,對于所有數據集,采用本文提出的自適應策略均能有效地降低制定模板的數量,減少人工干預,具有更高的適應性和智能性。

5 結語

本文提出一種基于模板的自適應Web頁面數據抽取方法。在制定抽取模板時不僅定義相應的抽取規(guī)則,而且根據頁面數據的文本特征、HTML標簽特征、上下文特征和視覺特征定義自適應搜索規(guī)則。Web頁面通過url相似性與模板進行匹配,匹配成功后按照抽取規(guī)則進行數據抽取。如果頁面發(fā)生變化,XPath表達式失效,則根據自適應搜索規(guī)則重新搜索數據,并更新XPath。實驗結果表明該方法具有較高的效率,并且有效地減少了抽取過程中的人工干預。

[1] Appelt D E. Introduction to information extraction[J]. Ai Communications, 999,12(3):161-172.

[2] Knoblock C A, Lerman K, Minton S, et al. Accurately and reliably extracting data from the web: A machine learning approach[J]. Intelligent exploration of the web. Physica-Verlag HD,2003,111:275-287.

[3] Broder A Z, Glassman S C, Manasse M S, et al. Syntactic clustering of the web[J]. Computer Networks and ISDN Systems,1997,29(8):1157-1166.

[4] Liu, Ling, Calton Pu, and Wei Han. XWRAP: An XML-enabled wrapper construction system for web information sources[C]//Proceedings of the 16th International Conference on Data Engineering. IEEE,2000:611-621.

[5] Liu, Bing, Robert Grossman, and Yanhong Zhai. Mining data records in Web pages[C]//Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2003:601-606.

[6] Zhai, Yanhong, and Bing Liu. Web data extraction based on partial tree alignment[C]//Proceedings of the 14th international conference on World Wide Web. ACM,2005.

[7] Crescenzi, Valter, Giansalvatore Mecca, Paolo Merialdo. Roadrunner: Towards automatic data extraction from large web sites[J]. VLDB,2001:109-118.

[8] Arasu, Arvind, and Hector Garcia-Molina. Extracting structured data from web pages[C]//Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM,2003:337-348.

[9] Gupta S, Kaiser G, Neistadt D, et al. DOM-based content extraction of HTML documents[C]//Proceedings of the 12th international conference on World Wide Web. ACM,2003:207-214.

[10] 孫承杰,關毅.基于統計的網頁正文信息抽取方法的研究[J].中文信息學報,2004,18(5):17-22. SUN Chengjie, GUAN Yi. A Statistical Approach for Content Extraction from Web Page[J]. Journal of Chinese Information Processing,2004,18(5):17-22.

[11] Song M, Wu X. Content extraction from web pages based on Chinese punctuation number[C]//Proceedings of the International Conference on Wireless Communications, Networking and Mobile Computing. IEEE,2007:5573-5575.

[12] 周佳穎,朱珍民,高曉芳.基于統計與正文特征的中文網頁正文抽取研究[J].中文信息學報,2009,23(5):80-86. ZHOU Jiaying, ZHU Zhenmin, GAO Xiaofang. Research on Content Extraction from Chinese Web Page Based on Statistic and Content-Features[J]. Journal of Chinese Information Processing,2009,23(5):80-86.

[13] Cai D, Yu S, Wen J R, et al. VIPS: a Vision-Based Page Segmentation Algorithm[R]. Microsoft technical report, MSR-TR-2003-79,2003.

[14] Liu W, Meng X, Meng W. Vide: A vision-based approach for deep web data extraction[J]. Knowledge and Data Engineering, IEEE Transactions on,2010,22(3):447-460.

[15] Cai D, Yu S, Wen J R, et al. Extracting content structure for web pages based on visual representation[C]//Web Technologies and Applications, Asian-pacific Web Conference, Xi’an,2003:406-417.

[16] Laender A H F,Ribeiro- Neto B A,Da Silva A S,et al.A Brief Survey of Web Data Extraction Tools[J].SIGMOD Record,2002,31(1):84.

Adaptive Web Data Extraction Method

WANG Long CHEN Xiaolei LI Xiaoguang SONG Baoyan

(School of Information, Liaoning University, Shenyang 110036)

According to the web page extraction, an adaptive web data extraction method based on extraction template was proposed. The adaptive web extraction process was given. The extraction rules and the adaptive search rules were defined, the matching method of the web page and the extraction template was presented, and the process of target data search and extraction template adaptive repair was described in details. Experimental results showed that the recall rate and precision rate were more than 95%, and the method can effectively reduce the quantity of extraction templates.

adaptive, data extraction, Web data, extarction template, matching degree

2016年5月3日,

2016年6月27日

國家自然科學基金(編號：61472169)；遼寧省科學技術基金(編號：20141049)；遼寧大學博士啟動基金資助。作者簡介:王龍，男，博士，講師，研究方向：機器學習，數據挖掘，大數據管理，圖數據管理技術等。陳曉雷，男，碩士研究生，研究方向：機器學習，數據挖掘等。李曉光，男，博士，教授，研究方向：數據庫技術，數據挖掘，大數據管理，圖數據管理技術等。宋寶燕，女，博士，教授，研究方向：數據庫技術，大數據管理，圖數據管理技術等。

TP391.1

10.3969/j.issn.1672-9722.2016.11.022