ITPub博客

首页 > 大数据 > 数据挖掘 > 达尔文、孟德尔与老愚公的会盟:基因表达式编程--趣味数据挖之十 tang

达尔文、孟德尔与老愚公的会盟:基因表达式编程--趣味数据挖之十 tang

数据挖掘 作者:chen_j838 时间:2012-02-17 16:14:45 0 删除 编辑

此文转自笔者的科学博客

达尔文、孟德尔与老愚公的会盟:基因表达式编程--趣味数据挖之十(唐常杰)

 

GEP的速度魅力 在本系列之九的末尾提到,基因表达式编程GEPGene Expression Programming)是一种数据挖掘工具,是进化计算家族中较新的成员。在很多应用中,GEP比更传统的进化算法2-4个数量级[1,2,3];在实践中还发现,在某些特定场合,比传统方法快5-6个数量级,甚至更多。目前一些学校把GEP作为计算机专业及相关专业作为硕博士选修课程。

GEP的速度魅力太吸引人了,12年前,关于GEP的简单信息在网上刚露头角,两周后,我们研究团队中,处于选题饥饿的博士生们读到了它,团队立刻跟踪研究,十多年来,得到过多个科学基金支持,至今还不疲不倦,无怨无悔,只因为它太奇妙,太快了。

为诠释这些稍难的内容,从过去的课程PPT中取较多图示,任重而文短,作为科普博文,只能给出大致的轮廓。

 

2 GEP不是什么,又是什么 GEP不是生物工程,不是生命科学。发明人Ferreira, Candida 把它称为 Biologically Inspired Computing,(生物灵感激发的计算),它是一种数据挖掘的工具,它借用了生命科学中基因,染色体等概念和进化的框架,作数据挖掘,用于发现公式、规则或规律。

 GEP可以做什么? 它可以挖掘多种表达式(关联规则、分类规则、聚类规则、 逻辑规则,数学方程、公式),例如发现太阳黑子规律,发现开普勒定律,设计门电路……,我们课题组还提出过一个新应用:作传统意义的因式分解,特别地,当给定多项式是质因式(在整数环上不可分解的多项式),如果强迫分解,也能做近似分解;表1给了一些示意,技术细节参见文献[4]

           

输入:指定的或随机产生的测试函数

输出:GEP分解的结果多项式集

2x6-x5-5x4+8x3+1

2.00x3+3.00x2–1.00x+1.00; 1.00x3-2.00x2+1.00x+1.00

12x7+2x6+27x5+52x4+24x3+70x2+39x+5

2.99x2-1.00x+5.00;  4.00x2+6.01x+0.98;

1.00x3-1.00x2+1.99x+1.00

2x10+x9-x8+18x7-46x6+87x5-58x4+79x3-90x2 +34x-24

1.00x2-2.01x+2.00;1.00x3-0.99x2+3.00x-4

2.00x2+0.98x+2.99; 1.02x3+3.00x2+1.00

1  GEP作因式分解

下面将比较GEP及其前辈算法GA(遗传算法 Genetic Algorithm)和 GP(遗传编程 Genetic Programming);先说差别,后说共性。

 

     差别在何处? 编码有代沟。

    GEP和与其前辈遗传算法(GA)和 遗传编程(GP)的差别表现在遗传物质编码方式。上文用非编码形式介绍过公式 1 + x4   5 – x的杂交和变异,回忆相关要点:

杂交 1 + x4 ,   5 - x ,施加以换头术,交换红蓝部分, 可以杂交出  5+ x 1-x

变异:在染色体中插入、删除、或修改 符号或符号片段。  6+x7 中的“+”变为“*”,得到 6*x7

 3.1 遗传算法(GA)的编码—线性串,简单编码解决简单问题  GA直接把进化对象编码成01之称的线性串,表2 示意了公式编码以及杂交(换头术):        

公式

编码

杂交(交换前k位)k=6

杂交后,解码出的公式

1+x4

1100101010

1011011010

5+x4

5-x

1011011110

1100101110

1 - x

2 GA的编码,杂交和变异

GA编码简单,适合计算机处理,但语义不丰富。是 简单编码解决简单问题

 

3.2 遗传编程(GP)的编码 – 树结构,复杂编码解决复杂问题

GP把进化对象(例如公式)编码成树。为简单,图1 示意了二叉树,基本数据结构是节点三元组:(节点号,左儿子指针,右儿子指针);通过指针适当地链接一组节点,组成从根节点开始的树。

图中语义多。理解有窍门由下而上,逐步归约。例如:左边的黄色部分,从b开始,其父节点是开平方运算Sqrt ,合起来表示 b1/2 ;类似地,右边黄色部分 可由下而上归约,得到:(b/c/a

GP的杂交 例如,把左图和右图中的黄色部分交换。(像不像器官对移?)

GP的变异: 例如,把左图中 a 突变为 x+y

GA相比,GP采用了复杂的树结构,可以表达复杂的语义,是 复杂编码解决复杂问题

 

 

1,遗传编程GP的编码,杂交和变异

  

3.3 GA和GP编码的致命缺点-遗传手术下存活率低  GAGP的遗传手术太残酷,杂交好像器官对换,变异中的插、删、改手术好像长瘤,截肢,器官移植,在这些很酷(Cool和残酷)的手术下, 大多数对象都死亡或伤残了,浪费了计算机的时空资源。

 

3.4 GA和GP的爱情结晶:GEP

Candida Ferreira融合了遗传算法(GA)和遗传编程(GP)的 优势,创造性地提出了基因表达式编程GEP。下图中给出了GAGP杂交产生GEP的框架:

 

 

2  基因表达式编程 GEP继承了遗传算法GA和遗传编程GP的优势

 

GA 继承了父亲GA的有刚性和规范,韬光养晦,藏复杂之树于简单之串,易作遗传操作,快速

GP继承了母亲GP的柔性和多变多能,语义(感情)丰富;

GEP向生物科学借鉴并实现了更多概念,如多基因染色体、如基因的表达、如中性区中隐形的继承和变异。最重要的是,GEP的巧妙编码使其成为不死鸟,在残酷的基因手术下能全部存活,这是GEPGA,GP的速度普遍提高2-4个数量级的最重要原因。

其奇妙而简单的编码称为基因表达式,将在在第5节详细解析,现保留一点美好的悬念。

 

4 家族共性:达尔文的进化框架,孟德尔的遗传规律,摩尔根的基因变异,老愚公的移山精神。
      GAGPGEP,乃至整个进化计算家族,闪耀着先贤和哲人的思想火花,有下列共性:达尔文的进化框架,孟德尔的遗传规律,摩尔根的基因变异,还有老愚公的移山精神。

算法思想和框架(粗可只看图,细则看解释) 3是遗传算法GA的进化流程,如果把其中编码方式换为GP的树,或GEP的基因表达式,就得到GPGEP的流程。与上文( 趣味数据挖掘之九 )的通例相比,图3稍细致一些:

 

 

3 遗传算法的编码和进化流程示意图

 

图1的解释(初读时,不妨跳过)中给出了编码进化的流程,初始化的三个函数 ,与进化目标y=x+sin(x)的戴劳展式相差甚远,标注框中是编码前的公式,编码成为01的串。下面跟着红色的编号(1)-(6),略作说明:

(1)初始解,离谜底y=x+sin(x)较远;(2)三个公式编码成为01串联(图是示意性的);(3)交叉,两个公式的编码实施换头术,得到后代C1C2(4)公式6+X7 变异成为6*x7   (5) 编码解码成为公式,计算误差(适应度)

(6) 轮盘赌,可比喻为庙会上的“转糖饼”游戏,轮盘的转与停是随机过程,以此决定奖励品种,颇有点“费厄泼赖”,貌似公平;而庄家实则在扇区面积上做文章,成本低的品种被选中的机会越大(对应于进化计算中的术语:适应度越大),例如,图3中的轮盘赌来自“转糖饼”游戏,其中的糖龙河糖虎成本高,对应的扇区小,指针停在这里的机会小;小糖饼成本低,对应的扇区大,指针停在这里的机会小,从而维护了庄家的利益;

(7)检查终止条件,如果没有达到终止条件,进入下一代循环,这里表现了愚公移山故事中的“子子孙孙是没有穷尽的”。

 

 5 简单编码解决复杂问题-简单而奇妙的基因表达式编码   

下图示意了GEP编码思路:图中有三个等价的表达:基因表达式,语法树和数学表达式:

 

 

4 三个等价表达,基因表达式,语法树,数学表达式

知识解释:从语法树中,从叶到根归约

 减号下面有,ab, 归约得到a-b;

加号下面有,ab, 归约得到a+b;

处理乘法符号,归约得到(a-b)* (c+d),      (如程序语言中,*表示乘法);

处理开平方符号Q,得到数学达式 ((a-b) * (c+d))1/2

 

知识表达。按计算的优先级(如先乘除,后加减)展开,先算的在下,后算的在上,最后算的为根

 

编码过程 语法树中, 从上到下,从左到右,把符号写成一串(解码程序只需几十行)。

 

解码过程:从左到右,按指标生育,按次序表达,两个要点:

(a)节点按指标生育开方只有一个参数,就只有子节点,+-*/有两个参数, 有两个子节点,If-Then-Else(或缩写为ITE)是一个运算的名称,有三个参数,即ITE节点有三个子节点。

(b)表达式中符号按次序表达。从基因表达式第一个符号开始表达:

首先表达Q(开方):Q只需一个参数,建立以Q为根的树(此时,图中只有一个根节点Q)

Q需要一个被操作数(儿子),表达式中下一个符号是X(乘法),X被表达为Q的儿子

X 需要两个被操作数(儿子),表达式中下两个符号“-”和“+”,二者作X的儿子节点,于是“-”和“+”被表达;

减号- 需要两个被操作数,表达式中下两个符号是a b,二者作减号的儿子, a b已被表达为a-b;

加号+ 需要两个被操作数,表达式中下两个符号是c d,二者作加号的儿子, c d已被表达 c+d.

叶节点上全是常数,不再需要被操作对象了, 表达完毕。

 

基因材料的 供过于求供不应求 细心地读者会发现红色的XYZ没有被表达,这种供过于求是好现象,模拟了生物基因中的中性区。如果供不应求,例如一个“+”号需要两个被操作数,基因表达中没有或只有一个被操作数,指向被操作数指针是空指针或者乱指针,将引起程序崩溃。

“平时看不见,偶尔露峥嵘”,中性区与隐性遗传,和生物基因中的中性区类似,中性区默默无闻地参加并积累着遗传和变异,但其对应的性状暂时没有表达出来。例如,图5中,X+y 是隐形基因,因为他们的父节点是常量a,而a不需要参数。假定有朝一日,符号a变异成为“+”,则“+”有两个生育指标,就把xy将表达出来了,使得这一个a会被(x+y)取代,最后结果变为((x+y-b)* (c+d))1/2   ,如图5. 人群中的隔代遗传现象不知是否有类似解释,请专家指正。

 

图5 中性区“平时看不见,偶尔露峥嵘”

 

基因表达式编程的编码之妙:F.Cadidda 发明了基因表达式编程的编码方法, 其最大的特点是:

1形串实树,藏复杂内容于平凡形式参加遗传操作时,以线性串的平凡姿态,存储简单,处理快捷;解释语义时,用树的形式表达深刻的语义。

(2)生命力强,永不死亡,前面说过,在GA和GP中,染色体在残酷的遗传手术(如换头,挖心,加瘤)下大量死亡(有时,存活的不到1%),程序要花大量时间和空间去检查存活性,极大制约的进化的速度和质量,下面的定理将说明,基因表达式在遗传操作下永不死亡 。

 

  6 Candida的直觉和基因表达式基本定理  Ferreira Candida有深厚生物医学背景,,在发明 GEP时候,她凭直觉采用了巧妙的  形“串”实“树”的数据结构,给出了下列两个宽松的约束:

a内容约束:分成头尾两部分,头部可算符与参数;尾部不含算符,只有参数;

(b)  长度约束如果头长h,尾长t,计算符号最大目数(参数个数)为n,则须满足t=h(n-1)+1 

Ferreira Candida直观感觉到,只要满足上述两条约束,头部的计算符号按生育指标索取子节点,在表达部分就有足够的被操作数供表达,不会出现供不应求的现象(而没有给证明或说明)。

供不应求对应于程序中使用未分配的指针或盲指针,例如,设P1和P2是指向参数的指针,做下列加法:

 *P1) + (*P2 ,其中P1P2 未分配的指针 或 盲指针,则可能引起程序崩溃或计算错误。

 

    2002年,我们的研究团队用数学归纳法严格地证明了:只要染色体满足上述两个(宽松是)约束, 则在任意残酷基因手术下,染色体永不死亡(参见文献[5])

 这个定理有时被称为GEP基本定理,它给出了GEP可行可信的理论依据。

 

 科学家和工程师的好工具。对于实验科学家和工程师,如果想自己开发一套GEP挖掘系统,需要半年或一年以上的学习(时间依赖于相关基础);如果使用现成的商品化的GEP系统,只需要几周的学习;这有点像造一个程序语言和使用程序语言的差别。程序语言即便简单如BASIC,也需要一定时间的学习,学好用好一个较复杂的语言(如C)要一年以上的学习和实践。

 在网上搜索Ferreira Candida 或GEP ,可以得到更多的信息,可以查到他们的公司和软件产品。也容易查到国内外研究者的成果和进展。

 使用现成的系统,经过不太长时间的学习,可从自己的实验数据中挖掘经验公式、类似于发现类似于太阳黑子规律、类似与开普勒定律的数学方程、设计门电路,还可以挖掘关联规则、分类规则、聚类规则、 逻辑规则,等等。

 

 

 下篇博文,拟讨论数据挖掘的十大算法以及哲学思考,为这个系列做个阶段性的小结。

 

参考文献

[1] Ferreira Candida, Complete reference for the first GEP paper, (12/5/2001). Gene Expression Programming: A New Adaptive 

     Algorithm        for Solving Problems, Complex Systems, 13 (2): 87 – 129 2000.12

[2] Ferreira Candida ,. Gene Expression Programming, First Edition, Printed and Bounded in Portugal, Angra doHeroismo,

       Portugal, 2002. Deposito legal n0 187498/02 (第一本GEP专著)

[3] Candida Ferreira, Gene Expression Programming: Mathematical Modeling by an Artificial

    Intelligence (Studies in Computational Intelligence),Publisher: Springer; 2nd edition

    (July 11, 2006).

[4]汪锐,唐常杰,段磊,陈宇,廖勇, 基于基因表达式的的多项式函数关系分解,计算机研究与发展,

     VOl.41. No.10 , Oct.2004 (Suppl.) P.442-447.

  [5] Zuo Jie, Tang Changjie and Zhang Tianqing"Mining Predicate Association Rule by

      Gene ExpressionProgramming", WAIM02 (International Conference for Web Information Age 2002).

      LNCS (Lecture Notes In Computer science) Vol.2419, pp.92-103,edited by, Springer Verlag

      Berling Heidelberg  2002.8,ISBN


 相关博文

    1“被打北大 的关联--- 趣味数据挖掘系列之 

    2 烤鸭、面饼和甜面酱之朴素关联---趣味数据挖掘系列之二 

    3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之

    4 巧挖科学博客之均击量公式,兼谈干预规则----趣味数据挖掘之四

    5 听妈妈讲 过去的故事,分房与分类-----趣味数据挖掘之五 

    6 借水浒传故事,释决策树思路---趣味数据挖掘之六

    7 团拜会和鸡尾酒会上的聚类趣味数据挖掘之七

    8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八

    9 灯谜、外星殖民、愚公移山和进化计算---趣味数据挖掘之九

    10 达尔文、孟德尔与老愚公会盟:基因表达式编程--趣味数据挖之十

             其它系列博文的入口      唐常杰博客主页       科学博客主页 





http://blog.sciencenet.cn/home.php?mod=space&uid=287179&do=blog&id=537914
<!-- 正文结束 -->

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/22358989/viewspace-1121778/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 没有了~
下一篇: 没有了~
请登录后发表评论 登录
全部评论

注册时间:2009-08-17