• 1. PageRank算法介绍
  • 2. 目录 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank主题敏感模型
  • 3. Google的网页排序在Google中搜索“体育新闻”
  • 4. Google的网页排序在Google中搜索“体育新闻” 搜索引擎工作的简要过程如下 针对查询词“体育新闻”进行分词——》“体育”、“新闻” 根据建立的倒排索引,将同时包含“体育”和“新闻”的文档返回,并根据相关性进行排序 这里的相关性主要是基于内容的相关性 但是会有一些垃圾网页,虽然也包含大量的查询词,但却并非满足用户需要的文档,如下图,一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的 因此,页面本身的重要性在网页排序中也起着很重要的作用
  • 5. Google的网页排序在Google中搜索“体育新闻”
  • 6. Google的网页排序如何度量网页本身的重要性呢? 互联网上的每一篇html文档除了包含文本、图片、视频等信息外,还包含了大量的链接关系,利用这些链接关系,能够发现某些重要的网页 直观地看,某网页A链向网页B,则可以认为网页A觉得网页B有链接价值,是比较重要的网页。 某网页被指向的次数越多,则它的重要性越高;越是重要的网页,所链接的网页的重要性也越高。AB网页是节点,网页 间的链接关系是边
  • 7. Google的网页排序如何度量网页本身的重要性呢? 比如,新华网体育在其首页中对新浪体育做了链接,人民网体育同样在其首页中对新浪体育做了链接 可见,新浪体育被链接的次数较多;同时,人民网体育和新华网体育也都是比较“重要”的网页,因此新浪体育也应该是比较“重要”的网页。新华网体育人民网体育
  • 8. Google的网页排序一个更加形象的图 链向网页E的链接远远多于链向网页C的链接,但是网页C的重要性却大于网页E。这是因为因为网页C被网页B所链接,而网页B有很高的重要性。
  • 9. 目录 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank主题敏感模型
  • 10. 什么是PageRank PageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排名的技术。 PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级,PR值越高说明该网页越受欢迎(越重要)。 PageRank近似于一个用户在Internet上随机地单击链接将会到达特定网页的可能性。通常,能够从更多地方到达的网页更为重要,因此具有更高的PageRank。
  • 11. Pagerank算法原理:质量假设 数量假设
  • 12. PageRank 的核心思想 PageRank 是基于「从许多优质的网页链接过来的网页,必定还是优质网页」的 回归关系,来判定所有网页的重要性。 链入链接数 (单纯的意义上的受欢迎度指标) 链入链接是否来自推荐度高的页面 (有根据的受欢迎指标) 链入链接源页面的链接数 (被选中的几率指标)
  • 13. PageRank简单计算: 假设一个由只有4个页面组成的集合:A,B,C和D。如果所有页面都链向A,那么A的PR(PageRank)值将是B,C及D的和。 继续假设B也有链接到C,并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑,D投出的票只有三分之一算到了A的PageRank上。 换句话说,根据链出总数平分一个页面的PR值。
  • 14. PageRank的简化模型 可以把互联网上的各网页之间的链接关系看成一个有向图。假设冲浪者浏览的下一个网页链接来自于当前网页。建立简化模型:对于任意网页Pi,它的PageRank值可表示为如下:其中Bi为所有链接到网页i的网页集合,Lj为网页j的对外链接数(出度)。
  • 15. PageRank的计算互联网是一个有向图 每一个网页是图的一个顶点 网页间的每一个超链接是图的一个有向边 用邻接矩阵来表示图,即:定义邻接矩阵为G,若网页j到网页i有超链接,则 ;反之 。 显然,如果网页有N个,则矩阵为N×N的0、1方阵。
  • 16. PageRank的计算定义邻接矩阵为G,若网页j到网页i有超链接,则 ;反之, 。 记矩阵G的列和、行和分别是 它们分别给出了页面j的链出链接数目和页面i链入链接数目
  • 17. 设共有 m 个网页,分别编号为 1、2、3、...、m,它们的级别(重要性)分别记为 r1、r2、r3、...、rm,G 表示由这些网页组成的有向图的邻接矩阵。G 中第 j 列的列和矩阵形式 其中 PageRank的计算
  • 18. 易知 r 是 Gm 的对应于特征值为 1 的特征向量PageRank 的计算概率转移矩阵
  • 19. 某7个网页之间的链接关系图
  • 20. 网页链接图的邻接矩阵 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0G =
  • 21. PageRank的计算 0 1 1/2 0 1/4 1/2 0 1/5 0 1/2 1/3 0 0 0 1/5 0 0 1/3 1/4 0 0 1/5 0 0 0 1/4 0 0 1/5 0 0 1/3 0 1/2 1 0 0 0 0 1/4 0 0 1/5 0 0 0 0 0 0 =状态转移概率矩阵
  • 22. PageRank的计算0.699456533837389 0.382860418521518 0.323958815672054 0.242969111754040 0.412311219946251 0.103077804986563 0.139891306767478 0.303514376996805 0.166134185303514 0.140575079872204 0.105431309904153 0.178913738019169 0.0447284345047923 0.0607028753993610求矩阵 特征值1对应的特征向量归一化
  • 23. 7个网页的PageRank值
  • 24. PageRank结果的评价 将 PageRank 的评价按顺序排列(PageRank小数点3位四舍五入):
  • 25. 页面之间相互关系及状态转移图
  • 26. PageRank结果的评价 让我们详细地看一下。ID=1的页面的PageRank是0.304,占据全体的三分之一,成为了第1位。 特别需要说明的是,对ID=1的PageRank值起到相当大效果的是从排在第3位的ID=2页面,从该页面中得到了所有的PageRank (0.166) 数。ID=2页面有从3个地方过来的链入链接,而只有面向 ID=1页面的一个链接,因此(面向ID=1页面的)链接就得到ID=2的所有的PageRank数。 不过,就因为ID=1页面是链出链接和链入链接最多的页面,也可以理解它是最受欢迎的页面。
  • 27. PageRank结果的评价 反过来,最后一名的 ID=6 页面只有 ID=1 的15%的微弱评价。 总之,即使有同样的链入链接的数目,链接源页面评价的高低也影响 PageRank 的高低。
  • 28. 简化模型面临的缺陷 实际的网络超链接环境没有这么理想化,PageRank会面临两个问题: Rank leak (等级泄漏) Rank sink (等级沉没)
  • 29. Rank LeakPR(A)PR(B)PR(C)PR(D)初始0.250.250.250.25一次迭代0.1250.1250.250.25二次迭代0.1250.1250.1250.25三次迭代0.1250.1250.1250.125……………n次迭代0000Rank leak:一个独立的网页如果没有外出的链接就产生等级泄漏 解决办法: 1.将无出度的节点递归地从图中去掉,待其他节点计算完毕后再加上 2.对无出度的节点添加一条边,指向那些指向它的顶点
  • 30. 幂迭代方法具体计算步骤输入矩阵 A 和迭代初始向量 v,以及精度 ,令 k = 0; 计算:vk+1 = Avk ; 如果 |vk+1 - vk |< ,则计算 PageRank 级别并停机。 否则转第二步。 幂迭代法
  • 31. Rank SinkPR(A)PR(B)PR(C)PR(D)初始0.250.250.250.25一次迭代00.3750.250.375二次迭代00.3750.3750.25三次迭代00.250.3750.375四次迭代00.3750.250.375五次迭代0………Rank sink:整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Rank sink
  • 32. 目录 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank主题敏感模型
  • 33. PageRank的随机浏览模型 假定一个上网者从一个随机的网页开始浏览,上网者不断点击当前网页的链接开始下一次浏览。但是,上网者最终厌倦了,开始了一个随机的网页。随机上网者用以上方式访问一个新网页的概率就等于这个网页PageRank值。 ① 这种随机模型更加接近于用户的浏览行为; ② 一定程度上解决了rank leak和rank sink的问题; ③ 保证pagerank具有唯一值。
  • 34. 随机浏览模型的图表示设定任意两个顶点之间都有直接通路, 在每个顶点处以概率p按原来蓝色方向转移,以概率1-p按红色方向转移。
  • 35. 设 (u) 是网页 u 的所获得的基本级别,则PageRank的随机浏览模型 基本思想:首先给每个网页设置一个基本级别其中: x(u) 表示网页 u 的最终级别 p 是一个加权系数,通常取 0.85 左右,按照 超链接进行浏览的概率 (u)= (1 – p )/m  
  • 36. 矩阵 形式与前面的讨论相类似,将所有网页进行编号: 1、2、... 、m于是可以把右式改写为:PageRank的随机浏览模型
  • 37. 其中:PageRank的随机浏览模型
  • 38. 规定: 记x 是 A 的对应于特征 值 =1 的特征向量。PageRank的随机浏览模型
  • 39. 改进的 PageRank 矩阵 A 的两个重要性质: A>0,即所有元素都是正数 A 的各列的列和等于 1 = (1 – p )/m
  • 40. 若矩阵 Gm 中存在 0 列,即存在 j 使得对所有的 i 有 gij = 0,则将导致 nj = 0 (nj 是 j 的导出链接总数), 此时规定:
  • 41.  = 1 是 A 的特征值吗?A 的各列的列和等于 1A 的行向量线性相关 = 1 是 A 的特征值
  • 42. 马尔可夫链收敛定理“不可约”是指每一个状态都可来自 任意的其它状态。当存在至少一个状 态经过一个固定的时间段后连续返回, 则这个过程被称为是“周期的”。
  • 43. 如果转移矩阵不可约,并且是非周期的,则收敛到一个每一列都是不同的平稳分布π,并且,独立于初始分布π0。    正的转移矩阵(即矩阵的每一个元素都是正的)是不可约和非周期的。 一个页面的PageRank是由其他页面的PageRank计算到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值(非0),由于等式PR=A*PR满足马尔可夫链的性质,如果马尔可夫链收敛,则PR存在唯一解.通过迭代计算得到所有节点的PageRank值。那么经过不断的重复计算,这些页面的PR值会趋向于平稳分布。 在此情况下,平稳分布π 是一个对应于特征根为1的、该转移矩阵的特征向量。   
  • 44. PageRank小结优点: 是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。 PageRank的缺点 过分相信链接关系 一些权威网页往往是相互不链接的,比如新浪、搜狐、网易以及腾讯这些大的门户之间,基本是不相互链接的,学术领域也是这样。 1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低 2)旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接,除非它是某个站点的子站点。
  • 45. 目录 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank主题敏感模型
  • 46. Topic-Sensitive PageRank(主题敏感) 其实上面的讨论我们回避了一个事实,那就是“网页重要性”其实没一个标准答案,对于不同的用户,甚至有很大的差别。 搜索“苹果”时 数码爱好者 iphone的信息 果农 苹果的价格走势和种植技巧 小朋友 苹果的简笔画 理想情况下,应该为每个用户维护一套专用向量,但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为Topic-Sensitive的折中方案。Topic-Sensitive PageRank的做法是预定义几个话题类别,例如体育、娱乐、科技等等,为每个话题单独维护一个向量,然后想办法关联用户的话题倾向,根据用户的话题倾向排序结果。
  • 47. Topic-Sensitive PageRank分为以下几步1、确定话题分类 一般来说,可以参考Open Directory(DMOZ)的一级话题类别作为topic。目前DMOZ的一级topic有:Arts(艺术)、Business(商务)、Computers(计算机)、Games(游戏)、Health(医疗健康)、Home(居家)、Kids and Teens(儿童)、News(新闻)、Recreation(娱乐修养)、Reference(参考)、Regional(地域)、Science(科技)、Shopping(购物)、Society(人文社会)、Sports(体育)。 2、网页topic归属 这一步需要将每个页面归入最合适的分类,具体归类有很多算法,例如可以使用TF-IDF基于词素归类,也可以聚类后人工归类,具体不再展开。这一步最终的结果是每个网页被归到其中一个topic。
  • 48. Topic-Sensitive PageRank分为以下几步3、分topic向量计算 在Topic-Sensitive PageRank中,向量迭代公式为 s是这样一个向量:对于某topic的s,如果网页k在此topic中,则s中第k个元素为1,否则为0。注意对于每一个topic都有一个不同的s。而|s|表示s中1的数量。
  • 49. 以右图的四张页面为例,假设页面A归为Arts,B归为Computers,C归为Computers,D归为Sports。那么对于Computers这个topic,s就是:|s|=2
  • 50. 一直迭代下去,直到连着两次计算出来的PageRank的值之差的绝对值小于一个阈值时停止,最后算出的向量就是Computers这个topic的rank。如果实际计算一下,会发现B、C页在这个topic下的权重相比上面非Topic-Sensitive的rank会升高,这说明如果用户是一个倾向于Computers topic的人(例如程序员),那么在给他呈现的结果中B、C会更重要,因此可能排名更靠前。 4、确定用户topic倾向。 最后一步就是在用户提交搜索时,确定用户的topic倾向,以选择合适的rank向量。主要方法有两种,一种是列出所有topic让用户自己选择感兴趣的项目,这种方法在一些社交问答网站注册时经常使用;另外一种方法就是通过某种手段(如cookie跟踪)跟踪用户的行为,进行数据分析判断用户的倾向。 Topic-Sensitive PageRank分为以下几步
  • 51. PageRank数值计算难点(一)计算机容量限制 假设N是104。通常,数值计算程序内部行列和矢量是用双精度记录的,N次正方行列A的记忆领域为 sizeof(double)*N*N=8*104*104=800MB。 N 如果变成105或106的话,就变成80GB, 8TB。这样的话不用说内存就连硬盘也已经很困难了。目前,Google处理着80亿以上的页面,很显然,已知的这种做法已经完全不适用了。
  • 52. PageRank数值计算难点(二)收敛问题 特征向量的求解,就是求解方程 ,是N元一次方程组,一般地不能得到分析解,所以只能解其数值。 然而,常用的迭代求解方法会导致收敛速度很慢。
  • 53. PageRank算法的应用学术论文的重要性排序 学术论文的作者的重要性排序 某作者引用了其它作者的文献,则该作者认为其它作者是“重要”的。 网络爬虫(Web Crawler) 可以利用PR值,决定某个URL,所需要抓取的网页数量和深度 重要性高的网页抓取的页面数量相对多一些,反之,则少一些 关键词与句子的抽取(节点与边)
  • 54. 谢谢大家!再见~\(≧▽≦)/~啦啦啦