Local coordinates alignment with global preservation for dimensionality reduction

Global and Local Similarity Learning in Multi-Kernel Space for Nonnegative Matrix Factorization

Most of existing nonnegative matrix factorization (NMF) methods do not fully exploit global and local similarity information from data. In this paper, we propose a novel local similarity learning approach in the convex NMF framework, which encourages inter-class separability that is desired for clustering. Thus, the new model is capable of enhancing intra-class similarity and inter-class separability with simultaneous global and local learning. Moreover, the model learns the factor matrices in an augmented kernel space, which is a convex combination of pre-defined kernels with auto-learned weights. Thus, the learnings of cluster structure, representation factor matrix, and the optimal kernel mutually enhance each other in a seamlessly integrated model, which leads to informative representation. Multiplicative updating rules are developed with theoretical convergence guarantee. Extensive experimental results have confirmed the effectiveness of the proposed model.

A generalized l 2,p-norm regression based feature selection algorithm

Feature selection is an important data dimension reduction method, and it has been used widely in applications involving high-dimensional data such as genetic data analysis and image processing. In order to achieve robust feature selection, the latest works apply the l 2 , 1 or l 2 , p -norm of matrix to the loss function and regularization terms in regression, and have achieved encouraging results. However, these existing works rigidly set the matrix norms used in the loss function and the regularization terms to the same l 2 , 1 or l 2 , p -norm, which limit their applications. In addition, the algorithms for solutions they present either have high computational complexity and are not suitable for large data sets, or cannot provide satisfying performance due to the approximate calculation. To address these problems, we present a generalizedl 2 , p -norm regression based feature selection ( l 2 , p -RFS) method based on a new optimization criterion. The criterion extends the optimization criterion of ( l 2 , p -RFS) when the loss function and the regularization terms in regression use different matrix norms. We cast the new optimization criterion in a regression framework without regularization. In this framework, the new optimization criterion can be solved using an iterative re-weighted least squares (IRLS) procedure in which the least squares problem can be solved efficiently by using the least square QR decomposition (LSQR) algorithm. We have conducted extensive experiments to evaluate the proposed algorithm on various well-known data sets of both gene expression and image data sets, and compare it with other related feature selection methods.

Learning Manifold Structures With Subspace Segmentations

Manifold learning has been widely used for dimensionality reduction and feature extraction of data recently. However, in the application of the related algorithms, it often suffers from noisy or unreliable data problems. For example, when the sample data have complex background, occlusions, and/or illuminations, the clustering of data is still a challenging task. To address these issues, we propose a family of novel algorithms for manifold regularized non-negative matrix factorization in this paper. In the algorithms, based on the alpha-beta-divergences, graph regularization with multiple segments is utilized to constrain the data transitivity in data decomposition. By adjusting two tuning parameters, we show that the proposed algorithms can significantly improve the robustness with respect to the images with complex background. The efficiency of the proposed algorithms is confirmed by the experiments on four different datasets. For different initializations and datasets, variations of cost functions and decomposition data elements in the learning are presented to show the convergent properties of the algorithms.

Learning to Map Social Network Users by Unified Manifold Alignment on Hypergraph

Nowadays, a lot of people possess accounts on multiple online social networks, e.g., Facebook and Twitter. These networks are overlapped, but the correspondences between their users are not explicitly given. Mapping common users across these social networks will be beneficial for applications such as cross-network recommendation. In recent years, a lot of mapping algorithms have been proposed which exploited social and/or profile relations between users from different networks. However, there is still a lack of unified mapping framework which can well exploit high-order relational information in both social structures and profiles. In this paper, we propose a unified hypergraph learning framework named unified manifold alignment on hypergraph (UMAH) for this task. UMAH models social structures and user profile relations in a unified hypergraph where the relative weights of profile hyperedges are determined automatically. Given a set of training user correspondences, a common subspace is learned by preserving the hypergraph structure as well as the correspondence relations of labeled users. UMAH intrinsically performs semisupervised manifold alignment with profile information for calibration. For a target user in one network, UMAH ranks all the users in the other network by their probabilities of being the corresponding user (measured by similarity in the subspace). In experiments, we evaluate UMAH on three real world data sets and compare it to state-of-art baseline methods. Experimental results have demonstrated the effectiveness of UMAH in mapping users across networks.

Manifold Warp Segmentation of Human Action

Human action segmentation is important for human action analysis, which is a highly active research area. Most segmentation methods are based on clustering or numerical descriptors, which are only related to data, and consider no relationship between the data and physical characteristics of human actions. Physical characteristics of human motions are those that can be directly perceived by human beings, such as speed, acceleration, continuity, and so on, which are quite helpful in detecting human motion segment points. We propose a new physical-based descriptor of human action by curvature sequence warp space alignment (CSWSA) approach for sequence segmentation in this paper. Furthermore, time series-warp metric curvature segmentation method is constructed by the proposed descriptor and CSWSA. In our segmentation method, descriptor can express the changes of human actions, and CSWSA is an auxiliary method to give suggestions for segmentation. The experimental results show that our segmentation method is effective in both CMU human motion and video-based data sets.

On the Equivalence of HLLE and LTSA

Among the representative algorithms of manifold learning, Hessian locally linear embedding (HLLE) and local tangent space alignment (LTSA) algorithms haven been regarded as two different algorithms. However, in practice, the effects of these two algorithms are very similar and LTSA performs better than HLLE in some applications. This paper tries to account for this phenomenon from a mathematical point of view. There are only two differences between HLLE and LTSA. First, LTSA includes a data point into its neighborhood, while HLLE does not. Second, HLLE and LTSA use different methods to align the local coordinates of manifold. In this paper, we show that, the first difference between HLLE and LTSA is not essential. However, from the viewpoint of data utilization, LTSA does better than HLLE in the neighborhood construction. This may account for why LTSA can perform better than HLLE in some applications. As for the second difference between HLLE and LTSA, we first prove that, the alignment equations used by HLLE and LTSA are exactly the same. Second, we prove that, although HLLE and LTSA uses different methods to solve the alignment equation, their solutions are exactly the same, provided that HLLE adopts the same method as LTSA to construct the neighborhoods. Based on these arguments, we claim that HLLE and LTSA are equivalent to each other. This conclusion can also be verified experimentally by using manifold learning MATLAB demo (MANI), a widely-used experimental platform of manifold learning. When testing HLLE on MANI, if HLLE adopts the same method as LTSA to construct the neighborhoods, the experimental results presented by MANI will be the same as those of LTSA.

Effective Discriminative Feature Selection With Nontrivial Solution

Feature selection and feature transformation, the two main ways to reduce dimensionality, are often presented separately. In this paper, a feature selection method is proposed by combining the popular transformation-based dimensionality reduction method linear discriminant analysis (LDA) and sparsity regularization. We impose row sparsity on the transformation matrix of LDA through l2,1-norm regularization to achieve feature selection, and the resultant formulation optimizes for selecting the most discriminative features and removing the redundant ones simultaneously. The formulation is extended to the l2,p-norm regularized case, which is more likely to offer better sparsity when 0 < p < 1. Thus, the formulation is a better approximation to the feature selection problem. An efficient algorithm is developed to solve the l2,p-norm-based optimization problem and it is proved that the algorithm converges when 0 < p ≤ 2. Systematical experiments are conducted to understand the work of the proposed method. Promising experimental results on various types of real-world data sets demonstrate the effectiveness of our algorithm.

Dimensionality Reduction for Hyperspectral Data Based on Class-Aware Tensor Neighborhood Graph and Patch Alignment

To take full advantage of hyperspectral information, to avoid data redundancy and to address the curse of dimensionality concern, dimensionality reduction (DR) becomes particularly important to analyze hyperspectral data. Exploring the tensor characteristic of hyperspectral data, a DR algorithm based on class-aware tensor neighborhood graph and patch alignment is proposed here. First, hyperspectral data are represented in the tensor form through a window field to keep the spatial information of each pixel. Second, using a tensor distance criterion, a class-aware tensor neighborhood graph containing discriminating information is obtained. In the third step, employing the patch alignment framework extended to the tensor space, we can obtain global optimal spectral-spatial information. Finally, the solution of the tensor subspace is calculated using an iterative method and low-dimensional projection matrixes for hyperspectral data are obtained accordingly. The proposed method effectively explores the spectral and spatial information in hyperspectral data simultaneously. Experimental results on 3 real hyperspectral datasets show that, compared with some popular vector- and tensor-based DR algorithms, the proposed method can yield better performance with less tensor training samples required.

Discriminative embedded clustering: a framework for grouping high-dimensional data

In many real applications of machine learning and data mining, we are often confronted with high-dimensional data. How to cluster high-dimensional data is still a challenging problem due to the curse of dimensionality. In this paper, we try to address this problem using joint dimensionality reduction and clustering. Different from traditional approaches that conduct dimensionality reduction and clustering in sequence, we propose a novel framework referred to as discriminative embedded clustering which alternates them iteratively. Within this framework, we are able not only to view several traditional approaches and reveal their intrinsic relationships, but also to be stimulated to develop a new method. We also propose an effective approach for solving the formulated nonconvex optimization problem. Comprehensive analyses, including convergence behavior, parameter determination, and computational complexity, together with the relationship to other related approaches, are also presented. Plenty of experimental results on benchmark data sets illustrate that the proposed method outperforms related state-of-the-art clustering approaches and existing joint dimensionality reduction and clustering methods.

Hybrid manifold embedding

In this brief, we present a novel supervised manifold learning framework dubbed hybrid manifold embedding (HyME). Unlike most of the existing supervised manifold learning algorithms that give linear explicit mapping functions, the HyME aims to provide a more general nonlinear explicit mapping function by performing a two-layer learning procedure. In the first layer, a new clustering strategy called geodesic clustering is proposed to divide the original data set into several subsets with minimum nonlinearity. In the second layer, a supervised dimensionality reduction scheme called locally conjugate discriminant projection is performed on each subset for maximizing the discriminant information and minimizing the dimension redundancy simultaneously in the reduced low-dimensional space. By integrating these two layers in a unified mapping function, a supervised manifold embedding framework is established to describe both global and local manifold structure as well as to preserve the discriminative ability in the learned subspace. Experiments on various data sets validate the effectiveness of the proposed method.