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

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


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


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