数学建模借鉴材料.ppt

1、结构主义建模与复杂网络,张齐鹏 南阳师范学院 Tel:目录 一、引子：学生的问题: 建模=引模吗? 二、什么是模型? 什么是数学模型？ 三、模型的抽象度与数学的普适性 四、结构主义数学建模方法 五、结构化建模例子 六、复杂系统建模与复杂网络,一、引子：建模=引模？,大学生的问题：数学建模 = 数学引模 ？,类比、引用和借鉴是很有效的方法：现状！,数学建模方法= 创造性的本质方法 + 模型类比方法,但是：,例一、Web中的问题,网络已经成为现代人的一种生活方式。在网上，每天有成千上万的多媒体文件在传输（例如，路透社每天收到网上文本文件达20万）。试建立数学模型，使得可以

2、对这些文件进行自动分类，以便人们阅读和使用。,没有可用案例时怎么办？,例二、中国菜系研究,中国是一个美食及其文化非常丰富的国家，因为国土辽阔，人口众多。中国著名的菜系：苏菜、闽菜、川菜、鲁菜、粤菜、湘菜、浙菜、徽菜。 请用数学建模方法研究这些菜系的特点。,这是一个研究性问题： 数学建模本质上是一个创造性的过程， 如何“创造”是一个科学研究课题。,数学建模的目的主要不是竞赛， 也不仅仅是为了教学， 根本的目的是数学应用！,二、什么是模型? 什么是数学模型？,从基本概念的理解出发： 模型？+ 数学？ 数学模型？ 如何建模？,问题：如何从数学模型的概念出发构造方法 ？,1）社会科学模型 经济与管理科

3、学模型、军事模型（越战）、政治模型、社会学模型等等。,1、模型的概念：什么是模型,这是一个通过举例或指认回答的简单问题。,例 项目管理科学中的甘特图模型 反映了在项目管理中各个过程的受控运行状态，是项目各部分关联结构的动态表示。 ISO9000系列实质上是管理过程的标准。,例 选举模型 多数选举法、累计选举法等等，是特种社会活动的模型。,这些模型共同特点是： 表达方式易于理解，抽象度低。,例经济学模型： 市场模型、竞争模型、企业战略模型、股票模型、金融模型，等等。,建筑模型 ，交通模型，电路模型，服装模型 等等。 表达：建筑设计图、交通网络、电路图、服装模版等。,2）工程技术模型,3）生命科学

4、模型 新陈代谢模型、光合作用模型、血液循环模型、DNA双螺旋模型 、蛋白质结构模型等等。,用专业理论抽象出的结构： 并用专业语言表示的模型。,5）物理模型 基本粒子、原子模型、晶体模型 、光学的衍射等等。,4）化学模型 苯环 、化学健理论、反应平衡等等；,2、模型是什么？,模型：以特定目的对事物原型抽象出结构并适当表示。,抽象出结构：不是一般概念的抽象，而是结 构的抽象；,适当的表示：使用不同知识与方法，需要不同 的语言表示。,特定目的：目的不同，关注的结构（事物的内部 联系）不同；,例. 飞机模型目标不同，模型不同,目的：空气动力学研究 抽象结构：外型结构，除去内部构造；,目的：机舱设计 抽

5、象结构：内部空间结构，除去外部结构；,不同目的关注的内容不同，抽象的结构不同。,表示：专业图形和航空语言表示。,例. 地图是结构的抽象！,概念的抽象（不是模型！）：楼群、居住小区、公共场所与设施、商区、政府机关、河流、湖泊、公交线路、各级公路、快速路、高速路、立交桥等等。,目的：城市交通研究,抽象出结构：小区、商区、立交桥、道路、交叉路口等概念的关联和区分忽略细部特征、概念的部分内涵、人口结构等等。,模型表示：城市交通地图,同一个集合，不同结构原型的意义不同。,例 语言,下雨天 留客天 留我不留,下雨天留客 天留我不留,语言的结构不同，含义不同（数据同）。,3、核心是结构,理解原型的结构，抽象

6、并表示结构是核心问题。,例.语言的不同结构产生不同的文学信息,唐诗 清明时节雨纷纷 路上行人欲断魂 借问酒家何处有 牧童遥指杏花村,宋词 清明时节雨 纷纷路上行人 欲断魂。 借问酒家何处 有牧童 遥指杏花村。,剧本(元曲) 清明时节 雨纷纷 路上 行人（欲断魂）： 借问酒家何处有？ 牧童 （遥指）: 杏花村。,时间 环境 地点 人物 语言 另人物 动作 语言,抽象出结构:,七言唐诗 ,比较规整,适于言志“诗言志”,宋词 ,错落有序,用语活跃,适于抒情“词抒情”,元曲 时间、地点、 情景、人物、 动作、言语 等。用语白话，易懂。,百姓故事,结构的不同表示可以表现出文学基调不同：,用音高表示：,唏

7、 唏 唏 唏,唏啦嫂发米来斗,嫂 啦 米 啦 嫂 米,规则,变化,4、模型抽象度与数学的普适性,1）、科学的依赖序关系与抽象度,这种单调的依赖关系由科学领域的物质组成决定,扩展的科学与技术的抽象递减顺序： 数学物理化学生物工程技术 社会科学,2）、模型的抽象度依科学序关系递减,模型表示的抽象度依次递减，表现出普适性。,结构主义学派（ Bourbaki ）： 数学 = 集合 + 结构,5、数学与普适性,数学的普适性一直被数学家与哲学家研究，笛卡儿、开普勒、牛顿、莱布尼茨等：大自然中隐藏着一种固有的和谐，反射到我们的心智中就呈现简单数学定理的形式。,1）、数学是什么？,这是一个困难的问题，并没有唯

8、一的答案。,2）、数学的普适性,原型：具体的元素与部件具体的结构,数学：抽象的元素抽象的结构,数学研究的内容决定了数学的普适性！,四、结构主义数学建模,“定义”： 模型原型结构的适当表示； 数学：集合+结构，数学是研究结构的， 数学模型：原型结构的数学表示。 “定义” 如何建模？,3）推导模型公式 完善模型的假设，并表示成适定的形式。,4）求解模型 选择正确的解法，特别是数值计算与分析。,5）回答问题 解释数学解，分析鲁棒性和近似假定，确定解对于问题的作用。,2）选择建模方法 利用经验、技巧和文献选择解决问题的一般性求解方法。,1）提出问题 列出所有变量、单位和所有假设，并表示。用数学表达式给

9、出问题的目标。,1、目前的方法,一般建模程序，Mark M. Meerschaert的著作“Mathematical Modeling”中，提出数学建模的五步法：,抽象什么、怎么抽象？ “抽象”是最抽象的！,结构化建模方法： 提供分析的方法分析结构的方法， 学习原型结构的表示方法建立专业模型，学习数学结构并产生建模的可操作程序。,结构化建模方法不是排斥“五步法”，而是充实“第二步”的具体可行的方法。,2、结构化数学建模程序,数学语言表示的结构,数学模型,专业语言描述结构,专业模型,分析出原型的结构，并用数学语言表示的模型。,一般流程：,有些问题专业模型难，有些问题数学模型难。,对原型确定目的,

10、1、在线文本自动分析,原型的目标： 在线电子文本的计算机自动分类与辅助理解。 理解基于分类，分类是理解的主体，理解就是分类！,两类“分类模型”的目标： 检索性分类国际图书分类法，目的是查询；,理解性分类基于语意、概念层、主题层的细分类，目的是分析和理解。,）、建立专业模型,五、结构化建模例子,原型的结构分析,文本章节段落语意团 句或短语词字符,文本的结构：,原型有两层结构：文本的结构； 文本集合的结构。,分析：文本集合的结构依赖于文本的结构； 文本集合的结构是原型对于目的的主要结构； 因此文本的结构的表示要有益于文本集合的结 构的描述。,原型的专业模型（源于关键词和摘要的作用的理解）,模型1.

11、 以关键词频为特征的分类模型,词: 有语意的初级字符串单位语言的细胞；,词在文本中的频率与不同类文本间频率差别是分类的基本特征和基本的结构性差别。,模型2. 以语意团为特征，重在语意差别的分类。,模型3. 混合模型,语言能力模型：乔姆斯基的语法结构模型是另一类语言模型。,文本集合的结构分析：分类是在文本的集合中进行，因此是原型的用于分类目标的主要结构。,联想到数学中的结构，例如代数结构，是在集合中定义代数运算加法和数法：元素间的运算关系,两个文本的合并还是文本加法封闭； 一个文本的倍数仍然是文本数乘封闭！,分析文本集的结构，首先是文本之间的相互关系： 两个文本合并是什么？还是文本！,）、同构分

12、析,同构： 此时问题的原型的结构直接和数学结构联系起来！ 建立原型结构的数学表示则建立了数学模型。,文本的集合应该有一个“线性空间”的结构； 文本的分类是在线性空间中的“向量的分类”！,具有高等代数的知识，对于线性代数的结构有清楚的理解和关注，则容易发现：,以上分析导至文本向量的概念：,每个文本对应地定义一个文本向量，用于分类。 分量如何定义？,显然，分量是“分类特征”的具体表示：,基于词频以及用于区分文本的量化的表示分析！,模型1的数学模型：向量空间的结构+词频特征。,）、同构表示与数学建模,根据专业模型，词频及具有分类的特征信息，因此可以仿照熵的定义：,假设TF(w(i),dj)是词w(i

13、)在文本dj中出现的次数，|D|是D中文本总数，DF(w(i)是指在D中至少出现一次w(i)的文本数。则每一个文本djD，和一个特征词w(i）存在一量：,这里熵的形式，一来用类似信息熵的定义，符合“分类”的特征信息的概念；二来，词频的作用大于词在文本集合中出现的作用。,记d(i)j =TFIDF(w(i),dj) ，则每一个文本djD，存在一个分量适当排序的文本向量:,文本集合的数学模型文本的特征向量空间。 分类问题是N维线性空间的向量的分类问题。,许多方法可以用于求解，例如SVM分类器对于数据压缩很有效。,文本自动分类: 理解文本的类属性,子空间分类. 文本自动聚类: 发现文本集合中的新模式

14、,新概念.,文本向量: 由文本的实意词的特征值或特征模式为分量的向量. 以信息熵的形式构造.,特征子空间: 具有某种共同意义的分量组成的子空间.,文本向量空间: 全部文本向量的高维线性空间.,应用事例：思想史研究中，“五四” 运动的讨论的主要思想是什么？,发现在“自由主义”的特征词所在的子空间中，文本的投影数量最大！,高维问题； 训练集的数据量大； 理解性细分类的精度低。,主要数学问题和某些进一步研究课题：,1、SVM的微分几何方法；,2、词频分布特征的研究，用分布特征分类和理解；,3、添加语意的分类模型；,4、大规模数据挖掘方法寻找分类模式与规则。,2、结构化建模的研究课题（概要）,系统地提

15、出结构化的建模方法是我们的首次尝试，因此方法实施的细节还远不成熟，有大量需要研究的问题。,1）分析原型结构的方法 利用皮亚杰的结构定义的“三性”：整体性、转换性和自调节性对于不同专业或领域建立分析方法；,2）建立在具有相同结构的不同集合（领域、专业、问题）之间的同构方法；,3）、研究数学方法的结构 三种数学母结构：序结构、代数结构和拓扑结构；其他数学方法的结构都是母结构的：组合或复合，形成复杂结构（布尔巴基的数学基础）。,4）、研究一些应用广泛的实际模型的数学表达（同构），例如网络模型。,5）、模型化方法将从数学模型扩展到数据模型。因此，研究数据结构和实际问题的原型结构的同构关系是一个新的领域

16、。,六、复杂系统建模与复杂网络,系统：集合（具体元素）+ 结构。 一切系统的基本结构都是网络； 一切系统的核心结构都是逻辑网络； 一切系统的逻辑网络中都有高阶逻辑。,复杂系统的基础数学模型：复杂网络,二十一世纪最重要的一类数学模型,复杂系统的结构：在系统中，元素以及部件之间关联的总和，具有以下性质： 1）整体性（封闭）； 2）转换性（运算）； 3）自调节性（守恒）； 4）可以形式化表达（数学）。 （皮亚杰：结构主义）,1、什么是复杂网络,2、为什么二十一世纪研究复杂网络？,二十一世纪涌现的新现象： 万维网是怎样“链”接的？ 计算机病毒是怎样传播的？ 传染病是怎样扩散或“消失”的？ 流言的传播速

17、度有多快？ 城市交通涌堵的机理是什么？ 金融和股票市场是如何变化的？ 什么是“系统生物学”？ 等等、等等、？,复杂网络研究的简史,Scientific Collaboration Network,Pl Erds (1913-1996) Oliver Sacks: A mathematical genius of the first order, Paul Erds was totally obsessed with his subject - he thought and wrote mathematics for nineteen hours a day until the day he d

18、ied. He traveled constantly, living out of a plastic bag, and had no interest in food, sex, companionship, art - all that is usually indispensable to a human life.,Santa Fe研究所的科学家合作网,Complex Network Example: WWW,Complex Network Example: Telecomm Networks,Complex Network Example: Routes of Airlines,F

19、ig. 4：New York State electric power grid,Complex Network Example: Biological Networks,Food Web,Nodes: trophic species Links: trophic interactions,R.J. Williams, N.D. Martinez Nature (2000),3、研究主要内容 复杂网络理论的主要研究内容可以归纳为：,发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法。 建模：建立合适的网络模型以帮助人们理解这些统计性质的意义与产生机理。 分析：基于单个节点的特性和

20、整个网络的结构性质分析与预测网络的行为。 控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。,二十一世纪复杂网络研究取得突破性进展的主要原因包括：,1）系统学方法已经成为科学与技术研究的重点，而系统的基本结构是网络。 2）越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据。 3）学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。 4）以还原理论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。,网络与复杂网络将成

21、为二十一世纪的新科学领域！,4、复杂网络的基本建模方法数据挖掘,近年来在Science, Nature, Physics Rev. Letter等杂志发表了大量研究和探讨复杂网络的文章，人们发现真实世界的复杂网络不同于Erds等数学家研究的经典随机图，发现相差甚远的领域形成的随机复杂网络具有惊人的相同的统计特征.,因此，复杂系统的网络模型不能只是用已经在数学上定义的几种网络去套用，除了已经知道系统元素之间的关联机制，通过数据分析的方法建模是最基本的方法。,例、关联规则、统计相关性建模 无向网， 有向网， 混合网络， 加权网，等等。,中国淮扬菜肴网,顶点原料食品 边菜肴中两种食品之间的相互作用

22、每道菜肴局域世界（完全图） 通过公共顶点连接构成中国淮扬菜肴网。 329道菜肴，242个顶点（食品），1713条边。 中药方剂网与此类似。,5、系统发生谱的高阶逻辑网络建模,2004年Bowers系统地建立了对蛋白质系统发生谱数据的逻辑分析方法（logic analysis of phylogenetic profiles，简称LAPP）。由于对一个复杂系统来说，清楚地了解所有元素（或部件）之间的关系是十分困难的（例如基因之间作用机理），直接进行机理性建模并不是普遍可行的。在Bowers的文章中给出的LAPP与通常的机理建模方法不同，它是一种从元素的表达数据出发，通过一系列有效的逻辑分析，发现

23、元素之间的逻辑关联性的方法。这就使得通过数据分析建立逻辑性的机理模型成为可能。 这种方法显然地可以用在几乎任何复杂系统中，它的最终作用是为复杂系统建立逻辑网络。,* Bowers P M, Cokus S J, Eisenberg D, et al. Use of Logic Relationships to Decipher Protein Network Organization. Science, 2004, 306(5706): 2246-2249,二阶逻辑例 超市数据分析，在国外会注意到面包、牛奶和芝士是常常一同采购，但是有一部分人买牛奶就不买芝士，或者买芝士就不买牛奶，于是就有二阶

24、逻辑： 设C是面包，A是牛奶，B是芝士，则C=AB，但是方向要根据条件熵给定。 但是，如果由此注意到概念分层，就可以发现在层之间会有一阶逻辑的关联规则，如果E记“奶制品”，则：E C. 如是，逻辑在属性概念分层，关联规则分析都有用，而且逻辑还和数据划分有直接关系。,1当且仅当AB同时存在时，C才存在； 2当A缺失或B缺失时，C才存在； 3当A存在或B存在时，C存在； 4当且仅当AB同时缺失时，C才存在； 5当A存在且B缺失时，C存在，或当B存在且A缺失时，C存在； 6当A存在或B缺失时，C存在，或当B存在或A缺失时，C存在； 7当AB其中之一存在时，C存在； 8当AB同时存在或同时不存在时，C

25、才存在；,Motif图是现实网络中比起对应的随机网络中显著多的子图，其具有特定的功能，是复杂网络的基本组成模块。利用相对的Motif图可以逐步的构建完善整个网络。,在Motif图中，节点处的“”代表关系“或”；节点处没有“”代表关系“与”；线上加“”代表“非”；箭头“”代表能够表达。,逻辑网络建模,二阶逻辑关系的基因表达网络图,6、逻辑网络研究例,2007年与南依利诺依大学合作，建立拟南芥在外界刺激下，基因表达谱数据建立逻辑网络，以及通过动力学模拟发现： 1）存在大量二、三阶逻辑，构成复杂的含高阶逻辑的逻辑网络； 2）模拟网络的时间动力学，发现不同的初值具有不同的动力学稳态或多稳态； 3）存在二周期稳态解； 等等。,复杂逻辑网络建模有极大的发展空间！,问题： 1）统计量是能够反映网络的什么结构？特别是逻辑网络的结构？ 2）网络的分层结构与社区结构问题； 3）网络结构的形式化； 4）关键节点的识别； 5）调控机制； 6）复杂网络分类； 7）网络演化动力学； 8）复杂系统的非线性逻辑建模与数据建模。,复杂网络研究的综述与