基于GP算法的知识发现系统

基于GP算法的知识发现系统南京建筑工程学院计算中心李亚非

摘要本文提出了一个新的学问发觉系统。该系统以遗传编程算法为核心，解决发觉一组属于面对对象数据库的对象所具有的共性问题。本文对系统作了扼要的说明，对GP算法进行了描述，并给出了一个试验例子。

关键词进化计算遗传编程学问发掘

在数据库中发觉有用的学问是数据挖掘（DataMining,DM）的主要任务，在肯定的状况下，全部的数据库查询可以认为是完成这项任务。我们现在有一套分析和探究数据的工具：SQL查询、OLAP和数据挖掘技术。SQL查询由关系代数所构成；OLAP供应了建立在多维数据模型基础上的高水平查询；而数据挖掘供应了最抽象的数据分析操作。我们可以认为不同的数据挖掘任务是在高水平上的简单查询。数据挖掘是机器学习和数据库技术的交叉学科，DM系统的主要特点是：在数据库中发觉能够用某些规章表述的、隐含的学问；与数据库是紧密集成的；高度自动化的；对学问发觉的处理是有效率的（尤其对大型数据库）。

这里我们给出一种基于GP（GeneticProgramming，遗传编程）算法的学问发觉系统，和通常对数据库的查询不同的是，这个系统可对特定的对象集产生特定的查询集，系统自动依据查询集访问数据库，从而发掘出数据库中隐含的学问。本文将对上述学问发掘过程进行具体描述，并提出了一种用遗传编程（GP）来进行数据挖掘的方法，GP个体由数据库查询组成，而这些查询代表了高水平上的规章。

1系统基本结构

我们在[1]文给出的学问发觉系统结构基础上加以改进，给出如图1的基于GP算法的学问发觉系统。

1．1系统结构描述

整个系统由GP引擎、OODBMS（Object-OrientedDatabaseManagementSystem,面对对象数据库管理系统）、学问库、DB接口和用户接口组成。系统以一组对象、领域学问和模式信息作为输入。依据所给输入，GP引擎将产生很多随机的'查询，系统将这些查询应用于OODBMS，OODBMS将返回其结果。系统用给定的输入对该返回结果进行评价，评价是计算个体查询的适应值的过程。那些能够匹配所给对象集的查询或查询集将被选中，在没有查询能够匹配所给对象集时，那么其最好的查询将被选中。最终，将能够最好地描述所给对象集特性的查询作为输出。

1．2面对对象的数据库

这里，我们假定一个基于面对对象和函数的数据库模型（Object-OrientedandFunctionalDataModel,OOFDM），OOFDM具有面对对象和函数数据模式的特性。这种模型要比传统的关系数据库模型在表达学问时更加靠近和简单。OOFDM的基本概念是"将感知到的真实世界作为相互关系对象的变量，并从不同的更细的层次上观看这些对象。"[2]函数数据模型可以简洁地借助函数的数学符号来表示数据间的关系。每个类（或实体集）有自己的属性和值，类与属性间的关系是将类中的对象集映射到属性域的一个函数。关系或逆关系组成了类间的连接。

1．3查询算子

我们使用下列查询算子作为其面对对象数据库的查询语言。

①SELC-1[(谓词)]该算子选择全部属于C-1且满意谓词的对象。C-1既可以是一个类名也可以是一个属于C-1的查询。谓词是一个可选项。假如在这个算子里没有谓词，它将选择该类中的全部对象。

②RESC-1谓词该算子依据所给谓词，限制给定集合的对象与另一个类的对象关联。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该算子是REL的逆算子，它选择全部C-2中与C-1中对象有关联的对象。C-1、C-2以及R-r的意义同REL算子。

2GP算法

遗传编程（GP）属于进化计算（EvolutionaryComputation，EC）模型的一种。EC是一种借鉴自然界进化机制而产生的并行随机搜寻算法。进化算法的基本原理是选择和转变，它区分于其他搜寻方法有两个显著特征：首先这些算法都是基于种群（population）的；其次在种群中个体（indvidual）之间存在竞争。

为搜寻特定的（感爱好的）查询需要一种工具，这种工具可智能生成一组查询并以它们是否能导出与用户给定的同样的对象集来进行评价。GP算法对这一类问题是很有用的。

2．1函数集与端点集

一般GP中可生成的程序集是使用者定义的函数集和端点集。表1给出了相应的函数集和端点集，其中函数集由1.3中定义的查询算子、规律运算算子以及比较算子所组成。

函数集{SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}，{，=，=，，=}端点集类集，属性集，值集表1函数集和端点集

在我们的应用中还有一些具有不同句法的查询算子。每个算子具有不同的句法且假定的数据库是面对对象的。因此，它具有为创建个体而使用的特殊的函数集（或算子集）和端点集。从而，构成种群的全部个体的创建必定受到每个算子的约束[3]。约束可以是算子的句法和查询的类型，或者是为创建查询选择适当属性值的领域学问。比较算子和规律算子只使用于查询的谓词。当比较符号操作数时，仅使用'='。

端点集由CLASS-SET、SLOT-SET和VALUE-SET组成。CLASS-SET由1.2中定义的类名组成，SLOT-SET由每个类的全部属性构成，VALUE-SET由数值和符号值所构成（它们均为属性值）。数值由整型或实型数构成，其数值范围由所用数据库模式定义。符号值由字符串表示的符号属性值构成。

2．2创建初始种群

为了创建一个个体（查询），首先必需确定特定查询所返回的对象类型。结果类型被选择后，从所选类型返回例子的算子集中随机地选择一个算子，这个过程对查询的每个参数递归地进行。最初，那些句法正确的预定义数量的查询被随机地产生，形成初始种群。

2．3选择属性值

由于可选择范围大，要从某个查询的值集中选择一个属性值（数值或符号常数）是相当困难的。对于一个范围为[1，10000]的整数集，随机选到一个特定整数的概率仅为1/10000。而对于符号常数，则需要很强的背景学问。因此，我们仅就发生在数据库里的范围选择属性值。

2．4繁殖新一代种群

每个个体用预定义的适应函数来进行评价。较适应的查询有较高的概率被选来繁殖新种群，这个过程用三个遗传算子：选择、杂交和变异来完成。为了产生下一代，选择算子依据个体的适应值来选择个体。我们用一个树来表示一个查询，杂交算子用交换两个父辈的子树来创建两个后代。变异算子用一个新的子树来代替一个父辈的子树，从而产生一个新的后代。选择-杂交-变异循环反复地进行直到终止标准被满意。

2．5评价（适应函数测量）

我们使用如下的适应函数f来评价种群中的个体查询i：

f(ni,hi)=T-(hi*hi)/ni,

其中：ni0，T≥hi，且i=1，2，…，种群的大小（T是被确定的对象集的势，hi是一个个体查询i被选中的次数，ni是查询i结果集的势）。

上述适应函数依靠于hi和ni，假如一个查询没有被选中（hi=0），则函数的值为T，这是最差的一个适应值。另一方面，假如查询结果能够很好地匹配提交给系统的对象集，那么它的适应值为0（在这种状况下hi=ni=T）。假如种群中消失个体适应值远远超过种群平均适应值，该个体很快就会在群体中占有肯定的比例，从而消失过早收敛的现象。另一方面，在搜寻过程的后期，群体的平均适应值可能会接近群体的最优适应值，从而导致搜寻目标难以得到改善，消失停滞现象[4]。为了防止上述状况的发生，我们将对一个个体查询的例子个数ni作为分母。

3一个例子

我们首先给出一个如表2所示的模拟"售后质量管理函数数据库"，用它来代表一个基于OOFDM的面对对象数据库，它包含了客户及其相关的信息。表3说明白类间的相互联系。

类属性值客户代码、电话、名称、地址、类别、地区、托付、购买代理商代码、名称、地址、电话、信誉等级产品名称、编号、出厂日期、购买日期、检验员修理记录问题、修理时间、修理次数、修理员使用培训否、技术力气质量问题外观、电器、机械、装配表2售后质量管理数据库

类客户代理商产品修理记录使用质量问题客户+++代理商+产品+++修理记录+使用++质量问题++表3类间的连接表

3．1问题的提出

依据质量管理部门反映，有两个客户反馈的产品质量问题较为严峻，我们盼望通过对数据库的查询来找出这两个客户在购买的产品及使用上所具有的共性。

3．2试验结果

在我们的数据库里包含如表2所示的模式组织起来的客户信息，我们通过用"选择反

代fafihini完全选中？026.6818.671012N226.5719.7127100N1025.7019.651323N2522.3911.001616N3617.690.002727Y522.850.002727Y93