流形距离与压缩感知核稀疏投影的局部线性嵌入算法

流形学习算法的目的是发现嵌入在高维数据空间中的低维表示,现有的流形学习算法对邻域参数k和噪声比较敏感。针对此问题,文中提出一种流形距离与压缩感知核稀疏投影的局部线性嵌入算法,其核心思想是集成局部线性嵌入算法对高维流形结构数据的降维有效性与压缩感知核稀疏投影的强鉴别性,以实现高效有降噪流形学习。首先,在选择各样本点的近邻域时,采用流形距离代替欧氏距离度量数据间相似度的方法,创建能够正确反映流形内部结构的邻域图,解决以欧氏距离作为相似性度量时对邻域参数的敏感。其次,利用压缩感知核稀疏投影作为从高维观测空间到低维嵌入空间的映射,增强算法的鉴别性。最后,利用Matlab工具对实验数据集进行仿真,进一步验证所提算法的有效性。     

流形学习中邻域大小参数的合适性判定

流形学习算法能否成功应用严重依赖于其邻域大小参数的选择是否合适,为此,提出了一种高效的邻域大小参数的合适性判定方法。基于流形的局部欧氏性,该方法用PCA（Principal Component Analysis,主成分分析）重建误差对邻域图上每一个邻域的线性程度进行衡量,然后根据邻域图上所有PCA重建误差的聚类个数来判定相应邻域大小的合适性。该方法无需象残差那样运行相对耗时的流形学习算法,从而具有较高的运行效率,其有效性可通过实验结果得以证实。     

ISOMAP算法参数的递增式选取

ISOMAP算法能否被成功应用依赖于其唯一参数——邻域大小的选取是否合适,然而,如何高效地选取一个合适的邻域大小目前还是一个难题。当邻域大小变得不合适时,短路边将会出现在邻域图中,从而严重破坏与之相关的最短路径距离对测地距离的逼近能力。和非短路边不同,短路边的两个端点虽然在欧氏空间中相距较近,但在流形上却相距甚远。基于短路边的这一特点,采用序来近似度量一条边的两个端点在流形上的远近程度,因而能够递增式地对邻域大小进行合适的选取。和基于残差的参数选取方法不同,该方法只需递增式地运行广度优先搜索算法,而无需就每一个可能的邻域大小分别运行整个ISOMAP算法,从而具有比较高的运行效率。最终的实验结果证实了该方法的可行性。     

流形学习算法中邻域大小参数的递增式选取

流形学习算法能否成功应用依赖于邻域大小参数的选取是否合适,但该参数在实际中通常难以高效选取。为此,提出一种邻域大小参数的递增式选取方法。按照流形的局部欧氏性,邻域图上的所有邻域都呈线性或近似线性,邻域大小参数若合适,此时所有邻域的线性度量可聚成一类;而邻域大小参数若不合适,邻域图上就会有部分邻域不再线性,其线性度量也不能聚成一类。对邻域图上的每一个邻域执行加权主成分分析,用重建误差对其线性程度进行度量,并计算相应的贝叶斯信息准则,以探测其聚类个数,从而实现对邻域大小参数的递增式选取。实验结果表明,该方法无需任何额外参数,具有较高的运行效率。     

邻域参数动态变化的局部线性嵌入

局部线性嵌入是最有竞争力的非线性降维方法,有较强的表达能力和计算优势.但它们都采用全局一致的邻城大小,只适用于均匀分布的流形,无法处理现实中大量存在的非均匀分布流形.为此,提出一种邻域大小动态确定的新局部线性嵌入方法.它采用Hessian局部线性嵌入的概念框架,但用每个点的局部邻域估计此邻域内任意点之间的近似测地距离,然后根据近似测地距离与欧氏距离之间的关系动态确定该点的邻域大小,并以此邻域大小构造新的局部邻域.算法几何意义清晰,在观察数据稀疏和数据带噪音等情况下,都比现有算法有更强的鲁棒性.标准数据集上的实验结果验证了所提方法的有效性.     

基于共享最近邻的密度自适应邻域谱聚类算法

在谱聚类算法没有先验信息的情况下,对于具有复杂形状和不同密度变化的数据集很难构建合适的相似图,且基于欧氏距离的高斯核函数的相似性度量忽略了全局一致性。针对该问题,提出一种基于共享最近邻的密度自适应邻域谱聚类算法（SC-DANSN）。通过一种无参数的密度自适应邻域构建方法构建无向图,将共享最近邻作为衡量样本之间的相似性度量进而消除参数对构建相似图的影响,体现全局和局部的一致性。实验结果表明,SC-DANSN算法相比K-means算法和基于K最近邻的谱聚类算法（SC-KNN）具有更高的聚类精度,同时相比SC-KNN算法对参数的选取敏感性更低。     

流形学习中基于局部线性结构的自适应邻域选择

近年来,流形学习成为包括机器学习、模式识别和计算机视觉等相关领域的研究热点.流形学习算法中,邻域选择直接关系到算法的性能,而传统的邻域选择算法如k近邻和ε邻域算法存在参数难以确定,所构建邻域不能反映流形学习算法对邻域要求等缺点.提出了一种基于流形局部线性结构的自适应邻域选择算法(ANSLL).首先通过分析现有流形学习算法,总结出构建邻域的两个基本原则:1)同一邻域的所有点都近似地位于某一d维线性子空间内(d为流形维数);2)每个邻域包含尽可能多的点.基于这两个基本原则,ANSLL 算法采用主成分分析技术(PCA)度量有限点集的线性程度,通过邻域压缩或扩张方式自适应地构建邻域.针对邻域线性结构的特点,还提出了一种改进的邻域图构建方法,以提高等度映射(Isomap)算法中测地线距离估计的准确性.最后大量系统的实验表明,ANSLL算法能够依据流形的局部曲率自适应地构建邻域,从而提高大多数流形学习算法(如Isomap和LLE)的性能.     

基于邻域保持的流形学习算法评价模型

应力函数和残差只适合于评价距离严格保持的流形学习算法,dy-dx表示法又是一个定性模型。虽然距离比例方差可以比较和评价大多数的流形学习算法,但其需要计算测地线距离,具有较高的计算复杂度。为此,提出一种基于邻域保持的流形学习算法定量评价模型,该模型仅仅需要确定两个空间中每个对象的k个近邻,并计算出每个点在低维空间中的近邻保持情况,不用计算测地线距离。理论分析表明,邻域保持模型的计算复杂度远远低于距离比例方差的复杂度。在三个数据集上比较了两个模型的性能,实验结果表明,利用邻域保持模型不但可以评价同一算法在不同邻域参数下的嵌入效果,而且可以在不同的流形学习算法之间进行比较,并且其评价流形学习算法的性能优于距离比例方差。     

基于最小连通邻域图的ISOMAP算法

噪音的干扰和邻域大小的不合适会在ISOMAP算法的邻域图中引入“短路”边,使其不能正确表达数据的邻域结构,从而使该算法具有较差的鲁棒性和拓扑稳定性。为此,根据最小连通邻域图能有效避免“短路”边的特点,提出了一种能有效删除“短路”边因而更具鲁棒性和拓扑稳定性的ISOMAP算法——基于最小连通邻域图的ISOMAP（MCNG-ISOMAP）算法。该算法能在一定程度上避免邻域大小难以有效选取的问题,同时还能在不依赖于邻域大小的情况下发现数据真正的固有维数。     

基于稀疏表示和随机游走的磨玻璃型肺结节分割

肺结节是早期肺癌在影像学上的表现形式.磨玻璃型（Ground glass opacity,GGO）肺结节被认为是恶变可能性最大的一类结节之一.针对GGO结节边缘模糊、大小各异、形状不规则和灰度不均匀等造成分割准确率低问题,本文提出了一种基于稀疏表示和随机游走模型的分割算法.首先,利用测地距离和局部搜索策略,自动地选取了种子点.其次,联合8-!邻域和稀疏表示的K-!最近邻算法建立了新的图,避免了噪声的干扰.结合灰度、纹理、空间距离和稀疏系数构建了新的加权矩阵.最后,将标签限制项引入到随机游走的能量函数中.该算法分割准确性较高,鲁棒性较强.     

基于特征子空间邻域的局部保持流形学习算法*

局部保持流形学习算法通过保持局部邻域特性来挖掘隐藏在高维数据中的内在流形结构。然而,对于缺乏足够训练样本的高维数据集,或者高维数据集存在非线性结构和高维数据特征中存在冗余、干扰特征,使得在原特征空间中利用欧式距离定义的邻域关系并不能真实反映数据的内在流形结构,从而影响算法的性能。提出利用正约束寻找特征子空间的方法,使得在此子空间中更多的同类样本紧聚,并进一步在该子空间中构建邻域关系来挖掘高维数据的内在流形,形成基于特征子空间邻域特性的局部保持流形学习算法(NFS-LPP和NFS-NPE)。它们在一定程度上克服了高维小样本数据集难以正确挖掘内在流形结构的问题,在Yale和ORL人脸库上的分类和聚类实验验证了其有效性。     

Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc.) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connecting those elements increases and when the "length" of paths decreases. It turns out that the square root of the average commute time is a Euclidean distance and that the pseudoinverse of the Laplacian matrix is a kernel matrix (its elements are inner products closely related to commute times). A principal component analysis (PCA) of the graph is introduced for computing the subspace projection of the node vectors in a manner that preserves as much variance as possible in terms of the Euclidean commute-time distance. This graph PCA provides a nice interpretation to the "Fiedler vector," widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities perform well in comparison with other methods. The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a relational database     

Clustering and embedding using commute times

This paper exploits the properties of the commute time between nodes of a graph for the purposes of clustering and embedding, and explores its applications to image segmentation and multi-body motion tracking. Our starting point is the lazy random walk on the graph, which is determined by the heatkernel of the graph and can be computed from the spectrum of the graph Laplacian. We characterize the random walk using the commute time (i.e. the expected time taken for a random walk to travel between two nodes and return) and show how this quantity may be computed from the Laplacian spectrum using the discrete Green's function. Our motivation is that the commute time can be anticipated to be a more robust measure of the proximity of data than the raw proximity matrix. In this paper, we explore two applications of the commute time. The first is to develop a method for image segmentation using the eigenvector corresponding to the smallest eigenvalue of the commute time matrix. We show that our commute time segmentation method has the property of enhancing the intra-group coherence while weakening inter-group coherence and is superior to the normalized cut. The second application is to develop a robust multi-body motion tracking method using an embedding based on the commute time. Our embedding procedure preserves commute time, and is closely akin to kernel PCA, the Laplacian eigenmap and the diffusion map. We illustrate the results both on synthetic image sequences and real world video sequences, and compare our results with several alternative methods.     

基于测地线距离的广义高斯型Laplacian 特征映射

传统的Laplacian 特征映射是基于欧氏距离的近邻数据点的保持,近邻的高维数据点映射到内在低维空间后仍为近邻点,高维数据点的近邻选取最终将影响全局低维坐标.将测地线距离和广义高斯函数融合到传统的Laplacian 特征映射算法中,首先提出了一种基于测地线距离的广义高斯型Laplacian 特征映射算法(geodesicdistance-based generalized Gaussian LE,简称GGLE),该算法在用不同的广义高斯函数度量高维数据点间的相似度时,获得的全局低维坐标呈现出不同的聚类特性;然后,利用这种特性进一步提出了它的集成判别算法,该集成判别算法的主要优点是:近邻参数K 固定,邻接图和测地线距离矩阵都只构造一次.在木纹数据集上的识别实验结果表明,这是一种有效的基于流形的集成判别算法.     

一种提高文本分类效果的改进流形学习算法

流形学习算法在模式识别领域有着重要应用,针对文本分类数据的特点,提出一种基于邻域选取进行修正的局部线性嵌入算法,用带有权值的欧式距离来构造文本数据的局部邻域,提高文本分类的识别率;同时,利用文本数据的类别信息,运用半监督局部线性嵌入算法构造分类器,提高文本分类的效果。实验表明,本文基于文本分类改进的流形学习算法,能够有效地对文本进行分类。     

Graph simplification and matching using commute times

This paper exploits the properties of the commute time for the purposes of graph simplification and matching. Our starting point is the lazy random walk on the graph, which is determined by the heat kernel of the graph and can be computed from the spectrum of the graph Laplacian. We characterise the random walk using the commute time between nodes, and show how this quantity may be computed from the Laplacian spectrum using the discrete Green's function. In this paper, we explore two different, but essentially dual, simplified graph representations delivered by the commute time. The first representation decomposes graphs into concentric layers. To do this we augment the graph with an auxiliary node which acts as a heat source. We use the pattern of commute times from this node to decompose the graph into a sequence of layers. Our second representation is based on the minimum spanning tree of the commute time matrix. The spanning trees located using commute time prove to be stable to structural variations. We match the graphs by applying a tree-matching method to the spanning trees. We experiment with the method on synthetic and real-world image data, where it proves to be effective.     

惰性随机游走视觉显著性检测算法

目的 鉴于随机游走过程对人类视觉注意力的良好描述能力,提出一种基于惰性随机游走的视觉显著性检测算法。方法 首先通过对背景超像素赋予较大的惰性因子,即以背景超像素作为惰性种子节点,在由图像超像素组成的无向图上演化惰性随机游走过程,获得初始显著性图;然后利用空间位置先验及颜色对比度先验信息对初始显著图进行修正;最终通过基于前景的惰性随机游走产生鲁棒的视觉显著性检测结果。结果 为验证算法有效性,在MSRA-1000数据库上进行了仿真实验,并与主流相关算法进行了定性与定量比较。本文算法的Receiver ROC（operating characteristic）曲线及F值均高于其他相关算法。结论 与传统基于随机过程的显著性检测算法相比,普通随机游走过程无法保证收敛到稳定状态,本文算法从理论上有效克服了该问题,提高了算法的适用性;其次,本文算法通过利用视觉转移的往返时间来刻画显著性差异,在生物视觉的模拟上更加合理贴切,与普通随机游走过程采用的单向转移时间相比,效果更加鲁棒。