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

Research on Heuristic Knowledge Reduction Algorithm for Incomplete Decision Table

作　　者：章正辉 戴小鹏[2] 熊大红[2] 陈垦[2] 邓胜[2] 

机构地区：[1]长沙市中等城乡建设职业技术学校,湖南长沙410126 [2]湖南农业大学信息科学技术学院,湖南长沙410128

出　　处：《计算机与现代化》2010年第3期170-172,共3页Computer and Modernization

基　　金：国家863资助项目(2007FJ4080)

摘　　要：经典Rough集理论是基于完备信息系统的。然而在实际应用中,由于数据存取或数据处理方面的原因,决策表经常是不完备的,即存在缺值。为了处理不完备信息系统,Kryszkiewicz提出了基于容差关系的Rough集模型。在该模型下进行知识约简时,现有的算法一般都采用构造区分矩阵和相应区分函数的方法。该方法虽然可以求得所有约简,然而业己证明这是一个NP-hard问题,因此实践中更为可行的方法是利用启发式搜索算法求出最优或次最优约简。在文中提出属性的重要性定义,并以此作为启发式信息,设计一种完备的知识约简算法。The classic theory of Rough sets is based on incomplete information systems. In practicing, decision tables are, however, usually incomplete due to the causes of data outputting or processing. That is to say, there are often default values. In order to deal with incomplete systems, Kryszkiewicz puts a Rough sets model on the basis of error tolerance relations. According to this model, constructing discernibility matrixes and discernibility functions are the familiar approach by the current knowledge reduction algorithms. By this means, all reductions can work out. But it has been proved that it is a problem of ＂NT-hard＂. So it is more effective when a heuristic search algorithm is used to attain the most optimized or the second most optimized reduction. In this paper, the importance of attributes is defined and used as heuristic information. Then a complete knowledge reduction algorithm is put forward.

关 键 词：ROUGH集 不完备决策表 知识约简 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]