Research On Feature Extraction And Feature Selection

In data mining and machine learning the prepared data usually contain multitudes of features withsmall sample size, which presents a big challenge for the orthodox approaches to retrieve usefulinformation. Feature extraction and feature selection are usually exploited to circumvent this poblem.Both methods aim to extract the most relevant features, eliminate the irrelevant and noisy features,and make the data analysis feasible. In this paper we will investigate these methods thoroughly topropose some improved algorithms, alleviating the small sample size and computational inefficiencydifficulties. The main contributions are listed as follows:1. A discriminant projection algorithm based on the k-nearest neighbor local margin is proposed.The hypothesis margin is introduced to measure the local discriminative power, i.e. the data points ofthe same class should be close to each other while the data points of different classes should be farfrom each other in the neighborhood. The local margin is projected into a linear low-dimensionalsubspace within which the neighborhood relationship is preserved. Maximizing the sum of theprojected local margins we obtain the global transforming matrix. To reduce the computation forfinding the inverse of the square matrix, the Gram-Schmidt orthogonalization is applied. Finally, theconnection between the algorithm and Local Linear Embedding (LLE) is explored and we note thatthe proposed algorithm can be considered as the variant of the LLE for discriminant analysis.2. The aforementioned feature extraction algorithm is extended to the semi-supervised case usingthe abundant unlabeled data points. The labeled data points are employed to separate the classes,while the unlabeled data points contribute to maintain the local structure. Similar to the supervisedcase the local margin including both the labeled and unlabeled data is projected into alow-dimensional subspace, from which a linear operator can be derived. The experimental resultsdemonstrate that the semi-supervised feature extraction algorithm can not only present superiorclassification accuracy, but also find different sub-manifold in the low-dimensional space.3. Spectral clustering algorithm has been demonstrated to be an effective unsupervised learningmethod. The spectral graph theory indicates that the eigenvalues and eigenvectors of the graphLaplacian are closely related with the clustering results. We prove that the distribution of theeigenvalues describes the distinctness of clusters and the eigenvectors implicitly present the targetvalues of the samples when normalized graph Laplacian is adopted. Based on this finding we proposea feature significance weighting algorithm. The feature weighting algorithm might be computationallyexpensive due to the involved eigen-decomposition of the Laplacian matrix, hence the Nystr m method is applied to reduce the computational cost.4. Motivated by the manifold learning, we rank the feature relevance according to thediscriminative capability of each feature in the local space of the data. Specifically, assuming that theimportant features will force the data points of the same class to maintain their intrinsic neighborrelations, whereas neighboring points of different classes no longer to stick to one another, we derivean optimization problem weighting each feature. Two ranking criteria, i.e. the difference criterion andquotient criterion, produce two feature selection algorithms. The algorithms do not contain the densematrix eigen-decomposition which might be time-consuming.We further measure the local structure of the data set in the feature weighted space using the mixedlabeled and unlabeled data points and incorporate it into the supervised formulation. From the featureweighting framework we derive two feature ranking algorithms, i.e. Semi-supervised Feature Rankingby Linear Discriminant Analysis (SFRLDA) and Semi-supervised Feature Ranking by DiscriminantNeighborhood Analysis (SFRDNE). The former is suitable for linearly separable problems, while thelatter is suitable for nonlinear separable problems.