An efficient bit-based feature selection method

Wei Chen, S. S. Tseng, Tzung‐Pei HongExpert 2007 · DOI

TL;DR

This paper introduces a novel bit-based feature selection method that leverages bitmap indexing and rough set theory to efficiently identify minimal yet representative feature sets. By transforming data into bit matrices and employing bitwise operations, the method significantly speeds up the feature selection process, making it more practical for large datasets.

What Problem Does This Paper Address?

Feature selection is a crucial step in machine learning and data mining, aiming to identify the most relevant features that describe an application domain. The goal is to reduce data dimensionality, improve model performance, and enhance interpretability. However, finding the optimal feature set is computationally challenging, often requiring exhaustive searches that are infeasible for large datasets. Existing methods fall into two main categories: optimal strategies that guarantee the best feature set but are slow, and heuristic strategies that are faster but may not find the optimal solution. This paper addresses the need for an efficient method that can discover optimal or near-optimal feature sets without prohibitive computational costs, particularly for classification and clustering tasks.

Methods

The proposed method, termed the "bitmap-based feature selection method," employs a two-phase approach:

  1. Bitmap Indexing Phase: The input dataset is transformed into a bitmap indexing matrix. This involves creating "record vectors" for each feature value, which are bit strings indicating which records possess that specific feature value. "Class vectors" are then derived, representing the relationship between feature values and the decision feature. These are combined into "feature-value vectors" and then aggregated into "feature matrices" for each feature. This phase leverages the efficiency of bitwise operations for data representation.
  2. Feature Selection Phase: This phase aims to find a minimal set of relevant features. It involves:
  3. Cleansing Tree Construction: A tree structure is built to identify and filter out inconsistent records (records with identical condition features but different decision features). The paper proposes an efficient algorithm for this, improving upon naive O(n²m) comparisons by using a cleansing tree with O(nmj) complexity. A "spanned feature order" (a permutation of features) is crucial for building this tree.
  4. Finding Appropriate Spanned Order: To optimize the cleansing tree construction, the paper introduces heuristics (H1 and H2) to determine an effective feature order. These heuristics consider the weight of feature values based on their occurrence with specific classes, leading to a more compact and efficient cleansing tree.
  5. Cleansing Feature Matrix: The valid mask derived from the cleansing tree is used to filter out inconsistent records from the feature matrix, ensuring data correctness.
  6. Selecting a Feature Set: The core of the selection process involves iteratively building feature matrices for sets of increasing size (s-feature matrices). An algorithm, SelectingFeatureSet, examines these matrices to find a feature set that can completely distinguish all classes. If no such set is found for a given 's', the CalculatingNextMatrix algorithm generates the (s+1)-feature matrix from the s-feature matrix, and the process repeats. This iterative approach, combined with bitwise operations, significantly reduces computation time compared to traditional methods.

Datasets

The paper evaluates its proposed method using several publicly available datasets from the UCI Repository:

  • Monk1
  • Monk2
  • Monk3
  • Vote
  • Mushroom
  • SoybeanL

Additionally, a large, real-world dataset from a financial group concerning endowment insurances was used to demonstrate the method's practical applicability. These datasets vary in characteristics, including the number of classes, condition features, records, and the presence of missing values.

Key Insights and Ideas

  • Bitwise Operations for Efficiency: The core innovation lies in representing and manipulating data using bit vectors and matrices. This allows for extremely fast operations (AND, OR, XOR) that are orders of magnitude faster than traditional arithmetic or logical operations on larger data types.
  • Bitmap Indexing as a Foundation: The paper effectively adapts bitmap indexing techniques, typically used for database queries, to the domain of feature selection. This provides a structured and efficient way to represent feature-class relationships.
  • Rough Set Theory for Optimality: By grounding the feature selection process in rough set theory, the method aims to find minimal feature sets that preserve the classification information of the original dataset, thus ensuring optimality or near-optimality.
  • Cleansing Tree for Data Quality: The introduction of the cleansing tree and its associated algorithms provides an efficient mechanism to handle noisy or inconsistent data, which is a common problem in real-world datasets.
  • Heuristics for Spanned Order: The proposed heuristics for determining the feature order in the cleansing tree are a clever way to optimize the tree construction, leading to smaller trees and faster processing.

Key Results

  • Accuracy: The proposed bit-based method consistently achieved 100% accuracy on all tested datasets, matching the performance of the traditional rough set method. This indicates that the method effectively identifies feature sets that preserve the classification information.
  • Efficiency (Speedup): The primary advantage demonstrated is a significant reduction in computation time. For instance, on the "Insurance" dataset, the proposed method took approximately 40 minutes, while the traditional rough set approach required over 468,000 minutes (more than 8 months). Even for smaller datasets like "Vote" and "Mushroom," the speedup was substantial.
  • Minimal Feature Sets: Both the proposed method and the traditional rough set approach were able to discover minimal feature sets, meaning they identified the smallest possible set of features that still achieved optimal classification accuracy.
  • SoybeanL Problem: The SoybeanL dataset, which is challenging for traditional methods due to its size and complexity, was handled efficiently by the proposed approach, which found a solution where the traditional method struggled.

Limitations and Future Work

  • NP-Complete Nature: The authors acknowledge that feature selection is an NP-complete problem. While their approach is significantly more efficient than traditional methods, it can still become unmanageable for datasets with an extremely large number of features or a very large number of possible values per feature.
  • Future Directions: The paper suggests future work in several areas:
  • Heuristic Approaches for Large Scale: Developing more efficient heuristic approaches to handle datasets with a massive number of features and values.
  • Hybrid Feature Selection: Investigating methods to integrate different feature selection approaches to automatically select the most appropriate one based on the characteristics of the data.

Summary updated

BibTeX
@inproceedings{chen2007efficient,
  author = {Wei Chen and S. S. Tseng and Tzung‐Pei Hong},
  title = {{An efficient bit-based feature selection method}},
  booktitle = {Expert},
  year = {2007},
  doi = {10.1016/j.eswa.2007.05.037},
}
Figure