An Efficient Technique for Calculating Exact Nearest-Neighbor Classification Accuracy
Matthew D. Mullin, Rahul Sukthankar · 1999
We present a technique for calculating exact nearest-neighbor classification accuracy. This is equivalent to averaging the results of an exponential number of trials (all test/train splits), yet it can be performed very efficiently. The technique is applied to each of four common classification experiment types. Complexity analysis and empirical results demonstrate the superiority of this algorithm over the customary approach of estimating accuracy by averaging several randomized test/train splits. This algorithm offers significant practical benefits to researchers in terms of vastly reduced computation time. 1 Introduction In machine learning experiments, a pool of labeled data, S, is typically split into a training set, T , and a test set S nT . 1 Items from the test set are presented to a classifier trained on T , and the empirical accuracy (fraction of test items classified correctly) is reported as the performance of the classifier. Given that the accuracy observed in such an e...