（教育技术学专业论文）一种基于gep的函数挖掘方法研究与应用.pdf

天津师范人学硕+ 学位论文 摘要 数据挖掘是从大量的数据信息中提取出隐含的知识、规律和行为模式的处理 过程，函数挖掘是从科学数据中发现有效的函数关系，它是数据挖掘技术研究的 重要方向。 本文对利用基因表达式编程( g e p + ) 技术在传统g e p 的基础上对函数关系 的挖掘进行了较深入的研究。首先介绍了数据挖掘的概念、功能和函数挖掘的概 念与步骤、基因表达式编程基本概念和国内外研究现状。针对传统g e p 挖掘方 法难以解决早熟和收敛速度较慢的问题，在基于支持度适应度函数的基础上，引 入了精度阈值队列，该方法有效的提高了挖掘的成功率，一定程度上解决了早熟 和收敛速度较慢的矛盾，同时对函数关系发现这一特殊知识发现形式的特点进行 了分析，在一致函数表达式挖掘方法u e m 的基础上，提出p t q u e m 算法 ( p r e c i s i o nt h r e s h o l dq u e u eu n i f o r me x p r e s s i o nm i n i n g ) ，并且进一步分析研究了二 域函数表达式挖掘方法b d m 。本文设计并在v c + + 的环境下实现了基于g e p p t q 的实验平台g e p p t q ，多种合成数据和真实标准数据对比实验证明，g e p p t q ， 挖掘成功率高，效果良好。 作为一种通用的函数发现技术，新方法除可应用于数据挖掘、符号回归、机 器学习等领域，更可以直接推广应用于教育教学相关数据的函数发现领域，可以 利用计算机自动寻找到能良好描述相关数据的有效数学模型。 关键词：函数挖掘；基因表达式；符号回归；精度阈值队列 天津师范人学硕十学位论文 a b s t r a c t d a t am i n i n gi sap r o c e s st h a td i s c o v e r sk n o w l e d g ef r o mm a s sd a t aa n d i n f o r m a t i o n i tp l a y sa ni m p o r t a n tr o l ei nd e c i s i o nm a k i n ga n da c t i o n sa sg u i d a n c e f u n c t i o nm i n i n gi sa ni m p o r t a n tr e s e a r c hd i r e c t i o no fd a t am i n i n gt od i s c o v e r f u n c t i o n sh i d d e ni ns c i e n t i f i ed a t a b a s e s t i l i sa r t i c l er e s e a r c h e do nt h ed a t am i n i n gf u r t h e rw h i c hi sb a s e do nt h e f o u n d a t i o no ft h et r a d i t i o n a lg e pu s i n gt h eg e n ee x p r e s s i o np r o g r a m m i n g ( g e p ) f i r s t ，i n t r o d u c i n gt h eb a s i cc o n c e p t 、g e n e t i cp r o c e d u r e 、f u n c t i o n 、s t e po ff u n c t i o n m i n i n go fd a t am i n i n g ，a n di n t r o d u c i n gt h ep r e c i s i o nt h r e s h o l dq u e u e ，a i m e da t s o l v i n gt h ec o n t r d u c t i o n b e t w e e np r e c o c i o u sa n dt h e c o n v e r g e n c er a t es l o w p r o p o s i n gf u n c t i o nm i n i n ga l g o r i t h mb a s e do np r e c i s i o nt h r e s h o l dq u e u e ，t h i s m e t h o dh a se n h a n c e dm i n i n gs u c c e s sr a t i oe f f e c t i v e l y , a n dh a sr e s o l v e dt h e c o n t r a d i c t i o nb e t w e e np r e c o c i o u sa n dt h ec o n v e r g e n c er a t es l o w e ri nt h ec e r t a i n e x t e n t a tt h es a m et i m e ，a n a l y z i n gc h a r a c t e r i s t i co ff u n c t i o n a lr e l a t i o n sw h i c hi sa s p e c i a lk n o w l e d g e ，p r o p o s i n gp t q u e m ( p r e c i s i o n t h r e s h o l dq u e u eu n i f o r m e x p r e s s i o nm i n i n g ) a l g o r i t h m o nt h eb a s e o fu e m ( u n i f o r m e x p r e s s i o n m i n i n g ) m i n i n gm e t h o d ，a n da n a l y z i n gt h em i n i n gm e t h o do fb d m t h i sa r t i c l eh a s d e s i g n e da n dc a r r i e do u te x p e r i m e n tp l a t f o r mb a s e do ng e p p t qa tt h ee n v i r o n m e n t o fv c 抖t h ec o n s t r a s te x p r i m e n tb e t w e e nm u l t i s y n t h e s i z ed a t aa n dt r u es t a n d a r d d a t ap r o v et h a tg e p p t qh a sh i g h e rs u c c e s sa n de f f e c ti sb e t t e r a sau n i v e r s a lt e c h n i q u eo ff a c t i o nm i n i n g ，n e wm e t h o dc a ng e n e r a l i z ea n d a p p l y t oe d u c a t i o na n df i e l do fr e l a t i v ed a t ao i lf u n c t i o nm i n i n g , e x c e p td a t am i n i n g 、 s y m b o lr e g r e s s 、m a c h i n el e a r n a l s o ，t h i sm e t h o dc a n u s ec o m p u t e rt oa u t o m a t i cl o o k f o rb e t t e re x p r e s s i o no fr e l a t i v ed a t a se f f e c t i v em a t h e m a t i c sm o d e l k e yw o r d s ： f u n c i t o nm i n i n g ，g e n ee x p r e s s i o np r o g r a m m i n 吕s y m b o lr e g r e s s ， p r e c i s i o nt h r e s h o l dq u e u e n 独创性声明 本人卢明所交的论文是我个人在导师指导卜进行的研究1 ：作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得墨注! 至整盘堂或其它教育机构的学位或证书而使用过的 材料。与我一同j i ：作的同j 占对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 签名： 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论 文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、 汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： 天津师范人学硕十学位论文 1 1 论文选题及其研究意义 第一章绪论 当前科学技术正进入多学科交叉，互相渗透、互相影响的时代，人们在科学 的各个领域不断的观察积累数据，在被称为“信息时代 的今天，各种数据量呈 指数级增长。历来自然科学的基本研究方法一般表现为“观察积累数据分析数 据理论概括用于指导实践 。面对如此的海量数据，现在人们不再满足于对数 据的应用只是查询和检索，而是希望能够在数据中发现相关事物的内在联系和规 律，以便更好的利用海量数据。 那么如何在海量数据中发现数据的关系，去伪存真，更好的利用数据、知识 呢? 研究者们利用挖掘的方法。数据挖掘技术是人类分析问题和发现知识能力的 延伸。它经过十多年的发展，己经逐渐建立起系统的挖掘理论和成熟的挖掘技术， 成为一门以关联规则挖掘、分类规则挖掘、聚类规则挖掘为主要形式，以数据库 技术、统计学、人工智能、可视化技术和信息技术为主要工具的多学科交叉的应 用技术。 函数关系挖掘是数据挖掘的重要研究方向。函数挖掘作为数据挖掘的一种形 式，是一个即古老又年轻的领域，一直吸引了无数研究者的目光。在计算机发明 之前，这种探索自然规律的精确描述工作通常由人来完成。事物间函数关系的挖 掘是依靠人们对大量数据进行不断的计算和摸索，再加上一些突发的灵感而得到 的。而这种函数关系的挖掘是及其艰苦和困难的事情。 进入2 0 世纪中后期，随着计算机技术的不断发展，计算机技术被不断运用 到了各个领域，极大地推动了各个领域的发展。在函数发现领域，在用计算机实 现了以往的方法的同时，由于生物技术的发展，仿生计算开始被运用到函数发现 领域，并取得了巨大的成功。神经网络，遗传算法等新方法的提出，为函数发现 提供了一系列行之有效的方法。 基因表达式编程( g e n ee x p r e s s i o np r o g r a m m i n g ，g e p ) 是c f e r r e i r a 发明的一 种新的遗传算法。基因表达式编程结合了遗传算法和遗传程序设计的优点，克服 了它们的缺点，在数学建模方面取得了非常好的效果。正因为其优点和良好的效 天津师范人学硕十学位论文 果，使得基因表达式编程在并不漫长的时间里引起了演化计算领域的广泛关注甚 至争议。 1 2 本文主要工作 本文以基因表达式编程为主要研究对象，进一步探索了利用基因表达式编程 技术进行函数关系挖掘的研究，并尝试在单精度阈值的基础上引入精度阈值队 列，实验证明取得很好的效果。 本文组织如下： 第一章本章介绍了论文研究的意义及本文的主要工作。 第二章本章阐述了数据挖掘的概念、功能和函数挖掘的概念与步骤，介 绍了基因表达式编程基本概念和国内外研究现状。 第三章本章在基于支持度的适应度函数的基础上引入了精度阈值队列，提 出了基于精度阈值队列的函数挖掘算法g e p p t q ，同时对函数关系发现这一特殊 知识发现形式的特点进行了分析，在一致函数表达式挖掘方法u e m 的基础上， 提出p t q u e m 算法，并且进一步分析研究了二域函数表达式挖掘方法b d m 。 第四章本章设计并实现了g e p p t q 实验平台，包括数据预处理、函数单次 挖掘和多次挖掘，以及进化动力特性模块。 第五章本章进行各种对比实验，对g e p p t q 在不同的输入参数情况下的性 能做了对比和评价，显示了g e p p t q 的实际效果；并且该方法可以在教育教学 中推广。 第六章本章对全文工作进行总结，对未来的工作进行展望。 本论文研究的重点是引入精度阈值队列，在传统g e p 的基础上，实现函数挖掘。 2 天津师范人学硕十学位论文 第二章知识发现简介 需要是发明之母。 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数 据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。通过数 据挖掘，有价值的知识、规则或高层次的信息就能从数据库中抽取出来，从而使 大型数据库作为一个丰富、可靠的资源为知识的提取服务。 2 1 数据挖掘 数据挖掘是信息技术发展的产物。从最初的数据收集和数据库创建到数据 管理( 包括数据存储、提取和数据库事务处理) ，再到当前的数据分析与理解( 涉 及数据仓库和数据挖掘【1 】【2 】) 。随着提供查询和事务处理的大量数据库系统广泛付 诸应用，数据分析和理解自然成为下一个目标。在过去的数十年中，随着科学技 术发展，产生和收集了大量的数据。数据库系统尤其是关系数据库系统的成功建 立，使我们能够高效地处理这些海量数据。然而，数据增长的速度远远超过了( 传 统的) 数据处理分析能力增长的速度，这一现象被描述为“数据丰富，信息贫乏 。 决策者缺乏从海量数据中提取有价值知识的工具，导致了重要的决策常常不是基 于蕴含在丰富数据中的知识，而是基于决策者的直观。决策支持系统的用户呼唤 强有力的海量数据分析工具，希望计算机能帮助分析数据，发掘数据中隐含的关 系。数据挖掘应运而生! 数据挖掘旨在对这些数据进行分析，发现重要的数据模 式，数据挖掘将数据“金砂转换成知识“金块，辅助人们认识世界、改造世 界。 2 1 1 数据挖掘的内涵 简单地说，数据挖掘是从大量数据中提取或“挖掘 知识，是发掘隐藏在数 据中的信息，如趋势、特征及相关性的过程，即从数据中挖掘知识。事实上，数 据挖掘应当更正确地命名为“从数据中挖掘知识 。许多人把数据挖掘视为另一 个常用的术语“数据库中知识发现”或k d d 3 1 的同义词。而另一些人只是把数 天津师范人学硕十学位论文 据挖掘视为数据库中知识发现过程的个基本步骤。 我们同意数据挖掘是知识发现过程的一个步骤。然而，在工业界、媒体和数 据库研究界，“数据挖掘”比比较长的术语“数据库中知识发现更流行。因此 在本文中，我们选用术语数据挖掘。我们采用数据挖掘的广义观点：数据挖掘【4 】 是从存放在数据库、数据仓库或其它信息库的大量数据中挖掘有趣知识的过程。 基于这种观点，典型的数据挖掘系统具有以下主要成分如图2 1 所示。 图2 1典型的数据挖掘系统结构 从数据仓库观点嘲，数据挖掘可以看作联机分析处理( o l a p n ) 的高级阶 段。然而，通过结合更高级的数据理解技术，数据挖掘比数据仓库的汇总型分析 处理走得更远。 数据挖掘涉及多学科技术的集成，包括数据库技术、统计、机器学习、高性 能计算、模式识别、神经网络、数据可视化、信息提取、图象与信号处理和空间 数据分析。通过数据挖掘，可以从数据库提取有趣的知识、规律或高层信息，并 可以从不同角度观察或浏览。发现的知识可以用于决策、过程控制、信息管理、 查询处理等等。因此，数据挖掘被信息产业界认为是数据库系统最重要的前沿之 一，是信息产业最有前途的交叉学科。 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、 数据仓库、事务数据库、先进的数据库系统、展平的文件和w w w 。先进的数据 库系统包括面向对象和对象关系数据库；面向特殊应用的数据库，如空间数据 库、时间序列数据库、文本数据库和多媒体数据库。挖掘的挑战和技术可能因存 4 天津师范大学硕士学位论文 储系统而异。 2 1 2 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。一般地，数据挖掘 任务可以分两类：描述和预测。描述性挖掘任务刻划数据库中数掘的一般特性。 预测性挖掘任务在当前数据上进行推断，以进行预测。 概念类描述：特征和区分 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和 概念可能是有用的。这种类或概念的描述称为类概念描述【1 1 。这种描述可以通过 下述方法得到：数据特征化( d a t ac h a r a c t e r i z a t i o n ) ，数据区分，数据特征化和比较。 数据特征化是目标类数据的一般特征或特性的汇总。数据区分是将目标类对象的 一般特性与一个或多个对比类对象的一般特性比较。目标类和对比类由用户指 定，而对应的数据通过数据库查询提取。 关联分析 关联分析发现关联规则7 1 ，这些规则展示属性值频繁地在给定数据集中一起 出现的条件。关联分析广泛用于购物篮或事务数据分析。关联规则是形如“a ， 八八a 小j b j 八a b 月( s u p t , c o n f ) 的规则；其中a , ( i e l ，m ) ) ，剐 l ，丑) ) 是关于属性的谓词。规则解释为“满足a ，八八的数据库元组满足b ，八八 & 的支持度为s u p t ，置信度为c o n f 。近年来，已经提出了许多有效的关联规则 挖掘算法。 分类 分类是这样的过程，它找描述或识别数据类或概念的模型( 或函数) ，以便能 够使用模型预测类标号未知的对象。导出模型是基于对训练数据集( 即其类标号 已知的数据对象) 的分析。导出模式可以用多种形式表示，如分类( i f t h e n ) 规则、判定树、数学公式或神经网络。判定树是一个类似于流程图的结构，每个 结点代表一个属性值上的测试，每个分支代表测试的一个输出，树叶代表类或类 分布。 时间序列预测 5 天津师范人学硕十学位论文 时间序列预测【8 1 根据数据随时间变化的趋势预测将来的值。它通过对数据进 行汇总和分析找出时间序列观测值中的规律与变化趋势，然后通过这些规律和趋 势的外推来确定未来的预测值。 聚类分析 聚类分析数据对象，而不考虑已知的类标号。一般地，训练数据中不提供类 标号，因为不知道从何开始。聚类可以产生这种标号。对象根据最大化类内的相 似性、最小化类间的相似性的原则进行聚类或分组。即对象的聚类这样形成，使 得在一个聚类中的对象具有很高的相似性，而与其它聚类中的对象很不相似。所 形成的每个聚类可以看作一个对象类，由它可以导出规则。聚类也便于分类编制， 将观察组织成类分层结构，类似的事件组织在一起。 局外者分析 数据库中可能包含些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是局外者。大部分数据挖掘方法将局外者视为噪音或例外而丢弃。然 而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正规出现的那些更有趣。 局外者数据分析称作局外者挖掘。 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管 这可能包括时间相关数据的特征、区分、关联、分类或聚类，这类分析的不同特 点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 2 2 函数挖掘 函数挖掘是数据挖掘的重要分支，它的目的是发现描述数据或趋势的函数， 以便能够使用函数模型进行预测。科研和工程中不仅需要对大量的数据定性分 析，而且需要对它们进行定量分析，这些常常会用到函数挖掘。这类问题是根据 得到的若干有关变量的一组数据，寻找因变量与自变量之间的一个函数，使该函 数对那组数据拟合得最好。 函数挖掘通常包括下列步骤【1 0 】： ( 1 ) 拟合从一组数据出发确定某些变量之间的定量关系式，即建立函数模型 并估计其中的未知参数； 6 天津师范大学硕士学位论文 ( 2 ) 变量选择判断哪些自变量的影响是显著的，哪些自变量的影响是不显著 的，将影响显著的自变量选入模型中，而剔除影响不显著的变量； ( 3 ) 估计与检验估计函数模型中的未知参数，并且对模型提出的各种假设进 行验证； ( 4 ) 预测利用所求的函数对一组输入数值进行预测； 目标函数可以用回归分析统计技术建模。许多问题可以用线性回归解决，并 且更多的可以对变量进行变换，使得非线性问题可以转换为线性的来加以处理。 2 2 - 1 一元线性回归和多元线性回归 简言之，线性回归【9 】用直线对数据建模。线性回归是最简单的回归形式。双 变量回归是将一个随机变量y 视为另一个变量x 的随机函数。即： y - q + 1 3x 。其中，q 和1 3 是回归系数，分别表示直线在y 轴的截断和直线的斜 率。这些系数可以用最小二乘法求解，这使得实际数据与该直线的估计之间误差 最小。 多元回归是线性回归的扩展，涉及多个自变量。因变量y 可以是一个多维 特征向量的线性函数。多元回归模型的一个例子是y = a + 1 3 ，x r 1 32 x 2 ，最d x - 乘法依然可以用在这里求解q ，1 3j 和b2 。 2 2 2 非线性回归 用非线性函数( 曲线，曲面或超曲面) 建模。通过在基本线性模型上添加多 项式，多项式回归可以用于对不呈现线性依赖的数据建模。通过对变量进行变换， 可以将非线性模型转换成线性的。 2 3 基因表达式编程g e p 2 3 1 基因表达式编程概述 基因表达式编程可以说是遗传算法和遗传程序设计【1 2 , 1 3 , 1 4 发展道路上的一个 不可避免的产物。f e r r e i r a 本人在他的第一本关于基因表达式编程的书里面也提 7 天津师范大学硕士学位论文 到，他是在学习遗传算法和遗传程序设计的过程中开发出基因表达式编程系统 的。f e r r e i r a 在他的书中从进化化学和生物化学的角度详细论述了基因表达式编 程比遗传算法和遗传程序设计更优越的理论基础。基因表达式编程的沿革【1 5 , 1 6 1 阐述了如下的观点如图2 2 所示。 “遗传算法比喻为父体，它刚性地使用定长的线性字符串作为遗传物质，采 用简单编码解决简单问题；遗传程序设计比喻为母体，它柔性地使用非线性的， 不定长的树结构，采用复杂结构解决复杂问题；而基因表达式编程继承了父母的 优点，它刚柔相济，表现为定长线性串，易于遗传操作，又间接地对应于柔性的 具有非线性结构的树结构，从而达到了简单编码解决复杂问题的目的，使得在速 度上比g a 和g p 提高了1 0 0 _ - 6 0 0 0 0 倒1 。丌。 文献1 1 8 1 用“沃土老树开新花” 来描述g e p ，即在“知识发现”这块沃土里，“遗传计算家族”这棵老树上开出 了“基因表达式编程 这朵新花。 图2 2g e p 与g p 、g a 的继承关系 基因表达式编程和遗传编程一样，是在遗传算法的基础上发展起来的。它和 遗传编程一样，采用了一种全新的不同于遗传算法的个体描述方法，其实质是用 广义的层次化计算机程序描绘问题。对这种广义的层次化计算机程序作形式化描 述，需要两类符号，即终结符和函数，它们是构造基因表达式编程中的一个程序 的元语。 终结符是提供给系统值的最末端结构。终结符自己提供信息，但不处理另外 的信息。通常终结符集合包括基因表达式编程程序中的输入、常量或者没有参数 的函数。如果用树形结构来表示程序，终结符代表树的这些叶节点。当程序运行 天津师范人学硕十学位论文 的时候，这些叶节点，要么接受外部的输入，要么自己就是一个常量，或者自己 能计算产生一个量。它们向系统提供信息，以供系统处理。 g e p 的基因由一头( h e a d ) - - 尾( t a n ) 两部分构成。头部由包含既代表函数又代 表终点的符号构成，而尾部仅仅含有终点。对每个问题而言，头的长度h 是选定 的，而尾的长度t 是h 和n 的函数，头部可以出现运算符和变量，而尾部只能出 现变量。其中n 是所需变量数最多的函数的参数个数( 也称为最大操作数) ，t 的 大小由( 2 1 ) 式的方程得到。 t = - h ( n - 1 ) + 1 ( 2 1 ) 采用这种头尾划分的好处在于，一方面整个基因的结构在设定字符集和头部 长度之后就能够确定，另一方面，整个基因在上面这个公式的前提下一定能够保 证结构上的正确性，而不用担心会产生任何非法的个体。 考虑如下这个由函数集为f = q ，奉 ，一，+ ) 和终点集为t 三 咖) 构成的基因。在 这里，n = 2 如果我们选择h = 1 5 ，那么t = - 1 5 ( 2 - l 卜1 = 1 6 1 所以基因g 的长度为 1 5 + 1 6 = 3 l 。 下面给出一个这样的基因如( 2 2 ) 式所示( 尾部用粗体标识) 。 0l2 3 4 5 6 7 8 9 0l2 3 4 5 6 7 8 9 0l2 3 4 5 6 7 8 9 0 车b + a - a q a b + + b + b a b b a b b b a b a b b a a a ( 2 2 ) 它编码成如图2 3 表达式树。 图2 3 e x p r e s s i o nt r c e 需要注意的是，o r f ( o p e nr e a d i n gf r a m e ) 【1 9 】终止于第7 位，但是基因终 止于第3 0 位。也就是说，整个基因中有一部分被编码到了树结构中，而另一部 分则没有在这种树结构出现。这里出现的部分叫做公开阅读框( o p e nr e a d i n g 9 天沣师范人学硕士学位论文 f r a m e ，o r f ) ，它是g e p 的表现型。而基因中没有出现的部分被称为非编码区 域。这些非编码区域的存在为程序进化提供了很大的空间。 g e p 染色体( c h r o m o s o m e ) 通常由等长的多个基因构成。对于每个程序或者 每次运行，基因的数目以及头部的长度都是选定的。每一个基因可以编码成一个 子表达式树( s u be t ) 而且子表达式树相互作用构成一个更复杂的多子树 ( m u l t is u b u n i t ) 的表达式树，子表达式树可以根据问题的具体情况采用一般的四 则运算符，或者用逻辑运算符来连接。其中，每个子表达式树既是一个独立的实 体，也是一个复杂的等级结构系统的一部分。 g e p 与其他演化算法【2 7 1 比较，它们在以下几个方面有着显著的区别： ( 1 ) 个体的表示 在g a 中，通常将个体表示为具有固定长度的线性数串；在g p 中，各个体 表现为具有不同尺寸和形式的非线性的对象( 比如呈树状) ；而g e p 中的个体被编 码为具有固定长度的但实际上可以表示不同规模个体的线性符号串。 ( 2 ) 个体的处理 由于g a 采用定长线性串，为遗传操作( 尤其是交叉) 处理提供了便利，同时 其处理问题的规模也是固定的；g p 由于个体形状尺寸不定，遗传操作时对个体 的处理方法也比较复杂；g e p 采用了固定长度的线性的符号串，遗传操作时具 有和g a 一样的便利。 ( 3 ) 结果的形式 g a 与g e p 对个体编码方式的不同决定了它们解的不同。g e p 得到的结果 在规模和形式上更具多样性。例如，我们可以用g a 去寻找适当的参数a 、b 、c 、 d ，以使得函数) ，= a x 3 + b x 2 + c x + d 能够尽量接近实验数据所满足的函数关系；而利 用g e p ，我们可能会得出形如s i n ( a x 2 + b x ) + c 的预想不到的结果，而这样的结果 也许更能反应各个量之间的真实函数关系。 对于我们所要研究的函数关系发现而言，我们所知的条件只有输入的样本数 据，而没有关于目标函数的形式的先验知识。因此我们选择了能够表示不同规模 和形式的个体的g e p 方法作为我们的搜索算法的基础。g e p 编码线性且定长的 特性对于遗传操作中降低计算复杂度也有很大的帮助。 1 0 天滓师范人学硕+ 学位论文 2 3 2 国内g e p 研究现状 目前，g e p 国内新成果也不断出现，四川人学在2 0 0 0 年底开始了对g e p 的跟踪性研究， 唐常杰教授 i s 2 睨6 1 己将该技术用丁公式发现、函数挖掘、关联规则挖掘、因子分解和太阿 黑 子预测，取得了满意的效果。2 0 0 4 年，汗锐i z8 j 等人利用g e p 方法实现了多项式函数分解， 提出了基于g e p 的多项式函数分解方法( g e pp o l y n o m i a lf a c t o r i z a t i o n ) 。该算法能将任意 多项式函数关系，按指定精度分解若干个低次多项式函数之积，提出了宽松环境进化策略 l e e ( l o o s ee n v i r o n m e n te v o l u t i o n ) 使得g e p 成功率比传统技术提高了最人5 8 倍，并通过一 系列的实验证明了g e p 的有效性。2 0 0 4 年，段磊瞄】等人借鉴生物具有的“趋利避害”天性， 提出了g e p 的“弱适应模型”，以实现在含噪声的数据集上挖掘函数关系，提出新概念“带 内集”、“带外集”并用于划分训练数据集，同时设计了弱适应模型下基于相对误差计算适应 度的算法( r e l a t i v ee r r o rf i m c s sa l g o r i t h m ，简称r e f a ) ，并用详尽的实验验证了r e f a 的有 效性。2 0 0 4 年7 月，黄晓冬【2 0 l 等人提出了一种基于基因表达式编程的函数发现关系分 域表达式挖掘方法( m u l t i - e x p r e s s i o nm i n i n g ，简称m e m ) 。它能处理具有一致表达式的关系 和具有不同分域表达式的复杂函数关系，在对该算法的复杂度和性能做出评价的同时，也论 证了m e m 方法具有对数数量级的复杂度。贾晓斌【2 9 等人分析了传统函数挖掘的不足，提出 了频繁函数集( f r e q u e n tf u n c t i o ns e t ，简称f f s ) 的概念米描述在指定数据集上具有一定支持 度的函数关系簇，同时分析了f f s 的性质并提出相应的挖掘算法，扩展f f s 以满足更多的 实际需要，还探索了f f s 在s q l 优化和分类中的应用。 天津师范人学硕十学位论文 第三章精度阈值队列驱动的g e p 方法 3 1k 表达式和g e p 编码规则 把一个问题的可行解从其解空间转换到算法所能处理的搜索空间的转换方 法称为编码。利用g e p 进行挖掘时，它不对所求解问题的实际决策变量直接进 行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传操作，达到 优化的目的。 对于一个函数关系z = f ( x ，y ) ，我们将表达式f 【x ，y ) 进行编码，形成基因。 其过程可简单描述为：将表达式根据其语义表示为表达式树( e x p r e s s i o nt r e e ， e n ；然后从上到下，从左至右的按层遍历e t ，得到的符号序列即为基因编码的 有效部分。遍历后得到的符号序列在此我们称为k 表达式( k - e x p r e s s i o n ) 1 7 1 。 基因表达式编程的染色体是由k - 表达式构成的。先来介绍一下什么是k 一表 达式。 如果表达式中出现的函数具有确定数量的变量，可以通过不同的方法将表达 式进行线性化。最常见的线性化方法就是采用先序、中序或者后序遍历序列来表 示表达式。因为运算符优先级和结合顺序的原因，中序遍历不能完全如实的反映 表达式，所以很少有进化算法将中序遍历序列作为遗传编码，并且让遗传算子操 作该序列。而先序和后序遍历序列则能够完全如实地反映原表达式，在某些改进 的遗传编程算法中，采用了先序或者后序遍历序列作为遗传编码。例如，对于表 达式( 3 1 ) 。 4 s i n ( x + x y ) ( 3 1 ) 其对应的e t 如图3 1 所示( 其中，q 表示开方运算，s 表示正弦运算) ， 对该e t 进行按层遍历，得到序列( 3 2 ) 。 1 2 天津师范人学硕十学位论文 q s + x 幸x y 图3 1 e x p r e s s i o nt r e e ( 3 2 ) 序列( 3 2 ) 是表达式( 3 1 ) 的k 表达式( k - e x p r e s s i o n ) ，它构成了我们表 达式的基因编码的主体。将k 表达式按以上过程的逆过程进行便能解码得出对 应的数学表达式。 定义1 ：( k - 表达式( k e x p r e s s i o n ) ) 对于定义在g e p = 上的表达式树， 对一棵表达式树，按照从上到下，从左到右的顺序遍历，所得到的序列，称为表 达式树的k 表达式【3 6 】。 实际应用问题往往比表达式( 3 1 ) 更复杂，可能在表达式中出现常量和系数。 由于符号和数字在格式上的差异，在进行遗传操作的时候不便统一进行处理，本 文在实验中将表达式中的具体数值分离出来，在出现数字( 常量或系数) 的地方用 一个统一的符号代替( 例如“? ) ，而将具体这些数值依次存至一个向量中。解码 时，在数值编码串中依次选取数值代替表达式中的“? ；相应的，其基因编码也 分为两部分：表达式编码串和数值编码串。其中，数值编码串的长度( m 个数字) 也是固定的，为保证足够的数字个数，我们令m = h 。 3 2 基因表达式编程g e p 算法 基因表达式算法的基本步骤从随机产生一定数量的染色体个体( 初始种群) 开始。然后将这些染色体生成表达式树，依靠一个适应度样本集( 也称为选择环 1 3 天津师范人学硕+ 学位论文 境，即问题的输入) 计算出每个个体的适应度。然后个体按照其适应度被选中， 进行有修饰的复制。留下具有新特性的后代。接下来，这些新的个体也要经历相 同的发展过程：基因组的表达，面临选择环境，选择和有修饰的复制。该过程重 复若干代，直到发现一个优良解。 3 - 2 1 遗传算子 ( 1 ) 选择( s e l e c t i o n ) 选择是用来确定重组或交叉个体，以及被选个体产生多少个子代个体。比较 常用的选择方法有：轮盘赌选择法【2 6 1 、随机遍历抽样法、局部选择法、锦标赛选 择法。本文采用轮盘赌选择测量。 ( 2 ) 变异( m u t a t i o n ) 对染色体的每一位基因按照设定的变异概率p m 进行变异，如果染色体的头 部基因发生变异，则随机选择一个函数符或终结符代替原来的基因；如果尾部基 因发生变异，则只能随机选择一个终结符代替原来的基因。这样，经过变异后， 染色体头部基因仍然是由函数符和终结符构成，尾部基因仍然只由终结符构成。 变异算子是对g e p 算法影响最大的遗传操作算子，进化速度与变异概率 的大小关系相当密切。在自然界中，每代变异发生的概率相当低，与之相比， g e p 算法中的变异概率要高的多。在g e p 算法中变异概率如果设置的太小，则 进化速度缓慢；设置的太大，则变成随机搜索状态，进化速度也很缓慢。目前， g e p 算法在理论上还很不成熟，设置变异概率还主要依靠经验。 ( 3 ) 根插串( r o o t h i n s e r t i o ns e q u e n c e ，r i s ) 从基因组头部随机选择一个基因位置，向尾部方向扫描，直到遇到第一个函 数符为止，然后从这个函数符开始向后读取一个基因片断，最后把这个基因片断 复制后插入到头部的第一个位置，头部基因顺序向后移动，超出头部长度的基因 将被删除。如果在头部没有扫描到函数符，则什么也不做。在根插串算子中，读 取基因片断的长度是从用户设置的几个值中随机选取的。 ( 4 ) 插串( i n s e r t i o ns e q u e l l c e ，i s ) 从基因组中随机选择一个开始位置，向后读取( 复制) 一个基因串，这个基 因串的长度是从设定的几个值中随机选取的。然后从基因组头部随机选择一个非 1 4 天津师范人学硕+ 学位论文 第一位的插入位置，把这个基因串插入到这个位置，插入位置后的头部基因向后 顺延。最后删除基因组头部最后边的几个超过头部长度的基因。 在插串算子中，开始扫描位置、插入位置和复制基因串的长度都是随机选择 的，只是插入位置不能是基因组的第一个位置。而在根插串中，插入位置只能是 基因组的第一个位置。插串中复制基因串的第一个基凶既可以是函数符也可以是 终结符，而在根插串中复制的基因串的第一个基因只能是函数符。 ( 5 ) 基因组迁移( g e n o m et r a n s p o s i t i o n ) 从染色体中随机选择一个基因组，然后把该基因组移动到染色体的最前边。 在基因组移动操作中，基因组执行的是移动，执行后原来的基因组就不存在了。 而r i s 和i s 操作中，基因片断执行的是复制，执行后原来的基因片断仍然存在。 如果染色体的连接函数是参数可以互换位置的函数，如+ 或o r ，则基因组迁 移后染色体的e t 表达式树不变。也就是说，染色体的表现型不会发生任何变化。 但是基因组迁移操作对下文所讲的基因重组操作有影响。 ( 6 ) 重组( ( r e c o m b i n a t i o n ) 在g e p 中有三种重组【3 2 】：单点重组( o n e p o i n tr e c o m b i n a t i o n ) ，两点重组 ( t w o p o i n t ，r e c o m b i n a t i o n ) ，基因重组( g e n er e c o m b i n a t i o n ) 。在单点重组的过程 中，两个染色体在一个随机选择的点处交叉，形成两个子代染色体。在两点重组 中，染色体配对而且进行重组的两个点随机选取，两个染色体中重组点之间的部 分随机互换，形成两个子代染色体。在基因重组中，交换的是整个基因。在所有 的情况中，两个随机选取的父代染色体配对并相互交换成分。值得注意的是，基 因重组算子并不能产生新的基因：新产生的个体只是现存基因的不同排列和组 合。 3 2 2 适应度函数 所有的进化计算算法都需要对代表个体的问题解答进行评价。在g e p 中由 于解答是一个程序，在很多应用中确切说是一个表达式，对表达式进行评价，就 是要评测利用表达式计算得到的数据和训练数据的符合程度。 而评价函数则是度量物种对环境适应能力强弱的指标，也是演化算法与问题 的接口，对演化算法的收敛速度和结果影响很大。根据问题的特点而设计合适的 1 5 天津师范人学硕+ 学位论文 评价函数，能产生适宜于演化算法处理的状态空问，能使算法快速有效地收敛。 c a n d i d a 提出了两种评价模型。根据不同的挖掘对象的特点，可以选择不同 的适应度函数。根据本文函数表达式的特点，本文引入文献 3 3 1 的两类适应度 函数，并进行讨论。 ( 1 ) 基于误差的适应度函数 针对误差在适应度函数中起的作用，我们讨论了3 种情况：( 1 ) 标准差法( 式 3 3 ) ；( 2 ) 均方差法( 式3 4 ) ；( 3 ) 误差算术平方根平均法( 式3 5 ) 。适应度函数均做 了归一化处理。我们把这三种适应度函数计算方法分别命名为f s e ( f i t n e s so l l s t a n d a r de r r o r ) 、f m s ( f i t n e s s o n0 1 1m e a ns q u a r e ) 和f m s r ( f i t n e s so nm e a ns q u a r e r o o te r r o r ) 。 f l2 f i2 ( g j 一乃) 2 = l + l + 1 ( 3 3 ) ( 3 4 ) ( 3 5 ) 其中，表示第i 个基因的适应度；c ，表示根据第i 个基因对应的函数表达 式利用第j 个样本中的变量数据求得的函数值；1 1 ，表示第j 个样本中包含的实际 测得的该目标函数值的真实值；1 1 则为样本数量。例如，若某一代的群体中第i 个基因的表现型表示量x 、y 、z 之间可能的函数关系z = f f x ，y ) ，而实验测得第j 个样本为( 弩，玢，劢，则g 产f ( x j ，y j ) ，而驴掣3 3 】。 显然，在样本数据无误差时，对于其表现型与真实的函数关系完全吻合的基 因g f ，有c i , f y j j = l ，2 ，n ) ，其适应度= 厶矿1 ； 实验中测得误差与适应度 值的关系如图( 3 2 ) 所示。从图中可以看出，只有误差为零时才能使适应度为l ， 即c 尸，踟= 1 ，2 ，n ) 时，与真实情况相去甚远的基因，其适应度将趋近于0 ， 而在实际操作中，无论是随机生成的数据还是在u c i 数据集上下载的数据，由 1 6 亨知( r ，巧) 一 【3 6 ) 。，i 二i _ ! 二三二；个基因代表的函数关系；为第，个样 忧 ，l 一。啦 、，柏镌i r 虿予 其中，n 同样为样本数；r f 表示第i 个基因。i l 砜刚幽” h , c , j - 7 j - - o 1 3 7 ) 著 篙膨 脚 嚣献碰晒 嚣 肘躬b 采躺灞 黔 一一一 p ，菇筌 旺 弗卿辩 一 一一一 编 磬是g 蝴 樽稚邪 达 遗噼滋 表 肭科嘣 一 一一一 天津师范大学硕士学位论文 1 8 天津师范人学硕+ 学位论文 图3 3g e p 的算法流程图 g e p 算法如下： 算法1 ：g e p 基本算法 输入：训练数据集d a t a s e t ，函数集f u n c t i o n s e t ，基因头部长度l e n g t ho f h e a d 输出：最优个体b e s t c h r o m o s o m e b