An Efficient, Parallelized Algorithm for Optimal Conditional Entropy-Based Feature Selection.

Area of Science:

• Machine Learning
• Computer Science
• Data Mining

Background:

• Feature selection is crucial for classifier design, aiming to identify optimal feature subsets.
• The U-curve problem, arising from feature selection within Boolean lattices, presents a minimization challenge.
• Existing U-Curve Search (UCS) is optimal but suffers from exponential time complexity.

Purpose of the Study:

• To address the scalability limitations of the U-Curve Search (UCS) algorithm for the U-curve problem.
• To introduce a novel, parallelizable algorithm for efficient feature selection.
• To evaluate the performance of the new algorithm against existing methods.

Main Methods:

• The U-curve problem, known to be NP-hard, was analyzed for scalability issues.
• A new algorithm, Parallel U-Curve Search (PUCS), was developed by partitioning the search space.
• PUCS was designed for high parallelizability to improve computational efficiency.
• Computational assays were conducted using synthetic and real-world Machine Learning datasets.

Main Results:

• The scalability issue in UCS was confirmed to stem from the NP-hard nature of the U-curve problem.
• PUCS demonstrated improved performance through its parallelizable approach.
• Comparative analysis showed PUCS effectiveness against UCS and other standard feature selection algorithms.

Conclusions:

• The NP-hard nature of the U-curve problem necessitates scalable solutions for effective feature selection.
• Parallel U-Curve Search (PUCS) offers a highly parallelizable and efficient alternative to existing methods.
• PUCS shows significant promise for improving computational efficiency in Machine Learning feature selection.