邻里成分分析

✍ dations ◷ 2025-09-14 03:40:27 #多变量统计,资料分析,统计模型

邻里成分分析(Neighborhood components analysis,NCA)是一种监督式学习的方法,根据一种给定的距离度量算法对样本数据进行度量,然后对多元变量数据进行分类。在功能上其和k近邻算法的目的相同,直接利用随即近邻的概念确定与测试样本临近的有标签的训练样本。

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

为了定义转换矩阵A,我们首先定义一个在新的转换矩阵中表示分类准确率的目标函数,并且尝试确定A*使得这个目标函数最大化。

A = argmax A f ( A ) {\displaystyle A^{*}={\mbox{argmax}}_{A}f(A)}

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

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

p i j = { e | | A x i A x j | | 2 k e | | A x i A x k | | 2 , if j i 0 , if j = i {\displaystyle p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if}}j\neq i\\0,&{\mbox{if}}j=i\end{cases}}}

输入点 i {\displaystyle i} 的分类准确率是与其相邻的最近邻居集 C i {\displaystyle C_{i}} 的分类准确率: p i = j n p i j {\displaystyle p_{i}=\sum _{j}^{n}p_{ij}\quad } 其中 p i j {\displaystyle p_{ij}} j {\displaystyle j} i {\displaystyle i} 的最近邻居的概率。定义用全局数据集作为随机最近邻的留一分类方法确定的目标函数如下:

f ( A ) = i j C i p i j = i p i {\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}}

由随机近邻理论知,与单一样本点 C i {\displaystyle C_{i}} 的同类别的在随机近邻域 C i {\displaystyle C_{i}} 样本点 j {\displaystyle j} 可以表示为:

P ( C l a s s ( X i ) = C l a s s ( X j ) ) = p i j {\displaystyle P(Class(X_{i})=Class(X_{j}))=p_{ij}} 。因此,单一样本点 i {\displaystyle i} 的预测类别是随机近邻集中其他样本类别的某种组合,其准确率与随机近邻域 C i {\displaystyle C_{i}} 中与 i {\displaystyle i} 同类别的 y {\displaystyle y} 所占的比例有关。因此,目标函数可以更好的选为:

f A = 2 A i j C i p i j ( x i j x i j T k p i k x i k x i k T ) {\displaystyle {\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)}

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

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

g ( A ) = i log ( j C i p i j ) = i log ( p i ) {\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})}

g A = 2 A i ( k p i k x i k x i k T j C i p i j x i j x i j T j C i p i j ) {\displaystyle {\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)}

在实际应用中运用此方法得到优化的 A {\displaystyle A} 与之前的方法得到的 A {\displaystyle A} 有相似的预测结果。

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

相关

  • 功能余气量功能余气量(英语:FRC, Functional Residual Capacity)是指平静呼气之后肺中残余气体的容积。功能余气量反映了缓冲呼吸过程中肺泡中氧气和二氧化碳分压的过度变化。由于功能余
  • 过渡体衬线体(Serif)是一种有衬线的字体,又称为有衬线体、衬线字、曲线描边字,俗称白体字;而与之相对的,没有衬线的字体则被称为无衬线体。衬线是字形笔画末端的装饰细节部分。一般认为
  • 安妮·班克罗夫特安妮·班克罗夫特(英语:Anne Bancroft,1931年9月17日-2005年6月6日),生于美国纽约,美国著名女演员,其作品《毕业生》蜚声世界影坛,1962年奥斯卡最佳女主角奖得主。1931年,班克罗夫特出
  • 徐州 (三国至明朝)徐州,中国古代的州,前身为监察区徐州刺史部。早期幅员广袤,包括今江苏省长江以北、山东省西南部和安徽省小部,南北朝时期辖境逐渐缩小,北朝后期以后辖境仅限于今江苏省徐州市一带
  • 三叉神经运动核三叉神经运动核是位于脑桥的一个神经核团,它包含三叉神经的第一腮弓的支配肌肉的运动神经元的细胞体。这些受支配的骨骼肌是与咀嚼功能相关的肌肉,包括鼓膜张肌,颚帆张肌,下颌舌
  • 1996年至1997年意大利足球甲级联赛 1996年至1997年意大利足球甲级联赛冠军是马尔切洛·里皮执掌的尤文图斯, 这是斑马军团的第24次夺得意大利顶级联赛冠军。卡利亚里降入1997年至1998年意大利足球乙级联
  • 成膜粒成膜粒存在于高等液泡植物细胞,主要功用为帮助有丝分裂。有别于动物细胞,植物细胞通常有大体积的液泡,以致细胞核被推至细胞的边缘。为了有丝分裂,细胞核必须挪至细胞中央。这发
  • 玉堂街道玉堂镇,是中华人民共和国四川省成都市都江堰市下辖的一个乡镇级行政单位。2019年12月,撤销中兴镇、玉堂镇,设立玉堂街道,以原中兴镇和原玉堂镇所属行政区域为玉堂街道的行政区域
  • 波格拉尼奇内波格拉尼奇内(俄语:Пограничный)为俄罗斯远东联邦管区滨海边疆区波格拉尼奇内区境内的一座市级镇,也是波格拉尼奇内区的行政中心。位在中俄边界东方15公里、海参崴西
  • 沙瓦尔什·弗拉基米罗维奇·卡拉佩特延沙瓦尔什·弗拉基米罗维奇·卡拉佩特延(亚美尼亚语:Շավարշ Կարապետյան,1953年5月19日出生于瓦纳佐尔)是一名已退役原苏联亚美尼亚蹼泳运动员,11次世界纪录保持者