近邻成分分析 NCA 是什么？学习一个让 K 近邻分得更准的距离

近邻成分分析（Neighbourhood Components Analysis，NCA）是一种度量学习方法，由 Jacob Goldberger、Sam Roweis、Geoffrey Hinton 和 Ruslan Salakhutdinov 在 2004 年提出。它的目标是从数据中学习一种衡量样本之间距离的方式，让 K 近邻分类器在这种距离下分类得更准确。它也可以用来进行有监督的降维。

从 K 近邻说起

K 近邻是一种非常直观的分类方法：要判断一个新样本属于哪一类，就找出训练数据中离它最近的 K 个样本，看它们大多属于哪一类。这种方法的效果非常依赖于“距离”的定义。通常使用的是欧氏距离，也就是直线距离，它把所有的特征看得同等重要。但这在很多情况下并不合理：有些特征对分类很重要，有些特征几乎没有用，还有些特征是噪声；不同特征的单位和取值范围也可能相差很大。如果用欧氏距离，那些无关的特征可能会主导距离的计算，导致找到的“近邻”其实并不相似。

NCA 的想法

近邻成分分析不使用固定的距离，而是从带有标签的训练数据中学习一个线性变换：把数据变换到一个新的空间中，在这个新的空间里再计算欧氏距离。学习的目标是：在变换后的空间里，每个样本的近邻尽量都是同一类的样本。

直接优化 K 近邻的分类准确率很困难，因为“谁是最近的 K 个邻居”是一个离散的选择，稍微改变一下变换，近邻的集合可能突然改变，准确率是不连续的，无法求导。NCA 的巧妙之处在于用了一种“软”的近邻选择：每个样本不是确定地选择几个邻居，而是以一定的概率选择其他每一个样本作为它的邻居，距离越近，被选中的概率越大，这个概率用类似 softmax 的方式计算。然后，计算每个样本被它随机选中的邻居正确分类的概率，所有样本的这个概率之和就是期望的分类准确率。这个目标是连续、可导的，可以用梯度上升来优化，找到最好的线性变换。

它的用途

提升 K 近邻的效果：学到的变换会自动地放大对分类重要的特征方向，压缩无关的特征方向，使 K 近邻分类更加准确。有监督的降维和可视化：如果让学习的线性变换把数据映射到更低的维度，比如二维或三维，就得到了一种考虑了类别信息的降维方法。与主成分分析这种不考虑类别的降维方法不同，NCA 会尽量让不同类别的数据在低维空间中分开，同一类的数据聚在一起，便于可视化和后续的分类。scikit-learn 等机器学习库中提供了 NCA 的实现。

局限与发展

NCA 的计算需要考虑所有样本两两之间的关系，当数据量很大时，计算的开销很高；它的目标函数不是凸的，可能陷入局部最优；而且它学习的是线性变换，表达能力有限。在度量学习领域，类似的方法还有大间隔最近邻（LMNN）等。后来，研究者用深度神经网络代替线性变换，发展出了深度度量学习，比如使用对比损失、三元组损失训练的网络，被广泛用于人脸识别、图像检索和推荐系统中，其基本思想与 NCA 一脉相承：学习一个让相似的东西靠近、不相似的东西远离的表示空间。