查看“︁邻里成分分析”︁的源代码

'''邻里成分分析（{{lang|en|Neighborhood components analysis，NCA}}）'''是一种[[监督式学习]]的方法，根据一种给定的距离度量算法对样本数据进行[[度量]]，然后对[[多元变量统计|多元变量]]数据进行[[分类问题|分类]]。在功能上其和[[k近邻算法]]的目的相同，直接利用随即近邻的概念确定与测试样本临近的有标签的训练样本。<ref>J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov. (2005) ''[http://www.csri.utoronto.ca/~roweis/papers/ncanips.pdf Neighbourhood Component Analysis] {{Wayback|url=http://www.csri.utoronto.ca/~roweis/papers/ncanips.pdf |date=20050223212335 }}.'' Advances in Neural Information Processing Systems. 17, 513-520.</ref>

== 定义 ==
邻里成分分析是一种[[距离]][[度量]]学习方法，其目的在于通过在训练集上学习得到一个[[线性空间]][[转移矩阵]]，在新的转换空间中最大化平均留一（LOO）分类效果。该算法的关键是与空间转换矩阵相关的的一个正定矩阵A，该矩阵A可以通过定义A的一个可微的目标函数并利用迭代法（如共轭梯度法、共轭梯度下降法等）求解得到。该算法的好处之一是类别数K可以用一个函数f（确定标量常数）来定义。因此该算法可以用来解决模型选择的问题。

== 解释说明 ==
为了定义转换矩阵A，我们首先定义一个在新的转换矩阵中表示分类准确率的目标函数，并且尝试确定A<sup>*</sup>使得这个目标函数最大化。

<math>A^* = \mbox{argmax}_A f(A)</math>

=== 留一分类 ===
对一个单一的数据点进行类别预测时，我们需要考虑有一种给定的距离度量确定的K个最近邻居，根据<math>k</math>个近邻的类别标签投票得到该样本的类别。这就是留一（Loo）分类算法。但是对所有数据集进行一个线性空间变换之后，新空间中的同一样本的最近邻居集可能跟原空间的最近邻居集有很大差别。特别的，为了平滑<math>A</math>中元素的变化，我们可以使该样本的最近邻居集离散化，也就是说任意一个基于一个点的最近邻居集的目标函数f都是离散的，因此也是不连续的。

=== 解决方法 ===
我们可以用一种受随机梯度下降法算法的启示得到的方法解决该问题。在新的转换空间中，我们并不是对每个样本点用留一分类方法求取<math>k</math>个最近邻居，而是在新空间中考虑整个数据集作为随机最近邻居。我们用一个平方欧氏距离函数来定义在新的转换空间中的留一数据点与其他数据的距离，该函数定义如下：

<math>p_{ij} =
\begin{cases}
 \frac{e^{-||Ax_i - Ax_j||^2}}{\sum_k e^{-||Ax_i - Ax_k||^2}}, & \mbox{if} j \ne i \\
 0, & \mbox{if} j = i
\end{cases}
</math>

输入点<math>i</math>的分类准确率是与其相邻的最近邻居集<math>C_i</math>的分类准确率：
<math>p_i = \sum_j^n p_{ij} \quad </math> 其中<math>p_{ij}</math>是<math>j</math>是<math>i</math>的最近邻居的概率。
定义用全局数据集作为随机最近邻的留一分类方法确定的目标函数如下：

<math>f(A) = \sum_i \sum_{j \in C_i} p_{ij} = \sum_i p_i</math>

由随机近邻理论知，与单一样本点<math>C_i</math>的同类别的在随机近邻域<math>C_i</math>样本点<math>j</math>可以表示为：

<math>P(Class(X_i) = Class(X_j)) = p_{ij}</math>。因此，单一样本点<math>i</math>的预测类别是随机近邻集中其他样本类别的某种组合，其准确率与随机近邻域<math>C_i</math>中与<math>i</math>同类别的<math>y</math>所占的比例有关。
因此，目标函数可以更好的选为：

<math>
\frac{\partial f}{\partial A} = - 2A \sum_i \sum_{j \in C_i} p_{ij} \left ( x_{ij} x_{ij}^T - \sum_k p_{ik} x_{ik} x_{ik}^T \right )
</math>

这里用到了连续梯度下降算法。

=== 目标函数优化 ===
最大化函数f（.）相当于最小化预测的类分布和真正的类分布之间的差距，即使两者更接近。故目标函数和梯度可以重新写作：

<math>
g(A) = \sum_i \log \left ( \sum_{j \in C_i} p_{ij} \right ) = \sum_i \log (p_i)
</math>

<math>
\frac{\partial g}{\partial A} = 2A \sum_i \left ( \sum_k p_{ik} x_{ik} x_{ik}^T - \frac{\sum_{j \in C_i} p_{ij} x_{ij} x_{ij}^T }{\sum_{j \in C_i} p_{ij}} \right )
</math>

在实际应用中运用此方法得到优化的<math>A</math>与之前的方法得到的<math>A</math>有相似的预测结果。

== 历史和背景 ==
邻里成分分析是由Jacob Goldberger, Sam Roweis, Ruslan Salakhudinov和Geoff Hinton 等人在2004年在多伦多大学计算机系创建的。

== 相关研究和理论 ==
*[[聚类分析]]
*[[K-Nearest Neighbours|K-近邻算法]]
*[[谱聚类]]

== 参考文献 ==
{{Reflist}}

== 外部链接 ==
* [http://www.cs.toronto.edu/~hinton/absps/nca.pdf Neighbourhood Components Analysis] {{Wayback|url=http://www.cs.toronto.edu/~hinton/absps/nca.pdf |date=20120219175803 }} (University of Toronto DCS)
* [http://github.com/vomjom/nca nca] {{Wayback|url=http://github.com/vomjom/nca |date=20100401170210 }} ([[C++]])

[[Category:多變量統計]]
[[Category:資料分析]]
[[Category:统计模型]]