基于模板的Ｗｅｂ信息自動提取方法
2009-01-01 00:00:00鄭長松傅彥佘莉
計算機應用研究 2009年2期
(電子科技大學 計算機工程學院 數據挖掘實驗室， 成都 610054)
摘 要：為了解決傳統Web信息提取過程中準確率和效率相矛盾的問題，提出了一種基于模板與機器自動識別相結合的Web信息自動提取方法。該方法先利用一組啟發式規則自動識別HTML文本中不同屬性信息之間的分隔符，再把它們配置到模板中，然后根據模板分析相同類型的網頁，最后以話題線索的方式存儲。實驗結果表明，與傳統的Web信息提取方法相比，本方法能夠處理多種結構類型的網頁，同時能夠在很大程度上提高準確率、召回率和效率；并且可以在不需要修改算法的情況下根據用戶需求動態提取相關信息，滿足各方面研究的需要。
關鍵詞：信息提取；模板化；自動識別；分隔標記；結構化
中圖分類號：TP393.04 文獻標志碼：A
文章編號：10013695(2009)02057003
Templatebased information automatic extraction of Web
ZHENG Changsong，FU Yang，SHE Li
(Laboratory of Data Mining， School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)
Abstract:In order to deal with the contradiction between accuracy and efficiency in the traditional Web information extraction，proposed one method to automatically extract Web information， which was based on the combination of template and machine automatic diagnosis.First，used a set of heuristic rules of automatic diagnosis to detect separating characters between different attributes in HTML text， and deployed those characters to the template， then based on the template analyzed Web page of the same kind， and finally saved the results in the form of topic thread. Experimental results demonstrate that compared with the traditional Web information extraction ways，this method can deal with Web pages with rich multiple structures， and sufficiently improve the accuracy， recalling rate and efficiency， and that the method can dynamically extract relevant information to respect users’ requirement and support various successive researches withoutrevision of the algorithm.
Key words:information extraction；template;automatic cognition;separator tag;structurization隨著互聯網用戶和信息量的激增，Web信息挖掘已成為一個重要的研究課題。網絡上的信息大多數都是以網頁的形式表現出來的，但是網頁結構在不斷變化，除了新聞等單結構類型網頁，還有如論壇、博客Blog、維基WIKI、聚合新聞RSS等的多結構類型網頁，如圖1所示。
網頁中大都充斥著大量的浮動廣告、網站導航、不必要的圖片、鏈接和版權等與網頁主題內容不相關的信息。如何快速、有效地獲取自己所需要的信息，而不被大量的不相關信息所迷惑，已成為迫切需要解決的問題。本文提出的Web信息提取方法從源頭上消除了網頁噪聲，避免了模板需要人工手動配置或訓練的繁瑣問題，解決了機器自動識別中信息詳細程度不高及效率低等缺陷，也滿足了各種信息形式的需求。該方法已應用于音樂論壇搜索、“P2P僵尸網絡發現與監測技術”項目和“Web輿情的社會網絡關系挖掘、音樂論壇的社會網絡挖掘”項目中。其中音樂論壇搜索項目已投入商業運行。
1 國內外研究現狀
在國內外已有許多網頁信息提取的方法。例如，文獻[1]通過訓練得到網頁主題內容的模板，然后用模板進行主題內容提取；文獻[2，3]根據網頁標簽標記與文本標記的特征采用聚類算法計算文本的相似性以確定主題信息的位置；文獻[4]主要是通過一組啟發式算法自動發現及提取目標對象；文獻[5]融合基于標志規則和基于內容規則的兩種方法，提出一種基于特征相關學習的網頁信息提取方法；文獻[6]利用網頁標記對網頁進行分塊，把網頁塊表示成特征向量，并根據有序標記集識別主題內容塊；文獻[7]用網頁信息擴展傳統的HMMs學習出GHMM，用得到的模型對網頁信息進行提取；文獻[8]通過源網站與屬于相同領域的不同站點的比較，分別提取出站點不變與站點依賴特征，用得到的結構對目標站點進行信息提取。
目前常用的信息提取方法大多只針對新聞等非交互性的網頁進行，能提取的網頁模式比較單一，提取信息細化度（信息的詳細程度）不高，而且不能根據用戶需求提取相關信息，準確率偏低。在對論壇、Blog等多結構類型的網頁進行信息提取時，文獻[1，5]的準確率就很低；文獻[2，4，6~8]雖然可以提取這類型的網頁，準確率也比較高，但是也只能提取網頁的主要內容，如論壇中的用戶信息和帖子評論信息則不能分離地提取出來，信息的詳細程度不高。結果不能按照信息屬性分開保存，也就不能滿足不同研究需要不同形式的信息。
本文是把模板化方法提取的準確性、高效性、詳細性與自動發現規則的機器操作優點相結合，準確高效地提取用戶需求的詳細信息，并用結構化的形式保存，方便用戶分析研究。
2 信息提取算法
本文方法所要分析的網頁是用爬蟲軟件從遠端站點下載，按照網站為單位保存到本地目錄，目錄名為網站的主頁名。
2.1 基本定義
定義1 解析(parse)。將HTML文檔轉換DOM樹的過程稱為解析。解析后，HTML文檔的內容包含在樹節點中，對HTML文檔的處理可通過對DOM樹的操作實現。
定義2 模板化。指用一個固定的框架來描述網頁的待提取信息的組織結構。
定義3 話題線索（topic thread）。指對一個網頁相關信息的描述，包括網頁的點擊率、回復數(多結構有效)、標題與評論。評論包含內容與作者信息。當網頁為單結構類型時回復數為0，評論只有一個；多結構類型時包含回復數個評論。
2.2 算法綜述
本文方法主要分成五個部分：HTML解析器、分隔符自動識別器、網頁結構模板生成器、信息提取和結果存儲。圖2是本文Web信息提取方法的處理流程。
解析器將HTML文檔轉換為DOM樹，本文采用開源工具HTMLParser中的解析方法。分隔符自動識別器識別DOM樹中不同屬性信息間的分隔標記。模板生成器由系統自動指定或者經人工按照自身需求篩選出所需分隔標記并配置模板。信息提取模塊根據配置好的模板對具有同一結構的網頁進行信息提取。結果存儲把得到的信息存放到數據庫中。
2.3 分隔符自動識別方法
該方法依據的是一個網頁中包含多少對等的信息塊，就包含多少與之對應的分隔標記。比如論壇中的某頁含有多個評論，每個評論之間某個（或某組）標簽可以把它們分離開來（參見文獻[4]）。
通過分析大量熱點網站，總結出五個啟發式規則用來識別分隔符標記，具體如下：
a）標準漂移式規則R1。統計兩個前后出現的標簽(同一類型)之間的距離，即包含的字符數，按升序對得到的候選標記進行排列。
b）重復匹配率規則R2。根據成對標記的出現次數與單個標記出現次數的不同，對候選標記進行升序排列。
c）分隔符標記標志規則R3。在大量實踐中總結出一組經常作為分隔標記符的標記列表，按照出現的頻率降序排列：{tr，table，p，li，hr，dt，ul，pre.font，dl，div，dd，blockquote，b，a，span，td，br ，h4，h3，h2，hl，strong，em，i}。
d）子樹路徑數比較規則R4。依次統計候選節點到達其他節點的路徑數，然后按降序對候選節點進行排列。
e）兄弟標記規則R5。由于分隔標記出現次數與待分目標對象的個數相一致，通過比較兩個相繼出現的標記在網頁中出現的次數，得到一組候選分隔標記，按照降序排列。
從15個熱點網站中選擇1 500個網頁對以上五個規則進行單獨測試，發現單個的效果并不好。具體數據如表1所示。
表1 各規則實驗數據
利用聯合概率對每個規則獲取到的候選標記進行聯合概率運算，篩選正確的分隔標記。若在一個文檔中，P(A)表示規則R1篩選分隔標記成功的概率，P(B)表示規則R2篩選成功的概率，則P(A∪B)= P(A) + P(B)-P(A)P(B)表示兩個規則聯合起來正確得到分隔標記的概率。例如，若標記tr作為分隔標記被規則R1、 R2、 R3成功識別出的概率分別為0.78， 0.73， 0.40，則這三個規則聯合起來正確識別tr作為分隔標記的概率為96%。當把五種規則聯合起來使用時準確率達到100%，召回率為93%~98%。
2.4 模板生成法
根據topic thread定義模板包含的數據項以及分隔標記的層次及數目，用XML搭建。具體要配置的數據項包括：
a）網站的主頁名。利用網站主頁名來識別對應的模板。
b）主題評論信息。包括作者、發表時間、點擊率、標題、內容等信息。
c）回復評論的信息。包括作者、發表時間、點擊率、標題、內容等信息。在多結構類型的網站中，如果需要提取回復評論，需要配置該項。
網頁包括單結構與多結構兩種內部模式。單結構的只配置a)b)數據項，而多結構類型又可以把網頁上的結構分成主題評論與回復評論。有可能這兩種評論的結構也不一致，所以本文方法把模板分成兩塊，分別對這兩種結構進行配置，配置a)b）c)數據項。
模板具體形式如下：
〈?xml version=\"1.0\" coding=\"utf8\"〉
〈forum desc=\"新浪網站\"HomeNeme=\"sira\"encode=\"gb 2312\"〉
〈!\"帖子列表\"頁面結構〉
〈contentpage〉
〈！主題帖基本結構框架〉
〈topic_review〉
〈filterInfo id=\"separate\"desc=\"主題帖的邊界\"tag=\"div\"〉
〈filterInfo id=\"author_info\"desc=\"作者信息\"tag=\"th\"〉
〈/filterInfo〉
……
〈/topic_review〉
〈!回復帖基本結構框架〉
〈review〉
……
〈/review〉
〈/content_page〉
〈!線索列表模板—start〉
〈!線索的類型〉
〈!話題線索模板—end〉
〈/forum〉
本文方法的模板配置具體涉及到兩種算法：
a)機器自動配置算法。把分隔符自動識別器獲取的分隔符直接配置到模板中。這樣提取的信息就比較粗糙，只能提取到標題、時間、用戶名、內容等混合在一起的信息，而不能把它們分離開。如果對信息詳細度要求不高，可以采用這種全機器操作的方式。
b)半人工篩選算法。先用分隔符自動識別器得到評論之間的分隔標記，添加到模板上的評論分隔項中；然后取其中一個評論的DOM子樹，用分隔符自動識別器獲取評論內部信息間的分隔標記，由人為指定每個分隔標記該具體配置在哪個數據項中，因為機器不能識別分隔標記所代表的語義。如果要求提取詳細信息，可以采用該方式，這樣提取的信息準確率可以達到100%。當然模板也可以全手工配置(可以增加或者刪除某類信息)。
2.5 信息提取及結果存儲
信息提取模塊是根據模板提取DOM樹中的信息，結果以話題線索的形式存儲到數據庫中。具體算法如下：
a)根據指定目錄尋找相關模板，若模板存在，執行b);若不存在，就使用模板生成器生成相關模板，然后執行b)；
b)按照順序讀取目錄下的文件。分析一個頁面，判斷該頁面是否已經分析過：如果分析過，再判斷是否還有部分信息沒有分析，若有，就提取尚未分析過的信息，沒有就拋棄該頁面；如果沒有分析過，就根據模板提取相關信息，生成topic thread對象。
c)把topic thread對象保存到數據庫中。
在提取和存儲過程中同時需要注意以下幾個方面：
a）更新操作。待分析的頁面可以分為兩類，一類是從未分析過的頁面，此時應從該頁面的主題評論開始，提取所有帖子的基本信息；另一類是已分析過的頁面，此時應根據上次分析的最后一個評論的位置，定位第一個新增評論的位置，再對所有新增評論進行挖掘。
b）多頁處理。按順序讀取網頁文件夾中的頁面，對于每一個頁面，根據頁面的編號找到對應話題線索對象或者創建一個新的話題線索對象；然后根據模板獲取該頁面中每一個評論（或連載）的HTML文本；再解析得到所有相關頁面的基本信息，并保存在一個話題線索中。
c）結果保存結構化。本文方法用topic thread對象來保存分析過的頁面，如果該話題有多個相關頁面，則這幾頁分析過的結果將被保存在同一個topic thread中。
3 實驗結果
根據本文方法所實現的Web信息提取系統Digger在投入商業運行前經過了專業的測試，現將測試的部分結果以表2形式給出。
注：測試環境CPU Intel Pentium4 2.66 GHz內存512 MB，硬盤可用空間56 GB，系統Windows XP SP2。
表2的測試及實驗結果可以說明本系統采用的模板與自動發現規則相結合的方法不僅提高了網頁信息的準確率、召回率；同時在效率、系統資源的占用上都優于目前常用的方法，而且本系統提取的信息是以數據結構topic thread結構化方式存儲的。而其他人提出的方法提取的信息還是絞合在一起的。
本文方法與幾種目前常用的信息提取方法比較的結果如表3和圖3~5所示。這些圖表說明在同樣的測試環境下，本文所用的方法在準確率、召回率、執行時間上都優于目前常用的方法，特別是在針對多結構類型的網頁時，本文方法的性價比更高。
4 結束語
本文提出的基于模板的Web信息自動提取方法不僅在準確率、召回率和效率方面都優于傳統方法，并且可以在不對方法作任何修改的前提下提取多類型網頁，同時支持多頁處理、更新操作和結果的結構化保存，具有應用場景廣、應用效果好的特點。
本方法仍然存在一些問題。例如提取的信息越詳細，調用自動識別分隔符方法的次數就越多，若只需要提取一個頁面內容信息，則只需要調用該方法一次；倘若要獲取包括標題、用戶、發表時間等詳細的信息，則需調用該方法兩次；當第二次調用自動識別分隔符方法獲取多個候選分隔標記時，由于每個分隔標記代表的意義不一樣，還需要人工進行篩選指定。如何通過機器自動篩選功能，達到完全的自動化提取將是下一步研究的重點。
參考文獻：
［1］
歐健文， 董守斌， 蔡斌. 模板化網頁主題信息的提取方法[J].清華大學學報：自然科學版，2005，45(s1):17431747.
[2]蒲宇達，關毅，王強.基于數據挖掘思想的網頁正文抽取方法的研究[C]//第三屆學生計算語言學研討會論文集.2006：246250.
[3]LE P B V，GAO Xiaoying.Using clustering for Web information extraction[C]//Proc of the 20th Australian Joint Conference on Artificial Intelligence.2007:415424.
[4]BUTTLER D，LIU Ling.A fully automated object extraction system for the World Wide Web[C]//Proc of International Conference on Distributed Computing Systems.2001:361370.
[5]張茂元，張金隆，盧正鼎，等.基于特征相關學習的網頁信息提取方法[J].華中科技大學學報：自然科學版，2007，35(7):14.
[6]殷賢亮，李猛.基于分塊的網頁主題信息自動提取算法[J].華中科技大學學報:自然科學版， 2007，35(10)：3941.
[7]王靜，姚勇，劉志鏡.基于廣義隱馬爾可夫模型的網頁信息抽取方法[J].山東大學學報：理學版，2007，42(11): 4952.
[8]WONG T L，LAM W.Adapting Web information extraction knowledge via mining siteinvariant and sitedependent features[J].ACM Trans on Internet Technology，2007，7(1)：6.
