Feature selection via set cover

Abstract

In pattern classification, features are used to define classes. Feature selection is a preprocessing process that searches for an `optimal' subset of features. The class separability is normally used as the basic feature selection criterion. Instead of maximizing the class separability as in the literature, this work adopts a criterion aiming to maintain the discriminating power of the data describing its classes. In other words, the problem is formalized as that of finding the smallest set of features that is `consistent' in describing classes. We describe a multivariate measure of feature consistency. The new feature selection algorithm is based on Johnson's algorithm for Set Cover. Johnson's analysis implies that this algorithm runs in polynomial time, and outputs a consistent feature set whose size is within a log factor of the best possible. Our experiments show that its performance in practice is much better than this, and that it outperforms earlier methods using a similar amount of time.