摘要
粗糙集理论是一种新的处理模糊和不确定知识的数学工具。知识约简是粗糙集理论研究中的重要内容之一,现已证明寻找信息系统的最小约简是NP-hard问题。文中提出一个基于绝对信息量的知识约简的启发式算法,该算法的时间复杂性为O(｜R｜3｜U｜2)。通过例子分析,表明该算法是有效的。
Rough set theory is a new mathematical tool to deal with vagueness and uncertainty.Attribute reduction is one of the important topics in the research on rough set theory.It has been proved that finding the minimal reduction of an information system is an NP-hard problem.In this paper,an absolute information quantity-based heuristic algorithm for reduction of knowledge is proposed,the time complexity of this algorithm is O(|R|~3|U|~2).Through running an example,show that this algorithm is effective.
出处
《微机发展》
2004年第10期114-116,119,共4页
Microcomputer Development
基金
安徽省教育厅自然科学基金资助项目(2002kj298zc)
关键词
粗糙集理论
信息系统
知识约简
绝对信息量
rough set theory
information systems
reduction of knowledge
absolute information quantity(AIQ)
