基于特征值特征向量的网页分级算法

1、基于特征值特征向量的网页分级算法摘要 随着互联网的高速发展，我们如若想在浩瀚的互联网海洋上获取到想要的信息难度与日俱增，因为我们需要不断地筛选、排除没用的信息，这会耗费我们大量的时间和精力。所以，我们需要一个好的搜索引擎帮我们过滤掉许多没用的信息，使我们能够方便快捷的找到所需信息，Google在这一方面就做的非常优秀。当我们用Google搜索某个词条时，常常会发现自己感兴趣的页面会排在比较前面的地方，这很大程度上是源于Google的PageRank算法。本文的主要目的是介绍PageRank算法，阐明了PageRank算法的基本原理，并分析了随机冲浪模型，最后介绍幂法。关键词 PageRank

2、特征向量 随机冲浪模型 幂法Page classification algorithm based on eigenvalue and eigenvector Abstract With the rapid development of the internet, we get to the wanted information on the internet increasing difficulty, since we need to constantly screened to exclude useless information, which will cost us a lot o

3、f time and energy. So, we need a good search engine to help us to filter out a lot of useless information, which can enables us to easily and quickly find the information we need, in this regard, Google doing very good. When we use Google search for a term, we often find that our interested page wil

4、l be ranked front in the result listings, which largely due to Google's PageRank algorithm. The main purpose of this paper is to introduce the PageRank algorithm, and clarify the basic principles of PageRank algorithm, and analyzes the random surfer model. last, introduce the power method.Keywor

5、ds PageRank Eigenvector The Random Surfer Model Power Method目录1 引言12简介搜索引擎12.1 搜索引擎的基本框架13 PageRank算法33.1 PageRank算法简介33.2 PageRank算法原理33.3 PageRank算法44 随机冲浪模型75 幂法86结论107 致谢词11 1 引言随着现代化科技的高速发展，我们逐渐进入了大数据时代，相应的，互联网上的数据量也正在以指数的形式暴增。总的来说，Web具有四大特点：庞大性、动态性、异构性、半结构化的数据结构环境。面对越来越多的数据，搜索引擎已然成为我们在网上检索信息的重

6、要工具，Google的搜索引擎是一个成功的例子。互联网上的网页除了包含文本、图片、视频等信息外，还包含了许多链接，用户可以通过该链接访问其他网页，Google用链接到该网页的数量和质量作为评价网页的重要性的指标。Google查询的全过程通常不超过半秒，其主要过程是网络服务器先将查询发送到索引服务器，索引服务器所包含的内容与书本索引目录相似，即说明哪些网页包含与查询匹配的文字；然后将查询的相关结果传输到文档服务器，生成描述每个搜索结果的摘录；最后将结果返回到用户。PageRank算法主要是将检索出来的网页按照重要程度排序，将一些比较重要的网页放在搜索结果的前面。与HITS相比，PageRank在

7、稳定性和适用性上更胜一筹，更适合大规模的搜索引擎。本文先简单介绍搜索引擎的基本框架，用以了解搜索引擎的基本工作原理，接着介绍PageRank算法和随机冲浪模型，最后简述用幂法求其重要性排序。2 简介搜索引擎2.1 搜索引擎的基本框架 从本质上说，搜索引擎是一个资料检索系统，搜索引擎拥有一个资料库（即互联网页面），用户提交一个检索条件（例如关键词），搜索引擎返回符合查询条件的资料列表。这样，搜索引擎有两个核心问题：1、建立资料库；2、建立一种数据结构，可以根据关键词找到含有这个词的页面。 第一个问题一般是通过一种叫做爬虫的特殊程序实现的。爬虫就是从一个页面出发，通过HTTP协议通信获取这个页面的

8、所有内容，把这个页面url和内容记录到资料库，然后分析页面的链接，再去分别获取这些链接链向的页面内容，将链接到的页面内容记录到资料库然后再分析这个页面的链接，一直重复这个过程，就可以将整个互联网的页面全部获取下来（当然这是理想的情况，要求整个web是一个强连通图，并且所有页面的http协议允许爬虫抓取页面，为了简单，我们假设web是一个强连通图，且不考虑robots协议）。下图为通用爬虫框架的基本结构图。图2-1 通用爬虫框架 Google至少包含两套不同目的的爬虫系统，一套被称为Fresh Bot，主要考虑网页的时新性，对于内容更新频繁的网页，目前可以达到以秒的更新周期；而另外一套被称之为D

9、eep Crawl Bot ，主要针对其他更新不是那么频繁的网页抓取，以天为更新周期。下图为Google的两套爬虫系统基本结构示意图。 图2-2 Google的两套爬虫系统 第二个问题是通过一种叫倒排索引来实现的，倒排索引是搜索引擎用来快速查找包含某个单词的文档集合的数据结构，抽象来说倒排索引是一组key-value结构，key是关键词，value是一些页面编号集合（假设资料库中每个页面都有唯一编号），表示这些页面含有这个关键词。 例如我们要查询“张三 微博”：搜索引擎获取“张三 微博”查询条件后，将其分为“张三”和“微博”两个词；接着从倒排索引中找到“张三”所对应的集合，假设是1,2,4,6

10、,8,12；“微博”所对应的集合试试1,3,4,7,9,12,15,26；将这两个集合做交运算，结果是1,4,12，最后从资料库中将1、4、12所对应的页面返回给用户就可以了。 PageRank算法的主要作用是对检索出的结果进行重要性排序，即对上例中的1、4、12进行排序。3 PageRank算法3.1 PageRank算法简介 PageRank算法是Google专有的算法，用于衡量特定网页相对于搜索引擎中的其他网页而言的重要程度。它是由Larry Page和Sergey Brin在20世纪90年代后期提出的，是Google用来标识网页的等级或重要性的一种方法，是一种在搜索引擎中根据网页之间相

11、互的链接关系计算网页排名的技术，其网页等级为1到10级，级别越高，表示越重要。其实现了将链接价值概念作为排名因素，将对页面的链接看成投票，指示了重要性。网页分级是基于“从许多优质的网页链接过来的网页必定还是优质网页”的回归关系,来判定所有网页的重要性.目前为了能够提高搜索引擎的效率，人们已经进行了许多相关方面的研究，其中有侧重于缩短收敛时间的，也有侧重于提高查询结果的准确性。其中也有人提出了分块式PageRank收敛算法。该算法将网络中的网页划分成不同的数据块，然后计算块内PageRank值和块间PageRank值，最后通过两种PageRank值求得最终向量值，其用分块的方式降低了矩阵的维数，

12、有效减少了原算法中的0元素和0相乘计算，从而达到了减少系统运行时的时空开销目的。3.2 PageRank算法原理 对于某个互联网网页A来说，该网页的PageRank值计算基于以下两个基本假设： 数量假设:在Wed图模型中，如果一个页面节点接收到的其他页面指向的入链数量越多，那么这个页面就越重要。质量假设：指向页面A的入链质量会有所不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，页面A就越重要。PageRank算法使用了投票思想。PageRank依靠的是网民对站点的支持率，利用大量的链接结构表明某个单独页面的价值。它就像是一个由互联网上所有其他页面发起的投票

13、，并由此来决定一个网页的重要性，一个指向某页面的链接代表一张投票。例如，有四个页面ABCD，其中页面A只有链向页面B，页面C链向页面A和页面D，假设最初每个页面都同等重要，页面B跟页面D都获得了一票，但链向页面B的页面A只有一条出链，而链向页面D的页面C有两条出链，这样页面C的投票重要性就会被平分，所以，同样只有一票的页面B跟页面D，页面B显得更重要一些。即链入的页面数量跟质量决定了页面的重要性，如果链入的数量越多且质量越高，则页面的重要性分数越高。3.3 PageRank算法 基于前面的两个假设，我们将网络上网页之间的关系抽象成有向图，即网页可以看做图中的节点，网页之间的超链接看作图中的有向

14、边。用表示页面1到页面的重要性分数，则每个页面的重要性分数可以由式子 （3-1）表示，其中代表页面向外的链接数，为页面的反向链接的集合。记，则网络中所有页面的关系可以表示成，其中为邻接矩阵。我们也可以直接根据图可以写出它们的邻接矩阵，其中如果页面链接到页面，则，否则。因为页面跳到他所有链接的页面中的一个的概率是一样的，所以将页面的PageRank值平均分配到它所链接的页面上，即对矩阵的每一行做归一化处理，得矩阵。但是PageRank算法主要关注的不是页面链接到哪些页面上，而是被哪些页面链接，所以PageRank算法中的矩阵是的转置，即，其称为转移概率矩阵。网页的重要性分数就是矩阵的特征值为1所

15、对应的特征向量。 下面证明矩阵有值为1的特征值。定义1：如果方阵的每一项元素都是非负的且每列元素相加和为1，则称方阵为列随机矩阵。没有悬挂结点的网络所对应的矩阵是列随机的。命题1：每个列随机矩阵都有一个值为1的特征值。证明：记为一个的列随机矩阵，为维列向量且其分量都等于1。因为矩阵和有相同的特征值；又因为是列随机的，可以容易得出，所以1是的一个特征值，即1也是的特征值。 2 1 3 4图3-1 简单的网络示意图 例1：如上图所示，求其页面的重要性排序。解：由上可得， 求出矩阵的特征值为1的特征向量。再归一化得到，。 所以得出页面4最重要，页面2次之，再到页面3，最后是页面1。虽然页面2获得了其

16、他所有页面的链接，但却不是最重要的。页面2只有链接到页面4，所以将所有投票投给页面4，再加上页面1的投票，所以使页面4变成最重要的。 但是使用上述方法进行网页排名的时候会出现一些问题。这里我们讨论两个问题:非一性排名跟悬挂节点。 非唯一排名。当把网络抽象成有向图是由几个互不相连的子图构成时，此时其矩阵有多个值为1的特征值，所以导致排名不唯一。例2：在图一中在加两个页面，页面5和页面6，使其两两互相链接，如下图。 5 21 6 43图3-2 网络简单示意图 相应的矩阵为： ， 求出值为1的特征值有两个线性无关的特征向量，即和，此时排序就不唯一了。 悬挂节点。悬挂网页可能是一个pdf文件或是网页向

17、外指向的超链接还没有被搜索引擎搜索到，即悬挂节点是指没有出链的网页节点。包含悬挂节点的网络生成的矩阵会包含一个或更多个全为0的列。在这种情况下，是列子随机的，也就是说矩阵的每列分量之和小于或等于1。这种矩阵的所有特征值小于或等于1，但1并不一定要是矩阵的一个特征值。然而，网络中有悬挂节点的网页可以使用类似的技术进行排名。相应的子随机矩阵必须有一个正的特征值以及对应的非负特征向量用来进行网页的排名。4 随机冲浪模型 PageRank算法原理中有个重要的假设：所有的网页形成一个闭合的链接图，除了这些文档以外没有其他任何链接的出入，并且每个网页能从其他网页通过超链接达到但是在现实的网络中，并不完全是

18、这样的情况当一个页面没有出链的时候，它的PageRank值就不能被分配给其它的页面。同样道理，只有出链接而没有入链接的页面也是存在的但PageRank并不考虑这样的页面，因为没有流入的PageRank而只流出的PageRank，从对称性角度来考虑是很奇怪的有时候也有链接只在一个集合内部旋转而不向外界链接的现象在现实中的页面，无论怎样顺着链接前进，仅仅顺着链接是绝对不能进入的页面群总归是存在的例如有四个页面，页面A链向页面B，页面B链向页面C，页面C链向页面D，最后页面D链向页面A，四个页面链接构成一个环，则页面的PageRank值在这个环内一直传递，就不能将值传递出去，会导致PageRank值

19、沉淀现象。 PageRank技术为了解决这样的问题，提出用户的随机冲浪模型：用户虽然在大多数场合都顺着当前页面中的链接前进，但有时会突然停止前进重新打开浏览器随机进入到完全无关的页面Google认为：用户在85的情况下沿着链接前进，但在15的情况下会跳跃到无关的页面中用公式表示相应的转移概率矩阵为 （3-1）其中，为分量全为l的维列向量，从而为全1矩阵，d(0，1)为权重因子，在实际中Google取d=085。也就是说，在随机冲浪模型中，求各个页面等级值PageRank 的问题变成了求正矩阵形的最大特征值所属的特征向量问题 首先证明有值为1的特征值？ 证明：因为d(0，1)，所以可以。又有，所

20、以是正的列随机矩阵，故有值为1的特征值。 可以证明的值为1的特征值只有唯一一个。由此可以知道无论是由多少个子网组成的网络，其只有唯一一个排名。 例3：用替换例1中的，并计算其排名。（d取0.85） 得到重要性分数，与例1有相同的排名，只是分数略有不同。例4：用替换例1中的，并计算其排名。（d取0.85） 求得，归一化得重要性分数为，。此时，用计算有唯一的排序，即允许我们比较不同子网站的网页。5 幂法 PageRank值的计算步骤： 初始阶段:网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的迭代计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算

21、进行，网页当前的PageRank值会不断得到更新。 在每一轮中更新网页PageRank值的计算方法：在每一轮更新页面的PageRank值的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接就获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank值。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank值计算。 PageRank算法在最初的时候赋予每个网页相同的重要性分数，通过迭代递归计算来更新每个页面节点的PageRank值，直到PageRan值稳定为止。基于前面的计算步骤，下面介绍用幂法求特征向

22、量。用幂方法计算矩阵的特征向量的大致思想是：幂法是一种计算矩阵主特征值（按模最大的特征值）及对应特征向量的迭代方法，特别是用于大型稀疏矩阵。若矩阵有特征值，即求及其所对应的特征向量，因为邻接矩阵的最大特征根为1，所以用幂法迭代出的结果即为网页的重要性分数。 1 从向量开始，根据公式（即）不断迭代，直到趋于稳定，其中为任意一个非零初始向量，为转移概率矩阵，即上文中的。向量可以看作是矩阵的最大特征值所对应的特征向量。然而，取决于特征值的大小，向量可能是没有边界或者接近于0向量。然而，为了确保幂方法在一个合理的范围内收敛，一个重要的要求是矩阵的最大特征值为1.也就是说，的多项式特点应该是这样的形式，

23、其中的度为,且不能整除. 或者，矩阵的特征值对应的特征向量应该具有除了特征向量在中的其他不一般性。 2 3图5-1 网络简单示意图 例6：如上图，可以得出，其中d=0.85.取则,与相差较大，继续迭代。继续迭代，.，一直迭代直到于收敛。将归一化得；若直接取，其直接收敛于。可以求出的特征值为1所对应的特征向量，归一化得。 在计算机实现的过程中，由于机器运算的特性，收敛的过程使用递归运算更为有效，因此使用递归运算式，算法表示如下：function =PowerMethod();k=1;Repeat ;k=k+1;Until 其中为设定的阈值，当小于时，便认为已达到收敛了。6 结论 PageRank

24、算法的优缺点。 优点：PageRank算法是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。 缺点： 1.人们的查询具有主题特征，PageRank算法忽略了主题相关性，导致结果相关性和主题性降低，会产生主题漂移现象。这样如果重要性高的排在前面的页面和搜索主题无关同样也是没有意义的，为此，Google使用了完善的超文本匹配分析技术，使得能够检索出重要而正确的网页。2. 旧的页面等级会比新页面高，因为即使是非常好的新页面也不会有很多外链，除非它是某个站点的子站点。新的页面往往没有较多的页面链向它，所以会导致其PageRan

25、k值会相对旧的页面小，这时有的新的页面是比较重要的，却排在比较靠后的位置。 PageRank算法主要根据网页上的网页的外部链接站点的数量和质量及链接页面等级决定PageRank值的大小，由PageRank值来决定改网页在搜索引擎中的排名，却忽略了链接页面对查询条件的主题相关性。如果该页面只是在内容中出现了关键词，可主题内容与该关键词相差很大，也会因其存在的页面PageRank值大而获得一个比较靠前的排名，这对用户来说是没有意义的。所以决定网页排名不但需要考虑网页的页面等级，更要考虑网页的页面主题内容与查询主题的相关性是否对称。7 致谢词 本论文是在储理才老师悉心指导下完成的，感谢老师在忙碌的工

26、作中，抽出时间来解答我的问题，审查修改我的论文，给予我指导与帮助，使我能够顺利完成论文。在此，谨向老师表示崇高的敬意和衷心的感谢！参考文献1 张巍.基于PageRank算法的搜索引擎优化策略研究D.四川：四川大学，2005.2 吕克强.Web超链接分析及其在搜索引擎中的应用研究D.北京:中国石油大学，2008.3 张俊林.这就是搜索引擎：核心技术详解M.北京：电子工业出版社，2012.4 吴秋月、何江宏.Google矩阵和它的性质J.大学数学，2006,22(6)：139-143.5 冯振明.分块式PageRank收敛算法及其改进D.南京:河海大学，2006.6 宿.PageRank算法Z.7 Kurt Bryan、Tanya Leise.The $25,000,000,000 Eigenvector:The Liner Algebra behind GoogleJ.Society for Industrial and Applied Mathematics,2006,48(3):569-581.8 赵国、宋建成.Google搜索引擎的数学模型及其应用J.西南民族大学学报（自然科学版），2010，36(3):1-4.9 冯振明.Google核心PageRank算法深讨J.计算机技术与发展，2006,16(7):3-6.10 Arasu A.Pagerank c