Related Experiment Videos
Fast k-nearest neighbor classification using cluster-based trees
1Departments of Human Genetics and Biostatistics, School of Medicine, UCLA, Los Angeles, CA 90095-7088, USA. binzhang@mednet.ucla.edu
IEEE Transactions on Pattern Analysis and Machine Intelligence
|September 24, 2004
Summary
We developed a novel cluster-based tree algorithm to speed up k-nearest neighbor (k-NN) classification. This method efficiently handles various distance measures without assuming metric properties, improving classification performance.
Area of Science:
- Computer Science
- Machine Learning
- Data Mining
Background:
- Fast k-nearest neighbor (k-NN) algorithms often rely on metric properties of distance measures for efficiency.
- Existing methods have limitations in handling nonmetric measures or require specific distance properties.
Purpose of the Study:
- To propose a novel cluster-based tree algorithm for accelerating k-NN classification.
- To develop a method that works effectively with both metric and nonmetric distance measures without prior assumptions.
Main Methods:
- A cluster-based tree structure is employed to organize data.
- Early decision-making mechanisms and optimized path searching are integrated for efficiency.
- The algorithm is designed to be independent of the metric form of the dissimilarity measure.
Main Results:
- The proposed algorithm significantly accelerates k-NN classification.
- Experimental results on NIST and MNIST databases demonstrate the algorithm's effectiveness.
- The method shows efficiency gains without presupposing metric properties.
Conclusions:
- The cluster-based tree algorithm offers an efficient approach for k-NN classification.
- This method provides a flexible solution for diverse distance measures in k-NN.
- The algorithm's performance is validated on benchmark datasets.