title: Fast k-nearest neighbor classification using cluster-based trees.
abstract: Most fast k-nearest neighbor (k-NN) algorithms exploit metric properties of distance measures for reducing computation cost and a few can work effectively on both metric and nonmetric measures. We propose a cluster-based tree algorithm to accelerate k-NN classification without any presuppositions about the metric form and properties of a dissimilarity measure. A mechanism of early decision making and minimal side-operations for choosing searching paths largely contribute to the efficiency of the algorithm. The algorithm is evaluated through extensive experiments over standard NIST and MNIST databases.
authors.affiliation: Departments of Human Genetics and Biostatistics, School of Medicine, UCLA, Los Angeles, CA 90095-7088, USA. binzhang@mednet.ucla.edu
authors.forename: Bin
authors.initials: B
authors.lastname: Zhang
authors.forename: Sargur N
authors.initials: SN
authors.lastname: Srihari
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003196:Computer Graphics; D003198:Computer Simulation; D016208:Databases, Factual; D006236:Handwriting; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted; D013382:Subtraction Technique