?1??? ?引言

????2008年1月17日，中國互聯網絡信息中心(CNNIC)發布了《第21次中國互聯網絡發展狀況統計報告》[1]，報告顯示：

???(1) 截至2007年12月，網民數已增至2.1億人。中國網民數增長迅速，比2007年6月增加4800萬人，2007年一年則增加了7300萬人，年增長率達到53.3%。，在過去一年中平均每天增加網民20萬人。

????(2) 目前中國的網民人數略低于美國的2.15億 ，位于世界第二位。目前中國網站數量已達150萬個，比去年同期增長了66萬個，增長率達到78.4%。博客/個人空間等眾多網絡應用需求、域名數量增長的拉動及創建網站操作的簡單化等因素作用在一起，共同使得網站數量猛增。

????(3) 目前中國網頁數為84.7億個，年增長率達到89.4%，網上信息資源的增長速度非常迅猛。這些網頁中，動靜態的比例為0.92:1，動態網頁的比重在逐年增高。

????(4) 目前網民平均上網時長是16.2小時/周，互聯網已經在網民生活中占據一定的地位。

????從以上內容可見，網絡作為人們獲取信息的主要渠道，已成為社會生活的一部分。網絡作為一種新的傳媒，與報紙、無線廣播和電視等傳統的媒體相比，具有開放性，不確定性，交互性，超時空性以及信息量的巨大性等特點。網絡不僅改變了人們的工作方式和生活方式，而且猛烈地沖擊著傳統的思想觀念和思維方式。網絡在傳播現代文明的同時，也附帶了各種“灰色文化”，例如色情、暴力等文化。這些不良網絡文化嚴重污染著網絡環境，尤其對生理日漸成熟、而心理并未成熟的青少年造成了極大的危害。網絡的淫穢站點泛濫成災，成為導致青少年性犯罪增加的一大誘因，也是導致暴力犯罪的一大根源。[2]在互聯網的信息中，有近70%的信息有淫穢的內容。56%的人認為，通俗文化中的色情內容是導致青少年暴力的一大誘因。網絡暴力文化的傳播，對青少年的行為產生誤導，從而導致校園暴力和有組織犯罪的增加。在互聯網上，宣傳暴力的文字和圖片隨處可見。青少年的模仿能力很強，加上暴力文化的影響，使青少年把暴力看成理所當然的事情，把犯罪看成一種游戲。

????當前，不良網絡文化問題已經引起了各國的重視，加強對該問題的調查和懲處是大勢所趨。打擊這些網絡灰色文化不僅需要制定相關的法律法規，還應該利用科技工作者的聰明才智，幫助阻擊或者是抑制這些灰色文化的傳播泛濫。

????互聯網最基礎的功能即提供信息。[1]目前互聯網上的信息已是海量，搜索引擎則是網民在汪洋中搜尋信息的工具，是互聯網上不可或缺的工具和基礎應用之一。目前2.1億網民中使用搜索引擎的比例是72.4%，即已有1.52億人從搜索引擎獲益，半年凈增加3086萬人。因此，為了有效的抵制網絡不良文化，對于搜索引擎服務商來說，需要采取各種有效措施嚴格封堵過濾網絡上的不良內容。

????原理上，搜索引擎技術主要涉及網絡搜索技術、文擋分類技術和網絡信息抽取技術。其中，網絡信息抽取技術是將網頁中的非結構化數據或半結構化數據按照一定的需求抽取成結構化數據。網絡信息抽取結果的質量將直接影響到封堵過濾網絡不良內容的效率。因此，網絡信息抽取技術是應對不良網絡文化的關鍵技術之一。本文將針對網絡信息抽取技術做概要性介紹。
?

?

2??? 網絡信息抽取技術概述

???? ?2.1網絡信息抽取的主要內容

???? 網絡信息抽取屬于網絡內容挖掘(Web content mining)研究的一部分。[3]如圖1所示，主要包括結構化數據抽取(Structured Data Extraction)、信息集成(Information integreation)和觀點挖掘(Opinion mining)等。

?

????圖1網絡信息抽取的主要內容

?

????結構化數據抽取(Structured Data Extraction)的目標是從Web頁面中抽取結構化數據。這些結構化數據往往存儲在后臺數據庫中，由網頁按一定格式承載著展示給用戶。例如論壇列表頁面、Blog頁面、搜索引擎結果頁面等。

????信息集成(Information integration)是針對結構化數據而言的。其目標是將從不同網站中抽取出的數據統一化后集成入庫。其關鍵問題是如何從不同網站的數據表中識別出意義相同的數據并統一存儲。

????觀點挖掘(Opinion mining)是針對網頁中的純文本而言的。其目標是從網頁中抽取出帶有主觀傾向的信息。

????大多數文獻中提到的網絡信息抽取往往專指結構化數據抽取。

????2.2 網絡數據抽取工具簡介

????2.2.1 工具的分類

????傳統的網絡數據抽取是針對抽取對象手工編寫一段專門的抽取程序，這個程序稱為包裝器(wrapper)。近年來，越來越多的網絡數據抽取工具被開發出來，替代了傳統的手工編寫包裝器的方法。目前的網絡數據抽取工具可分為以下幾大類(實際上，一個工具可能會歸屬于其中若干類)[4]：

????開發包裝器的專用語言(Languages for Wrapper Development)：用戶可用這些專用語言方便地編寫包裝器。例如Minerva，TSIMMIS，Web-OQL，FLORID，Jedi等。

????以HTML為中間件的工具(HTML-aware Tools)：這些工具在抽取時主要依賴HTML文檔的內在結構特征。在抽取過程之前，這些工具先把文檔轉換成標簽樹；再根據標簽樹自動或半自動地抽取數據。代表工具有W4F，XWRAP，RoadRunner，MDR。

????基于NLP(Natural language processing)的工具(NLP-based Tools)：這些工具通常利用filtering、part-of-speech tagging、lexical semantic tagging等NLP技術建立短語和句子元素之間的關系，推導出抽取規則。這些工具比較適合于抽取那些包含符合文法的頁面。代表工具有RAPIER，SRV，WHISK。

????包裝器的歸納工具(Wrapper Induction Tools)：包裝器的歸納工具從一組訓練樣例中歸納出基于分隔符的抽取規則。這些工具和基于NLP的工具之間最大的差別在于：這些工具不依賴于語言約束，而是依賴于數據的格式化特征。這個特點決定了這些工具比基于NLP的工具更適合于抽取HTML文檔。代表工具有：WIEN，SoftMealy，STALKER。

????基于模型的工具(Modeling-based Tools)：這些工具讓用戶通過圖形界面，建立文檔中其感興趣的對象的結構模型，“教”工具學會如何識別文檔中的對象，從而抽取出對象。代表工具有：NoDoSE，DEByE。

????基于本體的工具(Ontology-based Tools)：這些工具首先需要專家參與，人工建立某領域的知識庫，然后工具基于知識庫去做抽取操作。如果知識庫具有足夠的表達能力，那么抽取操作可以做到完全自動。而且由這些工具生成的包裝器具有比較好的靈活性和適應性。代表工具有：BYU，X-tract。

????2.2.2 工具的定性評價

????對一個抽取工具的定性評價可參考以下幾個指標[4]：

????自動化程度：這是個非常重要的指標。它意味著在生成包裝器的同時，需要用戶參與的工作量。用專用語言生成包裝器的工具需要用戶手工描繪要抽取的對象的邊界，所以自動化程度較低。以HTML為中間件的工具往往能提供自動化程度較高的生成包裝器的操作，但這種高度自動化的效果需要建立在一個假設上：被抽取頁面的HTML標簽具有高度的一致性。而這個假設對于現實網絡中的大部分頁面是不成立的。基于NLP的工具、包裝器的歸納工具、基于模型的工具都可以稱為半自動化工具，因為這些工具都需要用戶提供樣例頁面，從而生成包裝器。BYU這樣的基于本體的工具首先需要全人工的建立知識庫，但之后，只要本體有足夠的表達能力，抽取操作就能夠做到全自動。

????是否支持復雜結構對象的處理：網頁中大多數的數據呈現出復雜的結構，例如多層嵌套(multiple nesting levels)結構，如圖2所示。這就需要抽取工具能夠處理這些復雜的數據結構。

?

?

圖 2 多層嵌套結構舉例[3]
?

?

????是否支持頁面的文本分析：網頁的內容，基本可分成兩類：一類是半結構化數據，如圖3所示；一類是半結構化文本，如圖4所示。用專用語言生成包裝器的工具、以HTML為中間件的工具、包裝器的歸納工具、基于模型的工具往往依賴于識別出數據的邊界，從而生成抽取規則，所以它們更適合處理半結構化數據。基于NLP的工具更適合處理半結構化文本。BYU這樣的基于本體的工具則兩者都可處理。

?

?

????圖 3 半結構化數據舉例[4]

?

?

?圖 4 半結構化文本舉例[4]

?

????是否提供圖形用戶界面(GUI，Graphical User Interfaces)：為了幫助用戶更好地生成包裝器，一些工具提供了圖形用戶界面。

????是否支持非HTML文檔：一些網頁并不是用HTML寫的。因為基于NLP的工具在分析時完全不依賴于HTML標簽，所以非常適合處理非HTML文檔。包裝器的歸納工具、基于模型的工具在分析時不僅僅依賴于HTML標簽，所以也可以處理一部分非HTML文檔。以HTML為中間件的工具在分析時，則完全依賴HTML標簽，所以不能處理非HTML文檔。

????靈活性(Resilience)和適應性(Adaptiveness)：因為網頁的結構和表達往往變化頻繁，所以評價包裝器的一個重要指標就是靈活性，即當網頁有部分改變時，包裝器是否仍然有效。另一個重要指標是適應性，即一個針對某應用領域的某種Web源的包裝器是否也能對同一應用領域中的其他Web源有效。

????各類抽取工具的定性評價參見圖5。

?

?

?圖5 各類抽取工具的評價圖[4]

????

?

3????網絡信息抽取的主要方法

???? 這里重點介紹基于監督學習(supervised learning)的包裝器的歸納(Wrapper induction)和基于非監督學習(unsupervised learning)的全自動抽取(Automatic extraction)。[5]

???? 3.1 包裝器的歸納

???? 包裝器的歸納是基于監督學習的方法。具體地講，是利用機器學習生成抽取規則。主要步驟如下：

?????(1) 由用戶在訓練頁面中標注要抽取的內容；

???? (2) 系統從訓練頁面中學習出抽取規則；

???? (3) 利用抽取規則從新頁面中抽取出需要的內容。

???? ?研究人員已經研發出很多包裝器歸納系統，例如WIEN[6]，Softmealy[7]，Stalker[8]，BWI[9]，WL[10]等。在這里，我們以系統Stalker作為例子介紹包裝器的歸納方法。Fetch是系統Stalke的商業版本。

???? Stalker是一個分級包裝器歸納系統。基于分級抽取的思想，它將復雜的抽取問題變成一系列簡單的抽取子任務，不同級別的抽取相互獨立。該系統非常適合抽取多層嵌套結構的數據記錄。

???? Stalker在抽取過程中使用了內嵌目錄樹結構，即EC樹(Embedded catalog tree)。EC樹基于類型樹(Type tree)。圖6為一個網頁片段，圖7為圖6對應的類型樹，圖8為圖6對應的EC樹。

?

???? 圖6 一個網頁片段[5]

?

?

????圖7 圖6對應的類型樹[5]

?

?

?

圖8 圖6對應的EC樹[5]

????

?

?????如圖8所示，每個抽取項對應EC樹中的一個節點，包裝器將使用規則從該節點的父節點中將該項內容抽取出來。對每項要抽取的內容，需要兩條規則：

????(1) 一條開始規則，用于檢測抽取項的開始位置，即標識出抽取項對應節點的開始位置；

????(2) 一條結束規則，用于檢測抽取項的結束位置，即標識出抽取項對應節點的結束位置。

????以上規則不僅適用于葉子節點(對應數據項)，還適用于列表節點。對于列表節點，使用列表迭代規則將列表分割成一個個單獨的數據記錄。抽取操作之前，往往把HTML代碼切分成若干個標記(token)。標記的定義一般是指標簽、文本等，例如?

即為一個標記。抽取過程往往以標記作為原子單位加以操作。抽取規則基于路標(landmark)的思想，每個路標是一個連續的標記序列。用路標來定位一個抽取項的開始和結束位置。下面舉個例子來簡要說明抽取過程。圖9為圖6對應的HTML代碼。

?

?

?圖9 圖6對應的HTML代碼[5]

?

????我們要抽取restaurant 的名稱“Good Noodles”，可以使用以下兩條規則：

????R1: SkipTo() //開始規則

???R2: SkipTo()?//結束規則

????R1告訴系統，要找到restaurant的開始路標(landmark)，需要從頁面對應的HTML代碼的第一個標記(token)開始，跳過所有標記，直到遇到標記。在這里，標記就稱為一個路標(landmark)。同樣的，R2告訴系統，要找到restaurant的結束路標，需要從頁面對應的HTML代碼的第一個標記開始，跳過所有標記，直到遇到標記，標記也為一個路標(landmark)。
??
????這里需要注意的是，規則可能不是唯一的。例如，下面的規則R3、R4和規則R1的效果是一樣的。

?????? R3: SkiptTo(Name _Punctuation_ _HtmlTag_)

????? ?R4: SkiptTo(Name) SkipTo()?
????R3表示需要跳過所有標記，直到遇到詞“Name”，且該詞之后緊跟著一個標點符號以及一個HTML標簽(tag)。這里“Name _Punctuation_ _HtmlTag_”共同組成了一個路標。其中“_Punctuation_”和“_HtmlTag_”是通配符。

????接下來我們抽取圖6中的列表，其父節點對應圖9中代碼的第2行至第5行。為了識別整個列表，我們使用如下規則：

????R5:?????SkipTo(

)

????R6:?????SkipTo(

)?

?

????為了將列表分割成一個個單獨的數據記錄，我們使用如下規則：

????R7:?????SkipTo(?

• )?
  

  ?

  
  

  ????R8:?????SkipTo(

)
????系統在列表的父節點對應的代碼中，從第一個標記開始搜索，直到遇到標記?

• ，意味著找到了第一個數據記錄的起始位置，然后接著搜索，直到再次遇到標記?
  
• ，意味著找到了第二個數據記錄的起始位置，…，直到代碼結束。同樣的，系統在列表的父節點對應的代碼中，從最后一個標記開始搜索，直到遇到標記(

)，意味著找到了最后一個數據記錄的結束位置，然后接著搜索，直到再次遇到標記()，意味著找到了倒數第二個數據記錄的結束位置，…，直到代碼開始。當一條數據記錄的開始、結束位置被標出后，我們就能抽取其中的數據了。以上所有規則僅僅為了展示抽取過程，所以看起來比較簡單。實際環境中，由于網頁設計的多樣性，導致規則會比較復雜。

????Stalker使用連續覆蓋的策略來學習抽取規則，即在訓練過程中覆蓋盡可能多的正例，而忽略所有反例。具體地講，就是一旦一個正例滿足了一條規則，該正例就被剔出訓練集，直到所有的正例被規則覆蓋。

???? ??包裝器的歸納需要在學習階段，手工標引訓練例子。為了保證學習的準確性，需要大量的訓練例子，因此標引工作相當費時費力。可以使用協同測試(Co-testing)等方法提高學習過程的自動化程度。

???????包裝器的歸納還需要處理包裝器的維護問題。具體地講，就是如何解決如下難題：

????(1) 包裝器的檢測：當一個網站發生了變化，相應的包裝器能否知道這種變化？

????? ?(2) 包裝器的修復：當網站的變化被正確檢測到，怎樣自動修復包裝器？

????? ?解決以上兩個問題的方法之一就是學習出要抽取內容的特征模板，用這些模板監控抽取操作，及時判斷抽取結果的正確與否。一旦發現錯誤，當頁面僅僅是格式上的較小變化時，可以用模板來定位抽取項，并重新生成包裝器。解決好以上兩個問題相當困難，因為往往需要上下文和語義信息來檢測網站的變化，以及重新定位要抽取內容的位置。目前，包裝器的維護是比較熱門的研究點。

??????3.2 全自動抽取

????? 基于監督學習的包裝器歸納方法有以下兩大不足：

????? (1) 手工標引的高代價，使得該方法不適合應用于大規模網站的抽取。

???? ??(2) 包裝器的維護也需要付出相當大的代價。網絡是個動態環境，處在不停的變化中。由于包裝器歸納系統學習出的規則使用的是格式化標簽，因此當一個網站改變其格式化模板時，當前的抽取規則就無效了。

??? ???針對以上不足，大家開始研究基于非監督學習的全自動抽取。實現全自動抽取是可能的，這是因為一個網站中的數據記錄，往往被數量很少的固定模板所承載著，因此通過挖掘重復模式，是可以找到這些模板的。正則表達式(Regular expression)常被用來描述模板。給定一個正則表達式，可以用一個非確定有限自動機(nondeterministic finite-state automaton)在網頁對應的HTML代碼(可看成一個字符串序列)中作匹配，抽取出數據記錄。模板也可用字符串或樹模式描述。
?
???? 近來比較流行的全自動抽取方法有RoadRunner[11]、MDR[12]等。方法RoadRunner將多個HTML文件作比較，找出其相似特征和不同特征，基于這些特征生成包裝器。參考文獻[12]，我們在這里簡要介紹方法MDR(Mining Data Records in Web pages)的思路。

???? MDR的目標是從網頁中抽取結構化數據記錄，例如圖10所示產品列表。?

?

?

圖10 結構化數據記錄舉例[12]

?

? 圖11 圖10對應的標簽樹[12]

????

????方法MDR用標簽樹(DOM tree 或 tag tree)來描述模板。圖10對應的標簽樹如圖11所示(忽略了一些細節)。MDR的思路基于以下兩個觀察結果，以及串匹配算法：

????(1) 一組相似的結構化數據記錄可以看成一個相似對象的集合，這些對象在頁面中常被放在一片鄰近的區域中，該區域稱為數據區域(data region)，且承載每個對象的HTML標簽是相似的。例如，圖10中兩條關于書的記錄在網頁中被放置在一片鄰近的區域中，且每條數據記錄都被相似的HTML標簽序列所承載著。如果把一個頁面的HTML標簽看成是一個字符串，那么就能夠使用字符串匹配算法來比較不同的子串，從而找出那些相似子串，這些相似子串很可能就承載了相似的對象(即數據記錄)。

????(2) 一個網頁中的HMTL標簽的內嵌結構很自然地構成一棵標簽樹。在一片特定區域中的一組相似的數據記錄，在標簽樹中表現為共同擁有一個父節點。例如，圖11中每個短線方框代表了一條記錄。可見，每條數據記錄由5個TR節點及其子樹所承載，且這5個TR節點及其子樹共同擁有一個父節點TBODY。也就是說，每個數據記錄都被一些子樹所承載著，對于一組相似的數據記錄，承載它們的子樹共同擁有一個父節點。

????以上觀察結果在實驗中得到了證實。給定一個網頁，MDR方法的抽取流程如下：

????步驟1：為數據頁面建立HTML標簽樹；

????步驟2：基于標簽樹和字符串比較算法挖掘出頁面中的數據區域。注意，這里并不是直接去挖掘數據記錄，而是先挖掘出數據區域。例如，我們先找出圖11中節點TBODY下的整個數據區域。

????步驟3：從每個數據區域中識別出數據記錄。例如，在圖11中，這個步驟要找出TBODY下的數據區域中的數據記錄1和數據記錄2。

????3.3 小結

????基于監督學習的包裝器的歸納有如下優點：

????(1) 因為用戶在手工標引時，明確描述了其感興趣的抽取內容，所以抽取結果必定是用戶所需要的。

????(2) 因為用戶在手工標引時，明確描述了從不同網站獲取的數據的意義，所以抽取操作不需要考慮數據集成問題。

????同時，在上節提到，包裝器的歸納有以下兩大不足：

????(1) 手工標引代價高，使得該方法不適合大規模網站的抽取。

????(2) 網站的頻繁變化，使得包裝器的維護需要付出相當大的代價。

????基于非監督學習的自動抽取有如下優點：

????(1) 由于抽取過程是完全自動的，所以非常適用于大規模網站的抽取需求。

????(2) 由于抽取過程是完全自動的，所以維護代價非常小。

????同時，自動抽取有如下不足：

????? ?(1) 由于沒有用戶參與，所以系統并不知道用戶真正感興趣的是什么內容，導致抽取結果中可能會包含很多用戶不需要的數據。對這點不足，可以用領域啟發式信息或手工過濾的方法從抽取結果中剔除無關數據。

????(2) 從多個網站中抽取出的數據結果需要通過集成操作，才能真正入庫。

????在抽取精度方面，通常認為包裝器的歸納比自動抽取精確，但至今并沒有文獻給出具體比較結果。在應用方面，包裝器的歸納往往適合于要抽取的網站數量較少，且這些網站的模板數量較少的任務；自動抽取往往適合大規模的抽取任務，且這些任務不需要精確標引和數據集成。
?

4???? 結論

????當前，不良網絡文化問題已經引起了高度重視。為了打擊網絡灰色文化，不僅需要制定相關的法律法規，還應該充分利用高科技手段。搜索引擎是互聯網上不可或缺的工具和基礎應用之一。對于搜索引擎服務商來說，需要采取各種有效措施嚴格封堵過濾網絡上的不良內容，從而有效的抵制網絡不良文化。本文針對搜索引擎技術中的網絡信息抽取技術做了概要性介紹。因為網絡信息抽取結果的質量，會直接影響到搜索引擎封堵過濾網絡不良內容的效率，因此，研究網絡信息抽取技術對于解決不良網絡文化問題是非常關鍵的。

?

參考文獻
??[1] 中國互聯網絡信息中心 (CNNIC).中國互聯網絡發展狀況統計報告.2008.1.17.

??[2] 郭新建.警惕不良文化.鄭州日報,2007.7.15.

??[3] B.Liu. ACM SIGKDD Inaugural Webcast: Web Content Mining, Nov 29, 2006.

??[4] A. Laender, B. Ribeiro-Neto, A. Silva, and J. Teixeira. A brief survey of web data extraction tools. ACM SIGMOD Record, 31(2):84–93, 2002.

??[5] B. Liu. Web Data Mining - Exploring Hyperlinks, Contents, and Usage Data. Springer, December, 2006.

??[6] N. Kushmerick, D. S. Weld, and R. B. Doorenbos. Wrapper induction for information extraction. In Proc. of the Int. Joint Conf. on Artificial Intelligence, 1997.

??[7] C. Hsu and M. Dung. Generating finite-state transducers for semi-structured data extraction from the web. Information Systems, 23(8):521–538, 1998.

??[8] I. Muslea, S. Minton, and C. Knoblock. A hierarchical approach to wrapper induction. In Proc. of the Third Int. Conf. on Autonomous Agents, 1999.

??[9] D., Freitag and N., Kushmerick. Boosted wrapper induction. In Proc. of the Conf. on Artificial Intelligence, 2000.

??[10] W. Cohen, M. Hurst, and L. Jensen. A flexible learning system for wrapping tables and lists in html documents. In Proc. of the 11th Int. World Wide Web Conf., 2002.

??[11] V. Crescenzi, G. Mecca, and P. Merialdo. Roadrunner: Towards automatic data extraction from large web sites. In Proc. of 27th Int. Conf. on Very Large Data Bases, 2001.

??[12] B. Liu, R. Grossman, and Y. Zhai. Mining data records from web pages. In Proc. of 14th ACM SIGKDD Int. Conf. on Knowledge Discovery in Databases and Data Mining, 2003.

??[13] Y. Zhai and B. Liu. Web data extraction based on partial tree alignment. In Proc. of the 14th Int. World Wide Web Conf., 2005.

??[14] B. Liu and Y. Zhai. Net - a system for extracting web data from flat and nested data records. In Proc. of the 6th Int. Conf. on Web Information Systems Engineering, 2005.

總結

以上是生活随笔為你收集整理的应对不良网络文化的技术之一——网络信息抽取技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。