摘  要： 針對網(wǎng)頁非結(jié)構(gòu)化信息抽取復雜度高的問題，提出了一種基于網(wǎng)頁分割的Web信息提取算法,。對網(wǎng)頁噪音進行預處理,，根據(jù)網(wǎng)頁的文檔對象模型樹結(jié)構(gòu)進行標簽路徑聚類,，通過自動訓練的閾值和網(wǎng)頁分割算法快速判定網(wǎng)頁的關鍵部分，根據(jù)數(shù)據(jù)塊中的嵌套結(jié)構(gòu)獲取網(wǎng)頁文本提取模板,。對不同類型網(wǎng)站的實驗結(jié)果表明,，該算法運行速度快、準確度高,。
關鍵詞： 網(wǎng)頁分割,；信息提取,；聚類；閾值

　信息抽取IE(Information Extraction)是一種直接從自然語言文本中抽取事實信息,，并以結(jié)構(gòu)化的形式描述信息的過程,。通常被抽取出的信息以結(jié)構(gòu)化的形式存入數(shù)據(jù)庫中，可進一步用于信息查詢,、文本深層挖掘,、Web數(shù)據(jù)分析、自動問題回答等,。Web頁面所表達的主要信息通常隱藏在大量無關的結(jié)構(gòu)和文字中,，這使得對Web文檔進行信息抽取十分困難。一般的網(wǎng)頁內(nèi)容包括兩部分,，一部分是網(wǎng)頁的主題信息,，如一張新聞網(wǎng)頁的新聞標題、新聞正文,、發(fā)布時間,、新聞來源；另一部分是與主題無關的內(nèi)容,，如廣告信息,、導航條，也稱為噪聲信息,。如何有效地消除網(wǎng)頁噪聲,，提取有價值的主題信息已成為當前信息抽取領域的一個重要課題[1]。參考文獻[2]提出一種依靠統(tǒng)計信息,，從中文新聞類網(wǎng)頁中抽取正文內(nèi)容的方法,，有一定實用性，但適用范圍有限,。參考文獻[3]針對Deep Web信息抽取設計了一種新的模板檢測方法,，并利用檢測出的模板自動從實例網(wǎng)頁中抽取數(shù)據(jù)，但只能用于電子商務網(wǎng)站,。參考文獻[4]從網(wǎng)頁中刪除無關部分,，通過逐步消除噪音尋找源網(wǎng)頁的結(jié)構(gòu)和內(nèi)容,，但提取結(jié)果不完整。
　考慮以上方法的優(yōu)缺點,，本文首先對網(wǎng)頁噪音進行預處理,，通過自動訓練的閾值和網(wǎng)頁分割算法快速判定網(wǎng)頁的關鍵部分，根據(jù)數(shù)據(jù)塊中的嵌套結(jié)構(gòu)獲取網(wǎng)頁文本抽取模板,。
1 網(wǎng)頁預處理及區(qū)域噪音處理
1.1 網(wǎng)頁預處理
　可以通過以下3個預處理規(guī)則來過濾網(wǎng)頁中的不可見噪聲和部分可見噪聲：(1)僅刪除標簽,；(2)刪除標簽及起始與結(jié)束標簽包含的HTML文本；(3)對HTML標簽進行修正和配對,，刪除源碼中的亂碼,。
1.2 區(qū)域噪音的處理
　為了實現(xiàn)網(wǎng)頁的導航，顯示用戶閱讀的相關信息,，并幫助用戶實現(xiàn)快速跳轉(zhuǎn)到其他頁面,，網(wǎng)頁中一般要設計列表信息，在處理此類信息時,，本文設計了兩個噪音識別參數(shù),。
Length=Length(content)為<tag>…</tag>標簽內(nèi)純文本信息的長度，設定字符的ASCII code>255,？length+2：length+1,。


3 算法描述
3.1 Xpath聚類算法
　將一個目標頁面表示為DOM樹結(jié)構(gòu)，采用深度優(yōu)先遍歷策略,，提取DOM樹中的每個葉節(jié)點,。對于每次遍歷的葉節(jié)點，通過比較其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判別等統(tǒng)計參數(shù),，幫助定位分割信息條,。當?shù)?個滿足全部啟發(fā)式規(guī)則和統(tǒng)計信息的聚類出現(xiàn)時,，可以認為已經(jīng)找到了正文信息塊，完成分割任務,。分割算法描述如下：
Input XpathCluster //Xapth聚類
Output SegBoundary //分割邊界
Variables：Integer：Length_Threshold,；
//正文長度的最小閾值
Float：Bn_Threshold；//Bn列表噪音判定系數(shù)的閾值
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{//利用啟發(fā)式規(guī)則(1)進行分割
Detect segment point use(2.3.4)
Sort(new cluser),；
Count++；
}
}
Return SegBoundary,；
}
3.2 節(jié)點集合內(nèi)的文本抽取算法
　節(jié)點集合內(nèi)的文本抽取算法描述如下：
Input SegBoundary[],；//分割出來的符合條件的文本塊
Output TextHashMap<tagpath，table textchunk,，document
 //frequency>基于HashMap的文本塊模板映射
Variables Integer： Frequency_Threshold；
//table/div嵌套次數(shù)的閾值
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個閾值參數(shù)：Length_ Threshold、Bn_Threshold,、Frequency_Threshold,，它們對算法的時間復雜度和抽取效果具有一定調(diào)節(jié)作用，處理網(wǎng)頁結(jié)構(gòu)相似的網(wǎng)頁時,，可以通過訓練樣本自適應地算出相應的閾值,。對于不同類型網(wǎng)頁的閾值，3個參數(shù)的數(shù)據(jù)分布有較大不同,，Length,、Bn的數(shù)據(jù)分布絕大多數(shù)處于較小范圍內(nèi)，這些數(shù)據(jù)也是需要去掉的噪音數(shù)據(jù),，因此,，使用K-means[4]對樣本數(shù)據(jù)進行聚類處理,，而frequency數(shù)據(jù)相對前兩個參數(shù)沒有明顯的分布趨勢，數(shù)據(jù)量不大,，而且也處在{1-10}這樣的一個較窄的局部區(qū)間中,。實驗表明，聚類分析效果不明顯,，因此本文用算數(shù)平均值求解,。
　(1)單個樣本網(wǎng)頁的閾值訓練


　本文設計一種新的文本抽取算法，該算法采用網(wǎng)頁標簽分割和HTML樹結(jié)構(gòu),，能獲得較高準確度,。整個算法簡單實用，前期的去除網(wǎng)頁噪音算法可以讓抽取的網(wǎng)頁正文信息更準確,。在未來工作中,，可以把該方法與現(xiàn)有中文信息處理技術相結(jié)合，如考慮文本信息的相關性以及文本的字體屬性來判斷其重要性,。
參考文獻
[1] 歐健文,，董守斌，蔡斌.模板化網(wǎng)頁主題信息的提取方法[J].清華大學學報：自然科學版,，2005,，45(S1)：1743-1747.
[2] 孫承杰，關毅.基于統(tǒng)計的網(wǎng)頁正文信息抽取方法的研究[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].小型微型計算機系統(tǒng)，2003,，24(12)：2147-2149.
[7] 周順先.文本信息抽取模型及算法研究[D].長沙：湖南大學,，2007.