DemoFS: Scaling Up Feature Selection Through Democratization

TL;DR

Feature selection is a critical yet computationally expensive preprocessing step. When data scales, traditional algorithms like Genetic Algorithms (GA) and ReliefF often hit a wall. This paper introduces Democratic Feature Selection (DemoFS), a methodology that treats feature selectors like "weak learners" in an ensemble. By splitting data into small subsets and aggregating results through a smart voting mechanism, it achieves massive speedups without sacrificing accuracy.

Background: The Scalability Wall

In the era of Big Data, the dimensionality of datasets is exploding. While feature selection (Filter, Wrapper, or Embedded) helps by reducing the "Curse of Dimensionality," the selection process itself is often NP-hard.

• Wrappers are accurate but slow (O(2^N)).
• Filters are fast but ignore feature interactions.

The authors argue that scaling up isn't about rewriting algorithms from scratch, but about changing how we apply them.

Methodology: The Power of the Vote

The core insight of DemoFS is Democratization. Instead of asking one "expert" (an algorithm looking at the whole dataset) to pick features, it asks several "citizens" (the same algorithm looking at different subsets).

1. The Workflow

1. Data Partitioning: The training set is split into $n$ disjoint subsets by instances or features.
2. Local Selection: A base feature selection algorithm (like ReliefF or GA) is applied to each subset.
3. Voting: Features that are recommended for removal receive a "vote."
4. Thresholding: After $r$ rounds, global features with votes exceeding a dynamic threshold $v$ are pruned.

2. Automatic Threshold Determination

A crucial innovation is the fitness function used to find the optimal voting threshold $v$: $f(v)=\alpha \cdot {ϵ}_t(v)+(1-\alpha )\cdot m(v)$ This formula balances Testing Error (${ϵ}_t$) and Storage Requirements ($m$), ensuring the "democracy" doesn't become too restrictive or too lenient.

Experiments: Speed Meets Precision

The authors validated DemoFS on 27 UCI datasets using ReliefF and Genetic Algorithms.

Performance vs. Standard GA

For Genetic Algorithms, the "Democratic" approach (dividing by instances) matched the accuracy of the standard GA while significantly reducing the time required for high-dimensional sets like mfeat-pix or opt-digits.

The Runtime Advantage

The most striking result is the Execution Time. As problem complexity grows, the standard algorithms' runtimes grow exponentially, whereas DemoFS remains nearly linear.

Critical Insights & Conclusion

DemoFS proves that diversity of perspective (subsets of data) is better for feature selection than a single global view when computational resources are limited.

Key Takeaways:

• Agnostic Architecture: You can plug in any feature selection algorithm as the engine.
• Parallel Ready: Since each subset is processed independently, it is trivial to deploy this on a Spark or MPI cluster.
• Trade-offs: While partitioning by instances works well, partitioning by features requires larger subset sizes to maintain reliability.

Limitations: The current version uses random partitioning. Future work on "data-dependent" partitioning (e.g., using clustering to create subsets) could further improve the stability of the votes.

In summary, DemoFS is a robust framework for anyone needing to apply heavy-duty feature selection to datasets that were previously considered "too large to process."