摘 要： 針對網頁非結構化信息抽取復雜度高的問題，提出了一種基于網頁分割的Web信息提取算法。對網頁噪音進行預處理，根據網頁的文檔對象模型樹結構進行標簽路徑聚類，通過自動訓練的閾值和網頁分割算法快速判定網頁的關鍵部分，根據數據塊中的嵌套結構獲取網頁文本提取模板。對不同類型網站的實驗結果表明，該算法運行速度快、準確度高。
關鍵詞： 網頁分割；信息提取；聚類；閾值
信息抽取IE(Information Extraction)是一種直接從自然語言文本中抽取事實信息，并以結構化的形式描述信息的過程。通常被抽取出的信息以結構化的形式存入數據庫中，可進一步用于信息查詢、文本深層挖掘、Web數據分析、自動問題回答等。Web頁面所表達的主要信息通常隱藏在大量無關的結構和文字中，這使得對Web文檔進行信息抽取十分困難。一般的網頁內容包括兩部分，一部分是網頁的主題信息，如一張新聞網頁的新聞標題、新聞正文、發布時間、新聞來源；另一部分是與主題無關的內容，如廣告信息、導航條，也稱為噪聲信息。如何有效地消除網頁噪聲，提取有價值的主題信息已成為當前信息抽取領域的一個重要課題[1]。參考文獻[2]提出一種依靠統計信息，從中文新聞類網頁中抽取正文內容的方法，有一定實用性，但適用范圍有限。參考文獻[3]針對Deep Web信息抽取設計了一種新的模板檢測方法，并利用檢測出的模板自動從實例網頁中抽取數據，但只能用于電子商務網站。參考文獻[4]從網頁中刪除無關部分，通過逐步消除噪音尋找源網頁的結構和內容，但提取結果不完整。
考慮以上方法的優缺點，本文首先對網頁噪音進行預處理，通過自動訓練的閾值和網頁分割算法快速判定網頁的關鍵部分，根據數據塊中的嵌套結構獲取網頁文本抽取模板。
1 網頁預處理及區域噪音處理
1.1 網頁預處理
可以通過以下3個預處理規則來過濾網頁中的不可見噪聲和部分可見噪聲：(1)僅刪除標簽；(2)刪除標簽及起始與結束標簽包含的HTML文本；(3)對HTML標簽進行修正和配對，刪除源碼中的亂碼。
1.2 區域噪音的處理
為了實現網頁的導航，顯示用戶閱讀的相關信息，并幫助用戶實現快速跳轉到其他頁面，網頁中一般要設計列表信息，在處理此類信息時，本文設計了兩個噪音識別參數。
Length=Length(content)為<tag>…</tag>標簽內純文本信息的長度，設定字符的ASCII code>255？length+2：length+1。
3 算法描述
3.1 Xpath聚類算法
將一個目標頁面表示為DOM樹結構，采用深度優先遍歷策略，提取DOM樹中的每個葉節點。對于每次遍歷的葉節點，通過比較其Xpath，將其序號添加到具有最大相似度的Xpath聚類中。具體算法描述如下：
Input DOMTree
Output XpathCluster
Cluster(DOM Tree)
{ XpathCluster =?準；
for each xpath of leaf node
{
if (XpathCluster.xpath.Find(xpath))
{XpathCluster.xpath.Insert(node)；}
else
{XpathCluster.Insert(xpath)；
XpathCluster.xpath.Insert(node)；
}
}
Return XpathCluster；
}
由于在聚類過程中，可能將非正文信息聚類到正文信息類中，因此先分析其方差。若一個聚類中的方差很大，則利用式(5)定位到分割點，將目標正文信息塊與其周圍的分隔噪音塊分割開。另外，利用文本信息塊的聚類平均周期、信息長度和HUB判別等統計參數，幫助定位分割信息條。當第1個滿足全部啟發式規則和統計信息的聚類出現時，可以認為已經找到了正文信息塊，完成分割任務。分割算法描述如下：
Input XpathCluster //Xapth聚類
Output SegBoundary //分割邊界
Variables：Integer：Length_Threshold；
//正文長度的最小閾值
Float：Bn_Threshold；//Bn列表噪音判定系數的閾值
WebPageSeg
{ SegBoundary =?覬；
Count=0；
While(Count!=XpathCluster.size())
{
If(XpathCluster.at(count).var0 is within threshold)
If(xpathCluster.at(count).size()>
//MAXSIZE&&xpathCluster.at(cou
nt).length> Length_Threshold
&& xpathCluster.at(count).Bn>Bn_Threshold && ?駐 T>
PreD ) //check
{SegBoundary.insert(each node within XpathCluster.at(count))
Break；
}
else Count++；
}
}else{//利用啟發式規則(1)進行分割
Detect segment point use(2.3.4)
Sort(new cluser)；
Count++；
}
}
Return SegBoundary；
}
3.2 節點集合內的文本抽取算法
節點集合內的文本抽取算法描述如下：
Input SegBoundary[]；//分割出來的符合條件的文本塊
Output TextHashMap<tagpath，table textchunk，document
//frequency>基于HashMap的文本塊模板映射
Variables Integer： Frequency_Threshold；
//table/div嵌套次數的閾值
StringBuffer： textChunk； //文本塊
For each chunkp in SegBoundary[]
While p has more HTML nodes
nNode=p.nextnode；
ifnNode is not table/div Tag
textChunk=textChunk+extracted text from nNode；
//抽取nNode間的文本信息
else if nNode is table/div Tag
{
if TextHashMap.contains(tagpath)==true
{ documentfrequency++；}
else{
Documentfrequency=1；
}
TextHashMap.put(tagpath，textChunk，documentfrequency)；
}
While TextHashMap has more{tagpath，textChunk，document //frequency}
h is TextHashMap’s item
if document frequency of h≥Frequency_Threshold
Print textChunk of item h
3.3 閾值的確定
在上述算法中，需要設定3個閾值參數：Length_ Threshold、Bn_Threshold、Frequency_Threshold，它們對算法的時間復雜度和抽取效果具有一定調節作用，處理網頁結構相似的網頁時，可以通過訓練樣本自適應地算出相應的閾值。對于不同類型網頁的閾值，3個參數的數據分布有較大不同，Length、Bn的數據分布絕大多數處于較小范圍內，這些數據也是需要去掉的噪音數據，因此，使用K-means[4]對樣本數據進行聚類處理，而frequency數據相對前兩個參數沒有明顯的分布趨勢，數據量不大，而且也處在{1-10}這樣的一個較窄的局部區間中。實驗表明，聚類分析效果不明顯，因此本文用算數平均值求解。
(1)單個樣本網頁的閾值訓練
本文設計一種新的文本抽取算法，該算法采用網頁標簽分割和HTML樹結構，能獲得較高準確度。整個算法簡單實用，前期的去除網頁噪音算法可以讓抽取的網頁正文信息更準確。在未來工作中，可以把該方法與現有中文信息處理技術相結合，如考慮文本信息的相關性以及文本的字體屬性來判斷其重要性。
參考文獻
[1] 歐健文，董守斌，蔡斌.模板化網頁主題信息的提取方法[J].清華大學學報：自然科學版，2005，45(S1)：1743-1747.
[2] 孫承杰，關毅.基于統計的網頁正文信息抽取方法的研究[J].中文信息學報，2004，18(5)：17-22.
[3] Yang Shaohua， Lin Hailue， Han Yanbo. Automatic data extraction from template-generated Web pages[J]. Journal of Software， 2008，19(2)： 209-223.
[4] GUPTA S， KAISER G， NEISTADT D， et al. DOM-based content extraction of HTML documents[C]. Proceedings of the 12th Word Wide Web Conference New York， USA： [s. n.]， 2003.
[5] PELLEG D， BARAS D. K-means with large and noisy constraint sets[C]. Proceedings of the 18th European Conference on Machine Learning. Warsaw， Poland： [s. n.]， 2007.
[6] 于琨，蔡智，糜仲春，等.基于路徑學習的信息自動抽取方法[J].小型微型計算機系統，2003，24(12)：2147-2149.
[7] 周順先.文本信息抽取模型及算法研究[D].長沙：湖南大學，2007.