[14],两个序列分别为,A = abcabba,B = cbabac。计算得到.doc
《[14],两个序列分别为,A = abcabba,B = cbabac。计算得到.doc》由会员分享,可在线阅读,更多相关《[14],两个序列分别为,A = abcabba,B = cbabac。计算得到.doc(16页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、一种基于一种基于 LCSLCS 的相似网页检测算法的相似网页检测算法黄连恩, 王磊, 李晓明北京大学 网络与分布式系统实验室, 100871报告编号 PKU_CS_NCIS_TR2007012 提交时间 2007-12-20 北京大学 信息科学技术学院 网络与信息系统研究所,100871北京大学信息科学技术学院 网络与信息系统研究所: PKU_CS_NCIS_TR20070121一种基于一种基于 LCSLCS 的相似网页检测算法的相似网页检测算法 黄连恩, 王磊, 李晓明(北京大学 信息科学与技术学院, 100871) 摘要:网页的相似性检测长期以来是一个研究的热点,shingling 和 s
2、imhash 被认为是当前最好的两个算法,然而它们存在着一定的不足:一方面,高的分数意味着高的相似概率,但并不必然意味着高的相似度;另一方面,哈希代码的长度和多样性之间的冲突决定了难以同时获得高的准确率和覆盖率。本文提出了一种新型的相似网页检测算法,同时具备高准确率与高覆盖率的优点。该算法采用基于 LCS(longest common subsequence)的相似性度量方法,它可以更好地度量网页之间的相似度和包含关系,并获得高的准确度。同时,本文设计了一个包含了三个步骤的检测过程框架,以保证算法的效率。综合实验表明本文的算法同时获得了高准确率与高覆盖率并具有较好的效率。该算法成功应用于 4.
3、3 亿文章型网页集合,将其分割为 0.68 亿个相似网页子集,整个过程使用 6 台 Linux服务器仅花费了 5 天的时间。关键词: 相似性检测; 消重; 最长公共子序列; 相似性度量Achieving both High Precision and High Recall in Near-duplicate DetectionHuang Lianen, Wang Lei, Li XiaomingInstitute of Network Computing and Information Systems, Peking UniversityAbstract: To Find near-dupl
4、icate documents, fingerprint-based paradigms such as shingling and simhash have been recognized as effective approaches and are considered the state-of-the-art. Nevertheless, we see two aspects of these approaches which may be improved. First, high score under these algorithms similarity measurement
5、 implies high probability of similarity between documents, which is different from high similarity of the documents. Second, there has to be a tradeoff between hash-code length and hash-code multiplicity in fingerprint paradigms, which makes it hard to maintain a satisfactory recall level while impr
6、oving precision. In this paper we propose a new approache of near-duplicate detection for web pages, which has both merits of high precision and high recall. Technically, our approache is based on LCS (longest common subsequence) measurement, together with a 3-step framework, which is carefully desi
7、gned to ensure high efficiency. A comprehensive experiment was conducted, which shows our method achieves both high precision and high recall. Also, the method has been successfully used to partition a set of 430 million web pages into 68 million subsets of similar pages. The process of partition to
8、ok only 5 days to complete, using a cluster of 6 linux boxes, which demonstrates its effectiveness.Key words: near-duplicate detection; replica detection; longest common subsequence; similarity measurement1.引言引言Web 上相似网页的检测方法长期以来一直都是一个研究的热点。它在很多与 Web 信息相关的 应用中扮演着重要的角色,包括:检索结果的聚类和排序、Web 搜集、信息提取、Spam
9、检测等 此项工作得到国家自然科学基金项目(60573166)与国家 863 计划项目(2007AA01Z100)支持北京大学信息科学技术学院 网络与信息系统研究所: PKU_CS_NCIS_TR20070122等。 正是因为它的重要性,近年来,有很多的方法被提出来并得到评估,其中,Broder 提出的 shingling 算法1和 Charikar 的 simhash 算法2被认为是当今最好的算法。不过这两种算法存在着 一定的不足:它们都是基于哈希匹配的方法来评估两篇文档相似度,而不是基于文档内容的匹 配,高的评估分数意味着高的相似概率,但并不必然意味着高的相似度。两个完全不同内容的网 页,仍
10、然可能被判定为相似的。同时,文献3指出,在基于哈希的相似检测算法中,哈希代码的 长度决定了基于哈希方法的准确度,而多样性(multiplicity)则决定了召回率,两者之间的冲突 决定了无法同时获得高的准确度和召回率。 本文提出了一种基于 LCS(Largest Common Subsequence)的相似网页检测算法,它不同于基 于哈希的方法,能够有效地克服上述两种不足。本文在从 24 亿历史网页中筛选出的 4.3 亿篇文章 型网页上进行了综合的实验,结果表明,本文提出的方法同时获得了高的准确度和召回率。2.相关研究相关研究国际上对文档相似性检测的研究最初主要针对大型文件系统,后来由被扩展应
11、用于搜索引擎 等领域的相似网页检测,如 Stanford 大学的 SCAM 系统。到目前为止许多研究人员在该领域提出 了许多方法,这些方法主要可以从两个方面进行区分:从文档提取文档特征的策略,以及由这些 特征计算文档签名的策略。在第一个方面,shingles 和文档向量是最常采用的特征。Brin 等4在 COPS 系统中以句子为单位来获得 shingles,Broder 等1采用单词粒度上的滑动窗口来获得 shingles。Hoad 5和 Chowdhury 6等分别基于文档向量开发了相似性衡量标准以及利用词典来改 进文档向量;在第二个方面,基于 Shingles 的方法1,7通常利用 方法或
12、者 方法来从它们的特征 中获得文档签名。而 Charikar 的 Simhash 算法和 Chowdhury 等人的 I-match 6算法在文档向量上 计算文档签名。在这些技术中,Broder 的 shingling 算法和 Charikar 的 simhash 算法被认为是代表 了当前的技术发展水平,并已经被用于实际的搜索引擎系统中。Shingling 算法的相关研究Broder 的 Shingling 算法1用两个网页的 resemblance 和 containment 来衡量其相似性。网页 A 和网页 B 的 resemblance 是位于区间0,1中的一个数值,越接近于 1,这两个
13、网页越相似;类似 的,containment 也是位于区间0,1中的一个数值,越接近于 1,说明网页 A 被网页 B 包含的程度 越高。 Schleimer 的 Winnowing 算法8对经典的 shingling 算法做了改进,以期能够检测出两篇网页 的匹配部分,其主要流程是:将文章划分成长度为 k 的片段,每 w 个片段为一个窗口,在每个窗 口中取最小的片段哈希值作为该窗口的哈希值。所有被选择的哈希值作为文章的指纹。该算法能 够保证检测出长度大于等于 w+k-1 的相匹配字符串。 Fetterly 等人7在研究相似网页的群体演进的过程中对 shingling 算法作了改进。Simhash
14、 算法的相关研究Charikar 的 simhash(相似性哈希)算法2通过比较两个网页的哈希值中相同的位所占的比例来 衡量相似性,其主要思想是:将网页中的每个 token 映射到一个 b 维的向量空间,每一维的值为 1 或者-1。把网页中所有 token 的映射相加得到该网页的一个 b 维矩阵。该矩阵中每个非负的元素 都置为 1,否则置为 0,如此得到该网页的唯一哈希值。该哈希值所具有的性质是,两个网页的相 似程度与这两个网页的哈希值中相同的位的个数成正比。北京大学信息科学技术学院 网络与信息系统研究所: PKU_CS_NCIS_TR20070123Manku 等9设计了解决 Hamming
15、 距离问题的方法,即从一个 位的指纹集合中快速找到与一 个给定的指纹相异的位数最多为 的所有指纹,从而使得相似性哈希在海量网页的相似性检测中成 为实用的技术。相关的评测工作Henzinger 10对 shingling 算法和 simhash 算法的效果进行了大规模评测,通过调整参数来获 得近似相等的召回率,在此基础上比较两者的查准率。其实验显示出由于模板的影响,这两种算 法在查找相同网站上的相似网页时都不能获得理想的效果,在查找位于不同的网站上的相似网页 时查准率较高。近年来的其他技术在 Yang 和 Callan 11的工作中,他们将相似网页的检测问题视为实例层面的受限聚类问题, 并开发了
16、半监督性的聚类算法来解决此问题。他们考虑了三种类型的限制:must-link(被确认是 属于同一类别的) ,cannot-link(被确认是属于不同类别的)和 family-link(可能是属于同一类别 的) 。Huffman 等人12将相似性检测问题作为搜索评测的一个部分来进行研究,通过为每一对文 档计算多种类型的信号来提高精度。3.基于基于 LCS 的相似性度量的相似性度量3.1背景知识求解两个序列 A 和 B 的 LCS 和求解从 A 转变到 B 的最短编辑脚本(SES,shortest edit script)被认为是同一个问题的两个方面。这个问题的最早算法见于文献13,它是一个 O(
17、N2) 的 算法。后来,这个算法经过了很多的改进。其中 Myers 提出的 O(ND) 算法14在当参数 D 较小时 表现得最好。 Myers 的算法基于编辑图(Edit Graph) 。在编辑图中,求解 LCS 的问题等价于在编辑图中求 解包含最多斜线的路径。图 1演示一个实际的例子见于文献14,两个序列分别为,A = abcabba,B = cbabac。计算得到 A 和 B 的 LCS 为:caba。从 A 到 B 的最短编辑脚本(SES)为“1D 2D 3Ib 6D 7Ic” ,也就是说删除第 1、2、6 个字符,在第 3 个字符后插入b ,在第 7 个字 符后插入c 。北京大学信息科
18、学技术学院 网络与信息系统研究所: PKU_CS_NCIS_TR20070124图 1 一个 Edit Graph 例子3.2度量方法我们定义一个文档为一系列的字符组成。给定两个文档 A 和 B,|LCS| 为它们的 LCS 的长 度,|SES| 为最短编辑脚本的长度。以上述例子为例,设 A = abcabba,B = cbabac,A 和 B 的长度 分别表示为 |A| 和 |B|,则有,|A| + |B| = 2|LCS| + |SES| 定义 resemble rate 为:r(A,B) = |LCS| / (|A| + |B| - |LCS|) 定义 contain rate 为:c(
19、A,B) = |LCS| / |B| 这两参数分别表示了两篇文档 A 和 B 的相似度和包含率。 在本文中,我们判断符合下面条件的两篇文档为相似文档:如果 r(A,B) 或者 c(A, B) 超过了 一定阈值。3.3相似性度量的一般过程LCS 是一种两两比较文档的相似性检测方法。假设对于一个文档集合 R,经相似性检测后将 得到分割为若干相似文档子集 a, b, c, d, 共 n 个。那么,相似性检测的一般过程可描述如下: 1)按一定方法对文档进行排序,原则是尽可能使形成最大子集的文档排在前面。 2)读取第一个文档,放入第一个子集 a。 3)顺序读取其它文档,与已有子集的第一个文档比较,若不相
20、似,新生成一个子集。 分析可知,在这个过程中,每个文档最多将比较 n1 次。因此,每篇文档的比较次数,取 决于文档集合 R 的不相似文章数量。3.4和 COS 测度的比较当前,一种常见的相似性度量方法是 Cos(余弦)相似度量,它将两篇文档看作是词的向 量,如果 x、y 为两篇文档的向量,则:北京大学信息科学技术学院 网络与信息系统研究所: PKU_CS_NCIS_TR20070125yxyxyxCos),(Cos 测度实际上是 x 和 y 之间夹角(余弦)的度量。这样,如果余弦相似度为 1,则 x 和 y 之 间夹角为 0,并且除大小(长度)之外,x 和 y 是相同的;如果余弦相似度为 0,
21、则 x 和 y 之间夹 角为 90,并且它们不包含任何相同的词。 简单地比较,LCS 与 Cos 相比,具有下面三点重要的优势: LCS 体现了词的顺序,而 Cos 没有。显然,词的顺序在网页文档的相似性比较中本身就是一 种重要的信息,一个由若干词语按顺序组成的句子和若干没有顺序的词语组成的集合有着完全不 同的意义。完全有可能,两篇文档根本不同,但是 Cos 值却很接近 1,特别是当数规模很大的时 候。 LCS 可以评估两篇文档之间的包容关系,而 Cos 不能。一般地,如果文档 A 仅是文档 B 的一 个部分,我们仍然认为它们是相似的,这在很多应用中是很重要的,例如搜索引擎结果的消重。 网页上
22、有很多噪音信息,例如网站的模板,广告信息等,它们通常存在于网页的头尾部分, 使用 LCS 可以对不同位置文字赋予不同的权值,将这些信息和网页正文信息区别开来,从而提高 检测精度。 另一方面,一般认为,Cos 的方法要比 LCS 更快。不过,注意到,对于中文文档来说,这一 优势并不是那么明显。因为中文文档应用 Cos 方法时需要进行切词,而这一过程是很耗时的,以 我们的经验为例:我们曾经使用过的一个切词程序,1 秒种仅能切 10 个网页。 由此可见,与 Cos 测度相比,LCS 方法具有一些显而易见的潜在好处。其中最重要的是可以 获得更高的准确度,这也是我们研究基于 LCS 方法的一个主要动机。
23、同时本文提出的算法也较好 地解决了效率问题。4.算法与实现算法与实现4.1. 系统框架给定上述度量方法,我们有三个问题需要解决。前两问题是关于如何有效地计算文档的相似 性。考虑到 Myers 的 O(ND) 算法在相似的文档之间的计算很快,这两个问题可以表述为:1)如 何在计算 LCS 之前先尽可能排除掉那些完全不需要进行判断的文档,仅当两篇文档具有相似可能 性时再进行 LCS 计算;2)如何在计算 LCS 之前进一步减少两者之间的差异以提高计算速度。第 3 个问题则是关于如何在该度量的基础上进一步提高准确度。主要的问题是存在于 LCS 的相同网 站的模板可能会造成错误的肯定(false po
24、sitive) ,因此第三个问题可以表述为:如何从 LCS 中提 取出真正可信的部分(排除了网站模板的干扰)来用于计算文档相似性。 本文算法的系统框架划分为三个步骤:1)将网页文档集合分割为可能相似文档子集,仅在每 个可能相似文档子集中计算 LCS;2)在计算两篇网页文档的 LCS 之前,对网页文档进行过滤生 成文档过滤框架,在该框架而不是原始文档上进行 LCS 计算;3)计算 LCS 并选取它的可信部分 (称为 TLCS)来计算相似度。下面的小节将详细介绍这三个步骤。4.2. 可能相似子集的计算本文算法的第一个步骤是将网页文档集合分割为可能相似文档子集,以大大减少每个文档平 均需要进行的比较
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 14 两个 序列 分别 abcabba cbabac 计算 得到
限制150内