数学建模培训讲座市公开课一等奖百校联赛特等奖课件.pptx

数学建模课程 (Mathematics Modeling)数学建模培训主讲教师：任驰远第1页建模普通步骤及范例建模普通步骤及范例2评阅标准及论文写作评阅标准及论文写作4试题分析及论文导读试题分析及论文导读3 3建模普通思维方法建模普通思维方法3 1第2页2评阅标准及论文写作评阅标准及论文写作4试题分析及论文导读试题分析及论文导读3 3建模普通思维方法建模普通思维方法3 1建模普通步骤及范例建模普通步骤及范例第3页群体思维方法群体思维方法 平等地位、相互尊重、充分交流平等地位、相互尊重、充分交流杜绝武断评价杜绝武断评价不要回避责任不要回避责任不要对交流失去信心不要对交流失去信心 第4页发散性思维方法发散性思维方法借助于一系列问题来展开思绪借助于一系列问题来展开思绪这个问题与什么问题相同？这个问题与什么问题相同？假如将问题分解成两个或几个部分会怎样？假如将问题分解成两个或几个部分会怎样？极限情形（或理想状态）怎样？极限情形（或理想状态）怎样？综合问题条件可得到什么结果？综合问题条件可得到什么结果？要实现问题目标需要什么条件？要实现问题目标需要什么条件？借助于下意识联想（灵感）来展开思绪借助于下意识联想（灵感）来展开思绪抓住问题个别条件或关键词展开联想或猜测抓住问题个别条件或关键词展开联想或猜测综合所得到联想和猜测，得到一些结论综合所得到联想和猜测，得到一些结论深入思索找出新思绪和方法深入思索找出新思绪和方法第5页建模普通步骤及范例建模普通步骤及范例2评阅标准及论文写作评阅标准及论文写作4试题分析及论文导读试题分析及论文导读3 33 1建模普通思维方法建模普通思维方法第6页 数学建模普通步骤数学建模普通步骤问题分析问题分析模型假设模型假设建立模型建立模型模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用问问题题分分析析了解实际背景了解实际背景明确建模目搜集相关信息搜集相关信息掌握对象特征掌握对象特征形成一个形成一个比较清楚比较清楚问题问题第7页模模型型假假设设针对问题特点和建模目作出合理、简化假设作出合理、简化假设在合理与简化之间作出折中在合理与简化之间作出折中建建立立模模型型用数学语言、符号描述问题用数学语言、符号描述问题发挥想象力发挥想象力使用类比法使用类比法尽可能采取简单数学工具尽可能采取简单数学工具 数学建模普通步骤数学建模普通步骤第8页模型模型求解求解各种数学方法、软件和计算机技术各种数学方法、软件和计算机技术.如结果误差分析、统计分析、如结果误差分析、统计分析、模型对数据稳定性分析模型对数据稳定性分析.模型模型分析分析模型模型检验检验与实际现象、数据比较，与实际现象、数据比较，检验模型合理性、适用性检验模型合理性、适用性.模型应用模型应用 数学建模普通步骤数学建模普通步骤第9页1、问题分析、问题分析 问题前期分析问题前期分析 包含：包含：明确问题、分析条件、分析数据明确问题、分析条件、分析数据 为何问题前期分析至关主要？为何问题前期分析至关主要？数学建模问题往往含混不清数学建模问题往往含混不清,可能原因有可能原因有:*提出问题人未能清楚地表述问题提出问题人未能清楚地表述问题.*不一样领域人交流出现故障不一样领域人交流出现故障.*各领域应用者提出问题时，未给出恰当各领域应用者提出问题时，未给出恰当条件条件.*未能准确了解问题未能准确了解问题.第10页 对问题进行充分前期分析以前对问题进行充分前期分析以前,过早着手决问过早着手决问题题,往往会陷入一些意想不到陷阱往往会陷入一些意想不到陷阱,或者偏离处理或者偏离处理问题方向问题方向.(1)明确问题明确问题例例1 一家大商业印刷企业经理就关于应该雇一家大商业印刷企业经理就关于应该雇 多少推销员问题咨询你意见多少推销员问题咨询你意见.“终究需要做什么？终究需要做什么？”为明确问题为明确问题,可向相关人员问询以下问题：可向相关人员问询以下问题：1.企业规模有多大？企业规模有多大？2.该企业推销员工作方式？该企业推销员工作方式？碰到一个新问题时碰到一个新问题时,首先应问自己首先应问自己第11页着眼点着眼点是对各类推销队伍工作效果进行分析是对各类推销队伍工作效果进行分析 原问题原问题“推销员人数问题推销员人数问题”明确为：明确为：（1 1）不一样规模销售队伍会有什么影响；）不一样规模销售队伍会有什么影响；（2 2）怎样从他们销售工作中获取最大收益）怎样从他们销售工作中获取最大收益.明确了工作目标明确了工作目标,即设置好问题目标态即设置好问题目标态.第12页(2)条件及数据分析条件及数据分析 设置好问题目标态，着手工作还需要做设置好问题目标态，着手工作还需要做以下工作：以下工作：1.1.搜集必要资料和数据。搜集必要资料和数据。2.2.分析现有数据和条件，使问题深入分析现有数据和条件，使问题深入 明确化。明确化。第13页怎样搜集数据和资料？怎样搜集数据和资料？可在各类图书馆、网上查阅、向教授问询、可在各类图书馆、网上查阅、向教授问询、经过试验来得到经过试验来得到。搜集数据应列入工作计划，并注意：搜集数据应列入工作计划，并注意：1.1.向相关人员调查情况应事先设计好问题；向相关人员调查情况应事先设计好问题；2.事先确定所需资料清单、资料起源、事先确定所需资料清单、资料起源、搜集方式。搜集方式。第14页有条理收集计划可认为后期工作创造良好条件 对搜集到或者现有资料和数据要做对搜集到或者现有资料和数据要做仔细分析，使问题深入明确仔细分析，使问题深入明确。5.哪些条件是能够变动？等等哪些条件是能够变动？等等2.数据起源是否可靠？数据起源是否可靠？3.所给条件有什么意义？所给条件有什么意义？4.哪些条件是本质？哪些条件是本质？还应该分析还应该分析1.从数据中可得到什么信息？从数据中可得到什么信息？第15页建建模模过过程程中中几几个个关关键键点点模型整体设计模型整体设计合理假设合理假设建立数学表示式建立数学表示式建立数学结构建立数学结构时刻牢记建模目2、建立模型建立模型第16页完整数学模型应该同时描述出完整数学模型应该同时描述出相关原因之间相关原因之间数量关系数量关系和和结构关系结构关系。应清楚变量、变量之间数学表示式在整个应清楚变量、变量之间数学表示式在整个模型中模型中地位地位和和作用作用.例例1 考虑一个简化城镇供水系统考虑一个简化城镇供水系统,水是由水库经水是由水库经由管道流入水箱由管道流入水箱,再由水箱向各用户供水再由水箱向各用户供水.问题：问题：怎样才能怎样才能有效地保障有效地保障各用户正惯用水？各用户正惯用水？(1)(1)模型整体设计模型整体设计第17页按下述步骤对模型进行整体设计按下述步骤对模型进行整体设计 1.分析系统组成部分分析系统组成部分（研究对象、实体）（研究对象、实体）相关实体有：水库相关实体有：水库,管道管道,水箱和用户水箱和用户.*实体间实体间结构关系结构关系可表示以下：可表示以下：水库水库管道管道水箱水箱用户用户*以上各实体都可能是我们研究对象以上各实体都可能是我们研究对象.*应分析相对于各个实体原因对供水影响应分析相对于各个实体原因对供水影响2.分析各实体之间关系分析各实体之间关系,找出联络各实体找出联络各实体变量变量.第18页实体之间作用关系图实体之间作用关系图 各各实实体体之之间间关关系系 管道与水箱：管道水流量管道与水箱：管道水流量水库与管道：水库水深水库与管道：水库水深水箱与用户：出水口水流量水箱与用户：出水口水流量 （或有效水深（或有效水深）用户：总用水量用户：总用水量 3.依据各实体相互关系，依据各实体相互关系，提炼整理需考虑提炼整理需考虑变量变量以及变量之关系表示式以及变量之关系表示式.第19页 假设假设“水库能确保管道所需水流量水库能确保管道所需水流量”，现需考虑现需考虑t 时刻以下变量：时刻以下变量：*总需水量总需水量D(t)；*水箱有效储水量水箱有效储水量Q(t)及及 QM；或流出水流量或流出水流量F（t）及）及 FM；*管道能提供供水量管道能提供供水量G(t)及及GM.分析各变量特征：分析各变量特征：*D(t)不可控，但能够对其进行描述；不可控，但能够对其进行描述；*G(t)是可控变量。是可控变量。第20页4.4.用数学语言描述用数学语言描述要处理问题要处理问题 选择适当函数选择适当函数G(t)，使得，使得有有 Q(t)=G(t)F(t),F(t)=D(t),0G(t)GM，0Q(t)QM，同时成立同时成立.建模工作整体设计建模工作整体设计:1）确定需求函数确定需求函数D（t），是确保有效控制，是确保有效控制基础；基础；2）制订恰当评价指标，以评价方案优劣；制订恰当评价指标，以评价方案优劣；第21页 3）求出相对于评价指标最优水箱供水方案；求出相对于评价指标最优水箱供水方案；4）分析各种参数对方案影响；分析各种参数对方案影响；5）分析随机原因影响分析随机原因影响.模型整体设计作用模型整体设计作用 1）可将整个建模过程分解为一些可串行可将整个建模过程分解为一些可串行 或并行子任务。或并行子任务。2）可把握住工作重点、关键点和难点可把握住工作重点、关键点和难点.做出模型整体设计后，着手建立模型做出模型整体设计后，着手建立模型之前，撰写一份工作提要之前，撰写一份工作提要.提议提议:第22页(2)做出假设 依据对象特征和建模目标对问题进行依据对象特征和建模目标对问题进行必要、合理简化，用准确语言做出假必要、合理简化，用准确语言做出假设，是建模设，是建模关键步骤关键步骤。合合理理假假设设作作用用 简化问题简化问题 明确问题明确问题 限定模型限定模型适用范围适用范围 一个实际问一个实际问题不经过简题不经过简化假设化假设,极难极难抽象转化为抽象转化为数学问题。数学问题。第23页例例2 飞行管理问题中有叙述：飞行管理问题中有叙述：“对以下对以下数据数据进行进行计算计算（方向角误差（方向角误差不超出不超出0.01度度）”怎样了解？怎样了解？经过假设：经过假设：*所给飞行方向角数据误差不超出所给飞行方向角数据误差不超出0.01度度.或或 *数据运算结果误差限控制为数据运算结果误差限控制为0.01度度.使问题完全明确使问题完全明确.例例3 渔业管理问题中关于渔业管理问题中关于“季节性集中产卵繁季节性集中产卵繁殖殖”,怎样了解怎样了解“产卵孵化期是一年产卵孵化期是一年最终四个最终四个月月”？最优打鱼策略最优打鱼策略 飞行管理模型飞行管理模型 第24页有以下几个假设有以下几个假设:*产卵是均匀地分布在整个四个月期间内，产卵是均匀地分布在整个四个月期间内，从而孵化也是均匀进行从而孵化也是均匀进行.*产卵时间服从方差很小正态分布产卵时间服从方差很小正态分布.*鱼群个体在后四个月第一天集中产卵，鱼群个体在后四个月第一天集中产卵，在最终一天孵化出来在最终一天孵化出来.哪一条哪一条“最好最好”？第三种与第二种没有本质差异，第三种与第二种没有本质差异，处理较轻易处理较轻易.分析：分析：第一个不符合鱼类生物学实际；第一个不符合鱼类生物学实际；第二种比较符合实际，但大大增加了处理第二种比较符合实际，但大大增加了处理问题难度；问题难度；第25页假设起到简化问题作用假设起到简化问题作用 假设假设“渔场是非开放式，不与其它水域发生渔场是非开放式，不与其它水域发生关系，从而组成独立生态群落关系，从而组成独立生态群落”将建立数学模型限定在一定适用范围将建立数学模型限定在一定适用范围.设计假设应遵照标准设计假设应遵照标准 *假设应是有依据，基于对问题内在规律认假设应是有依据，基于对问题内在规律认识和对数据及现象分析；识和对数据及现象分析；*善于区分问题主次，抓主要原因，尽可能善于区分问题主次，抓主要原因，尽可能使问题简化使问题简化.*防止过于简单、过于详细或不合理防止过于简单、过于详细或不合理.第26页 例例4 渔业管理问题中有条件：渔业管理问题中有条件：“平均每条平均每条4 龄鱼产卵量为龄鱼产卵量为1.109105个，个，3 龄鱼产卵量龄鱼产卵量为这个数二分之一，为这个数二分之一，2 龄鱼和龄鱼和1 龄鱼不产卵龄鱼不产卵”.分析分析：为了计算鱼群产卵量，需明确此条件：为了计算鱼群产卵量，需明确此条件.*“平均每条鱼产卵量平均每条鱼产卵量”了解为对全部鱼了解为对全部鱼平均，平均，故在计算总产卵量时，不考虑雌雄区分故在计算总产卵量时，不考虑雌雄区分.有两种假设：有两种假设：*雌雄鱼百分比是雌雄鱼百分比是1:1；哪一个较为合理？哪一个较为合理？最优打鱼策略最优打鱼策略 第27页 可假设：可假设：*每到第二年初，头一年每到第二年初，头一年1、2、3 龄鱼均增龄鱼均增1岁，将岁，将5龄鱼归并为龄鱼归并为4龄鱼龄鱼.合理性解释：事实上，资料表明此种鱼寿命一般为3年，其次经过捕捞后4 龄鱼数量很少，可以忽略不计.对于假设：对于假设：*有时需要对假设以及假设推论进行检验；有时需要对假设以及假设推论进行检验；问题问题：当年当年4 龄鱼，第二年怎样处理？龄鱼，第二年怎样处理？*应意识到隐含假设应意识到隐含假设.第28页 3、求解模型、求解模型求数学模型解主要而困难求数学模型解主要而困难求解纯数学问题求解纯数学问题求解数学模型求解数学模型 *包括不一样数学分支知识，同时还需借助包括不一样数学分支知识，同时还需借助与背景知识与背景知识.*针对现实问题建立数学模型，往往仅可求数针对现实问题建立数学模型，往往仅可求数值解值解.*有类问题可采取分析法得到问题实际解答有类问题可采取分析法得到问题实际解答(如微分方程定性分析如微分方程定性分析).第29页4、模型解分析和检验、模型解分析和检验始于现实世界并终于现实世界始于现实世界并终于现实世界数学建数学建模工作模工作最终要得到现最终要得到现实问题解答实问题解答 求出模型数学解以后，求出模型数学解以后，必须对解意义进行分析、检验必须对解意义进行分析、检验第30页需讨论以下类似问题：需讨论以下类似问题：1.这个讲解明了什么问题？这个讲解明了什么问题？2.是否到达了建模目标？是否到达了建模目标？3.模型适用范围怎样？模型适用范围怎样？4.所建模型是否合理？是否合乎实际？是否有所建模型是否合理？是否合乎实际？是否有 原理性错误、常识性错误？原理性错误、常识性错误？第31页o 量纲一致性检验；量纲一致性检验；o假设合理性检验；假设合理性检验；o对模型参数灵敏度分析；对模型参数灵敏度分析；o模模型型及及模模型型解解误误差差分分析析，分分析析误误差差及及误误差差起起源源等；等；o参数或变量临界值；参数或变量临界值；模型与模型解分析与检验，通常需要做模型与模型解分析与检验，通常需要做以下几类工作：以下几类工作：第32页一个例子：一个例子：Google搜索引擎奥妙搜索引擎奥妙o引言n互联网高速发展使得网络上信息量爆炸似增加，高效搜索信息越来越主要，信息引擎已经成为除电子邮件之外第二大互联网网应用。n在众多搜索引擎中，Google以其庞大搜索量，快速而准确搜索结果和极高著名度成为搜索引擎代名词。n可是你知道它是怎样工作吗？第33页1、Google及其查询过程第34页2、搜索引擎需要完成工作o从页面上能够看到，与关键词“math modeling”匹配结果有3000多万条；与关键词“数学建模”匹配关键词有130多万条；用户需要显然不是全部，而是其中最主要，怎样实现快速搜索，怎样合理定义网页主要性无疑是Google制胜关键。o怎样最快速最准确提供搜索结果？o搜索引擎完成工作：n自动下载尽可能多网页；n建立快速有效索引；n依据相关性对网页进行公平准确排序。第35页2、搜索引擎需要完成工作o从页面上能够看到，与关键词“math modeling”匹配结果有3000多万条；与关键词“数学建模”匹配关键词有130多万条；用户需要显然不是全部，而是其中最主要，怎样实现快速搜索，怎样合理定义网页主要性无疑是Google制胜关键。o怎样最快速最准确提供搜索结果？o搜索引擎完成工作：n自动下载尽可能多网页；n建立快速有效索引；n依据相关性对网页进行公平准确排序。第36页o它要用到图论中遍历（Traverse)算法。n图论中所讨论图由一些节点和连接这些节点弧组成。假如我们把中国城市当成节点，连接城市国道当成弧，那么全国公路干线网就是图论中所说图。关于图算法有很多，但最主要是图遍历算法，也就是怎样经过弧访问图各个节点。n以中国公路网为例，我们从北京出发，看一看北京和哪些城市直接相连，比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们能够依次访问这些城市，然后我们看看都有哪些城市和这些已经访问过城市相连，比如说北戴河、秦皇岛与天津相连，青岛、烟台和济南相连，太原、郑州和石家庄相连等等，我们再一次访问北戴河这些城市，直到中国全部城市都访问过一遍为止。这种图遍历算法称为“广度优先算法”（BFS)，因为它先要尽可能广地访问每个节点所直接连接其它节点。n外还有一个策略是从北京出发，随便找到下一个要访问城市，比如是济南，然后从济南出发到下一个城市，比如说南京，再访问从南京出发城市，一直走到头。然后再往回找，看看中间是否有还未访问城市。这种方法叫“深度优先算法”（DFS)，因为它是一条路走到黑。这两种方法都能够确保访问到全部城市。需要统计已经访问过城市，以防同一个城市访问屡次或者遗漏哪个怎样自动下载互联网全部网页呢？第37页o经过超链接，我们能够从任何一个网页出发，用图遍历算法，自动地访问到每一个网页并把它们存起来。完成这个功效程序叫做网络爬虫，或者在一些文件中称为“机器人”（Robot)。o假定我们从一家门户网站首页出发，先下载这个网页，然后经过分析这个网页，能够找到藏在它里面全部超链接，也就等于知道了这家门户网站首页所直接连接全部网页，诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站邮件等网页，又能找到其它相连网页。我们让计算机不停地做下去，就能下载整个互联网。当然，我们也要记载哪个网页下载过了，以免重复。在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)列表而不是一个记事本纪录网页是否下载过信息。第38页o现在互联网非常巨大，不可能经过一台或几台计算机服务器就能完成下载任务。比如雅虎企业（Google 没有公开数目，这里举了雅虎索引大小为例）宣称他们索引了 200 亿个网页，假以下载一个网页需要一秒钟，下载这 200 亿个网页则需要 634 年。所以，一个商业网络爬虫需要有成千上万个服务器，而且由快速网络连接起来。怎样建立这么复杂网络系统，怎样协调这些服务器任务，就是网络设计和程序设计艺术了。第39页怎样建立快速索引？o世界上不可能有比二进制更简单计数方法了，也不可能有比布尔运算更简单运算了。尽管今天每个搜索引擎都宣称自己怎样聪明、多么智能化，其实从根本上讲都没有逃出布尔运算框框。o布尔代数简单得不能再简单了。运算元素只有两个1（TRUE，真)和 0（FALSE，假)。o你们可能会问这么简单理论能处理什么实际问题。实际上在布尔代数提出后80 多年里，它确实没有什么像样应用，直到 1938 年香农在他硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成为数字电路基础。全部数学和逻辑运算，加、减、乘、除、乘方、开方等等，全部能转换成二值布尔运算。第40页o文件检索和布尔运算关系n对于一个用户输入关键词，搜索引擎要判断每篇文件是否含有这个关键词，假如一篇文件含有它，我们对应地给这篇文件一个逻辑值-真（TRUE,或 1），不然，给一个逻辑值-假（FALSE,或0）。n比如我们要找相关原子能应用文件，但并不想知道怎样造原子弹：p写一个查询语句“原子能 AND 应用 AND(NOT 原子弹)”。p每一篇文件对于上面每一个条件，都有一个 True 或者 False 答案，依据上述真值表就能算出每篇文件是否是要找 网页。n当然在查询时，不能将每篇文件扫描一遍，来看看它是否满足上面三个条件，所以需要建立一个索引。第41页n最简单索引结构是用一个很长二进制数表示一个关键字是否出现在每篇文件中。有多少篇文件，就有多少位数，每一位对应一篇文件，1 代表对应文件有这个关键字，0 代表没有。p比如关键字“原子能”对应二进制数是0100100001100001 .，表示第二、第五、第九、第十、第十六篇文件包含着个关键字。p一样，我们假定“应用”对应二进制数0010100110000001 .。那么要找到同时包含“原子能”和“应用”文件时，只要将这两个二进制数进行布尔运算 AND。依据上面真值表，我们知道运算结果是0000100000000001.。表示第五篇，第十六篇文件满足要求。注意，计算机作布尔运算是非常非常快。现在最廉价微机都能够一次进行三十二位布尔运算，一秒钟进行十亿次以上。当然，因为这些二进制数中绝大部分位数都是零，我们只需要统计那些等于1位数即可。第42页o布尔运算它最大好处是轻易实现，速度快，这对于海量信息查找是至关主要。它不足是只能给出是是否判断，而不能给出量化度量。所以，全部搜索引擎在内部检索完成后，都要对符合要求网页依据相关性排序，然后才返回给用户。o查找关于“原子能应用”网页。我们第一步是在索引中找到包含这三个词网页。现在任何一个搜索引擎都包含几十万甚至是上百万个多少有点关系网页。那么哪个应该排在前面呢？显然我们应该依据网页和查询“原子能应用”相关性对这些网页进行排序。所以，这里关键问题是怎样度量网页和查询相关性。怎样确定网页和查询相关性？第43页o短语“原子能应用”能够分成三个关键词：原子能、应用。依据我们直觉，我们知道，包含这三个词多网页应该比包含它们少网页相关。n漏洞：就是长网页比短网页占廉价。o所以我们需要依据网页长度，对关键词次数进行归一化，也就是用关键词次数除以网页总字数。我们把这个商称为“关键词频率”，或者“单文本词汇频率”（Term Frequency)，概括地讲，假如一个查询包含关键词 w1,w2,.,wN,它们在一篇特定网页中词频分别是:TF1,TF2,.,TFN。（TF:term frequency)。那么，这个查询和该网页相关性就是:TF1+TF2+.+TFN。n漏洞：词“”词频对确定网页主题几乎没有用。称这种词叫“应删除词”（Stopwords)，也就是说在度量相关性是不应考虑它们频率。n另一个小漏洞。在汉语中，“应用”是个很通用词，而“原子能”是个很专业词，后者在相关性排名中比前者主要。o需要给分解关键词给一个权重。一个词预测主题能力越强，权重就越大，反之，权重就越小。第44页o我们很轻易发觉，假如一个关键词只在极少网页中出现，我们经过它就轻易锁定搜索目标，它权重也就应该大。反之假如一个词在大量网页中出现，我们看到它依然不很清楚要找什么内容，所以它应该小。概括地讲，假定一个关键词 在 个网页中出现过，那么 越大，权重越小，反之亦然。在信息检索中，使用最多权重是“逆文本频率指数”（Inverse document frequency 缩写为），它公式为（）其中是全部网页数。比如，我们假定汉字网页数是亿，应删除词“”在全部网页中都出现，即亿，那么它log(10亿/10亿）=log(1)=。假如专用词“原子能”在两百万个网页中出现，即万，则它权重log(500)=6.2。又假定通用词“应用”，出现在五亿个网页中，它权重=log(2)，则只有 0.7。也就只说，在网页中找到一个“原子能”比配相当于找到九个“应用”匹配。利用 IDF，上述相关性计算个公式就由词频简单求和变成了加权求和，即 TF1*IDF1+TF2*IDF2.+TFN*IDFN。第45页oTF/IDF（term frequency/inverse document frequency)概念被公认为信息检索中最主要创造。在搜索、文件分类和其它相关领域有广泛应用。o其实，信息论学者们已经发觉并指出，其实 IDF 概念就是一个特定条件下、关键词概率分布交叉熵（Kullback-Leibler Divergence)。这么，信息检索相关性度量，又回到了信息论。第46页怎样确定网页排名？oPage Rank Google 民主表决式网页排名技术nGoogle 革命性创造是它名为“Page Rank”网页排名算法，这项技术彻底处理了搜索结果排序问题。oGoogle为了提供搜索者想要信息，到达完美搜索引擎功效，采取“网页级别(Pagebank)”与“页面分析”两种技术来确保检索质量与准确率，所谓Pagebank技术是基于整个网络链接结构，按网页链接广泛程度来决定网页主要性，而“页面分析”也就是前面所讲相关性分析。Google将最相关和最可靠结果放在搜索结果顶端，普通而言，Pagebank对于排名影响还是比页面分析高。第47页oPagebank技术经过对多达80多亿个网页进行主要性分析，利用网络链接结构对网页进行组织整理。基本原理是：假如网页A链接到网页B，Google就认为“网页A投了网页B一票”，这是80多亿个网页之间海选，每个网页都有选举权，也有被选举权，投票次数不限。初看起来这么选举不是很有序，公平性似乎无从谈起，关键在于怎样“计票”，一个网页Pagebank并不是它得票数。o假设Google数据库中网页集合为W，该集合元素格式为N，为了描述这些网页之间关系，定义一个N*N方阵G=(gij).假如从网页j到网页i有超链接，则gij=1,不然为零，显然G是巨大不过非常稀疏矩阵，其中非零元素总数即是网页之间超链接总数。第48页第49页第50页第51页第52页o计算得到该Markov链平均分布为：x=(0.2330 0.2447 0.1965 0.1240 0.0777 0.1240)，这就是6个网页Pagebank.第53页 编号为2网页在选举中仅仅得到一票，不过它Pagebank要高于其它得到一票网页，原因在于它一票来自网页ALPHA，这个网页Pagebank也比较高，所以这是合理。第54页o理论问题处理了，又碰到实际问题。因为互联网上网页数量是巨大，上面提到二维矩阵从理论上讲有网页数目平方之多个元素。假如我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这么大矩阵相乘，计算量是非常大。Google 两个创始人拉里佩奇（Larry Page）和谢尔盖布林(Sergey Brin)两人利用稀疏矩阵计算技巧，大大简化了计算量，并实现了这个网页排名算法。今天 Google 工程师把这个算法移植到并行计算机中，深入缩短了计算时间，使网页更新周期比以前短了许多。o今天，Google 搜索引擎比最初复杂、完善了许多。不过网页排名在 Google 全部算法中依然是至关主要。在学术界,这个算法被公认为是文件检索中最大贡献之一，而且被很多大学引入了信息检索课程(Information Retrieval)教程。第55页 地面上存在着地面上存在着n个接收站与个接收站与n个发送站，而在通讯卫星上则个发送站，而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵设置了若干种开关模式。开关模式可用矩阵P=(pij)表示，若表示，若卫星可接收发送站卫星可接收发送站i发射信息并将信息送回地面接收站发射信息并将信息送回地面接收站j，矩，矩阵中元素阵中元素pij=1，不然，不然pij=0。通讯卫星上接收发送任务也能。通讯卫星上接收发送任务也能够用一个矩阵够用一个矩阵T=（tij）来表示，其元素）来表示，其元素tij为需经通讯卫星传为需经通讯卫星传递由递由i发点发送到发点发送到j接收点信息量传送时间长度。因为技术原接收点信息量传送时间长度。因为技术原因，当发送站因，当发送站i在发送给接收站在发送给接收站j信息时，它不能同时发送给信息时，它不能同时发送给别接收站信息；一样，当接收站别接收站信息；一样，当接收站j在接收发送站在接收发送站i信息时，也信息时，也不能同时接收其它发送站发送信息。你任务是：不能同时接收其它发送站发送信息。你任务是：另一个例子：通讯卫星上开关设置另一个例子：通讯卫星上开关设置第56页o设计一组开关模式，设计一组开关模式，k=1,r（注：（注：r应该尽可能小），使应该尽可能小），使得对任意给定任务矩阵得对任意给定任务矩阵T，卫星开关设置均能完成要求发，卫星开关设置均能完成要求发接收任务。接收任务。o设计一个算法，在发接收任务设计一个算法，在发接收任务T给出后，可依据你设计开给出后，可依据你设计开关模式（关模式（k=1,r）求出各开关使用时间）求出各开关使用时间，使得在完成预，使得在完成预定传送任务前提下使用各开关模式总时间短。定传送任务前提下使用各开关模式总时间短。o一样因为技术上原因，开关模式总数一样因为技术上原因，开关模式总数r有一个上限。当需要有一个上限。当需要传送任务数数量较大时，仍无法分配任务。要求想一些方传送任务数数量较大时，仍无法分配任务。要求想一些方法来处理这一困难，（当然，这时可能要作出一些牺牲，法来处理这一困难，（当然，这时可能要作出一些牺牲，即传送时间可能会增加一些）。即传送时间可能会增加一些）。第57页即要求设计开关系统及使用方法，达到以下目：（1）开关数量要少（控制在一个合理范围内）开关数量要少（控制在一个合理范围内）（2）使用卫星上开关时应尽可能节约卫星租用）使用卫星上开关时应尽可能节约卫星租用时间时间（3）设计详细操作方法）设计详细操作方法第58页问题及模型问题及模型问题标准形式为：在地面上存在着问题标准形式为：在地面上存在着n个收站与个收站与n个发战，而在个发战，而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵通讯卫星上则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示，若卫星可接收发射站来表示，若卫星可接收发射站i发射信息并将信息传送回发射信息并将信息传送回地面接收站地面接收站j时，矩阵元素时，矩阵元素pij=1，不然，不然pij=0。通讯卫星接发。通讯卫星接发任务也可用一矩阵任务也可用一矩阵T=（tij）来表示，其元素）来表示，其元素tij为需经通讯卫为需经通讯卫星传递由星传递由i发点发送到发点发送到j接收点信息量传送时间长度。问题要接收点信息量传送时间长度。问题要求求求求r并设计一组开关模式并设计一组开关模式Pk，k=1,r及模式及模式Pk使用时间使用时间k，使得在完成预定传送任务前提下各开关模式使用总时间最，使得在完成预定传送任务前提下各开关模式使用总时间最短，即要求求解下面问题：短，即要求求解下面问题：第59页一个实例一个实例设设 这是一个有这是一个有3个发送站与个发送站与3个接收站实例，个接收站实例，tij在矩阵中已给出，比如由在矩阵中已给出，比如由发站发站1传送到收站传送到收站1通讯量为通讯量为3单位时间等。单位时间等。分析分析 轻易看出，三个发站需传送时间分别为轻易看出，三个发站需传送时间分别为6、5、5；而三个收站需接收；而三个收站需接收时间分别为时间分别为6、3、7。为完成全部传送任务，通讯卫星总传送时间最少应为。为完成全部传送任务，通讯卫星总传送时间最少应为7单位时间，即下界为单位时间，即下界为7。因为技术上原因，当发站因为技术上原因，当发站i在发送给收站在发送给收站j信息时，它不能同时发送给别收站信息时，它不能同时发送给别收站信息；一样，当收站信息；一样，当收站j在接收发站在接收发站i信息时，也不能同时接收其它发站发送信信息时，也不能同时接收其它发站发送信息。这一要求说明，任一开关模式息。这一要求说明，任一开关模式Pk应含有以下性质：（应含有以下性质：（1）Pk每一行中有每一行中有且只有一个且只有一个1，每一列中也有且只有一个，每一列中也有且只有一个1；（；（2）全部）全部1均位于不一样行列均位于不一样行列中。中。满足（满足（1）、（）、（2）矩阵）矩阵 被称为置换矩阵，被称为置换矩阵，n阶置换矩阵阶置换矩阵Pk共有共有n!个，当个，当n较较大时，我们不可能在通讯卫星上设置这么各种不一样开关模式。因而，为了大时，我们不可能在通讯卫星上设置这么各种不一样开关模式。因而，为了设计出切实可行开关模式，我们还得另想方法。设计出切实可行开关模式，我们还得另想方法。（问题）最少要多少种开关模式？（问题）最少要多少种开关模式？易见，必须有易见，必须有 第60页（设计方法（设计方法1）注意到注意到Pk每行（或列）元素之和均为每行（或列）元素之和均为1，故不论怎样指派开关使用时间（即，故不论怎样指派开关使用时间（即不论怎样取不论怎样取k），矩阵），矩阵均含有一些特殊性质，比如其行和（及列和）均为同一常数。这么矩阵组均含有一些特殊性质，比如其行和（及列和）均为同一常数。这么矩阵组成一个线性空间（参见成一个线性空间（参见Drer魔方），为降低开关模式种类，可取此空间一魔方），为降低开关模式种类，可取此空间一组基底作为开关模式。在使用这种开关模式时，不论组基底作为开关模式。在使用这种开关模式时，不论T元素元素tij怎么取，通讯怎么取，通讯卫星对每一发（收）点开通时间总和是恒定。在这种开关模式下，可按以卫星对每一发（收）点开通时间总和是恒定。在这种开关模式下，可按以下方式指派各开关模式使用时间：下方式指派各开关模式使用时间：步步1 先将先将T改变为改变为 ，满足：满足：（1）T（2）记）记 ，步步2 用用Pk表示表示 ，即将，即将 分解为分解为（r为空间维数）为空间维数）第61页将将T化为化为 方法普通有没有穷各种，如可以下化法：方法普通有没有穷各种，如可以下化法：令令 实际上，实际上，（即通讯卫星传送总时间下界）。，（即通讯卫星传送总时间下界）。令令 其中其中 用这种方法化例中用这种方法化例中T，得到，得到任一行（或列）中元素之和均为任一行（或列）中元素之和均为7。第62页定义定义1 1称行和、列和均相等矩阵为双随机矩阵（称行和、列和均相等矩阵为双随机矩阵（Doubly stochastic matrix）定理定理1 1（Birkhoff定理，定理，1944）任一）任一n阶双随机矩阵均可写成至多阶双随机矩阵均可写成至多 （n1）2+1个置换矩阵非线性组合。个置换矩阵非线性组合。分解方法可以下进行：分解方法可以下进行：步步1 选取由选取由Pij0可推出可推出 0置换矩阵置换矩阵P步步2 确定确定 步步3 取取 ，用，用 代替代替步步4 若若 =0，停；不然，返回步，停；不然，返回步1。例例2.2.为方便起见，我们来分解一个元素均为非负整数为方便起见，我们来分解一个元素均为非负整数3阶双随机矩阵，阶双随机矩阵，（由（由Birkhoff定理，定理，r5）第63页解：取解：取 ，=min 1,3,3 =1分解成分解成，再取，再取 因因min 5,5,3=3，又有，又有，取，取 第64页于是又有于是又有 易得分解结果为：易得分解结果为：第65页尚需处理问题是怎样求尚需处理问题是怎样求P，使得，使得Pij0必有必有 。读者不难发觉，此问题。读者不难发觉，此问题能够经过求解一个两分图上最大流（或最大匹配）来实现，计算量为能够经过求解一个两分图上最大流（或最大匹配）来实现，计算量为O(n4)，是多项式时间可解。详细方法为：作一两分图，若，是多项式时间可解。详细方法为：作一两分图，若 ，则作，则作边（边（i,j），令边容量为），令边容量为1，这么，可作出，这么，可作出P充要条件是该最大流问题最大充要条件是该最大流问题最大流量为流量为n。对例。对例9.33，n=3。因为全部。因为全部 ，先取，先取，P1为为 于是又可求得于是又可求得第66页，对应两分图为：，对应两分图为：又可得又可得 ，如此下去，直到作不出，如此下去，直到作不出P为至，为至，因为因为 特殊性质及特殊性质及Birkhoff定理，上述分解必能在不超出定理，上述分解必能在不超出r=(n1)2+1步内终止。步内终止。上述开关设计方法要求在通讯卫星上设置上述开关设计方法要求在通讯卫星上设置(n1)2+1种不一样开关模式种不一样开关模式（即（即Pk），当），当n稍大时，稍大时，(n1)2+1仍显得太大而使得使用时不便。比如，仍显得太大而使得使用时不便。比如，当当n=41时，时，(n1)2+1=1601。为实用方便，人们研究了