Stochastic Neighbor Compression

We present Stochastic Neighbor Compression (SNC), an algorithm to compress a dataset for the purpose of k-nearest neighbor (kNN) clas-sification. Given training data, SNC learns a much smaller synthetic data set, that minimizes the stochastic 1-nearest neighbor classification error on the training data. This approach has sev-eral appealing properties: due to its small size, the compressed set speeds up kNN testing dras-tically (up to several orders of magnitude, in our experiments); it makes the kNN classifier sub-stantially more robust to label noise; on 4 of 7 data sets it yields lower test error than kNN on the entire training set, even at compression ra-tios as low as 2%; finally, the SNC compression leads to impressive speed ups over kNN even when kNN and SNC are both used with ball-tree data structures, hashing, and LMNN dimension-ality reduction—demonstrating that it is comple-mentary to existing state-of-the-art algorithms to speed up kNN classification and leads to substan-tial further improvements. 1