RCC-MAS: A New Algorithm for Computing All Rough-Set-Constructs

Abstract

In rough set theory, a construct is defined as a subset of attributes possessing the same capacity as the complete set of attributes to discern objects from different classes, while preserving similarity between objects from the same class. In the literature, it has been shown that algorithms designed for computing reducts or typical testors can be modified to calculate constructs. However, in practice, there are scenarios where even the fastest algorithms in the current state-of-the-art struggle to compute all constructs within a reasonable time-frame. This paper presents a novel algorithm to compute all constructs within a decision table to reduce this gap. Our proposed algorithm, RCC-MAS , works on the binary discernibility-similarity matrix and employs a recursive approach to reduce the search space systematically by analyzing minimum attribute subsets whose attributes, when excluded, lead to rows with zeros in those attributes in the matrix, violating the construct definition. This strategy reduces the number of subsets generated, focusing on attributes essential for constructs; additionally, we demonstrate theoretically that all constructs are computed. Experimental evaluations spanning several synthetic and real-world decision tables reveal that RCC-MAS is the best option to compute constructs regardless of the density of the SBDSM .