The labelled cell classifier: a fast approximation to k nearest neighbors

A k-nearest-neighbor classifier is approximated by a labeled cell classifier that recursively labels the nodes of a hierarchically organized reference sample (e.g., a k-d tree) if a local estimate of the conditional Bayes risk is sufficiently small. Simulations suggest that the labeled cell classifier is significantly faster than k-d tree implementations for problems with small Bayes risk, and may be more accurate as a larger reference sample can be examined in a fixed amount of time.