提出自适应kNN图模型,让分类又快又准。
Adaptive $k$NN graph model
- 用HNSW图结构分离计算负担,训练时预算邻居
- 六数据集测试,推理速度达实时,精度不降
- 适合需要快速高精度分类的大型应用
k近邻(kNN)算法是人工智能中非参数分类的基石,但在大规模应用中受限于推理速度与精度之间的计算权衡。现有近似最近邻方法虽加速检索,但常降低分类精度,且无法自适应选择最优邻域大小(k)。本文提出一种自适应图模型,将推理延迟与计算复杂度解耦。通过结合分层可导航小世界(HNSW)图与预计算投票机制,框架将邻居选择与加权的计算负担完全转移至训练阶段。该拓扑结构中,高层实现快速导航,低层编码精确、节点特异的决策边界,支持自适应邻居数量。在六个不同数据集上对比八种先进基线,结果表明该架构显著提升推理速度,实现实时性能,且不牺牲分类精度。研究为kNN的固有推理瓶颈提供了可扩展、鲁棒的解决方案,奠定了基于图的非参数学习的自适应结构基础。
原文摘要 · Abstract (English)
The $k$-nearest neighbors ($k$NN) algorithm is a cornerstone of non-parametric classification in artificial intelligence, yet its deployment in large-scale applications is persistently constrained by the computational trade-off between inference speed and accuracy. Existing approximate nearest neighbor solutions accelerate retrieval but often degrade classification precision and lack adaptability in selecting the optimal neighborhood size ($k$). Here, we present an adaptive graph model that decouples inference latency from computational complexity. By integrating a Hierarchical Navigable Small World (HNSW) graph with a pre-computed voting mechanism, our framework completely transfers the computational burden of neighbor selection and weighting to the training phase. Within this topological structure, higher graph layers enable rapid navigation, while lower layers encode precise, node-specific decision boundaries with adaptive neighbor counts. Benchmarking against eight state-of-the-art baselines across six diverse datasets, we demonstrate that this architecture significantly accelerates inference speeds, achieving real-time performance, without compromising classification accuracy. These findings offer a scalable, robust solution to the inherent inference bottleneck of $k$NN, laying an adaptive structural foundation for graph-based nonparametric learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。