基于图学习视角优化 $k$NN 图中的 $k$ 值
内容提要
本文综述基于邻域图的聚类与kNN方法研究，涵盖随机邻域图的最优聚类及参数k选择、含噪环境下识别聚类的概率证明、自适应选择k的改进kNN分类器及收敛界、融合分布信息的偏好附加k近邻图（paNNG）、kNN子图对簇树的一致估计及首个有限样本剪枝结果，以及非局部KNN松弛、局部加权回归、近似谱聚类、图学习算法和自适应核图神经网络。
延伸解读
k值选择：从固定参数到自适应决策
文章梳理的多项工作表明，kNN图中的k值并非固定不变最优。2019年的改进分类器为每个查询自适应选择k，且不同点之间可能显著变化；2023年的paNNG结合自适应kNN与分布信息，提升模糊样本表现。这提示读者：在实际任务中，固定k可能掩盖局部数据密度差异，自适应策略更值得关注。
图构建与聚类一致性的理论进展
文章提到，通过统计分析揭示了k-NN图的某些子图可构成底层点分布簇树的一致估计量，并给出首个有限样本剪枝结果。这意味着邻域图不仅是启发式工具，其聚类结构在理论上可获得一致性保证。读者可留意：图构建方式与剪枝策略共同决定能否删除虚假簇并恢复显著簇。
效率与表达能力的权衡
文章涵盖近似谱聚类、线性对数复杂度图学习以及自适应核图神经网络等工作。前者通过精简边界提升计算效率，后者用数据驱动核学习解决预定义核泛化问题。这些方向说明，kNN图相关方法正试图在计算成本与模型表达能力之间寻找平衡，读者评估方法时可同时关注复杂度与泛化表现。
Q&A
在基于邻域图的聚类中，如何确定最优的邻域图类型和参数k？
文章探讨了构建何种邻域图以获得最优聚类结果，以及如何选择邻域图和最优参数k的问题，并利用随机几何图理论技术证明在无噪声或嘈杂设置中成功识别聚类的概率。
改进的kNN分类器如何为每个查询自适应选择K值？
该分类器根据每个邻域的属性自适应地为每个查询选择K值，因此K值可能在不同点之间显著变化，并且可以利用条件概率推导出一些收敛界限。
paNNG是什么，它解决了传统kNN图的什么问题？
paNNG是偏好附加k-最近邻图，结合了自适应kNN和基于分布的图构建。它通过融合分布信息，大幅提高模糊样本的性能，将其拉回原始类别，从而提高整体准确性和泛化能力，并在多种基准数据集上胜过最先进算法。
k-NN图的子图如何用于估计聚类树？
通过统计分析，揭示了k-NN图的某些子图可以构成底层点分布簇树的一致估计量，并通过慎重选择聚类树的剪枝方式，同时保证删除虚假簇结构并恢复显著簇，得到了聚类领域首个有限样本结果。
非局部KNN松弛方法是如何工作的？
该方法利用自然信号的自相似性，提出对KNN选择规则进行连续确定性松弛，通过温度参数逐渐接近零将原始KNN保持为极限，并利用神经最近邻块（N3块）用于现代神经网络架构，在图像恢复等任务中展示了有效性。
AKGNN框架如何解决预定义核的泛化问题？
AKGNN是一种新型自适应核图神经网络框架，通过设计数据驱动的图内核学习机制来解决预定义核对于不同图之间的泛化问题，同时通过参数化技巧和全局输出函数增强表达能力，在基准数据集上展示了优异性能。
