基于遗传算法的粗糙集知识约简方法

《基于遗传算法的粗糙集知识约简方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第21卷第4期(总第118期)2003年7月系统工程SystemsEngineeringV01．2l，No．Jul．，2003文章编号：t001—4098(2003)04—0116-07基于遗传算法的粗糙集知识约简方法’陶志1’2，许宝栋1，汪定伟1，李冉1(1．东jE大学信息科学与工程学院，辽宁沈阳110004；2．沈阳航空工业学院，辽宁沈阳110034)摘要：提出一种基于遗传算法的知识相对约简算法。通过在知识表达系统中引入决策属性支持度的概念，来描述由条件属性所提供的知识对整体决策的支持程度，并通过决策属性支持度定义条件属性对决策属性的相对重要性，以此作为启发

2、式信息求出相对核，并将相对核加入遗传算法的初始种群中以加快算法的收敛。同时，在适应值函数中引入惩罚函数，可以保证所求约简既舍较少的属性又有较强的支持度，能够获得最佳的搜索效果。该算法通过实例分析，证明是求解知识约简问题的快速有效方法。关键词：粗糙集理论；遗传算法；决策属性支持度；相对核；相对约简；适应值函数中圈分类号：023文献标识码：A粗糙集理论是由波兰学者Pawlak于1982年提出的[1]．它作为一种刻划具有不完整性和不确定性信息的全瓤数学工具，已经成为人工智能领域的一个新的学术热点。其主要思想是，在保持知识库的分类能力不变的前提下通过知识(属性)约简，导出问题的决

3、策或分类规则[2]。目前，粗糙集理论已被成功的应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域[3“]。知识约简问题是粗糙集理论的一个核心问题。所谓知识约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的冗余知识。一般来讲，一个知识库中的知识约简不是惟一的，计算知识约简的复杂性是随者决策表的增大呈指数增长的，是一个典型的NP完全问题¨]。现有的约简算法，主要是从粗糙集的核出发。采用启发式搜索的方法构造所含条件属性最少的约简，即最小约简。但是这种算法并非对所有的知识表达系统都适用M]，而且随着问题规模的增大会越来越复杂。遗传算法，恰好由于它本身具

4、有全局优化和隐含并行性等优点，因此很适合于这个问题的求懈。遗传算法是基于生物学进化原理的全局搜索算法。通过用计算机模拟生物进化过程，群体不断优化，并在变化过程中找出最优解。用遗传算法求解知识约简，通常会减小计算的复杂性。本文利用遗传算法，提出在知识表达系统中求解知识相对约简的方法，该方法可以在问题规模较大时，求出最小相对约简或近似最小相誓约简。通过本文实例说明，该算法是有效的，可快速收敛到全局最优解。1粗糙集基本概念我们首先给出粗糙集的有关概念和结论。1．j知识表达系统与属性相对约简定义1E?’四元组S=(【，，A，V，厂)是一个知识表达系统，其中(，表示对象的非空有限集

5、合．称为论域；以一(1U，)，(1nD一⑦，C称为条件属性集．D称为决策属性集；矿=UV。，V。是属性d的值域；厂表示U×以一V是一个信息函数．它为每个对象的每个属性赋予一个信息值，即：Vd∈A，z∈U，f(x，口)∈V．我们将具有条件属性和决策属性的知识表达系统称为决策表。*收稿日期：2003—02—01基金项目：国家自然科学基金资助项目(70171056)；国家重点科技攻关资助项目(975620107)作者简介：陶志(1963一)．男，辽宁沈阳人．沈阳航空工业学院副教授，东北大学博士研究生；许宝栋(1943一)，男．江苏泗阳人东北大学教授；汪定伟(1944一)．男．江

6、西彭泽人，东北大学教授。博士生导师。万方数据第．{期陶志，许宝栋等：基于遗传算法的粗糙集知识约简方法1l7每个属性予集，∈A决定了一个二元不可区分关系[8■ⅣD(P)：IND(P)一{(z，y)∈U×U1V口∈A，f(x，口)=f(y，d)}性质1曲}IND(P)是论域(，上的等价关系，且IND(P)=NINl)({d))。性质2bo令P，Q呈A，pC_Q，则1ND(Q)SIND(P)。关系IND(，)(P∈一)构成了￡，的一个划分，用U／IND(P)表示．简记为U／1’．0／，ⅣD(，’)中的任何元素lr]，称为等价类。E，／JⅣD(P)表示知识表达系统5=([，，A，

7、V，厂)中与P褶关的知识．是最小不可识别对象集，也体现该知识交达系统的最高辨别能力。令P，Q量“，U／IND(P)=(，／，ⅣD(Q)表示Vz∈U有Ix]r=Ix]。；(，／，^rD(P)≤(，／，ⅣD(Q)表示Vz∈U有b]，=bL；U／IND(P)cU／IND(Q)表示Vz∈U有[。]，一b]。且存在z∈U有[z)，cb弘．定义2设S==((，，A，V，．厂)是一个知识表达系统，对于每个子集X∈(，和一个等价关系R量A，称子集RX—b∈(7I[。r]。曼x}为x的R下近似集。x的R下近似集也称作x的R正域，记作posR(x