大数据经典算法PageRank讲解.

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