CCDet_一种高效的大规模中文重复网页检测方法

来源：论文查重 时间：2019-08-11 14:58:57

摘要 论文查重重复文档检测是信息检索领域中一个非常重要的问题．由于网页结构和内容的复杂性，现有方 法在网页查重上没有达到很好的准确性，且只有少量工作用于处理包含关系网页检测问题；同时，由于 网页数量的巨大，重复网页检测处理时需要考虑大规模数据的并行化算法．提出一种基于句号特征的大 规模重复中文网页检测方法CCDet．CCDet采用了一种基于中文句号特征来完成重复文档的相似性比 对方法，与现有的主要重复网页检测算法相比，CCDet大幅提高了检测具有重复关系网页和具有包含 关系网页的准确性，并拥有较高的检测效率．同时，为了适应大规模新闻网页的查重处理，使用 MapReduce编程框架实现了并行化的CCDet算法，使之能够并行化地进行重复网页检测．实验结果表 明，并行化的CCDet算法具有较好的检测效果和计算性能，并具有良好的可扩展性．
重复文档检测是信息检索领域中一个非常重要 的问题，其中，重复网页检测问题因为网页结构和内 容的多变性显得尤为突出．一般来说，如果文档矗。 和d。内容基本相同，我们就称它们具有重复或者近 似重复关系；如果d。的内容基本是d。内容的子集， 则称盔包含于磊．为表达方便，我们将满足以上2种关系的文档统称为重复文档．目前已有很多算法用于 解决重复网页的检测问题[1‘6]．然而因为特征选择不 当等原因，这些算法在中文的处理上均未能达到很好 的效果，且关于包含关系检测问题的研究依然较少．
图1为2个来自不同网站的新闻网页文档示 例．其中，位于两个页面虚线框中的新闻内容完全相 同，而其余的网页模板文本则几乎完全不同．对于网 页浏览者来说，这两个网页即为重复网页，因为他们 只关心网页的主要内容．同样，图2为2个来自不同 网站的新闻网页，位于2个页面虚线框中的新闻内 容完全相同，与图1不同的是右边虚线框中的内容 是整个网页的新闻内容，而左边虚线框中的内容只 是整个新闻的一部分．对于用户来说，这2个新闻网 页具有包含关系．显然，用户在浏览新闻时不希望同 时看到图1或者图2中的2个新闻网页，因此搜索 引擎需要对这些网页进行查重处理．
随着互联网的不断发展，每天会有大量新的网 页出现在网络上，这些网页中存在着大量的重复信 息，给搜索引擎带来了很多额外的负担和技术困难， 大量冗余的文档数据会大大增加搜索引擎索引数据 处理、存储和查询的开销，也给用户的搜索使用体验 带来很大问题．
重复网页检测的主要问题是如何从大规模网页 中检测出重复的网页，并保证检测的准确性．近年 来，在提高检测准确性方面，许多算法已被相继提出，包括shinglin枣1l，IMatch[引，spotsigs[引，CoDet[引， LsH吲等．在大规模文档检测处理方面，也有许多 研究者展开相关工作，包括Wang等人嘲设计的 MapDupReducer系统、Kathpal等人嘲设计的分布 式重复文档检测系统．
本文提出一种称为CCDet的算法，这种算法基 于中文句号特征，可大幅提高中文新闻网页的查重 准确性．同时本文还基于MapReduce编程框架实现 了CCDet算法的并行化．
本文主要贡献如下：
1)提出一种基于中文句号特征的网页特征提 取和相似性检测方法； 2)提出基于中文句号特征的相似性网页度量 模型，可有效检测重复关系和包含关系的重复网页， 以有效的特征匹配手段和噪音特征过滤手段，大幅 提高查重精度和查重效率； 3)基于以上的文档相似性度量模型，研究实现 了一种有效的重复网页检测过程和方法； 4)研究实现了针对大规模网页检测的并行化 CCDet算法．
1 相关工作
近年来已有许多相关工作用于研究重复网页检 测问题．Broder等人最早提出了shinglin一1’101算法， 通过一个特定的HaSh函数，称为rniT卜谢se independent haShinFll]，将每篇文档Hash到固定长度的桶中，这 样每篇文档都能用固定长度的特征序列来表示而不 影响文档相似度计算．Charikar等人[5]提出了 Random Projection算法，通过将高维的文档特征序列 映射到低维的特征序列．来自Google的Henzinger等 人[23将shingling和Random Projection算法进行了 比较，并最终提出了将两者结合的方法以提高检测 精度．Manku等人[12]在Go091e的网页爬取阶段，利 用Random Projection算法进行网页的查重过滤． Chowdhury等人[43提出了IMatch算法，通过IDF 技术对网页的噪音内容进行过滤．Theobald等人[3] 提出了SpotSigs算法，通过提取英文中的停词特 征，目的也是对网页的噪音内容进行过滤．Indyk等 人[13_14]提出了采用Locality Sensitive Hashing (LSH)技术，在高维空间中快速地进行相似性检 测．随后，LSH的改进算法、Hamming—LSHu副和 LSH—Tree[73等算法被相继提出．由于采用LSH，降 维之后的文档之间能够继续维持Jaccard相似性， 因此，结合LSH的查重技术也被相应地提出． 在包含关系检测方面，CoDet嘲算法的提出旨 在能同时解决重复网页检测和包含关系网页检测问 题．基于上述这些算法，许多研究者提出了相关的应 用研究m。2 3|．然而，由于特征选择不当的原因，这些 方法均未能达到很好的准确性．
针对大数据处理，Wang等人[8]基于PPJoin算 法‘243设计并实现了一个MapDupReducer系统，旨 在高效地处理海量查重数据．Kathpal等人[9]也设计了一种分布式处理查重系统．本文前期工作[253也 提出了一种综合性并行化查重系统，旨在同时提高 查重精度和效率．此外，关于重复文档的聚类∞6七8|， 部分内容重复检测[z9。31]问题也有相关的工作．
本文提出的基于句号特征的查重处理方法 CCDet，大幅提高了中文新闻网页的查重精度．同 时，本文还使用MapReduce[3胡编程框架实现了 CCDet算法，使之能够并行地处理海量数据．
2中文句号特征
特征的选择在查重处理任务中起到了非常关键 的作用，现有的许多算法都在尽可能地从网页中提 取出有利于查重处理任务的特征．IMatch[4]试图基 于IDF技术来提取出网页的正文内容特征，过滤模 板内容特征．SpotSigs[33采用英文中的停词特征，试 图获取只在正文内容中出现的特征．而本文提出的 基于句号特征来区分正文内容和模板内容的方法， 可大大提高查重精度．
2．1 中文句号特征的作用
中文的句号“。”只用于表示某个句子的结束标 志口3I，而英文的句号“．”还可用于表示小数点等标 志[34。．在中文网页的正文部分通常不会出现句号， 因此，中文句号这个特性可以很好地区分中文网页 的正文内容和非正文内容．
图3所示即为图2网页截取下来的非正文内容， 不难发现，这些非正文内容可能会以感叹号或者问号 结尾，但却没有一个句子以句号结尾．这是因为，网页 设计者在设计网站时，为了语气上的表达，在一些重要链接上会增加感叹号或者问号进行强调．但是句 号只用于普通的陈述句表达，因此网页设计者一般 不会在链接后面刻意增加一个句号．这样，对于新闻 网页来说，除了正文内容之外，其他的非正文内容不 大可能出现句号，因此，我们可以利用这个特性来区 分新闻网页的正文内容和非正文内容．
一般来说，如果2个文档具有重复关系或者包 含关系，则这2个文档的绝大部分句子都是相同的， 因为句子是语言中表达相对完整意义的最小单位． 那么如果2个网页文档越相似，则它们提取出来的 句号特征集合就越相似，因此我们可以通过计算句号 特征集合的相似性来衡量网页文档间的重复关系．
2．2句号特征的提取
与spotSigs[33抽取停词特征的方法类似， CCDet采用抽取句号前若干个字符作为这个句号 对应的特征．具体句号特征字串定义如下：
1)将网页中句号前若干个固定长度(比如10 个字)的字符串作为这个句号的特征值抽取出来． 2)如果网页中连续出现的2个句号之间的字 符串长度小于所指定的固定长度，那么取后者到前 者之间的字符作为后者的特征值． 3)如果网页中连续出现的2个句号之间的字 符串长度为o，则忽略后者的特征值．
对于句号特征固定长度值的选择问题，只有当 所提取的特征值能够将2个不同的句子区分开来， 这个特征才有意义．理论上这个值越大，能够区分句 子的能力就越大，但为了减少存储和计算上的开销， 这个值也不宜过大．因此，我们在进行实验时选取固 定长度值为10，这样基本可以保证所提取的句号特 征能够正确区分不同的句子，因为很少会存在2个 句子最后10个字相同，但所要表达的却是完全不同 的意思．
重复网页检测问题一般来说主要有2个任务： 一个是找出主要内容完全重复或者基本重复的网 页，一个是找出主要内容是包含关系的网页．图2即 为主要内容重复的2个网页，其中虚线框部分的内 容是网页的主题内容，其他部分内容均称为网页模 板内容，包括网页广告、网页标题、超链接文本、时间 戳等．而文档包含关系是指2个文档不同，但其中一 个文档的内容是另一个文档的子集，比如一个网站对另一个网站的某篇新闻稿进行剪辑和简报式的报 道，此时被包含的文档在主题内容上保持与原始文 档是一致的，这种包含关系的文档也应被作为重复 文档检测出来．
为了衡量网页之间的重复关系或者包含关系， 传统方法通常基于文本相似性来度量网页的重复关 系，如Jaccard相似性和Cosine相似性，或者基于公 共子序列来度量包含关系，如最长公共子序列LCS 或公共子序列CS．但这些度量模型都比较单一，难 以适应于对不同类型重复文档的有效检测．为了能 够同时得到文本的重复关系和包含关系，又能区分 两者的不同，我们提出一种联合定义重复关系和包 含关系的共性相似性度量模型和方法．假设集合A， B分别为2个文本特征集合，定义公共包含相似性.
其中，Tccs和n￡r分别为CCS和CLR所设置 的判定阈值．对于CCS，如果阈值选择过高，则可能 会减少算法的召回；如果阈值选择过低，则可能会导 致一些误召回，本文将通过分析实验结果来选择合 适的阈值．对于CLR，其阈值的选定并不会对算法 整体的召回率和准确率造成影响，但会对重复网页和包含关系网页的判断造成影响．本文将c己R阈值 设为o．5，这由包含关系文档的定义决定，即如果较 短文档的长度小于较长文档长度的一半，才认为2 个文档具有包含关系．
利用句号特征字串，基于上述所定义的公共包 含相似性度量模型，我们可迸一步对所提取出的网 页主题文本进行重复文档检测处理．为了加速重复 文档检测的处理速度，实际处理大量网页文档的相 似性比对时，并不是两两逐个比较，而是多个文档同 时进行计算和处理．
图4即为计算多个文档相似度的处理过程， 图4中d。表示一个网页文档标识号，￡：表示一个特 定的句号特征字串．多文档相似度计算主要分为以 下3个步骤：
步骤1．为所有待比较的网页主题文本建立句 号特征倒排索引，如果某个句号特征字串在某些文本中出现，则将这些文本信息链接到同一链表中，并 以句号特征字串为链表的表头．同时文本信息中要 包含该文本所拥有的句号特征个数，以便最后进行相 似度的计算，这一步得到图4中(2)所示数据结构． 步骤2．将同一个链表中的所有文本分别与其 他文本配对并标记为1，每～对标记为1的文本对 表示这2个文本拥有一个相同的句号特征字串，这 一步得到图4中(3)所示数据结构．
步骤3．合并相同的文本对，并将文本对的标记 改为它所出现的次数，这一步得到图4中(4)所示数 据结构．
通过步骤3得到的信息，即可根据CCS和CLR 公式进行计算来判定文本对是否为重复或者包含关 系．如d。和d：的关系可通过如下方式判断：
虽然已经完成了以上的重复文档检测算法和基 本处理过程的设计，但由于在实际的搜索引擎应用 中，每天都会产生大量的新网页，搜索引擎后台处理 系统需要在尽可能短的时间内完成重复文档检测和 过滤处理并更新索引信息，仅仅有以上的串行化算 法是远远无法满足要求的．很显然，在可接受时间内 完成如此巨量的文档检测处理，唯一可行和有效的 办法就是并行化处理．
目前Web海量数据并行化处理最有效的方法 就是G009le公司提出的MapReduce海量数据并行 处理技术[32|．因此，我们将采用Google MapReduce 的开源实现软件Hadoop海量数据分布式存储和并 行处理系统来完成以上整个重复文档检测和过滤算 法的并行化设计和实现．
我们分别进行了2种实验比较：一种是为了验证算法精确性而进行的小样本数据实验，在这个实 验中我们还实现了其他几个经典算法与之比较；另 一种是大数据并行化计算性能实验，主要为了验证 经过并行化后的CCDet算法在处理大数据问题上 的高效性和可扩展性．前者在单机上实现，需要统计 重复网页的个数，数据量有3 000个网页；后者在 Hadoop集群上实现，需要统计算法的运行时间而 无须统计重复网页个数，数据量有200万个网页． 图6(a)表示的是SpotSigs用不同的停词列 表做实验得到的最高值．图6(b)表示的是CCDet， SpotSigs，Shin91ing和CoDet算法取不同阈值得到 的结果，其中SpotSigs使用的停词列表是图6(a)中 得到最高值的停词列表．
实验所用数据通过Nutch爬虫工具从不同的 中文新闻网站爬取而来．这些新闻网页的发表均在同一段相隔较近的时间内，以便能够保证有尽量多 的新闻内容是重复的．来自同一个网站的网页会打 上相同的标记，以便在索引剪切阶段使用.
本文主要的工作之一是在算法的运行效率上有 了较大的提高，这也要归功于本文提出的倒排索引 剪切方法．因此，除了准确性上的比较，我们还对各 个算法在单机上的性能进行了比较．图9显示 IMatch以及IMatch的2个改进算法运行时间最 短，当然它们是以牺牲准确性为代价；其次，CCDet 需要花费73 ms的运行时间，而未使用索引剪切算 法的NoPrunel需要花费83 ms的运行时间，使用 了IDF技术的NoPrunel需要花费75 ms的运行时 间，说明索引剪切算法对CCDet的运行效率也起到 了明显的提高作用．除IMatch和CCDet算法之外， 其余的算法运行时间均在270 ms以上.
图10(a)所示为CCDet算法在集群和单机上的 实验对比，图10(b)所示为并行化CCDet算法的运 行时间随着集群节点个数而变化的情况． 为了验证CCDet算法在处理大数据问题上的 有效性和高效性，我们使用MapReduce并行地实现 了CCDet算法．首先，我们测试了在实验数据从 3 ooo个增加到200万个网页的过程中，并行化 CCDet算法和单机算法在运行时间上的对比；其 次，我们还测试了并行化CCDet算法的运行时间随 着集群节点个数变化而变化的情况．
图10(a)显示，一方面并行化的CCDet运行时 间的增加几乎呈直线形式，而单机运行的时间在网 页数据从30万增加到200万时骤然提升；另一方 面，虽然在网页数据低于30万个时，单机运行时间要比集群运行时间短，但是当网页数据增加到200 万个时，集群的运行时间要比单机运行时间短得多． 图10(b)显示随着集群结点个数的增加，并行化 CCDet算法的运行时间几乎呈直线下降的趋势，说 明并行化CCDet算法具有较好的可扩展性．
本文提出了一种针对中文网页的重复网页检测 算法——CCDet，能够准确、高效地检测出重复网 页．首先，CCDet算法基于中文句号特征，使用CCS 和CLR相似性度量方法来计算和判定网页之间的 重复性．其次，cCDet算法使用高效的索引剪切手 段，可有效地过滤噪音特征和提高算法运行效率．最 后，为了解决实际应用时大规模网页的快速检测处 理问题，我们基于MapReduce编程框架，设计并实 现了CCDet的并行计算算法和框架，使之能够并行 地处理海量数据．实验结果表明，CCDet算法在检 测结果精度上比现有的检测算法有显著的提高；同 时，并行化后的检测算法可以快速地检测处理大规 模的重复网页，且并行化算法具有很好的可扩展性， 可以很好地应对重复网页数量的增长．
当然，CCDet算法还存在一些不足．一是CCDet 算法只适用于新闻页面的处理，对于普通网页的处 理还不是很好；二是对于同时出现新闻内容和评论 的页面，该算法也难以将评论中的噪音特征去除．

相关文章：提升本科毕业论文选题质量的途径探索