王亞利 李曉靜

(濟(jì)源職業(yè)技術(shù)學(xué)院，河南濟(jì)源 459000)

一種基于SVM的Web信息自動化抽取方法

王亞利 李曉靜

(濟(jì)源職業(yè)技術(shù)學(xué)院，河南濟(jì)源 459000)

針對傳統(tǒng)的Web信息抽取方法運(yùn)算量大、自動化程度低的問題，提出了一種基于SVM的WEB信息自動化抽取方法。利用SVM優(yōu)秀的分類性能將網(wǎng)頁中有用數(shù)據(jù)和無用數(shù)據(jù)分類標(biāo)注，有效地完成Web信息抽取任務(wù)，準(zhǔn)確地抽取出所需信息，實現(xiàn)數(shù)據(jù)抽取的自動化。實驗結(jié)果表明，該方法可以有效地獲取網(wǎng)頁信息特征，具有較高的召回率和準(zhǔn)確率。

支持向量機(jī);信息抽取;分類學(xué)習(xí)

信息抽取技術(shù)是近些年來發(fā)展起來的新領(lǐng)域，它是指從自然語言文檔中抽取指定的事件、事實信息，并以結(jié)構(gòu)化形式描述信息，以供信息查詢、文本深層挖掘、自動回答問題等應(yīng)用，從而為人們提供強(qiáng)有力的信息獲取工具。當(dāng)前隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，Web網(wǎng)已經(jīng)成為一個巨大的信息源，數(shù)據(jù)量呈爆炸式的增長，人們更多地開始從網(wǎng)絡(luò)中獲取所需信息。而Web頁面中通常含有大量用戶并不關(guān)心的如動畫廣告、超鏈接和網(wǎng)站版權(quán)等信息，如何從Web頁面中抽取出用戶感興趣的信息已經(jīng)成為當(dāng)前信息領(lǐng)域中的研究熱點之一。

支持向量機(jī) (Support Vector Machines，SVM)技術(shù)作為統(tǒng)計學(xué)習(xí)理論的一種重要發(fā)展成果，因其優(yōu)秀的分類性能，開始被應(yīng)用到信息抽取領(lǐng)域中?；赟VM的Web信息抽取方法是一種綜合利用網(wǎng)頁各種特征的信息抽取方法，它通過對網(wǎng)頁各種特征的分析將網(wǎng)頁特征向量化，再使用SVM優(yōu)秀的分類性能將網(wǎng)頁中的每個信息片斷進(jìn)行分類標(biāo)注，最終實現(xiàn)分類抽取。

1 相關(guān)理論

1.1 支持向量機(jī)

支持向量機(jī)方法是建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷，以期獲得最好的推廣能力［1］，基于SVM的機(jī)器學(xué)習(xí)方法其主要思想可以描述為：

給定樣本點，考慮使用某個特征空間的超平面對給定訓(xùn)練數(shù)據(jù)集作二值分類問題：

其中向量xi可能是從目標(biāo)樣本集中抽取的某些特征而直接構(gòu)造的向量，也可能是原始向量通過某個核函數(shù)映射到核空間中的映射向量。

在特征空間中求一個分類超平面(w·x)+b=0，關(guān)鍵是求其系數(shù)w和b。由于SVM理論要求分離超平面具有良好的分類特性，即必須滿足最優(yōu)分類超平面的條件：

為了找到最優(yōu)分類超平面，根據(jù)最優(yōu)理論和借助Lagrange函數(shù)將原問題轉(zhuǎn)化成為求解標(biāo)注型二次規(guī)劃問題：

通常ai≥0對應(yīng)的樣本點為支持向量。

1.2 Web結(jié)構(gòu)特征

Web頁面主要是以HTML頁面的形式出現(xiàn)的，HTML語言具有自身的結(jié)構(gòu)特點。用HTML語言寫成的源文本由不同含義的標(biāo)記 (例如＜Title＞、＜Body＞、＜Div＞等)，各種超鏈接、導(dǎo)航條等非主題信息，和文章的正文文本組成。雖然網(wǎng)頁數(shù)據(jù)屬于一種半結(jié)構(gòu)化的數(shù)據(jù)，但從其結(jié)構(gòu)來看通常包含有兩大部分信息，即內(nèi)容信息和格式信息。內(nèi)容信息即是文章的正文文本，主要是通過瀏覽器顯示給用戶的信息，在內(nèi)容信息中被標(biāo)記分割開的塊稱為信息片斷。格式信息即是由非主題信息組成，在網(wǎng)頁中用于表示和解釋內(nèi)容信息的信息。

2 基于SVM的Web信息自動化抽取

2.1 信息抽取方法

傳統(tǒng)的Web信息抽取方法是利用分裝器對網(wǎng)頁進(jìn)行模式匹配實現(xiàn)數(shù)據(jù)抽取，該方法需要用戶大量的標(biāo)記數(shù)據(jù)進(jìn)行訓(xùn)練學(xué)習(xí)，從而導(dǎo)致其自動化程度降低。本文提出以分類的方式來處理Web信息抽取問題，其主要思想是：先將網(wǎng)頁中不同的信息片斷歸納到不同的類別，然后將網(wǎng)頁中有用數(shù)據(jù)和無用數(shù)據(jù)正確區(qū)分開，再將特征向量化的網(wǎng)頁數(shù)據(jù)作用于SVM學(xué)習(xí)機(jī)中，最后利用SVM優(yōu)秀的分類性能來實現(xiàn)數(shù)據(jù)的自動分類抽取。

本文提出的基于SVM的Web信息自動化抽取框架包括三個功能器：網(wǎng)頁預(yù)處理、特征提取和數(shù)據(jù)抽取，如圖1所示。從圖中可以看出，在數(shù)據(jù)抽取過程中，SVM分類器是通過對樣本的學(xué)習(xí)來產(chǎn)生分類器，進(jìn)而實現(xiàn)數(shù)據(jù)的分類抽取。

圖1 基于SVM的Web信息抽取框架

2.2 網(wǎng)頁預(yù)處理

網(wǎng)頁預(yù)處理模塊分為網(wǎng)頁采集子模塊和網(wǎng)頁去噪模塊，網(wǎng)頁采集就是利用一些網(wǎng)頁抓取程序如crawler對網(wǎng)絡(luò)上的原始網(wǎng)頁進(jìn)行抓取，并將獲取到的網(wǎng)頁存入到本地數(shù)據(jù)庫中;網(wǎng)頁去噪的主要作用是規(guī)范化解析網(wǎng)頁，對所獲得的樣本網(wǎng)頁和目標(biāo)網(wǎng)頁進(jìn)行修復(fù)，并對其中的噪音進(jìn)行過濾，去除掉網(wǎng)頁中的干擾信息，以提高數(shù)據(jù)抽取的效率。

本模塊中的網(wǎng)頁去噪操作是一個重要環(huán)節(jié)，由于Web頁面中內(nèi)容繁多，除了包含主體信息以外，還包括標(biāo)簽以及指向圖片、音頻和視頻文件、與其他網(wǎng)頁的鏈接以及廣告信息、版權(quán)信息等眾多“噪音”內(nèi)容。這些噪音數(shù)據(jù)降低了主題信息數(shù)據(jù)抽取的準(zhǔn)確性和效率。另外Web上的數(shù)據(jù)大多是用HTML編寫的，而HTML的規(guī)則不嚴(yán)格，它允許網(wǎng)頁制作者在使用標(biāo)記時有太多的自由。例如，網(wǎng)頁制作者可以使用段落標(biāo)識符＜P＞來標(biāo)明段落的開始，但是卻并不一定要在段落的末尾使用段落結(jié)束符＜/P＞。HTML文檔中的標(biāo)簽交叉使用也不報錯，如＜tr＞＜td＞＜/tr＞＜/td＞。所以從這些文檔中抽取數(shù)據(jù)變得比較困難，相當(dāng)于從非結(jié)構(gòu)化文本中抽取數(shù)據(jù)。網(wǎng)頁去噪模塊先將網(wǎng)頁中不規(guī)范或不完整的HTML文檔轉(zhuǎn)換為結(jié)構(gòu)良好的XHTML文檔，使用解析函數(shù)將其進(jìn)一步解析成DOM樹結(jié)構(gòu)，再對DOM樹進(jìn)行操作，過濾掉網(wǎng)頁中包含有噪音信息的節(jié)點［2］。它可以簡化網(wǎng)頁內(nèi)標(biāo)簽結(jié)構(gòu)，減小網(wǎng)頁規(guī)模，降低抽取規(guī)則的學(xué)習(xí)和數(shù)據(jù)抽取所需的時間和空間開銷，是系統(tǒng)預(yù)處理過程中必不可少的重要環(huán)節(jié)。

2.3 網(wǎng)頁特征提取

特征提取模塊的主要作用是獲取DOM樹中信息片斷的特征，以此將網(wǎng)頁特征向量化。按照網(wǎng)頁中各種字符的不同作用，我們可以從網(wǎng)頁中獲取四類不同的特征：前后文特征，即網(wǎng)頁中信息片斷的前后信息，通常對信息片斷具有提示作用 (包括前引導(dǎo)詞和后引導(dǎo)詞)。布局特征，即信息片斷在網(wǎng)頁中的位置布局是相對確定的，DOM樹中的層次結(jié)構(gòu)路徑即可作為信息片斷的“坐標(biāo)”［3］。視覺特征，即用于表示信息片斷的大小、顏色、文本長短等特征。普通特征，即信息片斷自身之間所存在的區(qū)別。

上述四類特征可以將網(wǎng)頁中的信息片斷特征向量化，其獲取方法難易程度不同，視覺特征和普通特征只需檢測網(wǎng)頁即可獲得;前后文特征需要定位前后引導(dǎo)詞來獲取;布局特征的獲得相對來說比較復(fù)雜，算法可以描述為：首先檢查頁面的當(dāng)前標(biāo)記，若當(dāng)前標(biāo)記是頭標(biāo)記，并且該頭標(biāo)記的前一個標(biāo)記是頭標(biāo)記，將該頭標(biāo)記加入到路徑標(biāo)記中;若該頭標(biāo)記的前一個標(biāo)記是尾標(biāo)記，修改其路徑序號值;若當(dāng)前標(biāo)記是尾標(biāo)記，移除末端標(biāo)記。判斷尾標(biāo)記的前一個標(biāo)記是否是尾標(biāo)記，若是，移除末端標(biāo)記，并且重置前一個標(biāo)記。

2.4 數(shù)據(jù)抽取

數(shù)據(jù)抽取就是從目標(biāo)網(wǎng)頁中抽取出用戶所需要的信息，該模塊是整個方法的核心部分。為了實現(xiàn)有效抽取，需要通過多種算法對網(wǎng)頁文檔中的前后文特征、普通特征、視覺特征和布局特征進(jìn)行訓(xùn)練，以至達(dá)到將網(wǎng)頁中的信息片斷進(jìn)行分類標(biāo)注的目的。當(dāng)網(wǎng)頁中的信息用特征來表示的時候，通常比普通的文集更多，采用傳統(tǒng)分類算法時容易產(chǎn)生“過學(xué)習(xí)”問題［4］;同時，系統(tǒng)需要用戶提供一定數(shù)量的學(xué)習(xí)樣本，而這些樣本所能提供的特征信息有限，不能夠很好的刻畫出數(shù)據(jù)的總體分布特征，從而導(dǎo)致在使用傳統(tǒng)分類算法時容易出現(xiàn)誤差較大的情況?；谏鲜鲈颍疚牟捎肧VM作為分類方法的核心部分。

數(shù)據(jù)抽取模塊又具體劃分為分類抽取學(xué)習(xí)階段和數(shù)據(jù)抽取階段兩部分。在方法的分類抽取學(xué)習(xí)階段，特征向量化的樣本網(wǎng)頁被不斷訓(xùn)練并生成一個分類決策函數(shù)，即SVM分類器;在方法的數(shù)據(jù)抽取階段，SVM分類器對已到達(dá)的具有特征向量化的目標(biāo)網(wǎng)頁中的信息片斷進(jìn)行分類標(biāo)注，并將已標(biāo)注好類別的信息片斷存儲到本地數(shù)據(jù)庫中。

在SVM分類待抽取數(shù)據(jù)時，為提高數(shù)據(jù)抽取效率，它會試圖尋找最優(yōu)分類超平面。其中SVM的有效學(xué)習(xí)也很重要，具體的學(xué)習(xí)過程如下：

先假設(shè)訓(xùn)練樣本T為：

達(dá)到最小值，本算法最終將轉(zhuǎn)化成為一個二次型尋優(yōu)問題。

1)對于線性可分的情況，即求

2)對于線性不可分的情況，引入錯誤懲罰系數(shù)C，即求

3)對于非線性的情況，用核函數(shù)K( xi，xj)代替上式中 ( xi·xj)，即求

為解決上述二次型尋優(yōu)問題，采用序貫最小優(yōu)化算法 (Sequential Minimal Optimization，簡稱SMO)，關(guān)于SMO算法收斂的理論分析在文獻(xiàn) ［5］中有詳盡的證明。然后利用關(guān)系式：

最后，為了判別夠格樣本t是否屬于類a，還需要通過以下兩個步驟：

1)計算x=φ(t);

如果 ()f x=1，則t屬于類a，否則就不屬于。

當(dāng)SVM終止學(xué)習(xí)后，目標(biāo)網(wǎng)頁中的信息片斷就已經(jīng)被正確的分類標(biāo)注。SVM在學(xué)習(xí)的過程中，能夠利用少量樣本所提供的有限信息更好的刻畫出數(shù)據(jù)的總體分布特征，使用該方法在Web數(shù)據(jù)抽取時抽取的信息精度會進(jìn)一步提高。

3 實驗結(jié)果和分析

3.1 評價指標(biāo)

Web信息抽取領(lǐng)域內(nèi)的主要評價指標(biāo)是召回率 (#Recall)和準(zhǔn)確率 (#Precision)，公式為：

召回率=被正確抽取出來的數(shù)據(jù) (#Real)/應(yīng)該抽取出來的正確數(shù)據(jù) (#True);

準(zhǔn)確率=被正確抽取出來的數(shù)據(jù) (#Real)/所有被抽出的數(shù)據(jù)總數(shù) (#Total)。

召回率和準(zhǔn)確率的取值范圍都在 ［0，1］之間，兩者之間存在著反比關(guān)系，不同的數(shù)據(jù)抽取系統(tǒng)對Precision和Recall的側(cè)重有所不同。為了綜合評價抽取系統(tǒng)的性能，提出了各種綜合評價指標(biāo)，如：F－度量 (F－measure)，該指標(biāo)可以計算Recall和Precision的加權(quán)幾何平均值，其計算公式如下［6］：

β為召回率和準(zhǔn)確率的相對權(quán)重。β大于1時，準(zhǔn)確率比召回率更重要;β小于1時，召回率比準(zhǔn)確率更重要;β為1時，二者同樣重要。

3.2 實驗結(jié)果及分析

利用基于XML的Web信息抽取方法，以．NET為開發(fā)平臺，采用C#工具開發(fā)了信息抽取模型系統(tǒng)。系統(tǒng)通過網(wǎng)頁抓取程序從網(wǎng)站獲取頁面，經(jīng)過頁面清洗，實現(xiàn)去噪操作;根據(jù)樣本頁面學(xué)習(xí)獲取到信息片斷的特征，采用SVM分類器對各個信息片斷進(jìn)行分類標(biāo)注，將結(jié)果存儲到XML文檔中，最后將抽取結(jié)果以頁面形式顯示。

本文利用抽取系統(tǒng)進(jìn)行4個網(wǎng)站某項專題的信息抽取，將搜狐、新浪、網(wǎng)易和騰訊作為數(shù)據(jù)來源，對網(wǎng)站上有關(guān)2011年金融危機(jī)的新聞進(jìn)行抽取測試，實驗的目的是驗證SVM在Web信息抽取中的可行性和數(shù)據(jù)抽取的召回率和準(zhǔn)確率情況。按照3.1節(jié)中的評價標(biāo)準(zhǔn)，當(dāng)取β=1時所得的抽取測試結(jié)果如表1所示。

表1 四個網(wǎng)站2011年金融危機(jī)新聞抽取測試結(jié)果

實驗數(shù)據(jù)結(jié)果表明，使用SVM分類器可以很好地獲取網(wǎng)頁信息特征，該方法可以有效地完成信息抽取任務(wù)，準(zhǔn)確的抽取出所需信息，實現(xiàn)數(shù)據(jù)抽取的自動化。

4 結(jié)語

如何能高效抽取出網(wǎng)頁有效信息一直以來是人們研究的熱點之一，本文給出一種基于SVM的Web信息自動化抽取方法，將信息抽取技術(shù)和機(jī)器學(xué)習(xí)中的分類方法相結(jié)合，通過SVM將網(wǎng)頁中的信息片斷進(jìn)行分類標(biāo)注，用戶只需要提供少量的信息就可以完成抽取任務(wù)。實驗結(jié)果表明：該方法召回率和準(zhǔn)確率較高，對于結(jié)構(gòu)復(fù)雜的網(wǎng)頁具有良好的健壯性和適應(yīng)性。

［1］許建華，張學(xué)工．統(tǒng)計學(xué)理論基礎(chǔ)［M］．北京：電子工業(yè)出版社，2004．

［2］袁明軒，張選平，蔣宇，等．一種基于同層網(wǎng)頁相似性去除網(wǎng)頁噪音的方法［J］．計算機(jī)工程，2006(12)：61－63．

［3］李文立，王樂超，宋春雷．基于HTML樹和模板的文獻(xiàn)信息提取方法研究［J］．計算機(jī)應(yīng)用研究，2010(12)：4615－4617．

［4］李文杰，李方方，魏紅．基于支持向量機(jī)的位置相關(guān)計算［J］．計算機(jī)仿真，2008(2)：124－126．

［5］Keerthi S S．Convergence of a Generalized SMO Algorithm for SVM Classifier Design TR CD －00－01Control Division Dept of Mecha And Prod［D］．Singapore：Engineering National University of Singapore，2000．

［6］李保利，陳玉忠，俞士汶．信息抽取研究綜述［J］．計算機(jī)工程與應(yīng)用，2003(10)：1－5．

Web Information Automatic Extraction Method Based on SVM

WANG Ya-liLI Xiao-jing
(Jiyuan Vocational and Technical College，Jiyuan 459000，China)

Given the problems of heavy computation and low automatic level existed in traditional Web information extraction method，this paper proposes a kind of web information automatic extraction method based on SVM，effectively completing the task of Web information extraction and precisely extracting information so as to realize automation of data extraction．The results show that SVM can be used in web information extraction and it has higher rates of recall and precision．

support vector machine;web information extraction;classification learning

TP311

A

1009－0312(2012)05－0053－05

2012－09－01

王亞利 (1974—)，女，河南濟(jì)源人，副教授，碩士，主要從事計算機(jī)網(wǎng)絡(luò)、信息系統(tǒng)研究。