自適應(yīng)Web頁面數(shù)據(jù)抽取方法*

王 龍 陳曉雷 李曉光 宋寶燕

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

?

自適應(yīng)Web頁面數(shù)據(jù)抽取方法*

王 龍 陳曉雷 李曉光 宋寶燕

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

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

自適應(yīng); 數(shù)據(jù)抽取; Web數(shù)據(jù); 抽取模板; 匹配度

Class Number TP391.1

1 引言

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

Web數(shù)據(jù)抽取技術(shù)可分為基于頁面DOM結(jié)構(gòu)的數(shù)據(jù)抽取技術(shù)[4～9]、基于統(tǒng)計理論的數(shù)據(jù)抽取技術(shù)[10～12]和基于頁面視覺特征的數(shù)據(jù)抽取技術(shù)[13～15]。其中基于頁面DOM結(jié)構(gòu)的數(shù)據(jù)抽取技術(shù)應(yīng)用最為廣泛。

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

2 自適應(yīng)Web數(shù)據(jù)抽取整體流程

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

圖1 自適應(yīng)數(shù)據(jù)抽取整體流程

自適應(yīng)Web數(shù)據(jù)抽取方法的整體步驟如下：

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

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

Step3：如果不存在目標(biāo)數(shù)據(jù)抽取全部成功的模板,則提取錯誤項最少的模板進(jìn)行自適應(yīng)修改；

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

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

3 基于模板的自適應(yīng)數(shù)據(jù)抽取方法

3.1 抽取模板定義

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

圖2 網(wǎng)頁數(shù)據(jù)抽取模板

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

3.2 模板匹配

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

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

3.3 數(shù)據(jù)搜索規(guī)則

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

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

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

其中ntxt為DOM樹中節(jié)點數(shù)據(jù)對應(yīng)的文本信息,mkey為模板中對應(yīng)的〈keyword〉標(biāo)簽的值。

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

如果目標(biāo)數(shù)據(jù)對應(yīng)的HTML標(biāo)簽信息在Web頁面中是特殊的,則在模板中的相應(yīng)〈tag〉標(biāo)簽中加入該HTML標(biāo)簽信息,作為HTML標(biāo)簽規(guī)則。例如要抽取新聞?wù)念愴撁嬷械男侣剺?biāo)題信息,新聞標(biāo)題信息在〈h1〉標(biāo)簽中,則可將〈h1〉作為該目標(biāo)數(shù)據(jù)的HTML標(biāo)簽搜索規(guī)則。HTML標(biāo)簽相關(guān)度dtag(ntag,mtag)可定義為：

其中ntag為DOM樹中節(jié)點數(shù)據(jù)對應(yīng)的HTML標(biāo)簽信息,|ntag|為ntag在DOM樹中出現(xiàn)的次數(shù),mtag為模板中對應(yīng)的〈tag〉標(biāo)簽的值。

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

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

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

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

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

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

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

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

4 實驗分析

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

表1 性能測試結(jié)果

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

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

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

表2 自適應(yīng)能力測試結(jié)果

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

5 結(jié)語

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

[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] 孫承杰,關(guān)毅.基于統(tǒng)計的網(wǎng)頁正文信息抽取方法的研究[J].中文信息學(xué)報,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] 周佳穎,朱珍民,高曉芳.基于統(tǒng)計與正文特征的中文網(wǎng)頁正文抽取研究[J].中文信息學(xué)報,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日

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

TP391.1

10.3969/j.issn.1672-9722.2016.11.022