基于主题词语义分词与距离的去重算法
2014-09-02陈亚峰郭一帆王峥
陈亚峰++郭一帆++王峥
【摘 要】 对主题网页去重技术进行了综述，结合已有算法的缺点，提出了一种基于主题词语义与距离的网页去重算法。该方法通过对用户输入的关键词进行语义标注后分词检索，计算分词子集在网页文本中的距离，来判断网页与主题的相关度以及网页之间的相似度。同时避开了网页文本向量空间维数大的不足，在一定程度上考虑到了网页的语义信息。
【关键词】 网页去重 语义分词与距离 去重
目前大多数搜索引擎采用基于关键词的方法返回用户所需信息，这些信息的冗余度通常很高，很多不相关的信息没有进行有效的组织。因此人们迫切地希望拥有一种方法，能够自动的将与特定主题相关的信息分类汇总后，供用户查阅。主题搜索引擎的出现使得用户能够对特定主题相关信息的进行获取，然而在信息采集过程中如何对搜索回来的页面进行分类，在下一次信息采集的过程中让爬虫主动发现主题相关页面，并去除相关页面中的重复或近似重复的页面成为搜索引擎的研究热点之一。
1 网页去重技术综述
搜索引擎的工作原理主要分为三个部分：网页抓取，网页处理，提供检索服务。网页去重是搜索引擎预处理技术的关键部分，主要是由于web上存在大量的重复信息，有统计信息表明，网页的重复率平均为4，即用户通过一个URL在互联网上看到一篇相似网页的同时，平均还有三个URL不同的网页给出的内容相同或近似相同。因此为了提高搜索引擎的工作效率，网页去重在整个搜索引擎的工作中是必不可少的。
国外对于网页去重的研究最初主要是针对大型文件系统的近似镜像文档检测算法上的研究，后来这些算法又被拓展应用到数字化图书馆项目以及搜索引擎系统中。美国Arizona大学的研究人员对于大型文件系统中的相似文件采用了计算文档的重叠程度的方法来进行实现。国内，网页去重重点还是对网页去重的算法进行研究。大连理工大学韩冰主要研究了大规模的网页文本去重和科技论文抄袭检测。江苏大学吕霞提出了一种基于关键词和特征码的网页去重K-CC算法，在分析国内外目前比较通用的几种去重技术的基础上，提出了一种基于关键词和特征码的网页去重K-CC算法。
2 基于主题词语义分词与距离的网页去重算法的背景
传统的特征码实现的精确匹配完全可以与先进的检索系统联系起来，其去重效率比较高，是一种去重的好方法。但是该方法的缺点是：
（1）特征码所实现的是精确匹配，并不能有效的检测出转载所造成的近似的重复网页；（2）在没有利用网页文本结构信息的前提下，极有可能会发生长度不同甚至差别悬殊的文本被视为相同网页的情况；（3）作为可以产生特征码的标志的句号有时也并不会在网页文本中出现，也有可能只出现在文章的末尾，或者出现在版权信息和超链接中，而所有这些都会导致特征码产生重大错误。
由于目前大多数搜索引擎是通过关键词匹配来完成用户的检索请求的，考虑到正文文本语义的复杂性我们对关键词的语义进行标注，作为网页检索的主题词，并且利用不同关键词组合的语义及其之间的距离差因素作为评判标准。故提出了一种基于主题词语义分词与距离的网页去重方法。
3 基于主题词语义分词与距离的网页去重算法的背景
把主题词（Ks）按词组形式分成若干个词组的模糊集合S，S中词组的组合必须具有一定语义。然后在给定文本中记录每个词组wi在文本中的位置pi，j，pi，j组成Pi，然后比较所有Pi分量组成的向量的距离差，若距离差L不小于某个值Kd（模糊评判标准阀值），则与主题相关，若小于Kd，则与主题无关。在不大于Kd中，若L在某个区间[a，b]（此区间是认定为重复置信区间），若在此区间，则认定为重复，否则认定为不同类。具体模型和方法如下：
（1）设主题词为Ks
（2）Ks分拆的模糊集合S为：
S={w1，w2，…，wm}
（3）wi在文本中出现位置的向量：Pi=（pi，1，pi，2，…，pi，k），1≤i≤m，ki∈N
若：wi在文本中没有出现，则Pi=
（4）语义位置向量V={vi︱vj=（pi，j1，p2，j2，…，pm，jm），1≤jj≤ki}
注：若Pi=，则pi，ji不记入向量中。
（5）计算V中每个向量分量差分集合D={di︱dj=△vj=（pi，j-pi-1，ji-1）}
（6）根据D中的值来判断主题是否相关，包括不相关、相关（包括重复（强相关）或不同类（弱相关））。
4 相关性判别方法
判别指标用下式表示：
r=∩pi
若r=则不相关，否则相关。也可以用向量空间V的维数r=Dim（V））来判别，若r 重复性判别方法：在相关的情况下，判别主题内容是否接近或相同。 首先记： 该式表明模糊集S中前m-1个词的长度总合。 （1）若两文本（S1，S2）内容一样，则两个D1=D2应相同。（2）若一个文本S1包含另一文本S2，则D1D2。 注：这里的包含关系不是di∈D2，则d i∈D1，而是d i∈D2，要么di∈D1，要么di与D1中的某个dj相差的值小于主观认定的某个值Kd。把置信区间[a，b]置为[1，L]，则Kd∈[1， L]可以认为主题的语义相同，可以去重，否则认为不同即不同类。一般取L=Kd，否则，视查询文本复杂度主观设定。 通过下面例子对算法进行具体的说明：用户输入关键词“郑州游览区”，得到如下四段网页文本，用模糊搜索集合S{}表示为：S{郑州，黄河，游览区}。对应的标记集合中的各元素为：郑州—>w1，黄河—>w2，游览区—>w3。 文档A：“黄河游览区位于郑州市北郊的黄河游览区是20世纪70年代才在黄河之滨在荒山上开始建设的著名风景游览区，到20世纪80年代中期，它已有了相当的规模，不仅成为郑州市最重要的游览区，而且成为驰名中外的华夏历史文化纪念地。”例子中：
P1={8，73}
P2={1，13}
P3={3，15，45，80}
V={（8，1，3）；（8，1，15）；（8，1，45）；（8，1，80）；（ 8，13，3）；（8，13，15）；
（8，13，45）；（8，13，80）；（73，1，3）；（73，1，15）；（73，1，45）；（73，1，80）；
（73，13，3）；（73，13，15）；（73，13，45）；（73，13，80）；}
DA={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}
文档 B：“桃花峪黄河特大桥工程北起郑焦晋高速公路，南接郑州西南绕城高速公路，途经焦作武陟县、郑州荥阳市，全长28.64公里。其中，黄河特大桥长7.69公里，北连接线长8.92公里，南连接线长12.02公里。主桥位于郑州黄河风景区西侧桃花峪村附近，北望嘉应观、跨御坝，南临汉霸二王城，跨黄河中下游分界线桃花峪，俯瞰黄河游览区。大桥建成后将为沿黄风景名胜旅游发展提供便利，成为桃花峪综合旅游的基础性工程和新的景观线”。
P1={23，42，89}
P2={4，57，91，124，138}
P3={140}
文档C：“本网独家现场连线人民网河南视窗记者辛静表示，北京时间15时48分，郑州发生了日偏食现象，通过观测眼镜可以清晰看到太阳被吞噬掉一个小边。记者所在的郑州黄河游览区观测点聚集了上百名群众，大家都得到了相关机构免费派发的专业观测眼镜，并且很专注的在欣赏着日偏食景观，群众们的心情都十分激动”。
P1={32，71}
P2={73}
P3={75}
文档D：“位于郑州市北郊的黄河游览区是20世纪70年代才在黄河之滨在荒山上开始建设的著名风景游览区，到20世纪80年代中期，它已有了相当的规模，成为郑州市最重要的游览区。”
P1={3}
P2={9}
P3={11，40，73}
在上面的例子中分别得到了文档A、B、C、D中模糊集合S中出现元素的位置集合和语义位置向量集合V的值。由公式计算得到向量分量差分集合：
D1={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}
D2=（155，115，117，107，117，174，98，98，98，98，221，115，51，51）
D3={43，4}
D4={8，37，70}
置信区间为[1，4]。
分析D4，D4中37，70在D1中出现，8与D1中的7、9差1，在置信区间内，可以去重，而D4中任何元素与D2中元素差都不在置信区间内，可以认为不同类；D4维数与D3维数不同可以认为不同类，也可看出元素差不在置信区间内，认为不同类。
依次类推，D1，D2，D3，属于不同类。
5 结语
提出的一种基于主题词语义与距离的网页去重算法，通过对用户输入的关键词进行语义标注后分词检索，计算分词子集在网页文本中的距离，来判断网页与主题的相关度以及网页之间的相似度。该方法避开了网页文本向量空间维数大的不足，并在一定程度上充分考虑到了网页的语义信息。
参考文献：
[1]樊小超.基于机器学习的中文文本主题分类及情感分类研究[D].南京：南京理工大学，2014.
[2]何佳.基于社会化标注的网页搜索算法综述[J].小型微型计算机系统，2014（06）.endprint
P1={8，73}
P2={1，13}
P3={3，15，45，80}
V={（8，1，3）；（8，1，15）；（8，1，45）；（8，1，80）；（ 8，13，3）；（8，13，15）；
（8，13，45）；（8，13，80）；（73，1，3）；（73，1，15）；（73，1，45）；（73，1，80）；
（73，13，3）；（73，13，15）；（73，13，45）；（73，13，80）；}
DA={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}
文档 B：“桃花峪黄河特大桥工程北起郑焦晋高速公路，南接郑州西南绕城高速公路，途经焦作武陟县、郑州荥阳市，全长28.64公里。其中，黄河特大桥长7.69公里，北连接线长8.92公里，南连接线长12.02公里。主桥位于郑州黄河风景区西侧桃花峪村附近，北望嘉应观、跨御坝，南临汉霸二王城，跨黄河中下游分界线桃花峪，俯瞰黄河游览区。大桥建成后将为沿黄风景名胜旅游发展提供便利，成为桃花峪综合旅游的基础性工程和新的景观线”。
P1={23，42，89}
P2={4，57，91，124，138}
P3={140}
文档C：“本网独家现场连线人民网河南视窗记者辛静表示，北京时间15时48分，郑州发生了日偏食现象，通过观测眼镜可以清晰看到太阳被吞噬掉一个小边。记者所在的郑州黄河游览区观测点聚集了上百名群众，大家都得到了相关机构免费派发的专业观测眼镜，并且很专注的在欣赏着日偏食景观，群众们的心情都十分激动”。
P1={32，71}
P2={73}
P3={75}
文档D：“位于郑州市北郊的黄河游览区是20世纪70年代才在黄河之滨在荒山上开始建设的著名风景游览区，到20世纪80年代中期，它已有了相当的规模，成为郑州市最重要的游览区。”
P1={3}
P2={9}
P3={11，40，73}
在上面的例子中分别得到了文档A、B、C、D中模糊集合S中出现元素的位置集合和语义位置向量集合V的值。由公式计算得到向量分量差分集合：
D1={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}
D2=（155，115，117，107，117，174，98，98，98，98，221，115，51，51）
D3={43，4}
D4={8，37，70}
置信区间为[1，4]。
分析D4，D4中37，70在D1中出现，8与D1中的7、9差1，在置信区间内，可以去重，而D4中任何元素与D2中元素差都不在置信区间内，可以认为不同类；D4维数与D3维数不同可以认为不同类，也可看出元素差不在置信区间内，认为不同类。
依次类推，D1，D2，D3，属于不同类。
5 结语
提出的一种基于主题词语义与距离的网页去重算法，通过对用户输入的关键词进行语义标注后分词检索，计算分词子集在网页文本中的距离，来判断网页与主题的相关度以及网页之间的相似度。该方法避开了网页文本向量空间维数大的不足，并在一定程度上充分考虑到了网页的语义信息。
参考文献：
[1]樊小超.基于机器学习的中文文本主题分类及情感分类研究[D].南京：南京理工大学，2014.
[2]何佳.基于社会化标注的网页搜索算法综述[J].小型微型计算机系统，2014（06）.endprint
P1={8，73}
P2={1，13}
P3={3，15，45，80}
V={（8，1，3）；（8，1，15）；（8，1，45）；（8，1，80）；（ 8，13，3）；（8，13，15）；
（8，13，45）；（8，13，80）；（73，1，3）；（73，1，15）；（73，1，45）；（73，1，80）；
（73，13，3）；（73，13，15）；（73，13，45）；（73，13，80）；}
DA={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}
文档 B：“桃花峪黄河特大桥工程北起郑焦晋高速公路，南接郑州西南绕城高速公路，途经焦作武陟县、郑州荥阳市，全长28.64公里。其中，黄河特大桥长7.69公里，北连接线长8.92公里，南连接线长12.02公里。主桥位于郑州黄河风景区西侧桃花峪村附近，北望嘉应观、跨御坝，南临汉霸二王城，跨黄河中下游分界线桃花峪，俯瞰黄河游览区。大桥建成后将为沿黄风景名胜旅游发展提供便利，成为桃花峪综合旅游的基础性工程和新的景观线”。
P1={23，42，89}
P2={4，57，91，124，138}
P3={140}
文档C：“本网独家现场连线人民网河南视窗记者辛静表示，北京时间15时48分，郑州发生了日偏食现象，通过观测眼镜可以清晰看到太阳被吞噬掉一个小边。记者所在的郑州黄河游览区观测点聚集了上百名群众，大家都得到了相关机构免费派发的专业观测眼镜，并且很专注的在欣赏着日偏食景观，群众们的心情都十分激动”。
P1={32，71}
P2={73}
P3={75}
文档D：“位于郑州市北郊的黄河游览区是20世纪70年代才在黄河之滨在荒山上开始建设的著名风景游览区，到20世纪80年代中期，它已有了相当的规模，成为郑州市最重要的游览区。”
P1={3}
P2={9}
P3={11，40，73}
在上面的例子中分别得到了文档A、B、C、D中模糊集合S中出现元素的位置集合和语义位置向量集合V的值。由公式计算得到向量分量差分集合：
D1={9，21，51，86，15，7，37，73，74，86，116，151，70，62，92，127}
D2=（155，115，117，107，117，174，98，98，98，98，221，115，51，51）
D3={43，4}
D4={8，37，70}
置信区间为[1，4]。
分析D4，D4中37，70在D1中出现，8与D1中的7、9差1，在置信区间内，可以去重，而D4中任何元素与D2中元素差都不在置信区间内，可以认为不同类；D4维数与D3维数不同可以认为不同类，也可看出元素差不在置信区间内，认为不同类。
依次类推，D1，D2，D3，属于不同类。
5 结语
提出的一种基于主题词语义与距离的网页去重算法，通过对用户输入的关键词进行语义标注后分词检索，计算分词子集在网页文本中的距离，来判断网页与主题的相关度以及网页之间的相似度。该方法避开了网页文本向量空间维数大的不足，并在一定程度上充分考虑到了网页的语义信息。
参考文献：
[1]樊小超.基于机器学习的中文文本主题分类及情感分类研究[D].南京：南京理工大学，2014.
[2]何佳.基于社会化标注的网页搜索算法综述[J].小型微型计算机系统，2014（06）.endprint
