李偉男，李書琴，景 旭，魏 露，李新樂(lè)

（西北農(nóng)林科技大學(xué)信息工程學(xué)院，陜西楊凌712100）

0 引 言

伴隨著互聯(lián)網(wǎng)信息量的指數(shù)級(jí)增長(zhǎng)，快速、高效地定位并提取所需的信息成為研究熱點(diǎn)之一［1］。Web信息抽取技術(shù)是將Web頁(yè)面作為信息源，從中抽取用戶感興趣信息，是有效解決方案工具之一［2］。它主要包括基于詞典、規(guī)則和隱馬爾科夫模型（hidden markov model，HMM）的3種實(shí)現(xiàn)方式［3］。HMM具有強(qiáng)大的統(tǒng)計(jì)建模能力，能夠適應(yīng)網(wǎng)頁(yè)結(jié)構(gòu)多變的狀況，是Web信息抽取技術(shù)的主要研究方法之一。

基于HMM的Web信息抽取是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的方法，受到眾多研究者的關(guān)注［1］。文獻(xiàn)［3］利用正則表達(dá)式和文本推斷算法提取的規(guī)則描述特征；文獻(xiàn)［4］中將遺傳算法（genetic algorithm，GA）與Baum－Welch算法相結(jié)合，獲得全局優(yōu)化參數(shù)。一階HMM（HMM1）對(duì)參數(shù)初值十分敏感，同時(shí)利用Baum－Welch算法訓(xùn)練后極易得到局部最優(yōu)參數(shù)，且未考慮模型歷史狀態(tài)間的關(guān)聯(lián)性［5］。二階HMM（HMM2）加入某一時(shí)刻狀態(tài)轉(zhuǎn)移和觀察值輸出等概率與歷史狀態(tài)關(guān)聯(lián)性，提高了抽取的正確性［6］。

針對(duì)HMM1對(duì)模型參數(shù)初值敏感和未考慮歷史狀態(tài)的問(wèn)題，本文將模擬退火算法（simulated annealing，SA）引入HMM2，提出基于SA的HMM2（SA－HMM2）。在Web信息抽取的準(zhǔn)確度和召回率上，本文提出的方案比傳統(tǒng)基于HMM的方法性能更好，具有重要的應(yīng)用價(jià)值。

1 模擬退火算法

1953年，Metropolis提出了SA算法，該算法是基于物理淬火過(guò)程的一種模擬學(xué)習(xí)規(guī)則［7］。其具體求解步驟如下［8］:

（1）初始化:從可行解空間中隨機(jī)產(chǎn)生一個(gè)初始最優(yōu)點(diǎn)作為當(dāng)前最優(yōu)點(diǎn)S，初始設(shè)置溫度:θ←T0，計(jì)算目標(biāo)函數(shù)值；

（2）循環(huán)計(jì)數(shù)器初值設(shè)置:k←1；

（3）計(jì)算新目標(biāo)函數(shù)值增量:隨機(jī)擾動(dòng)可行解空間內(nèi)的當(dāng)前最優(yōu)點(diǎn)，得到一個(gè)新的最優(yōu)點(diǎn)S’，然后計(jì)算新目標(biāo)函數(shù)的值和增量Δ；

（4）最優(yōu)點(diǎn)判定:若Δ＜0，則以S’作為當(dāng)前最優(yōu)點(diǎn)；若Δ≥0，以概率p＝exp（－Δ/θ）接受S’，當(dāng)不接受時(shí)，繼續(xù)迭代；

（5）迭代判定:如果迭代次數(shù)k小于設(shè)定的終止步數(shù)，則k←k＋1，并跳轉(zhuǎn)到步驟（4）；

（6）終止判定:按照T（k＋1）＝λ×T（k）降低控制溫度T（k＋1），其中0＜λ＜1.0。若未到達(dá)冷卻狀態(tài)，則更新溫度θ←T（k＋1），然后跳轉(zhuǎn)到步驟（3）；否則跳轉(zhuǎn)到步驟（7）；

（7）將當(dāng)前解作為最優(yōu)解輸出。

2 HMM2的建立

HMM1有兩個(gè)主要的假設(shè)條件:①馬爾科夫性假設(shè):狀態(tài)構(gòu)成HMM1鏈，即時(shí)刻t＋1的狀態(tài)轉(zhuǎn)移只與時(shí)刻t的狀態(tài)有關(guān)，與時(shí)刻t以前的狀態(tài)無(wú)關(guān)；②輸出值的獨(dú)立性假設(shè):模型輸出僅與當(dāng)前狀態(tài)有關(guān)，即時(shí)刻t輸出觀測(cè)值的概率，只取決于t時(shí)刻的狀態(tài)而與歷史狀態(tài)無(wú)關(guān)［9］。以上兩個(gè)假設(shè)都只與當(dāng)前狀態(tài)有關(guān)，與歷史狀態(tài)無(wú)關(guān)。而在Web信息抽取中，相鄰信息域間具有很強(qiáng)的相關(guān)性，歷史狀態(tài)對(duì)抽取準(zhǔn)確度有著重要影響。HMM2同時(shí)考慮前向依賴和后向依賴，符合相鄰信息域關(guān)聯(lián)性高這一實(shí)際情況，能夠提高信息抽取的準(zhǔn)確度。文獻(xiàn)［9］簡(jiǎn)述了HMM2的原理，研究和推導(dǎo)了HMM2的學(xué)習(xí)算法。HMM2有以下兩個(gè)假設(shè):

（1）假設(shè)t＋1時(shí)刻的狀態(tài)轉(zhuǎn)移概率依賴于時(shí)刻t及t－1的狀態(tài)，即

（2）假設(shè)輸出觀測(cè)值Vk的輸出概率依賴于t及t－1時(shí)刻，即

本文將網(wǎng)頁(yè)中的論文頭部信息作為待抽取信息，進(jìn)行不同域的抽取。網(wǎng)頁(yè)中的論文頭部信息常用格式如下:

Oren Etzioni，Michele Banko.Open information extraction from the Web［J］.Commun ACM，2008，51（12）:68－74.

其中主要包括了作者（Author）、題目（Title）、期刊（Journal）、年份（Year）、卷（Volume）、期（NO.）、頁(yè)碼（Page）等狀態(tài)。

針對(duì)該實(shí)際應(yīng)用，對(duì)二階HMM中各個(gè)參數(shù)的定義如下:

1）S:模型狀態(tài)集，即文章頭部信息主要狀態(tài)抽取域，狀態(tài)集可以表示為S＝｛S1，S2，…，Si，Sj，…，SN｝，t時(shí)刻系統(tǒng)所處的狀態(tài)為qt，qt∈S。

2）V:模型輸出的觀察集，包含具體抽取信息域的字符串，記為V＝｛V1，V2，…，VM｝，t時(shí)刻的觀察值為ot，ot∈V。

3）A1，A2:狀態(tài)轉(zhuǎn)移概率分布A1＝｛aij｝，A2＝｛aijk｝，其中

4）B1，B2:觀察值概率分布B1＝｛bi（k）｝，B2＝｛bij（k）｝，其中

5）π:模型初始狀態(tài)分布，即第i個(gè)狀態(tài)為初始狀態(tài)的概率

根據(jù)各個(gè)參數(shù)的說(shuō)明和式（3）－式（7），HMM2可記為λ＝（S，V，A1，A2，B1，B2，π）。

3 SA－HMM2的訓(xùn)練算法

H MM1對(duì)模型參數(shù)初值十分敏感，訓(xùn)練算法選取不當(dāng)極易得到局部最優(yōu)模型參數(shù)，影響信息抽取準(zhǔn)確度?？紤]到SA算法是一個(gè)全局最優(yōu)化算法，本文提出SA－HMM2的訓(xùn)練算法，對(duì)獲取的網(wǎng)頁(yè)源碼進(jìn)行預(yù)處理，將預(yù)處理后的HTML文件利用基于可視化的網(wǎng)頁(yè)分割算法（vision－based page segmentation，VIPS）［10］進(jìn)行處理得到狀態(tài)轉(zhuǎn)移序列。隨機(jī)設(shè)置初始參數(shù)，利用SA算法進(jìn)行訓(xùn)練，得到HMM2全局最優(yōu)模型參數(shù)。SA－HMM2的訓(xùn)練算法流程，如圖1所示。

圖1 基于SA－HMM2的訓(xùn)練算法流程

具體算法步驟描述如下:

步驟1 利用Jsoup開源工具獲取網(wǎng)頁(yè)HTML源碼，將網(wǎng)頁(yè)中非標(biāo)簽對(duì)處理成標(biāo)簽對(duì)；利用正則表達(dá)式去除廣告、腳本信息；

步驟2 利用VIPS算法將網(wǎng)頁(yè)分割成狀態(tài)轉(zhuǎn)移序列；

步驟3 初始化模擬退火算法參數(shù):初始溫度:θ←T0（T0充分大）；隨機(jī)產(chǎn)生一個(gè)初始最優(yōu)點(diǎn)S（作為當(dāng)前最優(yōu)解）；每個(gè)T值的迭代次數(shù)L；

步驟4 對(duì)k＝1，…，L（k為降溫次數(shù)）做步驟5到步驟8；

步驟5 產(chǎn)生新解S’，計(jì)算增量Δ←P’（O｜λ）－P（O｜λ），其中P（O｜λ）為評(píng)價(jià)函數(shù)；

步驟6 如果Δ＜0，則接受S’作為當(dāng)前最優(yōu)解；如果Δ≥0，則以概率p＝exp（－Δ/θ）接受，作為新的當(dāng)前解，若不接受，則再次迭代；

步驟7 如果k＜最大迭代次數(shù)，則令k←k＋1，轉(zhuǎn)向步驟5；

步驟8 逐步降溫:依照T（k＋1）＝λ×T（k）（0＜λ＜1.0）降低控制溫度T（k＋1），如果未到冷卻狀態(tài)，則θ←T（k＋1），轉(zhuǎn)步驟4；否則轉(zhuǎn)步驟9；

步驟9 當(dāng)前解作為最優(yōu)解輸出，得到最優(yōu)HMM2的模型參數(shù)。

4 基于SA－HMM2的Web信息抽取

4.1 改進(jìn)的Viterbi算法

Viterbi算法用來(lái)解決解碼問(wèn)題，即確定最優(yōu)路徑。對(duì)于一個(gè)給定的觀測(cè)序列O＝（o1，o2，…，oT）和一個(gè)HMM2λ＝（S，V，A1，A2，B1，B2，π），計(jì)算與序列O相對(duì)應(yīng)的“最佳”狀態(tài)序列Q＊，即P（Q｜O，λ）最大時(shí)的狀態(tài)序列Q＊［11］。

HMM2對(duì)參數(shù)定義進(jìn)行了調(diào)整，因此傳統(tǒng)的Viterbi算法不能應(yīng)用于HMM2模型。定義δt（i，j）為t時(shí)刻沿狀態(tài)序列q1，q2，…，qt，且qt－1＝Si，qt＝Sj產(chǎn)生出的序列o1，o2，…，ot的最大概率，即

求解最佳狀態(tài)序列Q＊的過(guò)程為［12］:

（1）初始化

（2）遞歸

（3）終止

（4）求取最佳狀態(tài)序列

4.2 基于SA－HMM2的Web信息抽取過(guò)程

基于SA－H MM2的Web信息抽取可分為網(wǎng)頁(yè)預(yù)處理、獲取狀態(tài)轉(zhuǎn)移序列、模型訓(xùn)練和信息抽取等4個(gè)階段，抽取過(guò)程如圖2所示。

首先對(duì)網(wǎng)頁(yè)進(jìn)行預(yù)處理，去除無(wú)關(guān)信息，得到清洗后的HTML文件；然后利用VIPS算法對(duì)清洗結(jié)果進(jìn)行切割處理，得到H MM2的狀態(tài)轉(zhuǎn)移序列；接著，隨機(jī)設(shè)置HMM2初始參數(shù)，利用SA算法進(jìn)行訓(xùn)練，獲取全局最優(yōu)模型參數(shù)；接下來(lái)，利用Baum－Welch算法對(duì)HMM2訓(xùn)練，構(gòu)建HMM2模型；最后利用改進(jìn)的Viterbi算法求解出最佳狀態(tài)序列。

圖2 基于SA－HMM2的Web信息抽取框架

5 實(shí)驗(yàn)與分析

為了驗(yàn)證基于SA－HMM2的Web信息抽取有效性，以論文頭部為驗(yàn)證數(shù)據(jù)集進(jìn)行信息抽取。本方法的Web信息抽取過(guò)程如下:

（1）網(wǎng)頁(yè)預(yù)處理:對(duì)Web網(wǎng)頁(yè)中存在的廣告、導(dǎo)航、版權(quán)等與主題無(wú)關(guān)的信息進(jìn)行去除；將標(biāo)簽不完整或不規(guī)范的HTML源文件進(jìn)行清理修正，有利于狀態(tài)轉(zhuǎn)移序列的獲取。

（2）獲取狀態(tài)轉(zhuǎn)移序列:對(duì)預(yù)處理后的HTML文件，使用VIPS算法將其分割成多個(gè)小塊，作為HMM2的狀態(tài)轉(zhuǎn)移序列，提高信息抽取準(zhǔn)確度。

（3）模型訓(xùn)練:隨機(jī)設(shè)置HMM2初始參數(shù)，結(jié)合獲取到的狀態(tài)轉(zhuǎn)移序列，利用SA算法進(jìn)行訓(xùn)練，得到HMM2全局最優(yōu)模型參數(shù)。

（4）抽取信息:對(duì)測(cè)試網(wǎng)頁(yè)進(jìn)行預(yù)處理和狀態(tài)轉(zhuǎn)移序列的獲取，利用模型訓(xùn)練輸出H MM2，結(jié)合改進(jìn)的Viterbi算法獲取最佳狀態(tài)序列。

實(shí)驗(yàn)中，語(yǔ)料是從萬(wàn)方數(shù)據(jù)庫(kù)中隨機(jī)抽取的2000條論文記錄，隨機(jī)取出1800條作為訓(xùn)練語(yǔ)料，剩余200條作為測(cè)試集。在SA－HMM2訓(xùn)練算法中，初始溫度T＝2000，衰減溫度為0.90，退火迭代次數(shù)k＝1000。表1是基于HMM、基于GA－HMM的Web信息抽取方法和本文方法的實(shí)驗(yàn)結(jié)果。

從表1的實(shí)驗(yàn)結(jié)果可以看出，基于HMM的方法實(shí)驗(yàn)結(jié)果不太理想，這是由于訓(xùn)練算法Baum－Welch對(duì)初值敏感，容易陷入局部最小值；基于GA－HMM的方法在各抽取域的召回率和準(zhǔn)確度均有提高；而本文基于SA－HMM2方法的準(zhǔn)確度和召回率平均分別提高了約8%、5%。＜title＞域的準(zhǔn)確度和召回率提高了約44%和18%，這是因?yàn)椴扇×顺槿∏邦A(yù)處理和分塊網(wǎng)頁(yè)，減少了無(wú)關(guān)信息；由于部分期刊沒(méi)有Volume信息或者部分頭部信息書寫不規(guī)范，導(dǎo)致＜Volume＞和＜NO.＞的抽取準(zhǔn)確度和召回率比其它抽取域低；其它狀態(tài)的抽取準(zhǔn)確度和召回率總體上都有提高，體現(xiàn)了本文方法對(duì)錯(cuò)誤信息的識(shí)別能力。

當(dāng)比較兩個(gè)不同信息抽取系統(tǒng)的性能時(shí)，一般使用抽取準(zhǔn)確度和召回率這兩個(gè)指標(biāo)的綜合值Fβ＝1。從表2可以得出，本文方法比前兩種方法分別提高了約21%和7%，體現(xiàn)了新方法的有效性。

表1 基于HMM、基于GA－HMM和本文方法實(shí)驗(yàn)結(jié)果比較

表2 基于HMM、基于GA－HMM和本文方法平均Fβ＝1值比較

6 結(jié)束語(yǔ)

本文提出了一種基于SA－HMM2的Web信息抽取方法，利用提出的SA－HMM2訓(xùn)練算法獲取HMM2參數(shù)，解決了H MM1對(duì)初值敏感的問(wèn)題；HMM2考慮了模型狀態(tài)和概率間的關(guān)聯(lián)性，使得Web信息抽取精度提高。對(duì)網(wǎng)頁(yè)進(jìn)行預(yù)處理和分塊，得到HMM2的狀態(tài)轉(zhuǎn)移序列，采用SA－HMM2訓(xùn)練算法獲取最佳的HMM2參數(shù)，利用改進(jìn)的Viterbi算法實(shí)現(xiàn)了Web信息抽取。

實(shí)驗(yàn)結(jié)果表明，新方法比基于HMM以及基于GAHMM的信息抽取方法具有更好的性能，在信息抽取的精確度和召回率都有明顯提高，平均綜合值Fβ＝1分別提高了約21%和7%。但是，SA算法要求溫度足夠高、降溫速度足夠慢并在每個(gè)溫度T下進(jìn)行Metropolis抽樣，導(dǎo)致搜索過(guò)程冗長(zhǎng)，效率低下。在實(shí)際應(yīng)用中，如何設(shè)置初始參數(shù)，提高搜索效率，值得進(jìn)一步深入研究。

［1］LIANG Jiguang，TIAN Junhua，XIONG Ling.Research on information extraction based on second－order HMM［J］.Journal of Intelligence，2011，30（7）:169－171（in Chinese）.［梁吉光，田俊華，熊玲.基于二階HMM的信息抽取研究［J］.情報(bào)雜志，2011，30（7）:169－171.］

［2］CHEN Zhao，ZHANG Dongmei.Survey of Web information extraction technologies［J］.Application research of computers，2010，12（12）:4401－4405（in Chinese）.［陳釗，張冬梅.Web信息抽取綜述［J］.計(jì)算機(jī)應(yīng)用研究，2010，12（12）:4401－4405.］

［3］MA Yongjin.Applying symbol feature－based HMM in WEB information extraction［J］.Computer Applications and Software，2009，26（5）:281－284（in Chinese）.［馬永進(jìn).基于符號(hào)特征的隱馬模型在WEB信息抽取中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用與軟件，2009，26（5）:281－284.］

［4］XIAO Jiyi，ZOU Lamei，LI Chuanqi.Hybrid genetic algorithm and hidden Markov model for Web information extraction［J］.Computer Engineering and Applications，2008，44（18）:132－135（in Chinese）.［肖基毅，鄒臘梅，李傳琦.混合遺傳算法和隱馬爾可夫模型的Web信息抽?。跩］.計(jì)算機(jī)工程與應(yīng)用，2008，44（18）:132－135.］

［5］LI Rong，HU Zhijun，ZHENG Jiaheng.Improvement of Web information extraction based on genetic algorithm and hidden Markov model［J］.Computer Science，2012，39（3）:196－199（in Chinese）.［李榮，胡志軍，鄭家恒.基于遺傳算法和隱馬爾可夫模型的Web信息抽取的改進(jìn)［J］.計(jì)算機(jī)科學(xué)，2012，39（3）:196－199.］

［6］ZHOU Shunxian，LIN Yaping，WANG Yaonan，et al.Text information extraction based on the second－order hidden Markov model［J］.Acta Electronica Sinica，2007，35（11）:2226－2231（in Chinese）.［周順先，林亞平，王耀南，等.基于二階隱馬爾可夫模型的文本信息抽?。跩］.電子學(xué)報(bào)，2007，35（11）:2226－2231.］

［7］ZHU Haodong，ZHONG Yong.A kind of renewed simulated annealing algorithm［J］.Computer Technology and Development，2009，19（6）:32－35（in Chinese）.［朱顥東，鐘勇.一種改進(jìn)的模擬退火算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（6）:32－35.］

［8］ZOU Lamei，GONG Xiangjian，XIAO Fang，et al.Web information extraction based on simulated annealing algorithm and hidden Markov model［J］.Journal of University of South China（Science and Technology），2011，25（1）:70－74（in Chinese）.［鄒臘梅，龔向堅(jiān)，肖芳，等.基于模擬退火算法與隱馬爾科夫模型的Web信息抽取［J］.南華大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，25（1）:70－74.］

［9］FENG Yuejiao，HE Xingshi.The principle and achieving of second－order hidden Markov model［J］.Value Engineering，2009，28（12）:103－105（in Chinese）.［豐月姣，賀興時(shí).二階隱馬爾科夫模型的原理與實(shí)現(xiàn)［J］.價(jià)值工程，2009，28（12）:103－105.］

［10］CAI Deng，YU Shipeng，WEN Jirong，et al.VIPS:A vision based page segmentation algorithm［R］.Microsoft Research，2003.

［11］ZOU Lamei.Research of Web text mining technology based on hidden Markov model［D］.Hengyang:University of South China，2007（in Chinese）.［鄒臘梅.基于隱馬爾可夫模型的Web文本挖掘技術(shù)研究［D］.衡陽(yáng):南華大學(xué)，2007.］

［12］LIU Binbin.Reserch and improvement of Web information extraction method based on HMM model［D］.Chongqing:Chongqing University，2008（in Chinese）.［劉斌斌.基于HMM模型的Web信息抽取方法的研究與改進(jìn)［D］.重慶市:重慶大學(xué)，2008.］