Web數(shù)據(jù)抽取技術(shù)研究初探
2009-04-29 00:00:00李春艷,徐保民
電腦知識與技術(shù) 2009年35期
摘要:該文給出了數(shù)據(jù)抽取過程中需要的基本定義，描述了數(shù)據(jù)抽取所基于的頁面生成模型。同時(shí)給出了EXALG+這種數(shù)據(jù)抽取方法的基本流程，并給出了這種方法的抽取流程圖。
關(guān)鍵詞:數(shù)據(jù)抽取;EXALG+數(shù)據(jù)抽取方法;抽取流程圖
中圖分類號:TP311 文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)35-9920-03
Preliminary Study on Web Data Extraction Technology
LI Chun-yan， XU Bao-min
(Beijing Jiaotong University， Beijing 100000， China)
Abstract: In this paper， a basic definition of the data extraction process has been given and Described a page generation modelof the data extraction. It has also given the basic processandExtraction Flow of EXALG + data extraction method.
Key words: data extraction; eXALG +data extraction method; extraction flow
隨著互聯(lián)網(wǎng)的出現(xiàn)，Web文檔的信息抽取逐漸成為亟待解決的問題。一個(gè)Web文檔就是一個(gè)網(wǎng)頁，網(wǎng)頁與純文本的結(jié)構(gòu)差別很大，主要表現(xiàn)為網(wǎng)頁中存在大量的標(biāo)記，這些標(biāo)記將網(wǎng)頁要顯示的文本內(nèi)容分隔開來。大量的標(biāo)記為網(wǎng)頁信息抽取提供了更多可利用的信息，從而可以開發(fā)各種不同于傳統(tǒng)信息抽取的方法對網(wǎng)頁進(jìn)行信息抽取。
常見的動態(tài)網(wǎng)頁是由相應(yīng)數(shù)據(jù)庫中結(jié)構(gòu)化的數(shù)據(jù)值嵌入模版生成的。EXALG系統(tǒng)也是將動態(tài)網(wǎng)頁中的模版推導(dǎo)出來，然后利用推導(dǎo)得到的模版來進(jìn)行同類Web文檔上數(shù)據(jù)抽取工作。該系統(tǒng)初看起來是一個(gè)很成功的模版推導(dǎo)系統(tǒng)，但經(jīng)驗(yàn)證發(fā)現(xiàn)該系統(tǒng)還存在著一定的不足。本文正是在EXALG的基礎(chǔ)上，提出了改進(jìn)的抽取算法，即EXALG+算法。
1 數(shù)據(jù)類型定義
一個(gè)頁面的模板和內(nèi)容是由數(shù)據(jù)類型(Data Types)和數(shù)據(jù)值，也即數(shù)據(jù)實(shí)例(Instance)所構(gòu)建而成的。數(shù)據(jù)格式是多種屬性通過一種固定的序列進(jìn)行排列而成。其中每種屬性都可能是諸如字串，可選項(xiàng)或分離項(xiàng)等其它數(shù)據(jù)形式，由此，可以對數(shù)據(jù)類型作出遞歸定義。其中，分離項(xiàng)和可選項(xiàng)是數(shù)據(jù)抽取技術(shù)中通用的定義。
1.1 基本定義
定義1.1:基本數(shù)據(jù)類型由符號β表示。它描述了一個(gè)標(biāo)記串，是一個(gè)頁面文本的基本單元。在本文中，標(biāo)記定義為一個(gè)單詞(Word)或一個(gè)HTML的固有標(biāo)簽。
該數(shù)據(jù)類型的實(shí)例為各種標(biāo)記(Token)所組成的字串，有dom(β)={s|s從屬于string}。特別地，定義一個(gè)特殊的字串，記做Φ，表示為空字串的數(shù)據(jù)類型，也可以稱之為NULL數(shù)據(jù)類型。
定義1.2:若T1，T2，…，Tn是數(shù)據(jù)類型，則序列集合
類型< T1，T2，…，Tn>的一個(gè)實(shí)例為形如
定義1.3:如果T為數(shù)據(jù)類型，則集合{T}也是一個(gè)類型。稱集合{T}是由類型T通過集合構(gòu)造器構(gòu)造而成的類型，有dom({T})={e1，e2，…，ei | e從屬于dom(T)}。
類型{T}的實(shí)例為元素{e1，e2，…，em}的集合，其中，ei(1≤i≤m)均為類型T的一個(gè)實(shí)例。
由此，本文中將類型的實(shí)例稱作“值”，將符號“<>”和“{}”稱作類型構(gòu)造器符號，將元組構(gòu)造器和集合構(gòu)造器統(tǒng)稱為類型構(gòu)造器，并通過記號“<>”和“{}”來區(qū)分。
1.2 分離項(xiàng)和可選項(xiàng)
一般來說，一個(gè)模板的建立主要由兩種構(gòu)造器以及構(gòu)造器所使用的基本類型組成。這兩種構(gòu)造器一般分別為元組構(gòu)造器和集合構(gòu)造器。另外，在網(wǎng)頁頁面中同時(shí)還普遍存在著兩種其它形式的類型構(gòu)造器，分別為可選項(xiàng)和分離項(xiàng)兩種類型構(gòu)造器。
例如，在瀏覽Chinapub網(wǎng)站的時(shí)候看到的圖書信息，這些書中有的是國內(nèi)作者編著的書籍，有的是翻譯過來的書籍。后一種書籍中會有“譯者”這個(gè)選項(xiàng)，則其中“譯者”就可以看作是可選項(xiàng);而相應(yīng)的國內(nèi)作者所著的書籍中，有時(shí)候也會有中文版和外文版。如果在這本書籍的介紹頁面當(dāng)中僅可能出現(xiàn)一種版式，就是分離項(xiàng)的形式。
定義1.4:如果T為數(shù)據(jù)類型，則可選項(xiàng)(T)?也是一種數(shù)據(jù)類型，稱為可選項(xiàng)類型。有dom((T)?)=dom(T)∪{?椎}={ei|ei∈dom(T)∪?椎}。并稱數(shù)據(jù)類型(T)?是由類型T通過可選項(xiàng)構(gòu)造器構(gòu)造而成。
定義1.5:如果T1，T2都是數(shù)據(jù)類型，則(T1|T2)也是一種數(shù)據(jù)類型，有dom((T1|T2))=dom(T1)∪dom(T2)={axi|ali∈dom(T1)，or a2i∈dom(T2)}，稱為分離項(xiàng)類型。其中(T1|T2)是由類型T1，T2通過分離項(xiàng)構(gòu)造器構(gòu)造而成。
每一種數(shù)據(jù)類型都可以用數(shù)據(jù)類型樹來抽象表示，而且該樹具有一定的層次結(jié)構(gòu)，稱這種用來表示數(shù)據(jù)類型的樹為抽象模式樹(Abstract Schema Tree，AST)。
1.2 頁面生成模型
本節(jié)給出由動態(tài)頁面產(chǎn)生模板的頁面生成模型。如圖1所示，一個(gè)值X，通過使用一個(gè)模板T而被編碼到一個(gè)實(shí)際頁面中。用λ(T，X)表示編碼頁面結(jié)果。
定義1.6:一個(gè)模式S的模板，即將S中的每一個(gè)的類型構(gòu)造器τ映射到一個(gè)有序的標(biāo)記串集合T(τ)中，同時(shí)有如下特性。
1) 若τ是一個(gè)n維元組構(gòu)造器，則T(τ)是一個(gè)標(biāo)記串的序列，形如
2) 若τ是一個(gè)集合構(gòu)造器，則T(τ)是一個(gè)標(biāo)記串。
為區(qū)分不同的模板，把模板T記做TS，用于表示該模板是為模式S作作的定義。也就是說，在編碼函數(shù)λ(T，X)給定的時(shí)候，將模式S的實(shí)例X嵌入到模板T上，而此時(shí)，可以使用編碼函數(shù)，對該實(shí)例X可以按下列方式嵌入。
第一，如果X是基本類型β，則λ(T，X)就作為x自身輸出到頁面上。
第二，如果X為n維元組的形式，形如
第三，如果X是形如{e1，e2，…，em}τs的一個(gè)集合，則λ(T，X)為一個(gè)有序標(biāo)記串輸出到頁面上，形如λ(T，e1)Sλ(T，e2)S…λ(T，em)。其中T(τs)=S。
第四，如果X是形如(X)?的可選項(xiàng)，λ(T，X)輸出的實(shí)例為X或空字串Φ。
第五，如果X為形如X=(X1|X2)的分離項(xiàng)，則函數(shù)λ(T，X)為λ(T，X1)和λ(T，X2)二者其中的一個(gè)輸出到頁面上。
1.3 數(shù)據(jù)抽取
本文中的數(shù)據(jù)抽取是針對Web文檔進(jìn)行的，是一種根據(jù)網(wǎng)頁的相似性結(jié)構(gòu)自動找到網(wǎng)頁中的數(shù)據(jù)并歸納出抽取規(guī)則的完全自動化的抽取方法。網(wǎng)頁中的許多標(biāo)記和文字的出現(xiàn)常常是頻繁的，所以可以根據(jù)這些標(biāo)記形成等價(jià)類，推導(dǎo)出生成網(wǎng)頁的結(jié)構(gòu)模板，并利用這個(gè)模板抽取需要的數(shù)據(jù)。
1.3.1 數(shù)據(jù)抽取定義
定義1.7:給定一個(gè)具有n個(gè)頁面的集合P，其中Pi=λ(T，xi)(1 一般來說，從一個(gè)大的互聯(lián)網(wǎng)站點(diǎn)給定的一個(gè)實(shí)際頁面集合，在頁面編碼中，人工選擇正確的模板和數(shù)據(jù)值時(shí)一般不會有任何疑問。而要達(dá)到的目標(biāo)恰恰是解決實(shí)際網(wǎng)頁的抽取問題，也即能夠生成被“人”認(rèn)為是正確的模板和數(shù)據(jù)值。 如上所述，為了將頁面模板推導(dǎo)出來，可以將頁面中的所有標(biāo)記加以識別區(qū)分，判斷標(biāo)記是模板標(biāo)記值還是數(shù)據(jù)值。將所有屬于模板的標(biāo)記區(qū)分出來后，再利用這些標(biāo)記完成模板的建立和其后的數(shù)據(jù)抽取。因此，為了將數(shù)據(jù)標(biāo)記和模板標(biāo)記區(qū)分開來，可以利用頁面中的標(biāo)記的不變/變動特性來達(dá)到區(qū)分的效果。同一類網(wǎng)頁所使用的模板是固定不變的，而變化部分則是嵌入到這些模板標(biāo)記中的數(shù)據(jù)值，因此，通過分析網(wǎng)頁中的標(biāo)記是否具有變動性質(zhì)就可以完成區(qū)分工作。但是，實(shí)際工作依然很困難。 第一，模板標(biāo)記中的標(biāo)記值和數(shù)據(jù)集合中的標(biāo)記值可能相同，也就是會出現(xiàn)同樣的標(biāo)記扮演不同角色的情況。 第二，在頁面中出現(xiàn)的可選項(xiàng)和分離項(xiàng)使得不變/變動的性質(zhì)難以區(qū)分，從而使得模板推導(dǎo)更加復(fù)雜。 分離項(xiàng)可能具有多種表示方式，比如，“姓名”或“地址”就可能會出現(xiàn)由于語言習(xí)慣或地域的不同而使用不同的表示方式。同樣的，日期的表示格式等也屬于此類問題，而且表示方法更多:可以表示成“日期/月份/年份”或是“月份/日期/年份”等。 因此，在實(shí)際的模板推導(dǎo)中由于這些問題將會導(dǎo)致最終的推導(dǎo)結(jié)果出現(xiàn)很多不同可能的模板。此時(shí)與這些模板相對應(yīng)的抽取出來的數(shù)據(jù)也就不盡相同。也就是所謂的存在沖突模式(Ambiguity Schema)。目前，已經(jīng)證明了想要推導(dǎo)出一個(gè)無沖突的模式屬于一個(gè)NP完全問題。因此，抽取問題的關(guān)鍵，在于如何找到一個(gè)更好的或者說最佳的模板用于數(shù)據(jù)抽取。 1.3.2 數(shù)據(jù)抽取原理 EXALG是由Arvind與Hector二人于SIGMOD2003提出的數(shù)據(jù)抽取系統(tǒng)。該方法使用了類似RoadRunner的模型，希望將生成Web文檔的模板推導(dǎo)出來，然后再根據(jù)得到的模板，來抽取采用同樣結(jié)構(gòu)的Web文檔中的相關(guān)數(shù)據(jù)值。 這兩種方法的歸納方式不同。EXALG不是逐個(gè)比較兩個(gè)網(wǎng)頁中的標(biāo)記，而是提出了出現(xiàn)向量(Occurrence Vector)和等價(jià)類(Equivalence Class)的概念。通過統(tǒng)計(jì)最大最頻繁的等價(jià)類和角色區(qū)分來推導(dǎo)模板。EXALG對于給出頁面集合，可以發(fā)現(xiàn)頁面中所隱含的模板，并通過模板將數(shù)據(jù)抽取出來。 根據(jù)Arvind二人提供的數(shù)據(jù)和他們發(fā)布的EXALG系統(tǒng)的實(shí)際使用情況，可以發(fā)現(xiàn)EXALG對于原來已有的其它方法來說有了很大的進(jìn)步;而本文給出的抽取方法，對于抽取的數(shù)據(jù)在正確性和完整性方面做得更加完善。 本文的抽取方法，是受EXALG的啟發(fā)得到，所以稱之為EXALG+方法。它可分為兩個(gè)階段。在第一個(gè)階段用于發(fā)現(xiàn)與生成輸入頁面的未知模板中相同的類型構(gòu)造器相聯(lián)系的標(biāo)記的集合。在第二個(gè)階段則使用上面生成的集合推導(dǎo)出模板。然后，推導(dǎo)得到的模板被用來抽取頁面的編碼值。以上兩個(gè)階段的工作完全由機(jī)器完成，是無需人工參與的過程。 第一個(gè)階段，利用出現(xiàn)頻繁程度作為向量，用來表示一個(gè)標(biāo)記串在所有網(wǎng)頁中的出現(xiàn)頻率，并且利用原作者提出的等價(jià)類概念，即具有相同出現(xiàn)向量的標(biāo)記串，聚集到同一個(gè)有序的標(biāo)記串集合中。由于等價(jià)類中的所有標(biāo)記串在相同模板的作用下，會產(chǎn)生同樣的出現(xiàn)頻率，因此，利用這種特點(diǎn)將所有合法的等價(jià)類尋找出來，然后將這些等價(jià)類中的標(biāo)記串轉(zhuǎn)換成最后的模板。 可以將HTML文檔看作一棵DOM樹。首先，將頁面中所有相同的字串根據(jù)其DOM樹路徑位置的不同來區(qū)分其扮演的角色，將其稱為特定標(biāo)記串。然后，將所有扮演相同角色的特定標(biāo)記串按其出現(xiàn)次數(shù)組成出現(xiàn)向量，然后將所有具有相同出現(xiàn)向量的特定標(biāo)記串聚合在一起，形成一個(gè)等價(jià)類。在這一步驟中，可能會出現(xiàn)一些不合法的等價(jià)類，利用第三步將這些不合法的等價(jià)類去除。這些不合格等價(jià)類在被過濾掉的同時(shí)釋放該類所包含的所有特定標(biāo)記串，并將特定標(biāo)記串中一些與頁面意義不一致的個(gè)體過濾掉。這一步利用了當(dāng)特定標(biāo)記串出現(xiàn)在不同等價(jià)類的區(qū)間位置不同而具有不同的意義這一特性，可以把這些具有相同值的特定標(biāo)記串進(jìn)一步地區(qū)分開來，并反復(fù)形成新的等價(jià)類，過濾掉不合法的等價(jià)類，得到一個(gè)最頻繁出現(xiàn)的等價(jià)類集合。到此為第一個(gè)階段階段，稱為等價(jià)類生成階段。本文的主要改進(jìn)工作都是在這個(gè)階段完成的。對應(yīng)于這部分的模塊稱之為等價(jià)類生成模塊(Equivalence Class Generation Module:ECGM)。隨后，將這些等價(jià)類作為輸出傳送到第二個(gè)階段的模板分析模塊(Template Analysis Module)，由這個(gè)模塊產(chǎn)生最后的輸出。其流程如圖2所示。 第二個(gè)階段，即模板建立和值抽取模塊。該模塊的輸入是一個(gè)由第一個(gè)階段生成的頻繁等價(jià)類集合和一個(gè)使用標(biāo)記串描述的頁面集合，其輸出是一個(gè)模板和一個(gè)對應(yīng)頁面值的集合。該模塊由兩個(gè)子模塊組成，模板生成子模塊和值抽取子模塊。對于數(shù)據(jù)抽取技術(shù)，一旦獲得了正確的模板之后，值抽取是一個(gè)非常直觀的過程，在此不作贅述。 這些頻繁等價(jià)類集合中，存在一個(gè)最重要的等價(jià)類，<1，1，…，1>，將其稱為基本等價(jià)類。該等價(jià)類的特殊性在于，該集合中所有的標(biāo)記串出現(xiàn)各個(gè)頁面僅一次，比如常見HTML文檔中的等標(biāo)記串組合均屬此列。另外，一般來說等標(biāo)記串通常是一個(gè)頁面的開始標(biāo)記串和結(jié)束標(biāo)記串，因此，該基本等價(jià)類的頁面的范圍往往是最廣泛的，模板構(gòu)建模塊即由此等價(jià)類開始構(gòu)建模板。然后利用先深搜索方式，對于每個(gè)等價(jià)類的非空區(qū)間位置，判斷是否為數(shù)據(jù)嵌入位置，或者該區(qū)間是否嵌入了另外一個(gè)等價(jià)類。如果該位置為數(shù)據(jù)嵌入位置，則跳轉(zhuǎn)到該等價(jià)類的下一個(gè)非空的區(qū)間位置;如果該位置為一個(gè)等價(jià)類的嵌入位置，則進(jìn)入嵌入等價(jià)類的非空區(qū)間再次進(jìn)行判斷，直到將所有的等價(jià)類的非空區(qū)間遍歷完全，即可構(gòu)造出一個(gè)完整的頁面模板。 1.4 小結(jié) 文章給出了數(shù)據(jù)抽取過程中需要的基本定義，描述了數(shù)據(jù)抽取所基于的頁面生成模型。同時(shí)給出了EXALG+這種數(shù)據(jù)抽取方法的基本流程，并給出了這種方法的抽取流程圖。 參考文獻(xiàn): [1] Xi W P，Li X，Jiang K，et al.Information Extraction Technology for Web Forums[J].Computer Engineering，2005，31(4):34-37. [2] Chinchor N，Marsh E.MUC-7 Information Extraction Task Definition(version 5.1)[C].Proceedings of the Seventh Message Understanding Conference，1998:210-221. [3] 宋靜靜，李振坤.基于Wrapper技術(shù)的Web數(shù)據(jù)處理系統(tǒng)研究[J].計(jì)算機(jī)應(yīng)用研究，2004(12):298-300. [4] 李效動，股毓清.基于DOM的Web信息提取[J].計(jì)算機(jī)學(xué)報(bào)，2002，25(5):526-533. [5] 張紹華，徐林昊，楊文柱.基于樣本實(shí)例的Web信息抽取[J].河北大學(xué)學(xué)報(bào):自然科學(xué)版，2001(4):431-437.
