Prácticas de la asignatura de Metaheurísticas
Práctica 1 - Técnicas de Búsqueda Local y Algoritmos Greedy para el Problema del Aprendizaje de Pesos en Características
· Clasificador 1-NN sin pesos
· Greedy
· Búsqueda Local (BL)
Práctica 2 - Técnicas de Búsqueda basadas en Poblaciones para el Problema del Aprendizaje de Pesos en Características
· Algoritmos genéticos generacionales y estacionarios (AGGs, AGEs)
· Algoritmos meméticos (AMs)
Práctica 3 - Técnicas de Búsqueda basadas en Trayectorias para el Problema del Aprendizaje de Pesos en Características
· Enfriamiento Simulado (ES)
· Búsqueda Multiarranque Básica (BMB)
· Búsqueda Local Reiterada (ILS)
· Hibridación de ILS y ES
Descripción del problema
Con esta práctica se pretende mostrar en qué consiste un problema de clasificación en machine learning y cómo podemos afrontarlo construyendo diferentes clasificadores. Como en cualquier problema de este tipo, primero necesitamos los datos. Para ello, se dispone de tres bases de datos sencillas, como son “Ecoli”, “Parkinsons” y “Breast-cancer”, las cuales se han descargado de “UC Irvine Machine Learning Repository”. Estas bases de datos cuentan con muchos ejemplos conformados por características numéricas y la clase a la que pertenecen.
El objetivo de los algoritmos de clasificación, dentro del aprendizaje supervisado, es tener en memoria muchos datos etiquetados para luego saber predecir la clase de un nuevo ejemplo dadas sus características. Consideramos en primer lugar el clasificador 1-NN, el cual se basa en dar como clase predicha aquélla a la que pertenece el dato que se conoce “más cercano” al ejemplo nuevo. Esa noción de cercanía la medimos, en este caso, con la distancia euclídea, aprovechando que estamos tratando solo con atributos numéricos.
Sin embargo, podemos suponer que hay ciertas características que influyen más que otras a la hora de acertar con la clase a predecir o simplemente, queremos reducir el número de características por problemas de espacio aunque con ello empeore la precisión del clasificador. Por ello, asignamos unos pesos a los atributos para ponderar su relevancia en la clasificación. La forma de obtener estos pesos nos abre el camino a los problemas del aprendizaje de pesos en características, con los cuales se pretende optimizar tanto la precisión como la complejidad del clasificador. Según cómo se calculen esos pesos, desarrollamos una serie de clasificadores: greedy, búsqueda local, basados en poblaciones (genéticos y meméticos) y basados en trayectorias simples o múltiples.
Por supuesto, nos interesará finalmente comparar los resultados obtenidos con cada uno de los clasificadores empleados y ver cómo influye el usar pesos concretos frente a considerar todas las características por igual. Para ello, se usan cuatro métricas: tasa_class, que mide el porcentaje de acierto a la hora clasificar; tasa_red, que representa el porcentaje de características que se eliminan en la clasificación; fitness, que corresponde al valor de la función objetivo que está optimizando el algoritmo (combinando tasa_class y tasa_red); y el tiempo de ejecución empleado.