PIECEWISE-LINEAR CLASSIFIERS USING BINARY-TREE STRUCTURE AND GENETIC ALGORITHM

A linear decision binary tree structure is proposed in constructing pi ecewise linear classifiers with the Genetic Algorithm (GA) being shape d and employed at each nonterminal node in order to search for a linea r decision function, optimal in the sense of maximum impurity reductio n. The methodology works for both the two-class and multi-class cases. In comparison to several other well-known methods, the proposed Binar y Tree-Genetic Algorithm (BTGA) is demonstrated to produce a much lowe r cross validation misclassification rate. Finally, a modified BTGA is applied to the important pap smear cell classification. This results in a spectrum for the combination of the highest desirable sensitivity along with the lowest possible false alarm rate ranging from 27.34% s ensitivity, 0.62% false alarm rate to 97.02% sensitivity, 50.24% false alarm rate from resubstitution validation. The multiple choices offer ed by the spectrum for the sensitivity-false alarm rate combination wi ll provide the flexibility needed for the pap smear slide classificati on. Copyright (C) 1996 Pattern Recognition Society.