烏爾柯西，楊 抒，王 業(yè)，游香薷

(新疆農(nóng)業(yè)大學計算機與信息工程學院，新疆烏魯木齊 830052)

一種基于知識工程的DeepWeb信息抽取方法

烏爾柯西，楊 抒，王 業(yè)，游香薷

(新疆農(nóng)業(yè)大學計算機與信息工程學院，新疆烏魯木齊 830052)

DeepWeb中蘊含的信息越發(fā)龐大并且價值可觀。但是由于DeepWeb信息的高度異構(gòu)性、自主性、動態(tài)性以及不完整性，DeepWeb主題性網(wǎng)站的設計風格、頁面結(jié)構(gòu)、顯示內(nèi)容的不同，JavaScript技術(shù)的廣泛使用等因素，使傳統(tǒng)的抽取技術(shù)無法有效自動化集成蘊含在DeepWeb中的高質(zhì)量信息資源。提出一種基于KBE(知識工程)的DeepWeb信息抽取方法。通過對目標DeepWeb的頁面模式、頁面HTML結(jié)構(gòu)、頁面視覺信息等進行分析、整合，利用HTML DOM(Document Object Model)樹解析算法，自動或半自動方式匹配出符合頁面模式、頁面HTML結(jié)構(gòu)以及目標信息源等元素的模板，來對Deep-Web中的信息進行定位，從而得到頁面中的自由文本，結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)。實驗以大量嵌套結(jié)構(gòu)的網(wǎng)站數(shù)據(jù)作為數(shù)據(jù)來源，驗證了抽取方法的有效性。

DeepWeb;JavaScript技術(shù);嵌套結(jié)構(gòu);DOM樹;抽取模型

0 引言

根據(jù)美國伊利諾伊大學MetaQuerier［1］研究表明，DeepWeb具有規(guī)模大、覆蓋面積廣、增長迅速、信息結(jié)構(gòu)化程度高、信息質(zhì)量高等特點。與Surface Web相比，DeepWeb蘊藏的信息不但豐富，而且對于每個Web數(shù)據(jù)庫而言，往往更加專注于某一領(lǐng)域的信息，如金融、商貿(mào)、科技、教育、醫(yī)療、娛樂等。根據(jù)2010年清華大學給出的中文DeepWeb規(guī)模的統(tǒng)計結(jié)果表明，當前中文DeepWeb在萬維網(wǎng)上有60多萬個查詢接口，與2006年的統(tǒng)計結(jié)果相比增長了7倍［2］。其中，94.6%的DeepWeb查詢接口出現(xiàn)在站點的前3層，而且非結(jié)構(gòu)化數(shù)據(jù)庫的比例占到64%［3］。

雖然DeepWeb中蘊含了大量有價值的信息，但是由于DeepWeb信息也具有高度的異構(gòu)性、自主性、動態(tài)性，以及不完整性等特點，同時，DeepWeb網(wǎng)站都是主題性網(wǎng)站，每個站點的設計風格、頁面結(jié)構(gòu)、顯示內(nèi)容都各異;因此，能夠有效自動化集成蘊含在Deep-Web中的高質(zhì)量信息資源就成為一項極具挑戰(zhàn)性的課題。

1 相關(guān)研究

國內(nèi)外學者對DeepWeb網(wǎng)絡的研究主要包括DeepWeb數(shù)據(jù)源的發(fā)現(xiàn)、查詢接口的抽取、數(shù)據(jù)集成等，并且都取得了不錯的研究成果。國外的MetaQuerier［1］、ShopBot［4］、HiWE［5］等研究成果對DeepWeb網(wǎng)絡研究奠定了堅實的實踐基礎(chǔ)。近幾年，以孟小峰等為首的DeepWeb研究團隊也開發(fā)了Jobtong［6］系統(tǒng)。雖然在該領(lǐng)域已有許多研究成果，但是仍然存在著需要解決的問題。

在Web2.0時代，大部分DeepWeb是嵌套結(jié)構(gòu)，而且廣泛采用JS、XML等技術(shù)實現(xiàn)頁面加載和頁面跳轉(zhuǎn)［7］。有些頁內(nèi)鏈接都不包含在HTML源代碼中，而是隱藏在客戶端腳本JavaScript中［8］。傳統(tǒng)的Web抽取技術(shù)不能有效抽取這種嵌套結(jié)構(gòu)的信息。之前，有人使用嵌入式瀏覽器界面征服JavaScript動態(tài)跳轉(zhuǎn)來延續(xù)加載［9］，從而抽取嵌套結(jié)構(gòu)中的信息。但是，由于這種方法是利用嵌入式瀏覽器界面實現(xiàn)的，因此存在速度慢、效率低等不足。

目前，DeepWeb抽取方法主要有基于樣本訓練［10-11］的抽取方法和基于知識工程(KBE)的抽取方法［12］。樣本訓練方法主要通過學習已有的語料庫規(guī)則處理未知的新文本。這種方法是目前DeepWeb搜索引擎的研究趨勢，但它需要足夠數(shù)量的訓練數(shù)據(jù)，才能保證其處理質(zhì)量。KBE方法也稱為模式匹配和基于包裝器方法。主要靠編制一些規(guī)則，使規(guī)則能處理特定領(lǐng)域的信息抽取問題。此方法必須解決的一個關(guān)鍵問題是構(gòu)造Web站點的頁面模型(規(guī)則)。Crescenzi V和Chang C H提出的RoadRunner和MDR算法使用較多。上述兩種算法都需要通過對Web頁面確定需要抽取的信息塊，然后建立信息抽取模型［13］，從而獲取Web頁面信息。Dhamankar等開發(fā)了基于復雜語義的iMAP系統(tǒng)［14］，該方法是對所有可能的空間進行無限匹配，建立一個領(lǐng)域知識，然后采用人機交互方式對匹配進行檢查和修改。但是此方法檢索無限候選匹配耗時很長，不太實用。Madhavan等提出的基于語料庫的模式匹配方法［15］，通過許多模式及映射關(guān)系來增加待匹配模式之間的關(guān)系，以便能更好地進行匹配。但是語料庫中屬性之間的關(guān)系松散，不能完全表達屬性之間的關(guān)系。國內(nèi)的胡東東［16］、曲著偉［17］、廖濤［18］等都提出了一些針對特定領(lǐng)域的抽取方法，但由于抽取模型過于領(lǐng)域化，雖然效率高但不通用，不能有效地抽取嵌套結(jié)構(gòu)的DeepWeb網(wǎng)頁信息。

借鑒前人的研究成果，文中提出一種基于KBE的DeepWeb信息抽取方法。在實現(xiàn)過程中，通過對當前DeepWeb的一系列分析，匹配出符合頁面模式、頁面HTML結(jié)構(gòu)以及目標信息源等元素的模型，來對DeepWeb中的信息進行定位，從而得到頁面中的自由文本，結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)。

2 DeepWeb數(shù)據(jù)抽取過程

通過對Web頁面模式、頁面HTML結(jié)構(gòu)以及頁面視覺信息等結(jié)果的分析，使用知識工程方法進行信息抽取。

定義1(頁面模式):通過圖形界面與用戶交互，由用戶指出頁面上感興趣的區(qū)域，進而產(chǎn)生抽取規(guī)則。

定義2(頁面HTML結(jié)構(gòu)):抽取之前將Web頁面解析成一棵DOM樹，通過自動或半自動的方式產(chǎn)生抽取規(guī)則。

定義3(頁面視覺信息):視覺信息是頁面元素、某一特定的源代碼(JS、JavaScript)在HTML源碼中所處位置等視覺上的線索。

定義4(知識工程方法):也稱模式匹配方法。需要抽取的對象設定一個預先定義好的數(shù)據(jù)模型，使目標數(shù)據(jù)盡量能夠符合預定義的模型。

結(jié)合前面的分析，DeepWeb信息抽取可分為三個階段，即網(wǎng)頁分析、模板生成、數(shù)據(jù)抽取。抽取過程如圖1所示。

2.1 DeepWeb結(jié)構(gòu)分析

圖2是來自Wood365.cn的DeepWeb嵌套結(jié)構(gòu)的頁面。＜1，2，…，n＞定義為嵌套結(jié)構(gòu)。為了使分析更清楚，截取了部分信息塊頁面。圖中可以看到一些超鏈接和上下頁面索引，將它們稱之為主題信息塊。其中，單個鏈接稱之為信息條，鏈接終端的信息稱為信息源。

分析頁面的HTML源碼發(fā)現(xiàn)，頁面中同一信息塊的目標信息具有類似的HTML源碼，并且同一信息塊的信息記錄在DOM樹聚類中具有相同的節(jié)點中，就是說目標信息源的標簽名是相同的。還有，傳統(tǒng)的Web信息抽取中，通過分析源代碼中的＜a＞標簽得到其他頁面的URL地址，而在嵌套結(jié)構(gòu)的Web信息抽取中，不僅要考慮＜a＞標簽，還要考慮是否采用js技術(shù)-“網(wǎng)址從傳參獲得并轉(zhuǎn)向”來重寫URL并實現(xiàn)頁面跳轉(zhuǎn)，這是DeepWeb嵌套結(jié)構(gòu)的一種趨勢。一般，此類URL由前綴、索引、后綴組成:

前綴:信息塊頁面的主入口地址。

索引:n一般為數(shù)字，也就是頁面轉(zhuǎn)換時的關(guān)鍵傳參。賦有效的初始值后，通過遞增或遞減來改變n的值，從而達到頁面跳轉(zhuǎn)。如，n=1，2，3…。

后綴:一般為html、htm、asp等靜態(tài)網(wǎng)頁文件后綴。利用js技術(shù)，調(diào)用JavaScript腳本實現(xiàn)的頁面跳轉(zhuǎn)的代碼段如下:

Html源碼中的參數(shù)傳遞:

＜script language="javascript"type="text/javascript"＞loadPage(＇marketList_＇，＇html＇，26962，30，1)language="javascript"src="http://meta.wood365.cn/ wood365_ShangJi_Js/loadPage.js"type="text/javascript"＞＜/script＞

JavaScript代碼段:

//url頁面前綴

//suffix頁面后綴不包括"."

//recordCount總個數(shù)

//pageSize頁行數(shù)

//pageIndex頁索引

//當前頁

function loadPage(url，suffix，recordCount，pageSize，pageIndex){

if(recordCount==0){return false;}

var pageCount=(recordCount%pageSize==0)? recordCount/pageSize|0:(recordCount/pageSize+1)|0; //pageCount計算總頁數(shù)

var pre=0;//上一頁

var next=0;//下一頁

var startCount=0;//頁碼開始索引

var endCount=0;//頁碼結(jié)束索引

var pagestr="";

next=pageSize+1;

}

通常，這些信息都是生成抽取模型的關(guān)鍵。

2.2 生成抽取規(guī)則

生成模板在抽取過程中占有很重要的地位，通過對抽取區(qū)域的分析，限定抽取規(guī)則，采用信息塊的HTML標簽和索引值等信息相結(jié)合的方式，以自動或手動的形式進行模式匹配。基于網(wǎng)頁結(jié)構(gòu)的模型生成算法如下:

算法1:基于網(wǎng)頁結(jié)構(gòu)分析的算法。

(1)確定目標網(wǎng)頁，分析其結(jié)構(gòu)以及 HTML源代碼。

(2)預處理，經(jīng)過2.1節(jié)的分析過程已得到抽取規(guī)則的限定條件集。

(3)將限定條件集依次在抽取模板中以手動或自動的形式進行模式匹配。如，已知目標網(wǎng)頁中，信息塊的編碼為UTF-8、頁面間以“網(wǎng)址從傳參獲得并轉(zhuǎn)向”的形式跳轉(zhuǎn)以及目標信息源的HTML為P，那么以這些信息為限定條件進行模式匹配:{UTF-8＆URL＆＜title＞＜/title＞＆＜P＞＜/P＞＆…}，多個信息源的限定條件可以并存，以此來建立對應的抽取模型。

2.3 信息抽取

數(shù)據(jù)抽取需要根據(jù)符合頁面的模型來遍歷HTML源代碼，在遍歷過程中對當前頁面進行以下處理:(1)對頁面上的鏈接進行解析;(2)對頁面上符合抽取模型的所有節(jié)點進行聚類。

在第一步中，將正則表達式與模型相結(jié)合，找出頁面上所有鏈接放入待抽取URL隊列中。在第二步中，將對第一步中獲得的URL隊列一一訪問，通過遍歷HTML DOM樹中的所有節(jié)點，建立與模型對應的新的DOM樹結(jié)構(gòu)，再利用正則表達式對此DOM樹進行內(nèi)容提取。具體算法如下:

算法2:信息抽取算法。

(1)選擇符合當前頁面的模型。

(2)獲取網(wǎng)頁HTML源代碼并解析頁內(nèi)鏈接，并放入待抽取URL隊列中。

(3)從待抽取URL隊列中按先進先出的規(guī)律，訪問并獲得HTML源代碼。通過遍歷HTML DOM樹中的所有節(jié)點，在不影響網(wǎng)頁內(nèi)容的前提下能夠?qū)Ξ斍胺夏Ｐ偷乃泄?jié)點進行聚類，建立與模型對應的DOM樹結(jié)構(gòu)。比如，網(wǎng)頁源代碼如下:

＜html＞

＜head＞＜title＞網(wǎng)頁標題 ＜/title＞＜/head＞

＜body＞＜div＞＜P＞text1＜/P＞＜/div＞

＜table＞＜tr＞＜td＞text2＜/td＞＜/tr＞＜/table＞

＜div＞＜P＞text3＜/P＞＜/div＞

＜/body＞

＜/html＞

要想獲得title、P、table標簽里的內(nèi)容，通過模型獲得對應的DOM樹結(jié)構(gòu)如下:

＜title＞網(wǎng)頁標題＜/title＞

＜P＞text1＜/P＞

＜table＞＜tr＞＜td＞text2＜/td＞＜/tr＞＜/table＞

＜P＞text3＜/P＞

(4)利用簡單的正則表達式，從節(jié)點聚類的DOM樹中快速、準確地抽取目標信息text1、text2、text3并進行整合。

3 實驗

3.1 評價標準

召回率(Recall)、準確率(Precision)及綜合評價(F-Measure)是數(shù)據(jù)挖掘中常用到的評價指標。Precision就是檢索出來的條目(比如文檔、網(wǎng)頁等)有多少是準確的;Recall就是所有準確的條目有多少被檢索出來了。以本實驗為例，它們的關(guān)系如表1所示。

從表1中可以看出每個參數(shù)代表的含義:A為檢索出的相關(guān)數(shù)據(jù);B為檢索出的不相關(guān)數(shù)據(jù);C為未檢索出的相關(guān)數(shù)據(jù);D為未檢索出的不相關(guān)數(shù)據(jù);E表示A條檢索出的相關(guān)數(shù)據(jù)中有E條準確無誤;F表示B條檢索出的不相關(guān)數(shù)據(jù)中有F條準確無誤。

通過表1，將召回率R、準確率P以及綜合評價標準F值定義如下:

3.2 結(jié)果與分析

實驗從中國木業(yè)網(wǎng)、中國園林網(wǎng)等網(wǎng)站中隨機抽取了50個主題性站點作為測試源，分別對“行情信息”、“木業(yè)字典”、“求購”等多個主題的嵌套結(jié)構(gòu)的網(wǎng)頁進行模型匹配并抽取文本、表格等信息。從中任意選取了1 248條、3 000條、9 000條數(shù)據(jù)信息作為實驗的評價標準，以此來驗證基于網(wǎng)頁結(jié)構(gòu)特征的Deep-Web數(shù)據(jù)抽取的有效性。

根據(jù)上述評價標準，在表2中分別給出了抽取文本信息和表格后所得到的結(jié)果。

通過表2可以看出，此方法對兩種不同數(shù)據(jù)抽取都能達到比較好的效果。文本信息的準確性因為有些不相關(guān)的信息加進了文本信息，使得在召回率高的情況下，準確率略降低。而表格的抽取因為幾乎所有網(wǎng)頁中的HTML屬性值相同且它是以HTML源碼形式抽取，所以表格的召回率和準確率相對來說比較高。

4 結(jié)束語

文中針對DeepWeb嵌套結(jié)構(gòu)的網(wǎng)頁進行有效的信息抽取，證實了基于知識工程的DeepWeb網(wǎng)頁信息抽取的可行性。通過對多個DeepWeb網(wǎng)頁進行測試，發(fā)現(xiàn)該方法具有較高的準確率，并且模型結(jié)構(gòu)使得抽取技術(shù)具有較好的可移植性，但它在模型生成和補充模型中過于依賴網(wǎng)頁結(jié)構(gòu)，使得它在不同結(jié)構(gòu)的DeepWeb網(wǎng)頁信息抽取過程中受到了限制。為了克服現(xiàn)有方法的不足，下一步將重點研究基于網(wǎng)頁結(jié)構(gòu)自適應的抽取技術(shù)。

［1］ Cheng Tao，Yan Xifeng，Chang K C.EntityRank:searching entities directly and holistically［C］//Proceedings of the 33rd international conference on VLDB.［s.l.］:ACM，2007:387-398.

［2］ CNNIC.第十六次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告［R/ OL］.2015-07-08.http://www.cnnic.net.cn/.

［3］ 趙朋朋，崔志明，高 嶺，等.關(guān)于中國DeepWeb的規(guī)模、分布和結(jié)構(gòu)［J］.小型微型計算機系統(tǒng)，2007，28(10):1799-1802.

［4］ Robert B D，Oren E，Daniels S.A scalable comparison shopping agent for the World-Wide Web［C］//Proc of the international conference on autonomous agents.［s.l.］:［s.n.］，1997:39-48.

［5］ Raghavan S，Garcia-Molin H.Crawling the hidden Web ［C］//Proc of the 27th international conference on VLDB.［s. l.］:［s.n.］，2001:129-138.

［6］ Jobtong.面向領(lǐng)域的DeepWeb數(shù)據(jù)集成系統(tǒng)［EB/OL］. 2007.http://idke.ruc.edu.cn/reports/report2007/Systems/ Jobtong.pdf.

［7］ 楊俊峰，黎建輝，楊風雷.深層網(wǎng)站Ajax頁面數(shù)據(jù)采集研究綜述［J］.計算機應用研究，2013，30(6):1607-1610.

［8］ Garrett J J.Ajax:A new approach to web application adaptive pat［EB/OL］.2005.http://www.adaptivepath.com/ideas/essays/archives/000385.

［9］ Xia Tian.Extracting multi-records from web pages［C］//Proc of fourth international conference on semantics，knowledge and grid.［s.l.］:［s.n.］，2008:396-399.

［10］Wang Y，Hu J.A machine learning based approach for table detection on the Web［C］//Proc of the 11th international con-ference on world wide web.New York:ACM，2002:242-250.

［11］Soderland S.Learning information extraction rules for semistructured and free text［J］.Journal of the Machine Learning，1999，34(1-3):233-272.

［12］Appelt E D，Israel D J.Introduction to information extraction technology［EB/OL］.［2007-04-01］.http://ranger.uta.edu/ ～alp/dm/ixtutorial.pdf.

［13］Pinto D，McCallum A，Wei X.Table extraction using conditional random fields［C］//Proc of the 26th Annual international ACM SIGIR conf on research and development in information retrieval.New York:ACM，2003:235-242.

［14］Dhamankar R，Lee Y，Doan A，et al.iMAP:discovering complex semantic matches between database schemas［C］//Proc of the 6th international conference on SIGMOD.［s.l.］:ACM，2004:383-394.

［15］Madhavan J，Bernstein P，Doan A，et al.Corpus-based schema matching［C］//Proc of the international conf on data engineering.［s.l.］:［s.n.］，2005:57-68.

［16］胡東東，孟小峰.一種基于樹結(jié)構(gòu)的Web數(shù)據(jù)自動抽取方法［J］.計算機研究與發(fā)展，2004，41(10):1607-1613.

［17］曲著偉，李敏強.基于數(shù)據(jù)區(qū)域發(fā)現(xiàn)的信息抽取規(guī)則生成方法［J］.計算機工程，2009，35(22):59-61.

［18］廖 濤，劉宗田，孫 榮.Web表格定位技術(shù)的研究與實現(xiàn)［J］.計算機科學，2009，36(9):227-230.

A DeepWeb Information Extraction Method Based on Knowledge Engineering

WU Er-ke-xi，YANG Shu，WANG Ye，YOU Xiang-ru
(College of Computer＆Information Engineering，Xinjiang Agricultural University，Urumqi 830052，China)

The information contained in DeepWeb is more and more huge with great value.But due to the factors that DeepWeb information is highly heterogeneous，autonomous，dynamic and incomplete，and the design style，page structure，display contents of DeepWeb theme website are different，and the use of JavaScript technology is widespread，the traditional extraction technology can’t be effectively automated integration of high quality information contained in DeepWeb resources.Presents a DeepWeb extraction method based on knowledge engineering.The page mode，HTML structure and visual features of DeepWeb are analyzed and integrated.Applies HTML DOM tree parsing algorithm to match the template accorded with page mode，HTML structure and object information source by automatic or semi-automatic way，locating the information in DeepWeb to obtain the free text，structured and semi-structured data.Using a large number of site data with nested structure as data source，the effectiveness of extraction method is verified.

DeepWeb;JavaScript technology;nested structure;DOM tree;extraction model

TP301

A

1673-629X(2016)09-0183-04

10.3969/j.issn.1673-629X.2016.09.041

2015-07-07

2015-11-18< class="emphasis_bold">網(wǎng)絡出版時間:

時間:2016-08-23

新疆維吾爾自治區(qū)自然科學基金(2014211B023)

烏爾柯西(1989-)，女，碩士研究生，研究方向為深層數(shù)據(jù)挖掘;楊 抒，副教授，研究方向為數(shù)據(jù)挖掘、軟件工程、林業(yè)信息化。

http://www.cnki.net/kcms/detail/61.1450.tp.20160823.1112.014.html