摘 要：针对网页非结构化信息抽取复杂度高的问题，提出了一种基于网页分割的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)为
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
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.