Web頁(yè)面的信息抽取算法設(shè)計(jì)

楊鳳

【摘 要】本文給出一種Web頁(yè)面的數(shù)據(jù)結(jié)構(gòu)描述方式，比對(duì)所需信息的字符串序列，對(duì)通用型框架結(jié)構(gòu)和數(shù)據(jù)域進(jìn)行劃分，經(jīng)規(guī)則化處理后可以對(duì)web網(wǎng)頁(yè)自動(dòng)地生成模板，從而達(dá)到抽取信息的目的。

【關(guān)鍵詞】信息抽?。煌ㄓ每蚣?；算法設(shè)計(jì)

1.引言

計(jì)算機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展和普及，使得網(wǎng)絡(luò)逐漸成為信息交流的關(guān)鍵平臺(tái)。為了人們?cè)诤Ａ康木W(wǎng)絡(luò)信息中更加便捷地獲取所需信息，有必要對(duì)同領(lǐng)域信息的抽取、匯總、集成，可以建立對(duì)應(yīng)領(lǐng)域的信息庫(kù)。

Web動(dòng)態(tài)網(wǎng)頁(yè)由服務(wù)器根據(jù)請(qǐng)求從數(shù)據(jù)庫(kù)中選取數(shù)據(jù)并嵌入到通用模板而生成，缺乏結(jié)構(gòu)和語(yǔ)義信息的描述，其中包含的信息不易被一般應(yīng)用程序直接獲取。因此，如何將網(wǎng)頁(yè)中的數(shù)據(jù)抽取出來(lái)就變得非常迫切。Web頁(yè)面的信息抽取技術(shù)為實(shí)現(xiàn)這一目標(biāo)提供了新的途徑[1]。

2.Web信息抽取的過(guò)程設(shè)計(jì)

2.1信息抽取

信息抽?。↖nformation Extraction）是從文本包含中識(shí)別出用戶所需的部分信息，并將其轉(zhuǎn)換為結(jié)構(gòu)化、有特定組織形式的數(shù)據(jù)集合的過(guò)程。

2.2 Web 頁(yè)面信息的數(shù)據(jù)結(jié)構(gòu)的定義

Web網(wǎng)頁(yè)的基本元素用三類標(biāo)簽來(lái)描述，分別是開(kāi)始標(biāo)簽、結(jié)束標(biāo)簽以及文本內(nèi)容。Web網(wǎng)頁(yè)的數(shù)據(jù)結(jié)構(gòu)是用字符串序列、標(biāo)簽樹(shù)兩種結(jié)構(gòu)來(lái)描述。字符串序列是用開(kāi)始標(biāo)簽、結(jié)束標(biāo)簽以及文本內(nèi)容構(gòu)成的一種線性數(shù)據(jù)結(jié)構(gòu)；標(biāo)簽樹(shù)用開(kāi)始標(biāo)簽和文本內(nèi)容表示網(wǎng)頁(yè)層次結(jié)構(gòu)。

2.3 Web 信息抽取過(guò)程的設(shè)計(jì)

Web 信息抽取方法關(guān)鍵環(huán)節(jié)為通用框架結(jié)構(gòu)檢測(cè)、模板抽取。圖 1 是Web 信息抽取的過(guò)程圖。

Web 信息抽取是將包含用戶所需信息的 Web 網(wǎng)頁(yè)中的數(shù)據(jù)自動(dòng)提取到一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集內(nèi)的信息處理過(guò)程。Web 信息抽取針對(duì)有價(jià)值的文本進(jìn)行結(jié)構(gòu)分析，其效率和質(zhì)量較高，更注重工程性和可操作性，也更容易面向?qū)嶋H應(yīng)用[2]。

3.實(shí)現(xiàn)WEB信息抽取的關(guān)鍵技術(shù)

3.1 抽取規(guī)則——構(gòu)建通用型框架

通用型框架的建構(gòu)以比對(duì)字符串序列異同的方式進(jìn)行，對(duì)通用型框架結(jié)構(gòu)和數(shù)據(jù)域進(jìn)行劃分。其中，通用型框架是指與web網(wǎng)頁(yè)呈現(xiàn)的主要內(nèi)容無(wú)關(guān)的部分，如導(dǎo)航條、頭尾信息、廣告信息和 flash特效等。數(shù)據(jù)域是指web網(wǎng)頁(yè)中除了通用型框架以外的內(nèi)容，將數(shù)據(jù)域的字符串序列進(jìn)一步轉(zhuǎn)換成標(biāo)簽樹(shù)結(jié)構(gòu)，就得到數(shù)據(jù)的樣本集合。

通用型框架處理過(guò)程中檢測(cè)網(wǎng)頁(yè)間共有的且與網(wǎng)頁(yè)實(shí)質(zhì)內(nèi)容無(wú)關(guān)的信息，對(duì)去除通用型框架后得到的數(shù)據(jù)域信息進(jìn)行信息抽取時(shí)，準(zhǔn)確率會(huì)有所提高。具體操作是，首先進(jìn)行頁(yè)面分區(qū)，將網(wǎng)頁(yè)劃分成不相交的區(qū)域的過(guò)程。然后定義區(qū)域樹(shù)用樹(shù)狀結(jié)構(gòu)對(duì)頁(yè)面分區(qū)的結(jié)果進(jìn)行表示。樹(shù)的根結(jié)點(diǎn)對(duì)應(yīng)于整個(gè)網(wǎng)頁(yè)，父結(jié)點(diǎn)的區(qū)域由各子結(jié)點(diǎn)區(qū)域組成。接下來(lái)，確定結(jié)點(diǎn)的分區(qū)級(jí)別，得到該結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域時(shí)進(jìn)行的頁(yè)面分區(qū)次數(shù)。區(qū)域樹(shù)的分區(qū)級(jí)別指樹(shù)的深度。為區(qū)域樹(shù)選定合適的分區(qū)級(jí)別將有利于檢測(cè)到更佳的通用型框架結(jié)構(gòu)。再定義通用型框架結(jié)構(gòu)。將網(wǎng)頁(yè)間共有的、與網(wǎng)頁(yè)實(shí)質(zhì)內(nèi)容無(wú)關(guān)的頭信息、尾信息、廣告、瀏覽導(dǎo)向條以及 flash 等內(nèi)容信息稱為通用型框架結(jié)構(gòu)。用雙序列比對(duì)算法對(duì)網(wǎng)頁(yè)字符串序列進(jìn)行比對(duì)，將最佳的相似字符串作為通用型框架結(jié)構(gòu)。算法流程如下[3，4]：

（1） 對(duì)變量max、x和y進(jìn)行初始化。max 表示局部最大值，y 和x 分別表示矩陣當(dāng)前行及其前一行。

（2） 計(jì)算得分矩陣。該過(guò)程由以下三步迭代完成。

（2.1）

其中p（i+1，j+1）為字符串匹配函數(shù)，當(dāng)字符串匹配時(shí)取值c，否則，可取值d（d<0）；g為間隔罰分。

（2.2）當(dāng)p（i+1， j+1）<0時(shí)，如果max

（2.3）令x=y。

（3）計(jì)算最佳相似字符串的長(zhǎng)度 ，其中， 為調(diào)節(jié)參數(shù)。

（4）得到通用框架。位于Pm- 與Pm范圍中的最佳相似字符串就是通用框架。算法中，在找到最長(zhǎng)的匹配字符串后，需要對(duì)參數(shù)進(jìn)行調(diào)節(jié)，從而得到最佳的相似字符串作為通用型框架結(jié)構(gòu)。

3.2模板抽取

Web 上的動(dòng)態(tài)頁(yè)面有兩種來(lái)源，一類是超鏈接方式，另外一類需要填寫(xiě) Web 頁(yè)面上的表單（Form），然后提交給網(wǎng)站服務(wù)器后動(dòng)態(tài)生成，這類頁(yè)面無(wú)法直接獲取，也就是深網(wǎng)頁(yè)。根據(jù)動(dòng)態(tài) Web 頁(yè)面的構(gòu)成模板可以將其分為A、B兩大類。A 類：整個(gè)頁(yè)面內(nèi)容包括很多項(xiàng)數(shù)據(jù)，這些數(shù)據(jù)對(duì)應(yīng)于一個(gè)實(shí)體的各項(xiàng)屬性，組成了一條完整的記錄。B類：頁(yè)面中包含了多條記錄，每條記錄又包含多個(gè)數(shù)據(jù)項(xiàng)，即該條記錄的屬性項(xiàng)各條記錄的屬性項(xiàng)基本相同。

模板抽取是對(duì)樣本間各種匹配與不匹配的部分進(jìn)行搜索和劃分，經(jīng)規(guī)則化處理后可以得到模板。模板抽取過(guò)程如圖2所示：

本文給出的抽取算法是：輸入一個(gè)樣本集合，每一次比較包裝器樹(shù)和一個(gè)樣本網(wǎng)頁(yè)樹(shù)并產(chǎn)生一棵新的包裝器樹(shù)，然后再利用該包裝器樹(shù)和另一個(gè)樣本網(wǎng)頁(yè)樹(shù)進(jìn)行比較直至所有的樣本網(wǎng)頁(yè)比較完畢后生成最終的包裝器樹(shù)。其流程描述如下：

（1）設(shè)定任一基準(zhǔn)Pjz∈V集合；

（2）對(duì)P∈V-{Pjz}，從根結(jié)點(diǎn)開(kāi)始進(jìn)行深度遍歷，設(shè)Rjz=Root（Pjz），Rb=Root（P）。

（2.1）Rjz和Rb為葉結(jié)點(diǎn)，若Rjz.Name≠Rb.Name，令Rjz。Name待提取信息；

（2.2）Rjz和Rb均不為葉結(jié)點(diǎn)：

（2.2.1） Rb！=NULL，且Rjz.Name≠Rb.Name，令Rb為其第一右兄弟節(jié)點(diǎn)，重復(fù)（2.2.1），否則轉(zhuǎn)（2.2.2）；

（2.2.2）若Rjz.Name≠Rb.Name，Rjz，Rb為其第一左子結(jié)點(diǎn)，轉(zhuǎn)（2.1），否則轉(zhuǎn)（2.2.3）；

（2.2.3）若Rb==NULL，令Rjz.Name為設(shè)定值；

（2.3）當(dāng)Rjz 和Rb 中有且只有一個(gè)是葉結(jié)點(diǎn)時(shí)，

（2.3.1） 若Rb 非空，令Rb 為其第一右兄弟結(jié)點(diǎn)，重復(fù)（2.3.1），否則轉(zhuǎn)（2.3.2）；

（2.3.2） 若Rb 為空，令Rjz. Name =，否則，轉(zhuǎn)（2.1）；

（2.4）若Rjz 非空，令Rjz 為其第一右兄弟結(jié)點(diǎn)，重復(fù)（2.1），否則，轉(zhuǎn)（3）；

（3）重新遍歷Pjz ，對(duì)相同的子樹(shù)進(jìn)行合并。

通過(guò)對(duì)網(wǎng)頁(yè)的通用型框架結(jié)構(gòu)進(jìn)行定義，在信息抽取算法中引入了通用型框架結(jié)構(gòu)檢測(cè)階段，采用序列比對(duì)算法對(duì)同類網(wǎng)頁(yè)所共有的、與網(wǎng)頁(yè)表達(dá)的實(shí)質(zhì)內(nèi)容無(wú)關(guān)的信息進(jìn)行檢測(cè)，除掉了通用型框架結(jié)構(gòu)的網(wǎng)頁(yè)信息，對(duì)信息抽取更加有利。該算法可以對(duì)數(shù)據(jù)密集的真實(shí)網(wǎng)頁(yè)自動(dòng)地生成模板、抽取信息，既不局限于人為定制的測(cè)試網(wǎng)頁(yè)也不依賴于網(wǎng)頁(yè)內(nèi)容的先驗(yàn)知識(shí)[5]。

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

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

實(shí)驗(yàn)中，我們采用召回率和查準(zhǔn)率作為評(píng)價(jià)的指標(biāo)對(duì)信息抽取系統(tǒng)進(jìn)行評(píng)價(jià)。從直觀上說(shuō)，召回率可以理解為，從網(wǎng)頁(yè)中正確抽取出來(lái)的數(shù)據(jù)項(xiàng)的比例，查準(zhǔn)率可以理解為，被抽取出來(lái)的數(shù)據(jù)項(xiàng)中正確的比重。

當(dāng)我們?cè)u(píng)價(jià)一個(gè)信息抽取系統(tǒng)時(shí)，為了綜合評(píng)價(jià)系統(tǒng)的性能，應(yīng)同時(shí)考慮這兩個(gè)指標(biāo)。為了能夠直接地同時(shí)比較召回率和查準(zhǔn)率，設(shè)定β為權(quán)重參數(shù)，其值反應(yīng)在評(píng)測(cè)時(shí)側(cè)重召回率還是查準(zhǔn)率，由系統(tǒng)預(yù)設(shè)。若需要設(shè)定表明查準(zhǔn)率更重要，就設(shè)定 β> 1，反之，召回率更重要?jiǎng)t設(shè)定β< 1。在信息抽取系統(tǒng)中，通常設(shè)定β==1，以反應(yīng)召回率和查準(zhǔn)率的重要性是等同的。

4.2 實(shí)驗(yàn)設(shè)計(jì)與分析

本文實(shí)驗(yàn)采用的網(wǎng)頁(yè)來(lái)自于真實(shí)的站點(diǎn)中的動(dòng)態(tài) Web 網(wǎng)頁(yè)，其中包含的信息紛繁復(fù)雜，包括 HTML 頁(yè)面的頭信息、尾信息、廣告、瀏覽導(dǎo)向條、flash 等，實(shí)驗(yàn)中，我們預(yù)先對(duì)網(wǎng)頁(yè)中標(biāo)簽缺失的情況進(jìn)行修正以便建立標(biāo)簽樹(shù)。

在數(shù)據(jù)集合上應(yīng)用帶序列比對(duì)的信息抽取算法，對(duì)參數(shù)θ進(jìn)行調(diào)節(jié)，根據(jù)抽取結(jié)果為算法選擇合理的參數(shù)值。表 1 結(jié)果顯示的是θ取不同值時(shí)的召回率和查準(zhǔn)率。

對(duì)參數(shù)θ取不同的值分別進(jìn)行實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)結(jié)果為算法選擇合理的參數(shù)值，為后緒模板抽取實(shí)驗(yàn)做好準(zhǔn)備。圖3為表1對(duì)應(yīng)的曲線圖。

在實(shí)驗(yàn)召回率與查準(zhǔn)率對(duì)照?qǐng)D即圖3 中，縱坐標(biāo)表示召回率和查準(zhǔn)率，橫坐標(biāo)表示參數(shù)θ，如圖所示，當(dāng)θ的取值為 1.2時(shí)抽取信息的效果最優(yōu)。實(shí)驗(yàn)證明了本文上述抽取算法的有效性。

5.結(jié)論

web網(wǎng)頁(yè)的信息抽取過(guò)程中采用序列比對(duì)的方式進(jìn)行通用型框架結(jié)構(gòu)檢測(cè)，剝離網(wǎng)頁(yè)中的冗余信息，有利于模板抽取的精確度的提高。實(shí)驗(yàn)中把真實(shí)網(wǎng)站的數(shù)據(jù)密集型網(wǎng)頁(yè)作為樣本，對(duì)抽取算法在數(shù)據(jù)量和抽取準(zhǔn)確率等方面進(jìn)行了測(cè)試和比較，結(jié)果充分證明了算法的有效性。

參考文獻(xiàn)：

[1]張鵬程，李必信，李雯睿. 時(shí)間屬性序列圖： 語(yǔ)法和語(yǔ)義.軟件學(xué)報(bào)，2010，Vol.21（11）： 2752-2767.

[2]劉凱鵬，方濱興.一種基于社會(huì)性標(biāo)注的網(wǎng)頁(yè)排序算法.計(jì)算機(jī)學(xué)報(bào)，2010，Vol.33（6）： 1014-1023.

[3]陳傳夫，唐瓊，于媛，吳志強(qiáng)等.網(wǎng)絡(luò)上科學(xué)信息的時(shí)效性測(cè)量.情報(bào)學(xué)報(bào)，2009， Vol.28（4）： 610-617.

[4]劉冬寧，湯庸.時(shí)態(tài)數(shù)據(jù)庫(kù)時(shí)間軸的動(dòng)態(tài)邏輯模型.軟件學(xué)報(bào)， 2010， Vol.21（4）：694-701.

[5]寇月，李冬，申德榮，于戈，聶鐵錚.D-EEM： 一種基于DOM 樹(shù)的Deep Web 實(shí)體抽取機(jī)制. 計(jì)算機(jī)發(fā)展與研究，2010，Vol.47（5）： 858-865.

基金項(xiàng)目：

廣西教育廳科研課題（201106LX606）。

作者簡(jiǎn)介：

楊 鳳（1981-），女，湖南常德漢壽縣人，碩士，講師，主要研究方向?yàn)椋簲?shù)據(jù)挖掘。