page rank和HIts算法总结.doc

摘要当前其应用主要体现在网络信息检索、网络计量学、数据挖掘、Web结构建模等方面。作为Google的核心技术之一，链接分析算法应用已经显现出巨大的商业价值。在链接分析算法中，最有名对的当属PR算法和HITS算法搜索引擎是如何进行网页的相关性排序的呢？除了看网页本身的关键词密度和关键词位置外，还要看一个更重要的要素，就是链接流行度（或称之为链接分析），几个方面结合起来就能让排序更加精确。链接流行度的原理是，一个网页拥有的反向链接越多，就越有可能是高质量网页，不然也不会有更多人愿意为其做链接。因此，在其他因数相同的条件下，反向链接越多的网页排名更靠前。你可以在百度或Google搜索“SEO”这个词，返回的搜索结果有上亿之多，显然不能说排名靠前的网页就是含有“SEO”这个词多的网页，或在标题标签等重要位置出现这个词的网页。网页自己单方面怎么说并不能说明你这个网页就是最好的，重要的是其他网页怎么评价你链接流行度。链接流行度分析并不是等于简单的链接数相加，因为链接重要性各不相同，链接向你的网页越权威，效果就会越好。比如PR7的老站和PR3的新站，给你站的权威值贡献是有巨大差别的。那么搜索引擎又是如何判断是否权威网站呢？被大量高权威值的网站链接着的站点就是权威网站。但仅仅链接本身还不足以让网页获得好的排名，因为这些链接可能并非与用户搜索的关键词相关。于是，链接的相关性便成为链接流行度分析的重要部分，除了网站主题是否相关之外，锚文本出现关键词也是非常重要的。 关键词：链接分析 PageRank HITS 网页排名 PR算法简介一、 问题背景在互联网时代，网络运营商众多，但是绝对不可忽略的必定有一家公司自1998年问世以来，在极短的时间内声名鹊起，并且打败了所有的及竞争对手，成为世界上首屈一指的搜索引擎：Google。Google的成功有很多关键性因素，其中之一就是Google创始人拉里佩奇和谢尔盖布林于1997年构建早期的搜索系统原型时提出的链接分析算法。在谷歌主导互联网搜索之前， 多数搜索引擎采用的排序方法， 是以被搜索词语在网页中的出现次数来决定排序出现次数越多的网页排在越前面。 这个判据不能说毫无道理， 因为用户搜索一个词语， 通常表明对该词语感兴趣。 既然如此， 那该词语在网页中的出现次数越多， 就越有可能表示该网页是用户所需要的。但是很明显，这种搜索算法容易造成的后果是，一旦某个网页在自己的链接中不断重复某个字段，就很容易在该字段的搜索中排到前排，这种垃圾网页的出现极大地拉低了搜索结果的质量，也带来不好的搜索体验。这是在这种情况下，1996年初，谷歌创始人开始了自己对于网页搜索排序的研究。PageRank即网页排名，又称网页级别，Google左侧排名或者佩奇排名。二、 算法研究从早期的网页搜索来看，单单根据关键字的重复次数来进行网页排名是不现实的，无法有效地剔除垃圾网页。佩奇和布林根据学术界评判论文的通用方法，即查看论文的引用次数来判定论文的重要性。而网页的链接与论文的引用相类似。因此，布林和佩奇萌生根据网页链接来进行网页排序的思路。一个网站被链接的次数越多，它的排序就越靠前。但是仅仅如此还不够，也可能会被恶意利用，因此在评估的过程中增加了权重比例，即一个网页越是被排序靠前的网页所链接， 它的排序就也应该越靠前。 这一条的意义也是不言而喻的， 就好比一篇论文被诺贝尔奖得主所引用， 显然要比被普通研究者所引用更说明其价值。 依照这个思路， 网页排序问题就跟整个互联网的链接结构产生了关系。PageRank是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。其级别从0到10级，10级为满分。PR值越高说明该网页越受欢迎（越重要）。例如：一个PR值为1的网站表明这个网站不太具有流行度，而PR值为7到10则表明这个网站非常受欢迎（或者说极其重要）。一般PR值达到4，就算是一个不错的网站了。Google把自己的网站的PR值定到10，这说明Google这个网站是非常受欢迎的，也可以说这个网站非常重要。三、 算法步骤在问题的解决中，有一个关键因素，即初始条件是什么。想要知道一个网页wi的排序， 不仅要知道有多少网页链接了它， 而且还得知道那些网页各自的排序因为来自排序靠前网页的链接更有分量。 但作为互联网大家庭的一员，wi本身对其它网页的排序也是有贡献的， 而且基于来自排序靠前网页的链接更有分量的原则， 这种贡献与wi本身的排序也有关。 这样一来， 我们就陷入了一个 “先有鸡还是先有蛋” 的循环： 要想知道wi的排序， 就得知道与它链接的其它网页的排序， 而要想知道那些网页的排序， 却又首先得知道wi的排序。在问题的解决中，pr算法利用了假设：1）在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)其中PR（T）为T的PageRank值，L(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。（一）、PR简单计算假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是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，则可以计算得到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 factor）q。q的一般取值是0.85。其意义是，在任意时刻，1-q是用户到达某页面后并继续向后浏览的概率。就是用户停止点击，随机跳到新URL的概率。算法被用在所有页面上，估算页面可能被上网者放入书签的概率。最后，即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。这个公式就是谷歌的布林和佩奇定义的公式。虽然在初始状态下还不太好，但是随着数据量的增大，随着不断地对数据进行迭代和更新计算，所有页面的PR值会接近稳定。这个算法就是谷歌排序的数学基础。我们可以创建一个巨大的N*N的矩阵G，N是谷歌所收藏的网页数量，来存放网页之间的概率。这个算法解决了凭借关键词造假的隐患，并且与使用关键词的排序须不同，这种由网页之间的相互链接只与互联网的结构有关，而与用户具体搜索的东西无关，这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行。 谷歌搜索的速度之所以快捷， 在很大程度上得益于此。四、 PR的缺陷1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低 2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。 pagerank算法将互联网中大多数的网页通过基于链接来计算网页质量的方式进行排名，为搜索引擎用户提供较好的基于链接查询的搜索结果，同时该算法能够进行离线分析处理，大大缩短了搜索引擎用户的服务响应时间，因此就目前来说该算法是搜索引擎应用最好的算法，但是pagerank算法的缺点也是相当明显的，在上文中我们也进行了讨论，那就是该算法在初期的时候一直都是基于链接分析的，而一个网页上的链接包含很多：比如广告链接、功能链接、导航链接、以及多次重复的无效链接等等，这些链接都会被该算法计算在pr值传递之中，所以不能够对网页降噪之后在进行处理，同时，由于是基于链接分析，导致pagerank算法计算出来的搜索结果往往会偏离实际的搜索主题，也就是说该算法不能很好的基于主题查询，当我们在进行查询的时候，pagerank算法会自动将计算出来的主题相关网页连接到的不相关页面也集中起来，这就导致该出现的重要网页没有出现，而不该出现的与主题不相关的页面却出现了，这对整个用户来说都是不合理的。HITS 算法一、算法背景HITS（HITS(Hyperlink - Induced Topic Search) ） 算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1999年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。HITS算法是链接分析中非常基础且重要的算法，目前已被Teoma搜索引擎（）作为链接分析算法在实际中使用。作为几乎是与PageRank同一时期被提出的算法，HITS同样以更精确的搜索为目的，并到今天仍然是一个优秀的算法。在HITS算法中，每个页面被赋予两个属性：hub属性和authority属性。同时，网页被分为两种：hub页面和authority页面。hub，中心的意思，所以hub页面指那些包含了很多指向authority页面的链接的网页，比如国内的一些门户网站；authority页面则指那些包含有实质性内容的网页。HITS算法的目的是：当用户查询时，返回给用户高质量的authority页面。二、算法研究Hub页面（枢纽页面）和Authority页面（权威页面）是HITS算法最基本的两个定义。所谓“Authority”页面，是指与某个领域或者某个话题相关的高质量网页，比如搜索引擎领域，Google和百度首页即该领域的高质量网页，比如视频领域，优酷和土豆首页即该领域的高质量网页。所谓“Hub”页面，指的是包含了很多指向高质量“Authority”页面链接的网页，比如hao123首页可以认为是一个典型的高质量“Hub”网页。其实枢纽页面在前面从概念意义上解释来说已经告诉了大家如何去成为枢纽页面。比如360导航网站的某一个站点类型的聚合页面，再比如网站分类目录站点的某一个站点类型的聚合页面，这些都属于枢纽页面，但是枢纽页面也会分为高质量枢纽页面和一般性枢纽页面。比如360导航网站首页不仅是枢纽页面并且还是导航站点的权威页面。那么又如何成为权威页面呢?这里就会提到大家想要理解的一个深层次的东西了，所谓的高权重外链其实可以理解为高权威外链，即权重=权威。搜索引擎针对每一个站点和该站点的每一个页面都有一系列的网页评分，而这类评分决定着页面的链接是否为有效的信任度。HITS算法基于下面两个假设：1）一个高质量的authority页面会被很多高质量的hub页面所指向。2）一个高质量的hub页面会指向很多高质量的authority页面。什么叫“高质量”，这由每个页面的hub值和authority值确定。其确定方法为：1）页面hub值等于所有它指向的页面的authority值之和。2）页面authority值等于所有指向它的页面的hub值之和。我们在这里给出一个简单的例子：A CB 图2从图2的例子可以进行分析，假设页面a的hub值为H（A），authority值为A（A），所有页面两个初始的权值都是1.根据上述的确定规则我们可以计算，H(A)=0;H(B)=0;H(C)=A(A)+A(B)=2;A(A)=H(C)=2;A(B)=H(C=2;A(C)=0;从这里可以看出，页面C是一个相对好的authority页面，二页面A和B是一个相对较好的hub页面。算法描述： 图2如图2所示，给出了算法的迭代过程。三、算法步骤与PageRank算法不同，HITS算法是在用户搜索后运行的，所以HITS算法的处理对象集合肯定得小很多。首先，我们需要确定这个集合。整个互联网中的网页之间的关系可以抽象为一个有向图G=(V,E)，当有一个搜索请求产生时（不妨设关键字为）,我们可以取所有包含关键字的网页组成的集合Q为初始集合，并在这个集合上运行我们的HITS算法。然而，这个集合却有着明显的缺陷：这个集合可能非常之大，大到包含了数百万个网页，而这显然不是理想的集合大小。于是，我们进而想找到一个更小的集合S，满足以下条件：1. S确实足够小。2. S包含很多与查询相关的页面。3. S包含很多高质量的authority页面。如何找到这个S集合？我们假设用户输入关键字搜索，搜索引擎使用一个基于文本的引擎进行搜索。然后我们取排名（按照相关度排名）最靠前的t（t一般取200左右）个网页作为初始集合，记为根集合R。这个集合满足我们上面提到的前两个条件，但是还远远不能满足第三个条件。于是，我们需要扩展R。一般认为，一个与关键字相关的高质量的网页即使不在R中，那也很可能在R中有某些网页指向它。基于此，我们扩展R的过程如下（摘自Jon Kleinberg 的论文）：Subgraph(, t, d): a query string.: a text-based search engine.t, d: natural numbers.LetRdenote the top t results ofon.SetS:=RFor each page pRLet+(p)denote the set of all pages p points to.Let(p)denote the set of all pages pointing to p.Add all pages in+(p)toS.If|(p)|d, thenAdd all pages in(p)toS.ElseAdd an arbitrary set of d pages from(p)toS.EndReturnS程序1一开始我们令S=R。然后通过上面的方法，我们将所有被R中网页所指向的网页加入到S中，再把一定数量的指向R集合中网页的那些网页（每个R中网页最多能添加d个指向它的网页）加入到S中。为了保证S集合的合适的大小，d不能太大，一般设置为50左右。通常情况下，扩展之后集合的大小为10005000个网页，满足上面的三个条件。五、 算法缺点 HITS算法整体而言是个效果很好的算法，目前不仅应用在搜索引擎领域，而且被“自然语言处理”以及“社交分析”等很多其它计算机领域借鉴使用，并取得了很好的应用效果。尽管如此，最初版本的HITS算法仍然存在一些问题，而后续很多基于HITS算法的链接分析方法，也是立足于改进HITS算法存在的这些问题而提出的。 1.效率低这里说的“效率低”是针对其实时计算的特点而提出的。HITS算法是在用户提出搜索请求之后才开始运行的，然而计算出结果又需要多次迭代计算，所以就这点上来说HITS算法效率仍然较低。2.主题漂移在算法原理部分我们介绍了HITS算法是如何生成初始集合G。从根集合R我们通过链接添加网页的方法进行扩展，但这也很可能添加进与搜索主题无关的网页。若是这部分网页中又恰恰有着一些高质量的authority页面，则很有可能返回给用户，降低用户的搜索体验。3.作弊网页试想我们弄一个页面指向很多高质量的authority页面，那么这个页面就成为了一个高质量的hub页面。然后再弄个链接指向自己的搓网页，按照HITS算法，将大大提升自己的搓网页的authority值。4.稳定性差对于一个网页集合，若是删除其中的某条链接，就有可能造成一些网页的hub值和authority值发生巨大变化。总结从上面的分析可见，PageRank算法和HITS算法都是基于链接分析的搜索引擎排序算法，并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。虽然两种算法均为链接分析算法，但两者之间还是有明显的区别的。HITS算法计算的authority值只是相对于某个检索主题的权重，因此HITS算法也常被称为Query-dependent算法；而PageRank算法是独立于检索主题，因此也常被称为Query-independent算法。PageRank算法的优点在于它对互联网上的网页给出了一个全局的重要性排序，并且算法的计算过程是可以离线完成的，这样有利于迅速响应用户的请求。不过，其缺点在于主题无关性，没有区分页面内的导航链接、广告链接和功能链接等，容易对广告页面有过高评价；另外，PageRank算法的另一弊端是，旧的页面等级会比新页面高，因为新页面，即使是非常好的页面，也不会有很多链接，除非他是一个站点的子站点。这就是PageRank需要多项算法结合的原因。HITS算法的优点在于它能更好地描述互联网的组织特点，由于它只是对互联网中的很小的一个子集进行分析，所以它需要的迭代次数更少，收敛速度更快，减少了时间复杂度。但HITS算法也存在如下缺点：中心网页之间的相互引用以增加其网页评价，当一个网站上的多篇网页指向一