搜索引擎的网页排名问题数学实验报告.doc
《搜索引擎的网页排名问题数学实验报告.doc》由会员分享,可在线阅读,更多相关《搜索引擎的网页排名问题数学实验报告.doc(15页珍藏版)》请在咨信网上搜索。
1、精品文档实验七 搜索引擎的网页排名问题姓名:蒋芬 学号:1012211139一、 实验目的本实验涉及线性代数的一些知识,通过搜索引擎的排名算法介绍了正矩阵,列随机矩阵的一些性质,特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.二、 问题的提法今天,如果你打算了解某种信息,多半会利用互联网.在google首页搜索栏输入一些关键词,跟此有关的网页会很快迅速显示出来,也许只用不到一秒钟.而且这些网页会依照某些次序排列,通常是越靠前的越重要(也许是关注的人越多).那么google的搜索引擎是如何做到这一点的呢?三、 背景介绍随着互联网的高速发展,网络已经成为现代人生活的一个重要组成部分. 从网
2、络上搜索信息已成为继电子邮件后的第二大互联网应用. Google搜索引擎是世界上最大的免费搜索引擎. 目前,它对超过80多亿个网页进行整理,每天需提供的查询服务超过2亿次.当我们在Google搜索引擎中输入一些关键词后,Google会在很短的时间内从数以亿计的网页中搜索与关键词匹配的网页,并给网页的显示顺序. 事实上,Google会定期地对互联网上所用的网页进行搜索,并将结果保存在自己的数据库中. 所以,表面上看是我们通过Google进行网上搜索,而实际是在Google网站的数据库里进行搜索. 那么Google又是如何给出网页的排名情况的呢?这就要从搜索引擎排名算法说起. Google Pag
3、eRank是Google独有的搜索引擎排名算法, 作用是衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度. 它是由Larry Page和Sergey Brin在20世纪90年代后期发明的. Page Rank实现了将链接价值概念作为排名因素. 我们知道Google 工具条上有一个绿色的PageRank标尺,就是用来指示网站的链接广泛度的。 PageRank值从0到10.这里的链接包括网站内部链接、导出链接和导入链接,其中最重要的是导入链接. Google通过统计这些链接的质量和数量来给网站确定PageRank值,值越高排名也就越高.如果你想查看自己站点的PR值,可以访问: ,下载Goo
4、gle的工具栏,就可以看到自己网站的PR值. Google PageRank现在还在使用中,不过已经是一个更大的系统中的一部分. 其他部分还包括语言模块,查询模块,时间模块,个性化模块等.PageRank算法主要用到了线性代数的一些知识,包括正矩阵,列随机矩阵的一些性质,特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.四、 数学模型有向图的定义数学中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物,用连接两点的线段(直的或曲的)表示两个事物的特定的联系,就得到了描述这个“图”的几何形象.记这些点为,而它们的连线用表示,记为,那么一个图是指一个二元组,其中:
5、1) 是非空有限集,称为顶点集,其中元素称为图的顶点.2)2)是顶点集中的无序或有序的元素对组成的集合,称为边集,其中的元素称为边. 若图G中的边均为无序对,称G为无向图,若图G中的边均为有序对,称G为有向图.12345图7.1这样,假定某个网络包含n个网页,每个网页用一个数字k标记,。则该网络可以用一个有向图来表示,其中每个顶点看成是一个网页,边(箭头)表示从一个网页到另一个网页的链接. 当网页j 上有连到网页i的链接,则称网页j为网页i的导入链接,而称网页i为网页j 的导出链接. 比如,图7.1就可以看成是一个包含5个网页8个链接的小型网络,其中网页3有3个导入链接. 邻接矩阵有向图的邻接
6、矩阵为,其中 (7.1)对于图7.1所示的有向图,其邻接矩阵为我们用表示某个网络中第k个网页的重要性,是一个非负的正数,若则表示第i个网页的重要性大于第j个网页的重要性.五、 排名问题的算法. 简化的PageRank算法一种简单的衡量某个网页重要性的方法是看谁的导入链接最多. 由图7.1可得:,. 从而得到第3个网页的重要性最大,第2,4个网页的重要性其次,而第1,5个网页的重要性最小.然而上述排名算法显然不能令人满意,它不能区分第2,第4两个网页和第1,第5两个网页哪个更重要. 一种改进的做法是除了考虑导入链接的数量外,还应考虑导入链接的质量,即来自一个重要性相对较高网页的链接可以增加该网页
7、的重要性. 用数学语言可表达如下:若网页j包含个导出链接,其中的某个链接到了网页k (即第k个网页),则该链接赋给网页k的重要性为,即网页j的重要性被平分到其每个导出链接上. 令(注意这里的数字是表示网页的标记)为链接到网页k的那些网页的集合,则网页k的重要性可以由下式得到 (7.2)如果引进矩阵A称为链接矩阵,其元素那么(7.2)式等价于,也即等价于矩阵方程 (7.3)其中.不难验证:其中为邻接矩阵,为对角矩阵.注意方程(7.3)的解就是矩阵A对应于特征根1的特征向量,若规定,则对应的解就是矩阵A对应于特征根1的归一化特征向量.定义1:若一个方阵的所有元素均非负,且每列的和均为1,则该方阵称
8、为列随机矩阵.由上述定义可知,若某个网络的每个网页都有导出链接,则其链接矩阵必为列随机矩阵.定理1:列随机矩阵一定存在特征根1.证明:记A是一个n阶的列随机矩阵,e是一个n维的元素全为1的列向量。由定义1,易知,即1是矩阵的特征根。又因为A与有相同的特征根,所以A一定存在特征根1。例如,由图7.1所示的小型网络,可得:利用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. 再键入 abs(V(:,1)/
9、norm(V(:,1),1)则可以得到A对应于特征根1的归一化特征向量.这说明按照上述方法的网页排名为:。然而,上述方法仍然存在以下不足:(1)若网络中存在导出链接数为0的网页,则链接矩阵A中必存在某列全为0. 此时,可验证A的所有特征值的模都小于等于1,且1不一定是A的特征值. 解决这个问题的方法是采用所谓的Perron 特征向量来进行排名,即A中一定存在一个正的特征值,其对应的正的归一化特征向量称为Perron 特征向量. 我们在这里不讨论这种方法的理论依据,而通过例子来说明算法.我们来考察由图7.2所示的小型网络,易见网页3无导出链接1324图7.2 其对应的链接矩阵为:利用MATLAB
10、: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)输出的四个特征值的模都小于1,且1不是A的特征值。所以,无法利用特征值1对应的特征向量对网页进行排名。(2)存在无法确定排名的情况.考察由图7.3所示的小型网络12345图7.3该网络由两个互不相连的子网络构成,其对应的链接矩阵A为:利用MATLAB计算可得这个矩阵有1和1两个二重特征根,还有一个单重特征根0,特征根1对应的两个线性无关的归一化特征向量为:,。显然,利用上述特征向量无法对网页进行排名. 改进的PageRank算法只要对(7.2)式稍作改动,就可以
11、解决由于网页重要性相等而无法确定排名的问题。令n表示网络中包含的网页数,p称为加权因子其取值在0和1之间。则网页k的重要性可以由下式给出: (7.4)上式亦可以用如下形式的矩阵方程来表示: (7.5)其中s是一个元素全为的列向量. 若规定并记S是一个元素全为的n阶方阵,则由可得: (7.6)关于矩阵方程(7.6),可以证明:若A是列随机矩阵,则M亦是列随机矩阵.在的约束条件下,上述方程有唯一解. 其解为矩阵M特征根1所对应的归一化特征向量. 这样我们就可以解决这类网络的网页排名问题。回到图7.3所示的小型网络,n=5,p=0.85,利用MATLAB:p=0.85;A=0 0 0 0 0;0.5
12、 0 1 0 0;0.5 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)可以得到M的最大正特征根为1,进而可得其对应的归一化特征向量为,利用该特征向量就可以对不同子网络中的网页进行排名. 其对应的网页排名为:.若矩阵A中存在某列全为0,即存在j,aij=0,任意i,则规定矩阵M对应该列的元素均为1/n,这样,M就仍然是列随机矩阵。以图7.2所示的小型网络为例,通常取p=0.85,那么用MATLAB,易得 (7.7)而M的模最大的正特征值为1,对应的归一化特征向量为这样我们得到. . PageR
13、ank算法-幂法值得注意的是,前面的作为例子的小型网络的规模微小,用数学软件直接求解矩阵方程x=Ax或求A的特征根和特征向量都无困难. 当问题的规模很大,甚至A的阶数可能达到上万甚至上亿时,就必须寻找合适的数值计算方法. 下面我们介绍用于计算矩阵特征值的幂迭代算法。 假设矩阵A的特征值满足条件,其中是特征方程的实根,相应的特征向量可以取成实向量,对于任意给定的非零初始向量,迭代格式 (7.8)称为计算矩阵特征值的幂法. 假设A有n个线性无关的特征向量,则初值可以用它们线性表示,即 (7.9)从而幂法的迭代由下式给出 (7.10)若对所有的,均有. 所以只要,当k足够大时,由(7.9)式可得 ,
14、 (7.11) (7.12)即有 (7.13)而,故有 (7.14)这意味着,最终会趋于. 但是,直接采用幂法往往会导致迭代序列趋向于无穷大(而的绝对值小于1时则会趋于零).故在每次迭代是应当对进行归一化处理,所以上述算法可以改写为 (7.15), 其中 (7.16)例如再次考察图7.2所示的小型网络,相应的矩阵M如(7.7)式所示.那么给定初始向量,利用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.
15、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经计算得到幂法的迭代20次的序列如下: 表7.1kk07110213315416517(后两次的迭代结果完全相同,故未列出),从上表中可以看到,经过不足20步迭代,就可以得到与前面方法同样的排名结论.注意在网页数量很大时,迭代运算需要更多有效数字,迭代次数一般也会更多,才能使得归一化特征向量的各分量有序从而确定网页排名.六、实验任务1. 在改进的PageRank算法讨论图7.2所示的小型网络时,我们取p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索引擎 网页 排名 问题 数学 实验 报告
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。