文摘

特性非常重要,对于许多应用程序在生物医学信号分析和系统分析。快速区别的随机邻居嵌入分析(FDSNE)特征提取方法本文提出了通过改善现有DSNE方法。该算法采用一种基于其构造概率分布模型最近的邻居的组间和组内样本。此外,FDSNE扩展到非线性场景使用内核的技巧,然后基于内核的方法,也就是说,KFDSNE1 KFDSNE2。FDSNE、KFDSNE1 KFDSNE2评估在三个方面:可视化、识别、和运行时间。几个数据集上实验结果表明,与DSNE MSNP相比,该算法不仅大大提高了计算效率,而且还可以获得更高的分类精度。

1。介绍

近年来,空间减少,可以减少维数的诅咒(1在高维空间)和删除不相关的属性在许多领域中发挥着越来越重要的作用。它促进了分类、可视化和高维度数据的压缩。在机器学习中,降维用于维度降低样本高维空间映射到低维空间。有很多学习的目的:首先,减少的存储量,其次,去除噪声的影响,第三,理解数据分布,和最后但并非最不重要的,能达到良好的结果在分类或聚类。

目前,许多提出了降维方法,它们可以从不同的角度分类不同。根据输入数据的性质,它们大致分为两类:线性子空间方法,试图找到一个线性子空间的特征空间,以保持某种特征的观测数据,和非线性方法如基于技术和几何投影技术;从类标签的角度来看,他们分为监督学习和非监督学习;此外,前者的目的是最大化类之间的识别率,而后者是为了使信息损失最小。此外,判断样本是否利用局部信息或全局信息,我们把它们分成局部方法和全局方法。

我们简要地介绍几个现有的降维技术。在主线性技术,主成分分析(PCA) (2)旨在最大化方差样本的低维线性映射矩阵表示。它是全球性的监督和管理。不同于主成分分析,线性判别分析(LDA) (3)学习线性投影的协助下类标签。它计算线性变换通过最大化的组内的差异相对于组合方差的数量。基于LDA, fisher边际分析(MFA) (4),当地fisher判别分析(LFDA) [5),和极大极小距离分析(MMDA) [6提出了]。这三个都是线性监督降维方法。MFA利用内在图来描述同类密实度,并使用与此同时惩罚图描述组内的可分性。LFDA介绍了最小的致命剂量算法和位置是特别有用的样本组内单独的集群组成。MMDA考虑最大化最小两两组内的样品。

处理非线性结构数据,可以发现在生物医学的应用7- - - - - -10),大量的非线性降维方法已经开发出来。其中基于技术和几何投影技术是两个热点问题。基于技术试图获得非线性分布式数据的线性结构由原来的输入映射到一个高维特征空间。例如,核主成分分析(PCA)内核(11)是主成分分析的扩展使用内核的技巧。几何投影技术,一般来说,被称为流形学习技术,如等距映射(ISOMAP) [12),局部线性嵌入(米歇尔)[13),拉普拉斯算子eigenmap (LE) [14),黑森米歇尔(HLLE) [15),和局部切空间排列(LTSA) [16]。ISOMAP用于计算两两测地线距离流形学习的输入样本和扩展多维标度。米歇尔利用线性重建发现非线性高维空间中的结构。首先构造一个无向加权图,然后通过图形处理恢复歧管的结构。HLLE是基于稀疏矩阵技术。至于LTSA,它首先计算切线空间每一点,然后优化找到一个一致切线空间的嵌入。

最近,随机邻居嵌入(SNE) [17)和扩展为特征提取成为流行。新力的基本原理是将成对欧几里得距离转化为概率选择的邻居模型成对相似性。新力的扩展,新力(18)使用学生的成对分布模型在低维空间的异同和减轻优化问题和新力的拥挤问题的方法如下:(1)它使用使对称版本的新力成本函数与简单的梯度由厨师介绍了et al。19),(2)它雇佣了重尾分布在低维空间。随后,杨et al。20.系统地分析重尾分布的特点和解决拥挤问题。最近,吴et al。21]探索如何更准确地衡量歧管的相似性,提出了一个投影的方法称为manifold-oriented随机邻居投影(MSNP)基于SNE和特征提取新力。MSNP雇佣了柯西分布而不是学生的标准分布在新力。此外,对于学习的目的相似与精度高、歧管MSNP使用测地距离来描述数据的相似性。虽然MSNP有很多优势在特征提取方面,仍然存在一个缺点:MSNP是一个无监督方法和缺乏的想法类标签,所以这是不适合的模式识别。克服的缺点MSNP,我们做了一些初步的工作和提出了一个名为歧视随机邻居嵌入的方法分析(DSNE) [22]。DSNE有效地解决以上问题,但由于它选择的所有训练样本作为他们的参考点,它具有较高的计算成本,从而为大规模分类任务却是不可行的高维特征(23,24]。我们先前的研究的基础上,我们提出一个方法称为快速区别的随机邻居嵌入分析(FDSNE)克服DSNE本文的缺点。

本文的其余部分组织如下:在部分2详细介绍该FDSNE并简要MSNP和DSNE部分进行比较3。部分4给出了非线性FDSNE的延伸。此外,实验各种数据库介绍部分5。最后,部分6本文总结和未来工作描述的几个问题。

2。快有识别力的随机邻居嵌入分析

考虑一个标记数据样本矩阵 在哪里是一个维样本和手段th的样本类。是样品的数量类,样品的数量吗th类,。

事实上,FDSNE的基本原理是一样的新力将成对欧几里得距离转化为概率的选择邻居成对相似性模型(18]。自从DSNE选择训练样本作为参考点,它具有较高的计算成本,从而为大规模分类任务却是不可行的高维特性。所以根据资讯分类规则,我们提出一个替代概率分布函数使得目标样本的标签由首次决定在FDSNE最近的邻居。在这篇文章中,和定义。他们分别表示th-nearest的邻居从同一个类的不同的类转换空间。在数学上,联合概率是由 在公式(2),两个样本之间的欧式距离吗和,参数是高斯分布的方差参数决定的价值,,,,,,,,,,,,,然后在公式分母(2)意味着所有的参考点在同一类或选择不同的类。特别是,联合概率不仅使概率分布矩阵的对称特征但也让组内的数据的概率值为1,相同的同类数据。

为低维表示,FDSNE使用和高维数据点和。可以计算出一个类似的联合概率通过以下表达式:

接下来,我们将介绍由一个线性投影转换:这。然后通过简单的代数公式,公式(3)等价的表达式如下:

请注意,所有的数据都有内在的几何分布和组内样本和组内的样本也不例外。则必须持有相同的分布特征空间。自从Kullback-Leiber散度(25)是广泛用于量化两个概率分布的接近,我们选择这里来构建我们的罚函数。根据上述定义,函数可以被制定为:

在这项工作中,我们使用最小化的共轭梯度法。为了使推导不杂乱,我们首先定义四个辅助变量,,,为:

然后区分对变换矩阵给下面的梯度,我们采用学习:

让是顺序矩阵元素,让是顺序矩阵元素。请注意,和对称矩阵;因此,可以被定义为一个对角矩阵,每个条目列(或行)的总和和相同的,也就是说,和。有了这个定义,梯度表达式(7可以减少)

一旦梯度计算,我们的优化问题(5)可以解决基于共轭梯度法的迭代过程。FDSNE算法的描述可以由下面给出。

步骤1。收集样本矩阵类标签,集最近的邻居参数,方差参数,最大迭代次数。

步骤2。计算的成对欧式距离和联合概率计算利用公式(2)和类标签。

第三步(设置)。我们在循环搜索解决方案:首先,计算联合概率利用公式(4);然后,计算梯度利用公式(8);最后,更新基于通过共轭梯度的操作。

步骤4。判断(在本文中,我们采取)或收敛于一个稳定的解决方案达到了最大值。如果满足这些先决条件,则步骤5执行;否则,我们重复步骤3。

第5步。输出。

以后,我们称该方法速度区别的随机邻居嵌入分析(FDSNE)。

3所示。比较MSNP和DSNE

MSNP来源于新力和新力,它是一个线性方法和不错的属性,如灵敏度为特征提取非线性流形结构和便利。自MSNP结构接近FDSNE,我们简要比较FDSNE MSNP和DSNE在这一节中。

FDSNE、MSNP DSNE使用不同的概率分布来确定参考点。可以解释在以下方面的区别。

首先,MSNP学习高维样本的相似性关系估计邻域分布基于测地距离度量,和相同的分布在特征空间是必需的。然后线性投影矩阵是用来发现数据流形的底层结构是非线性的。最后,Kullback-Leibler散度目标函数是用来防止成对相似性特征空间。所以MSNP及其梯度的概率分布函数用于学习分别给出的 在哪里测地线距离吗和和柯西分布的自由程度参数。

DSNE选择联合概率模型输入样本的成对相似性与类标签。它还介绍了线性投影矩阵MSNP。构造成本函数最小化同类Kullback-Leibler散度以及组内的KL差异最大化。其概率分布函数和梯度,分别给出了 注意的基础上DSNE, FDSNE充分利用类标签不仅使概率分布矩阵的对称特征但也让组内的数据和组内数据的概率值是1,它能有效地克服大组内的混乱程度的预测子空间。

其次,很明显,参考点的选择在MSNP或DSNE与所有训练样本,而FDSNE只使用第一最近的邻居每个样本的所有类。换句话说,我们提出另一种概率分布函数来确定会选择作为其参考点。实际上,在优化过程中计算梯度主要决定MSNP和DSNE的计算成本。所以他们的计算复杂度可以写成在每个迭代中。同样,FDSNE的计算复杂度在每个迭代中,。很明显,。因此,FDSNE比MSNP快和DSNE在每个迭代。

4所示。内核FDSNE

桥梁从线性到非线性,内核方法出现在20世纪初初及其在模式识别中的应用可以追溯到1964年。近年来,内核方法吸引了广泛关注,许多研究者提出各种理论和方法的基础上。

内核的原则方法是数据从输入空间的一个映射到高维空间,我们将参考的特征空间通过非线性函数。然后在特征空间中执行数据处理,这可以表示只在特征空间的内积。因此,非线性映射不需要显式地构造,但可以通过定义指定内积的形式而言,美世的内核函数。

显然,FDSNE是一个线性特征降维算法。所以这一节的其余部分是致力于FDSNE扩展到非线性的情况下使用内核技术方法。让 我们可以计算内积的价值无需进行映射。

应该注意的是,我们使用来表示在以下简短。接下来,我们表达的转换与

我们定义和,然后。根据以上定义,之间的欧式距离和在空间是 在哪里是一个列向量。很明显,在内核中嵌入空间的距离核函数和矩阵有关。

在本节中,我们提出两种方法来构造目标函数。第一个策略使参数化的目标函数。首先,我们替换与在公式(3),这样,定义应用于高维空间可以写成 然后,我们表示通过修改通过替换与正则化项的公式(5)。最后,通过相同的参数公式(7),我们提供以下梯度:

为了使公式(15容易理解,,,,是由 与此同时,梯度表达式(15可以减少) 在哪里是顺序矩阵元素,是顺序矩阵元素。请注意,和对称矩阵;因此,可以被定义为一个对角矩阵,每个条目列(或行)的总和和相同的,也就是说,和。

为了方便起见,我们命名这个内核方法FKDSNE1。

另一个策略是让在嵌入空间中目标函数。所以它的梯度可以写成 在这种形式,可以认为矩阵与向量在th列向量在列和其他列都是零。

这种方法称为FKDSNE2。请注意,是一个常数矩阵。此外,公式的观察(18)让我们知道更新矩阵在优化只意味着更新矩阵。此外,不需要显式计算。因此,我们不需要显式地执行非线性映射以最小化目标函数。FKDSNE1的计算复杂度和FKDSNE2分别和在每个迭代中。因此,很明显,在每个迭代FKDSNE2比FKDSNE1快。

5。实验

在本节中,我们评估的性能FDSNE, FKDSNE1, FKDSNE2特征提取的方法。进行三组实验是哥伦比亚对象图像库(COIL-20) (http://www1.cs.columbia.edu/cave/software/softlib/coil - 20. - php),美国邮政服务(USPS) (http://www.cs.nyu.edu/ ~ roweis /研究司)和ORL (http://www.cam-orl.co.uk)面临数据集展示他们的好行为可视化,精度和运行时间。在第一组实验中,我们关注的是提出的可视化方法,比较与相关算法,包括新力(17),新力(18],MSNP [21]。在第二组实验中,我们运用我们的方法来识别任务来验证他们的特征提取能力和比较他们与MSNP DSNE [22]。此外,FDSNE的运行时间、FKDSNE1 FKDSNE2, DSNE第三组比较实验。特别是,高斯RBF内核选择的核函数FKDSNE1 FKDSNE2,哪里是集作为训练样本的方差组吗。

5.1。COIL-20,美国邮政总局和ORL数据集

我们的实验中使用的数据集进行了总结如下。

COIL-20 20是灰度图像的数据集对象。每个对象的图像拍摄5度分离的对象是旋转转盘,每个对象都有72的图片。每个图像的大小像素。图1显示了示例图像从COIL-20图像数据集。

USPS手写数字数据集包括10位字符,总共1100个样本。原始数据格式像素。图2显示裁剪图像样本USPS手写数字的数据集。

ORL由灰色图像面临来自40个不同的主题,以10为每个主题的照片。每一个主题,这些照片是用不同的照明条件和不同的面部表情。每个图像的原始大小256像素,每个像素灰度值。图3演示了一个示例ORL数据集的主题。

5.2。可视化使用FDSNE FKDSNE1, FKDSNE2

我们应用FDSNE、FKDSNE1 FKDSNE2可视化任务分类性能的评估他们的能力。分别进行实验,在COIL-20 USPS, ORL数据集。为了计算效率以及噪声过滤,我们首先调整每个图像的大小在ORL像素,然后我们选择五个样本COIL-20每个类,14 USPS,每个类的样本和五个样本在ORL每个类。

实验过程是为每个图像提取20维特性FDSNE, FKDSNE1和FKDSNE2分别。然后评估的质量特性通过第一个二维特征的可视化表示。

FDSNE、FKDSNE1 FKDSNE2相比,三是众所周知的可视化检测方法分类性能:(1)计划(2)新力,(3)MSPN。参数设置如下:最近的邻居参数FDSNE、FKDSNE1 FKDSNE2方法(让表示训练样本的数量在每个类),;新力,新力,困惑参数和迭代数;MSNP,柯西分布的自由程度和迭代号码是1000。

数据4,5,6显示FDSNE的可视化表示结果、FKDSNE1 FKDSNE2,新力,新力,MSNP分别COIL-20,美国邮政总局,ORL数据集。视觉表现表示为散点图中不同的颜色决定了不同的类信息。数据显示,这三个nearest-neighbor-based方法,也就是说,FDSNE, FKDSNE1, FKDSNE2,给比新力更好的分类效果,新力MSNP在所有的数据集,类之间的分离是相当明显的。特别是,新力和新力不仅对组内的数据得到更少的分离也产生较大的组内散射。MSNP,它有更小的组内散射,但存在一个类间重叠的现象。关于FDSNE, FKDSNE1 FKDSNE2,从数据我们可以发现,FKDSNE1显示最佳的分类性能在所有ORL脸上的算法数据集,而不是在另外两个数据集COIL-20和美国邮政总局;其中,分类性能的FKDSNE1不如FDSNE COIL-20在USPS FKDSNE2较低。此外,聚类质量和分离度FKDSNE1和FDSNE FKDSNE2显然比这更好。

5.3。识别使用FDSNE FKDSNE1, FKDSNE2

在本节中,我们应用FDSNE, FKDSNE1, FKDSNE2识别任务来验证他们的特征提取能力。如新力和非线性降维算法新力缺乏明确的样本外数据的投影矩阵,这意味着他们不适合识别。所以我们比较该方法与DSNE MSNP,他们都是线性方法和被证明是比现有特征提取算法如新力,新力LLTSA,垂直距离等等(21,22]。识别的过程描述如下:首先,将数据集分为训练样本集和测试样本集随机;其次,培训过程最优矩阵或对于FDSNE, FKDSNE1 FKDSNE2;第三,特征提取是完成所有样品使用或;最后,一个测试图像是由最近邻分类器。参数设置如下:最近的邻居参数,FDSNE FKDSNE1, FKDSNE2,;DSNE,困惑参数和迭代数;MSNP的自由程度柯西分布的MSNP是由交叉验证和迭代号码是1000。

图7展示了不同的子空间维度的有效性COIL-20((一个):,(b):)。图8实验结果在美国邮政总局((一个):,(b):),和图9显示了识别率和子空间维度在ORL((一个):,(b):)。每种方法的最大识别率和相应的维度表1,在大胆的代表数量最高识别率。从表1,我们可以发现FKDSNE1 FKDSNE2胜过MSNP, DSNE, FDSNE COIL-20,美国邮政总局,ORL。可以看到,FKDSNE1和FKDSNE2提高至少2%的最大识别率与其他三种方法相比。此外,FKDSNE1和FKDSNE2功能维度是20岁时达到相当大的识别精度的三个数据集。它表明FKDSNE1 FKDSNE2把握面临的关键字符图像相对于认同几个特性。尽管DSNE最大的识别率和FDSNE接近FKDSNE1和FKDSNE2 ORL数据库,相应的维度FKDSNE1 FKDSNE2是20,DSNE和FDSNE超过30。从减少空间的本质,这个结果表明FDSNE和DSNE不如FKDSNE1 FKDSNE2。

5.4。分析运行时间

在本节中,我们进一步比较DSNE的计算效率,FKDSNE FKDSNE1, FKDSNE2。算法相比MSPN不是以来识别率明显比其他算法。实验的参数是相同的部分5.3。数据10,11,12分别显示四个算法的运行时间在不同的子空间维度的三个数据集。可以观察到的数据FKDSNE2最低成本计算在四个算法而DSNE远不如其他nearest-neighbor-based算法在所有的数据集。特别是COIL-20数据集,FKDSNE2的运行时间比DSNE快2倍以上。至于DSNE FDSNE,前者明显低于后者。除此之外,两个内核方法,FKDSNE2明显高于FKDSNE1,证实了我们的讨论4。

此外,基于算法FKDSNE1和FKDSNE2能有效表示高维空间的线性结构。他们的目标函数可以实现更好的价值理想的尺寸。例如,图13说明了MSNP的目标函数值,DSNE FKDSNE, FKDSNE1, FKDSNE2 ORL数据集和迭代数。它可以发现FKDSNE2和FKDSNE1接近收敛值而FDSNE和DSNE只有实现和MSNP达到当迭代号码是400。这意味着FKDSNE1 FKDSNE2可以得到更精确的目标函数值和更少的迭代次数与DSNE和FDSNE相比;也就是说,FKDSNE1 FKDSNE2可以达到相同的值通过使用百分之四十的运行时间DSNE FDSNE。

6。结论

DSNE的基础上,我们提出一个方法称为快速区别的随机邻居嵌入分析(FDSNE)选择的参考点最近的邻居目标样本的同一个类和不同的类,而不是总训练样本,从而比DSNE更低的计算复杂度。此外,由于FDSNE是一个线性特征降维算法,我们FDSNE扩展到非线性的情况下使用内核技巧和技术提出了两种基于方法:FKDSNE1 FKDSNE2。实验结果COIL-20,美国邮政总局,ORL数据验证了上述方法的优越性能。我们未来的工作可能包括进一步实证研究的学习速度和鲁棒性FDSNE通过使用更广泛,尤其是大规模的实验。也仍然是重要的研究加速技术,在初始化和长期的学习阶段。

承认

本项目部分由浙江省自然科学基金(nos LQ12F03011和LQ12F03005)。