王海艷，曹攀

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

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

王海艷1,2，曹攀1

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

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

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

1 引言

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

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

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

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

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

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

2 相關(guān)概念

2.1 HTML DOM

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

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

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

2.2 樸素貝葉斯定理

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

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

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

3 海量Web信息抽取方法

3.1 基于MapReduce的抽取框架

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

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

算法1Map過程

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

輸出數(shù)據(jù)格式為＜key, value＞，具體函數(shù)中為＜pageNumber, content＞，pageNumber為經(jīng)過抽取后的頁面序列號(hào)，而content則是從頁面中抽取出來的有價(jià)值內(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é)點(diǎn)屬性Web信息預(yù)處理

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

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

9)}

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

3.2 DOM樹的剪枝融合

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

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

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

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

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

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

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

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

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

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

算法2剪枝融合算法

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

輸出：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對(duì)DOM樹進(jìn)行剪枝融合的示意，虛線框內(nèi)的元素為待融合的元素，并將簡(jiǎn)化后的DOM樹定義為簡(jiǎn)單樹ST。

圖2剪枝融合示意

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

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

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

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

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

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

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

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

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

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

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

根據(jù)上述定義的節(jié)點(diǎn)密度和視覺特征量以及相關(guān)抽取規(guī)則給出對(duì)應(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é)點(diǎn)視覺特征量閾值集合

6)remove leafnode from ST;

7)else

8)density (leafnode);

9)}

10) else {

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

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é)點(diǎn)內(nèi)容特征的Web信息抽取

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

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

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

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

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

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

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

由全概率公式得

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

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

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

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

3.5 信息抽取流程

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

對(duì)于DOM樹的簡(jiǎn)化過程，本文采用平均融合率fusionRate來驗(yàn)證此過程的必要性，其計(jì)算式如下

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

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

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

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

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

4.3 結(jié)果與分析

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

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

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

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

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

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

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

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

實(shí)驗(yàn)2基于MapReduce的可行性驗(yàn)證

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

在未來的工作中，將對(duì)本文提出的方法進(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é)報(bào), 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]黃詩琳, 鄭小琳, 陳德人.針對(duì)產(chǎn)品命名實(shí)體識(shí)別的半監(jiān)督學(xué)習(xí)方法[J]. 北京郵電大學(xué)學(xué)報(bào), 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)的中文開放式實(shí)體關(guān)系抽取[J]. 計(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ì)算機(jī)學(xué)報(bào), 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é)點(diǎn)密度分割和標(biāo)簽傳播的Web頁面挖掘方法[J]. 計(jì)算機(jī)學(xué)報(bào), 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é)基金資助項(xiàng)目（No.61201163, No.61672297）；“六大人才高峰”基金資助項(xiàng)目（No.2013-JY-022）；江蘇省“333高層次人才培養(yǎng)工程”基金資助項(xiàng)目

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

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