基于節(jié)點屬性與正文內(nèi)容的海量Web信息抽取方法

王海艷，曹攀

（1. 南京郵電大學(xué)計算機(jī)學(xué)院，江蘇 南京 210023；2. 江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室，江蘇 南京 210003）

基于節(jié)點屬性與正文內(nèi)容的海量Web信息抽取方法

王海艷1,2，曹攀1

（1. 南京郵電大學(xué)計算機(jī)學(xué)院，江蘇 南京 210023；2. 江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室，江蘇 南京 210003）

為解決大數(shù)據(jù)場景下從海量Web頁面中抽取有價值的信息，提出了一種基于節(jié)點屬性與正文內(nèi)容的海量Web信息抽取方法。將Web頁面轉(zhuǎn)化為DOM樹表示，并提出剪枝與融合算法，對DOM樹進(jìn)行簡化；定義DOM樹節(jié)點的密度和視覺屬性，根據(jù)屬性值對Web頁面內(nèi)容進(jìn)行預(yù)處理；引入MapReduce計算框架，實現(xiàn)海量Web信息的并行化抽取。仿真實驗結(jié)果表明，提出的海量Web信息抽取方法不僅具有更好的性能，還具備較好的系統(tǒng)可擴(kuò)展性。

Web信息；抽??；MapReduce；DOM樹

1 引言

Proteus工程創(chuàng)建者Grishman將信息抽取描述為“從文本中選擇出的信息創(chuàng)建一個結(jié)構(gòu)化的表現(xiàn)形式”[1]。作為數(shù)據(jù)挖掘的重要組成部分，信息抽取受到了眾多學(xué)者的廣泛關(guān)注并出現(xiàn)了一些相應(yīng)的解決方法，如李蕾等[2]在全信息論的基礎(chǔ)上提出的中文信息抽取系統(tǒng)，黃詩琳等[3]提出的從文本中抽取命名實體的方法，秦兵[4]、李天潁[5]等提出的關(guān)系信息抽取算法。近年來，隨著互聯(lián)網(wǎng)技術(shù)的普及，作為信息抽取的重要分支，Web信息抽取技術(shù)也得到了極大的發(fā)展，出現(xiàn)了諸多的抽取算法，主要有如下幾類。

基于視覺分塊抽取方法最早由微軟亞洲研究院的Cai等[6]提出的，該方法主要通過頁面分塊的視覺特征量對頁面內(nèi)容進(jìn)行分類來抽取正文信息，在此基礎(chǔ)上，Neil[7]提出了Extractor算法；Narwal等[8]提出了基于頁面內(nèi)容布局的信息抽取方法。相對于基于視覺分塊的方法，基于DOM樹的更容易實現(xiàn)，如Sun等[9]在根據(jù)DOM樹節(jié)點的文本密度來實現(xiàn)Web信息的抽取；張乃洲等[10]將DOM樹技術(shù)與標(biāo)簽傳播相結(jié)合構(gòu)建了統(tǒng)一的信息抽取框架；Wan等[11]在DOM樹的基礎(chǔ)上引入樸素貝葉斯的文本分類模型，實現(xiàn)中文網(wǎng)站的信息抽取。除了上述2種方法之外，還有基于模板的抽取技術(shù)，這種算法主要抽取的對象為通過固定模板生成的網(wǎng)頁，如Krishn等[12]提出的算法等。

但是，已有的這些方法要么算法的復(fù)雜度比較高，信息抽取的效率較低，要么頁面切割的思想較為簡單，不能夠較好地對頁面中的各類數(shù)據(jù)實現(xiàn)完整的抽取。另外，由于現(xiàn)有的大多數(shù)方法都是在單線程的基礎(chǔ)上進(jìn)行線性抽取，顯然無法滿足當(dāng)前大數(shù)據(jù)環(huán)境下信息抽取的需求，而MapReduce作為一個高度并行的編程模型，近年來，已經(jīng)運用到很多領(lǐng)域，如Mansurul等[13]提出的基于MapReduce的頻繁子圖挖掘算法和Jin等[14]提出了并行空間協(xié)同定位算法。這些研究都表明MapReduce作為一個高度統(tǒng)一的編程模型在處理海量數(shù)據(jù)時是高效且可行的。因此，基于上述分析，本文在現(xiàn)有理論的基礎(chǔ)上，針對當(dāng)前大數(shù)據(jù)環(huán)境下Web信息抽取存在的準(zhǔn)確率和召回率不高以及抽取效率較低問題，提出一種基于節(jié)點屬性與正文內(nèi)容的海量Web信息抽取方法，主要工作如下。

1) 提出針對DOM樹的剪枝與融合方法，在保證信息不丟失的基礎(chǔ)上，有效簡化DOM樹，提高后續(xù)信息抽取的準(zhǔn)確率和效率。

2) 充分考慮DOM樹節(jié)點的密度和視覺屬性，根據(jù)屬性值對Web頁面內(nèi)容進(jìn)行有效的預(yù)處理。

3) 引入MapReduce計算框架，實現(xiàn)海量Web信息的并行化抽取，提高信息抽取的效率。

2 相關(guān)概念

2.1 HTML DOM

文檔對象模型（DOM, document object model），是W3C組織推薦的處理可擴(kuò)展標(biāo)志語言的編程接口，它可以用來訪問和處理HTML文檔，并將其轉(zhuǎn)換為一個節(jié)點樹形結(jié)構(gòu)，根據(jù)W3C的HTML DOM標(biāo)準(zhǔn)，HTML文檔中的所有內(nèi)容都是節(jié)點。下述為一段標(biāo)準(zhǔn)的HTML代碼。

其對應(yīng)的DOM樹結(jié)構(gòu)如圖1所示。

圖1HTML對應(yīng)的 DOM樹結(jié)構(gòu)

2.2 樸素貝葉斯定理

貝葉斯定理的核心思想是通過對某一個事件過去發(fā)生的概率情況來推斷當(dāng)前這一事件發(fā)生的概率的計算方法。貝葉斯分類法基于貝葉斯定理，其在文本分類中已被廣泛使用，它們可以預(yù)測類隸屬關(guān)系的概率，如一個給定元組屬于一個特定類的概率。

設(shè)X是數(shù)據(jù)元組，通常由n個屬性集的測量值描述。令H為某種假設(shè)，如數(shù)據(jù)元組X屬于某個特定類C。P(H|X)是后驗概率，即在條件X下，H的后驗概率，P(H)是先驗概率，即H的先驗概率。類似地，P(X|H)是條件H下，X的后驗概率，P(X)是X的先驗概率。P(X)、P(H)、P(X|H)可以由給定的數(shù)據(jù)估計，貝葉斯定理通過這三者概率值計算后驗概率P(H|X)，計算式為

樸素貝葉斯分類法是在貝葉斯分類法的基礎(chǔ)上假定一個屬性值在給定類上的影響?yīng)毩⒂谄渌麑傩缘闹?，分類原理為對于給出的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，通過概率值判定待分的類歸屬的類別。通過這樣的假設(shè)，極大地簡化了計算，并通過相關(guān)實驗論證其具備較高的準(zhǔn)確率。

3 海量Web信息抽取方法

3.1 基于MapReduce的抽取框架

為了提高在海量數(shù)據(jù)環(huán)境下Web信息抽取的效率，引入MapReduce計算框架，實現(xiàn)抽取的并行化處理。首先，將本地待處理的網(wǎng)頁存儲于HDFS上，HDFS將這些數(shù)據(jù)動態(tài)的分配給Hadoop平臺中的每個Map節(jié)點，為了讓每一個節(jié)點都能完整且并行的處理數(shù)據(jù)，本文將抽取算法完整的映射到每一個節(jié)點上。Map節(jié)點在每一次Map過程中都將對網(wǎng)頁進(jìn)行完整的信息抽取，最終每個節(jié)點都將產(chǎn)生完整的信息，Reduce函數(shù)將以鍵值對的形式將這些數(shù)據(jù)輸出。下面將具體介紹Map以及Reduce過程。

Map過程將主要包含Web頁面向DOM樹的轉(zhuǎn)換、DOM樹的簡化、基于節(jié)點屬性的Web信息預(yù)處理以及在預(yù)處理基礎(chǔ)上根據(jù)節(jié)點內(nèi)容實現(xiàn)的信息抽取等4個模塊，具體的函數(shù)如下。

算法1Map過程

輸入數(shù)據(jù)格式為＜key, value＞，具體函數(shù)中為＜pageNumber, webpage＞, pageNumber為待抽取頁面的序列號，webpage為待抽取的頁面。

輸出數(shù)據(jù)格式為＜key, value＞，具體函數(shù)中為＜pageNumber, content＞，pageNumber為經(jīng)過抽取后的頁面序列號，而content則是從頁面中抽取出來的有價值內(nèi)容。

1)Procedure Map（offset key,object value）

2)for all webpages in List webpages do{

3)extraction Model model = createExtractionModel(webpage);

4)DOMTree tree = model.transfer (webpage);//頁面轉(zhuǎn)化為DOM樹

5)SimpleTree st = model.simplify (tree);//DOM的剪枝融合操作

6)st = model.Pretreatment(st); //基于節(jié)點屬性Web信息預(yù)處理

7)st = model.Extraction(st); //在預(yù)處理基礎(chǔ)上根據(jù)節(jié)點內(nèi)容完成抽取工作

8)emit (key, webpage);//輸出頁面中有價值的內(nèi)容塊

9)}

Reduce過程是對Map過程的輸出結(jié)果進(jìn)行合并處理，每個Reduce過程都對應(yīng)一個獨立的輸出文件。在Reduce過程之前，系統(tǒng)將執(zhí)行一個Sort和Partition過程，Sort會將Map的輸出結(jié)果按照pageNumber值進(jìn)行自然排序，Partition將對排序的結(jié)果進(jìn)行劃分，某一個范圍內(nèi)的數(shù)據(jù)將會被分配到同一個Reduce函數(shù)中，極大地簡化了任務(wù)的處理，有效地提高了效率。經(jīng)過Reduce函數(shù)處理之后，將得到待抽取頁面中有價值內(nèi)容塊的合集存儲到HDFS中，完成Web信息抽取整個操作。

3.2 DOM樹的剪枝融合

在本文采用開源項目HTMLParser將Web頁面轉(zhuǎn)化為DOM樹結(jié)構(gòu)，與其他解析器相比，HTMLParser具有較好的解析功能，相關(guān)的實驗表明它能夠正確、快速地解析大部分的HTML文檔。然而直接對Web頁面轉(zhuǎn)換后的DOM樹進(jìn)行信息抽取會在一定程度上降低方法的準(zhǔn)確率和效率，因為Web頁面中存在著許多無意義的內(nèi)容，如腳本語言、版本信息以及其他類型的標(biāo)簽等，根據(jù)常規(guī)的Web頁面編碼以及W3C相關(guān)規(guī)定，這些標(biāo)簽通常不包含正文內(nèi)容。為了提高信息抽取的效率和準(zhǔn)確率，本文對這些元素進(jìn)行剪枝操作，刪除內(nèi)容如下。

1) head標(biāo)簽及其包含的內(nèi)容，包括網(wǎng)站的標(biāo)題信息和頁面的樣式鏈接。

2) script標(biāo)簽及其包含的內(nèi)容，包括一些內(nèi)嵌的樣式鏈接和樣式文本。

3) 類型為hidden的標(biāo)簽及其包含的內(nèi)容，包括一些隱藏的導(dǎo)航信息、注冊信息等。

4) form標(biāo)簽及其包含的內(nèi)容，包括一些搜索模塊、登錄模塊和注冊模塊等。

5) HTML文檔中的注釋信息、amp;nbsp、命名空間等內(nèi)容。

6) 內(nèi)容為空的標(biāo)簽元素。

7) 其他一些自定義的非常規(guī)元素。

考慮到基于以上規(guī)則進(jìn)行剪枝操作之后的DOM樹中仍然存在大量的節(jié)點，如＜br＞、＜p＞、＜tr＞、＜td＞等標(biāo)簽節(jié)點，這些標(biāo)簽節(jié)點會讓語義上本屬于同一個內(nèi)容塊的文本被分割成2塊，因此，必須對這些節(jié)點進(jìn)行融合，這樣有效避免了由于信息量過短而導(dǎo)致的抽取精度下降等問題。根據(jù)W3C標(biāo)準(zhǔn)，DOM樹中的節(jié)點可分為2類：塊元素和內(nèi)聯(lián)元素，塊元素一般作為容器出現(xiàn)，用來組織結(jié)構(gòu)，它們可以包含內(nèi)聯(lián)元素，正文內(nèi)容以及其他塊元素，如＜h1＞、＜p＞、＜div＞等，通常在頁面編碼的時候，塊元素作為同一語義塊的最大容器，這樣有效避免了由于信息量過短而導(dǎo)致的抽取精度下降等問題；內(nèi)聯(lián)元素只能包含文本內(nèi)容和內(nèi)聯(lián)元素，如＜a＞、＜strong＞、＜em＞等?；谶@樣的標(biāo)準(zhǔn)，本文提出針對DOM樹的融合方法，融合規(guī)則如下。

1) 若內(nèi)聯(lián)元素有子節(jié)點，則將其子節(jié)點與其合并，此子節(jié)點也包括屬性節(jié)點，并標(biāo)記屬性節(jié)點的特征。

2) 若內(nèi)聯(lián)元素為某塊元素的子節(jié)點，且該塊元素有其他子節(jié)點，則將其與塊元素的其他子節(jié)點合并。

3) 存在兄弟關(guān)系或子孫關(guān)系的塊元素均不合并，保證頁面中的每一塊獨立的信息都對應(yīng)DOM樹中的一個節(jié)點。

根據(jù)上述定義的剪枝規(guī)則以及融合規(guī)則給出對應(yīng)的算法。

算法2剪枝融合算法

輸入：DOM樹根節(jié)點

輸出：ST樹

1) Procedure Simplify (root)

2) for each child node in DOMTree do{

3)if node in delete //delete中的元素為剪枝規(guī)則中的元素

4)remove node from DOMTree , continue;

5)else if curnode in fusion1 {//fusion1中的元素為融合規(guī)則1中定義的元素

6)node = node+node’s childnode;

7)remove node’s childnode from DOMTree ,continue;

8) }

9)else if node in fusion2 {//fusion2中的元素為融合規(guī)則2中定義的元素

10) parentnode’s child = node+ parentnode’s otherchild;

11)remove node and parentnode’s otherchild from DOMTree , continue;

12)}

13)else if node in fusion3 //fusion3中的元素為融合規(guī)則3中定義的元素

14)continue the next Simplify(node);

15) }

圖2給出了調(diào)用算法1對DOM樹進(jìn)行剪枝融合的示意，虛線框內(nèi)的元素為待融合的元素，并將簡化后的DOM樹定義為簡單樹ST。

圖2剪枝融合示意

3.3 正文內(nèi)容抽取

正文內(nèi)容抽取是為了有效地對頁面中不同區(qū)域塊中的信息進(jìn)行識別以消除噪音源，從而達(dá)到抽取正文信息的目的。傳統(tǒng)的基于統(tǒng)計的信息抽取方法所定義的密度屬性要么過于復(fù)雜，通常包含多個屬性值，導(dǎo)致最終抽取過程中時間的消耗較多；要么過于簡單，僅僅從單一的文本密度角度出發(fā)，這在傳統(tǒng)的單正文體中是比較合適的，但在UGC類型的頁面中則很難達(dá)到一個令人滿意的結(jié)果，綜合考慮當(dāng)前的現(xiàn)狀，本文從純文本密度和鏈接文本密度角度出發(fā)，首先頁面中信息進(jìn)行如下分類。

1) 純文本信息，包括正文信息、網(wǎng)站的版權(quán)信息以及相關(guān)地址信息等。

2) 鏈接信息，本文中的鏈接信息為廣義上的鏈接，其不僅包括網(wǎng)站的功能性鏈接、廣告鏈接以及正文區(qū)域中相關(guān)鏈接，還包括網(wǎng)站中的各類圖片鏈接（對于圖片鏈接的分析，將所有的相對地址轉(zhuǎn)化為絕對地址）。

在上述分類的基礎(chǔ)上，統(tǒng)計ST樹中純文本數(shù)量以及每個節(jié)點的純文本數(shù)量和鏈接數(shù)量，分別記為text、node.text和node.link，并對ST樹節(jié)點的密度屬性做出如下定義。

定義1純文本密度，其為node.text與text的比值。

它主要表示在ST中，各個節(jié)點所包含的純文本量占總文本量的比重。通過觀察發(fā)現(xiàn)，若網(wǎng)頁的正文區(qū)域是以大量文本構(gòu)成時，節(jié)點值越大，其越有可能包含正文信息內(nèi)容。

定義2鏈接文本密度，其為node.link與node.text的比值。

它主要表示在ST中，各個節(jié)點中鏈接數(shù)量與純文本數(shù)量的比值。通常正文區(qū)域的鏈接前后包含一定量的非鏈接文本而非正文區(qū)域的鏈接所在的節(jié)點通常不具備這樣的特征，它一般不含任何形式的文本或只包含鏈接文本。

此外，考慮到通常單一的基于節(jié)點密度屬性的Web信息抽取方法的仍然難以達(dá)到一個令人滿意的準(zhǔn)確率，本文在節(jié)點密度的基礎(chǔ)上本文定義了內(nèi)容塊的視覺相關(guān)屬性。因為在一般的網(wǎng)頁中有價值的內(nèi)容會集中于網(wǎng)頁中心位置，而其他信息，如廣告信息、導(dǎo)航信息、網(wǎng)站的版權(quán)信息一般會放置于網(wǎng)頁的邊緣，基于這樣的特征，可以通過視覺屬性較好的過濾掉網(wǎng)頁中處于邊緣位置的無價值信息。下面給出ST節(jié)點的視覺屬性定義，具體的屬性值通過CSS文件讀取。

定義3視覺特征量＜top，bottom，width，height＞。該四元組中，top表示頁面分塊與頁面頂端的距離，bottom表示頁面分塊與頁面底端的距離，width表示頁面分塊的寬度，height表示頁面分塊的高度，將這些數(shù)值映射到區(qū)間[0, 1]，當(dāng)top值大于bottom值時，采用＜bottom，width，height＞三元組來衡量內(nèi)容塊的重要性，反之則采用＜top，width，height＞三元組來衡量內(nèi)容塊的重要性。

根據(jù)上述定義的節(jié)點密度和視覺特征量以及相關(guān)抽取規(guī)則給出對應(yīng)的算法。

算法3正文內(nèi)容抽取算法

輸入：ST樹

輸出：頁面正文區(qū)域內(nèi)容

1) Procedure Extraction(ST)

2) get(ST’s leafnode);

3)for each leafnode in ST do{

4)if top＞bottom{

5)if ＜bottom, width, height＞ is not in Δ3//Δ3為節(jié)點視覺特征量閾值集合

6)remove leafnode from ST;

7)else

8)density (leafnode);

9)}

10) else {

11) if ＜top, width, height＞ is not in Δ4//Δ4為節(jié)點視覺特征量閾值集合

12) remove leafnode from ST;

13) else

14) density (leafnode);

15)}

16) function density(leafnode){

17) if1ρ＜Δ1 //Δ1表示純文本密度閾值

18) remove leafnode from ST;

19) else ifρ2＞Δ2//Δ2表示鏈接文本密度閾值

20) remove leafnode from ST;

21)}

22)}

3.4 基于節(jié)點內(nèi)容特征的Web信息抽取

經(jīng)過上述的預(yù)處理操作，ST中的節(jié)點將只包含正文內(nèi)容，由于正文內(nèi)容的主體也有可能由一些廣告內(nèi)容、灌水內(nèi)容以及其他一些價值率較低的內(nèi)容構(gòu)成，因此在下一步的工作中需要對這些信息進(jìn)行有效的分類，以提高信息的價值率。本文對正文中的內(nèi)容給出如下分類。

第1類：網(wǎng)頁的主題由廣告內(nèi)容，灌水內(nèi)容以及其他一些價值率較低的內(nèi)容構(gòu)成，對于這樣的頁面進(jìn)行整體過濾。

第2類：網(wǎng)頁主題的內(nèi)容具有一定的抽取價值，但是主題下存在一些價值率較低的回復(fù)，在保留主題基礎(chǔ)上，對這些回復(fù)進(jìn)行過濾。

基于上述分類，在預(yù)處理的基礎(chǔ)上引用基于樸素貝葉斯的文本分類模型來完成最終的抽取工作，并選擇停用詞表和特征項選擇的方法對正文內(nèi)容進(jìn)行有效的降維。

1) 停用詞表：正文中的連接詞、代詞等對內(nèi)容分類不僅沒有作用，還會起到干擾，所以本文建立一個停用詞表，將這類詞存放其中，若正文中出現(xiàn)停用詞表中的詞則將其刪除。

2) 特征項選擇：從高維度向量空間中選取對文本分類有效的特征項Xi，從而達(dá)到對向量空間降維的目的，本文采用信息增益的方法進(jìn)行特征項選擇。

將ST樹中節(jié)點包含的文本信息記為d，由n個屬性的測量值表示，其特征向量為T={x1,x2, x3,…,xn?1, xn}，xi∈{0, 1}，xi為d的特征項Xi的特征值，若xi=1，表示其特征項在d中出現(xiàn)，xi=0則表示特征項沒有在d中出現(xiàn)，根據(jù)式(1)，可知所選取的節(jié)點屬于cj(cj∈C，C為正文內(nèi)容的類別)的概率為

由全概率公式得

大量的文本信息將導(dǎo)致構(gòu)成向量X的特征值非常多，且特征值之間可能存在一定的關(guān)聯(lián)，直接由上述公式計算出d的歸屬概率是非常復(fù)雜的，因此，在貝葉斯定理的基礎(chǔ)上采用樸素貝葉斯定理，假定各屬性之間的相互影響是獨立的，即從d中提取出來的詞之間是沒有關(guān)聯(lián)的，通過這種假設(shè)，樸素貝葉斯模型不僅表現(xiàn)出高速度，并且也有較高的準(zhǔn)確率，則由此假設(shè)可得

由上述公式，可推演出d屬于某一類的概率的樸素貝葉斯公式為

根據(jù)式(7)，可以推算出內(nèi)容為無價值的概率為P(c0|d)，內(nèi)容為有價值的概率為P(c1|d)，若P(c0|d)＞P(c1|d)，則判定當(dāng)前節(jié)點包含的內(nèi)容為無價值的。

若ST樹中的首個節(jié)點包含的內(nèi)容被判定為無價值，則表示當(dāng)前抽取的網(wǎng)頁屬于第1種類型，停止對當(dāng)前Web頁面的抽取工作，將網(wǎng)頁從本地刪除，若非首節(jié)點內(nèi)容被判定為無價值內(nèi)容，則表示當(dāng)前抽取的網(wǎng)頁屬于第2種類型，刪除當(dāng)前被判定為無價值內(nèi)容的節(jié)點。

3.5 信息抽取流程

基于上述提出的相關(guān)算法與框架，下面給出基于節(jié)點屬性與正文內(nèi)容的海量Web信息抽取方法完整流程。

步驟1：將本地數(shù)據(jù)庫中Web頁面加載到HDFS中。

步驟2：通過HDFS將數(shù)據(jù)分配給每個Map節(jié)點，并將完整的抽取算法映射到Map節(jié)點。

步驟3：調(diào)用HTMLParser將網(wǎng)頁轉(zhuǎn)化為DOM樹。

步驟4：調(diào)用剪枝融合算法對DOM樹進(jìn)行簡化操作，形成簡單樹ST。

步驟5：根據(jù)DOM樹節(jié)點屬性對ST樹中的節(jié)點進(jìn)行篩選分類，實現(xiàn)Web信息的預(yù)處理。

步驟6：引入基于樸素貝葉斯的文本分類模型，根據(jù)節(jié)點內(nèi)容，在預(yù)處理的基礎(chǔ)上實現(xiàn)完成信息最終的抽取工作。

步驟7：Reduce函數(shù)將抽取出的內(nèi)容塊以鍵值對的形式輸出，存儲于本地數(shù)據(jù)庫中。

4 實驗結(jié)果與分析

為體現(xiàn)本文提出的信息抽取方法的性能（準(zhǔn)確率和運行效率），將實驗分為2部分：實驗1將本文提出的方法與Sun等[9]中提出的算法以及Wang等[11]提出的算法進(jìn)行對比，他們的算法分別從是從DOM樹的角度以及貝葉斯的角度進(jìn)行信息的抽取，因此，可以通過對比3種方法各自的Web信息抽取結(jié)果來驗證算法的準(zhǔn)確率；實驗2將驗證本文提出的基于MapReduce的海量Web信息抽取的可行性，分別從數(shù)據(jù)的擴(kuò)展性和機(jī)器的擴(kuò)展性2個角度，通過計算相應(yīng)的加速比和時間消耗來評估本文方法的性能。

4.1 數(shù)據(jù)集

為了達(dá)到較好的實驗效果，本文以爬蟲的方式從互聯(lián)網(wǎng)上收集約10000張頁面的數(shù)據(jù)量，分別來自百度貼吧、CSDN、小木蟲等主流站點，頁面內(nèi)容涵蓋了社會、計算機(jī)編碼、學(xué)術(shù)科研等多種類型，這些網(wǎng)站的頁面結(jié)構(gòu)與風(fēng)格迥異，有助于充分地驗證本文方法的準(zhǔn)確性、高效性以及頑健性。實驗1是為了驗證3種方法對不同結(jié)構(gòu)的頁面的抽取效果，將從10000張頁面中隨機(jī)挑選出240個頁面進(jìn)行相關(guān)的抽取工作。實驗2首先驗證本文方法的機(jī)器可擴(kuò)展性，在具體的實驗環(huán)境中將系統(tǒng)的節(jié)點數(shù)分為設(shè)為1、2、4、6、8個，抽取對象均為當(dāng)前加載到本地的10000張頁面，其次驗證本文方法的數(shù)據(jù)可擴(kuò)展性，具體的實驗環(huán)境中設(shè)立8個節(jié)點，處理的頁面量分別為100、500、2000、5000、8000張復(fù)雜度相差無幾的頁面。

4.2 評價標(biāo)準(zhǔn)

對于DOM樹的簡化過程，本文采用平均融合率fusionRate來驗證此過程的必要性，其計算式如下

其中，STNum為DOM樹中被剪枝融合掉的節(jié)點數(shù)量，DOMNum為剪枝融合之前DOM樹的節(jié)點數(shù)量。此外，每一個DOM樹可能對應(yīng)于多個簡單樹，因此，本文將剪枝融合得到的簡單樹數(shù)量定義為n，原始的DOM樹數(shù)量定義為N。

在Web信息的預(yù)處理實驗中，采用準(zhǔn)確率（Precision）、召回率（Recall）以及F-Score這3種指標(biāo)來評價實驗結(jié)果。準(zhǔn)確率的計算式為

TP表示抽取出的信息中有效信息量，F(xiàn)P表示抽取出的信息中包含的無效信息量。召回率計算式為

TP為抽取出的信息中有效信息量，F(xiàn)N表示未被抽取出的信息中有效信息量。F-Score計算式為

其中，P和R分別表示為信息抽取的準(zhǔn)確率和召回率。

4.3 結(jié)果與分析

實驗1Web信息抽取準(zhǔn)確率驗證

表1給出了實驗過程中DOM在簡化前后節(jié)點數(shù)量的變化情況，隨著實驗數(shù)據(jù)量的遞增，DOM樹的平均節(jié)點數(shù)基本維持在1700個左右，而經(jīng)過處理后的DOM樹只有大約600個節(jié)點，平均融合率達(dá)到了62.8%，極大簡化了后續(xù)信息抽取工作，一定程度上提高了方法的執(zhí)行效率，充分說明了預(yù)處理階段對DOM樹進(jìn)行剪枝融合的必要性與有效性。

表1DOM樹的剪枝融合結(jié)果

此外，從實驗1中的240張頁面中隨機(jī)地抽取50張頁面進(jìn)行正文內(nèi)容損耗統(tǒng)計，統(tǒng)計結(jié)果表明本文所提出的剪枝融合方法不會對損害正文區(qū)域的有效內(nèi)容，并且也不會對隸屬于不同語義的內(nèi)容進(jìn)行錯誤融合。

表2給出了本文算法、Sun等[10]提出的算法以及Wang等[11]提出的算法抽取結(jié)果，從數(shù)據(jù)中可以看到，3類信息抽取方法的召回率基本相近，但是在準(zhǔn)確率上，本文提出的方法要明顯優(yōu)于其他2種方法，并且得到了最高的F1值，主要原因如下。

1) 設(shè)計了剪枝融合算法，對DOM樹進(jìn)行了簡化操作，過濾了頁面中大量無效信息塊，并且對語義上屬于同一個內(nèi)容塊的信息進(jìn)行了融合，有效降低了信息量較少的內(nèi)容塊對信息抽取造成的干擾。

2) 將DOM樹節(jié)點的密度與視覺屬性相結(jié)合，可完成對頁面中鏈接、圖片、文本等各種信息的抽取，并且能對正文區(qū)域中發(fā)布者的身份、頭像、個性簽名等無效信息進(jìn)行有效的過濾。

3) 引入基于樸素貝葉斯的文本分類模型，對正文區(qū)域中的無價值內(nèi)容進(jìn)行了分類過濾，有效地提高了信息的價值率。

實驗2基于MapReduce的可行性驗證

為了觀察方法的并行化處理框架在集群規(guī)模增大時其性能變化情況，進(jìn)行了系統(tǒng)的可擴(kuò)展性實驗。在實驗中采用本地的10000張Web頁面進(jìn)行抽取工作，具體的集群中將分別采用1、2、4、6、8個計算節(jié)點，實驗結(jié)果數(shù)據(jù)處理后如表3所示。

表2Web信息抽取結(jié)果

在表3中設(shè)立了總時間消耗和平均時間消耗，并通過這2個度量屬性計算出相應(yīng)的加速比，將其作為衡量本文的分布式系統(tǒng)可擴(kuò)展性的重要指標(biāo)。從具體的數(shù)據(jù)中可以看到在前6個節(jié)點之前隨著系統(tǒng)環(huán)境中計算節(jié)點的增加其對應(yīng)的加速比幾乎是呈線性化增長的，但超過6個節(jié)點以后其對應(yīng)的加速比逐漸放緩，這主要是因為當(dāng)節(jié)點數(shù)增加整個算法的并行化的額外開銷也增加，在當(dāng)前數(shù)據(jù)量較小的情況下，并不能較好地體現(xiàn)多節(jié)點高度并行的處理優(yōu)勢。

但總體上來說，表3中的數(shù)據(jù)可以說明隨著處理器數(shù)量的增長，系統(tǒng)對頁面處理的時間下降以及加速比的增長都十分顯著，在一定程度上說明了本文提出的方法具備較好的系統(tǒng)可擴(kuò)展性。

表3系統(tǒng)可擴(kuò)展性驗證

在對算法的系統(tǒng)可擴(kuò)展性進(jìn)行了相關(guān)驗證的同時，本文對方法的數(shù)據(jù)可擴(kuò)展性也進(jìn)行了相關(guān)的實驗，在具體的實驗環(huán)境中，通過人工篩選的方式盡可能地選用復(fù)雜度相同但數(shù)據(jù)規(guī)模不同的5組數(shù)據(jù)，數(shù)據(jù)的規(guī)模從100張頁面到8000張頁面，對不同規(guī)模的數(shù)據(jù)分別做2組實驗，取其平均值作為最終的耗時。

在表4中設(shè)立了總時間消耗和平均時間消耗并將其作為系統(tǒng)數(shù)據(jù)可擴(kuò)展性的評價指標(biāo)。從具體的數(shù)據(jù)中可以看到在處理頁面的數(shù)量從100張增加到2000張的過程中，頁面的平均處理時間有一個減少的過程，在2000張頁面之后，頁面的平均處理時間趨向一個穩(wěn)定的值，這主要是因為在數(shù)據(jù)量較少時，算法的并行化的額外開銷在總體耗時的比重過大，其在一定程度上影響了抽取的效率。

但總體上來說，表4中的數(shù)據(jù)在一定程度上可以較好地說明本文提出的方法在面對頁面數(shù)量不斷增長時能夠表現(xiàn)出較好的抽取性能，有效地驗證了方法的數(shù)據(jù)可擴(kuò)展性。

表4數(shù)據(jù)可擴(kuò)展性驗證

5 結(jié)束語

如何有效地抽取Web頁面中有價值的內(nèi)容是當(dāng)前Web研究領(lǐng)域的熱點問題，本文根據(jù)現(xiàn)有Web信息抽取方法在大數(shù)據(jù)環(huán)境下的不足，提出一種基于節(jié)點屬性與內(nèi)容的海量Web信息并行抽取方法。該方法根據(jù)當(dāng)前Web前端編碼的特點以及W3C的相關(guān)規(guī)定，充分考慮節(jié)點的視覺與密度屬性以及節(jié)點包含的內(nèi)容的特點，可完全獨立于Web頁面的結(jié)構(gòu)，相關(guān)實驗表明了本文的方法是高效且可擴(kuò)展的。

在未來的工作中，將對本文提出的方法進(jìn)行深入研究，進(jìn)一步優(yōu)化MapReduce抽取框架，提高系統(tǒng)的性能。

[1]GRISHMAN R. Information extraction: techniques and challenges［EB/OL］. http:// cs.nyu.edu/cs/faculty/grishman/proteus.htm, 1997.

[2]李蕾, 周延泉, 王菁華.基于全信息的中文信息抽取系統(tǒng)及應(yīng)用[J].北京郵電大學(xué)學(xué)報, 2005, 28(6): 48-51.LI L, ZHOU Y Q, WANG J H. Comprehensive information based chinese information extraction system and application[J]. Journal of Beijing University of Posts and Telecommunications, 2005, 28(6):48-51.

[3]黃詩琳, 鄭小琳, 陳德人.針對產(chǎn)品命名實體識別的半監(jiān)督學(xué)習(xí)方法[J]. 北京郵電大學(xué)學(xué)報, 2013, 36(2): 20-23.HUANG S L, ZHENG X L, CHEN D R. A semi-supervised learning method for product named entity recognition[J]. Journal of Beijing University of Posts and Telecommunications, 2013, 36(2): 20-23.

[4]秦兵, 劉安安, 劉挺. 無指導(dǎo)的中文開放式實體關(guān)系抽取[J]. 計算機(jī)研究與發(fā)展, 2015, 52(5):1029-1035.QIN B, LIU A A, LIU T. Unsupervised Chinese open entity relation extraction[J]. Journal of Computer Research and Development,2015,52(5):1029-1035.

[5]李天潁, 劉璘, 趙德旺, 等. 一種基于依存文法的需求文本策略依賴關(guān)系抽取方法[J]. 計算機(jī)學(xué)報, 2013,31(1):54-62.LI T Y, LIU L, ZHAO D W, et al. Eliciting relations from requirements text based on dependency analysis[J]. Journal of Computers,2013, 31(1): 54-62.

[6]DENG C, YU S P, WEN J R. VIPS: a vision-based page segmentation[R]//Microsoft Technical Report, MSR-TR_ 203-79,2003.

[7]NEIL A, HONG J. Visually extracting data records from the deep-Web[C]//WWW 2013. Rio, IEEE Press, 2013: 1233-1238.

[8]NARWAL N. Improving Web data extraction by noise removal[C]//ARTCom 2013. Bangalore, IET, 2013: 388-395.

[9]SUN F, SONG D, LIAO L. DOM based content extraction via text density[C]//ACM SIGIR 2011. Beijing, 2011: 245-254.

[10]張乃洲, 曹薇, 李石君. 一種基于節(jié)點密度分割和標(biāo)簽傳播的Web頁面挖掘方法[J]. 計算機(jī)學(xué)報, 2015, 38(2): 349-364.ZHANG N Z, CAO W, LI S J. A method based on node density segmentation and label propagation for mining Web page[J]. Journal of Computers, 2015, 38(2): 349-364.

[11]WANG J B, WANG L Z, GAO W L, et al. Chinese Web content extraction based on naive bayes model[C]// International Federation for Information Processing IFIP. 2014: 404-413.

[12]KRISHNA S S, DATTATRAYA J S. Schema inference and data extraction from templatized Web pages[C]//ICPC, 2015: 1-6.

[13]BHUIYAN M A, ALHASAN M. FSM-H: frequent subgraph mining algorithm in Hadoop[C]//Big Data. 2014: 9-16.

[14]JIN S Y, BOULWARE D, KIMMEY D. A parallel spatial co-location mining algorithm based on MapReduce[C]//Big Data. 2014: 25-31.

Information extraction from massive Web pages based on node property and text content

WANG Hai-yan1,2, CAO Pan1
(1. School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;2. Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China)

To address the problem of extracting valuable information from massive Web pages in big data environments, a novel information extraction method based on node property and text content for massive Web pages was put forward. Web pages were converted into a document object model (DOM) tree, and a pruning and fusion algorithm was introduced to simplify the DOM tree. For each node in the DOM tree, both density property and vision property was defined and Web pages were pretreated based on these property values. A MapReduce framework was employed to realize parallel information extraction from massive Web pages. Simulation and experimental results demonstrate that the proposed extraction method can not only achieve better performance but also have higher scalability compared with other methods.

Web information, extraction, MapReduce, DOM tree

s:The National Natural Science Foundation of China (No.61201163, No.61672297), Six Talent Peaks Project in Jiangsu Province (No.2013-JY-022), 333 High Level Personnel Training Project in Jiangsu Province

TP393.07

A

10.11959/j.issn.1000-436x.2016190

2015-11-16；

2016-05-24

國家自然科學(xué)基金資助項目（No.61201163, No.61672297）；“六大人才高峰”基金資助項目（No.2013-JY-022）；江蘇省“333高層次人才培養(yǎng)工程”基金資助項目

王海艷（1974-），女，江蘇東臺人，南京郵電大學(xué)教授，主要研究方向為服務(wù)計算、可信計算、大數(shù)據(jù)應(yīng)用與云計算技術(shù)、隱私保護(hù)技術(shù)。

曹攀（1991-），男，江蘇鎮(zhèn)江人，南京郵電大學(xué)碩士生，主要研究方向為云計算與物聯(lián)網(wǎng)技術(shù)。