搜索引擎的网页排名.pptx

搜索引擎的网页排名.ppt,内容提要,Google,网页排名的数学原理,图与网络,回顾线性代数的相关内容,某些有关矩阵特征值知识的介绍,计算矩阵特征值的幂迭代法,Matlab,中矩阵运算,实际问题,现今，若你打算了解某种信息，多半会利用,互联网，在,Google(,或百度)搜索引擎中输入一些,而且这些网址会依照某些次序排列，通常是越靠,关,键词后，与此有关的网页地址会很快显示出来，,前的越重要(意味着关注的人越多).那么,google,的搜索引擎是如何做到这一点的呢？,准备知识,而数组称为,边,(,或,连线,),在数组两个元素有次序时,联系(,用数组,表示,),称为,图,D,元素称为,顶点,，,非空集合,以及其中元素间的,图的表示是十分形象的，,则图称为,有向图,例1:右图就表示了有4个顶点,6条边的有向图,1,2,3,4,邻接矩阵,将有向图,转化为代数形式表示,则称矩阵,G=,g,ij,为,邻接矩阵,例1的4个顶点6条连线,的有向图的邻接矩阵为,对于有向图,D,，定义,1,2,3,4,设某个网络包含,n,个网页，每个网页用一个,网络与有向图,数字,k,(1,k,n,),标记，则该网络可用一个有向,则表示网页间链接，当有网页,j,上有连到网页,i,图表示，其中每个顶点看成是一个网页，而边,的链接，称网页,j,为网页,i,的导入链接，而称网页,i,为网页,j,的导出链接,例1的有向图可表示含4个网页的小网络,网,页1、4各有一个导入链接,2、3各有2个导入链接,1,2,3,4,简化的,PageRank,算法,最简方法,看谁的导入链接更多,1,2,3,4,5,若用正数,x,k,表示某网络中第,k,个网页的重要,性，,那么,x,i,x,j,表示,网页,i,比网页,j,更重要,例,2,导入链接数：,x,3,=3,x,2,=,x,4,=2,x,1,=,x,5,=1,问题：1）未考虑导入链接网页的重要性,2)并列数能否区分(例如2、4),调整,增加考虑网页的质量因素,设网页,j,包含,n,j,个导出链接，则可认为网页,j,的重要性被平分赋予其导出链接的网页上，这些,网页均获得重要性数值为,记,L,k,为链接到网页,k,的那些网页标记的集合,那么,引进链接矩阵,A,，其元素,那么记,，就有,这方程的解就是矩阵,A,对应于特征根1的,特征向量,这意味着,我们要求的体现网页重要性的向量,考虑特征向量构成线性空间，规定,x,为矩阵,A,对应于特征根1的,归一化特征向量,注:,将邻接矩阵的每列除以该列元素之和就得到,A,方程有解吗,若一个方阵的所有元素非负，且每列的和均,为1，则该方阵称为,列随机矩阵,定理1：列随机矩阵一定存在特征根1,若网络的链接矩阵,A,是列随机矩阵,方程可解,例2网络的,链接矩,阵,A可解此方程,使用,Matlab,A=0 0.5 0 0 0;0.5 0 1 0 0;0.5 0 0 0.5 0.5;0 0.5 0 0 0.5;0 0 0 0.5 0;,V,D=eig(A);,diag(D),键入,会得到,A,的特征值(第1个是1).再键入,abs(V(:,1)/norm(V(:,1),1),得到对应1的,特征向量,依然有问题,1）网络的链接矩阵有某列元素全为零,(存在导出链接数为0的网页),可能特征值中不含1！,1,3,2,4,例3,Matlab,求特征值,A=0 0 0 0.5;1/3 0 0 0;1/3 0.5 0 0.5;1/3 0.5 0 0;,V,D=eig(A);,diag(D),2）依然可能出现无法排名的情况,1,2,3,4,5,例4,A=0 0 0 0 0;1/2 0 1 0 0;1/2 1 0 0 0;0 0 0 0 1;0 0 0 1 0;,V,D=eig(A);,diag(D),利用,Matlab,特征值1对应的归一特征向量(两个)，均无法排序,改进的,PageRank,算法,修改方程为,其中,P,是加权因子(小于1的正数,常取0.85)，这,的赋予，还有一个最低数据(即使无导出链接),意味着标志网页重要性的数据大部分来自各网页,这样若以,S,表示所有元素均为,的方阵，依然,要求,x,是归一化的，则,Sx,就是元素均,的列向量,记,M,=,p,A,+(1,-,p,),S,方程为,x=Mx,(*),情况讨论,1),A,是列随机矩阵,易见,M,也是列随机矩阵，且此时,(*),有,唯一归,一化解,也就是,M,的特征根1所对应的特征向量,考虑原来方法未能解决的例4，,n,=5,取,p,=0.85,利用,M,求特征值1和相应特征向量,就可以解决排名问题,p=0.85;,A=0 0 0 0 0;1/2 0 1 0 0;1/2 1 0 0 0;0 0 0 0 1;0 0 0 1 0;,S=ones(5,5)/5;,M=p*A+(1-p)*S;,V,D=eig(M);,diag(D),使用,Matlab,得到特征值1(第2个)，再由,abs(V(:,2)/norm(V(:,2),1),说明,x,2,=x,3,x,4,=x,5,x,1,（,并列合理吗?）,2),A,有某列元素全为零,M,对应的列元素全为,(1,p,)/,n,不是列随机矩阵,解决方法是,可把这列元素都换成1/,n,，得到列随机矩阵,去求特征根1所对应的归一化特征向量,也可直接求,M,的最大的正特征根，同时求得,对应的归一化特征向量,得到的排名结果是相同的,(理论：Perron-Frobnius定理),例3的排名实现-使用,Matlab,p=0.85;,A=0 0 0 1/2;1/3 0 0 0;1/3 1/2 0 1/2;1/3 1/2 0 0;,S=ones(4,4)/4;,M=p*A+(1-p)*S;,V,D=eig(M);,diag(D),M1=M;,M1(:,3)=ones(1,4)/4,V1,D1=eig(M1);,diag(D1),直接对,M,修改,M,PageRank,算法-幂法,当问题的规模很大，甚至,A,的阶数可能达到,幂迭代算法,上万甚至上亿时，必须寻找合适的数值计算方法,设矩阵,A,的特征值满足,1,是特征方程的实根，相应的特征向量,v,1,可以取,实向量,则任给初始向量,x,0,，幂法迭代格式为,x,k,=,Ax,k-1,假设,A,有,n,个线性无关的特征向量,v,i,则,初值可用它们线性表示，即,x,0,依照幂法,说明,x,k,最终趋于,v,1,正式迭代格式,防止迭代使数据趋无穷大或无穷小,其中,对例3，取,x,0,（0,0,0,1),T,只需迭代,不足20次，就可以得到与前面方法同样的结果,用,Matlab,可以容易实现这计算,M=0.0375,0.0375,0.0375,0.4625;0.32083,0.0375,0.0375,0.0375;0.32083,0.4625,0.0375,0.4625;0.32083,0.4625,0.0375,0.0375;,x(:,1)=0,0,0,1;,y(:,1)=0,0,0,1;,for k=2:20,y(:,k)=M*x(:,k-1);,x(:,k)=y(:,k)/norm(y(:,k),1);,end,x,使用,Matlab,实验任务见教材,补充说明,本例所介绍的内容有多种应用,再举一例,实际问题循环赛的名次,若干球队进行两两交锋的循环赛，假设每场,必决出胜负,现有6对比赛结果如下,如何排名呢?,A,B,C,D,E,F,A,1,-1,1,1,1,B,-1,-1,1,1,1,C,1,1,1,-1,-1,D,-1,-1,-1,1,1,E,-1,-1,1,-1,1,F,-1,-1,1,-1,-1,表中各行分别表示其左端的球队胜负情况，1表示胜，1表示负,