一種基于視覺特征的Deep Web信息抽取方法

孫　璐　陳軍華　廉德勝

(上海師范大學　上海　200234)

一種基于視覺特征的Deep Web信息抽取方法

孫璐陳軍華廉德勝

(上海師范大學上海200234)

摘要隨著Web數據庫的不斷增長,大量網絡信息通過普通搜索引擎難以滿足用戶的需求,需要用戶提交表單查詢并從后臺數據庫中返回結果頁面才能獲取到想要的信息,稱為Deep Web。因此如何有效地抽取這些實體信息成為一個值得研究的問題。論文通過分析Deep Web結果頁面的特點,結合人的視覺特征,提出了一種基于視覺特征的Deep Web信息抽取方法。該方法充分利用了人的視覺特征,在解析器將Web文檔解析成語法樹之前,將Web頁面一些與主題無關的信息(例如導航欄、廣告)等去除,并對優化后的DOM樹利用VIPS算法對其進行語義分塊,分塊后根據位置特征首先尋找到基準視覺塊,以該基準視覺塊作為中心位置逆序和順序遍歷DOM樹尋找所有相似的視覺塊并對其進行抽取。從實驗效果來看,該方法從提取信息速度和提取信息的準確率和完整率方面與傳統方法相比都有一定的提高。

關鍵詞Deep Web; 視覺特征; DOM樹; 語義分塊; 信息抽取

Class NumberJ653

1引言

信息抽取可以理解為從一段待處理文本中抽取指定的一類信息,并將其以結構化的形式表示(如XML等)供用戶查詢和使用的過程。針對Web信息抽取工作目前國內外已展開了大量的研究,并且取得了一定的成果。其中按照抽取技術的不同可以分為基于自然語言處理方式的實體抽取;基于包裝器歸納法的信息抽取;基于模板的信息抽取;基于視覺特征的信息抽取和基于DOM樹的實體抽取技術。其中基于視覺特征的信息抽取和基于DOM樹的信息抽取是目前應用比較廣泛的方法。

由于構成網頁的HTML語言在很大程度上是用來顯示數據而不是展示其內容結構的,所以從用戶的視覺角度對Web頁面進行分析有其一定的合理性。文獻[10]提出了基于視覺特征的VIPS算法,該算法充分利用了Web頁面的視覺特征,例如顏色、字體大小、圖片等,把Web頁面劃分為許多視覺塊,根據視覺塊之間的相似度重構頁面的內容結構,從而對信息進行抽取。但是該方法基于許多啟發式的規則,有時會受人的視覺誤導,把頁面一些無用的信息當作視覺塊處理,例如廣告信息等。文獻[6～8]提出了基于DOM樹的實體抽取技術。在該方法中,首先利用解析器將Web文檔解析成語法樹,然后深度遍歷整棵DOM樹,利用DOM樹節點之間的相似度確定正文區域,從而對文本信息進行有效抽取。但是該方法是把文本節點和標簽節點放在一起對整個DOM文檔進行遍歷分析,加大了遍歷DOM樹的時間復雜度。本文通過觀察大量Deep Web結果頁面,首先運用啟發式規則對原始頁面進行去噪處理,使得去噪后解析DOM樹的節點數大大減少,然后在DOM樹結構基礎之上,運用文獻[10]提到的VIPS算法,把Web頁面分割成許多大小不等的視覺語義塊,利用頁面中心位置的坐標確定出基準視覺塊,然后根據Web頁面正文信息的位置分布特征和正文視覺塊之間的視覺相似性,以該視覺塊作為中心位置,順序和逆序遞歸遍歷整棵DOM樹,尋找出所有相似視覺塊,即要提取的正文信息。實驗表明該方法與傳統的方法相比有一定的優勢。

2基于基準視覺塊的信息抽取算法

2.1Web頁面去噪

一般的網頁可以分為導航型網頁和內容型網頁兩種,由于本文主要是針對特定領域的關鍵詞搜索結果研究,所以不對導航型網頁做研究。對于一個已抽取到的Deep Web結果頁面,需要提取的數據區域往往集中于頁面的某個區域,稱之為正文區域。而普通的Deep Web頁面往往包含標題、廣告欄、導航鏈接等許多噪聲信息,一些針對特定領域的數據查詢(如圖書查詢),因為它們有規律地分布在頁面的特定部分,使得這些無用的噪聲信息占了整個頁面的一定比重,這樣不利于頁面的信息抽取,所以對初始頁面做去噪處理是非常有必要的。本文通過觀察大量的網頁后臺HTML代碼并結合文獻[9]提到的網頁信息去噪技術,得出如下一些啟發式規則:

規則一:如果一個節點周圍含有大量的鏈接節點,如〈link〉等,即鏈接節點數超過了該區域總數的一定比例,在這里取95%,那么傾向于把這片信息塊看作噪聲信息,反之則為正文信息;

規則二:如果一個節點的position屬性為fixed,并且該節點下還包括img、object或iframe節點,那么把該節點作為噪聲節點;

規則三:如果一個文本節點的文本字數低于版權信息節點所含文本的字數(這里把版權信息的字數作為一個閾值)那么傾向于把它看作噪聲節點或無用節點。基于以上一些規則,可以初步對原始Web頁面做一些優化處理。

本文采用HTMLPaster的詞法分析器對頁面的HTML代碼進行分析,通過提交關鍵字查詢獲取Deep Web頁面作為實驗數據的來源。解析到原始頁面的HTML代碼后,利用上一節提到的啟發式規則對頁面的噪聲進行過濾處理。可以看出,經過處理后DOM樹的節點數大大減少了。

圖1　頁面結構和去噪節點對比圖

2.2VIPS算法

VIPS算法主要是利用Web頁面的視覺特征如背景顏色,字體的顏色和大小等把頁面分成許多合適的視覺塊,根據視覺塊之間的邏輯間距重構語義DOM樹,進而對頁面信息抽取的過程。下面對該算法做一個簡單介紹。在VIPS算法中,一個Web頁面由Ω表示,Ω=(O,Φ,δ)。其中O={Ω1,Ω2,…,ΩN}是一系列有限的頁面塊的集合,Φ={Φ1,Φ2,…,ΦT}是一系列有限的分隔符的集合,δ=O×O→Φ∪{NULL},它表示O中每兩個塊之間的關系[10]。例如,假設Ωi和Ωj是O中的兩個對象,δ(Ωi,Ωj)≠NULL表明Ωi和Ωj之間是有聯系的,即它們有可能是DOM樹中的兩個相鄰的節點。另外,在Ω中,每一個頁面塊都可以看作一個子頁面,所以可以遞歸地對它作同樣的處理,直到當前頁面塊不能再分割為止。

下面以當當網為例具體闡述整個分割過程。在當當網首頁輸入“計算機”,點查詢,可以得到如圖2結果頁面。

圖2　當當網頁面

圖3　當當網視覺分塊圖

根據VIPS算法,把該頁面分割成如圖3所示的視覺塊,其中VB1中主要是查詢信息和導航信息,還夾雜了一些廣告信息,VB3和VB4是底下一些服務指南和版權信息,VB2是想要提取的正文信息。可以看到要提取的信息,即VB2主要集中在頁面的某一特定部位,以VB2為例簡單說明VIPS分塊過程。VB2的DOM樹結構如圖4所示。

圖4　VB2的DOM樹結構

首先得到〈table〉標簽,它有孩子節點〈tr〉,且孩子節點的背景顏色和它父親節點的背景顏色不同,所以分隔這個節點,這樣就得到兩個節點塊,然后分別對這兩個節點塊進一步分析。它有四個〈td〉節點,其中兩個是無效節點,取出剩下的兩個有效節點即VB2_1和VB2_2所在視覺塊。分別對兩個視覺塊深度遍歷,得到〈table〉子節點,它有可能是想要的文本信息,所以把它放到分塊池中等待進一步被分析。等到所有的節點都被分析完放入池中后,再遞歸地對分塊池中的節點塊作同樣的分析,直到得到合適的視覺信息塊。至此,整個DOM樹的分塊過程完畢。

2.3頁面信息提取算法

VIPS算法是對頁面所有信息進行分塊,而信息提取只需要提取與主題有關的正文信息,本文討論的是針對特定領域的Deep Web結果頁面信息,這些信息大都集中在Web頁面的特定位置(一般在正中間)。并且這些信息塊具有相似的層次結構,大小和顏色,所以可以根據頁面視覺特征和DOM樹的層次結構找出一個基準視覺塊,并逆序和順序遍歷整棵DOM樹,找出頁面所有相似視覺塊,若存在形似的視覺塊,再遞歸地對相似視覺塊做以上同樣的操作。直到找到所有想要抽取的信息。抽取流程圖如圖5所示。

圖5　信息抽取流程圖

下面具體說明正文信息提取算法。以圖6為例定義網頁左上角頂點為坐標原點,網頁中心坐標為(Center_X,Center_Y),定義每個視覺塊的中心坐標為(Block_Xi,Block_Yi),其中i={1,2,3,…,n},n∈Z。頁面信息提取過程可以描述如下:

步驟二:提取相似視覺塊。通過觀察可以發現,處于正文位置的視覺塊具有相似的視覺特征,并且它們在DOM樹中有相似的樹層次結構和相同的父節點信息,所以可以以該基準視覺塊即VB2_2_3所在樹層次作為中心位置,遍歷該視覺塊所在層次的所有的兄弟節點,得到VB2_2_1和VB2_2_2并把它們和VB2_2_3作比較,它們具有相似的視覺大小和顏色,并處在相同層次的結構樹中,所以把這三個視覺塊其作為要提取的正文信息存儲在目標池中。

步驟三:提取其他可能視覺塊。盡管在Web頁面中DOM結構樹為基本的對象提供了一種層次結構,但是DOM結構樹主要是用來顯示而不是組織內容的,所以具有相似語義的視覺塊可能存在不同的DOM樹中,因此需要對DOM樹進行進一步遍歷以便找到所有可能的視覺塊。這里采用文獻[11]提到的逆序遍歷方法。首先逆序遍歷DOM樹節點,找出目標池中所有視覺塊VB2_2_1、VB2_2_2和VB2_2_3對應DOM樹層次結構所在節點的公共父節點,即VB2_2,再逆序向上找出該公共父節點的根節點VB2,對此節點進行順序遍歷,得到VB2_1和VB2_3兩個子節點,它們為VB2_2所在DOM樹結構的所有兄弟節點。如果還有相似的正文目標視覺塊存在,那么他們應該存在于VB2_1和VB2_3的子節點中,否則,說明不存在其他DOM樹中包含相似的目標視覺塊。在這里遍歷到VB2_1_1、VB2_1_2、VB2_3_1和VB2_3_2四個孩子節點,把他們分別和基準視覺塊VB2_2_3作比較,從圖6中可以發現,這四個節點的大小和VB2_2_3相差較大,所以舍棄這些節點。

步驟四:根據步驟三的結果,如果提取到相似的視覺塊信息,那么以提取到的視覺塊作為新的基準視覺塊遞歸作同樣的操作,直到找到所有可能的視覺塊。至此,正文信息視覺塊提取結束。

圖6　頁面視覺分塊圖

圖7　頁面視覺塊對應的DOM結構圖

3實驗

本文實驗分別實現傳統的基于DOM樹的網頁信息抽取方法和本文提出的基于基準視覺塊的逆序提取網頁正文信息的抽取方法,并把這兩種方法做比較,以體現本文提出的方法的優勢。傳統的基于DOM樹的網頁信息抽取方法主要是用一些開源工具如NekoHTML、Jtidy等把Web頁面解析成一棵DOM樹,然后深度遍歷DOM樹節點提取出頁面正文信息。該方法實現簡單,并具有一定代表性。本文通過對當當網、淘寶網等一些特定領域網站提交關鍵詞查詢獲得大量的結果頁面,把這些結果頁面作為實驗數據的來源。實驗環境采用的是:主機ASUS,處理器Intel(R) Celeron(R) CPU 1.50GHz,內存4GB,硬盤250GB,操作系統為Window 7。

圖8　兩種算法使用的節點數比較

圖8顯示的是使用兩種不同的算法提取正文信息需要解析的DOM樹節點數,從圖中可以看出,不管是提取哪一類的網頁,經過去噪處理的基于基準視覺塊的逆序提取方法都只需解析幾乎只包含正文信息的DOM節點。

另外,為了進一步驗證該算法的性能和可行性,本文進行了信息抽取的準確率實驗。分別對每類網站抽取10個頁面,人工提取出關鍵正文信息,并估算總共包含的正文信息個數,與本文提出的抽取出正文信息塊方法抽取出的正文信息以及正文信息數量進行人工比對,結果如表1所示。

表1　Web頁面信息抽取性能

其中完整率=(抽取到正文信息個數/總共包含的正文信息個數)×100%;準確率=(準確抽取到正文信息個數/抽取到正文信息個數)×100%。從實驗結果可以看出,本文提出的基于基準視覺塊的Web頁面抽取方法可以較準確并完整地抽取到所需要的正文信息,證明了該方法的可行性。由于一些網站,例如搜狐,并不屬于純粹的針對特定領域的網頁,所以該類網頁中包含的干擾視覺信息塊較多,并且正文信息與基準信息不具有相似的視覺特征和位置特征,所以有部分正文信息塊會被遺漏,導致抽取的完整率和準確率會有所下降。

4結語

本文在基于DOM樹結構的Web頁面基礎之上,利用人的視覺特征,首先根據一些啟發式規則對原始頁面去噪優化,然后利用VIPS算法把Web頁面分成不同的視覺塊,根據正文信息在頁面的分布特征提取出基準視覺塊,并根據基準視覺塊的視覺特征逆序和順序遍歷整棵DOM樹,遞歸提取出所有相似的視覺塊。從實驗結果來看,本文提出的方法在提取速度方面與傳統方法相比有了一定的提高,并且有較高的準確率和完整率。但是本文的方法還有許多有待改進的地方。比如該方法比較適用于主題單一的網站,即整個網頁只含單個文本區域的網站。如果頁面結構較復雜,文本塊較多,那么使用該方法有可能丟失一些有用的信息。另外,基準視覺塊的大小也是一個關鍵,視覺塊過大或過小都會影響實驗的準確性和提取效率,下一步將對這方面做進一步研究,以達到更好的抽取效果。

參 考 文 獻

[1] 吳茜,劉嘉勇.基于VIPS算法和模糊字典匹配的網頁提取技術研究[J].技術研究,2014(10):49-53.

WU Qian, LIU Jiayong. Web Page extraction technology research Based on VIPS algorithm and fuzzy dictionary matching[J]. Netifo Security Technology Research,2014(1):49-53.

[2] 安增文,徐杰鋒.基于視覺特征的網頁正文提取方法研究[J].微型機與應用,2010(3):38-41.

AN Zengwen, XU Jiefeng. Web Page text extraction technology research Based on Visual feature[J]. Micro Computer and Application,2010(3):38-41.

[3] 郭迎春,劉一偉,陳召旭.Deep Web數據抽取的分析與研究[J].南開大學學報(自然科學版),2012,45(3):9-14.

GUO Yingchun, LIU Yiwei, CHEN Zhaoxu. Analysis and Research on Deep Web Data Extraction[J]. Journal of Nankai University(Natural Science Edition),2012,45(3):9-14.

[4] Wachirawut Thamviset, Sartra Wongthanavasu. Information extraction for deep web using repetitive subject pattern, World Wide Web 2014 DOI 10.1007/s11280-013-0248-y.

[5] 顧韻華,高原,等.基于模板和領域本體的Deep Web信息抽取研究[J].計算機工程與設計,2014,35(1):327-332.

GU Yunhua, GAO Yuan, et al. Deep Web information extraction research Based on template and domain ontology[J]. Computer Engineering and Design,2014,35(1):327-332.

[6] 田建偉,李石君.基于層次樹模型的Deep Web數據提取方法.計算機研究與發展 ISSN 1000-1239/CN 11-1777/TP,2011,48(1):94-102.

TIAN Jianwei, LI Shijun. Deep Web data extraction method based on hierarchical tree model[J]. Computer Research and Development ISSN 1000-1239/CN 11-1177/TP,2011,48(1):94-102.

[7] 李朝,彭宏,葉蘇南,等.基于DOM樹的可適應性Web信息抽取[J].計算機科學,2009,36(7):202-210.

LI Chao PENG Hong, YE Sunan, et al. Adaptive Web information extraction based on DOM Tree[J]. Computer Science,2009,36(7):202-210.

[8] 寇月,李冬.D-EEM:一種基于DOM樹的Deep Web實體抽取機制[J].計算機研究與發展,2010,47(5):858-865.

KOU Yue, LI Dong. A Deep Web entity extraction mechanism based on DOM Tree[J]. Computer Research and Development,2010,47(5):858-865.

[9] 付濤.基于DOM和顯示屬性的網頁信息除噪技術研究[J].商丘師范學院學報,2010,26(9):90-93.

FU Tao. Web Information noise cancellation technology research Based on DOM and Display attributes[J]. Journal of Shangqiu Normal College,2010,26(9):90-93.

[10] Deng Cai, Shipeng Yu. Extracting Content_Structure for Web Pages based on Visual Representation Microsoft Research Asia.

[11] 張瑞雪,宋明秋.逆序解析DOM樹及網頁正文信息提取[J].計算機科學,2011,38(4):213-215.

ZHANG Ruixue, SONG Mingqiu. Reverse parsing the DOM tree and informaiton extraction on the web page[J]. Computer Science,2011,38(4):213-215.

Deep Web Information Extraction Method Based on Visual Features

SUN LuCHEN JunhuaLIAN Desheng

(Shanghai Normal University, Shanghai200234)

AbstractWith the constantly development of Web database, a large number of information can not be got by ordinary search engine. The results which users want to get need them submit the form query so that the information can be got from the database behind called Deep Web. Thus how to effectively extract these information become a problem which worth of study. This paper propose an improved method by analyzing the characteristics of the results pages combining with human visual sense. This method makes full use of human visual characteristics, before the parser parsed the Web document into a syntax tree, and removed some information which has nothing to do with the theme such as navigation, advertising, etc. After that, division the DOM tree into semantic block using VIPS algorithm. Sw we can find the standard block according to the block’s position, then put the standard block as center block which used to find all similar visual blocks by reversing and suquential traversal the DOM tree. These result blocks are the information blocks which we want to extraction. According to the experimental results, this method has some improvement from the aspects of accuracy rate and complete rate to some extent compared with traditional method.

Key WordsDeep Web, visual characteristics, DOM tree, semantic block, information extraction

收稿日期:2015年12月5日,修回日期:2016年1月23日

作者簡介:孫璐,女,碩士研究生,研究方向:數據庫。陳軍華,男,碩士,副教授,研究方向:數據庫。廉德勝,男,碩士研究生,研究方向:人工智能。

中圖分類號J653

DOI:10.3969/j.issn.1672-9722.2016.06.026