基金項(xiàng)目自然科學(xué)2005ABA

計(jì)算機(jī)研究與發(fā) JournalofComputerResearchand 43(9):1644～1650,1 1(大學(xué)計(jì)算機(jī)學(xué)院2(中國(guó)計(jì)算機(jī)科學(xué)3(華技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院430072) WebInformationExtractionBasedonHTMLPatternLiShijun1,2,YuJunqing3,andOu1(SchoolofComputerScience,WuhanUniversity,Wuhan2(LaboratoryofComputerScience,ChineseAcademyofSciences,Beijing3(SchoolofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,WuhanGeneratingwrapperefficientlyforextractingWebdatahasbroadapplicationprospect,butisalsoadifficultproblemthatisnotyetsolvedefficientlytillnow1Totacklethisproblem,apatternalgebrafor sisintroduced,whichincludeskeyconcepts,suchasconsistentpatternset,andtheaddi2tionoperationofpattern,andbasedonitanewapproachtoextractWebinformationispresented1Itin2ducestheconsistentpatternsetwhichrepresentsidentifyingrulesofeachattributebyexploringthewholesamples,andthenextractsdatabytheconsistentpatternsetwithmultiplepatterns1ItcanapplyWebpageswithtabularstructure,inwhichtherearemissingattributesorattributeswithmultiplevaluesordif2ferentorderandhierarchicalstructure,andhasbeenvalidatedexperimentallyintheprototype1Webinformationextraction;wrapperinduction;Web摘要Web信息的包裝器有著廣闊的應(yīng)用前景,同時(shí)也是至今沒(méi)有得到有效解決的難題1,提出了基于HTML文檔的模式代數(shù),該代數(shù)包括一致模式集等重要概念以及模式的加法Web信息提取;包裝器歸納學(xué)習(xí)Web挖掘中圖法分類號(hào)WebWeb信RDFXMLOWLWeb的目的是使新Web,Web現(xiàn)有的和目前每天發(fā)布的主要信息都基于HTML,因此,目前期待整個(gè)Web采用語(yǔ)義Web標(biāo)注還不切實(shí)際1由于HTML,,不便

于機(jī)器理解和查詢因此提取Web信息是十分Web包裝器以網(wǎng)頁(yè)作為輸入,返回網(wǎng)頁(yè)中用戶感興趣的數(shù)據(jù)1XML表示1手寫包裝器開(kāi)發(fā)復(fù)雜且1歸納學(xué)習(xí)方法通收稿日期:2005-05-11;修回日期:2006-03-基金項(xiàng)目:國(guó)家自然科學(xué)基金項(xiàng)目 );省自然科學(xué)基金項(xiàng)目Web數(shù)據(jù)的包裝器1現(xiàn)有的包裝器歸納學(xué)習(xí)方法僅在數(shù)據(jù)的左右兩邊標(biāo)記(token)中學(xué)習(xí)該數(shù)據(jù)的提取規(guī)則,并僅采用單一提取規(guī)則來(lái)表示每個(gè)需提取的數(shù)據(jù)1,,僅能提取部Web不能適用于格式多樣、經(jīng)常變化的Web網(wǎng)頁(yè)1,,首先為形式HTML,提出HTML,該代數(shù)形式化地定模式集等重要概念;第2,在整個(gè)例子標(biāo)記中學(xué)習(xí)識(shí)別需提取數(shù)據(jù)的模式規(guī)則,而不僅僅只在屬性左右,因此提高了表達(dá)能力3,采用,因而適合于提取格式多樣的Web網(wǎng)頁(yè)1WebDOM的層次樹(shù)表示W(wǎng)eb信息,在該層次樹(shù)中頁(yè)結(jié)點(diǎn)表示需提取的數(shù)據(jù),內(nèi)部結(jié)點(diǎn)表示復(fù)合結(jié)點(diǎn)分為一般復(fù)合結(jié)點(diǎn)和listlist(x)表示多個(gè)x結(jié)點(diǎn)的集11HTML文檔,其層次樹(shù)表示如圖1所示1〈B〉TeatimeChocolateBiscuitsΠB〈BR〈I9120〈ΠIBR〈BSpecialtyBiscuits,Ltd1〈ΠBings 〈ΠIBRLII501ΠII8%〈ΠIBRFig11ThehierarchicaltreeoftheWebpageinexample11Web頁(yè)的層次

確提取后,可由標(biāo)注的實(shí)例學(xué)習(xí)父結(jié)點(diǎn)中各個(gè)子結(jié)點(diǎn)正確地提取1因此,Web層次信息的提取問(wèn)題可歸話、的值1首先由用戶標(biāo)注的商品例子,學(xué)習(xí)list(商品)中各商品的提取規(guī)則并提取各商品的值,然后由用戶標(biāo)注的廠家例子,、、的則并提取各廠家的值,最后由用戶標(biāo)注的廠家名 例子,學(xué)習(xí)廠家名、地址、、的提取規(guī)則并提取其值1設(shè)被正確提取的各廠家值為如下所示的e1,e2,e3,e4:e1:SpecialtyBiscuits,Ltd1〈ΠBB29King’sWay〈ΠBB(26)555—4448;e2:NewEnglandSeafoodCannery〈ΠB〈B〉2100PaulRevereBlvd〈ΠB〈B617)5553267〈ΠBB02134e3:G’day,Mate〈ΠBB170PrinceEdwardHill〈ΠBB2042〈ΠBB〉02)5555914〈ΠB〈B02)5555915:e4:Pavlova、、Ltd1〈ΠB〈B〉RoseSt1MooniePondsΠB〈B032444234〈ΠB〉B30581其中需提取的子結(jié)點(diǎn)數(shù)據(jù)采用關(guān)系模式可表示為廠家(廠家名、地址、郵編)1但與傳統(tǒng)關(guān)系模型不同的是提取的元組中存在缺省屬性(如e1缺省)、屬性存在多屬性值(如e3包含兩個(gè))、屬性的順序不一致(如e2的順序是,而e3是、)1現(xiàn)有方法不能正確提取例2中的數(shù)據(jù)1以下研究通過(guò)例子學(xué)習(xí)父結(jié)點(diǎn)e1,e2,e3,e4址、、的提取規(guī)則,并正確地提取其值1、、HTML文檔是由標(biāo)記(token),這些Num2),Punc2),SP2),SL2),SUL2),SU在以下歸納學(xué)習(xí)中,各種類型的具體標(biāo)記都可以泛化(generalizing為相應(yīng)的泛化標(biāo)記1如例1中的具注的例子頁(yè)[1]1例如,用戶可用鼠標(biāo)點(diǎn)亮標(biāo)注需提 “29,取的數(shù)據(jù)1對(duì)list(x)結(jié)點(diǎn),可由標(biāo)注的實(shí)例學(xué)習(xí) 取各x結(jié)點(diǎn)的規(guī)則1在上一層結(jié)點(diǎn)(父結(jié)點(diǎn))已被為數(shù)字的泛化標(biāo)記Num21從父結(jié)點(diǎn)中提取關(guān)鍵是獲得子結(jié)點(diǎn)在父結(jié)點(diǎn)中開(kāi)始和結(jié)束識(shí)別規(guī)則1因結(jié)束識(shí)別規(guī)則與開(kāi)始識(shí)別規(guī)則類,xx的,tHTML直到標(biāo)記until(t)”只能出現(xiàn)在最后1定義1模式中通配標(biāo)3表示通配任意標(biāo)定義21設(shè)標(biāo)記序列S=S1xS2,x為子結(jié)點(diǎn)若模式r的最后一個(gè)標(biāo)記不為直到until(t)”,rS1rS1

計(jì)算機(jī)研究與發(fā)展2006,43,11r1+r2=r2+r1;(r1+r2)+r3=r1+(r2+r3);③若r1與序列K,r是模式空間Ωr1+rK無(wú)關(guān)1以下設(shè)例子集ExE1:E1={e1:S1=S11xS12,e2:S2=S21xS22,em:Sm=Sm1xSm2}和不包含子結(jié)點(diǎn)xE2即E=E161rE1的子集Ej依次出現(xiàn)1若模式r的最后一個(gè)標(biāo)記為直到標(biāo)記untilt”rS1r中最后一S1t中出現(xiàn)1rS1,rx;

xrE2∪(E1-Ej,rEx的一致模式1R={r1,r2,?,rkriErrr: rSrS無(wú)關(guān)312e3r1=(3〈B)識(shí)別地址結(jié)點(diǎn),模式r2=(3〈B3〈B)識(shí)別結(jié)點(diǎn)但對(duì)e2,r2將導(dǎo)致錯(cuò)誤識(shí)別,因結(jié)點(diǎn)的第1個(gè)標(biāo)記為數(shù)字,而的第1個(gè)標(biāo)記為標(biāo)點(diǎn)符號(hào)1r33〈B3〈Buntil(Num2e3中的結(jié)點(diǎn),同時(shí),對(duì)e2,r3將不會(huì)導(dǎo)致錯(cuò)誤識(shí),untilNum2的語(yǔ)義表示“直到數(shù)字標(biāo)12kA31A=aa?a,M12kA{(12k)|i=aii=3∨i=g(ai),i=1?,k,g(ai表示ai的泛化標(biāo)記1m∈M,m∈M,m=a1a1?a1,m=a2a2

=E-Ej,EjEri,則若循E=E2RE中子結(jié)點(diǎn)x的一致模式集1設(shè)需從例子集En個(gè)子結(jié)點(diǎn)x1,x2,?xn1若對(duì)任一xi(i=12,?,n)存在例子集E中的Lin個(gè)子結(jié)點(diǎn)為掃描各個(gè)例子L1L2?,Ln若存在Lixi的開(kāi)始位置1xi的結(jié)束位置可同樣得到1因此,提取Web信息的關(guān)鍵是得到各個(gè)子結(jié)點(diǎn)的一致模式定義71設(shè)L1,L2,?,Ln分別為子結(jié)點(diǎn)x1 1 1 x,?, 的(開(kāi)始),R,R,?,R =a2,則m,m2之和定義為 =

+m2={a1a?

a|a=a1+a2,i=1,2,?,k},其中a=a1+ 別為子結(jié)點(diǎn)x1,x2,?,xn的結(jié)束一致模式集,則 式類包裝器定義為〈L1,R1,L2,R2, Ln若a1,a2中有一個(gè)為g(a),則和為 gai);aiai41SBxAx是需提取的結(jié)Ωm1until(mx))|(m1MB)∧(mx(Mx)Sx的模式空間151S=BxAx的模式空間為Ω,r1=(m1,until(n1))∈Ω,r2=(m2

until(n2))∈Ω其中m1,m2(MB,n1,n2∈Mx則r1與r2的和定義為r=r1+r2=((m1+m2),un2til(n1+n2))1Sx的模式空間為Ω,r1,r2Rn窮舉搜索子結(jié)點(diǎn)x的模式空間可以找到與子結(jié)點(diǎn)xi一致的模式但是一個(gè)NP完全問(wèn)題11在集合E1:{S11,S21,?,Sm1}中按特征順序選取最長(zhǎng)的序列1按特征順序的原因是HTML標(biāo)記是決定屬性的開(kāi)始和結(jié)束的最重要的標(biāo)志,其次為標(biāo)點(diǎn)和分隔標(biāo)記1選擇轉(zhuǎn)變?yōu)檎_匹配或無(wú)關(guān)1E1中特征最長(zhǎng)序列為Si1,Si=Si1xSi2=a1a2?akxSi2設(shè)結(jié)點(diǎn)x的首標(biāo)記為b算法分為以下兩步11:Sixr1=(3?3ak或r2=(3?3until(b))用r1或r2去匹Si若兩者都提前匹配Si則按特征順序從ak-1a1中選取一個(gè)標(biāo)記aj改進(jìn)模式r1和r2r1=r1+(3?3aj3?3),r2=r2+(3?3aj3?3),r1r2識(shí)別x1記改進(jìn)模式r1和r2的過(guò)程為AddSelfRule1AddSelfRule(S=a1a2?akxSr1=(3?3ak),r2=(3?until(b))Π3Whiler1r2Sr1←r1+(3?3aj3?3),r2←r2+(3?3aj3?3)Ifr1SThenr1Else2:1r去匹配例子集E=E1∪E2設(shè)rE產(chǎn)生錯(cuò)誤匹配的子集為E,的每個(gè)例子Sj設(shè)匹配的標(biāo)記序列為Sj按特征順序從ak-1到a1中選取一個(gè)不在Sj的逆置標(biāo)記序列中的標(biāo)記若不存在這種標(biāo)記則例子集E不存在子結(jié)點(diǎn)xi的一致模式集1否則,設(shè)該標(biāo)記為aj,則將模式rr=r+(3?3aj3?3),改rSjr要么SjSj無(wú)關(guān)1rAddNewRule1若子結(jié)點(diǎn)xi存在一致模式循環(huán)調(diào)AddNewRule得到的改進(jìn)模式rE的每一個(gè)rExi的一致模式1GenModeRul1利用GenModeRul,由一致模式集的定義可產(chǎn)生E中xi的一致模式集算法記為GenModeRuleSet1AddNewRule(rS=a1a2?akxS2)Π3改進(jìn)的模式r3ΠWhilerS設(shè)匹配的元素序列為S),SThenr←r+(3?3aj3?3),rGenModeRule(E=E1∪E2,E1:{ei:S1=SxS12,e2:S2=S21xS22,?,em:Sm=S)iE1Sr←AddSelfRule(Si1=a1a2

Π3Si=Si1xSi2=a1a2?akxSi23ForE=E1∪E2的每個(gè)例子Sj=Sj1xSIfrSjxr←AddNewRule(r,Sj=Sj1xSΠ3改進(jìn)錯(cuò)誤匹配的模式r為正確匹配或無(wú)關(guān)3ΠWhileESj=Sj1xSj2r←AddNewRule(r,Sj=Sj1xSj2)E=E-{Sj}GenModeRuleSet(E=E1Π3產(chǎn)生一致的模式集3While(E1r←GenModeRule(E=E1ForE1eiIfreiThenE1←E1-{R←R∪{r}Π3R3R由GenModeRule算法可知,由該算法產(chǎn)生的模式是與各子結(jié)點(diǎn)一致的模式;因此,GenModeRuleSet算法是有效的1至于算法的完備性問(wèn)題是一個(gè)有待例41以下對(duì)例2中的例子集E求關(guān)于子結(jié)點(diǎn)的一致模式集1此時(shí)E1={e2,e3,e4},E2=e1},e2的S21(即“NewEng2landSeafoodCannery〈ΠB5553267〈ΠB〉〈B)調(diào)用AddSelfRule可得到識(shí)別e2的模式:r13〈B〉3〈ΠBB〉untilNum2該模式e2e3e1e4錯(cuò)誤識(shí)別1e4調(diào)用AddNewRule得到改進(jìn)的模式:1=(3〈B〉3-3〈ΠB〈B〉untilNum2,1識(shí)別e4,e2但將導(dǎo)e31可得1仍然e1無(wú)關(guān)1置E1=E1-{e4,e2}={e3},重復(fù)以上步驟選擇特征最長(zhǎng)序列為e3的S31調(diào)用AddSel2fRulee3r23〈B3〈ΠBB)1E1=E1-{e3}=?1例子集E中子結(jié)點(diǎn)的一致模式集為L(zhǎng)4={1,r2}L4={(3〈B33〈ΠBBuntilNum23〈B〉3〈B〈B1L1{3until(SUL(2))},地址為L(zhǎng)2={3〈B},L3={3until((),3(3until((),3until(N(2)2)}1注意,在的一致模式集中,第1個(gè)模式識(shí)別e1,e2第2個(gè)模式識(shí)別e3中的多個(gè)第3e41類似可得到識(shí)別各子結(jié)點(diǎn)的結(jié)尾的一致模式集R1,R2,R3,R412中的例子集

計(jì)算機(jī)研究與發(fā)展2006,43,2主要包括具有缺省屬性、多屬性值、屬性順序不惟一的表結(jié)構(gòu)Web站點(diǎn)1表1各列分別為站點(diǎn)URLWeb,,訓(xùn)練例子數(shù)表示的實(shí)驗(yàn)結(jié)果12各列分別為站點(diǎn)的模式類包裝器為〈L1,R1,L2,R2, L4 R41S1S2,?Sn中本文實(shí)現(xiàn)了模式類包裝器原型系統(tǒng),對(duì)實(shí)際Web,部分站點(diǎn)的實(shí)驗(yàn)結(jié)果情況如

如,表2第2行中包含書目信息的中“作者”存在多屬性值;大部分書記錄具有“BibTex“屬性值,但少部分缺省該屬性值,另外屬性“書號(hào)ISBN”和“年是“書號(hào)ISBN ”Table1ExperimentResultofWebSiteswithHierarchical”1具有層次結(jié)構(gòu)數(shù)據(jù)的WebWebSiteNumberofMeanPrecision,RecallandNumberofTrain3Type:100%,100%,2;Date:100%,100%,2;ListofCompanyName2TheirURL:100%,100%,Language:100%,100%,1;URL:100%,100%,2;Image:100%,100%,6leyΠdbΠΠgroupsΠindex1html

Translation:88%,100%, State:100%,100%,2;Nation:100%,100%,2;University:100%,100%,1;Group:70%,83%,8;ListofGroupMemberandURL:60%,78%,101 NationName:100%,100%,1;ListofState,Capital,Area,Population:100%,100%,1;TotalArea:100%,100%,1;TotalPopulation:100%,100%,11 FilmName:100%,100%,1;Directedby:100%,100%,1;Screenplay70%,86%,3;Cast:100%,100%,51Table2ExperimentResultofWebSitesofTableStructurewithMissingAttributesorMultipleValuesAttributesorinDifferentOrderWebSite Numberof

MissingAttributesΠMultipleValuesΠDifferentOrder

MeanPrecision,RecallandNumberofTrainExamples 85%,83%

76%,71% 100%,100% 100%,100% 100%,100%不失普遍性,本文實(shí)驗(yàn)的選取沒(méi)有采用隨機(jī)選擇方法,

層次結(jié)構(gòu),以驗(yàn)證本方法的有效性1

結(jié)構(gòu)網(wǎng)頁(yè)信息又能提取層次結(jié)構(gòu)網(wǎng)頁(yè)信息,其平均查準(zhǔn)率、查全率較高,在某些上接近100%,能Web,且其訓(xùn)練例子在可接受的范圍內(nèi)1由實(shí)驗(yàn)結(jié)果可見(jiàn)本文方法是等等:基于HTML模式代數(shù)的Web怎樣提取Web信息并將其轉(zhuǎn)換為關(guān)系數(shù)據(jù)或機(jī)器能理解和查詢處理的XML[3]是一個(gè)的前寫代碼方法表達(dá)能力強(qiáng)但需要編寫復(fù)雜的代碼,且由于網(wǎng)頁(yè)經(jīng)常變化而1WIEN[1]提出了采用歸納學(xué)習(xí)生成包裝器的方法1主要針對(duì)規(guī)范的表式結(jié)構(gòu)信息,數(shù)據(jù)的識(shí)別和提取依賴于數(shù)據(jù)左右兩邊的公共標(biāo)記1其表達(dá)能力弱1SOFTMEALY[2采用有限狀態(tài)自動(dòng)機(jī)歸納學(xué)習(xí)提取Web信息的包裝器,其中數(shù)據(jù)的識(shí)別依賴于數(shù)據(jù)的左右兩邊標(biāo)記特征,較WIEN表達(dá)能力強(qiáng),但只針對(duì)表結(jié)構(gòu)數(shù)據(jù),不Web信息1STALKE[6提出了采用歸納學(xué)習(xí)方法提取層次結(jié)構(gòu)信息源的方法,通過(guò)例子學(xué)習(xí)由landmark(數(shù)據(jù)的左右兩邊連續(xù)若干個(gè)標(biāo)記)表示的提取規(guī)則1由于Web信息的復(fù)雜性和多樣性,很難獲得landmark來(lái)惟一地定位要提取的信息1本文基于模式代數(shù)的包裝器歸納學(xué)習(xí)方法與現(xiàn)有方法相比,具有以下特點(diǎn):①提出了基于HTML文檔的模式代數(shù),其是識(shí)別需提取數(shù)據(jù)的一致模式集;②在整個(gè)訓(xùn)練例子中搜索識(shí)別需提取數(shù)據(jù)的由多個(gè)模式組成的一致模式集1而存在的,,因而不能完全刻畫識(shí)別該數(shù)據(jù)的特征1因此,模式類包Web網(wǎng)頁(yè)信息既本文提出了基于HTML文檔的模式代數(shù),在此基礎(chǔ)上,提出了一種提取Web信息的新方法1該方法定義了模式類包裝器,并給出了其歸納學(xué)習(xí)生成算法1該方法采用在整個(gè)訓(xùn)練例子中學(xué)習(xí)由多個(gè)模式組成的一致模式集,結(jié)構(gòu)網(wǎng)頁(yè),其有效性在原型系統(tǒng)中通過(guò)實(shí)驗(yàn)得到驗(yàn)證1本文進(jìn)一步的研究工作包括在模式類包裝器中結(jié)合對(duì)象模型[12],以及對(duì)模式代數(shù)的完備性等

[1]NicholasKushmerick,DWeld,RDoorenbos1Wrapperinduc2tionforinformationextraction[C]1Int’lJointConfonArtificialInligence,Hyderabad, ,1997[2]Hsu,CMDung1Generatingfinite2statetransducersforsemi2structureddataextractionfromtheWeb[J]1JournalofInfor2mationSystems,1998,23(8):521-538[3]LüJianhua,WangGuoren,YuGe1OptimizingpathexpressionqueriesofXMLdata[J]1JournalofSoftware,2003,14(9):1615-1620(in(呂建華,王國(guó)仁,1XML數(shù)據(jù)的路徑表達(dá)式查詢優(yōu)化技術(shù)[J]1軟件學(xué)報(bào),2003,14(9):16151620)[4]JHammer,HGarcia2Molina,SNestorov,etal1Template2basedwrappersintheTSIMMISsystem[C]1Int’lConfonManagementofData,Tucson,Arizona,1997[5]RBaumgartner,SFlesca,GGottlob1VisualWebinformationextractionwithLixto[C]1VaryLargeDataBases,Roma,I2taly,2001[6]IMuslea,SMinton,Knoblock1Ahierarchicalapproachtowrapperinduction[C]1ThirdConfonAutonomousAgents,Seattle,WA,[7]XiaofengMeng,HongjunLu,etal1DataextractionfromtheWebbasedonpre2definedschema[J]1JournalofComputerSci2enceandTechnology,2002,17(4):377-388[8]LiXiaodong,GuYuqing1DOM2basedinformationextractionfortheWebsource[J]1ChineseJournalofComputers,2002,25(5):526-533(inChinese)(,1基于DOM的Web信息提取[J]1計(jì)算機(jī)學(xué)報(bào),2002,25(5):526533)[9]HuDongdong,MengXiaofeng1AutomaticallyextractingWebdatausingtreestructure[J]1JournalofComputerResearchandDevelopment,2004,41(10):1607-1613(inChinese)(胡東東,1一種基于樹(shù)結(jié)構(gòu)的Web數(shù)據(jù)自動(dòng)提取方法[J]1計(jì)算機(jī)研究與發(fā)展,2004,41(10):16071613)[10]HuangYuqing,QiGuangzhi,ZhangFuyan1Extractingsemi2structuredinformationfromtheWeb[J]1JournalofSoftware,2000,11(1):73-78(inChinese)(,,1從Web文檔中構(gòu)造半結(jié)構(gòu)化信息的提取器[J]1軟件學(xué)報(bào),2000,11(1):7378)[11]GaoJun,WangTengjiao,YangDongqing,etal1Ontology2basedtwo2phasesemi2automaticWebextraction[J]1ChineseJournalofComputers,2004,27(3):310-318(inChinese)(高軍,蛟,楊冬青,等1基于Ontology的Web內(nèi)容二階段半自動(dòng)提取方法[J]1計(jì)算機(jī)學(xué)報(bào),2004,273):310-[12]PengZhiyong,LuoYi,ShanZhe,etal1Realizationofwork2flowviewsbasedonobjectdeputymodel[J]1ChineseJournalofComputers,2005,28(4):651-660(inChinese)(,,單,等1基于對(duì)象模型的工作流視圖實(shí)現(xiàn)[J]1計(jì)算機(jī)學(xué)報(bào),2005,28(4):651660) 計(jì)算