摘要： 原属性约简算法在计算相容关系时，存在大量重复计算，从而导致时间复杂度为O(|C|3|U|2)。针对该问题，基于不完备决策表，提出时间复杂度为O(|U|2)的高效相容矩阵计算算法，在此基础上，设计改进的基于相容矩阵的属性约简算法。通过实例证明，当空间复杂度相同时，改进算法的时间复杂度从原有O(|C|3|U|2)降为O(|C|2|U|2)。

关键词: 粗糙集, 属性约简, 相容关系矩阵, 不完备决策表

Abstract: When original attribute reduction algorithm calculates tolerance relation, there is much repeatedly calculating consumption. And this leads to O(|C|3|U|2) time complexity. Aiming at this problem, based on incomplete decision table, this paper presents a high efficient tolerance matrix computational algorithm whose time complexity is O(|U|2). On that basis, it designs an improved attribute reduction algorithm based on tolerance matrix. Test proves that the time complexity of improved algorithm is reduced from O(|C|3|U|2) to O(|C|2|U|2) with the same space complexity.

Key words: Rough Set(RS), attribute reduction, tolerance relation matrix, incomplete decision table

中图分类号: 

• TP18

• TP393