PaperlayerView exact revision on arXiv

Source-linked AI summary

Feature Selection: A Data Perspective

Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P. Trevino, Jiliang Tang, Huan Liu

arXiv:1601.07996v5cs.LG

TL;DR

High-dimensional and expanding data settings make feature selection important for preparing data and addressing challenges associated with dimensionality, structure, heterogeneity, and streaming. The survey organizes representative algorithms across these data settings, groups conventional methods into four technical categories, and provides a repository and evaluation example. It also identifies scalability, stability, model-selection, and streaming-storage challenges for future research.

  • Problem

    The proliferation of high-dimensional, structured, heterogeneous, and streaming data creates challenges for feature-selection methods designed for simpler data settings.

  • Method

    The survey reviews representative algorithms across conventional, structured, heterogeneous, and streaming data, categorizing conventional methods into four technical groups and releasing a repository.

  • Results

    The survey provides a comprehensive, structured overview of feature-selection algorithms and presents an open-source repository containing representative methods.

  • Takeaways & Limitations

    Feature-selection research can be examined through data characteristics alongside algorithmic technique, with the repository supporting evaluation and continued community development.

  • Takeaways & Limitations

    Scalability remains constrained because large datasets may not fit in memory and many methods have time complexity proportional to O(d^2) or O(d)^3.

Abstract

from arXiv · show

Feature selection, as a data preprocessing strategy, has been proven to be effective and efficient in preparing data (especially high-dimensional data) for various data mining and machine learning problems. The objectives of feature selection include: building simpler and more comprehensible models, improving data mining performance, and preparing clean, understandable data. The recent proliferation of big data has presented some substantial challenges and opportunities to feature selection. In this survey, we provide a comprehensive and structured overview of recent advances in feature selection research. Motivated by current challenges and opportunities in the era of big data, we revisit feature selection research from a data perspective and review representative feature selection algorithms for conventional data, structured data, heterogeneous data and streaming data. Methodologically, to emphasize the differences and similarities of most existing feature selection algorithms for conventional data, we categorize them into four main groups: similarity based, information theoretical based, sparse learning based and statistical based methods. To facilitate and promote the research in this community, we also present an open-source feature selection repository that consists of most of the popular feature selection algorithms (\url{http://featureselection.asu.edu/}). Also, we use it as an example to show how to evaluate feature selection algorithms. At the end of the survey, we present a discussion about some open problems and challenges that require more attention in future research.

1. INTRODUCTION

High-dimensional and increasingly heterogeneous, structured, and streaming data create challenges that motivate feature selection. The survey organizes feature-selection research from a data perspective and provides a repository covering representative algorithms.

  • Motivation: High-dimensional data become sparse, encourage overfitting, and increase memory and computational costs.These effects are described as the curse of dimensionality and can degrade performance on unseen data.
  • Motivation: Feature selection directly selects relevant original features, preserving their physical meaning while supporting dimensionality reduction.Feature extraction instead constructs new features as combinations of the originals, which can hinder further analysis.
  • Motivation: Removing irrelevant, redundant, and noisy features can reduce storage and computation without significant information loss or learning-performance degradation.The paper illustrates redundancy through strongly correlated features and irrelevance through features unable to separate classes.
  • Existing perspectives: Feature-selection methods may be supervised, unsupervised, or semi-supervised, and may use wrapper, filter, or embedded strategies.Semi-supervised methods exploit both labeled and unlabeled samples when labeled data are limited.
  • Survey scope: The survey covers conventional, structured, heterogeneous, and streaming data, grouping conventional methods into similarity, information-theoretical, sparse-learning, and statistical categories.Wrapper methods are excluded from the four technical categories because they are computationally expensive and application-specific.
  • Survey scope: The authors release scikit-feature, a Python repository containing near 40 representative feature-selection algorithms.The repository is built on scikit-learn, NumPy, and SciPy and is intended to facilitate research.

2. FEATURE SELECTION ON CONVENTIONAL DATA

Traditional feature-selection algorithms for conventional data are broadly organized by technique. The survey identifies four principal groups and an additional category for methods that do not fit them.

  • Technical categories: Similarity-based methods select features using similarity-related criteria.
  • Technical categories: Information-theoretical, sparse-learning, and statistical methods form three additional groups for conventional-data feature selection.
  • Technical categories: Other methods are retained separately when their techniques do not fit the four main categories.

2.1. Similarity based Methods

Similarity-based methods define feature relevance through data similarity, using affinity structures to identify features that preserve local or class-related relationships. The survey unifies several supervised and unsupervised algorithms under utility maximization, while noting that redundancy remains a major limitation.

  • Similarity-based methods assess feature importance by how well features preserve data similarity derived from labels or distance metrics.
  • The unified framework selects a feature subset that maximizes utility for preserving the data manifold encoded by an affinity matrix.
  • Laplacian Score: Laplacian Score constructs an affinity matrix and Laplacian, then greedily selects the k features with the smallest individual scores.
  • SPEC: SPEC extends Laplacian Score to supervised and unsupervised settings and evaluates feature relevance through three spectral criteria.
  • Fisher Score: Fisher Score favors features with similar values within classes and dissimilar values across classes, selecting features with the largest scores.
  • Trace ratio directly targets a globally optimal subset but lacks a closed-form solution, whereas ReliefF can be reduced to the same utility-maximization framework.

2.2. Information Theoretical based Methods

Information-theoretical methods use heuristic information measures to select features that are relevant to class labels while controlling redundancy or encouraging complementary information. Their main scope limitations are reliance on supervision and the need to discretize continuous variables.

  • Information-theoretical methods use heuristic filter criteria to measure feature importance, commonly balancing feature relevance and feature redundancy.
  • Mutual information measures shared information between variables, is symmetric, and equals zero when discrete variables are independent.
  • MIM: MIM ranks features individually by correlation with class labels, selecting the highest-scoring features while ignoring feature redundancy.
  • MIFS and MRMR incorporate redundancy penalties, with MRMR reducing redundancy’s effect as the selected feature set grows.
  • JMI seeks features complementary to those already selected given class labels, whereas CMIM maximizes conditional mutual information to retain predictive ability and reduce redundancy.

Double Input Symmetrical Relevance

Double Input Symmetrical Relevance methods address feature selection by considering both feature–class correlation and feature–feature correlation. FCBF uses symmetrical uncertainty thresholds and redundancy tests to retain predominant, class-relevant features.

  • DISR: DISR normalizes mutual information and can be reduced to a nonlinear combination of Shannon information terms.
  • FCBF: FCBF simultaneously exploits feature–class and feature–feature correlations using a predefined symmetrical-uncertainty threshold δ.
  • FCBF: A feature is predominant when its class association reaches δ and no other retained feature has stronger association with it than with the class.
  • FCBF: FCBF partitions redundant features according to whether another feature has greater or weaker class association, then applies heuristics to remove redundancy.
  • Discussion: Unlike similarity-based methods, information-theoretical approaches generally model both feature relevance and redundancy, although they are usually limited to supervised discrete data.

2.3. Sparse Learning based Methods

Sparse-learning methods select features by combining predictive loss with sparsity-inducing regularization, driving unnecessary coefficients toward zero. The survey covers single- and multi-target settings, including convex relaxations and unsupervised graph-based extensions.

  • Sparse-learning methods minimize fitting error with regularization that makes many feature coefficients small or exactly zero.
  • ℓ0-norm regularization seeks the optimal nonzero feature set but is difficult to optimize, so ℓ1-norm regularization provides a tight convex relaxation.
  • Multi-class and multivariate problems seek parameter sparsity patterns shared across multiple predictive targets.
  • Features in multi-target models are ranked by row-wise coefficient magnitude, with larger values indicating greater feature importance.
  • The ℓ2,0-norm formulation is NP-hard and non-convex, while iterative algorithms or alternative ℓ2,q-norm formulations provide tractable solution strategies.
  • ℓ2,1-norm and ℓ∞,1-norm regularizers promote joint feature sparsity across multiple targets, and REFS combines ℓ2,1-norm loss and regularization for noise robustness.
  • Unsupervised methods such as MCFS construct graph-based embeddings and use sparse regression to score features without class labels.

2.4. Statistical based Methods

Statistical feature-selection methods use predefined statistical measures, usually in filter-based procedures, to assess feature relevance. They are simple and computationally efficient, but individual feature analysis can ignore redundancy.

  • Statistical methods use predefined measures to assess feature relevance, and most are filter-based methods that analyze features individually.
  • Statistical measures: Low Variance prunes features whose variance falls below a predefined threshold, including constant features that cannot discriminate instances.For boolean features, variance is computed as p(1 −p).
  • Statistical measures: T-score ranks binary-classification features by the statistical difference between class means relative to class variance.Higher t-scores indicate more important features.
  • Statistical measures: Chi-square evaluates feature–class independence, with higher scores indicating relatively more important features.
  • Statistical measures: Gini index quantifies class-separation ability; unlike the other described measures, lower values indicate more relevant features.For binary classification, the index can reach 0.5 and also applies to multiclass classification.
  • Subset-based measures: CFS evaluates subsets using predictive power and redundancy, favoring strong feature–class correlation and weak feature–feature intercorrelation.Its heuristic merit uses symmetrical uncertainty to obtain both correlation types.
  • Statistical methods are often used as low-cost preprocessing before more sophisticated algorithms, but individual evaluation inevitably ignores feature redundancy.

2.5. Other Methods

The survey reviews hybrid, deep-learning-based, and reconstruction-based feature-selection methods beyond its four main categories. These approaches address instability, representation learning, or preservation of the original data structure.

  • Hybrid methods: Hybrid methods ensemble feature subsets from different algorithms or samples, then aggregate them into a consensus result.Their two stages are constructing diverse selection results and aggregating the outputs.
  • Hybrid methods: Ensembling can alleviate instability and perturbation in individual feature-selection algorithms and enhance subsequent learning tasks.
  • Deep learning-based methods: Deep learning learns new feature representations, whereas feature selection directly identifies relevant original features and therefore produces more human-readable results.
  • Reconstruction-based methods: Reconstruction-based selection defines feature relevance by how well selected features approximate the original data through a reconstruction function.
  • Reconstruction-based methods: CPFS formulates unsupervised feature selection as convex optimization minimizing mean-squared reconstruction error with linear and sparsity constraints.
  • Reconstruction-based methods: Graph-regularized reconstruction selects features that preserve the original data manifold while reconstructing samples linearly.

3. FEATURE SELECTION WITH STRUCTURED FEATURES

Structured feature selection incorporates groups, trees, or graphs among features instead of assuming a flat independent structure. Structural regularization can improve subsequent learning, but it raises computational and structure-inference challenges.

  • Conventional methods often assume features are independent, whereas structured methods explicitly model group, tree, and graph relationships.The survey motivates structure-aware selection with spatial organization, disjoint or overlapping groups, trees, and graphs.
  • Structured selection minimizes empirical loss with a sparse regularization term that incorporates feature structure G and balances loss against structural regularization.
  • Group structures: Group Lasso selects or ignores entire feature groups, unlike Lasso, which selects individual features without using group structure.In the illustration, Group Lasso selects groups G2 and G4 while excluding G1 and G3.
  • Group structures: Sparse Group Lasso combines inter-group and intra-group sparsity, allowing selection of individual features within selected groups.Its parameter α balances the two sparsity contributions.
  • Tree structures: Tree-guided Group Lasso represents features as leaves and internal nodes as feature groups, with weights reflecting subtree height or correlation tightness.The example organizes eight features in an indexed tree of depth 3.
  • Tree structures: Tree-guided selection imposes hierarchical constraints: same-level internal nodes do not overlap, child features are subsets of parent features, and an unselected parent prevents selecting its children.
  • Graph structures: Graph Lasso encourages connected features with strong dependencies to be selected together and assigned similar coefficients.It adds a graph regularizer to Lasso, with larger edge weights enforcing greater coefficient similarity.

4. FEATURE SELECTION WITH HETEROGENEOUS DATA

Heterogeneous-data feature selection addresses multiple sources and linked instances, where traditional i.i.d. assumptions are inadequate. Reviewed methods integrate content, labels or pseudo-labels, links, latent representations, and multi-source geometry.

  • Heterogeneous data violates the single-source i.i.d. assumption because instances may combine noisy, partial, redundant, or linked information from multiple sources.
  • Linked data: Linked data supplements feature attributes with relational information represented by an adjacency matrix, as in social and biological networks.
  • Linked data: FSNet combines a linear classifier for content and labels with graph regularization to incorporate links during supervised feature selection.Its graph assumption is that linked instances are likely to have similar class labels.
  • Linked data: Social-media feature selection can integrate CoPost, CoFollowing, CoFollowed, and Following relations, with parameters controlling sparsity and relation contributions.
  • Linked data: LUFS performs unsupervised selection on linked data using pseudo-labels, latent factors from network structure, feature affinity, and row-sparse regularization.
  • Linked data: LUFS depends heavily on latent representations and can be jeopardized by noisy links, whereas NetFS embeds latent representation learning into feature selection to make the phases mutually supportive.
  • Multiple data sources: For multiple sources describing the same instances, a global geometric pattern can be formed by linearly combining source-specific affinity matrices.The coefficient αi controls each source’s contribution.
  • Multiple data sources: GPCOVvar selects features with the highest covariance variances, while GPCOVspca applies Sparse Principal Component Analysis to the geometry-dependent covariance matrix.

4.3. Feature Selection Algorithms with Multi-View Data

Multi-view feature selection selects features across dependent feature spaces by exploiting relations among views. Representative methods combine clustering, similarity, pseudo-labels, and structured sparsity, while scalability remains an open challenge for heterogeneous data.

  • 4.3. Feature Selection Algorithms with Multi-View Data: Multi-view feature selection selects features from different feature spaces simultaneously by using relations among views.The paper motivates this setting with image pixels, tags, and terms as multiple views of the same instances.
  • 4.3. Feature Selection Algorithms with Multi-View Data: AUMFS combines cluster structure, data similarity, and correlations among views to learn shared pseudo-labels and feature weights.It uses ℓ2,1-norm regularized least squares and joint spectral clustering across view-specific affinity matrices.
  • 4.3. Feature Selection Algorithms with Multi-View Data: MVFS differs from AUMFS by learning one feature weight matrix for each view while using spectral clustering to obtain pseudo-labels.
  • 4.3. Feature Selection Algorithms with Multi-View Data: Joint group ℓ1-norm and ℓ2,1-norm regularization produces view-wise sparsity and feature sparsity within selected views.The group penalty captures global relations across views, while the ℓ2,1-norm regularizer selects features among those views.
  • 4.3. Feature Selection Algorithms with Multi-View Data: Heterogeneous-data feature selection can fuse multiple data types, but matrix-based optimization often requires expensive operations that limit scalability.The survey identifies efficient and distributed algorithms as an open research direction.

5. FEATURE SELECTION WITH STREAMING DATA

Streaming feature selection addresses continuously arriving instances or features when data may be too large, unknown, or impossible to rescan. The surveyed methods use online acceptance, sparsity, statistical control, redundancy removal, and sketching, but storage and repeated passes remain limitations.

  • 5. FEATURE SELECTION WITH STREAMING DATA: Streaming feature selection handles data or features that arrive continuously, often requiring timely selection without loading all data into memory.Traditional batch methods are impractical when new samples or features arrive and a single scan is preferred.
  • 5.1.1. Grafting Algorithm: Grafting accepts a newly arriving feature when its loss reduction outweighs the added ℓ1-norm penalty, then reoptimizes current parameters to remove outdated features.It uses a conjugate-gradient procedure after accepted features are incorporated.
  • 5.1. Streaming Feature Selection: Alpha-investing dynamically changes the acceptance threshold to control the false discovery rate of newly arrived features.Its threshold is adjusted through a wealth value representing the acceptable number of false positives at the current time.
  • 5.1. Streaming Feature Selection: Online redundancy analysis can retain strongly relevant, non-redundant features while eliminating selected features conditionally independent of the class label.The surveyed approach maintains best candidate features and uses a Markov Blanket criterion for redundancy removal.
  • 5.2. Feature Selection with Data Streams: Unsupervised streaming methods address unlabeled streams using source information, gradient tests, or matrix sketching with limited storage and one data pass.FSDS maintains a low-rank approximation before applying regularized regression to obtain feature coefficients.
  • 5. FEATURE SELECTION WITH STREAMING DATA: Most streaming methods still require multiple data passes or historical storage, motivating algorithms effective under limited memory or disk capacity.

6. PERFORMANCE EVALUATION

The paper introduces scikit-feature as an open-source repository for applying, comparing, and jointly studying feature selection algorithms, then illustrates evaluation procedures for supervised and unsupervised methods. Its evaluation framework varies by output type, learning setting, and feature-selection task.

  • 6.1. Feature Selection Repository: Scikit-feature collects widely used feature selection algorithms to facilitate their application, comparison, joint study, and more reliable evaluation.
  • 6.1. Feature Selection Repository: The repository is implemented in Python and contains around 40 algorithms alongside benchmark datasets and evaluation resources.It is built on scikit-learn, NumPy, and SciPy, with a project website providing additional resources.
  • 6. PERFORMANCE EVALUATION: The repository lists applicable algorithms and their classification or clustering evaluations for each dataset.
  • 6.2. Evaluation Methods and Metrics: Feature-weighting methods are evaluated by assessing the top {5, 10, 15, ..., 295, 300} features, while subset methods are evaluated according to their selected features.
  • 6.2. Evaluation Methods and Metrics: Supervised evaluation selects features on a training set and tests a classifier on the selected test features using classification accuracy and additional metrics.
  • 6.2. Evaluation Methods and Metrics: Unsupervised evaluation applies K-means to selected features, repeating clustering 20 times and reporting average performance using NMI and ACC.
  • 6.2. Evaluation Methods and Metrics: The survey records each algorithm’s data type, label usage, output form, feature type, and supervised-task characteristics.The paper focuses its supervised-method metadata on classification, while noting that regression feature selection is also supervised.

7. OPEN PROBLEMS AND CHALLENGES

The survey identifies unresolved challenges in making feature selection scalable, stable, and appropriately tuned for large and weakly labeled data. Key difficulties include computational growth, limited understanding of unsupervised stability, and choosing model parameters such as feature and cluster counts.

  • 7.1. Scalability: Most feature selection algorithms may not scale to terabyte or ultrahigh-dimensional datasets, motivating distributed methods and linear or sublinear running times.Existing methods often have time complexity proportional to O(d^2) or O(d)^3, where d is the feature dimension.
  • 7.2. Stability: Feature-selection stability measures sensitivity to perturbations in training data, but stability for unsupervised methods remains insufficiently studied.Unsupervised stability is harder to study because prior knowledge about the data’s cluster structure is limited.
  • 7.3. Model Selection: Selecting the optimal number of features remains an open problem because too many features may add noise and redundancy, while too few may discard relevant features.Grid-searching candidate feature counts can be computationally expensive.
  • 7.3. Model Selection: Unsupervised feature selection also requires specifying the number of clusters or pseudo classes despite limited knowledge of the underlying clustering structure.Different cluster counts may merge distinct small clusters into one larger cluster.

8. CONCLUSION

Feature selection is presented as a practically significant preprocessing strategy for reducing dimensionality and supporting data mining and machine learning. The survey organizes methods across data types, categorizes conventional methods by technique, analyzes their strengths and shortcomings, and provides a repository to facilitate research.

  • 8. CONCLUSION: Feature selection reduces data dimensionality while supporting simpler models and improved data mining performance.It is described as effective preprocessing with practical significance across statistics, pattern recognition, machine learning, and data mining.
  • 8. CONCLUSION: The survey covers conventional, structured, heterogeneous, and streaming data, with conventional methods grouped into similarity, information theoretical, sparse learning, and statistical approaches.Structured features include group, tree, and graph features; heterogeneous data includes linked, multi-source, and multi-view data.
  • 8. CONCLUSION: The accompanying scikit-feature repository includes popular feature selection algorithms and is used to facilitate research and illustrate algorithm evaluation.The repository is presented as part of the survey’s contribution to the feature-selection research community.
Loading 1601.07996v5…