Online Group Feature Selection

Jing Wang, Zhong-Qiu Zhao, Xuegang Hu, Yiu-ming Cheung, Meng Wang, Xindong WuIJCAI 2013

TL;DR

This paper introduces Online Group Feature Selection (OGFS), a novel approach for dynamically selecting relevant features in streaming data where features arrive in groups. OGFS addresses the limitations of existing methods by considering feature relationships within groups, leading to improved classification accuracy and feature subset compactness.

What Problem Does This Paper Address?

In many real-world applications like image analysis and spam filtering, data streams are characterized by features arriving dynamically. Traditional feature selection methods, which assume all features are available upfront, are inefficient or impractical in these scenarios. Existing "online" feature selection methods, while handling dynamic feature arrival, typically evaluate features individually, ignoring potentially crucial relationships between features that often arrive in natural groupings (e.g., different image descriptors for the same image). This paper tackles the problem of online group feature selection, aiming to efficiently select a compact and discriminative feature subset from a stream of features arriving in predefined groups.

Methods

The proposed OGFS method employs a two-stage approach:

  1. Online Intra-Group Selection: When a new group of features arrives, this stage uses spectral analysis to identify discriminative features within that group. Two novel criteria are introduced:
  2. Criterion 1: Evaluates if adding a new feature improves the between-class distance while minimizing within-class distance, using a threshold $\epsilon$.
  3. Criterion 2: Assesses the significance of a feature's discriminative power using a t-test on its score, based on a previously selected subset.
  4. Online Inter-Group Selection: After intra-group selection, this stage refines the feature subset by considering the global group information. It utilizes Lasso regression to find a globally optimal subset of features by minimizing a predictive error objective function subject to an L1 norm constraint on the regression coefficients. Features with non-zero coefficients are selected.

This two-stage process is iterated until predefined stopping conditions (e.g., a target number of features, desired accuracy, or no more features) are met.

Datasets

The authors evaluated OGFS on a combination of benchmark and real-world datasets:

  • Benchmark Datasets: Eight datasets from the UCI repository and microarray domains (colon, prostate, leukemia, lungcancer). For these, feature groups were self-defined by partitioning the feature space.
  • Real-world Datasets:
    • PASCAL VOC 2010: A challenging image dataset with 10,103 images from 20 classes, used with pre-existing group structures based on SIFT descriptors.
  • 15 Scenes: A dataset of 4485 images from 15 categories, also using SIFT descriptors as groups.
  • Soccer: A dataset of 280 images from 7 football teams, using PHOG, Color Moment, and texture descriptors as groups.
  • Flower-17: A dataset of flower images with 17 categories, using the same three descriptors as groups.

Key Insights and Ideas

  • Group Structure Matters: The core insight is that features often arrive in meaningful groups, and ignoring these relationships leads to suboptimal feature selection, especially in online settings. OGFS explicitly leverages this group structure.
  • Spectral Analysis for Initial Filtering: Using spectral analysis for intra-group selection provides an effective way to quickly identify promising features within a newly arrived group, balancing discriminative power and redundancy.
  • Lasso for Global Optimization: Lasso's ability to perform sparse linear regression is crucial for inter-group selection, allowing it to find a globally optimal subset by penalizing irrelevant features and effectively handling group-level correlations.
  • Dynamic Re-evaluation: Unlike some online methods where selected features are fixed, OGFS re-evaluates features in each iteration, allowing it to adapt and potentially discard less relevant features as new data arrives.

Key Results

OGFS demonstrated superior performance compared to state-of-the-art online feature selection methods (Alpha-investing and Fast-OSFS) and a baseline method across various datasets:

  • Benchmark Data: OGFS achieved better or comparable classification accuracy on most benchmark datasets while often selecting a more compact subset of features. For instance, on the Colon and Leukemia datasets, OGFS significantly outperformed Alpha-investing in accuracy (0.91 and 1.0 vs. 0.80 and 0.65, respectively).
  • Real-world Data: OGFS generally outperformed Alpha-investing and Fast-OSFS in both accuracy and compactness. Notably, on the 15 Scenes dataset, OGFS achieved the best accuracy (0.54) with a significantly smaller feature subset compared to the baseline. On the Soccer dataset, OGFS achieved the best accuracy (0.369).
  • Efficiency: The algorithm's time complexity is linear with the number of features and groups, making it very fast.

Limitations and Future Work

  • Predefined Groups: The current OGFS framework assumes that feature groups are predefined. The paper does not discuss how to automatically discover these groups in a streaming context.
  • Stopping Conditions: While stopping conditions are defined (target feature count, accuracy threshold, or end of stream), their optimal selection might require further investigation.
  • Future Work: The authors suggest extending the framework to handle scenarios where features arrive individually rather than in groups, and exploring more sophisticated spectral analysis techniques for intra-group selection.

Summary updated

BibTeX
@inproceedings{wang2013online,
  author = {Jing Wang and Zhong-Qiu Zhao and Xuegang Hu and Yiu-ming Cheung and Meng Wang and Xindong Wu},
  title = {{Online Group Feature Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
}
Figure