A Minimum-Cost Feature-Selection Algorithm for Binary-Valued Features

An algorithm to select the minimum-cost collection of binary-valued features for use with a linear pattern classifier is presented. The feature-selection algorithm is motivated by the convex-hull representation of pattern-space separability. Combinatorial analysis and linear programming are used to find the minimum-cost collection of binary-valued features associated with a given set of preclassified patterns. A description of the interaction between these algorithm components is provided. The algorithm guarantees that its optimal feature set will correctly classify every pattern in the classifier's training sample. Coinputational considerations associated with algorithm use are discussed. An application of the algorithm to a three-feature classifier is presented in detail.