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.