Curvature-based adaptive k-NN outperforms fixed-k methods, especially with limited training data.
Local geometry informs neighborhood selection in kK-NN, enhancing robustness and generalization capabilities.
📚 https://arxiv.org/pdf/2409.05084
Original Problem 🔍:
The k-NN algorithm's performance depends heavily on choosing the right k value. Using a fixed k for all samples can lead to underfitting or overfitting in different regions of the feature space.
-----
Solution in this Paper 💡:
• Introduces kK-NN: adapts neighborhood size based on local curvature
• Estimates curvature using shape operator approximation
• Builds k-NNG with k=log2(n), computes curvature for each vertex
• Quantizes curvatures into 10 scores, prunes edges to adjust neighborhoods
• High curvature → smaller neighborhood, low curvature → larger neighborhood
-----
Key Insights from this Paper 💡:
• Adaptive k improves classification in regions with varying density
• Handles complex data patterns better than fixed-k approaches
• More robust to noise and outliers
• Performs well even with limited training data
-----
Results 📊:
• Outperformed regular k-NN and another adaptive k-NN on 19/30 datasets
• Superior balanced accuracy, especially with small training sets
• Example improvements:
- Vowel dataset: ~88% vs ~68% (adaptive k-NN) and ~53% (regular k-NN)
- Parkinsons dataset: ~94% vs ~76% (adaptive) and ~73% (regular)
Share this post