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

的创建必然受到每个算子的约束[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 ,
其中：ni > 0 ， 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所示的模式组织起来的客户信息，我们通过用"选择反

代 fa fi hi ni 完全选中？ 0 26.68 18.67 10 12 N 2 26.57 19.71 27 100 N 10 25.70 19.65 13 23 N 25 22.39 11.00 16 16 N 36 17.69 0.00 27 27 Y 52 2.85 0.00 27 27 Y 93 2.17 0.00 27 27 Y 199 2.59 0.00 27 27 Y
( T = 27 , P = 100 , 代数 = 200 )

映质量问题达到或超过3次的客户"的查询，即：
（G-REL（RES 产品（≥送交维修 3））购买 by 客户）
得到27个例子的对象集{"客户C5"，"客户B2"，… }。将这个对象集提交给系统，查询的发掘过程以100个随机产生的查询开始。表2显示了发掘出的每一代最好的查询摘要。fi，hi和ni分别是最佳查询i的适应值、被选中次数和结果集的势，fa为平均标准适应值（fa = (∑fi)/P,P是种群的大小，(∑fi)为种群适应值的和）。
在第52代时，我们已经得到了相当好的结果。此时，平均适应值已由第0代的26.68降到2.85。其最好的查询被完全选中，查询可叙述为"选择反映质量问题达到或超过3次的客户，并且购买的产品的出厂日期为97年11月以后到98年5月以前。"即：
（G-REL
（RES 产品（≥送交维修 3））
购买 by 客户
（SEL 产品 （OR（< 出厂日期 98年5月）（> 出厂日期 97年11月 ）））
如果不考虑所使用的是模拟数据的话，可以说我们已经发现了蕴藏在数据库中的知识了。

4 小结
本文在知识发掘系统的框架上引入了GP算法，并以一个实验例子为背景，说明使用GP算法产生最佳查询方法的有效性，展示了该系统的应用潜力。我们将进一

上一页  [1] [2] [3]  下一页