一種基于SVM的Web信息自動(dòng)化抽取方法

王亞利 李曉靜

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

一種基于SVM的Web信息自動(dòng)化抽取方法

王亞利 李曉靜

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

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

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

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

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

1 相關(guān)理論

1.1 支持向量機(jī)

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

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

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

在特征空間中求一個(gè)分類超平面(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對(duì)應(yīng)的樣本點(diǎn)為支持向量。

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

Web頁面主要是以HTML頁面的形式出現(xiàn)的，HTML語言具有自身的結(jié)構(gòu)特點(diǎn)。用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信息自動(dòng)化抽取

2.1 信息抽取方法

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

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

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

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

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

本模塊中的網(wǎng)頁去噪操作是一個(gè)重要環(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)記時(shí)有太多的自由。例如，網(wǎng)頁制作者可以使用段落標(biāo)識(shí)符＜P＞來標(biāo)明段落的開始，但是卻并不一定要在段落的末尾使用段落結(jié)束符＜/P＞。HTML文檔中的標(biāo)簽交叉使用也不報(bào)錯(cuò)，如＜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)，再對(duì)DOM樹進(jìn)行操作，過濾掉網(wǎng)頁中包含有噪音信息的節(jié)點(diǎn)［2］。它可以簡化網(wǎng)頁內(nèi)標(biāo)簽結(jié)構(gòu)，減小網(wǎng)頁規(guī)模，降低抽取規(guī)則的學(xué)習(xí)和數(shù)據(jù)抽取所需的時(shí)間和空間開銷，是系統(tǒng)預(yù)處理過程中必不可少的重要環(huán)節(jié)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)計(jì)算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ù)抽取時(shí)抽取的信息精度會(huì)進(jìn)一步提高。

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

3.1 評(píng)價(jià)指標(biāo)

Web信息抽取領(lǐng)域內(nèi)的主要評(píng)價(jià)指標(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)對(duì)Precision和Recall的側(cè)重有所不同。為了綜合評(píng)價(jià)抽取系統(tǒng)的性能，提出了各種綜合評(píng)價(jià)指標(biāo)，如：F－度量 (F－measure)，該指標(biāo)可以計(jì)算Recall和Precision的加權(quán)幾何平均值，其計(jì)算公式如下［6］：

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

4 結(jié)語

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

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

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

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

［4］李文杰，李方方，魏紅．基于支持向量機(jī)的位置相關(guān)計(jì)算［J］．計(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ì)算機(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ì)算機(jī)網(wǎng)絡(luò)、信息系統(tǒng)研究。