Uso de métricas generalizadas en clasificadores usando coloración de gráficas suaves
2018Profesores: Dr. Pedro Lara Velázquez y Dra. Hérica Sanchez Larios (UNAM)
Resumen:La coloración de gráficas suaves es una generalización del problema de coloración en el que se busca encontrar una coloración que minimice la dureza en la gráfica, o dicho de otra forma, reducir la suma de distancias entre vértices con colores idénticos (Lara-Velázquez, et al., 2015). Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético, calendarización de actividades, asignación de recursos en organizaciones, en reconocimiento de patrones en general y en particular en un algoritmo clasificador no supervisado (Flores, 2017). Se ha demostrado que es un problema de tipo NP-Duro, aunque para grafos de orden menor o igual a 20, se pueden utilizar algoritmos exactos que resuelven el problema; caso contrario es necesario el uso de técnicas heurísticas con aproximaciones bastante aceptables.
En este proyecto de tesis se propone hacer un estudio comparativo de las soluciones obtenidas utilizando estas métricas tradicionales con otras métricas, obtenidas estas otras de combinaciones lineales positivas de métricas Lp (con 0 < p ≤ ∞). Por ejemplo, se podría probar con una combinación lineal de la métrica euclidiana con la métrica Manhattan. En general, se trata de probar con qué valor de p y con qué combinación de métricas Lp se obtienen mejores resultados. En algunos problemas de optimización se ha mostrado que se obtienen mejores soluciones cuando se utiliza una combinación lineal de métricas Lp. La calidad de las combinaciones de metricas obtenidas se probarán en ejemplos de problemas reales, principalmente del UCI Machine Learning Repository de la Universidad de California en Irvine.
El alumno programará los códigos en uno de los siguientes lenguajes,: C, FreeBASIC o Python.
Objetivo general
- Hacer un estudio sobre el uso de diferentes métricas LP así como combinaciones lineales de las mismas, para mejorar el desempeño en instancias de prueba (UCI Machine Learning Repository).
Objetivos específicos
- Proponer dos modelos, uno básico y uno mejorado, del algoritmo de solución mediante combinaciones de métricas LP.
- Validar la calidad de los modelos mediante diseño de experimentos.
- Generar un artículo para congreso nacional.
- Reportar los resultados de la investigación en la idónea comunicación de resultados.
Ultima actualización 13/08/2022 por pcyti