| The data representation has been a central problem of data mining, machine learning, pattern recognition and related domains for a long time. With the development of online applications like social networks, the online data is increasing dramatically with various formats, such as text, video and image. An appropriate data representation is essential for the performance of data mining tasks. The base of the data representation is usually the feature space or the dictionary. In. the case that the base is the feature space, the representation can be classified as the problems of feature selection and principal component analysis (PCA). Feature selection aims to obtain a discrete representation of the samples by removing irrelevant and redundant features. PCA achieves a continuous representation vector to find the principal components of the observed data. In the case that the base is dictionary, the problem of representation is to obtain a linear representation of the data based on training samples. The sparse representation is one of the most popular models. To sum up, this dissertation focuses on the problems of feature selection, principal component analysis and the sparse representation model.Though these directions have been developed for years and some efficient algorithms are proposed, it occurs some deficiency while dealing with online data, such as the huge feature space and complicated data types. Specifically, feature selection is usually based on the global feature space which is expensive to obtain; The PCA approximates the rank by the nuclear norm which may not lead to a real low-rank matrix; The sparse representation adopts the ?-norm to obtain a discriminate and sparse representation. However, it may leads to unstable result especially in handling with the dictionary with high correlation. To overcome these drawbacks, this dissertation mainly focuses on the challenges in online situation and our main contributions are summarized as follows.1) In the online scenario, the feature space is expensive and usually in large scale. We address the problem of online feature selection and propose the method of online group feature selection (OGFS). Online feature selection assumes the global sample space is known in advance, the feature selection is performed by the time that the features are generated. Existing online feature selection methods consider the dynamic features but ignore the correlation among the feature stream, which contains semantic information and is important for feature selection. Thus, we assume that there exists semantic information among the features in a group, such as the texture descriptor with a feature group. There is still correlation information among groups of features. Thus, we propose online group feature selection (OGFS) which consists of two stages:online intra-group feature selection and online inter-group feature selection. A novel spectral graph related criterion is employed in the online intra-group feature selection. The features increase the discriminative ability of the selected feature space is thought to be "good" and will be selected. Otherwise, the features will be discarded. To make use of the correlation among feature from different groups, we adopt a sparse regression model Lasso for the online inter-group feature selection. Experimental results in multiple applications, such as image classification and face verification, demonstrate the superiority of our algorithm.2) In the online scenario, the observed data is usually complex. It is shown that the ground truth of the observed can be captured by low-rank structure, while the noise is usually sparse. We address the problem of principal component analysis and propose a joint Schatten-p norm and ?-norm regularized Principle Component Pursuit (p, q-PCP). The real-world data is complicated. The original data is usually with low-rank structure and the noise is usually with the sparse structure, like the background (low rank) and moving objects (sparse) in a surveillance video, the face (low rank) and shadow (sparse) of a human image. The most popular method is RPCA, that is to use the nuclear norm and the e1-norm to approximate the rank and the e0-norm. Though the problem is convex, it may not lead to real low-rank and sparse matrices. To overcome this problem, we propose a joint Schatten-p norm and ?-norm to approximate the rank and the e1-norm, p,q-PCP. A new Proximal Iteratively Reweighted Algorithm (PIRA) is presented to solve the p, q-PCP problem. Our algorithm is based on an alternating direction method of multipliers, where in each iteration we linearize the underlying objective function that allows us to have a closed form solution. We demonstrate that solutions produced by the linearized approximation always converge and have a tighter approximation than the convex counterpart. The effectiveness and efficiency of our algorithm are demonstrated in many applications, such as image denoising, object detection and face shadow/light removal.3) In the online scenario, the classification is difficult with the uncertainty of the online data. We address the problem of sparse representation and propose an adaptive sparse linear model. Based on t he representation, we develop an adaptive sparse representation classifier (ASRC). The sparse representation model (SR) obtains a discriminative representation by the adoption of the e1-norm. However, in the case that the dictionary is high correlatioin (different objects look similar), the e1-norm constraint may lead to unstable representation and deteriorates the performance of data mining. In such case, the collaborative representation (CR) with e2-norm constraint is with superiority by taking the consideration of the coherent structure of the dictionary. Thus, we propose an adaptive sparse representation (ASR) which takes consideration of both the sparsity and the correlation of the dictionary. That is, the representation is adaptive to the exact structure of the dictionary. In the case that the training samples are barely correlated, ASR acts like SR. In the case that the training samples are highly correlated, ASR is equivalent to CR. In general, the sparsity of the representation vector obtained by ASR is between the ones obtained by SR and CR. Based on the adaptive sparse representation model, we propose a related classifier, adaptive sparse representation based classifier (ASRC). The experimental results on the application of face recognition show that our algorithm outperforms the sparse representation based classifier (SRC) and collaborative representation based classifier (CRC). |
PDF Full Text Request