登录邻近成分分析是监督式学习算法中的一种。它主要是用来将多元数据进行分类。在功能上，它和K-临近（KNN）算法一致。
NCA是将马氏距离应用于KNN算法来实现降维的效果，它主要目的是通过找到一个线性变化矩阵，来最大化leave-one-out (LOO)分类精确度。算法的关键点在于可以通过可微的目标函数f(A)来找出线性变化矩阵A，比如说使用共轭梯度法。因此，NCA被普遍应用于模型的选择，降维，结构预测，异常分析，强化学习的神经网络中。
算法步骤：NCA首先将数据根据变换矩阵为Q=A'A转换，再计算出样本之间的距离（采用马氏距离）；马氏距离计算如下公式所示，其中A为一个线性变化矩阵，x为label数据，y为target数据。
因为距离是离散的，采用soft方式进行转化，计算出一个点和其余点是相同target的可能性pij。
该点与其余所有点相同可能性的和便是该点被正确分类的概率,pi。
最终的目标函数就是最大化所有点被正确分类的和,即是一个关于A的目标函数，如下图所示
有了目标函数后，对A进行求导，便可以求出被正确分类的最大可能性；因为函数f对于A来说是服从梯度下降的规则的，所以xij = xi − xj：
经过计算，整理后的结果：
在这里，第一，马氏距离（Mahalanobis distance）来计算样本之间的距离方法中的一种。第二，算法将离散的距离softmax化。
URL:https://en.wikipedia.org/wiki/Neighbourhood_components_analysis
发展历史
对于分类算法来说，KNN（ K-nearest neighbors algorithm）是一个非常经典的算法，最早之一的将KNN用于模式识别的算法的是Cover T, Hart P（1967年），计算距离的方式基本利用欧氏距离。因为欧式距离的计算很容易丢失样本中的信息，1993年Simard等人和2002年Belongie等人对KNN提出了新的计算距离的方法来对KNN进行优化。KNN简单并且适用于多目标结果的数据集。然而，KNN也是存在缺点的。
第一个计算量庞大，因为它为了分类一个点，他需要遍历训练集合的所有元素。第二个问题：距离矩阵该怎样定义才能更好体现‘近邻’这个概念。要知道，KNN分类的准确率在很大程度上是依赖于计算距离的方式上。由此distance metic learning 问题就这样被衍生出来了。所以， 2005年，Jacob Goldberger也是在KNN的基础上提出了新的计算距离的方式提出了NCA算法。NCA算法基于马氏距离的线性的变化矩阵不仅减小KNN的计算量庞大的问题，也用新的方式诠释了‘近邻’这个概念。除了Goldberger，同年，Shalev-Shwartz等人也提出了基于KNN的线性变化计算算法。这两位对于输入信息线性的变化的思想大大推动了KNN算法的发展。
然而，Domeniconi发现当训练集数目不够时，NCA会存在过拟合的问题；因此，Domeniconi基于支持向量机提出了一个局部自适应的矩阵来减少估计的偏差。随后，2007年，Salakhutdinov R等人认为NCA的这种线性变换无法对高阶原始数据各个维度的相关性进行建模。所以，提出了 Nonlinear NCA (NNCA) 非线性NCA算法来解决高阶数据问题。在2015年，Y Zheng等人认为无论是NCA 还是NNCA都无法捕捉到时序问题中数据的特性，所以，Y Zheng 等人提出的Convolutional Nonlinear Neighbourhood Components Analysis (CNNCA)卷积非线性NCA算法来解决时序问题中的分类问题。总体来说，NCA现在也被广泛用来解决降维问题，如2016年，Zhou H等人基于NCA和隐马尔科夫算法CHMM提出NCA-CHMM算法来解决故障识别的方法。
Tips: The leave-one-out (LOO)是一种交叉验证的方法。 举例，如样本数据集中有N个样本数据。将每个样本单独作为测试集（test_set），其余N-1个样本作为训练集（train_set），这样得到了N个分类器或模型，用这N个分类器或模型的分类准确率的平均数作为此分类器的性能指标。
主要事件
年份 | 事件 | 相关论文 |
1967 | Cover T, Hart P最早提出用于最近邻算法之一 | Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1), 21-27. |
1993 | Simard P基于KNN提出应用于模式识别的有效计算距离的计算方式 | Simard, P., LeCun, Y., & Denker, J. S. (1993). Efficient pattern recognition using a new transformation distance. In Advances in neural information processing systems (pp. 50-58). |
2003 | Xing E P提出基于应用的距离度量学习 | Bar-Hillel, A., Hertz, T., Shental, N., & Weinshall, D. (2003). Learning distance functions using equivalence relations. In Proceedings of the 20th International Conference on Machine Learning (ICML-03) (pp. 11-18). |
2005 | Jacob Goldberger基于KNN提出NCA算法 | Goldberger, J., Hinton, G. E., Roweis, S. T., & Salakhutdinov, R. R. (2005). Neighbourhood components analysis. In Advances in neural information processing systems (pp. 513-520). |
2007 | Salakhutdinov R提出NNCA非线性NCA算法 | Salakhutdinov, R., & Hinton, G. (2007, March). Learning a nonlinear embedding by preserving class neighbourhood structure. In Artificial Intelligence and Statistics (pp. 412-419). |
2016 | Zhou H等人基于NCA和隐马尔科夫算法CHMM提出NCA-CHMM算法来解决故障识别的方法 | Zhou H, Chen J, Dong G, et al. Bearing fault recognition method based on neighbourhood component analysis and coupled hidden Markov model[J]. Mechanical Systems and Signal Processing, 2016, 66: 568-581. |
发展分析
瓶颈
- 无法对高阶原始数据各个维度的相关性进行建模。
- NCA中提出的梯度算法不能保证局部极大值的收敛
- 当训练集数目不够时，NCA会趋向于过拟合。这种情况也经常出现在高维环境中。
- 无法捕捉到时序问题中的特性。
- 在NCA中，很有可能收敛于局部极小值
未来发展方向
- 在NCA中，很有可能收敛于局部极小值。在实践中，算法依赖于距离度量的初始值；所以可以对算法地初始化进行预处理。
- 可以结合神经网络来解决高阶数据源的问题。当然除此之外，要思考其他方法来解决高阶数据的问题。
- 可以结合隐马尔科夫算法来解决时序问题。
Contributor: Ruiying Cai
