基于結構相似網頁聚類的正文提取算法研究

王海涌，馮兆旭，楊海波，張津棟

WANG Haiyong,FENG Zhaoxu,YANG Haibo,ZHANG Jindong

蘭州交通大學 電子與信息工程學院，蘭州 730070

School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China

1 引言

隨著信息技術的進步，各種網頁制作工具和新的WEB標準，使得產生各種各樣網頁內容的速度越來越快，與此同時網頁上也出現了越來越多的額外信息，包括廣告、站內推廣信息、其他相關內容的鏈接，這些廣告鏈接等數據的加入使得開發人員更容易也更多樣化的方式來表達信息，不同類型的工具和元素使得網站的內部結構和頁面外觀更加復雜多樣。目前網絡數據主要是以HTML頁面的形式，由于HTML語言只是告訴瀏覽器如何顯示它定義的信息并執行，經過瀏覽器分析后的網頁適合于人們瀏覽，但不適合作為由計算機來處理的數據。網頁正文提取旨在從半結構化的網頁文檔中抽取出有價值的信息，它是數據挖掘、話題檢測、文本分類、網頁聚類等領域的關鍵環節，面對如此巨大互聯網信息庫，如何快速有效地提取網頁正文信息已成為當前信息處理的迫切需求。

20世紀90年代初，人們開始注重研究信息提取。近年來隨著網頁的應用越來越廣泛，人們逐漸將研究重點轉移到網頁信息提取上，并取得了不少成果。Arasu等人采用了詞頻統計與DOM路徑相結合的方法。然而對于網頁內容很多的網頁這種方法的效果不好[1]。Kim等人改進了網頁模板的生成方式，利用網頁不同區域內容所占面積大小來設定權重[2]。

當前，常見的網頁正文提取算法可分為四大類：基于啟發式規則的正文提取算法，基于網頁模板的正文提取算法，基于視覺分塊的正文提取算法以及基于統計、機器學習的正文提取算法。網絡上也有一些網頁正文提取產品和項目，如cx-extractor、Readability、Diffbot等，它們在正文提取的效果和性能上各有優劣。其中arc90實驗室的Readability算法的基本思想是：先將網頁解析DOM樹，所有標簽小寫。然后去除所有“script”標簽內容，再通過一對正則表達式的配合提取[3]。2010年1月西南科技大學的熊子奇、張暉、林茂松等人提出利用網頁標簽和文本內容相似度相結合來提取正文信息[4]。2015年9月中科院計算機網絡信息中心楊柳青等人提出并實現了一種基于布局相似性的網頁正文提取算法，該算法通過對比同一站點同一專題的網頁DOM樹中節點數據信息的相似性來實現正文提取[3]，但是該算法未能考慮互聯網網頁來源繁雜，正文提取結果受網頁結構相似度的影響較大。而且論文中提出的算法在樹路徑和查詢參數的相似性計算上采用“相同目錄層數/最大目錄層數”這樣一種簡單的度量方法，不能完全反映網頁的結構特征，要實現更精準的結果還需作進一步的研究。

2 網頁結構特征分析

2.1 基本原理

HTML是一種用于描述網頁文檔的文本標記語言，可以用DOM樹表示，DOM是文檔對象模型（Document Object Model）的縮寫[5]。DOM是一個瀏覽器、平臺獨立于語言的接口，允許用戶訪問其頁面的其他標準組件，HTML文檔被解析成DOM樹，每個HTML中的元素、屬性、文本代表一個樹節點[6]。

定義1DOM樹中節點擁有子樹數稱為節點的度。DOM樹中度為0的節點為葉子節點。

定義2節點的子樹稱為該節點的子節點；該節點稱為子節點的父節點。

定義3樹路徑是指從根節點到一個葉節點所經歷的所有節點組成的序列，表示如下：

其中，m表示該路徑在DOM樹中出現的次數；(t1,t2,…,tn)表示該路徑所經歷的節點標簽組成的序列；(s1,s2,…,sm)表示該路徑出現的位置[7]。DOM樹所有路徑的葉節點按遍歷排序，用順序號表示樹路徑的位置。一個網頁的DOM樹可用一個樹路徑集合表示。

2.2 網頁結構相似性

網頁相似度研究主要用于網頁信息抽取。網頁相似度的研究可分為基于網頁內容的文本相似度研究和基于網頁機構的結構相似度研究；前者是對網頁中的文本進行中文分詞后提取特征詞，構造特征向量并計算其相似性[8]。根據文獻[6]所述，網頁可分為：主題型網頁、目錄型網頁和多媒體網頁。

本文主要任務是從大量的網絡新聞網頁中提取正文內容，這些網頁來自許多不同的新聞網站，主要的研究對象是中文主題型網頁。網頁的結構特征是以塊的形式呈現的，而且通常在同一站點下的統一頻道中所有主體性網頁間的布局結構極為相似，所有的目錄型網頁的布局結構也極為相似，并且相同或相似的內容往往出現在固定的位置上[9]。澎湃新聞的網頁布局實例如圖1所示。

圖1 新聞網頁布局實例

在圖中，可以看到同一網站，同一專題下的新聞網頁具有相同的布局結構，網站的導航欄位于網頁的正上方；在網頁的右側會有一些網站的廣告或推薦信息等；再往下是網頁的版權信息，中間部分就是所需要的正文信息。而網頁中的導航欄、推薦信息、廣告信息、版權信息等布局相同，內容也相同；圖中的黑框部分就是網頁的正文信息，布局相同，內容不同；這樣的現象與現代網站開發模式有很大關系，目前大部分網站都采用動態頁面以達到節省開發時間和費用的目的，通常采用CSS、JS、HTML來制作通用的網頁前端模板，然后從數據庫中讀取相關數據，并與前臺模板相結合展示給用戶。

文獻[3]基于布局相似性的網頁正文內容提取研究，提出了利用相似網頁內容布局和樣式結構相似的特點提取正文信息的方法[4]，此方法的正確率受相互參照的兩個頁面在布局結構上的相似程度的影響較大，未考慮所提取目標網頁來源龐雜，沒有固定統一的格式，難以直接對比兩個網頁的DOM樹去除噪音，因此從網頁相似性入手，提出基于結構相似網頁聚類的正文提取算法，先將提取到的網頁進行相似度的計算，將相似度較高的網頁聚為一類，再利用正文提取算法提取正文，并針對文獻[3]中簡單的樹路徑相似度計算方法進行改進，提出改進的基于簡單樹匹配的網頁結構相似性度量算法，該方法提高了識別網頁結構相似性的能力，對結構差別較大的網頁進行良好的區分，進而能夠適應更復雜多樣的網頁結構，在網頁正文提取中具有更好的效果。

3 基于網頁結構相似的網頁正文提取

本文研究對象為中文主題型網頁，主要是各大新聞網站在某一段時間內的新聞報道。計算網頁相似度，將網頁相似度較高的網頁進行聚類，利用正文提取算法去除噪聲提取正文。

3.1 網頁相似度計算

由于基于結構相似網頁聚類的正文提取算法中引入了聚類算法，所以就必須使用到網頁相似性度量，原算法中采用的度量方法是基于樹路徑的網頁結構相似度匹配算法，由于這種度量方法不能很好地體現網頁的層次結構。所以，本文采用改進的基于簡單樹匹配的網頁結構相似性度量方法替換原有的基于樹路徑的網頁結構相似性度量方法。下面將對改進的基于簡單樹匹配的網頁結構相似性度量方法進行詳細的介紹。

定義4根據現有網站開發模式，通常網頁布局以各個區域形式呈現，將網頁中的各個區域稱為“塊”。

定義5將每個“塊”視為一個整體，在各個塊中又包含各個不同的內容區域，即將這個塊劃分成多個子塊，將這個塊稱為子塊的父塊。如此不斷迭代對網頁結構進行劃分，直到該塊不能再被劃分為子塊時，稱該塊為葉子塊。

定義6將第一次對網頁模板進行分塊得到的子塊稱為一級子塊。

如圖2所示為常見網頁的結構示意圖，該網頁在結構上可以劃分為三大“塊”，分別為上、中、下三塊，最上一塊一般包括標題、導航等信息；中間一塊可分為左右兩塊，左邊一塊通常用于展示噪音鏈接、索引等信息，右邊面積最大的一塊通常是網頁正文所在的位置；最下邊一塊一般用于展示網站的版權信息等。通常“塊”之間的切割是由HTML中的“塊級”標簽完成的。

圖2 網頁結構示意圖

圖2 所示網頁的結構代碼如下：

將上述網頁解析為DOM樹，可以表示為如圖3所示的樹，其中，A為樹的根節點，a、b、c為根節點的三個直接孩子節點，它們各自為一棵子樹，d、e是節點b的兩個孩子節點。

圖3 網頁DOM樹

在實際情況中，網頁模板的最上邊一塊和最下邊一塊中的內容是靜態的、固定不變的，中間塊的內容是動態生成的，其中左邊塊的內容在多數情況下也是靜態的，右邊塊內的內容是由網頁腳本在后臺從數據庫中取得的[10]。在DOM樹中表現為，根節點的三棵子樹中，第一棵子樹與最后一棵子樹在結構和內容都是靜態的、保持不變的，第二棵子樹中大部分節點為動態生成的，其余部分為靜態的、保持不變的。

根據上述特征，本文首先提出一種通過對比網頁“塊”相似度計算網頁結構相似度的方法，其基本思想如下：將網頁的相似度總和“1”平均分配到網頁的各大“塊”中，然后對比兩個網頁的“塊”的相似度。對比塊的相似度可以將塊視為整體1，并平均分配到這個塊的所有子塊。根據這種規則不斷迭代，直到每個“子塊”都是“葉子塊”。然后對比兩個網頁對應位置的“塊”的相似度，再根據某種規則綜合所有“塊”的相似度即可得到兩個網頁的相似度。將網頁的“塊”對應于DOM樹的節點，則“父塊”等同于“父節點”，“葉子塊”等同于“葉子節點”。那么就可以把計算兩個網頁“塊”的相似度轉化為計算兩個網頁DOM樹的相似度。

一棵樹可以表示為P=(X11,X21,X22,…,Xnm)，其中n表示節點的層次，根節點的層次為1，X11表示樹P的根節點，m表示在當前層中節點的序號。Xnm表示第n層中從左向右第m個節點[11]。

定義7兩棵樹P1，P2的相似度表示為：

其中，PiXnm表示樹Pi的Xnm節點，Num(n)表示樹中第n層節點的總數，并且：

定義8兩個節點相同指兩個節點的標簽名、屬性集以及子節點的個數都相同，以及兩個節點在DOM樹中的位置也相同。

定義9兩個節點不同是指兩個節點的標簽名、屬性集、子節點的個數以及在DOM樹中的位置這些屬性中，只要有一個不同，則兩個節點不同。

所以，當判斷出P1Xnm≠P2Xnm，σ=0，此時就沒有必要繼續計算的值，從而大大減少了計算量。當P1Xnm=P2Xnm時，那么這兩個節點的子節點個數也是相同的，即它們的Num(n)值是相同的。

對比兩棵DOM樹相似性算法Improved Simple Tree Matching(P1,P2)，簡稱ISTM(P1,P2)，描述如下。

算法1 ISTM(P1,P2)

算法給出了對比兩棵DOM樹相似性的過程，其過程如下：

步驟1首先判斷兩棵樹的根節點是否相同，如果根節點不同，則認為兩棵樹相似度為0，如果根節點相同，則進行第二步。

步驟2判斷兩棵樹根節點的子節點個數是否相同，若不相同，則兩棵樹相似度為0，如果相同，則進行第三步。

步驟3假設根節點的子節點個數為N，則每個子節點分配到的權重為

步驟4兩棵樹的相似度等于根節點下每個對應子節點的相似度與節點權重的乘積之和。

步驟5遞歸計算子節點的相似度，然后從葉子節點逐層向上傳遞子節點的相似度。

然而，根節點下所有子節點得到相同的權重并不能很好地體現網頁中各個“塊”對網頁模板的貢獻。標題、導航、快捷鏈接、版權信息在整個“網頁模板”中所占的比例遠高于模板中“正文”的部分。采用平均分配策略可能導致如下情況：當兩個網頁正文部分的結構和內容相同，但導航和版權信息部分部分相似時，兩個網頁的相似度也非常高，這顯然與算法的初衷是相背離的。

為了避免上述問題，本文又在上述算法的基礎上，引入按“貢獻”分配權重。即在相似度計算過程中，標題導航塊、版權信息塊以及靠近網頁兩端的在結構和內容相對固定的模塊得到較大權重，而靠近網頁中心位置，結構和內容變化可能性較大的模塊得到較小的權重。而且，按“貢獻”分配權重只針對網頁的一級“子塊”，因為將一級子塊作為父塊進行再分塊后，得到的各個子塊對父塊的“貢獻”是相同的。

修改權重因子Lp(n)為Lpn(m)：

綜上所述，兩棵樹的相似度可表示為：

算法2ISTM(P1,P2,n)

算法給出了引入按貢獻分配權重對比兩棵DOM樹相似性算法ISTM(P1,P2,n)的基本流程：

步驟1首先判斷兩棵樹根節點是否相同，如果根節點不同，則認為兩個數的相似度為0，如果根節點相同，則進行步驟2。

步驟2判斷兩棵樹根節點的子節點個數是否相同，若不相同，則兩棵樹相似度為0；如果相同，則進行步驟3。

步驟3假設根節點的子節點個數為N，則每個子節點分配到的權重為

步驟4兩棵樹的相似度等于根節點下每個對應子節點的相似度與節點權重的乘積之和。

步驟5遞歸計算子節點的相似度，從第三層子節點開始，每個子節點分配到的權重為，N為當前層節點的總數。

步驟6從葉子節點逐層向上傳遞子節點的相似度。

3.2 網頁正文提取

通過上文中網頁相似度的計算，運用層次聚類算法對網頁進行聚類，得到一組布局相似的網頁集；本節將詳細介紹針對聚類結果中的簇，如何完成網頁正文提取。

利用改進的網頁相似度算法對數據集中的網頁進行聚類后，結果集中每個簇包含的網頁具有如下共同特征：

（1）都是基于一個或幾個相似度極高的網頁前端模板實現的。

（2）網頁之間相同的部分為前端模板包含的內容。

（3）網頁之間不同的部分為網頁的正文[12]。

根據上述特征，提出提取網頁正文的方法，基本思想為：利用DOM樹解析工具將網頁簇中的兩個網頁解析成DOM樹，比較兩棵DOM樹并將其中相同的節點和子樹刪除，然后將剩余部分中的文字提取出來，即為網頁正文內容。具體流程如算法所示。算法對比DOM并刪除相同節點。

輸入：目標網頁DOM樹D1，參考網頁DOM樹D2。

在完成了完全相同節點刪除后，基于結構相似網頁聚類的正文提取算法即已執行完畢。

3.3 算法分析

本文考慮到所提取目標網頁來源龐雜，沒有固定統一的格式，難以直接對比兩個網頁的DOM樹去除噪音，因此從網頁相似性入手，提出一種基于結構相似網頁聚類的正文提取算法，先將提取到的網頁進行相似度的計算，將相似度較高的網頁聚為一類，簇中的網頁具有較高的相似度，對比它們的DOM樹并將相同的節點刪除，這些相同部分就是這些網頁中所共有的內容即與網頁中的無關信息和冗余數據；剩余的部分就是要提取的正文內容。該方法提高了識別網頁結構相似性的能力，對結構差別較大的網頁進行良好的區分，進而能夠適應更復雜多樣的網頁結構，在網頁正文提取中具有更好的效果。

4 實驗結果及分析

4.1 實驗環境和數據

為了驗證本文所提正文提取方法的有效性，本文對Readability正文抽取算法和基于網頁相似度的正文提取算法進行了對比實驗。實驗平臺為PC配置為CPU3.4 GHz，內存2 GB，500 GB硬盤，開發工具為Visual Studio 2010，算法采用C#語言實現，采用HtmlAgilityPack作為DOM樹解析工具。

為了對算法正文提取的效果進行更加客觀的評估，本文提取用于測試的網頁樣本以國內主要門戶網站的新聞頻道網頁為主，網頁來源網易、新浪、搜狐、騰訊、人民網、新華網、鳳凰網等共10個網站，從上述10個網站中隨機抽取100個網頁，總數量為1 000；再從每個網站樣本集中隨機抽取一定數量的網頁進行測試，抽樣測試集容量為100。本文實驗中所選取的新聞網頁均為中文主題型網頁，主題型網頁的結構特征是以塊的形式呈現的，含有一篇正文報道，而且同一站點下的同一頻道中所有主題型網頁間的布局結構極為相似，正文以及頁面其他信息位置相對固定[13]；不同站點網頁結構差別較大的網頁能夠更好地進行聚類，提高正文提取實驗效果。

4.2 實驗評價標準

網頁正文提取的評價標準是查準率P（Precision）和查全率R（Recall），最后統計各項內容的平均值。查準率表示在抽取結果中，標記正文內容所占的比重；查全率表示正確提取正文信息與人工標注正文信息的比例[14]。

計算公式如下：

其中A表示用實驗方法得到的網頁長度，B表示人工標注正文部分內容的長度；C表示A和B的公共部分長度[15]。

4.3 實驗結果

為了驗證本文算法的有效性，提取用于測試的網頁樣本以國內主要門戶網站的新聞頻道網頁為主，將本文算法與文獻[3]、Readability正文抽取算法進行了實驗測試對比，其中測試結果查準率P、查全率R以及綜合平均對比結果分別如表1至表3所示。

從實驗結果來看，三種算法都能較好地提取新聞網頁中的正文信息，對于網頁中的導航欄等無關信息有效地去除。本文算法在查準率和查全率以及綜合評定指標均優于文獻[3]算法和Readability正文抽取算法。本文算法在進行正文提取之前先將采集到的網頁進行聚類，提高了算法的準確度，降低了來自不同網站，結構復雜對正文提取的影響。從整體上看改進的方法能夠實現較高精度的網頁正文提取。

表1 正文提取結果查準率P對比 %

表2 正文提取結果查全率R對比 %

表3 正文提取結果綜合評價 %

5 結論

本文描述了一種先通過網頁聚類再進行正文提取的方法，該方法在正文提取充分考慮網頁采集來源的不確定性，以及網頁結構的復雜性對正文提取準確度的干擾，引入網頁結構權重的概念，并將網頁塊相似度計算轉化為網頁DOM樹相似度計算，對聚類之后結果簇中的所有網頁內相似部分去除，剩余部分則是網頁正文信息。實驗結果顯示本文提出的算法具有非常好的準確度，適合于大規模來源繁雜的網頁正文提取。另一方面本文提出的基于結構相似網頁聚類的正文提取算法運行效率較低。因此在未來的工作中，將繼續研究并解決這個問題，提高算法運行效率。

參考文獻：

[1]Arasu A，Garcia-Molina H.Extracting structured data from Web pages（poster）[C]//International Conference on Data Engineering，2003.

[2]Kim Y，Park J，Kim T，et al.Web information extraction by HTML tree edit distance matching[C]//Int Conf on Convergence Information Technology，2007：2455-2460.

[3]楊柳青，李曉東，耿光剛.基于布局相似性的網頁正文內容提取研究[J].計算機應用研究，2015，32（9）：2581-2586.

[4]熊子奇，張暉，林茂松.基于相似度的中文網頁正文提取算法[J].西南科技大學學報，2010，25（1）：80-84.

[5]段曉麗，王宇，谷靜，等.基于正文特征及網頁結構的主題網頁信息抽取[J].計算機工程與應用，2012，48（30）：151-156.

[6]廖浩偉，楊燕，賈真，等.一種改進的基于樹路徑匹配的網頁結構相似度算法[J].吉林大學學報：理學版，2012，50（6）.

[7]王亞普，王志堅，葉楓.一種改進的樹路徑模型在網頁聚類中的研究[J].計算機科學，2015，42（5）：109-113.

[8]Bishnu P S，Bhattacherjee V.Software fault prediction using quad tree-based K-means clustering algorithm[J].IEEE Transactions on Knowledge&Data Engineering，2012，24（6）：1146-1150.

[9]熊忠陽，藺顯強，張玉芳，等.結合網頁結構與文本特征的正文提取方法[J].計算機工程，2013，39（12）：200-203.

[10]Vineel G.Web page DOM node characterization and its application to page segmentation[C]//2009 IEEE International Conference on Internet Multimedia Services Architecture and Applications（IMSAA），2009：1-6.

[11]姬鑫，鐘誠.基于分塊的新聞網頁信息抽取算法[D].南寧：廣西大學，2015.

[12]王少康，董科軍，閻保平.使用特征文本密度的網頁正文提取[J].計算機工程與應用，2010，46（20）：1-3.

[13]Kim M，Kim Y，Song W，et al.Main content extraction from web documents using text block context[M]//Database and Expert Systems Applications.Berlin Heidelberg：Springer，2013：81-93.

[14]Mane T B，Potdar G P.Template extraction from heterogeneous Web pages[J].International Journal of Advanced Computer Research，2012，2（6）.

[15]Wang J，Liu Z.P2DHMM：A novel Web object information extraction model[C]//International Conference on Computer Engineering and Technology，2009：531-535.