摘要
从知识区分能力角度提出同可区分度的概念,并对其性质进行分析.利用同可区分度来刻画信息系统中属性的相对重要性,设计了一种基于信息论观点的启发式约简算法.该算法直接对原信息系统进行约简,不需要预处理,且对完备和不完备信息系统都适用,在保证较高约简率的同时使得信息论观点的约简算法在完备信息系统中的最坏时间复杂度降为O(│A│2│U│).最后用实例说明该算法的高效性.
From the point of knowledge classifications ability, the definition of common discernibility degree and the corresponding properties are introduced. By utilizing common discernibility degree to depict the relative importance of attribute in information system, a heuristic reduced algorithm based on information viewpoint is proposed and proved. It can be directly applied to both complete and incomplete information systems to reduce attributes without pretreatment. The approach ensures the relatively high reduction rate and simultaneously makesthe worst time complexity in complete information system fall to O（｜A｜2｜U｜） Finally, results of numerical experiments are used to illustrate the high efficiency of the algorithm in incomplete and complete information systems.
出处
《模式识别与人工智能》
EI
CSCD
北大核心
2010年第5期630-638,共9页
Pattern Recognition and Artificial Intelligence
关键词
粗糙集
不完备信息系统
约简
可区分关系
Rough Sets, Incomplete Information System, Reduction, Discernibility Relation
