雙 哲 孫 蕾

(華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 上海 200241)

基于改進(jìn)的隱馬爾可夫模型在網(wǎng)頁(yè)信息抽取中的研究與應(yīng)用

雙 哲 孫 蕾

(華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系 上海 200241)

信息抽取是從大量的數(shù)據(jù)中準(zhǔn)確、快速地獲取目標(biāo)信息，提高信息的利用率?？紤]網(wǎng)頁(yè)數(shù)據(jù)的特點(diǎn)，提出一種適用于網(wǎng)頁(yè)信息抽取改進(jìn)的隱馬爾科夫模型(HMM)，即結(jié)合最大熵模型(ME)在特征知識(shí)表示方面的優(yōu)勢(shì)，在HMM模型中加入后向依賴，利用發(fā)射單元特征來(lái)調(diào)整模型參數(shù)。改進(jìn)后的HMM狀態(tài)轉(zhuǎn)移概率和觀察輸出概率不僅依賴于模型的當(dāng)前狀態(tài)值，而且可以以模型的前向狀態(tài)值和后向特征值加以修正。實(shí)驗(yàn)結(jié)果表明，使用改進(jìn)后的HMM模型應(yīng)用到網(wǎng)頁(yè)信息抽取中，可以有效地提高網(wǎng)頁(yè)信息抽取的質(zhì)量。

隱馬爾可夫模型 最大熵模型 網(wǎng)頁(yè)信息抽取

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)及應(yīng)用的不斷成熟與深入，面對(duì)日益增多的海量網(wǎng)頁(yè)信息，人們需要一種自動(dòng)化工具來(lái)幫助人們從中快速發(fā)現(xiàn)真正需要的信息，并將這些信息自動(dòng)分類(lèi)、提取，使其有益于信息后續(xù)的檢查比較及自動(dòng)處理，由此需要相應(yīng)成熟的網(wǎng)頁(yè)信息抽取技術(shù)從搜索引擎得到的結(jié)果網(wǎng)頁(yè)中抽取目標(biāo)信息。網(wǎng)頁(yè)數(shù)據(jù)和傳統(tǒng)的自由文本數(shù)據(jù)相比具有半結(jié)構(gòu)化、更新快、形式多樣等特點(diǎn)。目前涉及這一熱點(diǎn)研究課題的相關(guān)方法和技術(shù)有：(1) 基于包裝器生成技術(shù)適用于格式固定的網(wǎng)頁(yè)，但在移植及維護(hù)上較困難[1]；(2) 基于NLP的信息抽取方法適用于純文本的抽取任務(wù)，但網(wǎng)頁(yè)數(shù)據(jù)被標(biāo)簽分割無(wú)法直接使用；(3) 基于本體的信息抽取方法需要較大的成本構(gòu)造本體[2-3]；(4) 基于DOM樹(shù)的技術(shù)基于網(wǎng)頁(yè)本身的結(jié)構(gòu)，其適用于相似結(jié)構(gòu)的網(wǎng)頁(yè)，包括DSE算法[4]和MDR算法[5]；(5) 大量網(wǎng)頁(yè)可通過(guò)讀取后臺(tái)數(shù)據(jù)庫(kù)填充到統(tǒng)一模板生成，從而形成了基于模板的抽取技術(shù)，但其使用范圍有限[6]。文中所研究與改進(jìn)的基于隱馬爾可夫模型(HMM)的網(wǎng)頁(yè)信息抽取模型，具有易于建立、不需要大規(guī)模詞典和規(guī)則集、移植性好、投入成本較少等顯著優(yōu)勢(shì)。然而，目前該類(lèi)模型還存在著其信息抽取的準(zhǔn)確率及效率有待進(jìn)一步改進(jìn)和完善的不足，其中已有的工作成果和進(jìn)展，如文獻(xiàn)[7-9]應(yīng)用HMM抽取論文頭部信息，用shrinkage改進(jìn)模型概率估計(jì)，并用隨機(jī)優(yōu)化技術(shù)動(dòng)態(tài)選擇模型結(jié)構(gòu)；文獻(xiàn)[10]在網(wǎng)頁(yè)中以語(yǔ)義塊作為抽取單元，并利用投票機(jī)制優(yōu)化發(fā)射概率分布；文獻(xiàn)[11-12]在網(wǎng)頁(yè)中選擇功能內(nèi)容塊(即邏輯內(nèi)容相關(guān)聯(lián)的塊被組織在一起)抽取單元，結(jié)合VIPS和DOM等技術(shù)識(shí)別并抽取一個(gè)目標(biāo)塊；文獻(xiàn)[13]提出的MEMM將文本詞匯本身包含的特征信息結(jié)合到馬爾科夫模型中，但MEMM只是考慮了抽象特征，并未對(duì)文本詞匯進(jìn)行統(tǒng)計(jì)；文獻(xiàn)[14-16]提出并驗(yàn)證了在很多應(yīng)用中二階模型的有效性，若為了提高模型的描述能力而單純?cè)黾幽Ｐ碗A數(shù)，參數(shù)空間會(huì)成指數(shù)增長(zhǎng)，而容易引發(fā)數(shù)據(jù)稀疏等問(wèn)題。

在此，提出改進(jìn)的HMM用于網(wǎng)頁(yè)數(shù)據(jù)的有效抽取，即將抽取信息的模型擴(kuò)展為二階且同時(shí)考慮文本上下文特征信息，利用最大熵模型(ME)在特征知識(shí)表示方面的優(yōu)勢(shì)，在HMM模型中加入后向依賴，利用發(fā)射單元特征來(lái)調(diào)整模型參數(shù)。改進(jìn)后的HMM狀態(tài)轉(zhuǎn)移概率和觀察輸出概率不僅依賴于模型的當(dāng)前狀態(tài)值，而且擬進(jìn)一步地利用模型的前向狀態(tài)值和后向特征值加以修正完善。從而解決了在以往的HMM中沒(méi)有考慮抽取對(duì)象的上下文特征和文本詞匯本身包含的特征信息等問(wèn)題。

1 基于改進(jìn)的HMM的網(wǎng)頁(yè)信息抽取的工作流程概述

隱馬爾可夫模型(HMM)是信息抽取的重要方法之一，文中針對(duì)HMM不足，結(jié)合網(wǎng)頁(yè)數(shù)據(jù)的特征，提出了改進(jìn)的HMM用于網(wǎng)頁(yè)信息抽取。改進(jìn)后的HMM充分考慮了抽取對(duì)象的上下文特征和文本詞匯本身包含的特征信息，修正了模型的轉(zhuǎn)移概率和發(fā)射概率(即在模型訓(xùn)練階段利用最大熵原理優(yōu)化了模型參數(shù)；在模型解碼階段讓改進(jìn)的viterbi算法更有效地完成信息抽取)。文中所研討的網(wǎng)頁(yè)信息抽取的主要方法和技術(shù)流程如圖1所示，其中：(1) 數(shù)據(jù)預(yù)處理：依據(jù)所處理數(shù)據(jù)的特征，將數(shù)據(jù)劃分為分組序列；(2) 初始化模型：確定模型的狀態(tài)集和模型的拓?fù)浣Y(jié)構(gòu)；(3) 模型訓(xùn)練：在訓(xùn)練集中使用ML算法[15]和與最大熵相關(guān)的GIS算法[13]來(lái)訓(xùn)練獲取模型的參數(shù)；(4) 完成信息抽?。翰捎酶倪M(jìn)的viterbi算法求最佳狀態(tài)標(biāo)記序列，結(jié)合標(biāo)注結(jié)果以結(jié)構(gòu)化形式存入數(shù)據(jù)庫(kù)表中。

圖1 基于HMM信息抽取主要執(zhí)行過(guò)程

2 基于改進(jìn)的HMM 的網(wǎng)頁(yè)信息抽取的功能剖析

2.1 網(wǎng)頁(yè)數(shù)據(jù)準(zhǔn)備

2.1.1 數(shù)據(jù)預(yù)處理

網(wǎng)頁(yè)信息抽取預(yù)處理就是依據(jù)所處理數(shù)據(jù)的特征選取基本抽取單元。網(wǎng)頁(yè)中數(shù)據(jù)被HTML標(biāo)簽、分隔符等元素分割成一個(gè)個(gè)的語(yǔ)義塊[10]，使得屬于同一個(gè)狀態(tài)的內(nèi)容將以很大的概率組織在同一個(gè)語(yǔ)義塊內(nèi)，文中保留了HTML標(biāo)簽和分隔符是為了更易于將邏輯相關(guān)的內(nèi)容組織在一起以形成語(yǔ)義塊分組。文中采用語(yǔ)義塊分組作為觀察序列的基本抽取單元，如此同類(lèi)別的數(shù)據(jù)被組織在一起，明顯比以單個(gè)單詞為抽取單元的效率更高。所以文中基于文獻(xiàn)[10]語(yǔ)義塊分組的思想對(duì)網(wǎng)頁(yè)數(shù)據(jù)進(jìn)行預(yù)處理，形成分組序列。并將數(shù)據(jù)預(yù)處理后的格式設(shè)定為：原始序列Raw、特征序列Type、狀態(tài)序列State[17]。

2.1.2 網(wǎng)頁(yè)信息抽取模型狀態(tài)集的改進(jìn)描述

值得說(shuō)明的是：為了對(duì)預(yù)處理后的分組序列標(biāo)注相對(duì)應(yīng)的狀態(tài)序列state，需要構(gòu)造相對(duì)應(yīng)的狀態(tài)集，而狀態(tài)集的選擇對(duì)最終抽取結(jié)果具有重要的影響。在構(gòu)造一個(gè)基于HMM的網(wǎng)頁(yè)信息抽取模型時(shí)，首先要確定模型的結(jié)構(gòu)，即應(yīng)該包含多少個(gè)狀態(tài)及各個(gè)狀態(tài)之間如何轉(zhuǎn)換，一個(gè)理想的初始模型是一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)標(biāo)記類(lèi)型，且任意兩個(gè)狀態(tài)間可以相互轉(zhuǎn)移。但是從文獻(xiàn)[7]的結(jié)論中我們得知這種方式并不是最優(yōu)的，而一個(gè)標(biāo)記類(lèi)型定義多個(gè)狀態(tài)又會(huì)增加模型復(fù)雜度。另外若兩個(gè)單詞以相同的頻率出現(xiàn)在同一個(gè)狀態(tài)內(nèi)，目前一般的做法是讓這兩個(gè)單詞具有相同的重要程度，但是這種做法卻忽略了一個(gè)重要的信息，那就是在同一個(gè)狀態(tài)內(nèi)多個(gè)單詞具有順序或前后關(guān)系。在此，為每一個(gè)標(biāo)記類(lèi)型定義兩個(gè)狀態(tài)：開(kāi)始狀態(tài)(start)和剩余狀態(tài)(rest)。如論文的“title”標(biāo)記，就包括：title.s和title.r。這種結(jié)構(gòu)十分適合網(wǎng)頁(yè)數(shù)據(jù)的特點(diǎn)，如“地址”標(biāo)簽addr.s之后就會(huì)是具體的地址addr.r。在此提出的模型中除了包含正常狀態(tài)外，還包含一些特殊的狀態(tài)標(biāo)記如start、end。

2.2 信息抽取模型的訓(xùn)練階段

模型訓(xùn)練階段，在完全標(biāo)記的樣本集中給定了觀察序列O和其相對(duì)應(yīng)的狀態(tài)序列Q，為了確定釋放該觀察序列的模型λ且使該觀察序列的釋放概率P(O|λ)最大，通常采用最大似然估計(jì)(ML)算法中相關(guān)的統(tǒng)計(jì)公式[15]訓(xùn)練獲取HMM的參數(shù)集。

傳統(tǒng)HMM是能隨機(jī)狀態(tài)轉(zhuǎn)移并輸出符號(hào)的有限狀態(tài)自動(dòng)機(jī)[7]如圖2(a)，其包括觀察層和隱藏層，觀察層是待識(shí)別的觀察序列，隱藏層即狀態(tài)序列是一個(gè)馬爾可夫過(guò)程。文中利用最大熵模型(ME)在特征知識(shí)表示方面的優(yōu)勢(shì)，考慮被抽取對(duì)象上下文特征信息且同時(shí)增加模型階數(shù)以增加模型的描述能力后，在模型中加入了前向、后向依賴。改進(jìn)的HMM主要擴(kuò)展了兩個(gè)假設(shè)條件：(1) 改進(jìn)的HMM在t時(shí)刻的狀態(tài)不僅由t-2和t-1時(shí)刻的狀態(tài)決定，且由t和t+1時(shí)刻觀察序列所具有的特征決定；(2) 在t時(shí)刻輸出觀察值的概率不僅依賴于t時(shí)刻所處的狀態(tài)而且依賴于t-1時(shí)刻的狀態(tài)。

圖2 HMM模型的改進(jìn)

在利用被抽取對(duì)象特征方面，最大熵原理提供一種方法，可以集成各種特征與規(guī)則到一個(gè)統(tǒng)一的框架下。如文獻(xiàn)[13]提出的MEMM是一個(gè)指數(shù)模型，其將被抽取對(duì)象的抽象特征作為輸入，并在馬爾科夫狀態(tài)轉(zhuǎn)移的基礎(chǔ)上選擇下一個(gè)狀態(tài)，其結(jié)構(gòu)接近于有窮狀態(tài)自動(dòng)機(jī)如圖2(b)。加入特征集合后影響了狀態(tài)之間的關(guān)聯(lián)，因而需用狀態(tài)轉(zhuǎn)移概率矩陣和特征-狀態(tài)轉(zhuǎn)移概率矩陣來(lái)描述新的狀態(tài)之間的關(guān)聯(lián)。從觀察序列相鄰兩項(xiàng)中提取數(shù)據(jù)特征，即t和t+1時(shí)刻相鄰兩項(xiàng)觀察所具有的特征部分決定了t時(shí)刻所處的狀態(tài)，以此可以從觀察序列中得到模型對(duì)后向數(shù)據(jù)特征的依賴，如圖2(c)所示。在現(xiàn)實(shí)應(yīng)用中可根據(jù)具體的應(yīng)用領(lǐng)域而構(gòu)造不同的特征集合，如在論文頭部信息抽取中是否大寫(xiě)字母開(kāi)頭、是否含有人名或人名縮寫(xiě)、是否是數(shù)字、是否含有@或email等。

改進(jìn)的HMM與傳統(tǒng)的HMM訓(xùn)練獲取參數(shù)集對(duì)比如表1所示。

需要特別說(shuō)明的是：

(1)

其中，r=∑k[λ×aijk+ (1-λ)×∑f(Cf,k× ff,k((ot,ot + 1),st))]為歸一化參數(shù)；引用文獻(xiàn)[13,18]中論述的最大熵原理在NLP各分支應(yīng)用中的公式，在此在給定的特征集上定義一個(gè)二值函數(shù)如下式：

fi,j((ot,ot+1),st)=

(2)

接著，基于最大熵思想及上述定義，在改進(jìn)后的HMM中需要構(gòu)造一個(gè)特征-狀態(tài)轉(zhuǎn)移的概率矩陣，即式(1)中參數(shù)C就是利用最大熵原理從觀察值序列的特征中獲取的特征-狀態(tài)轉(zhuǎn)移概率矩陣C={Ci,j}NF×NS，其中元素Ci,j就是從特征i到狀態(tài)j的概率，滿足條件：∑jCi,j= 1，其中NF是特征的個(gè)數(shù)，NS是狀態(tài)的個(gè)數(shù)。在訓(xùn)練階段對(duì)各個(gè)觀察序列進(jìn)行特征提取，在完全標(biāo)記的訓(xùn)練數(shù)據(jù)中每個(gè)觀察特征都對(duì)應(yīng)一個(gè)狀態(tài)，因此可以利用改進(jìn)的GIS算法統(tǒng)計(jì)獲取特征-狀態(tài)轉(zhuǎn)移概率矩陣，算法過(guò)程如圖3所示。

圖3 利用改進(jìn)的GIS算法求特征-狀態(tài)概率轉(zhuǎn)移矩陣方法流程

2) 在使用最大熵原理統(tǒng)計(jì)被抽取對(duì)象的特征信息方面，相比于MEMM沒(méi)有統(tǒng)計(jì)詞匯本身信息[13]，但在改進(jìn)后的模型中使用符號(hào)輸出概率矩陣統(tǒng)計(jì)詞匯本身信息，且改進(jìn)后的模型t時(shí)刻的觀察值依賴于t-1和t時(shí)刻的狀態(tài)如式(2)所示。

2.3 完成信息抽取階段

為了完成信息抽取需要解決的是解碼問(wèn)題，即給定訓(xùn)練得到的模型參數(shù)λ和觀察值序列O，求與觀察值序列對(duì)應(yīng)且使得P(Q|O,λ)最大的最佳狀態(tài)序列Q，通常采用的是viterbi算法。

定義δt(i,j)為t時(shí)刻沿路徑q1,q2,…,qt-1,qt(qt-1=si,qt=sj)釋放部分觀察值序列O1,O2,…,Ot的最大釋放概率式如(3)：

δt(i,j)=maxP(q1,q2,…,qt-1=Si,qt=

Sj,O1O2,…,Ot,Ot+1|λ)

(3)

通過(guò)推導(dǎo)可得t+1時(shí)刻路徑的最大概率如式(4)：

(4)

另外，定義一個(gè)用于存儲(chǔ)回溯路徑的數(shù)組變量如式(5):

(5)

求最佳狀態(tài)序列的改進(jìn)Viterbi算法主要實(shí)現(xiàn)步驟如下：

(1) 初始化：δ1(i)=πibi(Oi),Ψ1(i)=0

δ2(i,j)=πiaijbi(o1)bij(o2),Ψ2(i,j)=0

(2) 遞歸： /*模型的改進(jìn)應(yīng)用于此處*/

where(1≤j,k≤N&&2≤t≤T-1)：

1≤i,j,k≤N,2≤t≤T-1

(3) 終結(jié)：

(4) 回溯求最佳路徑：

2.4 針對(duì)模型進(jìn)一步優(yōu)化的改進(jìn)建議

1) 針對(duì)實(shí)際應(yīng)用過(guò)程中，從訓(xùn)練語(yǔ)料中學(xué)習(xí)模型的參數(shù)時(shí)經(jīng)常需要面對(duì)訓(xùn)練數(shù)據(jù)不足的情況，而使用最大似然(ML)估計(jì)模型參數(shù)時(shí)將會(huì)出現(xiàn)參數(shù)概率為零的情況。為避免出現(xiàn)上述情況使用參數(shù)平滑處理。主要的平滑技術(shù)包括：利用頻率信息進(jìn)行平滑的Good-Turing；使用低階模型和高階模型的線性組合的線性插值平滑；回退低階模型近似求解的katz`s回退式平滑[8]。文中依據(jù)上述三種平滑思想，結(jié)合文獻(xiàn)[16]中提及的Back-off shrinkage思想，進(jìn)一步改進(jìn)平滑技術(shù)以適應(yīng)將HMM應(yīng)用到網(wǎng)頁(yè)信息抽取中，文中統(tǒng)計(jì)在全局中數(shù)據(jù)出現(xiàn)的次數(shù)融入平滑公式中，對(duì)狀態(tài)轉(zhuǎn)移與觀察值輸出概率進(jìn)行平滑處理。如狀態(tài)轉(zhuǎn)移概率P(Si→Sj→Sk)=λ1P(Si→Sj→Sk)+λ2Pglobal(Si∪Sj∪Sk)其中，Pglobal(si∪sj∪sk)是三者在整個(gè)訓(xùn)練集中出現(xiàn)的概率；對(duì)觀察值發(fā)射概率P(Vm|Si→Sj)=λ1P(Vm|Si→Sj)+λ2Pglobal(Vm)其中，Pglobal(Vm)是Vm在整個(gè)訓(xùn)練集中出現(xiàn)的概率。

2) 如何解決在測(cè)試階段出現(xiàn)了而在訓(xùn)練階段沒(méi)有遇到的單詞的發(fā)射概率，這就是OOV(outofvocabulary)問(wèn)題。文中我們將使用較有效的最小頻率法：讓fmin表示最小頻率，詞匯表中單詞在訓(xùn)練數(shù)據(jù)集上的發(fā)射頻率都不會(huì)小于fmin，其他的單詞如果他們的頻率小于fmin，就會(huì)將他們標(biāo)記為，如果測(cè)試數(shù)據(jù)中的任意一個(gè)單詞不在詞匯表中則將它標(biāo)記為,所以不在詞匯表中單詞的發(fā)射概率就是的發(fā)射概率，這個(gè)值可以通過(guò)訓(xùn)練數(shù)據(jù)獲得。

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

實(shí)驗(yàn)一是模型有效性的驗(yàn)證，選擇改進(jìn)后的HMM與一階HMM(基本抽取單元分別選擇單詞和語(yǔ)義塊)、二階HMM，在語(yǔ)料庫(kù)DBLP[19]和CORA[20]上的對(duì)比結(jié)果。文中選擇F1參數(shù)衡量信息抽取模型的質(zhì)量，F(xiàn)1參數(shù)綜合了準(zhǔn)確率和召回率的結(jié)果，F(xiàn)1參數(shù)越大說(shuō)明模型的質(zhì)量越好，實(shí)驗(yàn)結(jié)果如圖4所示。由實(shí)驗(yàn)結(jié)果可知在考慮了前向和后向依賴的情況下各個(gè)狀態(tài)的抽取質(zhì)量均有提升，而Author、Data、Email等項(xiàng)由于較為明顯的特征信息可以取得明顯的效果。而某些數(shù)據(jù)項(xiàng)由于并非頻繁出現(xiàn)或特征不明顯而使得結(jié)果并沒(méi)有較大的改善。試驗(yàn)中還比對(duì)了采用語(yǔ)義塊后的效果，由于減少了將單個(gè)單詞錯(cuò)誤地分到其他狀態(tài)的概率，而抽取結(jié)果有明顯提升。

圖4 模型抽取結(jié)果質(zhì)量對(duì)比

圖5 網(wǎng)頁(yè)數(shù)據(jù)集上抽取結(jié)果對(duì)比

4 結(jié) 語(yǔ)

作為NLP的重要分支，信息抽取相對(duì)信息檢索更深層次的數(shù)據(jù)挖掘，在海量信息的時(shí)代其研究?jī)r(jià)值越來(lái)越受到重視。文中結(jié)合最大熵原理利用數(shù)據(jù)特征信息改進(jìn)HMM，在改進(jìn)后的HMM中有效地考慮了模型前向依賴和后向依賴。結(jié)合網(wǎng)頁(yè)數(shù)據(jù)特征，提出基于改進(jìn)的HMM的網(wǎng)頁(yè)信息抽取模型，對(duì)網(wǎng)頁(yè)數(shù)據(jù)進(jìn)行信息抽取，有效地適應(yīng)了網(wǎng)頁(yè)結(jié)構(gòu)的變化、充分地利用了網(wǎng)頁(yè)的半結(jié)構(gòu)化信息。通過(guò)對(duì)比實(shí)驗(yàn)，驗(yàn)證了改進(jìn)后的HMM方法可以有效地實(shí)現(xiàn)了針對(duì)網(wǎng)頁(yè)數(shù)據(jù)的信息抽取，且具有更好的性能。后續(xù)研究可以著眼于：將改進(jìn)后的模型應(yīng)用到元數(shù)據(jù)的抽取，自動(dòng)學(xué)習(xí)模型的結(jié)構(gòu)，利用主動(dòng)學(xué)習(xí)技術(shù)減少對(duì)標(biāo)記樣本的依賴，從而可以實(shí)現(xiàn)模型的自動(dòng)化構(gòu)造。

[1]CrescenziV,MeccaG,MerialdoP.RoadRunner:towardsautomaticdataextractionfromlargewebsites[C]//Proceedingsofthe27thInternationalConferenceonVeryLargeDataBases,2001:109-118.

[2]GutierrezF,DouD,FickasS,etal.Ahybridontology-basedinformationextractionsystem[J].JournalofInformationScience,2015:1-23.

[3]ZhangN,ChenH,WangY,etal.Odaies:ontology-drivenadaptivewebinformationextractionsystem[C]//IntelligentAgentTechnology,IEEE/WICInternationalConferenceon.IEEEComputerSociety,2003:454.

[4]WangJ,LochovskyFH.Data-richsectionextractionfromHTMLpages[C]//ProceedingsoftheThirdInternationalConferenceonWebInformationSystemsEngineering.IEEEComputerSociety,2002:313-322.

[5]LiuB,GrossmanR,ZhaiY.Miningdatarecordsinwebpages[C]//9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMinig.ACMPress,2003:601-606.

[6] 楊少華,林海略,韓燕波.針對(duì)模板生成網(wǎng)頁(yè)的一種數(shù)據(jù)自動(dòng)抽取方法[J].軟件學(xué)報(bào),2008,19(2):209-223.

[7]SeymoreK,McCallumA,RosenfeldR.LearninghiddenMarkovmodelstructureforinformationextraction[C]//AAAIWorkshoponMachineLearningforInformationExtraction,1999:37-42.

[8]FreitagD,McCallumAK.InformationextractionwithHMMsandshrinkage[C]//AAAIWorkshoponMachineLearningforInformationExtraction,1999:31-36.

[9]FreitagD,McCallumA.InformationextractionwithHMMstructureslearnedbystochasticoptimization[C]//ProceedingsoftheSeventeenthNationalConferenceonArtificialIntelligenceandTwelfthConferenceonInnovativeApplicationsofArtificialIntelligence,2000:584-589.

[10]LaiJ,LiuQ,LiuY.WebinformationextractionbasedonhiddenMarkovmodel[C]//ComputerSupportedCooperativeWorkinDesign(CSCWD),2010 14thInternationalConferenceon.IEEE,2010:234-238.

[11]ZhongP,ChenJ.AgeneralizedhiddenMarkovmodelapproachforwebinformationextraction[C]//WebIntelligence,2006IEEE/WIC/ACMInternationalConferenceon.IEEEComputerSociety,2006:709-718.

[12]ChenJ,ZhongP,CookT.DetectingwebcontentfunctionusinggeneralizedhiddenMarkovmodel[C]//Proceedingsofthe5thInternationalConferenceonMachineLearningandApplications.IEEEComputerSociety,2006:279-284.

[13]McCallumA,FreitagD,PereiraFCN.MaximumentropyMarkovmodelsforinformationextractionandsegmentation[C]//ProceedingsoftheSeventeenthInternationalConferenceonMachineLearning,2000:591-598.

[14]MariJF,HatonJP,KriouileA.Automaticwordrecognitionbasedonsecond-orderhiddenMarkovmodels[J].IEEETransactionsonSpeech&AudioProcessing,1997,5(1):22-25.

[15]DuS,ChenT,ZengX,etal.Trainingsecond-orderhiddenMarkovmodelswithmultipleobservationsequences[C]//Proceedingsofthe2009InternationalForumonComputerScience-TechnologyandApplications.IEEEComputerSociety,2009:25-29.

[16]OjokohB,ZhangM,TangJ.AtrigramhiddenMarkovmodelformetadataextractionfromheterogeneousreferences[J].InformationSciences,2011,181(9):1538-1551.

[17]GengJ,YangJ.AUTOBIB:automaticextractionofbibliographicinformationontheweb[C]//ProceedingsoftheInternationalDatabaseEngineeringandApplicationsSymposium.IEEE,2004:193-204.

[18]BergerAL,PietraVJD,PietraSAD.Amaximumentropyapproachtonaturallanguageprocessing[J].ComputationalLinguistics,1996,22(1):39-71.

[19]DBLP:ComputerScienceBibliography[OL].http://dblp.uni-trier.de/.

[20]CORA[DS/OL].http://www.cs.umass.edu/～mccallum/data/.

[21]SmallSG,MedskerL.Reviewofinformationextractiontechnologiesandapplications[J].NeuralComputingandApplications,2014,25(3):533-548.

[22] 郭喜躍,何婷婷.信息抽取研究綜述[J].計(jì)算機(jī)科學(xué),2015,42(2):14-17,38.

[23] 李榮,馮麗萍,王鴻斌.基于改進(jìn)遺傳退火HMM的Web信息抽取研究[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(4):40-44.

[24] 陳釗,張冬梅.Web信息抽取技術(shù)綜述[J].計(jì)算機(jī)應(yīng)用研究,2010,27(12):4401-4405.

RESEARCH AND APPLICATION FOR WEB INFORMATION EXTRACTION BASED ON IMPROVED HIDDEN MARKOV MODEL

Shuang Zhe Sun Lei

(DepartmentofComputerScienceandTechnology,EastChinaNormalUniversity,Shanghai200241,China)

The task of information extraction is to obtain the objective information precisely and quickly from a large scale of data and improve the utilization of information. According to the characteristics of web data, an improved hidden Markov model (HMM) for web information extraction is proposed, which means combining the advantage of maximum entropy (ME) model in the representation of feature knowledge. The backward dependency assumption in the HMM is added and the model parameters are adjusted by using the characteristic of the emission unit. The state transition probability and the output probability of the improved HMM are not only dependent on the current state of the model, but also be corrected by the forward and backward state values of the historical state of the model. The experimental results show that applying the improved HMM model to web information extraction can effectively improve the quality of web information extraction.

Hidden markov model Maximum entropy model Web information extraction

2016-01-29。國(guó)家自然科學(xué)基金項(xiàng)目(61502170)。雙哲，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，信息抽取。孫蕾，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.02.007