数据仓库9.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,昆 明 理 工 大 学,第9章,公 式 发 现,1,.,目录,9.1公式发现概述,9.2科学定律重新发现系统,9.3经验公式发现系统,2,.,9.1 公式发现概述,在科学发展史上，各种物理学、化学、天文学中的自然规律都是著名科学家对大量的实验数据进行深入的研究，最后得到了自然规律。,如牛顿三大定律、万有引力定律、开普勒行星运行定律等。这些,自然定律是科学发展和社会进步的奠基石,。,3,.,在大量的工程问题中，同样存在着大量的实验数据需要人们去寻找它们的规律性。,在找到完全精确的规律性之前，一般用经验性规律（带有一定的误差）来代替，去完成工程计算、设计和施工。,经验规律的发现一般是由有经验的工程师来完成的。,4,.,随着计算机的出现，发展了数据拟合技术。它是数值计算的重要分枝。,数据拟合是利用科学试验中得出的大量测量数据，去求得自变量和因变量的一个近似公式。,数据拟合任务：,从科学试验中得到的大量测试数据，（例如N个（x,i,，y,i,），去求得自变量x和因变量y的一个近似解析表达式,yf(x),这种公式统一表示为代数多项式形式，它的系数由最小二乘原理建立正规方程组求出。,5,.,存在问题：,当它的次数增大时，使线性方程组系数行列式出现“病态”（即行列式元素微小变化引起解的大变化）。,有效方法：,采用正交多项式的方法来逼近试验数据，使逼近公式的效果大为提高。（如勒让德多项式）,6,.,数据拟合方法,在科学试验或统计研究中，人们常常需要从一组测定的数据。,已知,N,个点,(x,i,，y,i,),去求得自变量,x,和因变量,y的,一个近似表达式：,y=(x),这就是数据拟合问题。根据数据之间的关系给出它们之间的数学公式有：,y*=a,0,+a,1,*,1,(x)+a,2,*,2,(x)+,+a,k,*,k,(x),7,.,在曲线拟合中，一般取,k,(x)x,k,或者 正交多项式,总之，y的表达式是多项式形式。,其中a,0,、a,1,、a,2,a,k,各个系数的确定常用的是最小二乘法，即使各点的误差平方和最小：,(y-y*),2,=,(y-(a,0,+a,1,*,1,(x)+a,2,*,2,(x)+,+a,k,*,k,(x),2,=min,8,.,选择a,0,、a,1,、a,2,a,k,使误差平方和最小，可以用数学分析中求极值方法，即函数(a,0,，a,1,，a,2,，a,k,)对a,0,、a,1,、a,2,a,k,求偏微商，再使偏微商等于零，得到a,0,、a,1,、a,2,a,k,应满足的方程：,9,.,求得这组方程的解a,i,，即可得拟合公式。,用多项式作逼近公式：,数据拟合方法虽然能解决一些实际问题，但是它把寻找公式的范围限制在多项式形式之内。,正交多项式一般表示都很复杂，如勒让德多项式。这对使用者来说很不直观，建立不起各个变量之间的直观概念。,缺点：,公式不直观,10,.,化学反应中,浓度随时间变化,数据：,时间（分）,浓度y(*10,-4,）,时间（分）,浓度(y*10,-4,）,5,1.27,30,4.15,10,2.16,35,4.37,15,2.86,40,4.51,20,3.44,45,4.60,25,3.87,50,4.66,11,.,用数据拟合方法，得出公式,：（用5次正交多项式逼近）,Y=Q,5,(x)=3.26p,0,10,(x)-2.15p,1,10,(x)-0.19p,2,10,(x)-,0.16p,3,10,(x)-0.02p,4,10,(x)-0.01p,5,10,(x),其中p,m,n,（x）称为,勒让得德项式,（正交多项式）,它的通式为：,其中,x,(k,),=x(x-1).(x-k+1),12,.,具体有：,P0,n(x)=1,P1,n(x)=1-2x/n,P2,n(x)=1-6x/n+6x(x-1)/n(n-1),P3,n(x)=1-12x/n+30 x(x-1)/n(n-1)-20 x(x-1)(x-2)/n(n-1)(n-2),P4,n(x)=1-20 x/n+90 x(x-1)/n(n-1)-140 x(x-1)(x-2)/n(n-1)(n-2)+70 x(x-1)(x-2)(x-3)/n(n-1)(n-2)(n-3),P5,n()=1-30 x/n+210 x(x-1)/n(n-1)-560 x(x-1)(x-2)/n(n-1)(n-2)+630 x(x-1)(x-2)(x-3)/n(n-1)(n-2)(n-3),-252x(x-1)(x-2)(x-3)(x-4)/n(n-1)(n-2)(n-3)(n-4),13,.,随着人工智能技术的发展，近10年来，机器发现技术得到发展。比较典型的系统有：,科学定律发现系统,BACON,，数学概念发现系统,AM,等。它们都造成了巨大的影响。,对于科学发现的自然规律，用数据拟合的方法在计算机上是绝对得不出来的。只能采用新的途径，这就需要用人工智能技术来完成。,BACON,系统就是在这种思想指导下产生的。,14,.,机器发现学习是从一组观测结果或数据中归纳出这些数据的一个或多个规律。,例如容器中的气体，人们能够观察到的具体数据是温度（T）、体积（V）和压强（P），它们之间的规律性是这些属性项之间的关系式（即PV/T=K）。发现学习的人们就是找出能够解释给定数据集合的规律性。,15,.,发现学习有两种方式：数据驱动方式和模型驱动方式。,数据驱动方式,是根据在搜索数据中所发现的数据的规律性，采用不同的归纳发现动作，在一系列归纳发现动作之后形成所发现的经验规律。,已知：一组观测结果或者试验数据,求解：能够概括这组数据的规律,典型系统：,1、科学定律发现系统BACON（Pat.Langly）,。,2、经验公式发现系统FDD（陈文伟等）,16,.,模型驱动方式,的典型例子是数学概念发现系统,AM,。,它包括了各种各样的搜索法（242个启发式规则）指导在数据领域中的搜索，从集合、表、项等1000多个基本数学概念出发，,AM,使用具体化、一般化、类比、复合等操作去产生新的数学概念，如得出自然数、质数等重要的数学概念。,AM,系统还找到了与这些概念有关的定性规律，如唯一因子分解定理等。,17,.,9.2,科学定律重新发现,系统,9.2.1,BACON,系统基本原理,1.,BACON,系统的思想,BACON,系统是运用人工智能技术从试验数据中寻找其规律性比较成功的一个系统，是,Pat Langly,于,1980,年研制的。,它运用数据驱动方法，即这种方法使用的规则空间与假设空间是分开的。,系统的规则空间包括若干精炼算子，通过精炼算子修改假设。,所谓精炼算子就是修改假设空间的子程序，每个精炼算子以特定的方式修改假设空间。,假设空间决定选用规则空间哪个精炼算子。,18,.,规则空间,(精练算子空间),假设空间,(训练例和新项),选择,修改,19,.,这类学习方法的大致步骤为：,步骤,1,收集某些训练例,放入假设空间。,步骤,2,对训练例进行分析，决定应该使用的精炼算子。,步骤,3,使用选出的算子修改当前的假设空间,重复执行步骤1到步骤3直到取得满意的假设为止。,BACON,系统的思想是程序反复地考察数据并使用精炼算子创造新项，直到创造的这些项中有一个是常数时为止。,于是一个概念就用“项常数”的形式表示出来，其中项为变量运算的组合而形成的表达式。,20,.,2.,BACON,系统主要精炼算子,（1）发现常数,当某一属性特征向量取某一值至少两次的时候，触发这个算子，该算子建立这个特征向量等于常数的假设。,（2）具体化,当已经建立的假设同数据相矛盾时触发这一算子，它通过增加合取条件的形式把假设具体化。,（3）斜率和截距的产生,当发现两个特征向量是线性相互依赖时触发这一算子，它是建立线性关系的斜率和截距作为新项。,21,.,（4）乘积的产生,当发现两个特征向量以相反方向递增但又不线性依赖时触发该算子，产生两向量的乘积作为新项。,（5）商的产生,当发现两向量以相同方向递增但又不线性依赖时触发该算子，产生两向量的商作为新项。,（6）模,n,项的产生,当发现两向量v,1,和v,2,在模某一数n相等时触发这一算子，产生,v,2,(mod n),作为新项。,22,.,9.2.2 BANCON系统实例,1.开普勒行星第三定律的发现,2.理想气体定律的发现,23,.,BACON系统发现开普勒行星第三定律,P行星运行周期 d行星离太阳距离,p,d,d/p,d,2,/p,d,3,/p,2,水星,1,1,1,1,1,金星,8,4,0.5,2,1,地球,27,9,0.33,3,1,简化数据,24,.,实际数据,P（天）,d（百万公里）,d,3,/p,2,水星,88,58,25.19,金星,225,108,24.88,地球,365,149,24.80,火星,687,228,25.13,木星,4343.5,778,24.93,土星,10767.5,1430,25.29,开普勒行星第三定律:,d,3,/p,2,=25,25,.,2.理想气体定律的发现,理想气体有4个变量：体积（,V,）、压强（,P,）、温度（,T,）和克分子个数（,N,）。,V,P,T,N,I,1,I,2,I,3,I,4,I,5,I,6,I,7,I,8,I,9,I,25,I,26,I,27,.0083200,.0062400,.0049920,.0085973,.0064480,.0051584,.0088747,.0066560,.0053248,.0266240,.0199680,.0159740,300,000,400,000,500,000,300,000,400,000,500,000,300,000,400,000,500,000,300,000,400,000,500,000,300,300,300,310,310,310,320,320,320,320,320,320,1,1,1,1,1,1,1,1,1,3,3,3,26,.,为了发现它们之间的规律，先取变量,T,和,N,的相同的数据（如前三列中,T,=300，,N,=1），对变量,V,和,P,进行发现，由于,V,、,P,两变量以相反方向递增，利用BACON精炼算子，建立两变量相乘的新变量,PV,，且,PV,等于常数2496。,对于另一组相同的数据（,T,=310，,N,=1），利用相同方法得到,PV,新常数2579.1999。这样得到新的理想气体数据，,V,P,T,N,I,1,I,2,I,3,.0083200,.0062400,.0049920,300,000,400,000,500,000,300,300,300,1,1,1,27,.,PV,T,N,I,1,I,2,I,3,I,4,I,5,I,6,I,7,I,8,I,9,2,496,2,579.1999,2,622.3999,4,991.9999,5,158.3999,5,324.7999,7,488,7,737.5999,7,987.2,300,310,320,300,310,320,300,310,320,1,1,1,2,2,2,3,3,3,合并PV变量后的理想气体数据,28,.,新变量,PV,，它和变量,T,和,N,仍是三个变量。为了有效地发现它们之间的规律，仍先固定变量,N,，研究变量,PV,与,T,之间的关系。上表中每三行数据均为,N=,1、2、3是常数的数据。,分析在,N,=常数的三行数据中，变量,PV,与,T,是以相同方向递增，利用BACON精炼算子，建立两变量相除的新变量,PV/T,，且新变量等于常数（不同,N,时，,PV/T,常数不同）。这样，得到的理想气体数据:,29,.,PV/T,N,I,1,I,2,I,3,8.32,16.64,24.95,1,2,3,最新的理想气体数据,30,.,上表中数据是两变量,PV/T,与,N,的数据。,分析两变量,PV/T,与,N,的变化关系。两变量以相同方向递增，利用BACON精炼算子，建立两变量相除的新变量,PV/T/N=PV/TN,，得到常数8.32.,按BACON精炼算子，发现公式为：,PV/NT=8.32,31,.,9.2.3,BACON,系统的进展,BACON,系统共有五个版本,，不同的版本其规则空间也不同。,1.,BACON.1,提出了六条精练算子，发现了开普勒定律。,2.,BACON.2,是,BACON.1,的扩展形式，它包括两条附加的运算程序，能够发现递归序列并通过计算重复差的方法产生多项式，,BACON.2,的能力有很大提高，可以解决一大类序列外推的任务,。,32,.,3.,BACON.3,由大约86个产生式规则组成，共分七组,，各组产生式规则负责不同的任务，有的负责直接搜索观测数据，有的负责数据的规律性，有的计算项的值，有的把新项分解为它的组成部分。,BACON.3,发现的规律有：,理想气体定律：,pt/nt=k,1,Kepler,第三定律：,d,3,/(a-k,2,*t),2,=k,3,Coulomb,定律：,f*d,2,/q,1,*q,2,=k,4,Galileo,定律：,d*p,2,/lt,2,=k,5,Ohm,定律：,t*d,2,/(l,c,-k,6,*c)=k,7,33,.,4.,BACON.4,把使用了启发式搜索方法,：,程序总是注意两个数值变量之间增加和减少的单调关系，如果斜率为常数，则系统建立两个新的推理项（斜率项和截距项）作为有关变量的线性组合。,如果斜率是变化的（不是线性关系），则,BACON.4,计算有关项的乘积或比值，并把这个变量当作一个新的推理项，,BACON.4,又发现了若干自然规律：,Snell,折射定律：,sin(i)/sin(r)=n,1,/n,2,动量守恒动量：,m,1,*v,1,=m,2,*v,2,万有引力定律：,F=G*m,1,*m,2,/d,2,Black,比热定律：,c,1,*m,1,*t,1,+c,2,*m,2,*t,2,=(c,1,*m,1,+c,2,*m,2,)t,f,34,.,5.,BACON.5,增加简单的类比推理发现守恒定律。,对两个物体具有完全相关项，,BACON.5,推测最后的定律是对称的。,在物理中普遍存在的对称定律可以很容易的发现。,BACON.5,发现了能量守恒定律。,35,.,9.3.1,FDD.1,系统基本原理,经验公式发现系统,FDD(Formula Discovery from Data),是我们应用人工智能技术的机器发现技术和数值计算中的曲线拟合技术以及可视化技术结合起来自行研制的系统。,它是从大量试验数据中发现经验公式。逐步完成任意函数的任意组合（线性组合、初等运算组合、复合函数运算组合等），对自然规律和经验规律的发现。,9.3,经验公式发现,系统,36,.,1、问题描述,给定一组可观察变量,X(x,1,x,2,x,n,),以及这组变量的试验数据,D,i,(d,i1,d,i2,d,in,),i=1,2,3,m,公式发现系统找出该组变量满足的数学关系式：,f(x,1,x,2,x,n,)=c,其中,c,为常数,对于任意一组试验数据,(d,i1,d,i2,d,in,),均满足关系式:,f(d,i1,d,i2,d,in,)=c,37,.,找出的关系式,f(x),是任何形式的数学公式，包括分段函数。,对于关系式,f(x,1,x,2,x,n,)=c,的复杂程度可分为：,(1)变量的初等运算,f(x,y)=xy,其中,:,+、-、*、/,。,(2)变量的初等函数运算,f(x)=c,其中,f(x),为初等函数。,(3)初等函数的任意组合,f(x,y)=a,1,*,f(x)a,2,*,f(y),38,.,(4)复合函数的运算,g(f(x)c,其中,g(x),、,f(x),均为初等函数。,(5)复合函数的任意组合,h(a,1,*,g,1,(f(x)a,2,*,g,2,(f(y),，其中,h(x),、,g(x),、,f(x),均为初等函数。,(6)多个初等函数的组合,f(x,y)=a,1,*,f,1,(x)a,2,*,f,2,(x)a,k,*,f,k,(y),其中,f(x),、,f(y),均为初等函数。,(7)分段函数,对于不连续的点，分别用不同的函数加以描述。,以上是对两个变量的讨论。在现实世界中存在着多变量的更为复杂的关系，在机器发现过程中采用,先寻找两变量的关系，再逐步扩充为多变量的关系,的方法。,39,.,2、,FDD.1,的设计思想,FDD.1,系统的基本思想是利用人工智能启发式搜索函数原型、寻找具有最佳线性逼近关系的函数原型，并结合曲线拟合技术及可视化技术来寻找数据间的规律性。,（一）人工智能的启发式方法,启发式方法是求解人工智能问题的一个重要方法。,一般启发式是建立启发式函数，用以引导搜索方向，以便用尽量少的搜索次数，从开始状态达到最终状态。,40,.,FDD.1系统在执行搜索的过程中，对原型函数的搜索以及对它们的组合函数的搜索，也是一种组合爆炸现象。为解决这一问题，在设计系统时采用了启发式方法来实现。,对某一变量取初等函数和另一变量或它的初等函数进行线性组合，向直线靠拢。,即从原型库中选取逼近效果最好的少数几个初等函数作为基函数，并进一步形成组合函数，直至找到最后的目标函数。,41,.,FDD.1,系统的启发式函数形式为：,f(x,2,),a+b,*,f,1,(x,1,),线性逼近误差公式为：,dt=(a+b,*,f(x,1,)-f(x,2,)/f(x,2,),我们总是选取,dt,最小的,f(x,i,),作为继续搜索的当前结点。,这一启发式函数在以后的多次应用中证明是有效的。,42,.,3、,FDD.1,系统中的知识,在,FDD.1,系统中，知识采用的是产生式规则的表示形式,（ifthen）,主要的基本规则有：,规则1.发现常数,当某一变量,x,取一个常数，则建立该变量等于常数的公式，即：,x=c,规则2.两变量的初等运算组合,当两变量进行初等运算若等于常数，则建立该变量的初等运算关系式：,a,1,x,1,a,2,x,2,=c,其中,：、,*、/,43,.,规则3.变量取初等函数,当某变量取初等函数等于常数，则建立该变量的初等函数关系式：,f(x)=c,其中,f(x),为初等函数,规则4.两变量取初等函数的线性组合,两变量分别取初等函数后的线性组合等于常数，则建立两变量取初等函数的线性组合关系式：,a,1,f,1,(x,1,)+a,2,f,2,(x,2,)=c,其中,f,1,(x,1,)、f,2,(x,2,),为初等函数,规则5.某变量取某一初等函数与另一变量的线性组合,对某一变量,x,i,取初等函数后与另一变量,x,j,进行线性组合，若为常数，则建立关系式：,c,1,f(x,i,)+c,2,x,j,=c,44,.,规则6.,对某一变量,x,j,取初等函数，另一变量,x,i,取两个,x,i,的初等函数进行线性组合，若为常数，则建立关系式：,c,1,f,1,(x,i,)+c,2,f(x,i,)+c,3,g(x,j,)=c,规则7.建立新变量（启发式1）,若两变量的某初等运算接近常数，则建立新变量为该两变量的某种初等运算。,规则8.建立某变量的某种初等函数为新变量（启发式2）,若某变量的某种初等函数与另一变量或它的初等函数进行线性组合接近常数，则建立该变量的初等函数为新变量。,以上规则的嵌套或递归使用，将形成变量的任意函数间的任意组合。,45,.,试验数据输入,数据生成器,数据库,可视化,过程,数据项,（x,y）,初始处理,优化公式,继续发现,公式修正,原型,选择,公式,生成,原型,算法库,误差,分析,循环控制,公式发现控制,知识库,公式输出,可视化显示,公 式 库,9.3.2 FDD.1系统结构图,46,.,原型算法库,原型是构成数学公式的基本单元，原型算法库所包括的原型决定了系统的发现能力。本系统的函数原型由基本原型和组合原型构成。,基本原型由初等函数组成，如：,x、x,2,、x,3,、x,1,、x,2,、sqrt(x)、x,1/3,、log(x)、exp(x)、sin(x)、cos(x,)等,组合原型由初等函数的初等运算组合而成，如：,xsin(x)、xcos(x)、xexp(x)、xlog,10,(x)、x,-1,log,10,(x)、,x,-1,exp(x)、1/log,10,(x)、1/sqrt(x)、sin(x)+cos(x),等,在原型算法库中，每个原型都给出了一个算法，只不过每个算法的程序结构都非常相似。,用户还可以根据需要随意增加、删除原型。,47,.,9.3.3,FDD.1,系统开发的实例,1.行星运动开普勒第三定律的重新发现,原始数据:,行星运行的近似数据,开普勒第三定律搜索树,对于行星绕太阳运动的开普勒第三定律，我们利用变量取初等函数的线性组合趋向直线方程的思想,对该定律也重新发现，公式发现的搜索树如图,（,下页）,所示。,从搜索过程可见，,FDD,系统的公式的发现过程与,BACON,系统的公式发现过程是完全不同的,。,距离d,1,4,9,16,25,36,49,64,81,100,周期p,1,8,27,64,125,216,343,512,729,1000,48,.,(d,p),(f(d),p),(d,f(p),(d,sqrt(p),dt=2.541,(d,log(p),dt=2.240,(,log(d),log(p),dt=0.0001,(sqrt(d),p),dt=3.554,(log(d),p),dt=2.538,(1/d,*,log(d),p),dt=3.244,(,log(d),log(p)dt=0.0002,开普勒第三定律公式发现图,49,.,公式发现搜索树中有两个分枝,左分枝路径为:,先固定,d,，对变量,p,求各原型函数,f(p),用,d,和,f(p),拟合线性方程,f(p)=a+b,*,d,，求逼近,f(p),的相对误差,选误差最小的函数为,log(p)，,误差为,2.240,建立新变量,p=log(p)，,并固定它，再对,d,变量求各原型函数,g(d),对,log(p),和,g(d),拟合线性方程，并求逼近,g(d),的相对误差,选取误差最小者为,log(d),误差为0.00001,调用公式生成模块求得公式及系数，公式为:,log10(d)=0.0+0.666666667,*,log10(p),即为:,d,3,=p,2,从右分枝树也可发现开普勒第三定律,这里不再详述。,50,.,2.实例数据的公式发现,例如，炼钢厂出钢时所用盛钢水的钢包，在使用过程中由于钢液及炉渣对包衬耐火材料的侵蚀，使其容积不断增大，钢包的容积与相应的使用次数（即包龄的数据如下表所示：,使用次数x,容积y,使用次数x,容积y,2,3,4,5,7,8,10,106.42,108.20,109.58,109.50,110.00,109.93,110.49,11,14,15,16,18,19,110.59,110.60,110.90,110.76,111.00,111.20,钢包容积数据,51,.,对这组试验数据的搜索过程与例一相同，只给出了它的公式发现搜索树和最终公式形式，并与某书中方法及结果作以比较，公式发现搜索树见图,（下页）,。,52,.,(1/x,log(y),dt=0.00349,(x,y),(x,f(y),(f(x),y),(x,1/y),dt=0.065,(x,log(y),dt=0.0139,(x,sqrt(y),dt=0.0324,(log(x),y),dt=1.745,(1/x,y),dt=1.644,(1/x,*,log(x),y),dt=1.807,(f(x1),log(y),(1/x,g(y),(1/x,log(y),dt=1.76363,(log(x),log(y),dt=1.8228,(1/x,*,log(x),log(y),dt=1.7797,(1/x,1/y),dt=0.01647,(1/x,sqrt(y),dt=0.00823,钢包容积变化公式发现图,53,.,从右分枝开始搜索，我们得到了组成公式的两组基函数为：(1/x,log(y)；(1/x,sqrt(x)调用公式发现模块求得公式及系数，最终得到经验关系式为：,sqrt(y)=10.5591908-0.4711268*1/x （1）,dt=0.008233,log(y)=2.0472975-0.0392124*1/x （2）,dt=0.00349,经效果分析均满足误差要求。,这样我们用FDD系统发现了上述两个公式。,54,.,某书所讲述的公式为：,y=x/(0.008966+0.00083012x),（3）,这个公式是人们根据自己的专业知识和经验，并根据其离散点在图上分布形状选择适当的曲线公式来拟合数据，并经过一定的公式变形而得到的。,用,FDD,发现经验公式并不一定要求用户的经验、专业知识，用户只提供充分的试验数据，并作一些简单的交互，,FDD,系统很快便能发现效果良好的经验公式，这是,FDD,系统的一个显著优点。,由公式,(1)、(2)、(3),所拟合的每个点的,y,值分别用,y1、y2、y3,表示，它们各点的值见下表,(下页),：,55,.,说明了,FDD,系统发现试验数据的经验公式是成功的,。,x,y1,y2,y3,y,2,3,4,5,7,8,10,11,14,15,16,18,19,106.58,108.20,109.02,109.51,110.08,110.25,110.50,110.59,110.79,110.84,110.88,110.95,110.98,106.58,108.20,109.02,109.59,110.08,110.25,110.50,110.59,110.79,110.83,110.87,110.94,110.98,106.60,109.19,109.01,109.50,110.08,110.26,110.51,110.60,110.80,110.85,110.89,110.96,110.99,106.42,108.20,109.58,109.50,110.00,109.93,110.49,110.59,110.60,110.90,110.76,111.00,111.20,56,.,设给出的测量数据为：,一阶差分：,x,k,=x,k+1,-x,k,;y,k,=y,k+1,-y,k,;（k=1,2,n-1,）,二阶差分：,2,y,k,=y,k+1,-y,k,；,2,x,k,=x,k+1,-x,k,（k=1,2,n-2）,.,m阶差分,m,y,k,=,m-1,y,k+1,-,m-1,y,k,，,在这里差分指向前差分。,一阶差商,y,k,=(y,k+1,-y,k,)/(x,k+1,-x,k,)（k=1,2,n-1）,二阶差商,2,y,k,=(,y,k+1,-,y,k,)/(x,k+2,-x,k,)（k=1,2,n-2）,m阶差商,m,yk=(,m-1,y,k+1,-,m-1,y,k,)/(x,k+m,-x,k,),I,1,2,.,N,X,x,1,x,2,.,x,n,Y,y,1,y,2,.,y,n,934 FDD.2系统,57,.,规则1 差分发现常数。,当某一变量y的差分取一个常数c，则建立该变量等于常数的公式，即：,y=a+cx,。,规则2 差商发现常数,当两个变量y的差商取一个常数c，则建立该变量等于常数的公式，即：,y=c,。,58,.,规则3 特殊函数形式导数函数,（1）阶差（向前差分）法判定类型,若,2,y,i,=,定值，则方程为,y=a+bx+cx,2,；,若,3,y,i,=,定值，则方程为,y=a+bx+cx,2,+dx,3,；,若,(y,i,)-1,=定值，则方程为,y,-1,=a+bx,；,若,2,(y,i,2,)=,定值，则方程为,y,2,=a+bx+cx,2,；,若,2,(x,i,/y,i,),=定值，则方程为,y=x/(a+bx+cx,2,),；,若,y,i,成等比数列，则方程为,y=ab,x,+c；,若,log(y,i,),成等差数列，则方程为l,og(y)=,a+bx+cx,2,；,若,2,y,i,成等比数列，则方程为,y=ab,x,+cx+d；,59,.,（2）差商判定类型,若,log(y,i,)/log(x,i,),=定值，则方程为,logy=ax,b,；,若,log(y,i,)/x,i,=,定值，则方程为,y=ab,x,；,若,(x,i,y,i,)/x,i,=,定值，则方程为,y=a+b/x,；,若,(x,i,/y,i,)/x,i,=,定值，则方程为,y=x/(ax+b),；,若,y,i,/(x,i,2,),=,定值，则方程为,y=a+bx,2,；,60,.,规则4 两变量的导数运算组合,当某变量差分（或差商）后与另一变量进行初等运算若等于常数，则建立该变量差分（或差商）的初等运算关系式：,f(x,1,),f(x,2,)=c,其中,：、*、/,，其中.,f,为差分或差商计算。,规则5 两变量取导数运算的线性组合,两变量分别取导数运算后的线性组合等于常数c，则建立两变量取导数运算的线性组合关系式：,a,1,f,1,(x,1,)+a,2,f,2,(x,2,)=c,其中,f,1,(x,1,)、f,2,(x,2,),为导数运算。,以上规则和FDD.1中的规则的嵌套或递归使用，将形成变量的任意函数和导数运算组合。,61,.,FDD.2公式发现实例,导数函数公式的发现,x,y,为样本数据，,Y,为发现的公式计算值。,发现导数函数公式：y=1.52-4.34sin(x)，误差：0.048,x,1.01,2.07,2.98,7.89,7.02,6.03,6.98,8.01,9.04,9.99,11.02,12.01,12.97,y,4.61,10.51,14.65,14.61,11.08,10.2,12.6,18.27,27.3,24.46,22.08,19.72,20.93,Y,4.66,10.66,14.24,14.52,11.74,10.38,12.67,18.26,27.17,24.25,22.04,19.96,21.11,62,.,935 FDD.3系统,多维函数扩展规则（MultiRule）,（1）扩展到三维函数公式的启发式规则,设给定,n,组不同的数据,x,1,k,，x,2,k,，x,3,k,，k=1,2,3.n,，存在不同的函数,f,1,，f,2,，f,3,，f,4,以及常量,C,1,，C,2,，B,1,，B,2,，有如下函数关系：,如果在固定,x,3,的情况下得出,x,1,和,x,2,的方程为：,（9.13）,在固定,x,2,的情况下得出,x,1,和,x,3,的方程为：,（9.14）,从严格意义上讲,在式(9.13)中常数,C,1,C,2,是,x,3,的函数;在式(9.14)中的常数,B,1,B,2,是,x,2,的函数。,63,.,对于同一函数,f,1,(,x,1,)应该有关于,x,2,和,x,3,的统一的公式，故对,f,1,(,x,1,)而言在式(9.13)中确定了,x,1,与,x,2,的关系，式(9.13)中确定了,x,1,与,x,3,的关系，合并（9.13）（9.14）式，有如下启发式公式：,（9.15）,（9.16）,64,.,如果在固定x,2,的情况下得出x,1,和x,3,的方程为：,（9.17）,合并式（9.13）式（9.17）则有如下多个启发式公式：,（9.18）,其中为+、-、*、/等操作。,65,.,或者：,（9.19）,g函数的结构形式实质上是函数,f,2,和,f,3,的复合形式,由于,f,2,和,f,3,有系数项也有常数项,故,f,2,和,f,3,复合函数形式根据具体函数的不同有不同的合并方式,常见的是用一个公式的函数项去替换另外一个公式的系数和常数。,66,.,（2）扩展到四维函数公式的启发式规则,设在三维数据的基础上增加一维数据,x,4,如果得到公式,(9.20),(9.21),则有如下启发式公式：,(9.22),(9.23),67,.,（3）多维函数的扩展，通过增加函数变量的方法可以实现对多维函数变量公式的发现。,多维函数扩展规则给出了函数公式的具体框架表示形式，最后必须通过给定的数据对各个启发式公式进行检验，决定公式的取舍。,首先，通过实际给出的数据应用最小二乘法计算上式中各个常量的值；,其次通过给定的数据确定各个启发式公式的误差，最后进行选择，满足误差需求的公式即为所求公式。,68,.,折射定律的发现,实验数据如下表所示（液体，温度为20C）。,物质,从空气中入射率n,1,（n,1,i恒定）,从空气射入玻璃（n,1,n,2,恒定）,折射率n,2,入射角i,折射角,入射角i,折射角,丙酮,1.3585,30,21.60,30,19.47,苯胺,1.5863,30,18.37,35,22.48,苯,1.5014,30,19.45,40,27.37,二硫化碳,1.6279,30,17.89,45,28.13,四氯化碳,1.4607,30,20.02,50,30.71,肉桂醛,1.6195,30,17.16,55,37.10,氯仿,1.4453,30,20.24,60,37.26,乙醇,1.3618,30,21.54,69,.,设入射角为i，折射角为,，入射线所在介质的折射率为n,1,，折射线所在介质的折射率为n,2,。,因为光的可逆性，所以入射角和入射线的折射率与折射角和折射线的折射率两组数据可以互换，折射角,改为入射角i，入射角i变为折射角,，入射线和折射线所在位置的折射率也相应的调换。,对于从空气中入射到各介质，固定n,1,和i角后，应用二维函数公式发现算法，得到折射率和折射角的公式：,s,in(,)=0.5/n,2,（9.28）,70,.,反之，从介质中入射到空气时（n,1,变为n,2,，i角变为,角），固定n,2,和,角后，发现公式为：,sin(i)=0.5/n,1,（9.29）,在固定空气和玻璃两种介质时（n,1,n,2,恒定），入射角i和折射角,的关系，通过公式发现得：,sin(i)=1.5,sin(,),（9.30）,71,.,式（9.28）和式（9.29）两个公式从空气中入射不同物质的数据中生成，式（9.30）为从空气中入射玻璃的一组数据中生成。式（9.29）和式（9.30）应用三维扩展规则得：,sin(i)=C,1,sin(,)/n,1,+C,2,，即sin(,)=C,1,*,sin(i),n,1,+C,2,*,(9.31),对式（9.28）和式（9.31）利用四维扩展规则进行合并，得：,sin(,)=C,1,sin(i),（n,1,/n,2,）+C,2,(9.32),用已知的数据确定系数,得,C,1,=1，C,2,=0,，即得Snell折射定律：,sin(i),n,1,=sin(,),n,2,(9.33),72,.,FDD.1,、,FDD.2,和,FDD.3,的比较分析,FDD.2,是通过引入,导数规则,对,FDD.1,算法得规则进行扩充，同时修改算法流程，使得算法运行更加合理，扩大了发现公式的宽度和广度。,FDD.3,算法引入,多维函数处理规则,后对,FDD.2,算法进行了扩充，同时通过嵌套,FDD.2,算法流程，实现三维以上公式发现算法,FDD.3,。,73,.,比较方面,FDD.1,FDD.2,FDD.3,时间复杂度,O(8nm),O(2n,2,m),O（C,d,2,2n,2,m）,流程循环,函数作用于一个变量,不同的函数作用于两个变量,剪枝条件,误差最小原则,误差最小原则,误差收敛原则,误差最小原则,误差收敛原则,发现公式范围,初等函数、复合函数及其组合,在FDD.1基础上增加导数以及和导数相关的处理,在二维FDD基础上增加：,三维扩展规则,多维扩展规则,FDD.1、FDD.2和FDD.3的比较分析,74,.,BACON系统采用“项常数”的形式描述公式形式,FDD采用“项初等函数或初等函数的复合形式”，并且引入导数规则等,FDD和BACON相比发现公式的范围和复杂度都有很