基于模擬退火算法和二階HMM的Web信息抽取

李偉男，李書琴，景 旭，魏 露，李新樂

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

0 引 言

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

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

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

1 模擬退火算法

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

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

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

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

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

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

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

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

2 HMM2的建立

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

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

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

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

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

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

針對該實際應用，對二階HMM中各個參數(shù)的定義如下:

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

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

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

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

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

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

3 SA－HMM2的訓練算法

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

圖1 基于SA－HMM2的訓練算法流程

具體算法步驟描述如下:

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

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

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

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

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

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

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

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

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

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

4.1 改進的Viterbi算法

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

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

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

（1）初始化

（2）遞歸

（3）終止

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

4.2 基于SA－HMM2的Web信息抽取過程

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

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

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

5 實驗與分析

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

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

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

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

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

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

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

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

表1 基于HMM、基于GA－HMM和本文方法實驗結果比較

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

6 結束語

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

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

［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］.情報雜志，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］.計算機應用研究，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）.［馬永進.基于符號特征的隱馬模型在WEB信息抽取中的應用［J］.計算機應用與軟件，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信息抽?。跩］.計算機工程與應用，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］.計算機科學，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）.［周順先，林亞平，王耀南，等.基于二階隱馬爾可夫模型的文本信息抽取［J］.電子學報，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］.計算機技術與發(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）.［鄒臘梅，龔向堅，肖芳，等.基于模擬退火算法與隱馬爾科夫模型的Web信息抽?。跩］.南華大學學報（自然科學版），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）.［豐月姣，賀興時.二階隱馬爾科夫模型的原理與實現(xiàn)［J］.價值工程，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文本挖掘技術研究［D］.衡陽:南華大學，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信息抽取方法的研究與改進［D］.重慶市:重慶大學，2008.］