On piece-wise linear classification

If two sets of vectors (in N-dimensional real Euclidean space [R.sup.N]) do not have an element in common, then they can always be separated from each other by using a series of N -- 1 dimensional hyperplanes in [R.sup.N]. In piecewise-linear classification, one finds such a series of hyperplanes using a training set containing elements from both classes. Efficient methods to find such a piecewise-linear separation for the training sets have been proposed in the literature. However, since complete separation of the training set fits the "noise" as well as the "signal" in the training set, the desirability of such a complete separation depends on the nature of the data. In this paper, we make use of a real data set (containing 9-D measurements of fine needle aspirates of a patient's breast for the purpose of classifying a tumor's malignancy) for which early stopping in the generation of the separating hyperplanes is not appropriate. We compare a piecewise-linear classification method (both with complete separation on the training set and with separation using only seven hyperplanes) with classification based on a single (but in a statistical sense optimal) linear separator. A precise methodology for comparing the relative efficacy of two classification methods for a particular task (including a way of providing the statistical significance of the results) is described and is applied to the comparison on the breast cancer data of the relative performances of the two versions of the piecewise-linear classifier and the classification based on an optimal linear separator. It is found that for this data set, the piecewise-linear classifier that uses all the hyperplanes needed to separate the training set outperforms the other two methods and that these differences in performance are significant at the 0.001 level. There is no statistically significant difference between the performance of the other two methods. We discuss the relevance of these results for this and other applications. Index Terms--Malignancy detection, medical diagnosis, optimal linear separation, pattern recognition, performance evaluation, piecewise-linear classification.