基于gp算法的知识发现系统论文

《基于gp算法的知识发现系统论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于GP算法的知识发现系统论文摘要本文提出了一个新的知识发现系统。该系统以遗传编程算法为核心，解决发现一组属于面向对象数据库的对象所具有的共性问题。本文对系统作了扼要的说明，对GP算法进行了描述，并给出了一个实验例子。关键词进化计算遗传编程知识发掘在数据库中发现有用的知识是数据挖掘（DataMining,DM）的主要任务，在一定的情况下，所有的数据库查询可以认为是完成这项任务。我们现在有一套分析和探索数据的工具：SQL查询、OLAP和数据挖掘技术。SQL查询由关系代数所构成；OLAP提供了建立在多维数据模型基础上的高水平查询；而数据挖掘提供了最

2、抽象的数据分析操作。我们可以认为不同的数据挖掘任务是在高水平上的复杂查询。数据挖掘是机器学习和数据库技术的交叉学科，DM系统的主要特点是：在数据库中发现能够用某些规则表述的、隐含的知识；与数据库是紧密集成的；高度自动化的；对知识发现的处理是有效率的（尤其对大型数据库）。这里我们给出一种基于GP（GeicProgramming，遗传编程）算法的知识发现系统.freelentSystem,面向对象数据库管理系统）、知识库、DB接口和用户接口组成。系统以一组对象、领域知识和模式信息作为输入。根据所给输入，GP引擎将产生许多随机的查询，系统将这些查询应

3、用于OODBMS，OODBMS将返回其结果。系统用给定的输入对该返回结果进行评价，评价是计算个体查询的适应值的过程。那些能够匹配所给对象集的查询或查询集将被选中，在没有查询能够匹配所给对象集时，那么其最好的查询将被选中。最后，将能够最好地描述所给对象集特性的查询作为输出。1．2面向对象的数据库这里，我们假定一个基于面向对象和函数的数据库模型（Object-OrientedandFunctionalDataModel,OOFDM），OOFDM具有面向对象和函数数据模式的特性。这种模型要比传统的关系数据库模型在表达知识时更加逼近和容易。OOFDM的

4、基本概念是"将感知到的真实世界作为相互关系对象的变量，并从不同的更细的层次上观察这些对象。"2函数数据模型可以简单地借助函数的数学符号来表示数据间的关系。每个类（或实体集）有自己的属性和值，类与属性间的关系是将类中的对象集映射到属性域的一个函数。关系或逆关系组成了类间的连接。1．3查询算子我们使用下列查询算子作为其面向对象数据库的查询语言。①SELC-1(谓词)该算子选择所有属于C-1且满足谓词的对象。C-1既可以是一个类名也可以是一个属于C-1的查询。谓词是一个可选项。如果在这个算子里没有谓词，它将选择该类中的所有对象。②RESC-1谓词该算

5、子根据所给谓词，限制给定集合的对象与另一个类的对象关联。C-1和谓词同SEL算子，但对于RES的谓词属性必须是关系型的属性，而对于SEL算子谓词属性则必须是非关系型属性。③RELC-1R-rClass-2该算子选择所有C-1中与C-2中对象有关联的对象。这是一个通过R-r将一个类C-1与另一个类C-2关联起来的关系算子。R-r可以是一个通过C-1中定义的关系集中的关系属性之一。C-1既可以是一个类名也可以是一个属于C-1的查询。C-2必须是一个类名或是一个属于C-2的查询，并且通过R-r关联到另一个类C-1。④G-RELC-1R-rC-2该算子

6、是REL的逆算子，它选择所有C-2中与C-1中对象有关联的对象。C-1、C-2以及R-r的意义同REL算子。2GP算法遗传编程（GP）属于进化计算（Evolutionaryputation，EC）模型的一种。EC是一种借鉴自然界进化机制而产生的并行随机搜索算法。进化算法的基本原理是选择和改变，它区别于其他搜索方法有两个显著特征：首先这些算法都是基于种群（population）的；其次在种群中个体（indvidual）之间存在竞争。为搜索特定的（感兴趣的）查询需要一种工具，这种工具可智能生成一组查询并以它们是否能导出与用户给定的同样的对象集来进行

7、评价。GP算法对这一类问题是很实用的。2．1函数集与端点集一般GP中可生成的程序集是使用者定义的函数集和端点集。表1给出了相应的函数集和端点集，其中函数集由1.3中定义的查询算子、逻辑运算算子以及比较算子所组成。函数集{SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}，{，=，=，，=}端点集类集，属性集，值集表1函数集和端点集在我们的应用中还有一些具有不同句法的查询算子。每个算子具有不同的句法且假定的数据库是面向对象的。因此，它具有为创建个体而使用的特别的函数集（或算子集）和端点集。从而，构成种群的所

8、有个体的创建必然受到每个算子的约束3。约束可以是算子的句法和查询的类型，或者是为创建查询选择适当属性值的领域知识。比较算子和逻辑算子只使用于查询的谓词