网页去重的改进算法

王 静 ,刘观宁 ，张钰辉

(1.西安电子科技大学 计算机学院,陕西 西安 710071;2.安徽省技术创新服务中心,安徽 合肥 230001)

随着互联网的高速发展，Web已经成为最大的信息来源。但是如何获取这些Web信息为我所用则是大家面临的共同问题。网页去重是Web网页信息处理的重要环节，只有在对网页的去重基础上才可以准确处理网页中的信息。本文介绍网页的去重算法。

提取出来的网页，有些内容可能很相似，对于这些内容相似的网页没必要保存。针对系统中的人才招聘网页更是必要：一个公司的招聘信息很可能会在数十家招聘网站以及自己公司主页同时发布，所以有必要对这些网页去重。

1 网页的特征表示

词、词组和短语是组成文档的基本元素，在不同内容的文档中各词条出现频率有一定的规律性，不同的特征词条可以区分不同内容的文本。因此可以抽取一些特征词条构成特征矢量，在VSM[1]模型中把 t1,t2,…,tn看成一个N维的坐标系 w1(d),w2(d),…,wn(d)为相应的坐标值,因而文本d被看成是N维空间中的一个规范化特征矢量：V(d)=(t1,w1(d);…;ti,wi(d);…;tn,wn(d);)

对于网页，ti就表示特征词条，wi(d)就是文本d中ti的权值。用这个特征矢量来表示网页文本。在网页表示中，对任一特征而言有两个因素影响特征的权值。一是词在HTML文档中出现的词频，另一个是该词在该文档中出现的位置。词频指的是某一词条在文档中出现的频率，频率越高 (当然不包括那些停用词)则说明该词越重要,越能代表该网页的内容。对于网页的主题包含在之间的词组比在之间的词组更具有代表性。因此本文提出了一种把该词出现的频率以及该词出现的位置相结合的权重计算方法，能够更有效地表示网页。公式如下：

这里α=2,α=3,α=4和α=6都是经过实验得到的。实验结果也证明了此改进算法对网页分类正确率的有效性。

2 网页的特征提取

使用VSM模型表示法时，表示文档的特征向量的维数会达到成百上千。同时，具有代表性的特征以及词汇特征也会很大，并且是冗余的。这种未经处理的文本矢量会给后继的处理工作带来巨大的计算开销。特征提取主要用于排除那些被认为无关或关联性不大的特征。基于VSM常用的特征项提取算法有：词频、信息增益、互信息量[2]及X2统计量[3]等。在中文文本分类中使用较多的是互信息量和X2统计量。

(1)互信息量

互信息是信息论中的概念，它用于度量一个消息中两个信号之间的相互依赖程度。在特征选择领域中人们经常利用它来计算特征t与类别c之间的依赖程度，将特征t与各个类的互信息融合起来作为特征的权重。特征t与第i类的互信息计算公式如下（两个公式等价）：

其中：tk表示任意特征项 (特征词)；ci表示任意类别；g为训练集中所有文本数；P(tk,ci)为tk和ci同时出现的概率（即对于任意一篇文章X,含有特征项tk且文章X属于类别 ci的概率)；P(tk)为文章中出现特征项 tk的概率；P(ci)为文章属于类别ci的概率，类似地不难理解

(3)联合特征提取方法

虽然X2统计量法是目前常用的特征提取方法之一，但该方法仍存在一些缺点，如它提高了在指定类中出现少而在其他类中出现较高的特征的权重以及降低了低频词的权重等。根据公式(3)～(5)，对于指定类中出现频率低而其他类中出现频率高的词语，当P(t，ci)→0，而 P(t)和 P(ci)均不趋向于零，则 P(t，ci)/(P(t)P(ci))→0，于是I(t,c)将趋向于负无穷，故这些词语会被过滤掉。根据式(6),对于有相同 logPr(t|c)的词语来说，低频词的权重将更高，即在多类中普遍出现的高频词的权重将比只在特定类中出现的低频词的权重低。这样就很好地解决了上述问题，所以本文提出一种联合特征提取的方法，该方法综合了X2统计量法和互信息量法,可以获得较好的结果。该方法可以描述为：

其中E1(t,c)是使用X2统计量法得到的特征权重；E2(t,c)为使用互信息量法得到的特征权重。

3 SOM神经网络算法

3.1 向量归一化

向量的归一化是对输入向量进行预处理的第一步。其目的是把所有不同长短和方向的向量变成方向不变、长度为1的单位向量。设：

在网络训练过程开始时，定义获胜节点的邻域节点是为了能使二维输出平面上相邻输出节点对相近的输入模式类做出特别反应。假设本次获胜节点为Nj,它在t时刻的邻域节点用 NEj表示，NEj(t)是包含以 Nj中心而距离不超过某一半径的所有节点。随着训练过程的进行，NEj(t)的半径逐渐减小，最后只包含获胜节点 Nj本身，也就是说在训练的起始阶段不仅对获胜节点做权值调整，而且也对其较大范围内的几何邻节点做相应的调整，随着训练过程的继续进行，与输出节点相连的权向量也越来越接近其代表的模式类。这时，在对获胜节点的权值进行比较细微的调整时，只对其几何邻节点比较近的节点进行相应的调整，直到最后只对获胜节点本身做细微的调整。在训练过程结束后，几何上相近的输出节点所连接的权向量既有联系又有区别，这样，保证了对某一类输入模式获胜节点能够做出最大“响应”，而相邻节点做出“较大”响应。几何上相邻节点代表特征上相近的模式类别。

自组织特征映射学习过程包括描述最佳匹配神经元的选择和描述权矢量的自适应变化过程两部分。SOM输出层通常由两维m×m的网格节点组成，从输入向量到网络输出层的每个节点j的权值向量定义为w，w和xi的维数是相同的，设为d，影射节点的数量从数十个到数千个决定SOM正确性和概化能力。

3.2 Kohonen网络训练算法[4～5]

其算法步聚如下：

(1)权连接初始化：初始化输出层节点j的权值矢量wij时可选随机值，初始值通常要选择小一点。初始化学习率和领域函数时要尽量大一些，对连接输入神经元和输出神经元之间的权系数设定为小的随机数a，一般有0

(2)网络输入模式为:

(3)在SOM迭代训练的每一步，从输入数据集中随机地选择文本向量xi属于实数集,计算xi和som输出层所有节点j的权值向量wij的距离,最匹配的点用d表示,权值向量用wij表示,它是输出层节点中最接近xi的。

(5)在每一步学习中CN的神经元自适应变化而CN外的神经元保持不变，调整输出节点所连接的权值以及几何邻域内节点所连权值为：

式中 η(t)为标量自适应增益，0<η(t)<1,η(t)是单调降函数,它可以是线性指数的或者是与其成反比的形式等，通常选择η(t)=0.9(1-t/1 000)，它与 N(t)都是经验函数。

(6)若还有输入样本数据则t=t+1转到步骤(2)。

网络输出与权值调整竞争学习算法规定，获胜神经元输出为1，其余输出为零。只有获胜神经元才有权调整其权向量j×w，调整后权向量为：

其中，α∈(0,1]为学习率，一般其值随着学习的进展而减小。可以看出，当 j≠j*时，对应神经元的权值得不到调整，其实质是“胜者”对它们进行了抑制，不允许它们兴奋。另外，调整后得到的新向量不再是单位向量，因此需要对调整后的向量重新归一化。步骤（3）完成后回到步骤(1)继续训练，直到学习率α衰减到0。

4 实验结果

采用以上介绍的算法,对一批数量在50～100之间的网页集合进行去重处理，集合中包含了一与此内容完全相同或部分相同的网页，将实验结果与人工判别的结果进了比较，发现重复网页的正确率达到95%以上，出现错误的判断的是由于网页转载时出现错码等现象，有的是两个重复网页的段落排列差异太大。测试结果如图1所示。

本文将SOM的思想和方法引入中文Web文档的聚类问题.探索向用户提供高质量的网页信息具有很强的理论意义和实际价值。但是，这种方法的不足之处是当网络的连接过多、节点数目庞大时其计算量大，需要较长的学习时间。所以对于上述问题，笔者正在研究通过网络剪枝技术，在不增加聚类错误的前提下，剪去多余的连接和节点，降低特征向量空间的维数从而减少计算工作量。

[1]LINSKER R.An application of the principle of maximum information preservation to linear systems[Z].Adv.Neural Inform.Process Systems,1989,1.

[2]JUTTEN C,HERAULT J.Blind separation of sources,Part 1:An adaptive algorithm based on neuromimetic architecture[J].Signal Processing,1991,24:10.

[3]COMMON P.Independent component analysis,a new concept[J].Signal Processing,1994,36:287-314.

[4]TONAZZINI A,BEDINI L,KURUOGLU E E.Blind separation of auto-correlated images from noisy images using mrf models,.in 4th Int.Symp.on ICA and Blind Source Separation,Nara,Japan,2003.

[5]SHULMAN D,HERVE J Y.Regularization of discontinuous flow fields.in Proc.Workshop on Visual Motion,1989:81.86.

[6]BOUMAN C,SAUER K.A generalised gaussian image model for edge-preserving MAP estimation,.IEEE Trans.Image Processing,vol.2,pp.296-310,1993.2704.