局部子空间聚类

现有子空间聚类方法通常以数据全局线性为前提,将每个样本点表示为其他样本点的线性组合,因而导致常见子空间聚类方法不能很好地应用于非线性数据.为克服全局线性表示的局限,借鉴流形学习思想,用k近邻局部线性表示代替全局线性表示,与稀疏子空间聚类和最小二乘子空间聚类方法相结合,提出局部稀疏子空间聚类和局部最小二乘子空间聚类方法,统称局部子空间聚类方法.在双月形数据、6个图像数据集和4个基因表达数据集上进行实验,实验结果表明该方法是有效的.     

Locally affine patch mapping and global refinement for image super-resolution

This paper deals with the super-resolution (SR) problem based on a single low-resolution (LR) image. Inspired by the local tangent space alignment algorithm in [16] for nonlinear dimensionality reduction of manifolds, we propose a novel patch-learning method using locally affine patch mapping (LAPM) to solve the SR problem. This approach maps the patch manifold of low-resolution image to the patch manifold of the corresponding high-resolution (HR) image. This patch mapping is learned by a training set of pairs of LR/HR images, utilizing the affine equivalence between the local low-dimensional coordinates of the two manifolds. The latent HR image of the input (an LR image) is estimated by the HR patches which are generated by the proposed patch mapping on the LR patches of the input. We also give a simple analysis of the reconstruction errors of the algorithm LAPM. Furthermore we propose a global refinement technique to improve the estimated HR image. Numerical results are given to show the efficiency of our proposed methods by comparing these methods with other existing algorithms.     

Incremental Alignment Manifold Learning

A new manifold learning method,called incremental alignment method(IAM),is proposed for nonlinear dimensionality reduction of high dimensional data with intrinsic low dimensionality.The main idea is to incrementally align low-dimensional coordinates of input data patch-by-patch to iteratively generate the representation of the entire dataset. The method consists of two major steps,the incremental step and the alignment step.The incremental step incrementally searches neighborhood patch to be aligned in the next step,and the alignment step iteratively aligns the low-dimensional coordinates of the neighborhood patch searched to generate the embeddings of the entire dataset.Compared with the existing manifold learning methods,the proposed method dominates in several aspects:high efficiency,easy out-of-sample extension,well metric-preserving,and averting of the local minima issue.All these properties are supported by a series of experiments performed on the synthetic and real-life datasets.In addition,the computational complexity of the proposed method is analyzed,and its efficiency is theoretically argued and experimentally demonstrated.     

稀疏子空间聚类综述

稀疏子空间聚类(Sparse subspace clustering, SSC)是一种基于谱聚类的数据聚类框架. 高维数据通常分布于若干个低维子空间的并上, 因此高维数据在适当字典下的表示具有稀疏性. 稀疏子空间聚类利用高维数据的稀疏表示系数构造相似度矩阵, 然后利用谱聚类方法得到数据的子空间聚类结果. 其核心是设计能够揭示高维数据真实子空间结构的表示模型, 使得到的表示系数及由此构造的相似度矩阵有助于精确的子空间聚类. 稀疏子空间聚类在机器学习、计算机视觉、图像处理和模式识别等领域已经得到了广泛的研究和应用, 但仍有很大的发展空间. 本文对已有稀疏子空间聚类方法的模型、算法和应用等方面进行详细阐述, 并分析存在的不足, 指出进一步研究的方向.     

基于[k]-近邻与局部相似度的稀疏子空间聚类

为了获得结构更加合理的仿射矩阵,提出了一种基于[k]-近邻与局部相似度的稀疏子空间聚类算法。该算法首先计算每个点的[k]-近邻,并对其用[k]-近邻数据点进行线性表示,使仿射矩阵在整体稀疏的情况下保证局部的强线性关系。基于图论知识,利用数据的实际分布情况对仿射矩阵进行约束,使仿射矩阵进一步合理地等价于待进行谱聚类的相似矩阵。在人造数据集、随机生成的子空间数据集、图像数据集以及真实数据集上进行了实验,结果表明该算法是有效的。     

基于重叠片排列的流形学习算法

针对线性数据降维算法对处理非线性结构数据的降维效果不是很好,提出一种基于重叠片排列的流形学习算法,该算法根据局部的线性贴片处在非线性流形中的特性,将流形划分为线性互相重叠的局部区域贴片,且利用主成分分析方法得到局部区域贴片的低维表示,然后排列且对齐其低维坐标,以获得整体数据的低维坐标.通过仿真结果证明,基于重叠片排列的流形学习算法在应用于人脸识别和分类问题时以及在识别准确率方面要优于其他经典的流形学习算法.     

非负子空间聚类指导下的非负矩阵分解

非负矩阵分解作为一种有效的数据表示方法被广泛应用于模式识别和机器学习领域。为了得到原始数据紧致有效的低维数据表示,无监督非负矩阵分解方法在特征降维的过程中通常需要同时发掘数据内部隐含的几何结构信息。通过合理建模数据样本间的相似性关系而构建的相似度图,通常被用来捕获数据样本的空间分布结构信息。子空间聚类可以有效发掘数据内部的子空间结构信息,其获得的自表达系数矩阵可用于构建相似度图。该文提出了一种非负子空间聚类算法来发掘数据的子空间结构信息,同时利用该信息指导非负矩阵分解,从而得到原始数据有效的非负低维表示。同时,该文还提出了一种有效的迭代求解方法来求解非负子空间聚类问题。在两个图像数据集上的聚类实验结果表明,利用数据的子空间结构信息可以有效改善非负矩阵分解的性能。     

基于稀疏子空间聚类的多层网络社团检测

现有的子空间聚类方法大多只适用于单层网络,或者仅对多层网络中每层的聚类结果简单地进行平均,未考虑每层网络中包含信息量不同的特点,致使聚类性能受限。针对该问题,提出一种面向多层网络的稀疏子空间聚类方法。将距离正则项和非负约束条件集成到稀疏子空间聚类框架中,从而在聚类时能够同时利用数据的全局信息和局部信息进行图学习。此外,通过引入稀疏约束使学习到的图具有更清晰的聚类结构,并设计迭代算法进行优化求解。在多个真实数据集上的实验结果表明,该方法能够挖掘网络不同层的互补信息,得到准确的一致性联合稀疏表示,有效提高社团聚类性能。     

Discover latent discriminant information for dimensionality reduction: Non-negative Sparseness Preserving Embedding

How to define sparse affinity weight matrices is still an open problem in existing manifold learning algorithms. In this paper, we propose a novel unsupervised learning method called Non-negative Sparseness Preserving Embedding (NSPE) for linear dimensionality reduction. Differing from the manifold learning-based subspace learning methods such as Locality Preserving Projections (LPP), Neighbor Preserving Embedding (NPE) and the recently proposed sparse representation based Sparsity Preserving Projections (SPP); NSPE preserves the non-negative sparse reconstruction relationships in low-dimensional subspace. Another novelty of NSPE is the sparseness constraint, which is directly added to control the non-negative sparse representation coefficients. This gives a more ground truth model to imitate the actions of the active neuron cells of V1 of the primate visual cortex on information processing. Although labels are not used in the training steps, the non-negative sparse representation can still discover the latent discriminant information and thus provides better measure coefficients and significant discriminant abilities for feature extraction. Moreover, NSPE is more efficient than the recently proposed sparse representation based SPP algorithm. Comprehensive comparison and extensive experiments show that NSPE has the competitive performance against the unsupervised learning algorithms such as classical PCA and the state-of-the-art techniques: LPP, NPE and SPP.     

Rank–sparsity balanced representation for subspace clustering

Subspace learning has many applications such as motion segmentation and image recognition. The existing algorithms based on self-expressiveness of samples for subspace learning may suffer from the unsuitable balance between the rank and sparsity of the expressive matrix. In this paper, a new model is proposed that can balance the rank and sparsity well. This model adopts the log-determinant function to control the rank of solution. Meanwhile, the diagonals are penalized, rather than the strict zero-restriction on diagonals. This strategy makes the rank–sparsity balance more tunable. We furthermore give a new graph construction from the low-rank and sparse solution, which absorbs the advantages of the graph constructions in the sparse subspace clustering and the low-rank representation for further clustering. Numerical experiments show that the new method, named as RSBR, can significantly increase the accuracy of subspace clustering on the real-world data sets that we tested.     

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

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

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

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

一种改进的局部切空间排列算法

局部切空间排列(LTSA)算法是一种有效的流形学习算法,能较好地学习出高维数据的低维嵌入坐标。数据点的切空间在LTSA算法中起着重要的作用,其局部几何特征多是在样本点的切空间内表示。但是在实际中,LTSA算法是把数据点邻域的样本协方差矩阵的主元所张成的空间当做数据点的切空间,导致了在非均匀采样或样本邻域均值点与样本自身偏离程度较大时,原算法的误差增大,甚至失效。为此,提出一种更严谨的数据点切空间的计算方法,即数据点的邻域矩阵按照数据点本身进行中心化。通过数学推导,证明了在一阶泰勒展开的近似下,提出的计算方法所得到的空间即为数据点自身的切空间。在此基础上,提出了一种改进的局部切空间排列算法,并通过实验结果体现了该方法的有效性和稳定性。与已有经典算法相比,提出的计算方法没有增加任何计算复杂度。     

Locally adaptive subspace and similarity metric learning for visual data clustering and retrieval

Subspace and similarity metric learning are important issues for image and video analysis in the scenarios of both computer vision and multimedia fields. Many real-world applications, such as image clustering/labeling and video indexing/retrieval, involve feature space dimensionality reduction as well as feature matching metric learning. However, the loss of information from dimensionality reduction may degrade the accuracy of similarity matching. In practice, such basic conflicting requirements for both feature representation efficiency and similarity matching accuracy need to be appropriately addressed. In the style of “Thinking Globally and Fitting Locally”, we develop Locally Embedded Analysis (LEA) based solutions for visual data clustering and retrieval. LEA reveals the essential low-dimensional manifold structure of the data by preserving the local nearest neighbor affinity, and allowing a linear subspace embedding through solving a graph embedded eigenvalue decomposition problem. A visual data clustering algorithm, called Locally Embedded Clustering (LEC), and a local similarity metric learning algorithm for robust video retrieval, called Locally Adaptive Retrieval (LAR), are both designed upon the LEA approach, with variations in local affinity graph modeling. For large size database applications, instead of learning a global metric, we localize the metric learning space with kd-tree partition to localities identified by the indexing process. Simulation results demonstrate the effective performance of proposed solutions in both accuracy and speed aspects.     

Locality-constrained nonnegative robust shape interaction subspace clustering and its applications

In this paper, we present a locality-constrained nonnegative robust shape interaction (LNRSI) subspace clustering method. LNRSI integrates the local manifold structure of data into the robust shape interaction (RSI) in a unified formulation, which guarantees the locality and the low-rank property of the optimal affinity graph. Compared with traditional low-rank representation (LRR) learning method, LNRSI can not only pursuit the global structure of data space by low-rank regularization, but also keep the locality manifold, which leads to a sparse and low-rank affinity graph. Due to the clear block-diagonal effect of the affinity graph, LNRSI is robust to noise and occlusions, and achieves a higher rate of correct clustering. The theoretical analysis of the clustering effect is also discussed. An efficient solution based on linearized alternating direction method with adaptive penalty (LADMAP) is built for our method. Finally, we evaluate the performance of LNRSI on both synthetic data and real computer vision tasks, i.e., motion segmentation and handwritten digit clustering. The experimental results show that our LNRSI outperforms several state-of-the-art algorithms.     

基于选择聚类集成的相似流形学习算法

流形学习是当今最重要的研究方向之一.约简维度的选择影响着流形学习方法的性能.当约简维度恰好是本征维度时,更容易发现原始数据的内在性质.然而,本征维度估计仍然是流形学习的一个研究难点.在此基础上,提出了一种新的无监督方法,即基于选择聚类集成的相似流形学习(SML-SCE)算法,避免了对本征维度的估计,并且性能表现良好.SML-SCE利用改进的层次平衡K-means(MBKHK)方法生成具有代表性的锚点,高效地构造相似度矩阵.随后计算得到了多个不同维度下的相似低维嵌入,这些低维嵌入是对原始数据的不同表示,而且不同低维嵌入之间的多样性有利于集成学习.因此,SML-SCE采用选择性聚类集成方法作为结合策略.对于通过K-means聚类得到的相似低维嵌入的聚类结果,采用聚类间的归一化互信息(NMI)作为权重的衡量标准.最后,舍弃权重较低的聚类,采用基于权重的选择性投票方案,得到最终的聚类结果.在多个数据集的大量实验结果表明了该方法的有效性.     

基于图信息的自监督多视角子空间聚类

多视角子空间聚类方法通常用于处理高维度、复杂结构的数据. 现有的大多数多视角子空间聚类方法通过挖掘潜在图信息进行数据分析与处理, 但缺乏对潜在子空间表示的监督过程. 针对这一问题, 本文提出一种新的多视角子空间聚类方法, 即基于图信息的自监督多视角子空间聚类(SMSC). 它将谱聚类与子空间表示相结合形成统一的深度学习框架. SMSC首先通过挖掘多视角数据的一阶图和二阶图构成潜在图信息, 其次利用聚类结果监督多个视角的公共潜在子空间学习过程. 通过在4个标准数据集上进行的广泛实验, 结果验证本文所提方法相较于传统的多视角子空间聚类方法更具有效性.     

联合低秩稀疏的多核子空间聚类算法

针对多核子空间谱聚类算法没有考虑噪声和关系图结构的问题，提出了一种新的联合低秩稀疏的多核子空间聚类算法(JLSMKC)。首先，通过联合低秩与稀疏表示进行子空间学习，使关系图具有低秩和稀疏结构属性；其次，建立鲁棒的多核低秩稀疏约束模型，用于减少噪声对关系图的影响和处理数据的非线性结构；最后，通过多核方法充分利用共识核矩阵来增强关系图质量。7个数据集上的实验结果表明，所提算法JLSMKC在聚类精度(ACC)、标准互信息(NMI)和纯度(Purity)上优于5种流行的多核聚类算法，同时减少了聚类时间，提高了关系图块对角质量。该算法在聚类性能上有较大优势。     

基于联合知识表示学习的多模态实体对齐

基于知识表示学习的实体对齐方法是将多个知识图谱嵌入到低维语义空间,通过计算实体向量之间的相似度实现对齐.现有方法往往关注文本信息而忽视图像信息,导致图像中实体特征信息未得到有效利用.对此,提出一种基于联合知识表示学习的多模态实体对齐方法(ITMEA).该方法联合多模态(图像、文本)数据,采用TransE与TransD相结合的知识表示学习模型,使多模态数据能够嵌入到统一低维语义空间.在低维语义空间中迭代地学习已对齐多模态实体之间的关系,从而实现多模态数据的实体对齐.实验结果表明,ITMEA在WN18-IMG数据集中能够较好地实现多模态实体对齐.     

Incremental Isometric Embedding of High-Dimensional Data Using Connected Neighborhood Graphs

Most nonlinear data embedding methods use bottom-up approaches for capturing the underlying structure of data distributed on a manifold in high dimensional space. These methods often share the first step which defines neighbor points of every data point by building a connected neighborhood graph so that all data points can be embedded to a single coordinate system. These methods are required to work incrementally for dimensionality reduction in many applications. Because input data stream may be under-sampled or skewed from time to time, building connected neighborhood graph is crucial to the success of incremental data embedding using these methods. This paper presents algorithms for updating $k$-edge-connected and $k$-connected neighborhood graphs after a new data point is added or an old data point is deleted. It further utilizes a simple algorithm for updating all-pair shortest distances on the neighborhood graph. Together with incremental classical multidimensional scaling using iterative subspace approximation, this paper devises an incremental version of Isomap with enhancements to deal with under-sampled or unevenly distributed data. Experiments on both synthetic and real-world data sets show that the algorithm is efficient and maintains low dimensional configurations of high dimensional data under various data distributions.