A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets

Efficient attribute reduction in large, incomplete decision systems is a challenging problem: existing approaches have time complexities no less than O(vertical bar C vertical bar(2)vertical bar U vertical bar(2)). This paper derives some important properties of incomplete information systems, then constructs a positive region-based algorithm to solve the attribute reduction problem with a time complexity no more than O(vertical bar C vertical bar(2)vertical bar U vertical bar log vertical bar U vertical bar). Furthermore, our approach does not change the size of the original incomplete system. Numerical experiments show that the proposed approach is indeed efficient, and therefore of practical value to many real-world problems. The proposed algorithm can be applied to both consistent and inconsistent incomplete decision systems. (c) 2009 Elsevier Inc. All rights reserved.