信息系统中知识约简的一种启发式算法.doc

本文由yuerlover1230贡献 pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 第26 卷 第2 期 2004 年4 月 压 电 与 声 光 Vol. 26 No. 2 Apr. 2004 PIEZOELECT2ICS ACO5STOOPTICS 文章编号： 1004-2474 2004） （ 02-0158-03 不完备信息系统中知识约简的一种启发式算法 何先刚1 ， 黄 兵2 ， 温平川3 （1. 重庆邮电学院 学报编辑部， 重庆 400065； 南京理工大学 自动化系， 2. 南京 210094； 重庆邮电学院 外语学院， 3. 重庆 400065） 摘 要： 不完备信息系统中的知识获取是粗集理论应用的难点。通过引入信息熵和条件信息熵， 对信息系统 中属性的必要性进行了定义； 提出了一种基于条件信息熵的知识约简启发式算法， 并指出该算法的时间复杂度是 多项式的。通过实例说明， 该算法能得到信息表的约简和决策表的最小相对约简。 关键词： 粗糙集；信息熵；启发式算法；知识约简 TP18 文献标识码： A 中图分类号： A Heuristic Algorithm for Reduction of Knowledge under Incomplete Information Systems HE Xian-gang1 ，HUANG Bing2 ， WEN Ping-Chuan3 （1. Editorial Board of Journal of Chongqing University of Posts Telecommunications，Chongqing 400065， China； 2. Dept. of Automation，Nanjing University of Science Technology，Nangjing 210094， China； 3. College of Foreign Languages， Chongqing 5niversity of Psots Telecommunications， Chongqing 400065， China） Abstract： Knowledge acquisition based on rough set theory is an important but difficult task under incomplete information systems. Information entropy and conditional information entropy are defined to express indispensable of attributes under incomplete information systems. A heuristic algorithm based on conditional information entropy for knowledge reduction is proposed，and the complexity of this algorithm is analyzed. Finally，an illustrative example analysis shows that this algorithm can find the minimal reduct for decision tables. Key words rough set；information entropy；heuristic algorithm；knowledge reduction 1 引言 粗集理论是近年来发展起来的一种处理不精 是多项式的， 并通过实例说明该算法能得到决策表 ［4， 的最小约简； 王国胤 5］等人对粗集理论的信息论 观点进行了分析， 对知识约简在信息论观点和代数 观点进行了研究， 以条件熵为启发知识设计了决策 表的知识约简算法， 通过仿真实验验证了该算法的 有效性和约简效果。 以上研究都是以完备信息系统为研究对象的， 在现实中， 信息的不完备 对象的属性值缺损） （ 现象 是广泛存在的， 此时， 经典粗集理论的等价关系不再 ［6］ 成立， 于是人们将等价关系放宽为相容关系 （ 自 ［7］ 反性、 对称性） 相似关系 （ 自反性、 、 传递性） 甚至 ， ［8］ 为一般二元关系 （ 一般要求满足自反性） 。因此， 确、 不完全信息的软计算