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

基于超链接分析的排序算法洪赛2015.1.415:19:21WME小组:洪赛1搜索引擎排序算法概述超链接分析排序算法概述PageRank算法PageRank算法概述从入链数量到PageRankPageRank算法原理PageRank幂法计算PageRank优缺点CONTENT15:19:21WME小组:洪赛2HITS算法Hub页面与Authority页面算法基本思想：相互增强关系HITS算法HITS算法存在的问题HITS算法与PageRank算法比较搜索引擎排序算法，主要经历了三个阶段的发展历程：第一阶段，主要考虑关键词因素，统计关键词在文档中出现的频率和关键词在文档中出现的位置信息。词频位置加权算法应用广泛，发展也相对比较成熟，目前这种算法仍然是许多搜索引擎的核心排序算法。这类算法的代表为TF-IDF。第二阶段，考虑网页权重因素，网页本身的级别越高，在检索结果排序中越靠前。利用超链接分析，有效地计算网页的相关度与重要度，代表的算法有PageRank，HITS等。第三阶段，有效利用用户日志数据与统计学习方法，使网页相关度与重要度计算的精度有了进一步的提升，代表的方法包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。搜索引擎排序算法概述15:19:21WME小组:洪赛3超链接分析排序算法的思想起源于文献引文索引机制：一篇文章若被其他文章引用的次数越多或者被权威的论文引用，则该文章被认为很有价值。超链接分析的思想与上述思想极为相似，一个网页被其他网页引用的次数越多，或者被某一权威的网页所引用，该网页就显得越重要。超链接分析排序算法概述15:19:21WME小组:洪赛4大部分链接分析算法建立在两个概念模型上：随机漫游模型：针对浏览网页用户行为建立的抽象概念模型，用户上网过程中会不断打开链接，在相互有链接指向的网页之间跳转，这是直接跳转，如果某个页面包含的所有链接用户都不感兴趣则可能会在浏览器中输入另外的网址，这是远程跳转。该模型就是对一个直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型；典型的使用该模型的算法是PageRank；子集传播模型：基本思想是把互联网网页按照一定规则划分，分为两个甚至是多个子集合。其中某个子集合具有特殊性质，很多算法从这个具有特殊性质的子集合出发，给予子集合内网页初始权值，之后根据这个特殊子集合内网页和其他网页的链接关系，按照一定方式将权值传递到其他网页。典型的使用该模型的算法有HITS和Hilltop算法。15:19:21WME小组:洪赛5链接算法很多，从其概念模型来说，基本遵循上述介绍的随机游走模型和子集传播模型。而从图中可看出，在众多算法中，PageRank和HITS算法可以说是最重要的两个具有代表性的链接分析算法，后续的很多链接分析算法都是在这两个算法基础上衍生出来的改进算法。链接分析算法之间的关系15:19:21WME小组:洪赛6PageRank，即网页排名，又称网页级别、Google左侧排名或佩奇排名。Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期搜索系统原型时提出的链接分析算法。目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法。PageRank算法概述15:19:21WME小组:洪赛7PageRank的级别从0到10级，10级为满分。PR值越高说明该网页越受欢迎（越重要）。PR值为7到10则表明这个网站非常受欢迎（或者说极其重要）。一般PR值达到4，就算是一个不错的网站了。Google把自己的网站的PR值定到10。15:19:21WME小组:洪赛8早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。PageRank除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。从入链数量到PageRank15:19:21WME小组:洪赛9对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。从入链数量到PageRank15:19:21WME小组:洪赛10PageRank的计算充分利用了数量假设和质量假设。步骤如下：1）在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。PageRank算法原理15:19:21WME小组:洪赛11基本思想：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)其中PR（T）为T的PageRank值，L(T)为T的出链数;则A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。PageRank算法原理15:19:21WME小组:洪赛12假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的和。PR(A)=PR(B)+PR(C)+PR(D)或R𝑖=𝑅(𝑗)𝑗∈𝐵(𝑖)(B(x)表示所有指向x的网页)假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。PR(A)=PR(B)/2+PR(C)/1+PR(D)/3换句话说，根据链出总数平分一个页面的PR值。PR(A)=PR(B)/L(B)+PR(C)/L(C)+PR(D)/L(D)或R𝑖=𝑅(𝑗)𝐿(𝑗)𝑗∈𝐵(𝑖)（L(j)表示j页面的超链接数）PageRank算法原理15:19:21WME小组:洪赛13例子：如图所示的例子来说明PageRank的具体计算过程。PageRank算法原理15:19:21WME小组:洪赛14修正PageRank计算公式:由于存在一些出链为0，也就是那些不链接任何其他网页的网，也称为孤立网页，使得很多网页能被访问到。对PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数（dampingfactor）q，q一般取值q=0.85。其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。1-q=0.15就是用户停止点击，随机跳到新URL的概率的。PageRank算法原理15:19:21WME小组:洪赛15ArvindArasu在《JunghooChoHectorGarcia-Molina,AndreasPaepcke,SriramRaghavan.SearchingtheWeb》更加准确的表达为：p_1,p_2,...,p_N是被研究的页面，L(p_j)是p_j链出页面的数量，而N是所有页面的数量。PageRank算法原理15:19:21WME小组:洪赛16一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。要得到一个页面的PageRank，得先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗？那么有没有不依赖于初始值的PageRank算法？也就是说，如果存在一种计算方法，使得无论怎样设置初始值，最后都会收敛到同一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。PageRank算法原理15:19:21WME小组:洪赛17将页面看作节点，超链接看作有向边，整个互联网就变成一个有向图了。此时，用邻接矩阵P表示整个互联网，若第I个页面有存在到第J个页面的超链接，那么矩阵元素p[i][j]=1，否则p[i][j]=0。对于右图有矩形P:P=011001100PageRank幂法计算15:19:21WME小组:洪赛18观察矩阵P可发现，P的第i行表示第i个网页指向的网页，M的第j列表示指向j的网页。如果将P的每个元素都除于所在行的全部元素之和，然后再将P转置（交换行和列），得到P’T：P=011001100P’=01/21/2001100P’T=0011/2001/210P为网页链接矩阵，P’为网页链接概率矩阵，P’T为概率转移矩阵PR可以看作P’T的特征向量，其对应的特征值为1/q（特征向量的定义——对于矩阵A，若存在着列向量X和一个数c，使得AX=cX，则X称为A的特征向量，c称为A的特征值）PageRank幂法计算15:19:21WME小组:洪赛19PageRank值是一个P’T中的特征向量。这个特征向量为：R是如下等式的一个解：如果网页i有指向网页j的一个链接，则否则PageRank幂法计算15:19:21WME小组:洪赛20PageRank公式可以转换为求解lim𝑛→∞𝐴𝑛𝑋的值其中矩阵为A=q×P’T+(1-q)*𝑒𝑒𝑡/N。𝑒𝑡为n维的全1行.则𝑒𝑒𝑡=1⋯1⋮⋱⋮1⋯1PageRank幂法计算15:19:21WME小组:洪赛21幂法计算过程如下：X设任意一个初始向量,即设置初始每个网页的PageRank值均。一般为1.R=AX;while(1){if(lX-RIƐ){//如果最后两次的结果近似或者相同，返回RreturnR;}else{X=R;R=AX;}}用幂法计算PageRank值总是收敛的，即计算的次数是有限的。不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。PageRank幂法计算15:19:21WME小组:洪赛22优点：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。缺点：1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。PageRank需要多项算法结合应用PageRank优缺点15:19:21WME小组:洪赛23HITS(Hyperlink-InducedTopicSearch)算法是由康奈尔大学(CornellUniversity)的JonKleinberg博士于1997年首先提出的,为IBM公司阿尔马登研究中心(IBMAlmadenResearchCenter)的名为“CLEVER”的研究项目中的一部分。HITS算法是链接分析中非常基础且重要的算法，目前已被Teoma搜索引擎（）作为链接分析算法在实际中使