Partial Discernibility Matrices for Enumerating Relative Reducts of Large Datasets

Discernibility matrix is one of the basic tools for enumerating relative reducts of decision tables in rough sets, however it needs heavy computing load when dealing with large datasets. In this paper, we propose the partial discernibility matrix which has only elements with respect to the pairs of the objects indiscernible by the set of attributes. It is possible to obtain all or some of certain relative reducts from the partial discernibility matrix. Indeed, we can enumerate all minimal sets of attributes with the following two conditions: (1) It preserves the classification ability of all attributes. (2) It includes the set of attributes employed in the construction of the partial discernibility matrix. If the employed set of attributes consists of only core attributes, then all of relative reducts are directly enumerated. Moreover, if the employed set has only one attribute and we check whether this attribute is redundant in each of the derived sets, then we can obtain several relative reducts. The results of comparison experiments show that the partial discernibility matrix is effective when finding relative reducts of large datasets.