Automated design of multiple-class piecewise linear classifiers

A new method and a supporting theorem for designing multiple-class piecewise linear classifiers are described. The method involves the cutting of straight line segments joining pairs of opposed points (i.e., points from distinct classes) ind-dimensional space. We refer to such straight line segments aslinks. We show how nearly to minimize the number of hyperplanes required to cut all of these links, thereby yielding a near-Bayes-optimal decision surface regardless of the number of classes, and we describe the underlying theory. This method does not require parameters to be specified by users — an improvement over earlier methods. Experiments on multiple-class data obtained from ship images show that classifiers designed by this method yield approximately the same error rate as the bestk-nearest neighbor rule, while providing faster decisions.This research was supported in part by the Army Research Office under grant DAAG29-84-K-0208 and in part by the University of California MICRO Program. We thank R. W. Doucette of the U.S. Naval Weapons Center and R. D. Holben of Ford Aerospace Corporation for providing the ship images in our experiments.