(课程与教学论专业论文)一种基于数据挖掘和公式发现的智能教具系统.pdf_第1页
(课程与教学论专业论文)一种基于数据挖掘和公式发现的智能教具系统.pdf_第2页
(课程与教学论专业论文)一种基于数据挖掘和公式发现的智能教具系统.pdf_第3页
(课程与教学论专业论文)一种基于数据挖掘和公式发现的智能教具系统.pdf_第4页
(课程与教学论专业论文)一种基于数据挖掘和公式发现的智能教具系统.pdf_第5页
已阅读5页,还剩61页未读, 继续免费阅读

(课程与教学论专业论文)一种基于数据挖掘和公式发现的智能教具系统.pdf.pdf 免费下载

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

文档简介

摘要教育创新是一个民族的灵魂,是一个国家兴旺发达的不竭动力。新的教学理念也必须有相应的教学手段给予支持。随着现代信息技术与计算机技术的飞速发展,许多新的技术都应用到教育领域,促进着教育技术的进步,为现代教育技术注入了新的内容。人工智能是信息技术发展的重要方向之一。世界各国都在开展智能教具的研究工作,智能型教学仪器的发展方向是智能化和小型化。我国教学用具的特点主要表现为:智能化程度低、系统尺寸庞大,现行教具只能为学习者提供进行验证型实践活动的支持,对学习者创造力和想象力的培养作用十分有限。目前,世界上只有美国德州仪器公司开发成功了手持式的具有知识发现能力的智能教具图形化计算器。但是,它在公式发现上仍然采用的是传统的数据拟合技术,存在着当行列式元素微小变化引起解的显著变化的问题,即线性方程组系数行列式存在“病态问题”。并且,图形化计算器发掘出来的公式只有多项式一种类型,知识形式单一、可理解性、可用性差。为了解决这个问题,本文采用人工智能理论、数据挖掘、知识发现与嵌入式系统设计技术相结合,研究新型智能教具系统。在本文中,我们对f d d ( f o r m u l a d i s c o v e r y f r o m d a m ) 公式发现的基本理论做了深入的研究,对f d d 基本理论中的误差计算、函数库( 原型库) 功能、搜索标准、以及误差比较做了改进和优化,并在此基础上,围绕f d d 的基本思想,在p c 机上实现了改进型f d d 公式发现系统。改进型f d d 公式发现系统可以对学习者所输入的实验数据进行公式挖掘,以初等函数的形式表示出实验数据之间的公式,并且通过大量实验证明其公式发现的效果比单纯按照f d d 基本理论所设计的系统有明显提高。另外,此系统具备强大的图形显示功能,能够将公式发现过程与结果以图形形式直观地呈现给学习者。改进型f d d 公式发现系统的实现为嵌入式智能教具系统的研究提供了算法原型,形成了整个项目中具有开创性的研究成果。关键词:教育创新;数据挖掘;知识发现;智能;教具;公式发现;f d da b s t r a c te d u c a t i o n a li n n o v a t i o ni st h es o u lo fan a t i o n , a n dt h ei n e x h a u s t i b l ep o w e rf o rt h ep r o s p e r i t yo fac o u n t r y n e wt e a c h i n gi d e a sm u s tb es u p p o r t e db yt h ec o r r e s p o n d e n tt e a c h i n gm e t h o d s w i t ht h er a p i dd e v e l o p m e n to fm o d e mc o m p u t e rt e c h n o l o g ya n di n f o r m a t i o nt e c h n o l o g ) ,m a n yn e wt e c h n o l o g i e sw h i c ha r ea p p l i e dt ot h ef i e l do fe d u c a t i o np r o m o t et h ep r o g r e s so fe d u c a t i o nt e c h n o l o g y , a n da d dn e wc o n t e n tt om o d e me d u c a t i o nt e c h n o l o g y a r t i f i c i a li n t e l l i g e n c ei so n eo ft h ei m p o r t a n td i r e c t i o n sf o r t h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y t h er e s e a r c ho fi n t e l l i g e n tt e a c h i n ga i d sh a sb e e nc o n d u c t e di nm a n yc o u n t r i e s t h ed e v e l o p m e n t a ld i r e c t i o no ft h ei n t e l l i g e n tt e a c h i n gi n s t r u m e n ti st h ei n t e l l i g e n c ea n ds m a l l s c a l e t h ec h a r a c t e r i s t i c so f0 1 1 1 t e a c h i n ga i d sa r el o wi n t e l l i g e n tl e v e la n dh u g es y s t e m a t i cs i z e t h e s et e a c h i n ga i d sl i m i tt h el e a r n e r sc r e a t i v i t ya n di m a g i n a t i o n a tp r e s e n t , o n l yt h et ic o m p a n yi nu s ah a ss u c c e s s f u l l yd e v e l o p e dg r a p h i cc a l c u l a t o rw h i c hi sp o r t a b l ea n dc a p a b l eo fk n o w l e d g ed i s c o v e r y b u ti ts t i l lu s e st r a d i t i o n a ld a t af i t t i n gi nf o r m u l ad i s c o v e r y i ti saq u e s t i o ni nt r a d i t i o n a ld a t af i t t i n gt h a ts m a l lc h a n g e so fd e t e r m i n a n te l e m e n tw i l ll e a dt oas i g n i f i c a n tc h a n g ei nt h es o l u t i o n i na d d i t i o n , t h ef o r m u l aw h i c hi sd i s c o v e r e db yg r a p h i cc a l c u l a t o ri so n l yaf o r mo f p o l y n o m i a l s ,w h i c hi sp o o ru n d e r s t a n d i n g i no r d e rt os o l v et h i sp r o b l e m , t h i sp r o j e c ts t u d i e sak i n do fi n t e l l i g e n ts y s t e mo ft e a c h i n ga i db a s e do na r t i f i c i a li n t e l l i g e n c e ,d a t am i n i n g ,k n o w l e d g ed i s c o v e r y , a n ds m a l l - s i z e de m b e d d e ds y s t e m t h i sp a p e rd i da ni n - d e p t hs t u d yo ff d d ( f o r m u l ad i s c o v e r yf r o md a t a ) b a s i ct h e o r y , a n di m p r o v e dt h ec a l c u l a t i o ne r r o r ,f u n c t i o nl i b r a r yf u n c t i o n s ,s e a r c hc r i t e r i a ,a n de r r o rc o m p a r i s o n o nt h i sb a s i s ,w er e a l i z e di m p r o v e df d ds y s t e ma r o u n dt h eb a s i ci d e ao ff d d t h ei m p r o v e ds y s t e mc a nd of o r m u l am i n i n gf o re x p e r i m e n t a ld a t aw h i c hi m p o r t e db yl e a r n e r s ,a n ds h o wt h ef o r m u l ao f t h ee x p e r i m e n t a ld a t ai nt h ef o r mo fp r i m a r yf u n c t i o n t h r o u g hn u m e r o u se x p e r i m e n t s ,t h ei m p r o v e ds y s t e mi sb e t t e rt h a no l ds y s t e mi nr e s u l t so ft h ef o r m u l ad i s c o v e r y i na d d i t i o n ,t h ei m p r o v e ds y s t e mc a no u t p u tt h ep r o c e s sa n dr e s u l to ft h ef o r m u l ad i s c o v e r yi nt h ef o r mo fg r a p h i c st h o u g hi t sp o w e r f u lg r a p h i c sd i s p l a y t h ei m p r o v e df d ds y s t e mp r o v i d e dap r o t o t y p ea l g o r i t h mf o rt h er e s e a r c ho fi n t e l l i g e n tt e a c h i n ga i db a s eo ne m b e d d e ds y s t e m ,s oi tl e a d st oag r o u n d b r e a k i n gr e s e a r c hr e s u l t si ne n t i r ep r o j e c t k e yw o r d s :e d u c a t i o n a li n n o v a t i o n ;d a t am i n i n g ;k n o w l e d g ed i s c o v e r y ;i n t e l l i g e n c e ;t e a c h i n ga i d s ;f o r m u l ad i s c o v e r y ;f d di i首都师范大学学位论文原创性声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名:7 名;z 和日期:2 刀年争月,2 - 日首都师范大学学位论文授权使用声明本人完全了解首都师范大学有关保留、使用学位论文的规定,学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质舨。有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。黜姗鹕。聪爹隰脚年日首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统第一章绪论1 1 研究智能教具的意义当时针指向二十一世纪,传统的教育观受到了严峻的挑战。在新的世纪里,信息化成了时代的主旋律,社会对高素质人才的需求使教育面临新的选择,教育创新已经成为每一个教育工作者都不能回避的问题。所谓“创新教育”指的是以培养人的创新精神和能力为基本价值取向的教育。这里所说的“创新”,是指通过对学生的教育和影响,使他们能够善于发现和认识有意义的新知识、新思想、新事物、新方法,掌握其中蕴含的基本规律,并具备相应的能力。这样的创新精神和能力几乎是人人都具有的,问题是我们能否通过恰当的教育将其开发和培育起来,这应该是当代教育的使命。教育创新是一个民族的灵魂,是一个国家兴旺发达的不竭动力。新的教学理念也必须有相应的教学手段给予支持。在当前,一本书、一枝笔的教学时代已不复存在。本项目研究的基于知识发现的智能教具有两种工作模式,一方面,它可以帮助学生通过实验结果验证基础理论,加深对理论知识的理解,另一方面,又可以通过对实验结果的分析与挖掘,帮助学生了解隐藏在大量数据之后的深层次的未知规律和新知。( 1 ) 探索归纳模式教学的目标不仅仅教会学生一些必要的基本知识,更深层次地,应该通过教学过程,培养学生的创新意识、创造精神和发现能力。探索归纳发现是创新和发明的基本思维框架。在我们的教学活动中,存在着大量的可采用上述框架进行思维活动的教学内容。因此在教学过程中应根据教育内容的特点,采用探索归纳模式的教学改革与实践方法,从而提高学生的创新意识和发现能力。( 2 ) 直观验证模式传统的理工科基础理论课比较强调严格的逻辑证明与分析,这对于培养学生的逻辑思维能力是有好处的。但严格的演绎证明也不是万能的,并不是唯一的证明方法与思维模式。在教学过程中应从多角度培养学生的思维活动,让学生既要学会由特殊到一般的思维方法,也要学会由一般到特殊的思维形式,猜想出来的结论可以采用演绎的方法进行严格的逻辑证明,也可以采用个例进行验证,虽然个例验证不是严格的逻辑证明,但也不失思维训练的实际意义。直观验证的教学模式可以使用基于知识发现的智能教具来验证所猜想的结论,实践由一般到特殊的思维过程。通过实验结果验证基础理论,大大加深了学习者对理论知识的理解。在一个国家的教育系统中,智能教学教具的发展水平和应用推广程度,对于教育现代化建设和创新知识工程具有重要作用。让学生使用现代化教学技术和手首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统段,自己探索新知识,亲身经历知识的形成过程,这对培养学生的创新精神与实践能力意义重大。随着现代信息技术与计算机技术的飞速发展,许多新的技术都应用到教育领域,促进着教育技术的进步,为现代教育技术注入了新的内容。人工智能是信息技术发展的重要方向之一,有许多研究成果己经进入人们的生活、学习和工作中,并对人类的发展产生了重要影响”1 。世界各国都在开展智能教具的研究工作,智能型教学仪器的发展方向是智能化和小型化。智能化主要是指通过机器的发现学习,帮助学习者分析实验数据、发现潜在规律、验证学生的设想,这对培养学生的创新能力和实践动手能力十分有益;小型化主要是为了方便学习者使用,在脱离计算机,甚至无室内电源供电情况下,便于学生充分利用时间进行实践、学习。目前,世界上只有美国德州仪器公司开发成功了手持式的具有知识发现能力的智能教具图形化计算器。1 。但是,它在公式发现上仍然采用的是传统的数据拟合技术,存在着当行列式元素微小变化引起解的显著变化的问题,即线性方程组系数行列式存在“病态问题”。并且,图形化计算器发掘出来的公式只有多项式一种类型,知识形式单一、可理解性、可用性差。我国教学用具的特点主要表现为:智能化程度低、系统尺寸庞大,现行教具只能为学习者提供进行验证型实践活动的支持,对学习者创造力和想象力的培养作用十分有限。造成这种现状的原因在于:我国传统的教学模式是“传授一接受式”,这种教育模式影响了我国智能教具的发展。创新教学是近期才提出的新的教学思想,因此,与之相应的教学手段还很不完善;基于知识发现的数据挖掘、公式发现技术都是新兴学科,它们对信息处理技术、现代教育技术的影响时间还很短,智能教具所提供的功能和技术水平不高;因此,为了适应创新教育的需要,解决我国现有教具存在的问题,本课题所依托的项目拟采用人工智能理论、数据挖掘、知识发现与嵌入式系统设计技术相结合,研究新型智能教具系统。1 2 研究现状及存在的问题1 2 1 公式发现方法综述在科学的发展史上,各种物理学、化学、天文学中的自然规律都是著名科学家对大量的实验数据进行深入的研究,最后得到了自然规律。如牛顿三大定律、万有引力定律、开普勒行星运行定律等,这些自然定律是科学发展和社会进步的奠基石。2首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统自然界存在着无数的规律,除了已经被发现的外,还有很多规律需要人们去继续发现。在大量的工程问题中,同样存在着海量的实验数据需要人们去寻找它们的规律性,在找到完全精确的规律之前,一般用经验性规律( 带有一定的误差)来代替,去完成工程计算、设计和施工“1 。随着计算机的出现,发展了数据拟合技术,它是数值计算的重要分支。数据拟合是利用科学实验中得出的大量测量数据,去求得自变量和因变量的一个近似公式。这种公式统一表示为代数多项式,它的系数由最小二乘法原理建立正规方程组求出”。但是,代数多项式存在的一个问题是,当它的次数增大时,线性方程组系数行列式会出现“病态”( 郎行列式元素微小变化引起解的大交化) 。另外,实际的动态测试数据千差万别,而且对动态测试数据进行回归分析的目的也不同,从而使得采用最小二乘法进行回归分析的结果达不到所要求的目的伽。为此,数值计算学者提出了采用正交多项式”1 的方法来逼近试验数据,这种方法使逼近公式的效果大为提高。数据拟合方法虽然能解决一些实际问题,但是它把寻找公式的范围限制在多项式形式之内,由多项式表示的逼近公式对使用者来说很不直观,建立不起各个变量之间的直观概念。例如:给出一组实验数据,其中变量x 为从1 0 到2 0 步长为0 0 5 的2 0 1 个值,变量y 满足关系式y = s i n ( x ) 。如果利用m a t l a b 软件提供的最小二乘法功能0 1 来拟合这组数据可以得到如下结果:y = 6 9 4 8 8 x 1 0 5 x 7 0 0 0 7 6 6 7 x 6 + o 3 5 6 6 9 x 5 9 0 6 1 9 x 4 + 1 3 5 7 1 x 31 1 9 7 6 x 2 + 5 7 6 6 x 1 1 6 8 8 9( 在m a t l a b 中选择最高次数为7 次的最小二乘法拟合)利用m a t l a b 软件中将变量x ,y 之间的关系曲线以及x ,y 之间的关系曲线放入同一坐标系中显示如图1 1 所示。图1 1 实际的正弦曲线与使用m a t l a b 拟合的近似公式的比较3首都师范大擘硕士论文一种基于数据挖掘和公式发现的智能教具系统如图1 1 所示,蓝色细线为原始实验数据曲线,红色粗线为利用最小二乘法拟合后所获得的公式曲线,两条曲线基本重合,拟合效果比较好。然而,如上所述,利用最小二乘法拟合得出的公式形式为高次多项式形式,从公式中无法得到任何直观的、能够反应实验数据之间规律的信息。比如:上面的例子中变量x 与变量y 本来是满足正弦函数规律的,且有周期性,但是,如果只从最小二乘法拟合的结果公式来看,所得公式反映不出两变量之问的周期性,这使得实验者无法建立起变量之间直观的本质规律,由此看来,对于科学发现的自然规律,使用传统的数据拟合方法是无法得到本原公式的,只能寻找新的途径。随着人工智能技术的发展,近l o 年来,机器发现技术得到发展。比较典型的系统有:科学定律发现系统b a c o n ,数学概念发现系统a m “”等,它们都产生了巨大的影响。机器发现学习是从一组观测结果或数据中归纳出这些数据的一个或多个规律“”“”。观测结果是符号的。饲如,容器中的气体,人们能够观察的具体数据是温度仃) 、体积o ,) 和压强p ) ,它们之间的规律性是这些属性项之间的关系式( 即p v t = k ) 。发现学习的目的就是让人们找出能够解释给定数据集合的规律性。发现学习有两种方式:数据驱动方式和模型驱动方式。数据驱动方式是根据在搜索数据中所发现的数据规律性,采用不同的归纳发现动作,在一系列归纳发现动作之后形成所发现的经验规律。b a c o n 系统就是在这种思想指导下产生的。b a c o n 系统是运用人工智能技术从试验数据中寻找其规律比较成功的一个系统,是p a tl a n g l y 于1 9 8 0 年研制的。它运用数据驱动方法,即这种方法使用的规则空间与假设空间是分开的。b a c o n 系统的思想是程序反复地考察数据并使用精炼算子创造新项,直到创造的这些项中有一个是常数时为止。于是一个概念就用“项= 常数”的形式表示出来,其中项为变量运算的组合而形成的表达式n u “。模型驱动方式的典型例子是数学概念发现系统a m 。它包括了各种各样的搜索法( 2 4 2 个启发式规则) 指导在数据领域中的搜索,从集合、表、项等1 0 0 0多个基本数学概念出发,a m 系统还找到了与这些概念有关的定性规律,如唯一因子分解定理等“”“”“”。经验公式发现理论f d d ( f o r m u l ad i s c o v e r yf r o md a m ) 是应用人工智能技术的机器发现技术和数据计算中的曲线拟合技术以及可视化技术结合起来的系统。它是从大量实验数据中发现经验公式,逐步完成任意函数的任意组合( 线性组合、初等运算组合、复合函数运算组合等) ,实现对自然规律和经验规律的发现”“。由于f d d 理论的基本思想是利用人工智能启发式搜索函数原型,寻找具有最佳线性逼近关系的函数原型,并结合曲线拟合技术及可视化技术来寻找数据间的规律性。因此,f d d 有效地解决了搜索中组合爆炸现象,运用启发式函数引导搜4首都师范大擘硕士论文一种基于数据挖掘和公式发现的智能教具系统索方向,可以最大限度地减少搜索次数,使系统尽快达到最佳状态“1 。1 2 2 本文的研究背景本课题依托教育部重点项目“基于嵌入式系统的智能教具研究”( 2 0 0 6 - -2 0 0 8 ) 和北京市自然科学基金项目“基于数据挖掘和公式发现的智能教具研究”( 2 0 0 6 2 0 0 8 ) 。1 2 3 开发环境与工具硬件仿真、测试平台:p c 机。最终硬件运行平台:脱离p c 机独立工作的嵌入式系统。前期软件工具:v i s u a lc + + 6 0 、m a t l a b 、m a t c o m 。最终软件工具:v h d l 语言。1 3 本文拟解决的问题本论文在充分调研和实践的基础上,以人工智能的理论为指导,结合数据挖掘、公式发现等方法和技术,以小型便携的嵌入式系统为基础,提出并建立基于知识发现的智能教具系统。本文的主要研究内容如下:( 1 ) 实验数据挖掘方法和经验公式发掘规则的确定;( 2 ) 确定具有最佳线性逼近关系的函数原型方法,引导搜索方向;( 3 ) 定义进行误差计算的评估函数和规则;( 4 ) 设计直观验证型模式、探索归纳模式算法:( 5 ) 开展实验与仿真分析研究。首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统第二章f d d 公式发现理论f d d 系统是由国防科技大学研制的一个基于试验数据库的经验公式发现系统。它运用了人工智能中的启发式搜索方法和数据处理中的曲线拟合技术,通过对所提供原型之间的线性组合和一定程度的复合不断逼近试验数据,最终得到蕴藏在大量实验资料中的经验公式。目前f d d 的基本理论中有3 个版本:f d d 1 、f d d 2 、f d d 3 。f d d 理论的基本思想“”是利用人工智能启发式搜索函数原型,寻找具有最佳线性逼近关系的函数原型,并结合曲线拟合技术及可视化技术来寻找数据间的规律性。因此,f d d 算法有效地解决了搜索中组合爆炸现象,运用启发式函数引导搜索方向,可以最大限度地减少搜索次数,使系统尽快达到最佳状态。所以,本课题所研究的内容全部是围绕着f d d 算法的研究、改进、优化和实现等工作。在本章将重点介绍f d d 公式发现算法的基本设计思想和基本理论。2 1f d d 12 1 1问题描述给定一组可观察变量x k ,x :,x 。) 以及这组变量的试验数据d l p 。d j :,d m ) ,扛1 , 2 ,3 ,m ,机器发现系统找出该组变量满足的数学关系式:b ,x :,) = c ,其中c 为常数,即对于任意一组试验数据 。,吐:,屯)均满足关系式,p 。d 。,丸) = c 。所找出的关系式州是任何形式的数学公式,包括分段函数。对于关系式厂g 。,x :,) = c 的复杂程度可分为以下几类。( 1 ) 变量的初等运算:f ( x ,y ) = x o y ,其中口为+ ,一,x ,。( 2 ) 变量的初等函数运算厂g ) = c ,其中厂g ) 为初等函数。( 3 ) 初等函数的任意组合b ,j ,) = a l f ( x ) o a :f ( y ) ,其中口为+ ,一,。( 4 ) 复合函数的运算g 驴g ) ) = c ,其中翻,刷均为初等函数等。( 5 ) 复合函数的任意组合: 0 ,g ,( 厂g ) 净:g 。( 厂o ) ) ) ,其中,聃,甜,州均为初等函数等,口为+ ,一,x ,。( 6 ) 多个初等函数的组合:f ( x ,) ,) = 4 。石g ) 国: g ) o a 。 ) ,其中荆,刑均为初等函数,9 为+ ,一,。( 7 ) 分段函数:对于不连接的点,分别用不同的函数加以描述。以上是对两个变量的讨论。在现实生活中存在着多变量的更为复杂的关系,在机器发现过程中采用先寻找两变量的关系,再逐步扩充为多变量的关系的方6首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统法。2 1 2f d d 的设计思想f d d 系统的基本思想是利用人工智能启发式搜索函数原型寻找具有最佳线性逼近关系的函数原型,并结合曲线拟合技术及可视化技术来寻找数据间的规律。( 1 ) 人工智能的启发式方法启发式方法是求解人工智能问题的一个重要方法。一般启发式方法是建立启发式函数,用以引导搜索方向,以便用尽量少的搜索次数,从开始状态达到最终状态。f d d 系统在执行搜索的过程中,对原型函数的搜索以及对他们的组合函数的搜索,也是一种组合爆炸的想象。为解决这一问题,在设计系统时采用了启发式方法来实现。对某一变量取初等函数和另一变量的初等函数或原始数据进行线性组合,即从原型库中选取逼近效果最好的少数几个初等函数作为基函数,并进一步形成组合函数,直至找到最后的目标函数。f d d 系统的启发式函数形式为:f ( x 2 ) = 口+ 奶b 。)线性逼近误差公式为d t = 0 + mx 。) 一厂g :) ) ,g :)我们总是选取d t 最小的,b :) 作为继续搜索的当前结点。这一启发式函数在以后的多次应用中证明是有效的。( 2 ) 数值分析中的曲线拟合在科学实验或统计研究中,人们常常需要从一组测定的数据,例如已知个点x ,y ,) 去求得自变量x 和因变量y 以及一个近似表达式y = 础) 。这就是数据拟合问题。根据数据之闻的关系给出它们之间的数学公式为) ,+ = 口o + 口l 仍g ) + 口2 仍g ) + + 口t 吼g )在曲线拟合中,伊。g ) 一般取工或者是正交多项式。总之,y 的表达式是多项式的形式。其中,r t 0a ,口:,a 。各个系数的确定常用的是最小二乘法q ,即使各点的误差平方和最小。一y + ) 2 = 一0 。+ 口。纯0 ) + 口:鲠+ + 吼纯g ) ) ) 2 = m i n对于如何选择a 。,a 。,口:,使误差平方和最小,可以用数学分析中求极值的方法,即函数妒瓴,q ,口2 ,吼) x c a 。,a ,a 2 ,一,啦求偏微商,再使偏微商等于零,得到,a 1 ,口2 ,吼应满足的方程“”。f d d 系统中吼g ) 是取各种初等函数或者是它们的组合,或者是复合函数。用启发式搜索找到所需要的基函数,然后利用曲线拟合方法求得其系数,从而得首都师范大学硕士论文一种基于教据挖掘和公式发现的智能教具系统到经验公式。2 1 3f d d 系统的结构( 1 ) 总体结构图f d d 算法的总体结构如图2 1 所示。图2 1f d d 算法的总体结构( 2 ) 各模块说明试验数据输入( i n p u td a t a )提示用户输入试验数据。数据生成器( g e n e r a t o r )此模块用于测试系统效果。给定一个已知公式后,它能生成一批数据,f d d系统的核心程序将利用这些模块来找出给定的公式,从而达到测试系统的公式发现能力的效果。此模块是一个可独立执行模块。数据库( d a t a b a s e )数据库存放待处理的变量数据,一般是科学和工程试验数据库。公式的j 下确与否与数据的规律性和充分性密切相关。系统本身可提供直接输入的功能,用户可在系统的提示下将数据输入。也可用数据生成器为系统提供数据,系统将其按一定的格式存储起来,存放在数据库中。数据库中有一个缓冲区,供系统运行时存放中间变量以及实现数据的移动和变化。可视化过程8首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统此模块又分成3 个子模块。a 描绘试验数据的变化趋势b 描绘出原型算法库中各函数原型的变化趋势。此子模块具有很大的灵活性,用户可根据需要随意调用所选择原型以描绘其变化趋势。c 描绘所发现的公式的变化规律与原始数据之间误差分布状况。公式发现控制模块此模块是f d d 的核心部分,它主要是利用知识库中的知识,优选函数原型、控制继续发现和修正公式等。它包括:初始处理、优选公式、继续发现和公式修正4 个子模块。下面便是对这4 个子模块的功能说明。a 初始处理此模块的主要功能有两个方面,其一是根据具体情况对用户所提供的数据进行初步处理;其二是在多变量中选择两个变量及向多变量的过渡处理。b 优选公式其主要功能是对公式库中提供的公式根据其误差逼近情况来优选原型函数,对原型函数一般选择2 3 个。c 继续发现此模块将根据误差分析情况,建立新变量,颠倒变量关系,对所选择的原型函数进行组合。d 公式修正这是在输出公式之前所必经的一个过程,此过程将根据用户提供的误差要求决定是否对系统所发现的公式进行修正。选择原型此过程通过调用原型算法库、可视化过程、及误差分析模块提供的误差来进行函数原型的选择。有两种选择方式:a 由用户指定选择。b 通过循环控制进行顺序选择。公式生成此模块主要应用数值分析中的曲线拟合技术求得拟合公式的系数同时生成公式。误差分析模块此模块的主要功能是对“公式生成”模块提供的公式计算相对误差及对误差进行比较。循环控制模块。此模块设有一个控制开关,对“选择原型”和“公式发现控制”两个过程进行循环运行。公式输出和可视化显示此过程是系统所要执行的最后一步,当“公式发现控制”模块决定最终输出9首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教县系统公式后,执行此模块,输出公式并进行可视化显示。这样用户可很直观地阅读公式,了解所发现的公式逼近实验数据的情况。原型算法库原型是构成数学公式的基本单元,原型算法库所包括的原型决定了系统的发现能力。本系统的原型函数由基本原型和组合原型构成。基本原型由初等函数组成如:x ,工2 ,x 3 ) x - ix - 2s q r t ( x l x i 3 ,j o g g l e x p g ls i n g l c o s g ) 等。组合原型由初等函数的初等运算组合而成,如:xs i n g ) x c o s g l x e x p g lx l o g ( x ) , x 。l o g ( x ) , x 。e x p g l l l o g g x l s g g l s i n g ) + c o s g ) 等。在原型算法库中,每个原型都给出了一个算法,只不过每个算法的程序结构都非常相似。用户还可以根据需要随意增加、删除原型算法,在程序运行过程中,我们给出了一个控制参数,用户可通过它来调用所需算法。知识库知识库中知识用于构造和发现关系式。公式库公式库用来存放在搜索过程中初步选择的原型函数组成的公式,以备公式发现控制模块使用。公式库中的公式包含两个变量取某原型函数的线性组合以及该公式的逼近误差。在搜索过程中,每当发现一个比较可行的公式或原型函数,便将其送入公式库等待下一步的选择,每一轮选择之后便把落选的公式剔除出公式库,直至发现满意的公式为止。2 1 4f d d 系统中的知识在f d d 系统中,知识采用的是产生式规则的表示形式( i f t h e n ) 。主要的基本规则有:规则1 发现常数当某一变量x 取一个常数,则建立该变量等于常数的公式,即工= c规则2 两变量的初等运算组合当两变量进行初等运算若等于常数,则建立该变量的初等运算关系式,即a t x l 胁2 石22c其中,口可为+ ,一,x 。规则3 变量取初等函数当某变量取初等函数等于常数,则建立该变量的初等函数关系式,即f ( x ) = c ,1 0首都师范大荦硕士论文一种基于数据挖掘和公式发现的智能教具系统其中,厂g ) 为初等函数。规则4 两变量取初等函数的线性组合两变量分别取初等函数后的线性组合等于常数,则建立两变量取初等函数的线性组合关系式,即口l z g 。) + 口:五g :) = c其中六g ,) ,五g :) 为初等函数。规则5 某变量取某一初等函数与另一变量的线性组合对某一变量x 。取初等函数后与另一变i x ,进行线性组合,若为常数,则建立关系式,即e l f ( x , ) + c 2 x 1 = c规则6 对某一变量x ,取初等函数,另一变量x ,取两个x ,的初等函数进行线性组合,若为常数,则建立关系式,即c 。z g ,) + c :厶g ) + 白g b ,) = c规则7 建立新变量( 启发式1 )若两变量的某初等运算接近常数,则建立新变量为该两变量的某种初等运算。规则8 建立某变量的某种初等函数为新变量( 启发式2 )若某变量的某种初等函数与另一变量或它的初等函数进行线性组合接近常数,则建立该变量的初等函数为新变量。以上规则的嵌套或递归使用,将形成变量的任意函数间的任意组合。在应用规则时,利用可视化技术将减少各种函数和各种运算的选取,大大节省了搜索时间。2 1 5f d d 1 系统实例行星运动开普勒第三定律的重新发现,原始数据如表2 1 所示。l 距离d1491 62 53 64 96 48 11 0 0l 周期p182 76 41 2 52 1 63 4 35 1 27 2 91 0 0 0利用f d d 算法对数据进行公式发现的操作,其搜索树如图2 2 所示。首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统q 锺夕邸) ,l p ) l ( d ,l o g ( p ) )( d ,s q r t ( p ) )( s q r t ( d ) ,p ) )( 1 吨( d ) ,p )( 1 d l o g ( d ) ,p )( 1 0 酎d ) ,l o 甙p ) )( 1 0 9 ( d ) ,l o g ( p ) )d t - - o 0 0 0 1d t - = o 0 0 0 2图2 2 开普勒第三定律发现的搜索树由图2 2 所示的搜索树以及最小二乘法拟合计算可以得到公式发现结果( 其中系数0 6 6 6 6 6 6 6 6 7 是利用数据拟合算法计算得到的) :l o g ( d ) = 0 6 6 6 6 6 6 6 6 7 l o g ( p ) d t = o 0 0 0 1其化简公式为:d 3 = p 2上例中,公式发现的结果误差满足要求,公式发现比较成功。由人工选择的函数原型或推理机自动选择函数原型组合成数学关系式,利用最d - - 乘法原理求组合关系式的各个系数,由可视化过程显示变化趋势,根据数学关系式的逼近效果,由人决定重新构造关系式还是进行自动推理深入构造数学关系式,并进行误差分析,在搜索过程中,每当发现一个比较可行的公式或函数原型,便将其送入公式库等待下一步的选择,每一轮选择之后便把落选的公式剔除出公式库,直至发现满意的公式为止。其基本步骤为:步骤l :固定变量x :,对而进行学习,即在现有原型基础上,依次对实验数据进行匹配。用最小二乘法求出a , b 系数,若某一原型经过线性组合后与试验数据的相对误差小于一给定值,则学习成功,否则转步骤2 ;步骤2 :固定在步骤1 求出的相对误差最小的原型f l ( x , ) ,对膏,进行学习,方法同步骤l ,若误差仍不满足要求,则在固定本步骤中得到的相对误差最小的原型f 2 ( x :) ,对f l ( x 。) 进行学习。重复步骤1 和步骤2 ,直到求出满足要求的经验公式为止。1 2首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统2 2f d d 2f d d 2 对f d d 1 做了改进,即每次运算后选择误差最小的和误差有减小趋势的原型进入下一次迭代。这样,就改进了在f d d 1 中不能保证上一次最好的公式能进入下一次迭代的缺点。另外,f d d 2 在f d d 1 的基础上除了使用f d d 1的函数运算规则,还增加了导数运算规则。即在一次循环中有两个方面的内容,一个是函数作用于变量生成公式;另外一个是数据通过导数规则处理后,应用函数作用于变量生成公式。如图2 3 所示。图2 3f d d 2 公式生成算法的搜索树引入导数规则后,生成的公式类似于y = ,( x ) ,经处理得:y = p g 矽g ) + c再利用最d x - - 乘法求出c 。2 3f d d 3应用f d d 2 发现算法确定两个参数的变化规律后,对其进行扩展,确定三维以上函数之间得关系就形成f d d 3 算法。2 4 本章小结本章主要介绍了f d d 公式发现算法的设计思想以及基本理论,阐述了f d d算法中的启发式规则、曲线拟合技术的运用、以及f d d 算法总体结构。首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统第三章对f d d 算法的改进和优化f d d 公式发现算法的设计思想和基本理论已经成为公式发现领域中被研究者广为接受的、有较重要影响力的准则,并且,围绕着f d d 理论基本思想,已有一些公式发现系统被应用到很多行业之中,如:深度优先的公式发现算法o “、基于遗传建模的公式发现研究”“、基于算子空间的公式发现算法研究”等。但是,在对f d d 公式发现算法进行研究的过程中,我们发现,f d d 公式发现算法在误差准则、函数库扩展等方面存在一些问题,在实际应用中,这些问题会影响利用f d d 算法进行公式发现时的搜索效果。为逐步完善f d d 算法,我们开始探索改进和优化f d d 算法的新方法。3 1 误差d t 的计算f d d 公式发现系统在某一层对变量x 、y 进行学习时,通常需要固定某一变量,对另一变量进行学习。例如:如果是对变量y 进行学习,则需要固定x ,对变量y 依次进行原型函数的匹配厂( ) ,) ,再利用最小二乘法拟合计算出f ( y ) = a + k 的系数a 、b ,这时就需要计算f ( y ) 与d + h 之间的误差西,以确定厂( y ) 是否为本层所确定的搜索方向。关于误差西的计算方法,按照上一章f d d理论的介绍,针对变量x 、,( _ ) ,) ,其计算公式应为:d t = 【d + b x 一厂( y ) 】( y )( 3 1 )由式3 1 可以看出,也是一个相对误差,即误差率,误差率表示它们之间相差的比利关系。另外,从式3 1 来看,出的计算结果可能是正数也可能是负数,这取决于a + b x 一厂( 力的符号与f ( y ) 的符号,这样,如果比较廖的大小,就有可能出现部分函数在对变量学习之后,计算出的误差率是负数,所以被选中作为下一步的搜索方向,然而此函数并不一定是最佳的结果。如:现有两个数字3 和8 ,要求从这两个数字中找出一个与数字7 比较接近的。按照式3 1 的计算规则,1数字3 与数字7 的误差率为一三,而数字8 与数字7 的误差率为去,如果单纯比t|较两个误差率的大小则会选中数字3 ,然而,实际上数字8 与7 才是比较接近的,只是由于它的误差率为正数,所以未被选中。由此可以看出,通过式3 1 计算出的误差率是没有绝对可比性的,解决的办法是式3 1 的计算公式中引入绝对值符号,其形式如下:d t 刊【口+ b x 一厂( y ) 】( y ) i( 3 2 )另外,在f d d 公式发现算法中所学习的变量应该是一组实验数据,也就是说变量x 、y 存在一组具体的数值。依据式3 2 计算出的误差率出应该是在某一1 4首都师范大学硕士论文一种基于数据挖掘和公式发现的智能教具系统个数据点上的误差率,而f d d 算法在对变量学习过程中所求出的误差率应是所有实验数据总体的误差率,因此,应该继续扩展式3 2 ,使其反映所有实验数据总体的误差率。在算法中,如果定义衍为数据中所有点的误差率之和,显然不合理,因为我们输入的数据个数不同,求和没有可比性。因此,在本算法中,席的精确定义是平均误差率,即所有实验数据点上误差率的平均值,其计算公式如下:d t = ( i a + b x ,- f ( y ,) 】,( y 刊) ,栉( n 为实验数据的个数)( 3 3 )i = 1如式3 3 所示,西的最终求解过程是把各个点上的误差率求和后计算平均值,即为平均误差率。下面通过实例来介绍求解平均误差率出的方法。例:已知一组数据的两个变量在某次学习中的取值如表3 1 所示,求这两个变量之间的平均误差率出。,( 茗:,)2468口+ 坛( 而,)2 43 86 38 2计算过程:d t l = l 口+ b g ( x 1 1 ) 一f ( x 2 1 ) l f ( x 2 1 ) l = 0 2d t 2 = | 【口+ b g ( x 1 2 ) 一f ( x 2 2 ) 】,( x 2 2 ) i = o 0 5d r 3 = l 口+ b g ( x 1 3 ) 一f ( x 2 3 ) 】( 】嘧) i = o 0 5d t 4 = | 【口+ b g ( 工1 4 ) 一f ( x 2 4 ) 】,( x 2 4 )

温馨提示

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

评论

0/150

提交评论