Problemi di feature selection modellati come problemi di programmazione lineare intera

In data analysis it is of crucial importance the selection of a compact subset of the available features that correctly represent the relevant information contained in the data. This problem, referred to as feature selection, is receiving increasing attention as the amount of information gathered in many settings of relevant practical importance is often of intractable dimensions for the application of advanced of data mining and data analysis algorithm. Feature selection problems are of particular importance in the analysis of biological data, such as microarrays, haplotype and genotype data, where the number of variables that describe each experiment can have extremely large size. In such cases the feature selection step plays a key role for the success of the analysis, of superior importance w.r.t. to the modelization and classification steps. A special class of models that has been proposed to solve this problem is based on integer programming formulations that try to represent the retained information using constraints associated with the observed data. Although very precise, these methods present the significant limit of being based on a computationally difficult formulation whose size grows rapidly with the size of the data. Indeed, to efficiently solve the resulting combinatorial optimization problem, we propose a GRASP (Greedy randomized Adaptive Search Procedure).