網(wǎng)絡(luò)信息抽取技術(shù)分析與比較

宋鑫瑩　趙鐵軍

摘要：隨著互聯(lián)網(wǎng)爆炸式的發(fā)展和普及，網(wǎng)絡(luò)信息已經(jīng)成為了一種寶貴的信息數(shù)據(jù)資源。海量的網(wǎng)絡(luò)數(shù)據(jù)使得數(shù)據(jù)分析與挖掘系統(tǒng)進(jìn)入了一個(gè)新時(shí)代，越來(lái)越多的網(wǎng)絡(luò)應(yīng)用系統(tǒng)需要對(duì)來(lái)自不同數(shù)據(jù)源的結(jié)構(gòu)化數(shù)據(jù)進(jìn)行抽取、挖掘和整合。然而，由于網(wǎng)頁(yè)文檔的半結(jié)構(gòu)化性質(zhì)，網(wǎng)頁(yè)上呈現(xiàn)的數(shù)據(jù)往往不能被機(jī)器自動(dòng)地抽取和理解，因此，網(wǎng)絡(luò)信息抽取的研究目標(biāo)在于提取網(wǎng)頁(yè)的結(jié)構(gòu)化數(shù)據(jù)?；ヂ?lián)網(wǎng)數(shù)據(jù)的海量規(guī)模與高度異構(gòu)，為網(wǎng)絡(luò)信息抽取帶來(lái)了巨大的挑戰(zhàn)。分析和總結(jié)了近年來(lái)網(wǎng)絡(luò)信息抽取相關(guān)的研究與工作，剖析了各個(gè)工作的優(yōu)勢(shì)和局限，并進(jìn)一步作了綜合的分類(lèi)與比較。

關(guān)鍵詞：網(wǎng)絡(luò)信息抽??； 包裝器； 模板

中圖分類(lèi)號(hào)：TP391 [KG*2]文獻(xiàn)標(biāo)識(shí)碼：A[KG*2][HT5”H]文章編號(hào)：2095-2163（2013）05-0024-05

0引言

互聯(lián)網(wǎng)已經(jīng)成為一種公用信息的重要載體。在過(guò)去的二十年間，隨著互聯(lián)網(wǎng)的爆炸式的發(fā)展和大眾型普及，涌現(xiàn)了眾多應(yīng)用網(wǎng)站，如新聞、博客、微博、社交網(wǎng)絡(luò)、點(diǎn)評(píng)網(wǎng)站、在線論壇等。數(shù)量龐大的新聞媒體、商家機(jī)構(gòu)和普通用戶(hù)寫(xiě)手正不斷、不停地在網(wǎng)絡(luò)上發(fā)布信息，構(gòu)成了一個(gè)海量的、寶貴的知識(shí)信息資源。

盡管互聯(lián)網(wǎng)已成為龐大的數(shù)據(jù)金礦，但HTML網(wǎng)頁(yè)——這一網(wǎng)絡(luò)信息主要呈現(xiàn)方式——的設(shè)計(jì)初衷是供用戶(hù)閱讀，而非由機(jī)器讀取，人們對(duì)網(wǎng)絡(luò)數(shù)據(jù)信息的獲取都僅限于網(wǎng)頁(yè)瀏覽或是搜索引擎檢索[1]。這種表層的網(wǎng)頁(yè)文本獲取方式僅適于簡(jiǎn)單的文檔檢索任務(wù)，無(wú)法勝任更復(fù)雜、更精確的網(wǎng)絡(luò)數(shù)據(jù)分析與挖掘任務(wù)。例如構(gòu)建社區(qū)論壇的專(zhuān)家搜索系統(tǒng)，需要抽取帖子的發(fā)帖人、發(fā)帖時(shí)間、帖子內(nèi)容等元數(shù)據(jù)信息。圖 1為網(wǎng)絡(luò)論壇頁(yè)面的示意圖，共包含兩個(gè)論壇帖子（虛線框所示，稱(chēng)為數(shù)據(jù)記錄），每個(gè)帖子又可分為若干數(shù)據(jù)單元，其含義由相應(yīng)的語(yǔ)義標(biāo)簽進(jìn)行表明和指示（如時(shí)間、作者、內(nèi)容等）。數(shù)據(jù)記錄、數(shù)據(jù)單元及單元的語(yǔ)義標(biāo)簽，即構(gòu)成了網(wǎng)頁(yè)呈現(xiàn)的結(jié)構(gòu)化數(shù)據(jù)，如圖 2所示。基于網(wǎng)絡(luò)數(shù)據(jù)的大多數(shù)搜索和挖掘應(yīng)用，都依賴(lài)于由輸入網(wǎng)面轉(zhuǎn)換而來(lái)的結(jié)構(gòu)化的數(shù)據(jù)。由互聯(lián)網(wǎng)網(wǎng)頁(yè)中抽取結(jié)構(gòu)化數(shù)據(jù)的過(guò)程稱(chēng)為網(wǎng)絡(luò)信息抽?。╓eb Information Extraction）[1，2]。

網(wǎng)絡(luò)信息抽取任務(wù)不同于傳統(tǒng)的信息抽?。↖E）任務(wù)。傳統(tǒng)信息抽取的目的在于從自由文本中抽取數(shù)據(jù)，使用自然語(yǔ)言處理（Natural Language Processing）的技術(shù)，如詞性標(biāo)注、語(yǔ)法分析等。而網(wǎng)絡(luò)信息抽取則從網(wǎng)頁(yè)文檔中抽取數(shù)據(jù)。網(wǎng)頁(yè)文檔是一種半結(jié)構(gòu)化文檔，通常是由服務(wù)器端的后臺(tái)程序或腳本自動(dòng)生成，含有特定的HTML標(biāo)簽作為分隔標(biāo)志，但整體缺乏嚴(yán)格且統(tǒng)一的語(yǔ)法和語(yǔ)義信息，包含了表現(xiàn)上的一定自由度。不同于高度結(jié)構(gòu)化的文檔（如XML），半結(jié)構(gòu)化的文檔并不能由機(jī)器直接讀取。而互聯(lián)網(wǎng)數(shù)據(jù)的海量規(guī)模與高度異構(gòu)特征，也為網(wǎng)絡(luò)信息抽取帶來(lái)了巨大的挑戰(zhàn)。因此，開(kāi)展網(wǎng)絡(luò)信息抽取的研究工作具有相當(dāng)?shù)谋匾院蛯?shí)用性。

1主要工作介紹和分析按照模型方法的自動(dòng)化程度，可以將網(wǎng)絡(luò)信息抽取工作

分為人工化、半自動(dòng)化和全自動(dòng)化三類(lèi)。本節(jié)將從這三個(gè)方面，根據(jù)模型的提出時(shí)間，依次介紹相關(guān)工作，并分析各自的優(yōu)勢(shì)和局限

1.1人工化的網(wǎng)絡(luò)信息抽取方法

早期的網(wǎng)絡(luò)信息抽取工作，依靠人工編寫(xiě)的過(guò)程化程序來(lái)完成，如TSIMMIS[3]，Minerva[4]等。編寫(xiě)的程序依賴(lài)于特定的網(wǎng)頁(yè)結(jié)構(gòu)，無(wú)法移植于其它結(jié)構(gòu)的網(wǎng)頁(yè)，且需要一定的計(jì)算機(jī)程序?qū)I(yè)知識(shí)，限制了方法的應(yīng)用和推廣。因此，這種方法并不適于大規(guī)模的網(wǎng)絡(luò)信息抽取工作，已逐漸喪失其使用價(jià)值。

[HTH]1.2半自動(dòng)化的網(wǎng)絡(luò)信息抽取方法[HTSS]

半自動(dòng)化的方法，需要一定量的標(biāo)注數(shù)據(jù)，因此也需要一定的人力成本。然而與人工化的方法不同，半自動(dòng)化方法的標(biāo)注任務(wù)簡(jiǎn)單直觀，標(biāo)注員經(jīng)過(guò)簡(jiǎn)單訓(xùn)練即能勝任，并不需要計(jì)算機(jī)程序設(shè)計(jì)的專(zhuān)業(yè)知識(shí)，所以半結(jié)構(gòu)化的方法能收集得到較大規(guī)模的標(biāo)注數(shù)據(jù)，處理更大規(guī)模的抽取任務(wù)。

一類(lèi)典型的半自動(dòng)化方法，是利用標(biāo)注數(shù)據(jù)，通過(guò)歸納推導(dǎo)，構(gòu)建得到包裝器（Wrapper）。包裝器是信息集成系統(tǒng)中的一個(gè)模塊，能抽取網(wǎng)頁(yè)數(shù)據(jù)并將其轉(zhuǎn)換為結(jié)構(gòu)化數(shù)據(jù)（圖 2）。具體可分為兩種模式：基于抽取模式規(guī)則[5，6]和基于模板樹(shù)匹配[7，8]。這兩種模式均刻畫(huà)了網(wǎng)頁(yè)的模板結(jié)構(gòu)，但卻只適用于相同結(jié)構(gòu)的網(wǎng)頁(yè)，因此被稱(chēng)作（網(wǎng)站）模板相關(guān)的工作。當(dāng)處理新結(jié)構(gòu)的網(wǎng)站時(shí)，仍然需要再次標(biāo)注。另外，模板的檢測(cè)和維護(hù)也是重要的研究問(wèn)題[9]。只是數(shù)據(jù)標(biāo)注和模板維護(hù)都需要巨大的成本，因此，這種方法不適用于大規(guī)模的網(wǎng)絡(luò)信息抽取工作。

為了克服模板化方法對(duì)網(wǎng)頁(yè)結(jié)構(gòu)的高依賴(lài)性，近年來(lái)半自動(dòng)化的研究工作相繼提出了（網(wǎng)站）模板無(wú)關(guān)的方法[10，11]。利用機(jī)器學(xué)習(xí)模型理論，挖掘領(lǐng)域內(nèi)通用的、與網(wǎng)頁(yè)結(jié)構(gòu)無(wú)關(guān)的特征，從標(biāo)注數(shù)據(jù)中訓(xùn)練得出統(tǒng)計(jì)模型。訓(xùn)練得到的模型不依賴(lài)于特定網(wǎng)站或特定的網(wǎng)頁(yè)HTML結(jié)構(gòu)，對(duì)同領(lǐng)域的多個(gè)網(wǎng)站具有普適性。然而，該模型仍然依賴(lài)于領(lǐng)域相關(guān)的標(biāo)注數(shù)據(jù)和復(fù)雜的分類(lèi)特征，當(dāng)在不同領(lǐng)域應(yīng)用時(shí)，頁(yè)需要重新標(biāo)注數(shù)據(jù)、修改特征甚至更換模型方法。

如引言所述，結(jié)構(gòu)化數(shù)據(jù)一般包含三個(gè)層次：數(shù)據(jù)記錄、單元和語(yǔ)義標(biāo)簽。半自動(dòng)化方法往往將其中多個(gè)級(jí)別的抽取工作合并為一個(gè)步驟，以盡快利用數(shù)據(jù)單元的豐富特征信息。然而，這也導(dǎo)致了該類(lèi)方法的模板或領(lǐng)域局限性。

[HTH]1.3全自動(dòng)化的網(wǎng)絡(luò)信息抽取方法[HTSS]

全自動(dòng)化方法不需要標(biāo)注數(shù)據(jù)，與半自動(dòng)的方法相比具有更大的優(yōu)勢(shì)。早期工作基于先驗(yàn)的啟發(fā)式規(guī)則，包括Embley等[12]和OMINI[13]。然而，這類(lèi)方法過(guò)度依賴(lài)于預(yù)先設(shè)計(jì)的啟發(fā)式規(guī)則，難于擴(kuò)展，抽取效果也不夠理想。

其[JP2]后跟進(jìn)的研究主要采用HTML標(biāo)簽重復(fù)序列模式識(shí)別的方法，包括IPEAD[14]和 Dela[15]，但在實(shí)際應(yīng)用中仍需要人工選擇有效識(shí)別模式。另外，依賴(lài)的HTML標(biāo)簽序列模式，并不能較好地反映HTML網(wǎng)頁(yè)標(biāo)簽所展示的層次結(jié)構(gòu)信息。[JP]

近年來(lái)，主流研究演進(jìn)為利用網(wǎng)頁(yè)DOM樹(shù)（Document Object Model）識(shí)別重復(fù)相似子樹(shù)的方法。與HTML標(biāo)簽序列相比，DOM樹(shù)能更好地反應(yīng)HTML網(wǎng)頁(yè)內(nèi)在的層次結(jié)構(gòu)信息。MDR[16]對(duì)數(shù)據(jù)對(duì)象結(jié)構(gòu)做了典型的簡(jiǎn)單假設(shè)，并通過(guò)檢測(cè)相似的DOM子樹(shù)識(shí)別得到數(shù)據(jù)記錄，獲得了良好的抽取效果。后續(xù)工作包括DEPTA[17]，NET[18]，ViPER[19]，MiBAT[20]，RST[21]等。TPC[22]提出了一個(gè)基于DOM樹(shù)路徑特征挖掘的方法，對(duì)DOM樹(shù)上所有從樹(shù)根到標(biāo)簽的路徑展現(xiàn)模式實(shí)現(xiàn)了聚類(lèi)，同一聚類(lèi)下若干重復(fù)交疊出現(xiàn)的樹(shù)路徑則組成一組數(shù)據(jù)記錄。

另一類(lèi)全自動(dòng)方法利用了頁(yè)面的視覺(jué)信息。Cai等[23]提出了VIPS算法，通過(guò)視覺(jué)布局，將輸入網(wǎng)頁(yè)分隔成不同部分。ViNTs[24]則利用了邊界的視覺(jué)曲折變化特征，抽取搜索結(jié)果記錄。ViDE[25]只是單純利用了網(wǎng)頁(yè)的視覺(jué)信息。然而，網(wǎng)頁(yè)的視覺(jué)信息特征往往需要額外的資源文件（如Cascading Style Sheets （CSS）文件），用以計(jì)算網(wǎng)頁(yè)元素的位置及大小信息，因此在實(shí)際應(yīng)用中具有一定的局限性。

還有一類(lèi)方法利用特定領(lǐng)域的本體知識(shí)以輔助數(shù)據(jù)抽取工作。例如，Embley等[12]將領(lǐng)域本體知識(shí)作為一種啟發(fā)式規(guī)則。MiBAT[20]則將自動(dòng)化的數(shù)據(jù)抽取方法與通用的領(lǐng)域約束相結(jié)合，由此提高數(shù)據(jù)抽取精度。

抽取的數(shù)據(jù)對(duì)象可以分為兩種類(lèi)型，即簡(jiǎn)單的關(guān)系K元組（K表示每個(gè)數(shù)據(jù)記錄中含有的數(shù)據(jù)單元數(shù)量）和復(fù)雜的、具有嵌套層次結(jié)構(gòu)的數(shù)據(jù)對(duì)象。Dela[15]研究識(shí)別嵌套的序列模式，NET[18]利用DOM樹(shù)后序編歷過(guò)程識(shí)別每一級(jí)的層次嵌套結(jié)構(gòu)，TPC[22]和RST[21]利用啟發(fā)式后續(xù)處理來(lái)檢測(cè)嵌套結(jié)構(gòu)。

以上研究工作主要集中于數(shù)據(jù)記錄的信息抽?。m然有些工作同時(shí)也完成了數(shù)據(jù)單元抽取），另外一些工作則集中研究數(shù)據(jù)單元的抽取。DEPTA[17]提出了局部樹(shù)匹配以對(duì)齊數(shù)據(jù)單元，Lu等[26]則對(duì)數(shù)據(jù)單元進(jìn)行了相似性聚類(lèi)。Zhao等[27]討論了DOM樹(shù)結(jié)構(gòu)與數(shù)據(jù)單元結(jié)構(gòu)的不一致問(wèn)題。RoadRunner[28]和EXALG[29]進(jìn)一步比較了同一網(wǎng)站的多個(gè)網(wǎng)頁(yè)的相似與差異，用以推導(dǎo)網(wǎng)頁(yè)的文法模式或標(biāo)簽?zāi)０濉?/p>

記錄級(jí)別和單元級(jí)別的抽取完成時(shí)，全自動(dòng)的方法還需要為每個(gè)數(shù)據(jù)單元分配適合的標(biāo)簽，以表示其具體語(yǔ)義（例如：“作者”、“時(shí)間”、“內(nèi)容”等，見(jiàn)圖 2）。目前，語(yǔ)義標(biāo)簽的自動(dòng)化抽取仍然是個(gè)開(kāi)放的問(wèn)題。初步的研究工作主要基于啟發(fā)規(guī)則和特征[15]或網(wǎng)頁(yè)表單的查詢(xún)接口等[26]。然而，同一種數(shù)據(jù)單元在不同的網(wǎng)站可能具有不同的標(biāo)簽文本，如何將這些標(biāo)簽映射到同一個(gè)全局的語(yǔ)義標(biāo)簽，則需要數(shù)據(jù)集成（Data Integration）方面的相關(guān)工作[2]。

2綜合分類(lèi)和比較

由前文分析論述可知，除了按自動(dòng)化程度劃分之外，網(wǎng)絡(luò)信息抽取任務(wù)還可以由輸入類(lèi)型、輸出數(shù)據(jù)對(duì)象類(lèi)型和使用的方法等多方面進(jìn)行分類(lèi)。

按輸入頁(yè)面數(shù)量，可以分為單一頁(yè)面（即只需要一個(gè)單獨(dú)的網(wǎng)頁(yè)即可進(jìn)行信息抽?。?、多頁(yè)面（需要利用由同一模板或腳本生成的多個(gè)網(wǎng)頁(yè)）、網(wǎng)站鏈接地圖（需要利用多種不同類(lèi)型的網(wǎng)頁(yè)及其中的鏈接指向關(guān)系）三種。