《pagerank和HIts算法总结》由会员分享，可在线阅读，更多相关《pagerank和HIts算法总结（10页珍藏版）》请在金锄头文库上搜索。
1、.摘要当前其应用主要表达在网络信息检索、网络计量学、数据挖掘、Web结构建模等方面。作为Google的核心技术之一，分析算法应用已经显现出巨大的商业价值。在分析算法中，最有名对的当属PR算法和HITS算法搜索引擎是如何进行网页的相关性排序的呢？除了看网页本身的关键词密度和关键词位置外，还要看一个更重要的要素，就是流行度或称之为分析，几个方面结合起来就能让排序更加精确。流行度的原理是，一个网页拥有的反向越多，就越有可能是高质量网页，不然也不会有更多人愿意为其做。因此，在其他因数相同的条件下，反向越多的网页排名更靠前。你可以在百度或Google搜索“SEO这个词，返回的搜索结果有上亿之多，显然不能
2、说排名靠前的网页就是含有“SEO这个词多的网页，或在标题标签等重要位置出现这个词的网页。网页自己单方面怎么说并不能说明你这个网页就是最好的，重要的是其他网页怎么评价你流行度。流行度分析并不是等于简单的数相加，因为重要性各不相同，向你的网页越权威，效果就会越好。比如PR7的老站和PR3的新站，给你站的权威值贡献是有巨大差别的。那么搜索引擎又是如何判断是否权威呢？被大量高权威值的着的站点就是权威。但仅仅本身还不足以让网页获得好的排名，因为这些可能并非与用户搜索的关键词相关。于是，的相关性便成为流行度分析的重要部分，除了主题是否相关之外，锚文本出现关键词也是非常重要的。关键词：分析 PageRank
3、 HITS 网页排名PR算法简介一、 问题背景在互联网时代，网络运营商众多，但是绝对不可忽略的必定有一家公司自1998年问世以来，在极短的时间声名鹊起，并且打败了所有的及竞争对手，成为世界上首屈一指的搜索引擎：Google。Google的成功有很多关键性因素，其中之一就是Google创始人拉里佩奇和尔盖布林于1997年构建早期的搜索系统原型时提出的分析算法。在谷歌主导互联网搜索之前，多数搜索引擎采用的排序方法，是以被搜索词语在网页中的出现次数来决定排序出现次数越多的网页排在越前面。这个判据不能说毫无道理，因为用户搜索一个词语，通常说明对该词语感兴趣。既然如此，那该词语在网页中的出现次数越多，就
4、越有可能表示该网页是用户所需要的。但是很明显，这种搜索算法容易造成的后果是，一旦某个网页在自己的中不断重复某个字段，就很容易在该字段的搜索中排到前排，这种垃圾网页的出现极拉低了搜索结果的质量，也带来不好的搜索体验。这是在这种情况下，1996年初，谷歌创始人开始了自己对于网页搜索排序的研究。PageRank即网页排名，又称网页级别，Google左侧排名或者佩奇排名。二、 算法研究从早期的网页搜索来看，单单根据关键字的重复次数来进行网页排名是不现实的，无法有效地剔除垃圾网页。佩奇和布林根据学术界评判论文的通用方法，即查看论文的引用次数来判定论文的重要性。而网页的与论文的引用相类似。因此，布林和佩奇
5、萌生根据网页来进行网页排序的思路。一个被的次数越多，它的排序就越靠前。但是仅仅如此还不够，也可能会被恶意利用，因此在评估的过程中增加了权重比例，即一个网页越是被排序靠前的网页所，它的排序就也应该越靠前。这一条的意义也是不言而喻的，就好比一篇论文被诺贝尔奖得主所引用，显然要比被普通研究者所引用更说明其价值。依照这个思路，网页排序问题就跟整个互联网的结构产生了关系。PageRank是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更
6、具“等级/重要性的网页在搜索结果中另排名获得提升，从而提高搜索结果的相关性和质量。其级别从0到10级，10级为总分值。PR值越高说明该网页越受欢迎越重要。例如：一个PR值为1的说明这个不太具有流行度，而PR值为7到10那么说明这个非常受欢迎或者说极其重要。一般PR值达到4，就算是一个不错的了。Google把自己的的PR值定到10，这说明Google这个是非常受欢迎的，也可以说这个非常重要。三、 算法步骤在问题的解决中，有一个关键因素，即初始条件是什么。想要知道一个网页的排序，不仅要知道有多少网页了它，而且还得知道那些网页各自的排序因为来自排序靠前网页的更有分量。但作为互联网大家庭的一员，本身对
7、其它网页的排序也是有贡献的，而且基于来自排序靠前网页的更有分量的原那么，这种贡献与本身的排序也有关。这样一来，我们就陷入了一个“先有鸡还是先有蛋的循环：要想知道的排序，就得知道与它的其它网页的排序，而要想知道那些网页的排序，却又首先得知道的排序。在问题的解决中，pr算法利用了假设：1在初始阶段：网页通过关系构建起Web图，每个页面设置相同的PageRank值，通过假设干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其
8、当前的PageRank值平均分配到本页面包含的出链上，这样每个即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。如果网页T存在一个指向网页A的连接，那么说明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PRT/L(T)其中PRT为T的PageRank值，L(T)为T的出链数，那么A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超相当于对该页投一票。一
9、个页面的PageRank是由所有链向它的页面链入页面的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。一、PR简单计算假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PRPageRank值将是B，C及D的和。继续假设B也有到C，并且D也有到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。换句话说，根据链出总数平分一个页面的PR值。例如，A的PR值时0.1，B的PR值时0.09，A有到C、D，B有到C、D、E，那么可以计算
10、得到PR(C)=0.1/2+0.09/3=0.08，PR(D)=0.1/2+0.09/3=0.08，PR(E)=0.09/3=0.03。同理可以求得接下来的PR值。二、PR修正计算公式但是并不是所有的用户都会在点击一个之后继续点击下一个。这里有一个初始概率，即用户会点击的概率。因此需要在简单公示的基础增加一个系数，称为阻尼系数damping factorq。q的一般取值是0.85。其意义是，在任意时刻，1-q是用户到达某页面后并继续向后浏览的概率。就是用户停止点击，随机跳到新URL的概率。算法被用在所有页面上，估算页面可能被上网者放入书签的概率。最后，即所有这些被换算为一个百分比再乘上一个系数
11、q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。这个公式就是谷歌的布林和佩奇定义的公式。虽然在初始状态下还不太好，但是随着数据量的增大，随着不断地对数据进行迭代和更新计算，所有页面的PR值会接近稳定。这个算法就是谷歌排序的数学基础。我们可以创建一个巨大的N*N的矩阵G，N是谷歌所收藏的网页数量，来存放网页之间的概率。这个算法解决了凭借关键词造假的隐患，并且与使用关键词的排序须不同，这种由网页之间的相互只与互联网的结构有关，而与用户具体搜索的东西无关，这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之所
12、以快捷，在很大程度上得益于此。四、 PR的缺陷1人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低 2旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游，除非它是某个站点的子站点。pagerank算法将互联网多数的网页通过基于来计算网页质量的方式进行排名，为搜索引擎用户提供较好的基于查询的搜索结果，同时该算法能够进行离线分析处理，大大缩短了搜索引擎用户的服务响应时间，因此就目前来说该算法是搜索引擎应用最好的算法，但是pagerank算法的缺点也是相当明显的，在上文中我们也进行了讨论，那就是该算法在初期的时候一直都是基于分析的，而一个网页上的包
13、含很多：比如广告、功能、导航、以及多次重复的无效等等，这些都会被该算法计算在pr值传递之中，所以不能够对网页降噪之后在进行处理，同时，由于是基于分析，导致pagerank算法计算出来的搜索结果往往会偏离实际的搜索主题，也就是说该算法不能很好的基于主题查询，当我们在进行查询的时候，pagerank算法会自动将计算出来的主题相关网页连接到的不相关页面也集中起来，这就导致该出现的重要网页没有出现，而不该出现的与主题不相关的页面却出现了，这对整个用户来说都是不合理的。HITS 算法一、算法背景HITSHITS(Hyperlink - Induced Topic Search) 算法是由康奈尔大学( C
14、ornell University ) 的Jon Kleinberg 博士于1999年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER的研究项目中的一部分。HITS算法是分析中非常基础且重要的算法，目前已被Teoma搜索引擎.teoma.作为分析算法在实际中使用。作为几乎是与PageRank同一时期被提出的算法，HITS同样以更精确的搜索为目的，并到今天仍然是一个优秀的算法。在HITS算法中，每个页面被赋予两个属性：hub属性和authority属性。同时，网页被分为两种：hub页面和authority页面。hub，中
15、心的意思，所以hub页面指那些包含了很多指向authority页面的的网页，比如国的一些门户；authority页面那么指那些包含有实质性容的网页。HITS算法的目的是：当用户查询时，返回给用户高质量的authority页面。二、算法研究Hub页面枢纽页面和Authority页面权威页面是HITS算法最基本的两个定义。所谓“Authority页面，是指与某个领域或者某个话题相关的高质量网页，比如搜索引擎领域，Google和百度首页即该领域的高质量网页，比如视频领域，优酷和土豆首页即该领域的高质量网页。所谓“Hub页面，指的是包含了很多指向高质量“Authority页面的网页，比如hao123首页可以认为是一个典型的高质量“Hub网页。其实枢纽页面在前面从概念意义上解释来说已经告诉了大家如何去成为枢纽页面。比如360导航的某一个站点类型的聚合页面，再比如分类目录站点的某一个站点类型的聚合页面，这些都属于枢纽页面，但是枢纽页面也会分为高质量枢纽页面和一般性枢纽页面。比如360导航首页不仅是枢纽页面并且还是导航站点的权威页面。那么又如何成为权威页面呢这里就会提到大家想要理解的一个深层次的东西了，所谓的高权重外链其实可以理解为高权威外链，即权重=权威。搜索引擎针对每一个站点
