基于超链接分析的排序算法课件

1、基于超链接分析的排序算法洪赛2015.1.42022/10/41WME小组:洪赛小组:洪赛搜索引擎排序算法概述超链接分析排序算法概述PageRank算法PageRank算法概述从入链数量到 PageRankPageRank算法原理PageRank幂法计算PageRank优缺点CONTENTHITS算法Hub页面与Authority页面算法基本思想：相互增强关系HITS算法HITS算法存在的问题HITS算法与PageRank算法比较2022/10/42WME小组:洪赛小组:洪赛搜索引擎排序算法，主要经历了三个阶段的发展历程：第一阶段，主要考虑关键词因素，统计关键词在文档中出现的频率和关键词在文档

2、中出现的位置信息。词频位置加权算法应用广泛，发展也相对比较成熟，目前这种算法仍然是许多搜索引擎的核心排序算法。这类算法的代表为TF-IDF。第二阶段，考虑网页权重因素，网页本身的级别越高，在检索结果排序中越靠前。利用超链接分析，有效地计算网页的相关度与重要度，代表的算法有 PageRank ，HITS等。第三阶段，有效利用用户日志数据与统计学习方法，使网页相关度与重要度计算的精度有了进一步的提升，代表的方法包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。搜索引擎排序算法概述2022/10/43WME小组:洪赛小组:洪赛超链接分析排序算法的思想起源于文献引文索引机制：一篇

3、文章若被其他文章引用的次数越多或者被权威的论文引用，则该文章被认为很有价值。超链接分析的思想与上述思想极为相似，一个网页被其他网页引用的次数越多，或者被某一权威的网页所引用，该网页就显得越重要。超链接分析排序算法概述2022/10/44WME小组:洪赛小组:洪赛大部分链接分析算法建立在两个概念模型上：随机漫游模型：针对浏览网页用户行为建立的抽象概念模型，用户上网过程中会不断打开链接，在相互有链接指向的网页之间跳转，这是直接跳转，如果某个页面包含的所有链接用户都不感兴趣则可能会在浏览器中输入另外的网址，这是远程跳转。该模型就是对一个直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型；典型的使用

4、该模型的算法是PageRank；子集传播模型：基本思想是把互联网网页按照一定规则划分，分为两个甚至是多个子集合。其中某个子集合具有特殊性质，很多算法从这个具有特殊性质的子集合出发，给予子集合内网页初始权值，之后根据这个特殊子集合内网页和其他网页的链接关系，按照一定方式将权值传递到其他网页。典型的使用该模型的算法有HITS和Hilltop算法。2022/10/45WME小组:洪赛小组:洪赛PageRank，即网页排名，又称网页级别、Google左侧排名或佩奇排名。Google创始人拉里佩奇和谢尔盖布林于1997年构建早期搜索系统原型时提出的链接分析算法。目前很多重要的链接分析算法都是在PageR

5、ank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法。PageRank算法概述2022/10/47WME小组:洪赛小组:洪赛PageRank的级别从0到10级，10级为满分。PR值越高说明该网页越受欢迎（越重要）。PR值为7到10则表明这个网站非常受欢迎（或者说极其重要）。一般PR值达到4，就算是一个不错的网站了。Google把自己的网站的PR值定到10。2022/10/48WME小组:洪赛小组:洪赛对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量

6、越多，那么这个页面越重要。质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。从入链数量到 PageRank2022/10/410WME小组:洪赛小组:洪赛PageRank的计算充分利用了数量假设和质量假设。步骤如下：1）在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分

7、的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。 PageRank算法原理2022/10/411WME小组:洪赛小组:洪赛基本思想：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)其中PR（T）为T的PageRank值，L(T)为T的出链数;则A的PageRank值为一系列类似于T

8、的页面重要性得分值的累加。 即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。PageRank算法原理2022/10/412WME小组:洪赛小组:洪赛例子：如图所示的例子来说明PageRank的具体计算过程。PageRank算法原理2022/10/414WME小组:洪赛小组:洪赛修正PageRank计算公式:由于存在一些出链为0，也就是那些不链接任何其他网页的网， 也称为孤立网页，使得

9、很多网页能被访问到。对 PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数（damping factor）q， q一般取值q=0.85。其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。1-q=0.15就是用户停止点击，随机跳到新URL的概率的。 PageRank算法原理2022/10/415WME小组:洪赛小组:洪赛一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。要得到一个页面的PageR

10、ank，得先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗？那么有没有不依赖于初始值的PageRank算法？也就是说，如果存在一种计算方法，使得无论怎样设置初始值，最后都会收敛到同一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。PageRank算法原理2022/10/417WME小组:洪赛小组:洪赛PageRank幂法计算2022/10/418WME小组:洪赛小组:洪赛PageRank幂法计算2022/10/419WME小组:洪赛小组:洪赛PageRank值是一个PT中的特征

11、向量。这个特征向量为：R是如下等式的一个解：如果网页i有指向网页j的一个链接，则否则PageRank幂法计算2022/10/420WME小组:洪赛小组:洪赛PageRank幂法计算幂法计算过程如下： X设任意一个初始向量,即设置初始每个网页的PageRank值均。一般为1.R = AX;while (1 )if( lX -R I ) /如果最后两次的结果近似或者相同，返回Rreturn R; else X =R;R = AX;2022/10/421WME小组:洪赛小组:洪赛用幂法计算PageRank 值总是收敛的，即计算的次数是有限的。不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛

12、到他们的真实值。PageRank幂法计算2022/10/422WME小组:洪赛小组:洪赛HITS(Hyperlink - Induced Topic Search)算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。HITS算法是链接分析中非常基础且重要的算法，目前已被Teoma搜索引擎（）作为链接分析算法在实际中使用。HITS算法2022/10/424WME小组:洪赛小组:洪赛Hub页面

13、（枢纽页面）和Authority页面（权威页面）是HITS算法最基本的两个定义。所谓“Authority”页面，是指与某个领域或者某个话题相关的高质量网页，比如搜索引擎领域，Google和百度首页即该领域的高质量网页，比如视频领域，优酷和土豆首页即该领域的高质量网页。所谓“Hub”页面，指的是包含了很多指向高质量“Authority”页面链接的网页，比如hao123首页可以认为是一个典型的高质量“Hub”网页。 HITS算法的目的即是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量“Authority”页面和“Hub”页面，尤其是“Authority”页面，因为这些页面代表了能够

14、满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。Hub页面与Authority页面2022/10/425WME小组:洪赛小组:洪赛根集合将查询q提交给基于关键字查询的检索系统，从返回结果页面的集合总取前n个网页(如n=200)，作为根集合(root set)，记为root，则root满足：1).root中的网页数量较少2).root中的网页是与查询q相关的网页3).root中的网页包含较多的权威(Authority)网页HITS算法2022/10/427WME小组:洪赛小组:洪赛扩展集合base在根集root的基础上，HITS算法对网页集合进行扩充（参考右图）集合base扩充原则

15、是：凡是与根集内网页有直接链接指向关系的网页都被扩充到集合base，无论是有链接指向根集内页面，或者是根集页面有链接指向的页面，都被扩充进入扩展网页集合base。HITS算法在这个扩充网页集合内寻找好的“Hub”页面与好的“Authority”页面。HITS算法2022/10/428WME小组:洪赛小组:洪赛对于“扩充网页集合”来说，我们并不知道哪些页面是好的“Hub”或者好的“Authority”页面，每个网页都有潜在的可能，所以对于每个页面都设立两个权值，分别来记载这个页面是好的Hub或者Authority页面的可能性。在初始情况下，在没有更多可利用信息前，每个页面的这两个权值都是相同的，

16、可以都设置为1。 之后，即可利用上面提到的两个基本假设，以及相互增强关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定不再发生明显的变化为止。HITS算法2022/10/429WME小组:洪赛小组:洪赛右图给出了迭代计算过程中，某个页面的Hub权值和Authority权值的更新方式。HITS算法假设以A(i)代表网页i的Authority权值，以H(i)代表网页i的Hub权值。在右图所示例子中，“扩充网页集合”有3个网页有链接指向页面1，同时页面1有3个链接指向其它页面。那么，网页1在此轮迭代中的Authority权值即为所有指向网页1页面的Hub权值之和；类似的，网

17、页1的Hub分值即为所指向的页面的Authority权值之和。2022/10/430WME小组:洪赛小组:洪赛“扩充网页集合”内其它页面也以类似的方式对两个权值进行更新，当每个页面的权值都获得了更新，则完成了一轮迭代计算，此时HITS算法会评估上一轮迭代计算中的权值和本轮迭代之后权值的差异，如果发现总体来说权值没有明显变化，说明系统已进入稳定状态，则可以结束计算。将页面根据Authority权值得分由高到低排序，取权值最高的若干页面作为响应用户查询的搜索结果输出。如果比较发现两轮计算总体权值差异较大，则继续进入下一轮迭代计算，直到整个系统权值稳定为止。HITS算法2022/10/431WME小

18、组:洪赛小组:洪赛HITS算法2022/10/432WME小组:洪赛小组:洪赛 HITS算法整体而言是个效果很好的算法，目前不仅应用在搜索引擎领域，而且被“自然语言处理”以及“社交分析”等很多其它计算机领域借鉴使用，并取得了很好的应用效果。尽管如此，最初版本的HITS算法仍然存在一些问题，而后续很多基于HITS算法的链接分析方法，也是立足于改进HITS算法存在的这些问题而提出的。HITS算法存在的问题2022/10/433WME小组:洪赛小组:洪赛归纳起来，HITS算法主要在以下几个方面存在不足：1.计算效率较低：HITS算法是与查询相关的算法，必须在接收到用户查询后进行计算，并且HITS算法

19、本身需要进行很多轮迭代计算才能获得最终结果2.主题漂移问题:如果在扩展网页集合里包含部分与查询主题无关的页面，且这些页面之间有较多的相互链接指向，那么HITS算法很可能会给予这些无关网页很高的排名，导致搜索结果发生主题漂移，这种现象被称为“紧密链接社区现象”（Tightly-Knit Community Effect）。3.易被作弊者操纵结果:比如作弊者可以建立一个网页，页面内容增加很多指向高质量网页或者著名网站的网址，这就是一个很好的Hub页面，之后作弊者再将这个网页链接指向作弊网页，于是可以提升作弊网页的Authority得分。4.结构不稳定:在原有的“扩充网页集合”内，若添加删除个别网页或者改变少数链接关系，HITS算法的排名结果就会有非常大的改变。HITS算法存在的问题2022/10/434WME小组:洪赛小组:洪赛 HITS算法和PageRank算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。然而两者在基本概念模型、计算思路以及技术实现细节都有很大的不同，下面对两者之间的差异进行逐一说明。 1.HITS算法是与用户输入的查询请求密切相关的，而PageRank与查询请求无关。所以，HITS算法可以单独作为相似性计算评价标准，而PageRank必须结合内容相似性计算才可以用来对网页相关性进行