基于CSS視覺(jué)分塊的Web碎片信息抽取算法

摘 要：為進(jìn)一步解決在半結(jié)構(gòu)化的Web頁(yè)面中抽取Web碎片信息的困難，針對(duì)Web頁(yè)面設(shè)計(jì)的目的是給用戶顯示相關(guān)的信息，瀏覽器只是呈現(xiàn)的中間手段，在抽取Web碎片信息時(shí)應(yīng)該“以人為本”，從“人”的視覺(jué)效果出發(fā)，將Web頁(yè)面按照CSS視覺(jué)效果進(jìn)行分塊，提出一種基于CSS視覺(jué)分塊的Web碎片信息抽取算法。以隨機(jī)輸入的1000個(gè)Web碎片信息站點(diǎn)作為實(shí)驗(yàn)對(duì)象，實(shí)驗(yàn)結(jié)果表明，算法具有良好的性能，達(dá)到了較高的召回率與查準(zhǔn)率。

關(guān)鍵詞：Web；Web碎片信息；CSS；信息抽取

中圖分類號(hào)：TP391

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，互聯(lián)網(wǎng)的信息呈現(xiàn)方式正在發(fā)生日新月異的變化，微博的出現(xiàn)使人們隨時(shí)隨地都可以分享自己的信息。同時(shí)，微博的出現(xiàn)也正在改變著人們關(guān)注信息的習(xí)慣，網(wǎng)民們獲取信息的方式越來(lái)越“碎片化”，從傳統(tǒng)的“一對(duì)多”的信息分享方式變成的“多對(duì)多”的信息分享方式。也就是說(shuō)，在信息碎片化的時(shí)代，每個(gè)人都是信息的制造者，也是信息的獲取者。由于每個(gè)人均可以通過(guò)碎片信息發(fā)布平臺(tái)（如新浪微博、騰訊微博）發(fā)布信息，使得碎片信息出現(xiàn)了很大的隨意性，信息的構(gòu)成不再像傳統(tǒng)方式的規(guī)范化，而出現(xiàn)了多元化、異構(gòu)化及碎片化。在進(jìn)行碎片信息抽取的時(shí)候，由于其本身可能只是“只言片語(yǔ)”，就有可能被當(dāng)成信息“噪聲”過(guò)濾了，因此給信息的抽取與整合帶來(lái)了一定的困難，針對(duì)碎片信息所固有的特點(diǎn)，考慮到信息的分享者是“人”，而非瀏覽器本身，對(duì)信息的抽取應(yīng)該從瀏覽器給人的視覺(jué)分塊出發(fā)，提出了一種基于CSS視覺(jué)分塊的Web碎片信息抽取算法。首先對(duì)Web信息抽取的技術(shù)進(jìn)行分析，其次基于CSS視覺(jué)分塊的Web碎片信息抽取算法，然后通過(guò)實(shí)驗(yàn)對(duì)提出的算法進(jìn)行驗(yàn)證與分析，最后對(duì)算法進(jìn)行總結(jié)。

1 Web信息抽取技術(shù)

Web信息抽取的目的就是便于檢索或者數(shù)據(jù)挖掘，從松散的、半結(jié)構(gòu)化的Html網(wǎng)頁(yè)中抽取出有價(jià)值的、隱含的數(shù)據(jù)信息，并將其結(jié)構(gòu)化存入數(shù)據(jù)庫(kù)中。這一概念最早是由Gwiederhold提出的[1]。相應(yīng)地，Web碎片信息抽取就可以引申為：從無(wú)結(jié)構(gòu)或半結(jié)構(gòu)的Web碎片信息網(wǎng)頁(yè)制取出用戶關(guān)心的、有價(jià)值的信息片段，并形成結(jié)構(gòu)化數(shù)據(jù)的過(guò)程[2]。

目前，有很多研究者在研究Web信息抽取的技術(shù)，力求達(dá)到準(zhǔn)確、高效的效果?？v觀目前關(guān)于Web信息抽取的研究成果，不難發(fā)現(xiàn)，抽取的效果取決于是否能準(zhǔn)確找出Web頁(yè)面中的抽取規(guī)則，即抽取規(guī)則的生成。通常有基于統(tǒng)計(jì)理論的抽取技術(shù)、基于DOM樹(shù)的抽取技術(shù)及基于歸納的抽取技術(shù)。

基于統(tǒng)計(jì)理論的抽取技術(shù)是一種傳統(tǒng)的抽取方法，主要思想是通過(guò)統(tǒng)計(jì)網(wǎng)頁(yè)標(biāo)簽所包含的信息量或鏈接文本與普通文本的比值來(lái)獲取網(wǎng)頁(yè)的主題信息。如孫承杰等人提出的通過(guò)獲取網(wǎng)頁(yè)中的

標(biāo)簽的源碼信息，去掉所有的HTML標(biāo)簽，對(duì)文本的長(zhǎng)短進(jìn)行統(tǒng)計(jì)，長(zhǎng)度較大的就是主題信息[3]。如Gupta等人提出利用鏈接文本與普通文本的比值來(lái)確定頁(yè)面中的正文分塊，如果普通文本比例較大，則認(rèn)為是所要抽取的目標(biāo)文本，否則認(rèn)為是噪聲（如廣告信息）[4]?？舍槍?duì)Web信息碎片的抽取，這種方法有其局限性，因?yàn)閃eb信息碎片所占的比重小，有可能會(huì)被當(dāng)作噪聲去掉，會(huì)直接影響抽取算法的召回率。

基于DOM樹(shù)的抽取技術(shù)是通過(guò)DOM解析器將Web頁(yè)面解析為Dom語(yǔ)法樹(shù)[5]，Dom語(yǔ)法樹(shù)的本質(zhì)就是在內(nèi)存中構(gòu)建XML語(yǔ)法樹(shù)，它主要包括根元素（Document Element）與節(jié)點(diǎn)（Node），其中Node能反映出所有Web頁(yè)面的所有結(jié)構(gòu)信息，包括文本信息與屬性信息，方便了對(duì)各節(jié)點(diǎn)的操作?；贒OM樹(shù)的Web信息抽取算法在抽取時(shí)先獲取HTML源碼，再經(jīng)過(guò)預(yù)處理，構(gòu)造XML語(yǔ)法樹(shù)，然后去噪，最后根據(jù)需求抽取信息。如劉軍等人提出的基于DOM的網(wǎng)頁(yè)主題信息的提取技術(shù)[6]，那赫提出的基于DOM的Web主題信息提取系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[7]。

基于歸納的抽取技術(shù)是基于樣本訓(xùn)練的模式，假設(shè)某網(wǎng)站具有信息公用模板，并且此模板下生成了大量的頁(yè)面，然后對(duì)這些頁(yè)面進(jìn)行樣本訓(xùn)練，尋找出網(wǎng)頁(yè)的結(jié)構(gòu)及文本特征的變化規(guī)律，從而獲得頁(yè)面之間相對(duì)穩(wěn)定的相似結(jié)構(gòu)特征，發(fā)生變化的只有文本特征。以此來(lái)歸納內(nèi)網(wǎng)頁(yè)的統(tǒng)一公用模板，并利用公用模板抽取出頁(yè)面的信息。如石倩等人提出的基于規(guī)則歸納的信息抽取系統(tǒng)實(shí)現(xiàn)[8]。但基于歸納的抽取技術(shù)需要大量的相似頁(yè)面作為訓(xùn)練的對(duì)象，不適應(yīng)一些頁(yè)面較少的網(wǎng)站。

2 基于CSS視覺(jué)分塊的Web碎片信息抽取算法

眾所周知，HTML頁(yè)面的編寫(xiě)具有很強(qiáng)的靈活性與隨意性，不同的網(wǎng)頁(yè)設(shè)計(jì)者可以按自己的方式設(shè)計(jì)頁(yè)面，就導(dǎo)致了頁(yè)面呈現(xiàn)出異構(gòu)性，給信息的抽取帶來(lái)了困難。但網(wǎng)頁(yè)開(kāi)發(fā)的目標(biāo)是在瀏覽器上顯示所設(shè)計(jì)的內(nèi)容，把設(shè)計(jì)的視覺(jué)效果通過(guò)瀏覽器根據(jù)設(shè)計(jì)的CSS樣式將其展現(xiàn)給用戶，網(wǎng)頁(yè)設(shè)計(jì)的目的給“人”看的，瀏覽器只是一種顯示的手段。因此，在進(jìn)行Web碎片信息抽取時(shí)，將CSS視覺(jué)分塊引入信息抽取是必要的，因?yàn)镃SS視覺(jué)分塊是從“人”的角度出發(fā)的，不僅僅是瀏覽器。2003年微軟亞洲研究院首先提出了將VIPS（a Vision-based Page Segmentation Algorithm）[9]將視覺(jué)分塊引入到了網(wǎng)頁(yè)信息的分塊之中，VIPS主要依靠計(jì)算分塊的背景顏色、內(nèi)容字體的大小及空白區(qū)域等視覺(jué)特征，根據(jù)HTML標(biāo)簽特征及相關(guān)規(guī)則計(jì)算Web頁(yè)面的視覺(jué)分塊。VIPS算法在某種程度上達(dá)到了Web頁(yè)面視覺(jué)分塊的要求，但算法本身所采用的啟發(fā)式規(guī)則是基于HTML標(biāo)簽結(jié)構(gòu)的。如果能將CSS視覺(jué)特征引入頁(yè)面分塊中，會(huì)更加符合網(wǎng)頁(yè)設(shè)計(jì)的意圖。

定義1 CSS視覺(jué)塊 構(gòu)成Web頁(yè)面的基本單位，也是一個(gè)CSS盒子，如圖1所示。其是一個(gè)矩形的視覺(jué)區(qū)域，由CSS盒子模型的高（height）、寬（width）、外邊距（margin）、內(nèi)邊距（padding）、邊框（border）及內(nèi)容（content）構(gòu)成。即：

CSS-V={height，width，margin，padding，border，content}

其中，content可以是CSS視覺(jué)塊，也可以是文本內(nèi)容，也可以為空。

定義2 CSS頁(yè)面視覺(jué)塊B Web頁(yè)面本身就是一個(gè)CSS視覺(jué)塊，由若干其他的CSS視覺(jué)塊所構(gòu)成。

定義3 CSS普通文本視覺(jué)塊T 內(nèi)容為文本信息的CSS視覺(jué)塊。

定義4 CSS鏈接文本視覺(jué)塊A 內(nèi)容為文本信息且含有鏈接指向的CSS視覺(jué)塊。

定義5 空塊N 內(nèi)容為空的CSS視覺(jué)塊。

算法主要思想：對(duì)于Web碎片信息的抽取往往中關(guān)心上述幾種視覺(jué)塊信息，對(duì)于其他的塊可以作為干擾噪聲去掉。由此根據(jù)Web頁(yè)面的DOM樹(shù)（Document Object Model Tree），計(jì)算出CSS所有的CSS視覺(jué)塊，去掉不屬于{B，T，A}的視覺(jué)塊，生成視覺(jué)塊描述文件。如騰訊微博http：//t.qq.com/xiangchengguan的視覺(jué)塊描述文件如圖2。常言道“物以類聚”，對(duì)于Web碎片信息所在塊的識(shí)別，盡管信息較短，但它們是以“聚集”的方式出現(xiàn)的，所占用塊的面積在整個(gè)頁(yè)面視覺(jué)塊中占有比率應(yīng)不小于30%，同時(shí)它們的個(gè)數(shù)在整個(gè)頁(yè)面中也是最多的。因此，需要對(duì)所有的CSS視覺(jué)塊進(jìn)行分類，分類采用統(tǒng)計(jì)的方法進(jìn)行，即根據(jù)CSS-V中的height、width、margin、padding、border及content進(jìn)行相似度計(jì)算，如果結(jié)果相同就可視為同一類CSS視覺(jué)塊，如對(duì)圖2所示的視覺(jué)塊描述文件進(jìn)行分類可得到表1所示的分類結(jié)果。

由表1可以計(jì)算出，視覺(jué)塊個(gè)數(shù)最多為20，它占用的面積在整個(gè)頁(yè)面中的比率最大，因此其必為Web碎片信息的視覺(jué)塊。

抽取算法分為四步進(jìn)行：

Step1 計(jì)算出CSS所有的CSS視覺(jué)塊；

Step2 刪除不屬于{B，T，A}的視覺(jué)塊，并生成描述視覺(jué)塊的XML文件；

Step3 統(tǒng)計(jì)分類結(jié)果，找出Web信息所在的CSS視覺(jué)塊，并刪除其他視覺(jué)塊；

Step4 對(duì)Web信息所在的CSS視覺(jué)塊進(jìn)行信息抽取，并將結(jié)果格式化后寫(xiě)入數(shù)據(jù)庫(kù)。

3 實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，實(shí)驗(yàn)以隨機(jī)選取的1000個(gè)Web碎片信息站點(diǎn)作為測(cè)試的數(shù)據(jù)集，分別對(duì)基于統(tǒng)計(jì)理論的抽取算法（Ext-ST）、基于DOM樹(shù)的抽取算法（Ext-DOM）、基于歸納的抽取算法（Ext-I）與基于CSS視覺(jué)分塊的Web碎片信息抽取算法（EXT-CSSV）進(jìn)行對(duì)比測(cè)試。算法均采用C#語(yǔ)言實(shí)現(xiàn)，實(shí)現(xiàn)過(guò)程中通過(guò)微軟的Visual Studio 2008提供的WebBrowser控件調(diào)用IE內(nèi)核，從而生成CSS視覺(jué)分塊。實(shí)驗(yàn)中運(yùn)行的硬件環(huán)境為Intel? Rentium?III Xeon processor（2 CPUS），2.6GHz。160G硬盤(pán)，內(nèi)存為1GB。存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)庫(kù)為Microsoft sql server 2000，操作系統(tǒng)為Microsoft Windows XP。

實(shí)驗(yàn)中主要檢測(cè)查準(zhǔn)率與查全率兩個(gè)指標(biāo)。查準(zhǔn)率為算法抽取到的Web碎片信息中準(zhǔn)確的信息數(shù)與實(shí)際Web碎片信息數(shù)的比值。查全率為算法抽取的Web碎片信息數(shù)與應(yīng)抽取的Web碎片信息數(shù)的比值。實(shí)驗(yàn)結(jié)果如表2所示。

為了進(jìn)一步驗(yàn)證算法的效率，實(shí)驗(yàn)中分別采用隨機(jī)選取500、1000、1500、2000、2500、3000、3500、4000、4500、5000個(gè)頁(yè)面作為輸入頁(yè)面，各算法運(yùn)行的對(duì)比結(jié)果以圖3所示。

從表2可以看出，基于CSS視覺(jué)分塊的Web碎片信息抽取算法的查準(zhǔn)率為97.14%，查全率為96.87%，均比基于統(tǒng)計(jì)理論的抽取算法、基于DOM樹(shù)的抽取算法及基于歸納的抽取算法要好。在時(shí)間效率上，從圖3可以看出，隨著輸入頁(yè)面數(shù)量的增多，基于CSS視覺(jué)分塊的Web碎片信息抽取算法越占優(yōu)勢(shì)。

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

從半結(jié)構(gòu)化的Web頁(yè)面中抽取出相關(guān)的Web碎片信息，可以作為相關(guān)研究工作獲取數(shù)據(jù)的重要前提，可以為研究人員獲取相關(guān)的Web碎片信息，例如對(duì)于Web輿論導(dǎo)向研究具有十分重要的意義?；贑SS視覺(jué)分塊的Web碎片信息抽取算法從CSS視覺(jué)效果出發(fā)，不僅考慮到瀏覽器的因素，更重要的是考慮了網(wǎng)頁(yè)設(shè)計(jì)的對(duì)象是“人”的因素，從用戶所見(jiàn)的視覺(jué)效果的角度對(duì)Web頁(yè)面進(jìn)行分塊，可以快速地尋找出碎片信息所在的塊，方便了信息的抽取，在一定程序上提高了碎片信息抽取的準(zhǔn)確性與效率。目前，基于CSS視覺(jué)分塊的Web碎片信息抽取算法已經(jīng)被用于貴州省優(yōu)秀科技教育人才省長(zhǎng)專項(xiàng)資金項(xiàng)目——基于信息碎片與移動(dòng)網(wǎng)絡(luò)的信息傳播與輿論導(dǎo)向研究中，作為前期獲取信息碎片的主要工具之一，并體現(xiàn)出了較強(qiáng)的實(shí)用價(jià)值。

參考文獻(xiàn)：

[1]王賢.基于樹(shù)結(jié)構(gòu)的DeepWeb數(shù)據(jù)抽取研究[D].昆明，昆明理工大學(xué)，2007.

[2]詹沐清，朱穎.基于Web的信息抽取技術(shù)探討[J].中國(guó)科技信息，2013（4）：69-70.

[3]王賢.基于統(tǒng)計(jì)的網(wǎng)頁(yè)正文信息抽取方法的研究[J].中文信息學(xué)報(bào)，2004，18（5）：17-22.

[4] GUPTA S，KAISER G.DOM-based content extraction of HTML documents[C]//Proc of the 12th World Wide Web Conference. New York： ACM Presses，2003： 207-214.

[5]李文，鄭邦習(xí)，鄧武.基于XML和DOM技術(shù)的Web信息抽取模型[J].大連交通大學(xué)學(xué)報(bào).2013，34（3）：96-99.

[6]劉軍，張凈.基于DOM的網(wǎng)頁(yè)主題信息的抽取[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（5）：188-190.

[7]那赫.基于DOM的Web主題信息提取系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2010（7）：30-31.

[8]石倩，陳榮，魯明羽.提出的基于規(guī)則歸納的信息抽取系統(tǒng)實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（21）：166-170.

[9] Deng Cai， Shipeng Yu， Ji-Rong Wen， and Wei-Ying Ma. VIPS： A Vision-based Page Segmentation Algorithm. Microsoft Technical Report， MSR-TR-2003-79， 2003.

作者簡(jiǎn)介：向程冠，碩士，講師，主研領(lǐng)域：數(shù)據(jù)庫(kù)技術(shù)，數(shù)據(jù)挖掘與信息檢索；熊世桓，碩士，教授，主研領(lǐng)域：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，數(shù)據(jù)庫(kù)與軟件工程。