Application of the Gabriel graph to instance based learning algorithms
Kaustav Mukherjee · Summit (Simon Fraser University) · 2004
Instance based learning (IBL) algorithms attempt to classify a new unseen instance (test data) based on some rule, i.e. by taking a majority vote among the class labels of its proximal instances in the training or reference dataset. The k nearest neighbours (k-NN) are commonly used as the proximal neighbours. We study the use of the state of the art approximate technique of k-NN search on the best known IBL algorithms. The results are impressive; substantial speed up in computation is achieved and on average the accuracy of classification is preserved. Geometric proximity graphs especially the Gabriel graph (a subgraph of the well known Delaunay triangulation) provides an elegant algorithmic alternative to k-NN based IBL algorithms. The main reason for this is that the Gabriel graph preserves the original nearest neighbour decision boundary between data points of different classes very well. However computing the Gabriel graph of a dataset in practice is prohibitively expensive. Extending the idea of approximate k-NN search to approximate Gabriel neighbours search, it becomes feasible to compute the latter. We thin (reduce) the original reference dataset by computing its approximate Gabriel graph and use it independently as a classifier as well as an input to the IBL algorithms. We achieve excellent empirical results; in terms of classification accuracy, reference set storage reduction and consequently, query response time. The Gabriel thinning algorithm coupled with the IBL algorithms consistently outperforms the IBL algorithms used alone, with respect to storage requirements and maintains similar accuracy levels.