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

烏爾柯西，楊 抒，王 業，游香薷

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

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

烏爾柯西，楊 抒，王 業，游香薷

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

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

DeepWeb;JavaScript技術;嵌套結構;DOM樹;抽取模型

0 引言

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

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

1 相關研究

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

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

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

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

2 DeepWeb數據抽取過程

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

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

定義2(頁面HTML結構):抽取之前將Web頁面解析成一棵DOM樹，通過自動或半自動的方式產生抽取規則。

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

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

結合前面的分析，DeepWeb信息抽取可分為三個階段，即網頁分析、模板生成、數據抽取。抽取過程如圖1所示。

2.1 DeepWeb結構分析

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

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

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

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

后綴:一般為html、htm、asp等靜態網頁文件后綴。利用js技術，調用JavaScript腳本實現的頁面跳轉的代碼段如下:

Html源碼中的參數傳遞:

＜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總個數

//pageSize頁行數

//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計算總頁數

var pre=0;//上一頁

var next=0;//下一頁

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

var endCount=0;//頁碼結束索引

var pagestr="";

next=pageSize+1;

}

通常，這些信息都是生成抽取模型的關鍵。

2.2 生成抽取規則

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

算法1:基于網頁結構分析的算法。

(1)確定目標網頁，分析其結構以及 HTML源代碼。

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

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

2.3 信息抽取

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

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

算法2:信息抽取算法。

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

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

(3)從待抽取URL隊列中按先進先出的規律，訪問并獲得HTML源代碼。通過遍歷HTML DOM樹中的所有節點，在不影響網頁內容的前提下能夠對當前符合模型的所有節點進行聚類，建立與模型對應的DOM樹結構。比如，網頁源代碼如下:

＜html＞

＜head＞＜title＞網頁標題 ＜/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標簽里的內容，通過模型獲得對應的DOM樹結構如下:

＜title＞網頁標題＜/title＞

＜P＞text1＜/P＞

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

＜P＞text3＜/P＞

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

3 實驗

3.1 評價標準

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

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

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

3.2 結果與分析

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

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

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

4 結束語

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

［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.第十六次中國互聯網絡發展狀況統計報告［R/ OL］.2015-07-08.http://www.cnnic.net.cn/.

［3］ 趙朋朋，崔志明，高 嶺，等.關于中國DeepWeb的規模、分布和結構［J］.小型微型計算機系統，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.面向領域的DeepWeb數據集成系統［EB/OL］. 2007.http://idke.ruc.edu.cn/reports/report2007/Systems/ Jobtong.pdf.

［7］ 楊俊峰，黎建輝，楊風雷.深層網站Ajax頁面數據采集研究綜述［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］胡東東，孟小峰.一種基于樹結構的Web數據自動抽取方法［J］.計算機研究與發展，2004，41(10):1607-1613.

［17］曲著偉，李敏強.基于數據區域發現的信息抽取規則生成方法［J］.計算機工程，2009，35(22):59-61.

［18］廖 濤，劉宗田，孫 榮.Web表格定位技術的研究與實現［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">網絡出版時間:

時間:2016-08-23

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

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

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