大数据十大经典算法PageRank讲解.ppt

PageRank算法,一小组：王高翔，李渠，刘晴，柳永康，刘昊骋 二小组: 王飞，李天照，赵俊杰，陈超，陈瑾翊,基本PageRank,面向主题PageRank,Link Spam与反作弊,导航页与权威页,一.Pagerank定义及终点，自连接点的概念,早期搜索引擎的弊端,Pagerank的定义,终止点,自连接点,1.早期搜索引擎的弊端,不评价,早期很多搜索引擎根本不评价结果重要性，而是直接按照某自然顺序（例如时间顺序或编号顺序）返回结果。一旦结果集变大，简直就是一场灾难，这也注定这种方法不可能用于现代的通用搜索引擎,基于检索词的评价,基于检索词评价的思想非常朴素：检索关键词出现次数越多的页面匹配度越高，而匹配度越高的页面重要性越高,词项作弊,作弊者可在他网页上增加一个词项，并将该词项重复千百次，搜索引擎可能以为该网页与检索关键词高度相关而把该网页放在搜索结果的前列,Pagerank思想： “被越多优质的网页所指的网页，它是优质的概率就越大”,2.Pagerank的定义,Pagerank是一个函数，它对Web中的每个网页赋予一个实数值。它的意图在于，网页的Pagerank越高，那么它就越“重要”。 首先，我们将Web做如下抽象：1、将每个网页抽象成一个节点；2、如果一个页面A有链接直接链向B，则存在一条有向边从A到B。因此，整个Web被抽象为一张有向图。,2.Pagerank的定义,双击添加 标题文字,一个N维矩阵，其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵 、,对应的转移矩阵如左图,设初始时每个页面的rank值为1/N，这里就是1/4。按A-D顺序将页面rank为向量v： 第一步之后，冲浪者的概率分布为Mv； 第二步之后，冲浪者的概率分布为Mv； 第i步之后，依次类推，可得冲浪者经过i步 之后的位置概率分布向量为Miv。 我们可以从初向量v出发，不断左乘矩阵M， 直到前后两轮迭代产生的结果向量差异很小 时停止，从而得到M的主特征向量。 实际上，对于Web本身而言，迭代50-75次 已经足够收敛。,3.终止点,双击添加标题文字,一个没有出链的网页称为终止点。,这里D页面不存在外链，是一个终止点。由矩阵论的知识可推知，迭代结果将最终归零。 那么该如何处理终止点呢？ 迭代拿掉图中的终止点及终止点相关的边（之所以迭代拿掉是因为当目前的终止点被拿掉后，可能会出现一批新的终止点），直到图中没有终止点。对剩下部分计算rank，然后以拿掉终止点逆向顺序反推终止点的rank值。,双击添加 标题文字,4.自连接点,如下图，D有外链所以不是终止点，但是它只链向自己（注意链向自己也算外链，当然同时也是个内链）。这种节点叫做自连接点，如果对这个图进行计算，会发现D的rank越来越大趋近于1，而其它节点rank值几乎归零。,单击添加,击添加,为了克服这种问题，需要对PageRank计算方法进行一个平滑处理，具体做法是加入“跳转因子（teleporting）”。所谓跳转因子，就是我们认为在任何一个页面浏览的用户都有可能以一个极小的概率瞬间转移到另外一个随机页面。当然，这两个页面可能不存在超链接，因此不可能真的直接转移过去，跳转因子只是为了算法需要而强加的一种纯数学意义的概率数字。,单击此处添加段落文字内容,其中往往被设置为一个比较小的参数（0.2或更小），e为N维单位向量，加入e的原因是这个公式的前半部分是向量，因此必须将/N转为向量才能相加。这样，整个计算就变得平滑，因为每次迭代的结果除了依赖转移矩阵外，还依赖一个小概率的心灵转移。,如果按这个公式迭代算下去，会发现自连接点的问题解决了，从而每个页面都拥有一个合理的pagerank。,单击此处添加段落文字内容,分块式Pagerank算法：,原来的算法存在的问题： 1.时间开销大。每次迭代就算时间开销为 2.因特网中数据大部分是分布式的，计算过程需要多次传递数据，网络负担太大。 3.n维矩阵式一个稀疏矩阵，无论计算还是存储都很浪费资源。,能否考虑先算出局部的Pagerank值？,单击此处添加段落文字内容,分块式Pagerank算法：,1.分数据块，计算每一个网络图Gi的的Local Pagerank。,算法实现步骤：,2.根据各数据块之间的相关性，计算缩略图p的Blockrank。,3.将所得Local Pagerank和Blockrank按照一定原则进行计算，得到一个新的n维Pagerank.,4.将n维Pagerank多次迭代，得到最后收敛的pagerank向量。,面向主题PageRank,动机,不同的人有不同的兴趣，而有时完全不同的兴趣却采用相同的查询词项来表达。如果搜索引擎能够推断出用户的兴趣，那么在返回相关页面的时候会表现得更好 比如用户搜索“苹果“,理想情况,实际情况,做法,做法,每个用户有一个私 人的PageRank向量,对每一个主题方向 建立偏向该主题的 一个PageRank向量,Open Directory(DMOZ) 分16个顶层类别,思路及公式,假定我们知道某些网页代表一个主题（体育），为了构建面向主题的PageRank，我们可以安排随机冲浪者只到达一个随机的体育类网页，而不是到达任意类别的一个网页。 这种做法的后果是，随机冲浪者很可能停留在已知的体育类网页上，或者从这些已知的体育类网页上通过较短的路径就可到达的网页上。体育类网页链向的网页很可能与体育类相关，随着离已知体育类网页的距离的增加，这些网页离体育相关的概率也随之降低。 假定S是一个网页的集合，其中的网页属于类别S（随机跳转集合）。es是一个向量，如果其分量对应的网页属于S，则该分量置为1，否则为0。于是S的面向主题的PageRank的迭代公式如下:,M 是Web的转移矩阵，|S|是集合S的大小,例子,假设 = 0.8 S=B,D.,于是转移矩阵乘以得：,那么(1 )eS/|S| 的第二和第四个分量是 1/10，其它分量为0.因为1 =1/5,S的大小为2,向量es中B和D对应的分量为1，A和C 对应分量为0,迭代过程:,初始V,面向主题的PageRank的使用,为了将面向主题的PageRank集成到搜索引擎中，我们必须 1.确定哪些主题需要构建特定的PageRank 2.对每个主题选择一个随机跳转集合，使用该集合来计算面向当前主题的PageRank向量值 3.对特定的搜索查询请求，寻找一种方法来确定最相关的主题和主题集合 4.对上述查询，应用步骤3中选出的主题和主题的集合的PageRank向量来返回应答结果。 上述过程第三步是最棘手的，现有一些解决方法： A.允许用户从菜单中选择一个主题 B.通过用户最近搜索查询或最近浏览的Web网页来推断主题 C.利用用户的信息（如用户的收藏夹或者社交网站上列出的兴趣）来推断主题 确定一个网页的所属类别可以使用“基于词汇的主题判断”方法,三、Link Spam与反作弊,Link Spam方法,交 换 链 接,交换链接是指网站之间人为地互相增加对方网站的链接，是增加外链成本最低和使用最多的一种方法。由于交换链接可以增加网站的外链，提高网站的pagerank值。,链 接 农 场,链接农场是指由互联网中的一部分网页组成，这些网页非常密集地互相连接在一起。链接农场是通过创建一个堆砌大量链接而没有实质内容的网页，这些链接彼此互链，或指向特定网站，以提高某个或者某些特定网页的Pagerank值为目的。,Link Spam,开 源 建 站 系 统,开源建站系统中的大多数网页都是由网页模板生成的，网页模板中含有固定的链接指向一些共同的网页甚至是作弊网页。,黄 金 链,指一些高权重的网站出售首页的链接给作弊网站，提高作弊网站的pagerank值。,链接农场,设T的总rank为y，则y由三部分组成： 1、可达页的rank贡献，设为x。 2、心灵转移的贡献，为/n。其中n为全部网页的数量，为转移参数。 3、支持页的贡献： 设有m个支持页，因为每个支持页只和T有链接，所以可以算出每个支持页的rank为： 则支持页贡献的全部rank为： 因此可以得到：,链接农场,由于相对，n非常巨大，所以可以认为/n近似于0。 简化后的方程为： 解方程得： 假设为0.2，则1/(2-2) = 2.77则这个spam farm可以将x约放大2.7倍。,Link Spam反作弊,一种方法是通过对网页的图拓扑结构分析找出可能存在的spam farm。 但是随着Web规模越来越大，这种方法非常困难，因为图的特定结构查找是时间复杂度非常高的一个算法，不可能完全靠这种方法反作弊。,网络拓扑分析,Link Spam反作弊,TrustRank的思想很直观：如果一个页面的普通rank远高于可信网页的topic rank，则很可能这个页面被spam了。 设一个页面普通rank为P，TrustRank为T，则定义网页的Spam Mass为：(P T)/P。 Spam Mass越大，说明此页面为spam目标页的可能性越大。,TrustRank,四、权威页与导航页,Page 28,链接分析技术,PageRank：关注 链接 的入度和出度，即本网页与其他网页的关系，计算出一个PR值，由此，来判断网页的重要程度。而此项，是搜索引擎查询时另外一个依据，可以说是第一个过滤项。,HITS: 分析网页的导航度和权威度，由此来判断网页的作用。,倒排索引：第一代搜索技术，将网页的数据分解成关键词项，然后按关键字建立索引，由关键字索引找到对应的网页。另外，还有非主属性值，有称副键值。带有倒排索引的文件被称为倒排文件，倒排文件中 次关键字索引被称为倒排表。由倒排表可以对集合进行并、交等操作，得到结果后再对记录进行操作。,Page Rank判断页面重要性,Page 29,PageRank，有效地利用了 Web 所拥有的庞大链接构造的特性。 从网页A导向网页B的链接被看作是对页面A对页面B的支持投票，Google根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数)，对投票的页面也进行分析。重要性高的页面所投的票的评价会更高，因为接受这个投票页面会被理解为重要的物品。根据这样的分析,得到了高评价的重要页面会被给予较高的 Page Rank(网页等级)，在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标，而且不会受到各种检索(引擎)的影响。倒不如说，PageRank 就是基于对“使用复杂的算法而得到的链接构造“的分析，从而得出的各网页本身的特性。当然，重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此 Google 使用了精练后的文本匹配技术，使得能够检索出重要而且正确的页面。,PageRank 能够对网页的重要性做出客观的评价,Page 30,1、敏感度较高，反应较快 Google对新建的网站具有较高的查知性， Google收录新建网站的两个途径是： 第一，通过网站的外部链接； 第二，通过向Google提交网站登录数据。 如果Google对外部链接网站的评价高、收录频率高那么其发现新站的速度也相应地高，新建网站被收录的日期就会被提前。,2、并重相关性和重要性 Google 使用 PageRank 技术检查整个网络链接结构，并确定哪些网页重要性最高。然后进行超文本匹配分析，以确定哪些网页与正在执行的特定搜索相关。在综合考虑整体重要性以及与特定查询的相关性之后，Google 才把最相关最可靠的搜索结果放在首位。,PageRank 能够对网页的重要性做出客观的评价,Page 31,4、较重视链接的文字描述 Google会把链接的文字描述作为关键词加以索引,PageRank 能够对网页的重要性做出客观的评价。 PageRank 并不计算直接链接的数量，而是把从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。,3、变化较快、机动性较高 Google 漫游器会定期抓取 Web，把大量网页列入索引。稍后完成的下一次抓取会注意到新网站、对现有网站的更改以及失效的链接，并对内容的变化在搜索结果中加以调整。,Page 32,权威页与导航页,权威页,某些网页提供某个主题的信息，而且具有非常重要的信息，这些网页被称为权威页,导航页,不提供主题信息，但可以找到有关该主题的网页信息，这样网页的被称为导航页,“导航页和权威页”的计算方式类似于pagerank，通过矩阵-向量的方式迭代，直到一个收敛的点。其算法又称HITS算法。 pagerank考虑的是网页重要性的一维重要性信息，而HITS认为网页具有二维的重要性信息：,Page 33,导航页与权威页,表示形式：每个网页都有一个权威度和导航度属性，若分别用h和a来表示网页的两个属性，那么h和a第j个分量就分别表示第j个网页的权威度值和导航度值。,每个网页的导航度就等于累加其链出网页的权威度，每个网页的权威度就等于累加其链入网页的导航度。并保证归一化。,单击此处添加段落文字内容 单击此处添加段落文字内