An Efficient Algorithm for Computing Core Based on Positive Region

摘要

How to find the core is important for attribute reduction based on rough set. To reduce the computational complexity, simplified decision table is introduced at first. For computing simplified decision table, IND(C) should usually be calculated at first, so based on radix sorting, a new algorithm for computing IND(C) with time complexity O (|C‖U|) is designed. On the other hand, to reduce the space complexity, a new algorithm for computing POS_C(D) is also proposed. Then based on the above definition and algorithms, a new algorithm for computing core is presented, whose time complexity is max(O(|C‖U|,O(|C|~2|U/C|)). Finally, an example is used for illustrating the proposed algorithms.