文摘

降维是一个很重要的问题对于许多应用程序,包括生物医学图像分析和系统分析。邻居嵌入,那些代表着全球和局部结构以及处理多个集合管,如弹性嵌入技术,可以超越传统的降维方法,找到更好的最适条件。然而,现有的邻居嵌入算法不能直接应用于分类遭受几个问题:(1)计算复杂度高,(2)非参数映射,和(3)类标签信息的缺乏。我们提出一个监督邻居嵌入叫歧视弹性嵌入(迪)集线性投影矩阵和类标签到最终的目标函数。此外,我们目前的拉普拉斯算子的搜索方向快速收敛。迪是评估在三个方面:嵌入可视化,训练效率和分类性能。实验结果在多个基准数据库目前该迪展览监督降维方法不仅模式揭示能力强,但也带来了比标准的基于梯度的方法计算的优势。

1。介绍

高维数据的分类,如生物特征序列,high-definite图片,和基因表达式,仍然是一个艰巨的任务(1]。这些高维数据构成的主要挑战包括结果性能低劣,巨大的存储需求,和高计算复杂度。降维(博士)2),作为子空间学习社区的核心研究课题,是盛典维度问题的解诅咒。分类任务,博士的目标侧重于构建一个数据的低维表示为了达到更好的歧视和加快后续处理。在这个领域,非常简单的算法是主导,作为先进技术博士提出的计算复杂度太高了。

Fisher判别分析(FDA) (3)和它的变体(4,5),它包含类标签信息和旨在保护嵌入的子空间分类精度的博士采用的主要技术。FDA放大了类间散,同时减少在类散射子空间为目的的理想的可分性。最近,LFDA [6],MMDA [7),直流电压(8],MMPA [9)明显提高FDA通过求解的性能不同的现有的棘手问题。LFDA Fisher将本地保存属性添加到标准,它保留了多通道结构。MMDA小说提供了一个标准,直最大化整个类的最小两两距离更好的类间分离性。直流电压避免了“小样本”问题通过使用两种不同的方法,在类散射矩阵和gram - schmidt正交化过程,获取歧视共同向量。MMPA考虑组内和组内的几何图形,也具有投影矩阵的正交性属性。一般来说,所有这些方法都有一个独特的解决方案计算广义eigensolver和表现出可接受的性能在大多数数据,但他们可能是次优的数据与非均匀密度或多个集合管。

处理更复杂的数据结构,尤其是在生物医学应用(10- - - - - -12),一批小说技术(博士13- - - - - -19基于随机邻居嵌入(SNE) []13)吸收大量的利益。与FDA-type技术相比,那些只考虑原始高维空间构造目标函数。新力相似性匹配,实现高维和低维空间。此外,新力(14]扩展新力对称相似性和利用学生的在低维空间中分布。对称新力(15解释了为什么重尾分布和对称相似形式新力带来更好的性能。NeRV [16)使用“双重”Kullback-Leibler(吉隆坡)分歧在信息检索角度博士十分满意的结果。李等人。17)采用了广义的扩展版本Jensen-Shannon散度,更好的保护小K-ary社区。缩聚et al。18]分析的可视化表现新力任意差异和声称KL散度是最可接受的。可视化的结果,所有这些技术比过去的技术。然而,这行为的原因还不太清楚。李和Verleysen [20.]调查所扮演的角色的特定相似性和确定适当的规范化与财产移不变性的主要原因是令人钦佩的性能。然而,Carreira-Perpinan [21新力)显示的基本关系和拉普拉斯算子eigenmaps [22博士)方法,提出了一种新的方法,弹性嵌入(EE),可以被视为学习的坐标数据点之间的紧密联系而不移不变性的财产。

EE比新力更高效和健壮,新力和NeRV。即便如此,它不能直接应用于分类任务,因为现实的歧视能力,样本外的问题,一些大规模的高计算复杂度分类任务(23,24]。许多研究人员一直致力于解决这些缺点。Venna et al。16]提出监督NeRV由复杂的局部线性功能更好的辨别能力。缩聚et al。25)博士提出了一个通用框架,各种非参数技术再扩展到通过优化参数映射。Gisbrecht et al。26)只有一小部分整体样本用于训练模型博士在交互设置。杨et al。27]和Maaten [28)同时采用Barnes-Hut树,提出了一种通用的近似优化技术,减少了邻居嵌入优化成本来。

受这些作品的启发,我们提出了一个线性监督技术博士歧视EE(迪)分类。具体而言,介绍了线性投影矩阵解决样本外问题同样在(29日]。类标签信息作为MMPA参与建设的目标函数。我们寻找一个合理的方向基于迭代处理来解决我们的模型的梯度方法。本文的其余部分的结构如下。部分2提供了一个简短的观点相关的工作。部分3描述了目标函数和我们建议的迪的搜索方向。部分4收集实验结果。最后,部分5得出了结论和草图一些未来的工作。

2。基本的贡献

尽管有很多以前学习算法中嵌入高维数据可视化或分类,我们这里只关注几个方法是最近提议的,我们将使用比较评估。涉及的技术包括弹性嵌入(EE)的区别的随机邻居嵌入(DSNE) [30.),和min-max投影分析(MMPA)。让 是维样本,是标签和对应的类是所有样品的矩阵,是样本大小和是类的大小。非线性嵌入方法继续寻找子空间矩阵的列向量是像素地图的坐标,在哪里d子空间维数。另一方面,通常的线性嵌入技术的目的是学会一个投影矩阵进一步,这是用来计算嵌入坐标。

2.1。弹性嵌入

弹性嵌入(EE)技术,非线性和无监督,SNE-type算法的扩展。EE被定义为的目标函数 在哪里和,,。左边术语(1),称为有吸引力的词,保留当地距离的拉普拉斯算子eigenmaps [22]。正确的术语(1),称为排斥力,保持全球距离平面的方式比传统的新力算法。交易是一个可调参数从吸引和排斥。

的梯度在(1然后计算) 作者定义了相似在哪里 和图拉普拉斯算子常见的方式。度矩阵。后获得的梯度,EE使用定点(FP)对角迭代方案实现全球和快速收敛性。首先,梯度是分裂 这时,一个搜索方向是派生的。

两个目标函数的梯度EE直觉更清晰和更少的比其他EE以来SNE-type算法避免了非线性累赘的σ。此外,外交策略导致更少的当地的最适条件。然而,EE仍然是非线性,所以样本外的嵌入输入是低效的。此外,EE忽略类标签的使用,使得EE非最优分类。

2.2。有识别力的随机邻居嵌入

有识别力的随机邻居嵌入(DSNE)技术,线性和监督,是一个扩展的新力算法。为每个输入数据每个潜在的邻居在同一类或不是,概率那选择因为它的邻居 在哪里是一个正则化参数手动设置。嵌入的样品重尾分布的学生分布与邻居一个自由度,因此,诱导嵌入式概率那选择组内或组内的邻国 DSNE的目的是将接近同类样本和地点远组内的样本。这是通过最小化目标函数,这是吉隆坡的总和之间的分歧和考虑类的标签

的梯度在(7)可以获得 在哪里和是同类样本的拉普拉斯算子矩阵和组内的样本,分别。DSNE介绍显式投影矩阵和标签信息,让它适合分类任务。然而,繁琐的σ术语和乏味的共轭梯度训练方法使DSNE收敛缓慢。

2.3。Min-Max投影分析

min-max投影分析(MMPA)是另一个最近提议线性监督降维技术。MMPA结合块优化和整体定位策略的主要优势(31日]。它还包含了一个理想的财产从边际费舍尔分析(32),也就是说,齐心协力在类邻居尽可能远,以及放置了邻居尽可能有不同的标签。这些属性的结合导致了技术,胜任网络输入流数据和理想的辨别能力。投影矩阵来自MMPA是解决目标函数如下: 通过解决广义特征值问题(9),MMPA得到一个封闭形式的解决方案没有任何迭代过程,这是密切相关的经典,如直流电压和LFDA降维算法。所有这些技术目前高效的计算成本。然而,他们总是拥挤问题导致凌乱的子空间可视化。

3所示。有识别力的弹性嵌入

在本节中,我们描述了迪技术,侧重于探索一个显式的映射,呈现一个大分离组内的地区和实现更快的收敛。我们首先介绍的嵌入配方。

3.1。配方

就像前面提到的2eigenmap-type算法,如MMPA采用简单关联函数构造直接泛化特征值问题,对噪声敏感,结果在拥挤的嵌入的子空间。DSNE可以超越光谱技术和找到更好的最适条件,表现出不同阶层差距巨大以及处理多个集合管。然而,优化DSNE是当地最适条件昂贵和容易。此外,我们对这些SNE-type算法的理解仅限于一个直观的解释他们的成本函数。EE进一步理解通过推导新力和拉普拉斯算eigenmaps之间明确的关系。此外,EE采用简单的非规范更有效和鲁棒优化模型。EE的目标函数是由当地距离项和全球距离项代表更好的全局和本地嵌入结构。然而,本文的目的是扩大不相交的区域为不同的类。我们解决这个问题通过引入类标签有吸引力的关联权重和排斥的亲和力与MMPA重量相似: 此外,我们采用显式的投影矩阵EE线性和避免样本外的问题。也就是说,在(1),我们替换作为使它成为 方程(12选择在这里作为我们的目标函数。我们所说的模型作为区别的弹性嵌入(迪)。在接下来的部分,我们将最优投影矩阵的优化策略。

3.2。定点搜索方向

的成本函数(12)描述所需的嵌入:鼓励组内样本嵌入的对象附近,但鼓励组内的样本嵌入的对象。然而,这个方程是凸,没有封闭的解。一些基于梯度的方法如梯度下降法、共轭梯度和乘法更新(33)用于现有SNE-type算法。这些都是报道非常缓慢而微小的步骤。EE中使用的定点迭代策略更好的工作,所以我们这个FP方法引入到迪技术在这一节中。迪得到的梯度 我们替换和简洁。从驻点梯度方程(13),我们可以分开成两部分 在哪里是对称的,积极的,明确的和是对称的。然后,我们可以得到FP迭代计划,进一步暗示了FP的搜索方向。目标函数将减少和聚合驻点与FP方向的线搜索满足了沃尔夫条件(34]。每个FP迭代的主要成本是由梯度方程(13),这是。

3.3。拉普拉斯算子的搜索方向

在本节中,我们的目标是提供一个搜索方向,可以导致快速和全局收敛性。有两种常见的方式实现这一目标。一是加快计算的基于梯度的迭代计划。另一种是实现最优目标价值尽可能几个迭代。直观的方法来加快计算是减少样本的大小。这明显的二次抽样方法总是产生差结果。在[27,28),作者同时采用Barns-Hut树近似SNE-type梯度,导致大量计算优于现有的邻居嵌入技术。然而,这种Barns-Hut树策略需要足够的训练样本维护更好的性能。此外,基于Barns-Hut树的邻居嵌入方法只能适用于嵌入数据在二维或三维树的大小。总之,我们将探索为减少迭代最好的搜索方向。

从数值优化理论34),我们重复的线搜索方法 在哪里选择搜索方向,目标函数的梯度,是一个正定矩阵确保下降方向,沃尔夫满足条件。我们的目的是选择一个理想的矩阵范围从我海赛矩阵获得的 在哪里是单位矩阵。当选为单位矩阵吗我优化精制是梯度下降法,收敛速度非常慢。在另一个极端,当使用麻绳,优化称为牛顿方法,它消耗太多的每次迭代计算。我们的直观原则是采用尽可能多的黑森信息导致一个有效的解决方案线性方程(15)(例如,稀疏和常数)。我们进一步分裂(16), 自密切相关的变量第二部分和第三部分(17)需要重新计算每个迭代。第一部分是恒定的,它只需要在第一次迭代计算一次。此外,由于条目是对称和非负(10),这个词是对称的、积极的和半定,我们可以添加一个小实现一个正定矩阵。总之,有吸引力的黑森构造我们最后的搜索方向是理想妥协的快速收敛性和高效的计算。因为这个方向主要是相关的有吸引力的拉普拉斯算子,我们叫它为拉普拉斯算子的方向(LD)。注意避免的直接计算这成本我们可以首先实现了柯列斯基因素R的然后用两个backsolves拉普拉斯算子的方向。柯列斯基分解的成本它只需要计算一次。的两个backsolves成本。我们发现拉普拉斯算子的方向工作与迭代次数更少得惊人。

4所示。实验和结果

我们评估算法的性能在这一节中。迪第一,比较四种方法:梯度下降法(GD),用于新力;共轭梯度(CG)中使用新力;定点(FP),用于EE;(LD)和拉普拉斯算子的方向,提出了。之后,我们将演示迪的有效性与一些经典算法相比,聚类可视化等新力、DSNE和情感表达。最后,我们给出了该系统的实验结果对图像分类。四个数据集用于评估:COIL20图像数据库,ORL人脸数据库,耶鲁面孔数据库,数据库和USPS手写数字。

4.1。数据集

COIL20数据库包含20个对象。每个对象的图像拍摄5度分离的对象是旋转转盘,每个对象都有72的图片。每个图像的大小每像素256像素,与灰色水平。脸ORL数据库包含400脸图像从40人(每人10个样本)。每一个主题,拍摄的图像在不同的时间,不同的照明,面部表情(打开/关闭眼睛,微笑/不笑),和面部细节(搪瓷/非搪瓷)。所有的图片都被黑暗的均匀背景与受试者在一个正直的,前面的位置(宽容一些侧运动)。耶鲁大学数据库包含165面临15个人的形象。有11个图片/主题,每个不同的面部表情或配置:一个轻心,戴眼镜,开心,左灯,没有眼镜,正常,右灯,悲伤,昏昏欲睡,惊讶,眨眼。我们通过调整这些原始图像预处理变换和缩放变换,两只眼睛对准在同一位置。然后,面部区域裁剪到由此产生的图像。在我们的实验中,每一个图像在ORL数据库是手工裁剪和缩放和耶鲁大学像素。USPS手写数字数据集包括10位字符,总共1100个样本。的数据格式像素。图1显示了一些示例图像的四个数据集。

4.2。评价不同的训练方法

许多不同的训练方法已经申请解决SNE-type嵌入算法。我们有以下四个方法实现优化迪模型与拉普拉斯算子的方向一节中描述的方法3:梯度下降法(GD),最初用于新力;共轭梯度(CG),最初用于新力;和定点迭代,最初用于对称新力和情感表达。有几个参数值,需要用户设置为所有三种实现方法。一般,毫无线索的参数值是最合适的。这是LD法的主要原因,没有参数被设置,是我们的首选。我们设置的参数是一样的(13,14,21]。1000不断和设置最大迭代最终收敛条件成立。前三个数据集、COIL20 ORL和耶鲁,我们使用所有的样本作为输入数据。避免混乱,我们随机选择60为每个类样本为USPS手写数字的输入数据集。

可视化结果如图2,3,4,5,所有的输入数据都投影到二维空间。不同的颜色代表不同的类。图6展示了学习曲线的函数的渐进迭代。还国家单一模型的运行时间以秒为单位建设。从数据2- - - - - -5我们可以看到,不同的训练方法,迪为集群不同的类数据是很有用的。然而,LD法显然比其他三种方法更具竞争力。在数据2和5,色坐标显示迪与LD法准确地分离底层分离结构在不同的类。然而,其他三种方法有更多不同阶层之间发生重叠。在数据3和4,尽管所有的四种方法表现出明显不同的类之间的分离因素,内部类坐标FP, CG,和GD更分散,这是次优的分类。从图6,很明显,迪与LD法可以用更少的迭代次数达到更精确的目标价值。降低效率,大概四个方法应该下令LD > FP > CG和GD。CG方法最需要迭代次满足收敛条件。然而,CG的客观价值比GD值更准确。这也解释了为什么CG的聚类结果比GD的数据更准确2- - - - - -5。通常,FP是更有效的比CG和GD,花费更少的时间完成一个迪模型建设。然而,运行时在每一个迭代循环FP不仅仅是CG和GD。建设时间FP是低于GD COIL20数据集,这两个方法花近迭代时间。LD不仅达到最精确客观值,但至少还需要运行时。ORL数据库为例;LD只需要13个迭代获得最佳的客观价值,但FP需要大约390次迭代的收敛条件。所以,LD的成本大约是1秒迪构造模型,大概是38倍FP,第二个有效方法的顺序。这个结果符合理论分析部分2光谱方向快速收敛更有用。

4.3。评估不同的嵌入算法

迪模型与LD策略被证明是最有效和高效的方法在前面的评价。开始提出的分类性能分析方法,其次比较它与其他嵌入算法评估其能力避免重叠的不同的类。我们进行了比较DSNE、情感表达和新力在2 d嵌入空间中。可视化结果见图7,8,9,10。很明显从这些数字就是迪和DSNE更能够分离数据除了比EE和不同的类新力。注意,情感表达和新力都忽视的类标签模型建设。这表明类标签应该是更重要的因素来提高分类性能。此外,从数据7和9,我们不仅可以看到DSNE阶级之间的重叠,但也有更多的同类比迪散射。这是由于两个主要因素。首先,传统SNE-type嵌入算法等新力或DSNE使用归一化概率,这是繁琐和不必要的。然而,迪放弃标准化术语,但关注的重要和显式非线性关系和光谱方法,这使得迪更健壮的各种类型的数据。第二,迪使用光谱方向优化,这是有效的和没有参数优化。尽管DSNE使用共轭梯度方法优化,有许多参数需要手动调整,这是困难和费时。此外,共轭梯度方法容易陷入局部最优,从而导致混乱子空间坐标。

4.4。分类性能的评价

在[19,30.],一些比较研究SNE-type嵌入算法和谱方法证明了图像数据和高光谱数据,分别。这些示威表明,虽然SNE-type嵌入算法,提高分类的性能要求更加简洁的子空间维数仍然是一个挑战。在部分实验结果4.3,我们知道的类标签的分类性能很重要。我们比较迪和其他三个监督降维技术,DSNE,直流电压,MMPA。直流电压和MMPA是两个最近提议光谱方法。直流电压没有特殊参数需要调整。对于MMPA,我们设置参数和组内和组内的平均欧氏距离,分别。对于DSNE,我们遵循的参数设置为30.]。为了说明投影空间的分类性能,用最近邻分类器产生的决定的结果。COIL20数据集,我们随机选择15个样品为每个对象作为训练样本。ORL和耶鲁的数据集,我们统一提供训练样本的50%。在美国邮政总局,25个样本在每个类被用于输入数据。所有其他的数据作为测试样本。图11显示了迪的识别率和进步的空间维度,DSNE,直流电压,MMPA在四个不同的数据集。所有的结果在图11形成了十复制。从这幅图中,我们可以看到的最大直流电压子空间维数是有限的C1、由于差别矩阵的秩。在一些数据集,这种限制使得直流电压表现不佳。此外,直流电压要求更多同类散射矩阵的零空间信息更好的识别率。美国邮政总局的数据集,直流电压的最优精度仅为83%,这是最坏的与其他三种算法相比。如果没有这一限制,其他三个算法免费子空间维数的选择。然而,由于共轭梯度方法是不稳定的和次优,DSNE只会更好的识别率比直流电压及其精度曲线起伏的。最好的识别率MMPA和迪非常接近。相比之下,识别率迪比MMPA平滑的曲线。这减少了复杂的选择一个合适的子空间维度的价值广泛的用户。此外,迪达到较高的识别率较低的子空间维度值,这符合降维的本质。 In other words, DEE is capable of using as little as possible subspace dimensions for representing the original feature space.

5。结论

提出了一种新的基于EE的嵌入算法。该算法可用于聚类可视化和分类。我们的实验插图都集中在图像数据中嵌入;然而,该算法也可以扩展到其他数据的降维没有任何调整。迪,监督嵌入算法,能够齐心协力同类例子以及推动了组内的例子。这种“pull-push”属性使得迪资格歧视的任务。所有SNE-type算法的主要缺点是他们的优化是一个非凸问题需要迭代过程相对缓慢。我们介绍了拉普拉斯算子的搜索方向改善这种基于梯度的优化策略。经验,通过拉普拉斯算子的解决方案解决方向是更快和更有效的比现有的优化方法。本文实验结果在四个图像数据集显示迪优于现有最先进的算法聚类可视化和分类。 With fewest computation cost and more concise subspace dimension, DEE shows better embedded structure and reaches highest recognition rate.

在未来的工作中,我们计划加快计算的成本在每一个迭代循环LD的策略,使“大数据”的可视化和分类。我们也会调查所有SNE-type的可伸缩的优化算法,我们可以建立统一的基于SNE嵌入框架。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢匿名评论者的建设性的意见和建议。这个项目的部分支持由浙江省级科学基金会(LQ12F03011),中国国家自然科学基金(61379123)和国家科技支撑计划(2012 bad10b0101)。