  Feature selection is popular for obtaining small, interpretable, yet highly
accurate prediction models. Conventional feature-selection methods typically
yield one feature set only, which might not suffice in some scenarios. For
example, users might be interested in finding alternative feature sets with
similar prediction quality, offering different explanations of the data. In
this article, we introduce alternative feature selection and formalize it as an
optimization problem. In particular, we define alternatives via constraints and
enable users to control the number and dissimilarity of alternatives. We
consider sequential as well as simultaneous search for alternatives. Next, we
discuss how to integrate conventional feature-selection methods as objectives.
In particular, we describe solver-based search methods to tackle the
optimization problem. Further, we analyze the complexity of this optimization
problem and prove NP-hardness. Additionally, we show that a constant-factor
approximation exists under certain conditions and propose corresponding
heuristic search methods. Finally, we evaluate alternative feature selection in
comprehensive experiments with 30 binary-classification datasets. We observe
that alternative feature sets may indeed have high prediction quality, and we
analyze factors influencing this outcome.
