肝胆双清颗粒哪里卖:基于标签路径聚类的文本信息抽取算法

1、 网页预处理

可以通过以下3 个预处理规则来过滤网页中的不可见噪声和部分可见噪声：

1. 仅删除标签本身；
2. 删除标签本身及其相应的起始与结束标签包含的HTML 文本；
3. 对HTML 标签进行修正和配对，删除源码中的乱码。

2、区域噪音的处理

为了实现网页的导航，显示用户阅读的相关信息，并帮助用户实现快速跳转到其他页面，网页中一般要设计列表信息，把提供指向权威页面链接集合的一个或多个Web 页面称为HUB 页面，如图1 所示。

在处理此类信息时，本文设计了2 个噪音识别参数。Length=Length(content)为…标签内纯文本信息的长度，设定字符的ASCII code>255?length+2:length+1。

其中， Cn 为列表噪音判定系数；Nstring  是块中非链接字符的字数；Nlink  是块中链接字符的字数；NODEhref  是块中有href属性的节点数；NODEnohref 是块中没有href 属性的节点数。

3、基于标签路径聚类的网页分割

网页分割算法基于启发式规则，算法分为2 步：(1)Xpath聚类；(2)对聚类的Xpath 进行分割。本文约定DOM 树的叶节点按照其在原始HTML 文件中出现的先后顺序编号。

(1)Xpath 聚类。对具有最大相似度的叶节点进行聚类。节点取得最大相似度时2 个节点Xpath 完全相同。本文用向量,1 ,2 , }表示第i 个Xpath 的聚类。其中，xi, j 表示第i 个Xpath 聚类中的第j 个叶节点。

定义节点间距为1 个Xpath 聚类中2 个节点编号之间的间隔。

式(2)表示第i 个Xpath 聚类的第j 个与第k 个节点之间的编号间隔。

定义平均周期为一个Xpath 聚类中相邻节点间距的均值。

定义间距方差为考察一个聚类中各个节点离散程度的量。

(2)分割点，将一个聚类中的不连续点称为分割点。为了反映分割点的具体位置定义了一个变量θ ，它是前后2 个间隔之间的比值。

为了增强分割鲁棒性，为θ 设定一个阈值范围。实验表明当θ ∈[0.85,2] 时可以得到较好的分割效果。

算法采用如下启发式规则：

(1)如果θ ∉[0.85,2] ，则将向量i X 在分割点处分割开。

(2)如果一个向量的平均周期ΔT > PreSpan，且没有进行分割，节点数目大于预定义值，则认为已经到达网页内嵌块聚类的边界。

4 、算法描述

4.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))
{XpathClusfer.xpath.Insert(node);}
Else
{XpathCluster.Insert(xpath);
XpathCluster.xpath.Insert(node);
}
}
Return XpathCluster;
}

由于在聚类过程中，可能将非正文信息聚类到正文信息类中，因此先分析其方差。若一个聚类中的方差很大，则定位到分割点，将目标正文信息块与其周围的分隔噪音块分割开。另外，利用文本信息块的聚类平均周期、信息
长度和HUB 判别等统计参数帮助定位分割信息条。当第1 个满足全部启发式规则和统计信息的聚类出现时，可以认为已经找到了正文信息块，完成分割任务。

分割算法描述如下：

Input XpathCluster //Xapth 聚类
Output SegBoundary //分割边界
Variables: Integer: Length_Threshold; //正文长度的最小阈值
Float：Cn_ Threshold;// n C 列表噪音判定系数的阈值
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). Cn > Cn_Threshold && ΔT >
Pr eSpan ) //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;
}

4.2 节点集合内的文本抽取算法

节点集合内的文本抽取算法描述如下：

Input SegBoundary[]；//分割出来的符合条件的文本块
Output TextHashMap
//基于HashMap 的文本块模板映射
Variables Integer: Frequency_Threshold; //table/div 嵌套次数的
//阈值
StringBuffer: textChunk; //文本块
For each chunk p in SegBoundary[]
While p has more HTML nodes
nNode=p.nextnode;
If nNode 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

5、阀值的确定

在上述算法中， 需要设定3 个阈值参数： Length_Threshold，Cn_Threshold，Frequency_Threshold，它们对算法的时间复杂度和抽取效果具有一定调节作用，处理网页结构
相似的网页时，可以通过训练样本自适应地算出相应的阈值。

对不同类型网页的阈值，3 个参数的数据分布有较大不同，Length、Cn 的数据分布绝大多数处于较小范围内，这些数据也是需要去掉的噪音数据，因此，使用K-means[4]对样本数据进行聚类处理，而frequency 数据相对前2 个参数没有明显的分布趋势，数据量不大，而且也处在{1-10}这样的一个较窄的局部区间中，实验表明，聚类分析效果不明显，因此，本文用算数平均值求解。

其中，Kmeans(Array[],Cluseternum) 为聚类处理函数，Array[]为处理数据集合，Clusternum 为聚类数目；Min(Array[]) 获取集合最小值。

文章作者：山西工程职业技术学院网络电教中心 刘云峰