基于網頁聚類的正文信息提取方法

2018-03-28 06:33:14王一洲戴遠飛

小型微型計算機系統 2018年1期

王一洲,陳星,戴遠飛

1(福州大學數學與計算機科學學院,福州 350108) 2(福建省網格計算與智能信息處理重點實驗室,福州 350108)

1 引言

Web技術的迅猛發展,使得Web網頁成為信息發布的主要載體,因此,Web網頁正文內容的抽取成為了當前學術界的一個研究熱點.然而,在網頁內容抽取中存在兩個難點:第一,在一個Web頁面中除了包含用戶感興趣的正文外,還包含導航條、廣告、推薦鏈接、版權聲明等與主題無關的噪音信息.第二,由于動態腳本和CSS技術的廣泛應用,使得網頁之間的結構差異性不斷增大并且網頁自身結構的復雜性不斷提高.針對這兩個難點,人們提出基于統計的網頁正文提取和基于網頁分割的網頁正文提取,然而,當正文內容字符數較少且噪音信息過長的情況下,網頁正文內容的提取可能出錯.例如:在網頁中游客評論的信息過長,就會導致系統將評論誤認為正文內容.

實際上,HTML頁面是存儲在后臺數據庫中的數據和HTML內容模板的結合體,在網站內部的網頁大多都是由一套相同的內容模板生成的,因此可以認為網頁的設計是有一定規律的.通過這個規律,本文提出一種新的基于網頁聚類的正文信息提取方法,用于抽取Web頁面中的正文內容.

本文的主要貢獻有兩點:

1)提出一種基于網頁的結構特征對網頁聚類的方法.

2)提出一種面向相似網頁集合的正文位置特征生成方法.

本文第2節簡要介紹相關的研究工作.第3節介紹基于網頁聚類的正文信息提取方法的框架.第4節提出基于結構特征的網頁聚類.第5節提出一種面向相似網頁集合的正文位置特征生成方法.第6節是實驗和分析部分.最后,第7節對本文工作進行總結和展望

2 相關工作

Web網頁正文信息提取技術隨著需求的增加而不斷豐富,近年來國內外涌現了多種方法.根據其原理可分為3類:基于統計的網頁正文提取、基于網頁分割的網頁正文提取和基于機器學習的網頁正文提取.

基于統計的網頁正文提取方法主要根據網頁中文本的分布情況來決定提取的內容.文獻[1]中作者先將Web頁面轉化為DOM樹,然后提取DOM樹中每一個節點的標簽路徑,基于路徑標簽,提出了6個特征,如文本標簽路徑長度特征,文本標簽路徑比特征等.通過將不同特征融合來得到綜合特征值,再利用綜合特征值來提取網頁中的新聞.文獻[2]則是一種完全脫離HTML標簽的正文內容提取方式,通過統計去除HTML標簽后網頁中各行塊的字符數,建立行塊分布圖,再由行塊分布圖直接定位網頁正文的位置.基于統計的網頁正文提取方法其缺陷在于當網頁中正文內容字符數較少時,其統計出來的數據就會導致選取錯誤的文本.

基于網頁分割的正文提取是根據網頁中的一些特征對網頁進行切割,再從切割后的各個塊中選取包含網頁正文的塊并提取網頁正文.文獻 [3,4]都是通過網頁分割來提取正文內容.文獻[3]則提出3個基本的節點密度特征,再利用節點密度特征計算節點密度熵,以節點密度熵為度量將DOM樹自動分割為若干個塊.最后,利用視覺特征[4]如:塊的大小,位置等信息對分割的塊進行分類,最后將頁面中的塊分為多種類型,方便進行內容提取.文獻[5],則是將Web網頁根據相應的規則分解成基本元素節點,將這些節點轉化為一張圖,通過基本元素節點之間的文本相似度比較和在網頁中的相對位置給圖中每兩個節點之間加權值,再利用類似谷歌PageRank的排序算法來處理加權圖選取包含正文內容的基本元素節點.基于網頁分割的正文提取其缺陷在于當網頁正文內容字符數較少,而噪音信息較多時,選取的塊可能出錯.

文獻[6]中提出了基于機器學習的網頁正文提取方法,文中將網頁內容的提取轉化為對DOM樹中節點的選擇,提取DOM樹中節點的多個特征,利用機器學習將這些特征作為輸入訓練出相應的模型,再通過模型選出包含有正文的候選節點.其缺陷在于需要大量的訓練樣本才能保證準確率.

本文吸收了基于統計的網頁正文提取方法和基于網頁分割的正文提取方法,在網頁聚類的基礎上解決了因為正文內容字符數較少,噪音信息較長的特殊情況導致網頁正文內容提取出錯的問題.

3 方法概覽

如圖1所示,基于網頁聚類的正文信息提取由3個模塊組成,分別是網頁解析模塊、基于結構特征的網頁聚類模塊和面向相似網頁集合的正文特征生成模塊.

基于結構特征的網頁聚類模塊:給定網頁對應的DOM樹,遍歷DOM樹提取網頁的結構特征.利用結構特征計算網頁之間的相似度.根據網頁之間的相似度對網頁集合進行分層聚類.最后生成一系列的標記類集合,以及每個標記類的網頁特征.

面向相似網頁集合的正文特征生成模塊:針對同一類網頁,對網頁進行切割分塊,統計各個塊的節點密度特征,尋找包含正文內容并且不包含噪聲信息的塊并提取該塊的特征作為該類網頁中正文內容塊的抽取規則.

圖1中,用戶需要輸入一個網站中多個頁面,通過網頁聚類模塊得到聚類結果中每個標記類網頁的結構特征.針對每個標記類提取其網頁正文內容塊的特征.當用戶輸入該網站的網頁時,會根據網頁的結構特征確定該網頁所屬的標記類,并利用該標記類網頁的正文內容塊特征來提取網頁中的正文內容.

圖1 基于網頁聚類的正文信息提取方法Fig.1 Webpage clustering based on structure feature

4 基于結構特征的網頁聚類

在相關工作中我們分析了基于統計的網頁正文提取的缺陷,當網頁正文內容的字符數較少時,基于統計的網頁正文提取就會失效.當然,在一個網站中絕大多數網頁中的正文內容的字符數是足夠用來判斷正文內容的位置,而網頁正文內容字符數較少導致判斷出錯的頁面是特殊情況.因此本文利用網頁聚類將正文內容所處位置相同(即網頁結構相同)的網頁放入同一個標記類中,通過對同一標記類中的網頁進行統一的正文內容提取操作來消除因為個別網頁中正文內容字符數較少引起的錯誤提取.

4.1 網頁結構特征的表示

為了方便表示網頁的結構特征,本文引入如下4個定義:

定義1.每一個Web頁面均可以表示成一個DOM樹Td,Td是一個有向圖,其中V為頂點的集合,V={v|v∈html 標簽集Tag}.E為有向邊的集合,E={|u,v∈V,其中u稱為v的父頂點,而v稱為u的子頂點,且在html結構上,v對應的標簽被u對應的標簽收包含}.

定義2.一顆DOM樹Td可表示為一個頁面塊的集合B={bi|bi∈V,且bi節點對應的html標簽為

或},稱該節點為塊節點.

定義3.Td是一顆以v0為根的DOM樹,對于任意的節點v∈V,vk0vk1…vkn是樹Td從vk到達vkn的節點序列,其中,parent(vkj-1)=vkj(1<=j<=n),vkj=v,則稱vk0vk1…vkn為節點v的路徑,記為p(v).如:“body1/div3/div2”為一個塊節點的路徑.

定義4.給定網頁w和對應DOM樹中所有塊節點的路徑集合f={p1,p2,…,pn|pi=p(bi),bi∈B},可表示為一個網頁特征F=.

為了能夠快速計算網頁之間的相似度,本文將DOM樹中各個塊節點的路徑作為網頁的結構特征[7].通過前序遍歷的方式遍歷網頁DOM樹Td,提取塊節點的路徑集合F.f,構成二元組F=來表示網頁w的結構特征.最后將輸入的網頁集合W轉化為網頁特征集合D={F1,F2,…,Fk}.

4.2 網頁聚類

通過上節網頁結構特征的表示,我們可以從網頁集合中提取出網頁的結構特征集合D={F1,F2,…,Fk}.根據網頁結構特征F,可以計算得到網頁之間的相似度.

定義5.給定有限集合A={x1,x2,…,xn},將有限集合A的元素個數記為card(A)=n.

本文定義了計算兩個頁面的相似度函數為:

(1)

其中Fi和Fj分別表示第i個網頁和第j個網頁的結構特征.為了方便算法表示本文給出了聚類結果后標記類特征的定義.

定義6.給定結構相似的網頁集合W={w1,w2,…,wn|sim(,)>0.82,05}和網頁結構特征Fi={|wi∈W},則可表示網頁聚類結果中每一個標記類特征為一個二元組C(c)=,其中c表示該類的標記,c∈正整數N.

本文使用分層聚類算法通過網頁相似度計算對一組網頁進行聚類,如算法1.

算法1．getClasses輸入：網頁結構特征集合D={F1，F2，…，Fk}，表示k個網頁的結構特征集合輸出：標記類集合M={C1，C2，…，Cn}，表示聚類結果為n個標記類 Begin Foreach Fi∈D then Ck←? add(Ck，Fi) ForeachFj∈D then ifsim(Fi，Fj)>0．82then add(Ck．W，Fj．w) remove(D，Fj) ifcard(Ck．W)>5then add(M，Ck)End

通過算法1,可以得到網頁標記類網頁集合M,集合中的每一個元素表示該標記類的特征.為了保證正文特征生成的準確性,在網頁聚類的過程中,我們只篩選出標記類中網頁數量大于5的標記類.

5 面向相似網頁的正文特征生成

在獲得網頁聚類結果后,還需要對同一標記類的網頁提取正文內容的抽取規則.本文采用基于統計的節點密度特征和網頁分塊相結合的方式來確定網頁內容的位置.在網頁中,正文內容的分布一般相對較集中,因此,正文內容所在的節點的文本密度比其他節點的文本密度要高.從HTML文件在瀏覽器中展現的效果來看,頁面是由若干個塊構成的,這些塊是由HTML容器標簽(

和

標簽)分割而成的.所以本文將HTML頁面切割成塊集合B,再從塊集合B中選擇不包含噪聲信息,但包含完整正文內容的正文內容塊.

5.1 塊節點密度特征

本文采用密度特征來判斷塊節點是否為正文內容塊,下面給出3個密度定義:

定義7.設n∈B為DOM樹Td中的一個塊節點,則n的文本密度定義為:

(2)

其中Tn為塊節點n包含的純文本字符數(不含鏈接文本),T為Td代表的整個文檔中的純文本字符數(不包含鏈接文本).

Ptext反映了在全局頁面中,文本內容在某個塊節點中的相對集中程度.我們發現Ptext越大,往往意味著該節點越有可能包含待發現的正文內容塊.

定義8.設n∈B為DOM樹Td中的一個塊節點,則n的鏈接密度定義為:

(3)

其中lNn為節點n中所包含的鏈接數,lN為Td代表的整個文檔中所包含的鏈接數.

Plink反映了在全局頁面中,鏈接在某個塊節點的相對集中程度.我們發現Plink越大,往往意味著該塊節點包含噪聲信息的可能性越大.

定義9.設n∈B為DOM樹Td中的一個塊節點,則n的節點文本密度定義為:

(4)

其中Tn為塊節點n的純文本字符數(不含鏈接文本),lTn為塊節點n的文本字符數(包含鏈接文本).

Ptextl反映了在某個節點的純文本集中程度.我們發現Ptextl越大,往往意味著該節點越有可能包含待發現的正文內容塊.

給出了3個密度度量后,可以定義塊節點的綜合密度特征值H(b):

(5)

其中b∈B表示該塊節點,size(b)表示該塊節點中子孫節點個數.p1,p2,p3分別代表節點的密度特征,取p1=ptext,p2=1-plink,p3=ptextl.α是調節塊節點b的子孫節點數量對H值影響的參數,在實驗中取α=0.3.當α設置過低時,選取的塊可能帶有噪音信息,當α設置過高時,利用綜合密度特征H可能選取錯誤的塊.

5.2 正文特征生成

通過4.1節我們可以得到網頁標記類集合M,在同一標記類中的網頁,正文內容塊的位置是相同的,所以在同一類網頁中通過密度特征選擇正文內容塊,再提取正文內容塊的特征作為該類網頁正文內容的抽取規則,如算法2所示.在網頁中塊的特征可以有三種表示方法,塊class屬性對應的值,塊id屬性對應的值和塊的路徑path.為了方便算法表示,本文給出了每個標記類中正文內容塊特征的定義,即每個標記類正文內容的抽取規則.

定義10.給定聚類結果中標記類的標記c={ci|ci=Ci.c},定義該標記類網頁正文內容塊的特征為一個三元組L(c)=,其中class表示正文內容塊b的class屬性對應的值,id表示正文內容塊b的id屬性對應的值,p表示正文內容塊的標簽路徑,p={p|p=p(b)且b∈B}.

將聚類的結果經過算法2可以得到每個標記類對應正文內容塊的特征L(c),即為該標記類網頁的正文內容提取規則.在L(c) 中記錄正文內容塊的三個特征,根據這三個特征可以從網頁中提取出正文內容塊.在一個Web網頁中并不是每個塊都有id和class屬性,所以在L(c)中,本文按優先級id>class>p依次進行提取,當id和class屬性不存在時用路徑p來提取正文內容塊.最后,從正文內容塊中提取出正文內容.

算法2．getBlock輸入：標記類集合M={C1，C2，…，Cn}，表示聚類結果為n個標記類輸出：抽取規則集合N={L1，L2，…，Lk}，表示n個標記類對應的k個正文內容塊特征集合，其中k<=n．BeginForeachCi∈MthenBF←?//BF={，，…，} Foreachw∈Ci．Wthen 將網頁w轉化為DOM樹結構，提取網頁中的塊集合B 計算塊b∈B對應綜合密度特征H(b) 選擇H(b)最高的塊b，提取其特征L(b)，記錄該塊的特征和其綜合密度特征為bf= 若?bfi∈BF且bfi．L=bf．L則bfi．H=bfi．H+bf．H否則add(BF，bf) Endfor 從BF集合中選擇H最高的L作為該標記類對應的抽取規則，add(N，L)EndforEnd

6 方法評估

為了驗證本文提出方法的有效性,我們實現了相應的原型系統.該原型系統分為兩個過程:基于網頁聚類的正文特征生成和網頁正文內容提取.實驗環境為CPU(Inter Pentium CPU,3.10GHz)+RAM(8GB)+Window7+Eclipse3.10.在實驗中,采用工具Jsoup對網頁進行解析和塊的提取.

實驗中所使用的數據集WebSet來自包括5個網站的1500個網頁.該數據集通過半手工方式(種子URL+爬蟲+手工篩選)從互聯網網上收集得到的,來源于網易、搜狐、新浪、人民網和新華網,這些網頁分布在網站中的不同主題類目.在具體實驗過程中,我們又從WebSet中產生2個子集:1)網頁聚類數據集WebSet-1.包括500個網頁從WebSet中手工選取,來自5個站點并且覆蓋每個站點中的主題.2)網頁正文內容抽取數據集WebSet-2.包括1000個網頁.

我們對數據集WebSet-1中的網頁進行聚類處理并生成正文特征,其結果如圖2所示.在實驗中,網易和新浪中出現在同一主題模塊的頁面中產生多個類別.圖3展示了在聚類過程中,不同網站的頁面中平均塊節點個數,在圖3結果中網易、搜狐和新浪的頁面中平均塊節點個數量遠遠超出新華網和人民網.而在這些塊節點中絕大多數是只包含噪音信息的塊節點,因此除了網站中網頁本身的設計結構的差異,網頁中的噪音信息在一定程度上也影響網頁的聚類結果.

圖2 網頁聚類結果Fig．2 Experimentalresultofwebpageclustering圖3 網頁分塊結果Fig．3 Experimentalresultofwebpagesegmentation

在網頁正文提取方面,本文對數據集WebSet-2中的網頁進行內容的提取.實驗分為兩種,第一種是不利用網頁聚類處理的結果,只通過塊節點的綜合密度特征來對網頁正文內容進行提取,其結果如表1所示.第二種是利用網頁聚類和生成的正文內容塊特征(抽取規則)來進行網頁正文內容的提取,其結果如表2所示.從表1和表2的對比中我們可以發現網頁聚類能夠顯著提高網頁正文內容提取的準確率,基本能夠消除因為正文內容字符數較少導致提取錯誤的塊的問題.在5個站點中,網易的提取結果并不理想.這是因為在網易財經模塊中大部分網頁并不存在正文內容塊,而是將推薦鏈接等噪音信息與正文內容嵌入在同一個塊中,導致實驗中提取的正文內容塊包含部分噪音信息.

表1 無聚類處理的正文內容提取結果
Table 1 Experimental result of web information extraction with no clustering processing

DataSet網頁總數準確率網易20088%搜狐20096．5%新浪20095%新華網20097%人民網20092%

表2 基于網頁聚類的正文內容提取
Table 2 Experimental result of web information extraction with clustering processing

DataSet網頁總數準確率網易20092%搜狐200100%新浪20098%新華網200100%人民網20099．5%

在時間性能方面,因為網頁結構的復雜程度不同,所以不同網站中網頁聚類和正文特征生成所耗費的時間也存在差異.實驗中,平均對每100個網頁進行聚類并生成正文特征的時間為4571ms.在網頁正文內容提取方面,在無聚類的情況下,平均抽取一個網頁的時間為26ms,在有聚類的情況下平均抽取一個網頁的時間21ms.從實驗結果來看,在有聚類的情況下平均抽取一個網頁的時間比無聚類情況下要快5ms.

文獻[8]也是一種基于網頁聚類的正文提取方法,該方法采用樹編輯距離計算網頁之間的相似度,并且利用DOM樹的結構差異來確定網頁的抽取規則,其準確率為82.5%.與該方法相比本文采用的方法的準確率高達97.9%,并且本方法采用路徑集合來計算網頁之間的相似度降低了網頁聚類的時間消耗.文獻[1]中的CEPR算法在網易,新浪,新華網和人民網的數據集上精確率達到99.29%,98.57%,94.72%和95.11%,基本與本方法相當.然而,CEPR算法平均抽取一個網頁的時間為375ms,不適合針對大規模網頁的處理.

7 總結

本文結合現有的Web信息提取方法,基于網頁分割的正文提取和基于統計的密度特征正文提取,再結合網頁聚類,提出了一種基于網頁聚類的正文信息提取方法.該方法利用對結構相同的網頁進行統一的提取操作,來提高網頁正文內容抽取的準確率.在實驗中,我們將有聚類處理和無聚類處理的網頁正文內容提取進行對比,其準確率顯著上升.本方法適用于提取來自同一網站的網頁,不需要復雜的計算,簡單實用.

未來的工作重點主要包含兩個方面:一方面,將本文提出方法運用到大規模網頁處理的環境中.另一方面,已有的Web信息抽取方法主要提取粗粒度的Web內容,面向精準的細粒度結構化Web信息抽取的精度仍不是很理想,因此,我們的研究重點將轉為對網頁中細粒度的實體提取.

[1] Wu Gong-qing,Hu Jun,Li Li,et al.Online web news extraction via tag path feature fusion [J].Journal of Software,2016,27(3):714-735.

[2] Wang J,Wang J.qRead:a fast and accurate article extraction method from web pages using partition features optimizations[C].Proceedings of the 7th International Joint Conference on Knowledge Discovery,Knowledge Engineering and Knowledge Management (IC3K 2015)，Lisbon,Portugal,2015:364-371.

[3] Zhang Nai-zhou,Cao Wei,Li Shi-jun.Amethod based on node density segmentation and label propagation for mining web page [J].Journal of Computer Science and Technology,2015,38(2):349-364.

[4] Cai D,Yu S,Wen J R,et al.Extracting content structure for web pages based on visual representation[C].Proceedings of the 5th Asian-Pacific Web Conference(APWEB 2003)，Xi′an,China,2003:406-417.

[5] Yin X,Lee W S.Using link analysis to improve layout on mobile devices[C].Proceedings of the 13th International Conference on World Wide Web(WWW 2004)，New York,USA,2004:338-344.

[6] Wu S,Liu J,Fan J.Automatic web content extraction by combination of learning and grouping[C].Proceedings of the 24th International Conference on World Wide Web(WWW 2015)，Florence,Italy,2015:1264-1274.

[7] Joshi S,Agrawal N,Krishnapuram R,et al.A bag of paths model for measuring structural similarity in Web documents[C].Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD 2003)，Washington,USA,2003:577-582.

[8] Yang Tian-qi,Qiu Tao-fen.A method of automatic web information extraction based on page clustering[C].Proceedings of the 8th World Congress on Intelligent Control and Automation(WCICA 2011)，Taipei,2011:390-393.

附中文參考文獻：

[1] 吳共慶,胡駿,李莉,等.基于標簽路徑特征融合的在線Web新聞內容抽取[J].軟件學報,2016,27(3):714-735.

[3] 張乃洲,曹薇,李石君.一種基于節點密度分割和標簽傳播的Web頁面挖掘方法[J].計算機學報,2015,38(2):349-364.

[8] 楊天奇,邱韜奮.一種Web信息自動抽取的網頁聚類方法[C].第8屆智能控制與自動化世界大會(WCICA 2011),臺北,2011:390-393.