A Piecewise Linear Classifier

Abstract

A piecewise linear network is discussed which classifies N-dimensional input vectors. The network uses a distance measure to assign incoming input vectors to an appropriate cluster. Each cluster has a linear classifier for generating class discriminants. A training algorithm is described for generating the clusters and discriminants. A pruning algorithm is also described. The algorithm is applied after the network has grown completely, i.e, it has achieved the maximum number of clusters. The pruning algorithm eliminates the least important clusters, one at a time, leading to a more compact network. Theorems are given which relate the network's performance to that of nearest neighbor and k-nearest neighbor classifiers. It is shown that the error approaches Bayes Error as the number of clusters and patterns per cluster approach infinity. The mathematical complexity of the piecewise linear network classifier, in terms of number of multiplies, is compared against those of classical neural net classifiers, like the multi-layer perceptron and the nearest neighbor classifier. The classifier is also compared with these classifiers with respect to their sizes, i.e, number of clusters or hidden units. It is shown that the piecewise linear network classifier generally outperforms on both fronts.