Using Pairs of Data-Points to Define Splits for Decision Trees

Part of Advances in Neural Information Processing Systems 8 (NIPS 1995)

Bibtex Metadata Paper


Geoffrey E. Hinton, Michael Revow


Conventional binary classification trees such as CART either split the data using axis-aligned hyperplanes or they perform a compu(cid:173) tationally expensive search in the continuous space of hyperplanes with unrestricted orientations. We show that the limitations of the former can be overcome without resorting to the latter. For every pair of training data-points, there is one hyperplane that is orthog(cid:173) onal to the line joining the data-points and bisects this line. Such hyperplanes are plausible candidates for splits. In a comparison on a suite of 12 datasets we found that this method of generating candidate splits outperformed the standard methods, particularly when the training sets were small.