Google搜索引擎的数学模型及其应用.pdf_第1页
Google搜索引擎的数学模型及其应用.pdf_第2页
Google搜索引擎的数学模型及其应用.pdf_第3页
Google搜索引擎的数学模型及其应用.pdf_第4页
Google搜索引擎的数学模型及其应用.pdf_第5页
已阅读5页,还剩2页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

西南民族大学学报 自然科学版 第 36 卷第 3 期 Journal of Southwest University for Nationalities Natural Science Edition May 2010 收稿日期 2010 03 13 作者简介 赵国 1979 男 硕士 西南民族大学计算机科学与技术学院讲师 主要研究方向为金融数学 数学模型 基金项目 西南民族大学青年项目 文章编号 1003 2843 2010 03 0480 07 Google 搜索引擎的数学模型及其应用 赵国 宋建成 西南民族大学计算机科学与技术学院 四川成都 610041 摘 要 该文在阐明 Google 搜索引擎中关键的页面等级算法 PageRank 原理的基础上 分析了 PageRank 算法的随机冲 浪模型 并着重讨论相应的数学模型在足球队排名问题 1993年全国大学生数学建模竞赛B题 中的应用 具体做法是综 合考虑各队的比赛成绩 为每支球队计算相应的等级分 Rank 然后根据各队的等级分高低来确定名次 考虑到竞技比 赛结果的不确定性 最后建立了等级分的随机冲浪模型 分析表明等级分排名结果具有良好的参数稳定性 并且可以成 功地处理数据缺损方面的困难 关键词 搜索引擎 Google PageRank 算法 随机冲浪模型 足球队排名问题 中图分类号 O141 4 文献标识码 A 1 引言 据统计 在短短 20 多年的时间里 Internet 中产生的信息量相当于人类过去 100 年产生的信息总量 而且 Internet 上的信息量正以几何级数递增 搜索引擎已经成为人们进行 Internet 信息资源搜索必不可少的工具 在 众多的搜索引擎中 Google 搜索引擎以其雄厚的技术为支撑 凭借其强大的检索功能和高质量的检索服务 逐 渐脱颖而出 Google 搜索引擎是由斯坦福大学 Sergey Brin 和 Lawrence Page 共同设计的 1 它是目前功能最强的 搜索引擎 通过对 80 亿网页进行整理 Google 可为世界各地的用户提供所需的搜索结果 而且搜索速度极快 通常不到半秒 每天可提供约 3 亿次查询服务 图 1 Google 搜索引擎的工作原理示意图 图 2 Internet 网络的拓扑结构 Google 的优势在于掌握的信息量以及检索模型和检索速度 传统的搜索引擎在很大程度上取决于文字在 网页上出现的频率 Google 使用 PageRank 技术检查整个网络链接结构 并确定哪些网页重要性最高 然后进 行超文本匹配分析 Hypertext Matching Analysis 以确定哪些网页与正在执行的特定搜索相关 在综合考虑整体 481 第 3 期 赵国等 Google 搜索引擎的数学模型及其应用 重要性以及与特定查询的相关性之后 Google 可以将最相关最可靠的搜索结果放在最前面 2 Google 搜索引擎的数学模型 Google 拥有多项专利技术 其中 PageRank 算法是关键技术之一 它奠定了 Google 强大的检索功能及提供 各种特色功能的基础 虽然Google每天有很多工程师负责全面改进Google 系统 但是仍把PageRank 算法作为 所有网络搜索工具的基础结构 2 2 1 PageRank 原理 PageRank 算法是 Google 搜索引擎对检索结果的一种排序算法 它的基本思想主要是来自传统文献计量学 中的文献引文分析 即一篇文献的质量和重要性可以通过其它文献对其引用的数量和引文质量来衡量 也就是 说 一篇文献被其它文献引用越多 并且引用它的文献的质量越高 则该文献本身就越重要 Google 在给出页面 排序时也有两条标准 一是看有多少超级链接指向它 二是要看超级链接指向它的那个页面重要不重要 这两 条直观的想法就是 PageRank 算法的数学基础 也是 Google 搜索引擎最基本的工作原理 PageRank 算法利用了互联网独特的超链接结构 在庞大的超链接资源中 Google 提取出上亿个超级链接页 面进行分析 制作出一个巨大的网络地图 具体的讲 就是把所有的网页看作图里面相应的顶点 如果网页A有 一个指向网页 B 的链接 则认为一条从顶点 A 到顶点 B 的有向边 这样就可以利用图论来研究网络的拓扑结构 PageRank 算法正是利用网络的拓扑结构来判断网页的重要性 具体来说 假如网页 A 有一个指向网页 B 的 超链接 Google 就认为网页 A 投了网页 B 一票 说明网页 A 认为网页 B 有链接价值 因而 B 可能是一个重要的 网页 Google 根据指向网页 B 的超链接数及其重要性来判断页面 B 的重要性 并赋予相应的页面等级值 PageRank 网页 A 的页面等级值被平均分配给网页 A 所链接指向的网页 从而当网页 A 的页面等级值比较高 时 则网页 B 可从网页 A 到它的超链接分得一定的重要性 根据这样的分析 得到了高评价的重要页面会被赋 予较高的网页等级 在检索结果内的排名也会较高 页面等级值 PageRank 是 Google 表示网页重要性的综合 性指标 而且不会受到不同搜索引擎的影响 当然 重要性高的页面如果和检索关键词无关同样也没有任何意义 为此 Google 使用了完善的超文本匹 配分析技术 使得能够检索出重要而且正确的网页 2 2 PageRank 算法 PageRank 算法的具体实现可以利用网页所对应的图的邻接矩阵来表达超链接关系 为此 首先写出所对应 图的邻接矩阵A 为了能将网页的页面等级值平均分配给该网页所链接指向的网页 对各个行向量进行归一化 处理 得矩阵A PageRank 算法的矩阵是将归一化矩阵A转置所得矩阵 T AW 这样形成的矩阵W被称为转 移概率矩阵 它的各个列向量之和为全概率 1 各个行矢量表示状态之间的转移概率 转移概率矩阵与 Markoff 过程有着密切的联系 3 转置的理由是 PageRank 算法并非重视链接到多少页面 而是重视被多少页面链接 各 个网页的页面等级值 PageRank 的计算 就是求这个转移概率矩阵 W 的最大特征值所属的特征向量 现在以前面给出的三个页面之间的超链接关系为例 说明 PageRank 算法如何计算给定网页的页面等级值 PageRank 从而定量地知道哪些网页是最重要的 为利用网页所对应的图的邻接矩阵来表达链接关系 首先写 出所对应图的邻接矩阵 001 100 110 A 为了能将网页的页面等级值平均分配给该网页所链接指向的网页 对各个行向量进行归一化处理 得 第 36 卷 482 西南民族大学学报 自然科学版 001 100 2 1 2 1 0 A 将归一化所得的矩阵A转置 所得到的转移概率矩阵 ij wW 为 012 1 002 1 100 T AW 现给每个页面 i P一个 PageRank 值 i x 这些 PageRank 值应该由链接到该页面的那些页面的 PageRank 值确 定 即指向 i P的那些页面的页面等级值之和应该与 i P的页面等级值 i x成正比 设共同的比例系数为 则有下 面的线性方程组 i j jij xxw 3 1 3 2 1 i 1 令 T xxxx 321 为页面等级值组成的列向量 则由矩阵乘法 等式 1 可以写成 xWx 由此求出转移概率矩阵的最大正特征值1 相应非负特征向量 T x 1 2 1 1 由此可以确定网页的排 序为 C A B 其中页面 A C 的排序无显著差别 之所以将 C 排在前面是因为指向 C 的超链接数更多一些 2 3 随机冲浪模型 Random Surfer Model PageRank 算法原理中有一个重要的假设 所有的网页形成一个闭合的链接图 除了这些文档以外没有其他 任何链接的出入 并且每个网页能从其他网页通过超链接达到 但是在现实的网络中 并不完全是这样的情况 当一个页面没有出链的时候 它的 PageRank 值就不能被分配给其它的页面 同样道理 只有出链接而没有入链 接的页面也是存在的 但 PageRank 并不考虑这样的页面 因为没有流入的 PageRank 而只流出的 PageRank 从 对称性角度来考虑是很奇怪的 同时 有时候也有链接只在一个集合内部旋转而不向外界链接的现象 在现实 中的页面 无论怎样顺着链接前进 仅仅顺着链接是绝对不能进入的页面群总归是存在的 PageRank 技术为了解决这样的问题 提出用户的随机冲浪模型 用户虽然在大多数场合都顺着当前页面中 的链接前进 但有时会突然重新打开浏览器随机进入到完全无关的页面 Google 认为 用户在 85 的情况下沿着 链接前进 但在 15 的情况下会跳跃到无关的页面中 用公式表示相应的转移概率矩阵为 T ee n d dWW 1 其中 e为分量全为 1 的n维列向量 从而 T ee为全 1 矩阵 1 0 d为权重因子 damping factor 在实际中 Google 取85 0 d 也就是说 在随机冲浪模型中 求各个页面等级值 PageRank 的问题变成了求正矩阵W的 最大特征值所属的特征向量问题 还是考虑前面给出的三个网页 A B C 之间的超链接关系 在随机冲浪模型下为方便计算令5 0 d 相 应的转移概率矩阵为 0 16670 66670 4167 0 16670 16670 4167 0 66670 16670 1667 3 5 01 5 0 T eeWW 根据著名的 Perron Frobenius 定理 3 转移概率矩阵W的最大正特征值是 1 相应的特征向量为 T 13 15 13 14 13 10 由此可以确定网页的排序为 C A B 可见随机冲浪模型下的排序结果更合理一些 483 第 3 期 赵国等 Google 搜索引擎的数学模型及其应用 3 页面等级算法 PageRank 的应用 首先我们从图论的角度解释 PageRank 算法的原理 一是看这个页面对应顶点的入度 二是要给指向该顶 点的边赋予权重 表明这个超级链接的重要性 具体的讲 就是把所有的页面看作图里面的点 然后给每一个页 面一个数量 用这个数量来刻画页面的重要性 这样网页的重要性就脱离了它的具体内容 我们只需从网络拓 扑结构出发研究网页的重要性 这样就可以用图论来研究向互联网这样的随机复杂网络 而且按照这个原理对 网页排序具有三个优点 第一 排序与特定搜索关键词无关 第二 网页排序与网页的具体内容无关 第三 只 需要知道网页所对应的图的结构 PageRank 算法的这个特点使得它可以被应用于社会领域的其他问题 例如体育比赛的排名问题 下面针对 1993 年全国大学生数学建模竞赛 B 题 4 利用 PageRank 算法讨论足球队排名次问题 我们发现随机冲浪模型可 以有效克服数据缺损等方面的困难 足球队排名次问题要求我们建立一个客观的评估方法 只依据过去一段时间 几个赛季或几年 内每个球队 的战绩给出各个球队的名次 具有很强的实际背景 5 通过分析题中 12 支足球队在联赛中的成绩 不难发现表 中的数据残缺不全 队与队之间的比赛场数相差很大 直接根据比赛成绩来排名次比较困难 下面我们利用 PageRank 算法的随机冲浪模型来求解 类比 PageRank 算法 我们可以综合考虑各队的比赛成绩为每支球队计算相应的等级分 Rank 然后根据各 队的等级分高低来确定名次 直观上看 给定球队的等级分应该由它所战胜和战平的球队的数量以及被战胜或 战平的球队的实力共同决定 具体来说 确定球队 i T的等级分的依据应为 一是看它战胜和战平了多少支球队 二要看它所战胜或战平球队的等级分的高低 这两条就是我们确定排名的基本原理 在实际中 若出现等级分 相同的情况 可以进一步根据净胜球的多少来确定排名 由于表中包含的数据量庞大 我们先在不计平局 只考虑获胜局的情形下计算出各队的等级分 以说明算 法原理 然后我们综合考虑获胜局和平局 加权后得到各队的等级分 并据此进行排名 考虑到竞技比赛的结果 的不确定性 我们最后建立了等级分的随机冲浪模型 分析表明等级分排名结果具有良好的参数稳定性 3 1 获胜局的等级分 首先利用有向赋权图的权重矩阵来表达出各队之间的胜负关系 用图的顶点表示相应球队 用连接两个顶 点 i T与 j T的有向边表示两队的比赛结果 同时给该边赋予相应的权重 表明 i T战胜 j T的次数 由此 可以写出 表中 12 支球队所对应的有向赋权图的权重矩阵 S 0 1 1 3 1 1 0 1 2 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 2 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 2 0 1 2 0 0 0 2 3 2 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 2 0 2 1 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 例如 表中 3 T与 8 T比赛了两场 各胜一场 故1 38 T 1 83 T 同理 3 14 T表明 1 T曾 3 次战胜 4 T 注意到被战胜球队的等级分应该平均分配给各个获胜球队 将权重矩阵的各个列向量向量进行归一化 得 转移概率矩阵 ij sS 为 第 36 卷 484 西南民族大学学报 自然科学版 S 0 0 1667 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 3333 0 1667 0 0 0 125 0 0 0 0 0833 0 1667 0 25 0 0 3333 0 1667 0 3333 0 0 25 0 0 0 0 0833 0 1667 0 0 0 0 1667 0 1667 0 125 0 0 0 0 0 0833 0 1667 0 0 2 0 3333 0 1667 0 3333 0 375 0 25 0 0 0 0 1667 0 1667 0 0 4 0 0 0 0 0 0 0 0 2 0 0833 0 0 0 0 0 1667 0 0 0 0 0 0 0 0833 0 0 0 0 0 0 0 0 125 0 0 0 0 0 0 0 0 0 0 1667 0 125 0 125 1 0 3333 0 2 0 0833 0 0 5 0 2 0 0 0 0 125 0 0 0 3333 0 0 0833 0 1667 0 0 2 0 0 0 0 25 0 125 0 0 3333 0 2 0 25 0 1667 0 25 0 现设每个队 i T的等级分 i x 这些等级分应由被 i T战胜的那些队的等级分确定 即 i j jij xxs 12 1 12 2 1 i 3 其中 为比例系数 令 T xxx 121 则由矩阵乘法 等式 3 可以写成 xxS 即各个队的等级分的计算 转化求这个转移概率矩阵S的最大正特征值 所属的正特征向量 直接利用 Matlab软 件 计 算 得1 相 应 等 级 分 为 0 2731 0 2085 0 7144 0 0302 0 0026 0 003 0 456 0 2416 0 2503 0 2042 0 0005 0 0006 由此可以确定只算获胜局的情况下各队的排名为 1112564102 89 173 T T T T T T T T T T T T 3 2 加权等级分 在实际中 平局也会队双方的排名产生影响 因此也有必要考虑平局对等级分的贡献 因为平局是相互的 所以可以利用无向赋权图的权重矩阵来表达出各队之间的平局关系 即 P 0 2 0 0 1 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 2 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 2 0 0 0 1 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 2 2 0 1 2 0 0 1 0 0 2 0 0 0 0 0 0 1 1 0 注意平局的权重矩阵P是对称的 同时注意到被战平球队的等级分也应该平均分配给各个与之战平的球队 故将权重矩阵的各个列向量向量进行归一化处理 得转移概率矩阵 485 第 3 期 赵国等 Google 搜索引擎的数学模型及其应用 P 0 1 0 0 0 2 0 0 0 6667 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3333 0 2 0 25 0 0 0 2 0 0 1 0 5 0 0 0 1429 0 0 0 0 0 0 2 0 0 1 0 0 2 0 0 1429 0 0 0 25 0 0 0 0 0 2 0 0 0 0 1429 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1429 0 3333 0 0 0 0 0 0 5 0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 0 25 0 0 0 1429 0 3333 0 4 0 5 0 0 3333 0 4 0 0 0 25 0 0 0 2857 0 0 0 0 0 0 0 5 0 1 0 根据常识 在一场比赛中平局出现的概率为 3 1 同时 考虑到通常平局与获胜局的得分比为3 1 我们可以 对平局和获胜局的转移概率矩阵进行加权处理 得到下面的加权权重矩阵 SPW3 3 2 1 3 1 0 0 6667 0 0 0 0667 0 0 0 6222 0 0 0 0 0 1333 0 0 0 0 0 0 0 4 0 0 0 0 0 6667 0 3333 0 0 1111 0 3167 0 0833 0 0 0 2333 0 3333 0 5333 0 1667 0 6667 0 3333 0 7143 0 0 5 0 0 0 0 2333 0 3333 0 0333 0 0 0667 0 3333 0 3810 0 25 0 0 0833 0 0 0 1667 0 3333 0 0667 0 4 0 6667 0 3333 0 7143 0 75 0 5667 0 0 0 0 3333 0 3333 0 0667 0 8 0 0 0 0 0 0 0 0 4 0 1667 0 0 0 0 1333 0 3333 0 0 0 0 0 0 0 1667 0 0 0333 0 0 0 0 0476 0 1111 0 25 0 0 0 0 0 1667 0 0667 0 0 0 0 3333 0 25 0 25 2 0 6667 0 4 0 2333 0 1 0 4833 0 0 0 0476 0 3611 0 1333 0 1667 0 6667 0 1111 0 3 0 3333 0 0 4833 0 0 0 0952 0 5 0 25 0 0 6667 0 4 0 5 0 5 0 5333 0 同样 被战胜或或战平球队的等级分也应该平均分配给各个获胜队或与之战平的球队 故将加权权重矩阵的各个 列向量向量进行归一化 得转移概率矩阵 ij wW 为 W 0 0 2857 0 0 0 0286 0 0 0 2667 0 0 0 0 0 0571 0 0 0 0 0 0 0 1714 0 0 0 0 0 2857 0 1429 0 0 0476 0 1357 0 0357 0 0 0 1 0 1429 0 2286 0 0714 0 2857 0 1429 0 3061 0 0 2143 0 0 0 0 1 0 1429 0 0143 0 0 0286 0 1429 0 1633 0 1071 0 0 0357 0 0 0 0714 0 1429 0 0286 0 1714 0 2857 0 1429 0 3061 0 3214 0 2429 0 0 0 0 1429 0 1429 0 0286 0 3429 0 0 0 0 0 0 0 0 1714 0 0714 0 0 0 0 0571 0 1429 0 0 0 0 0 0 0 0714 0 0 0143 0 0 0 0 0204 0 0476 0 1071 0 0 0 0 0 0714 0 0286 0 0 0 0 1429 0 1071 0 1071 0 8571 0 3333 0 1714 0 1 0 0 4286 0 2071 0 0 0 0204 0 1548 0 0571 0 0714 0 3333 0 0476 0 1286 0 1429 0 0 2071 0 0 0 0408 0 2143 0 1071 0 0 3333 0 1714 0 2143 0 2143 0 2286 0 现设每个队 i T的等级分为 i x 这些等级分应由 i T所战胜或战平的那些队的等级分确定 即 i j jij xxw 12 1 12 2 1 i 4 第 36 卷 486 西南民族大学学报 自然科学版 其中 为比例系数 令 T xxx 121 则由矩阵乘法 等式 4 可以写成 xxW 即各个队的等级分的计算 转化求平局的转移概率矩阵矩阵W的最大正特征值 所属的非负特征向量 直 接利用 Matlab 软件计算得1 相应等级分为 0110 0 0026 0 419 0 25210 2473 0 2 0 4435 118 0 009 0 0981 0 0 27 0 265 0 66 0 3173 由此可以确定在综合考虑获胜局和平局的情况下各队的排名为 116125498 102 173 T T T T T T T T T T T T 3 3 等级分的随机冲浪模型 在大多数时候 竞技比赛的结果都是两队之间实力的客观反映 但是 竞技比赛的结果有时具有一定的不 确定性 它很容易受到某些偶然或人为因素的影响 为了消除这些不确定因素的影响 我们需要建立等级分的 随机冲浪模型 设球队的实力能确定比赛的结果的概率为d 即强队因为不确定因素输掉给任意一支球队的概率为d 1 则可得下面的转移概率矩阵 T ee n d WdW 1 其中 e为分量全为 1 的n维列向量 从而 T ee为全 1 矩阵 1 0 d为权重因子 在实际中可以根据历史数据 确定 同样 各个队的等级分的计算 转化求转移概率矩阵W最大正特征值所属的正特征向量 下面着重分析权重因子 1 0 d的变化对排名的影响 为此 我们利用 Matlab 软件计算出权重因子d取不 同的值时的排名情况如表 1 表 1 权重因子d取不同的值时的排名情况 d取值范围 球队排名 1 d 116125498 102 173 T T T T T T T T T T T T 95 09 0 d 116512498 102 173 T T T T T T T T T T T T 85 045 0 d 116512489 102 173 T T T T T T T T T T T T 4 0 d 6115124109 82 173 T T T T T T T T T T T T 从表中可以看出 根据等级分的排名结果具有良好的稳定性 并且 权重因子的变化

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论