基于遗传算法的粗糙集知识约简
摘要:知识约简是粗糙集理论的核心内容之一。本文通过知识表达系统中条件属性对决策属性的重要性,来描述由条件属性所提供的知识对整体决策的重要程度,利用遗传算法,提出一种基于遗传算法的粗糙集知识约简方法。
关键词:遗传算法;粗糙集;知识约简
粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就是在保持分类能力不变的前提下,通过知识约简,导出问题的决策或分类规则。目前粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域,成为近年来的热点研究方向。
知识约简是粗糙集理论的核心内容之一。众所周知,知识库中知识(属性)并不是同等重要的,甚至其中某些知识是冗余的。知识约简,就是在保持知识库分类能力不变的条件下,删除其中不相关或不重要的知识,使得高维数据降为低维数据,从而有效地实现数据缩减、减少冗余信息,是知识发现中的重要步骤。
1知识约简的相关概念
定义1K=(U, R)为一个知识库,其中U≠是对象的有限论域,R是U上的所有等价关系的集簇。显然,如果P∩R,P≠,则∩P(P中所有等价关系的交集)也是一个等价关系,称为P上的不可区分关系,记为ind(P)。
定义2令R为一族等价关系,R∈R,如果
ind(R)=ind(R-{R}),
则称R为R中不必要的;否则R为R中必要的。
定义3如果每一个R∈R都为R中必要的,则称R为的;否则称R为依赖的。
定义4设Q∈P,如果Q是的,且ind(Q)= ind(P),则称Q为P的一个约简。显然,P可以有多种约简。P中所有必要关系组成的集合称为P的核,记作core(P)。
核与约简有如下关系
core(P)=∩red(P)
其中red(P)表示P的所有约简。
定义5令K=(U,R)为一个知识库,且P,Q∩R,当
时,我们称知识Q是k(0≤k≤1)度依赖于知识P的,记作P Q 。
定义6设S=(U,A,V,f )为一个知识表达系统,A=C∪D,C∩D≠,其中C和D分别条件属性集和决策属性集,属性子集C’∩C关于D的重要性为
特别当C ‘={a}时,属性a∈C关于D的重要性为
传统的约简算法,主要是从粗糙集的核出发,采用启发式搜索的方法构造所含条件属性最少的约简,即最小约简。但是这种算法并非对所有的知识表达系统都适用,而且随着问题规模的增大会越来越复杂。遗传算法恰好由于它本身具有全局优化和隐含并行性等优点,能够有效解决规模较大、结构复杂、计算效率较低的问题,因此很适合于这个问题的求解。
2遗传算法基本原理
遗传算法(Genetic,Algorithms,GA)是在达尔文进化论和孟德尔遗传学说的基础上提出的一种全局搜索算法。它是一类借鉴生物界自然选择和自然遗传机制的概率搜索方法。因为它既不要求目标函数连续,也不要求可微,仅要求问题可计算,并且它的搜索始终遍及整个解空间,因此易得到全局最优。
遗传算法的一般流程如下图所示
第1步随机产生初始种群,个体数目一定,每个个体为染色体的基因编码;
第2步 计算个体的适应度,并判断是否符合优化准则,若符合,输出最佳个体及其代表的最优解,并结束计算;否则转向第3步;
第3步 依据适应度选择再生个体,适应度高的个体被选中的概率高,适应度低的个体可能被淘汰;
第4步 按照一定的交叉概率和交叉方法,生成新的个体;
第5步 按照一定的变异概率和编译方法,生成新的个体;
第6步 由交叉和变异产生新一代的种群,返回到第2步。
在遗传算法中包含了如下五方面的关键因素:参数编码;初始群体设定;适应度函数的设计;遗传操作设计;控制参数的设定。
3约简的遗传算法
3.1参数编码
采用最常用的二进制编码方法。用一个长度为N的二进制串表示一个个体,其中N为条件属性总数,二进制串的每一位对应一个条件属性,某位取1表示选择该位对应的条件属性,取0示不选该位对应的条件属性。
3.2适应度函数的选取
由于是寻找分类能力最大的属性集,所以适应度函数确定为个体对应的条件属性关于决策属性D的重要性:f(a)=σCD(a)。
3.3遗传算法的操作
选择采用轮盘赌选择法。设种群大小为n,对种群中的个体按选择概率
采用轮盘赌法进行选择,其中f i为第i个个体的适应度函数,交叉算子采用两点交叉。以一定的概率pc选择个体参与交叉,对于参与交叉的两个父辈个体,随机选择两个交叉点,然后对交叉点后的部分子串相互进行交换,来产生下一代个体;以概率pm选择个体实施变异,随机选取变异个体的基因位,进行取反。
在遗传算法的运行过程中,由于选择、交叉、变异算子会破坏当前群体中适应度最好的个体,为了使当前群体中所有适应度最好的个体尽可能地保留到下一代群体中,本文采用稳态繁殖法。其具体操作过程为:①找出当前群体中所有适应度最高的个体;②对当前群体进行选择、交叉、变异运算后产生的新群体的个体适应度进行排序;③用当前群体中所有适应度最高的个体替换掉新群体中适应度低的个体。采用该方法的优点是可以加快遗传搜索的速度,同时又可保证找到所有的最优解。
4结束语
本文从知识表达系统出发,依赖条件属性对决策属性的重要性,利用遗传算法,提出一种基于遗传算法的粗糙集知识约简方法,由于遗传算法本身具有全局优化和隐含并行性的特点,所以它可以解决现有启发式算法难以解决的问题。是求解知识约简问题的一种行之有效的方法。
参考文献:
[1]王文辉,周东华.基于遗传算法的一种粗糙集知识约简算法[J].系统仿真学报,2001(13)(增刊):91-93.
[2]陶志,许宝栋,汪定伟,李冉.基于遗传算法的粗糙集知识约简方法[J].系统工程,2003,21(4):116-121.
[3]吕军,冯博琴,李波.基于遗传算法的属性约简[J].微电子学与计算机,2006,23(7):151-154.
[4]王清毅,范炎,蔡庆生.知识的约简研究[J].小型微型计算机系统.2000,2
1(6):623-627.
[5]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[6]张文修,吴伟志,梁吉业,李德玉.粗糙集理论与方法[M].北京:科学出版社,2001.
[7]刘清.Rough集及Rough推理[M].北京:科学出版社,2001.
