每一个网站背后都有一个故事!  会员中心 会员登录   设为首页 设为首页   加入收藏 收藏百万站   百万学院 百万学院  
 
 
您当前位置:百万站 > 乐园 > 百万学院 > 有问必答
»点此完善

百万站官网资料-如何计算网站网页相似度?

⑶⑷⑸⑹㊞※ ♀3 回 囟
因㊊

如何计算网站中的网页相似度?

near duplicate detection 的任务是检测重复的内容,这项工作在搜索引擎,版权保护,信息展示等方面都有很好的应用。在搜索引擎上,主要是去掉重复的页面,图片,文件,文档等等。下面就指讨论网页的deduplication。

问题是什么?

据统计,网页上的大部分相同的页面占29%,而主体内容完全相同的占22%,这些重复网页有的是没有一点改动的拷贝,有的在内容上稍作修改,比如同一文章的不同版本,一个新一点,一个老一点,有的则仅仅是网页的格式不同(如 HTML, Postscript),文献[Models and Algorithms for Duplicate Document Detection 1999年]将内容重复归结为以下四个类型:

1.如果2篇文档内容和格式上毫无差别,则这种重复叫做full-layout duplicate。

2.如果2篇文档内容相同,但是格式不同,则叫做full-content duplicates

3.如果2篇文档有部分重要的内容相同,并且格式相同,则称为partial-layout duplicates

4.如果2篇文档有部分重要的内容相同,但是格式不同,则称为partial-content duplicates

网页去重的任务就是去掉网页中主题内容重复的部分。它和网页净化(noise reduction),反作弊(antispam) 是搜索引擎的3大门神

去重在我看来起码有四好处:减少存储;增强检索效率;增强用户的体验;死链的另一种解决方案。

目前从百度的搜索结果来看,去重工作做的不是很完善,一方面可能是技术难度(precision和recall都超过90%还是很难的);另一方面可能是重复的界定,比如转载算不算重复?所以另一项附属的工作是对个人可写的页面(PWP)进行特殊的处理,那么随之而来的工作就是识别PWP页面。^_^这里就不扯远呢。

问题如何解决?

网页的deduplication,我们的算法应该是从最简单的开始,最朴素的算法当然是

对文档进行两两比较,如果A和B比较,如果相似就去掉其中一个

然而这个朴素的算法,存在几个没有解决的问题:

   0.要解决问题是什么?full-layout?full-content?partial-layout还是partial-content?

   1. 怎么度量A 和 B的相似程度

   2. 去掉A还是去掉B,如果A ~B(~表相似,!~表示不相似),B~C 但是 A!~C,去掉B的话,C就去不掉。另一个更深入的问题是,算法的复杂度是多少?假设文档数为n,文档平均长度为m,如果相似度计算复杂度为m的某一个复杂度函数:T=T(m),文档两两比较的复杂度是O(n^2),合起来是O(n^2 * T(m)) . 这个复杂度是相当高的,想搜索引擎这样处理海量数据的系统,这样的复杂度是完全不能接受的,所有,另外三个问题是:

   3. 如何降低相似度计算的复杂化度

   4. 如何减少文档比较的复杂度

   5. 超大数据集该如何处理

   第0个问题是,我们要解决的关键,不同的问题有不同的解决方法,从网页的角度来看,结构的重复并不能代表是重复,比如产品展示页面,不同的产品展示页面就有相同的文档结构。内容来看,复制网站会拷贝其他网站的主要内容,然后加些广告或做些修改。所以,解决的问题是,partial-content deduplication,那么首先要抽取网页的主体内容。算法变成:

   抽取文档主体内容,两两比较内容的相似性,如果A和B相似,去掉其中一个

   其次,问题2依赖于问题1的相似度度量,如果度量函数具有传递性,那么问题2就不存在了,如果没有传递性,我们的方法是什么呢?哦,那就找一个关系,把相似关系传递开嘛,简单,聚类嘛,我们的框架可以改成:

   抽取文档主体内容,两两比较内容的相似性,如果A和B相似,把他们聚类在一起,最后一个类里保留一个page

最后,归纳为几个步骤

第一步:识别页面的主题内容,网页净化的一部分,以后讨论

第二步:计算相似度

第三步:聚类算法,计算出文档那些文档是相似的,归类。

核心的问题是,“如何计算相似度?”这里很容易想到的是

   1. 计算内容的编辑距离edit distance(方法很有名,但是复杂度太高)

   2. 把内容分成一个个的token,然后用集合的jaccard度量(好主意,但是页面内容太多,能不能减少啊?)

   好吧,但是,当然可以减少集合的个数呢,采样,抽取满足性质的token就可以啦,如满足 mod m =0 的token,比如有实词?比如stopwords。真是绝妙的注意.在把所有的idea放一起前,突然灵光一现,啊哈,

   3. 计算内容的信息指纹,参考google研究员吴军的数学之美系列。

把他们放在一起:

第一步:识别页面的主题内容,网页净化的一部分,以后讨论

第二步:提取页面的特征。将文章切分为重合和或不重合的几个结合,hash out

第三步:用相似度度量来计算集合的相似性,包括用信息指纹,Jaccard集合相似度量,random projection等。

第四步:聚类算法,计算出文档那些文档是相似的,归类。

方法分类:

按照利用的信息,现有方法可以分为以下三类

1.只是利用内容计算相似

2.结合内容和链接关系计算相似

3.结合内容,链接关系以及url文字进行相似计算

一般为内容重复的去重,实际上有些网页是

按照特征提取的粒度现有方法可以分为以下三类

1.按照单词这个级别的粒度进行特征提取.

2.按照SHINGLE这个级别的粒度进行特征提取.SHNGLE是若干个连续出现的单词,级别处于文档和单词之间,比文档粒度小,比单词粒度大.

3.按照整个文档这个级别的粒度进行特征提取

算法-具体见真知

1. I-Match

2. Shingling

3. Locality Sensitive Hashing.(SimHash)

4. SpotSigs

5. Combined


Bai Wan Zhan . Com
上一站:  12306订票网站: 当前访问用户过多 请稍后再试!我该怎么办
当前推荐网站:  如何计算网站网页相似度?
下一站:  谷歌pin码老收不到该肿么办?


申明:本资料由百万站会员提供,转载请注明出处,资料来源百万站网站知识库:http://www.baiwanzhan.com/site/t129549/.
如何计算网站网页相似度? 感谢您的支持!

»如果您觉得'如何计算网站网页相似度?'相关资料不全,请点此协作更新!
复制本页网址,与您QQ/MSN上的好友分享,就是您对百万站最大的支持!
踩踩此网站0
支持此网站0
(提示:顶到百万站首页,分享给更多网友!)  
现在有0人对'本文'发表评论 »查看全部评论

您的姓名: * 可选项,留空即为匿名发表
评论内容:
剩余字数:  * 按 Ctrl + Enter 发送.
           
百万站温馨提示:资料由百万站会员自行发布,请大家自辩真伪;评论只需提交一次,请耐心等候审核通过,方可显示.
»网友留言

如何计算网站网页相似度?

贡献者:webuser101点击数: 累积有7109人浏览
所属类别:有问必答主页标签:网页相似度 
参考网址:http://www.baiwanzhan.com/site/t129549/
导航目录:乐园 > 百万学院 > 有问必答
内容简介:near duplicate detection 的任务是检测重复的内容,这项工作在搜索引擎,版权保护,信息展示等方面都有很好的应用。在搜索引擎上,主要是去掉重复的页面,图片,文件,文档等等。
2019,与百万网友携手打造百万站!
百万站-百万优秀网站的大本营!我们深信:每一个优秀网站的背后都有一个值得我们解读的故事。
合 作 伙 伴