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

　信息抽取IE(Information Extraction)是一種直接從自然語(yǔ)言文本中抽取事實(shí)信息,，并以結(jié)構(gòu)化的形式描述信息的過(guò)程,。通常被抽取出的信息以結(jié)構(gòu)化的形式存入數(shù)據(jù)庫(kù)中，可進(jìn)一步用于信息查詢,、文本深層挖掘,、Web數(shù)據(jù)分析、自動(dòng)問(wèn)題回答等,。Web頁(yè)面所表達(dá)的主要信息通常隱藏在大量無(wú)關(guān)的結(jié)構(gòu)和文字中,，這使得對(duì)Web文檔進(jìn)行信息抽取十分困難。一般的網(wǎng)頁(yè)內(nèi)容包括兩部分，一部分是網(wǎng)頁(yè)的主題信息,，如一張新聞網(wǎng)頁(yè)的新聞標(biāo)題,、新聞?wù)摹l(fā)布時(shí)間,、新聞來(lái)源,；另一部分是與主題無(wú)關(guān)的內(nèi)容，如廣告信息,、導(dǎo)航條,，也稱(chēng)為噪聲信息。如何有效地消除網(wǎng)頁(yè)噪聲,，提取有價(jià)值的主題信息已成為當(dāng)前信息抽取領(lǐng)域的一個(gè)重要課題[1],。參考文獻(xiàn)[2]提出一種依靠統(tǒng)計(jì)信息，從中文新聞?lì)惥W(wǎng)頁(yè)中抽取正文內(nèi)容的方法,，有一定實(shí)用性,，但適用范圍有限。參考文獻(xiàn)[3]針對(duì)Deep Web信息抽取設(shè)計(jì)了一種新的模板檢測(cè)方法,，并利用檢測(cè)出的模板自動(dòng)從實(shí)例網(wǎng)頁(yè)中抽取數(shù)據(jù),，但只能用于電子商務(wù)網(wǎng)站。參考文獻(xiàn)[4]從網(wǎng)頁(yè)中刪除無(wú)關(guān)部分,，通過(guò)逐步消除噪音尋找源網(wǎng)頁(yè)的結(jié)構(gòu)和內(nèi)容,，但提取結(jié)果不完整。
　考慮以上方法的優(yōu)缺點(diǎn),，本文首先對(duì)網(wǎng)頁(yè)噪音進(jìn)行預(yù)處理,，通過(guò)自動(dòng)訓(xùn)練的閾值和網(wǎng)頁(yè)分割算法快速判定網(wǎng)頁(yè)的關(guān)鍵部分，根據(jù)數(shù)據(jù)塊中的嵌套結(jié)構(gòu)獲取網(wǎng)頁(yè)文本抽取模板,。
1 網(wǎng)頁(yè)預(yù)處理及區(qū)域噪音處理
1.1 網(wǎng)頁(yè)預(yù)處理
　可以通過(guò)以下3個(gè)預(yù)處理規(guī)則來(lái)過(guò)濾網(wǎng)頁(yè)中的不可見(jiàn)噪聲和部分可見(jiàn)噪聲：(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)頁(yè)的導(dǎo)航，顯示用戶閱讀的相關(guān)信息,，并幫助用戶實(shí)現(xiàn)快速跳轉(zhuǎn)到其他頁(yè)面,，網(wǎng)頁(yè)中一般要設(shè)計(jì)列表信息，在處理此類(lèi)信息時(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聚類(lèi)算法
　將一個(gè)目標(biāo)頁(yè)面表示為DOM樹(shù)結(jié)構(gòu),，采用深度優(yōu)先遍歷策略，提取DOM樹(shù)中的每個(gè)葉節(jié)點(diǎn),。對(duì)于每次遍歷的葉節(jié)點(diǎn),，通過(guò)比較其Xpath，將其序號(hào)添加到具有最大相似度的Xpath聚類(lèi)中,。具體算法描述如下：
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；
}
　由于在聚類(lèi)過(guò)程中,，可能將非正文信息聚類(lèi)到正文信息類(lèi)中,，因此先分析其方差。若一個(gè)聚類(lèi)中的方差很大,，則利用式(5)定位到分割點(diǎn),，將目標(biāo)正文信息塊與其周?chē)姆指粼胍魤K分割開(kāi)。另外,，利用文本信息塊的聚類(lèi)平均周期,、信息長(zhǎng)度和HUB判別等統(tǒng)計(jì)參數(shù)，幫助定位分割信息條,。當(dāng)?shù)?個(gè)滿足全部啟發(fā)式規(guī)則和統(tǒng)計(jì)信息的聚類(lèi)出現(xiàn)時(shí),，可以認(rèn)為已經(jīng)找到了正文信息塊，完成分割任務(wù),。分割算法描述如下：
Input XpathCluster //Xapth聚類(lèi)
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[],；//分割出來(lái)的符合條件的文本塊
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)頁(yè)結(jié)構(gòu)相似的網(wǎng)頁(yè)時(shí)，可以通過(guò)訓(xùn)練樣本自適應(yīng)地算出相應(yīng)的閾值,。對(duì)于不同類(lèi)型網(wǎng)頁(yè)的閾值,，3個(gè)參數(shù)的數(shù)據(jù)分布有較大不同，Length,、Bn的數(shù)據(jù)分布絕大多數(shù)處于較小范圍內(nèi),，這些數(shù)據(jù)也是需要去掉的噪音數(shù)據(jù)，因此,，使用K-means[4]對(duì)樣本數(shù)據(jù)進(jìn)行聚類(lèi)處理,，而frequency數(shù)據(jù)相對(duì)前兩個(gè)參數(shù)沒(méi)有明顯的分布趨勢(shì)，數(shù)據(jù)量不大,，而且也處在{1-10}這樣的一個(gè)較窄的局部區(qū)間中,。實(shí)驗(yàn)表明，聚類(lèi)分析效果不明顯,，因此本文用算數(shù)平均值求解,。
　(1)單個(gè)樣本網(wǎng)頁(yè)的閾值訓(xùn)練


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