Heuristic Search Algorithm for Dimensionality Reduction Optimally Combining Feature Selection and Feature Extraction

The following are two classical approaches to dimensionality reduction: 1. Approximating the data with a small number of features that exist in the data (feature selection). 2. Approximating the data with a small number of arbitrary features (feature extraction). We study a generalization that approximates the data with both selected and extracted features. We show that an optimal solution to this hybrid problem involves a combinatorial search, and cannot be trivially obtained even if one can solve optimally the separate problems of selection and extraction. Our approach that gives optimal and approximate solutions uses a “best first” heuristic search. The algorithm comes with both an a priori and an a posteriori optimality guarantee similar to those that can be obtained for the classical weighted A* algorithm. Experimental results show the effectiveness of the proposed approach.

Authors

• Baokun He
• Swair Shah
• Crystal Maung Department of Computer Science, University of Texas at Dallas, Texas, USA
• Gordon Arnold
• Guihong Wan Departments of Biostatistics and Epidemiology, Harvard T. H. Chan School of Public Health, MA, USA Department of Dermatology, Massachusetts General Hospital, Harvard Medical School, MA, USA
• Haim Schweitzer Department of Computer Science, University of Texas at Dallas, Texas, USA

Keywords

No keywords are indexed for this paper.