不完备决策表的启发式知识约简算法研究

摘要

经典Rough集理论是基于完备信息系统的.然而在实际应用中,由于数据存取或数据处理方面的原因,决策表经常是不完备的,即存在缺值.为了处理不完备信息系统,Kryszkiewicz提出了基于容差关系的Rough集模型.在该模型下进行知识约简时,现有的算法一般都采用构造区分矩阵和相应区分函数的方法.该方法虽然可以求得所有约简,然而业己证明这是一个NP-hard问题,因此实践中更为可行的方法是利用启发式搜索算法求出最优或次最优约简.在文中提出属性的重要性定义,并以此作为启发式信息,设计一种完备的知识约简算法.