Automated design of linear tree classifiers

摘要

An automated method is presented for the design of linear tree classifiers, i.e. tree classifiers in which a decision based on a linear sum of features is carried out at each node. The method exploits the discriminability of Tomek links joining opposed pairs of data points in multidimensional feature space to produce a hierarchically structured piecewise linear decision function. The corresponding decision surface is optimized by a gradient descent that maximizes the number of Tomek links cut by each linear segment of the decision surface, followed by training each node's linear decision segment on the data associated with that node. Experiments on real data obtained from ship images and character images suggest that the accuracy of the tree classifier designed by this scheme is comparable to that of the k-NN classifier while providing much greater decision speeds, and that the trade-off between the speed and the accuracy in pattern classification can be controlled by bounding the number of features to be used at each node of the tree. Further experiments comparing the classification errors of our tree classifier with the tree classifier produced by the Mui/Fu technique indicate that our tree classifier is no less accurate and often much faster than the Mui/Fu classifier.