GRASP con VNS para el Problema de la Selección de Características

Abstract

Dada la cantidad de volumen de datos que se maneja hoy en día, se hace necesaria la aplicación de técnicas de preprocesamiento sobre los conjunto de datos. De las técnicas que se pueden desarrollar para la preparación de los datos, centraremos la atención en la reducción de datos. De las múltiples vías que se pueden seguir para obtener esta reducción, profundizaremos en la selección de características. En este proyecto fin de carrera se han desarrollado tres algoritmos para resolver el problema de la selección de características. El primero de ellos consiste en, a partir de una base de datos vacía, ir añadiendo características de la base de datos mientras mejore la calidad de ésta. El segundo consiste en, a partir de una base de datos completa, ir quitando características mientras mejore la calidad. Por último se ha desarrollado un algoritmo meta-heurístico, GRASP. Este tipo de procedimientos se caracterizan por utilizar una construcción greedy, de la cual se obtiene una solución, que posteriormente es mejorada. Los resultados que se obtienen tras los experimentos indican, que no es posible determinar a priori si una tabla obtendrá mejores porcentajes si aplicamos un constructivo de añadir características o un constructivo de eliminar características. Esto vendrá condicionado por los datos y las clases que contenga la base de datos. Sí podemos determinar que, cuánto mayor es el volumen de las características que contienen las bases de datos, mayor es el tiempo de ejecución que se tarda en evaluar cada una de ellas.