摘要
属性约简是RoughSet理论研究中的核心内容之一,现在已经证明寻找决策表的最小约简是NP hard问题。本文首先阐述了可辨识矩阵的概念;然后在此基础上提出了一种基于可辨识矩阵和信息熵的属性约简的新算法,并给出了该算法的时间复杂度;最后,通过实例分析表明,本文算法能够成功用于决策判断,并且在多数情况下该算法能够得到决策表的最小约简。
Attribute reduction is one of the most important topics in the research on rough set theory. It has been proved that computation of the optimal (minimal) reduction for decision table is a NP-hard problem. In this paper, the concept of dicernibility matrices are introduced; then an algorithm based on dicernibility matrices and information entropy is proposed, and the complexity of this algorithm is analyzed. The experimental results show that this algorithm can be used in decision successfully and can find the optimal reduction for most of the decision tables.
出处
《电光与控制》
北大核心
2005年第1期47-50,68,共5页
Electronics Optics & Control
关键词
粗糙集理论
属性约简
可辨识矩阵
信息熵
算法复杂性
rough set theory
attribute reduction
dicernibity matrix
information entropy
complexity of algorithm