Fast 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 character images suggest that the accuracy of the tree classifier designed by this scheme is comparable to those of the k-NN classifiers and the tree classifier of J.K. Mui and K.S. Fu (1980), while providing much greater decision speeds, and that the tradeoff 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