The Problem of Finding the Simplest Classifier Ensemble is NP-Hard – A Rough-Set-Inspired Formulation Based on Decision Bireducts

We investigate decision bireducts which extend the notion of a decision reduct developed in the theory of rough sets. For a decision table [Formula: see text], a decision bireduct is a pair (X, B), where [Formula: see text] is a subset of attributes which allows to distinguish between all pairs of objects in [Formula: see text] labeled with different values of decision attribute d, and where B and X cannot be made, respectively, smaller and bigger without losing this property. We refer to our earlier studies on deriving bireducts (X, B) from decision tables and utilizing them to construct families of rule-based classifiers, where [Formula: see text] is equal to total support of decision rules built using attributes in [Formula: see text]. We introduce the notion of a correct ensemble of decision bireducts [Formula: see text], where each [Formula: see text] must be validly classified by more than [Formula: see text] of the corresponding models. We show that the problem of finding a correct ensemble of bireducts with the lowest cardinalities of subsets [Formula: see text] is NP-hard.