Abstract
In many data analysis tasks, one is often confronted with the problem of selecting features from very high dimensional data. Most existing feature selection methods focus on ranking individual features based on a utility criterion, and select the optimal feature set in a greedy manner. However, the feature combinations found in this way do not give optimal classification performance, since they neglect the correlations among features. While the labeled data required by supervised feature selection can be scarce, there is usually no shortage of unlabeled data. In this paper, we propose a novel hypergraph based semi-supervised feature selection algorithm to select relevant features using both labeled and unlabeled data. There are two main contributions in this paper. The first is that by incorporating multidimensional interaction information (MII) for higher order similarities measure, we establish a novel hypergraph framework which is used for characterizing the multiple relationships within a set of samples. Thus, the structural information latent in the data can be more effectively modeled. Secondly, we derive a hypergraph subspace learning view of feature selection which casting the feature discriminant analysis into a regression framework that considers the correlations among features. As a result, we can evaluate joint feature combinations, rather than being confined to consider them individually. Experimental results demonstrate the effectiveness of our feature selection method on a number of standard face data-sets.
Introduction
In fields such as computer vision and bioinformatics, researchers frequently encounter "high-dimensional, low-sample-size" data. Traditional feature selection methods often fall into two primary traps. First, the Greedy Trap involves ranking features individually and selecting the top $N$. This approach ignores feature correlations, leading to redundancy where multiple selected features provide identical information. Second, the Pairwise Trap relies on standard graphs to model data similarity. However, simple pairwise relationships often fail to capture the complex underlying structure of high-dimensional data.
As illustrated in Figure 1, defining a similarity measure for images of a surface under varying illumination often requires considering multiple images simultaneously—a relationship that standard graphs cannot represent. To address these issues, this paper introduces a semi-supervised feature selection method that leverages hypergraphs and Multidimensional Interaction Information (MII) to capture higher-order relationships while utilizing both labeled and unlabeled data.
Methodology: The HG+Semi Framework
The proposed HG+Semi (Hypergraph Semi-supervised feature selection) framework operates in three main stages:
1. Hypergraph Construction via MII
Unlike standard graphs where edges connect only two nodes, a $K$-uniform hypergraph uses hyperedges to connect $K$ nodes. The authors utilize Multidimensional Interaction Information (MII) to weight these edges. MII quantifies the "extra" information shared by a group of samples that is not apparent when examining smaller subsets, allowing for a more robust characterization of data manifolds.
2. Hypergraph to Graph Transformation
Since the mathematical representation of hypergraphs (tensors) is computationally intensive to decompose, the framework employs a "clique average" method. This approximates the hypergraph as a standard adjacency matrix while preserving the higher-order structural information captured during the MII phase.
3. Semi-supervised Subspace Learning
The final stage casts feature selection as a regression problem:
- Label Propagation: The graph structure is used to "spread" labels from a small labeled set to a larger unlabeled set. This process includes an "outlier class" to mitigate the impact of noise.
- Label Regression: By treating feature selection as a regression task with an $\ell_1$-norm constraint (similar to Lasso), the model is forced to select a sparse, non-redundant set of features. The Least Angle Regression (LARs) algorithm is used to identify the feature combinations that best reconstruct the predicted labels.
Experimental Evaluation
The HG+Semi method was evaluated on three standard face-recognition benchmarks characterized by high dimensionality and significant variations in lighting, expression, and occlusion:
- ORL: 400 images across 40 classes.
- CMU PIE: 1,428 images across 68 classes, specifically focused on varying illumination.
- AR: 130 images across 10 classes, including occlusions such as sunglasses and scarves.
Key Results
The proposed method consistently outperformed state-of-the-art supervised (MRMR, Fisher Score) and unsupervised (Laplacian Score, SPEC, UDFS) techniques:
- Accuracy: On the ORL dataset, HG+Semi achieved 93% accuracy with only 88 features, significantly higher than the 83.5% achieved by MRMR with 95 features.
- Efficiency: On the CMU PIE dataset, HG+Semi reached peak performance with fewer than 20 features, whereas competing methods required over 100 features for comparable results.
- Redundancy Reduction: Quantitative tests confirmed that features selected by HG+Semi had the lowest Redundancy Rate (RED) across all datasets, validating the effectiveness of the joint regression framework.
Conclusion
The HG+Semi framework demonstrates that moving beyond pairwise relationships to capture "group dynamics" through hypergraphs significantly improves feature selection in high-dimensional spaces. By evaluating features jointly rather than individually, the method naturally penalizes redundancy and preserves the natural manifold structure of the data. While computational complexity for large $K$ values remains a challenge, this hypergraph-based approach provides a powerful tool for semi-supervised learning in complex domains.
Summary updated