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 \(\mathbb {A}=(U,A\cup \{d\})\), a decision bireduct is a pair (X, B), where \(B\subseteq A\) is a subset of attributes which allows to distinguish between all pairs of objects in \(X\subseteq U\) 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 \(X\subseteq U\) is equal to total support of decision rules built using attributes in \(B\subseteq A\). We introduce the notion of a correct ensemble of decision bireducts \((X_1,B_1),...,(X_m,B_m)\), where each \(u\in U\) must be validly classified by more than \(50\%\) of the corresponding models. We show that the problem of finding a correct ensemble of bireducts with the lowest cardinalities of subsets \(B_i\subseteq A\) is NP-hard.