Source-linked AI summary
Unsupervised Feature Selection with Adaptive Structure Learning
Liang Du, Yi-Dong Shen
TL;DR
Unsupervised feature selection must identify informative features while estimating the structures those features should preserve, although noisy and redundant features make this interdependent. FSASL jointly learns global and local structures from selected features and reselects features within a unified framework; benchmark experiments report statistically significant improvements over state-of-the-art methods. The method’s formulation has computational limits involving parameter tuning, eigen-problems, and high-dimensional optimization.
Problem
Existing unsupervised feature-selection methods estimate data structures using all features, allowing redundant and noisy features to contaminate the structures used for selection.
Method
FSASL simultaneously performs feature selection and adaptive global and local structure learning, using selected features to refine both structures within a unified framework.
Results
Comprehensive experiments on benchmark data sets show statistically significant improvement over state-of-the-art feature-selection methods.
Takeaways & Limitations
By coupling the two tasks, FSASL can mutually improve structure characterization and feature selection while refining structures with selected features.
Takeaways & Limitations
FSASL requires tuning three parameters and solving an eigen-problem, while a related optimization can scale as O(d3 + nd2) and require XXT to be non-singular.
Abstract
from arXiv · showhide
The problem of feature selection has raised considerable interests in the past decade. Traditional unsupervised methods select the features which can faithfully preserve the intrinsic structures of data, where the intrinsic structures are estimated using all the input features of data. However, the estimated intrinsic structures are unreliable/inaccurate when the redundant and noisy features are not removed. Therefore, we face a dilemma here: one need the true structures of data to identify the informative features, and one need the informative features to accurately estimate the true structures of data. To address this, we propose a unified learning framework which performs structure learning and feature selection simultaneously. The structures are adaptively learned from the results of feature selection, and the informative features are reselected to preserve the refined structures of data. By leveraging the interactions between these two essential tasks, we are able to capture accurate structures and select more informative features. Experimental results on many benchmark data sets demonstrate that the proposed method outperforms many state of the art unsupervised feature selection methods.
1. INTRODUCTION
Unsupervised feature selection seeks features that preserve data structure, but noisy and redundant features can contaminate the structures used for selection. FSASL addresses this chicken-and-egg problem by jointly and adaptively learning structures and selecting features, with benchmark experiments reporting improvements over state-of-the-art methods.
- Motivation: Unsupervised feature selection aims to retain features that reveal or preserve underlying global, local-manifold, and discriminative data structures.These structures are commonly represented using graph-based models.
- Motivation: Graph-based methods typically estimate structure from all features and then keep the graph fixed while searching for informative features.Selection performance therefore depends strongly on graph-construction quality.
- Motivation: Noisy and irrelevant features can distort the estimated structure, creating a chicken-and-egg dilemma between identifying informative features and characterizing structure accurately.The desired informative subset is unknown before selection.
- Proposed approach: FSASL unifies structure learning and feature selection so each task can iteratively improve the other.It learns global structure through sparse representation and local manifold structure through a probabilistic neighborhood graph based on selected features.
- Results: Comprehensive benchmark experiments report statistically significant improvements over state-of-the-art feature selection methods.The authors present this result as evidence of the proposed method’s effectiveness.
2. RELATED WORKS
Existing unsupervised feature-selection methods depend on estimated data structures, but using all features can contaminate those structures. FSASL jointly updates structure learning and feature selection to refine both global and local structure representations.
- Embedded-method taxonomy: Existing embedded methods differ in whether they detect structure, perform cluster analysis, use feature-selection feedback, or iteratively update structure learning.
- Limitations of existing methods: LLCFS iteratively updates its graph Laplacian using feature relevance, but uses a discrete k-nearest-neighbor graph and separate objectives for structure learning and feature search.
- Proposed framework: FSASL unifies feature selection with structure learning, using each task’s result to improve the other and addressing contamination from redundant and noisy features.
- Unsupervised feature selection: Unsupervised feature selection seeks features that preserve intrinsic data structures without class labels, including global, local manifold, and discriminative structures.
- Adaptive structure learning: The method learns global structure through sparse reconstruction and local manifold structure through a probabilistic neighborhood graph, while selecting features that respect both.
- Optimization: A direct generalized-eigenproblem solution can require O(d^3 + nd^2) computation and a nonsingular XX^T, limiting its appeal for high-dimensional data.
- Optimization: FSASL alternates optimization over its variables, monotonically decreases the objective, and typically requires fewer than 20 iterations in experiments.
4. DISCUSSION
The discussion contrasts FSASL with related feature-selection methods, emphasizing its unified and adaptive learning of global and local structures alongside feature search.
- Unlike LLCFS, FSASL adaptively learns both global and local structures within a unified objective using probabilistic neighborhood relationships.LLCFS explores only local structure, uses a discrete k-nearest graph, and separates structure learning from feature search.
- FSASL preserves both global and local manifold structures, whereas JELSR incorporates only local structure and keeps that local structure unchanged during iterations.FSASL instead adaptively improves both structure characterizations using selected features.
- FSASL uses a probabilistic neighborhood graph that can be refined through feature selection, rather than JELSR's fixed k-nearest-neighbor graph.This refinement is part of FSASL's adaptive structure characterization.
- FSASL captures global structure through sparse representation and refines both global and local structures using selected features, unlike GLSPFS.GLSPFS uses Gaussian-kernel global structure and constructs both structures from all features.
5. EXPERIMENTS
Experiments on eight public datasets evaluate FSASL against established unsupervised feature-selection methods using clustering accuracy and NMI. FSASL improves clustering while selecting fewer than 10% of features, and ablations support combining global and local structures with adaptive updates.
- Experiment Setup: Experiments use eight publicly available datasets spanning digit or letter recognition, face images, objects, and biomedical data.The selected-feature ranges for each dataset are summarized in Table 3.
- Compared Methods: The comparison includes AllFea and nine state-of-the-art unsupervised feature-selection methods, including LapScore, MCFS, UDFS, NDFS, SPFS, RUFS, JELSR, GLSPFS, and LLCFS.Methods represent diverse graph, spectral, local-learning, robust, and embedding-based approaches.
- Clustering with Selected Features: 13.6% higher accuracy and 18.1% higher NMI are achieved by FSASL than clustering with all features while using fewer than 10% of the features.FSASL also outperforms the other nine feature-selection algorithms by 4.77%–38.5% in accuracy and 3.98%–33.8% in NMI.
- Effect of Adaptive Structure Learning: FSASL integrates global and local structures more effectively than using either structure alone, while adaptive structure updates improve each corresponding feature-selection setting.These conclusions are evaluated across six FSASL settings on USPS200 using different numbers of selected features and aggregated results.
- Parameter Sensitivity: Clustering accuracy is relatively insensitive to regularization parameters α, β, and γ across wide ranges but remains relatively sensitive to the number of selected features.The sensitivity analysis uses JAFFE and TOX.
6. CONCLUSION
The proposed method jointly learns global and local structures with feature selection, using each task to improve the other. Its main practical limitations are three parameters to tune and an eigen-problem that is computationally prohibitive for large-scale data.
- Conclusion: FSASL jointly integrates global and local structure learning with feature selection in sparse representation and probabilistic neighborhood frameworks.The method uses feedback between structure learning and feature selection to boost both tasks.
- Conclusion: FSASL requires tuning three parameters, which is computationally cumbersome for real applications.
- Conclusion: Eigen-problem computation in FSASL is computationally prohibitive for large-scale data.The authors plan an iterative algorithm without eigen-decomposition to improve scalability.