Decision bireducts and decision reducts - a comparison

In this paper we revise the notion of decision bireducts. We show new interpretations and we prove several important and practically useful facts regarding this notion. We also explain the way in which some of the well-known algorithms for computation of decision reducts can be modified for the purpose of computing decision bireducts. For the sake of completeness of our study we extend our investigations to relations between decision bireducts and so-called approximate decision reducts. We compare different formulations of those two approaches and draw analogies between them. We also report new results related to NP-hardness of searching for optimal decision bireducts and approximate decision reducts from data. Finally, we present new results of empirical tests which demonstrate usefulness of decision bireducts in a construction of efficient, yet simple ensembles of classification models.