Contribuciones al problema de agregación de rankings. Aplicaciones al aprendizaje automático
Estado Finalizada
Trabajo fin de master y Tesis doctoral
Director UCLM
Codirectores no UCLM:
José A. Gámez (Departamento de Informática, UCLM)
Resumen

La tesis se centra en el estudio de problemas clásicos como el problema de rankings de Kemeny y el problema de agregación de rankings. En ellos, partiendo de N ordenaciones o rankings de n elementos representando las preferencias de N jueces, se pretende encontrar la permutación que esté a menor distancia del conjunto inicial. Para medir distancias entre rankings, se usan diversas distancias, entre las que tiene especial importancia la distancia de Kendall. Estos problemas son NP-duros para N mayor o igual que 4, lo que hace especialmente interesante su estudio. En el problema de rankings de Kemeny las N ordenaciones son permutaciones, es decir, rankings de n elementos en los que la preferencia entre los elementos está perfectamente determinada. En cambio, para el problema de agregación de rankings las ordenaciones pueden presentar o no empates y pueden ser o no incompletas. Por ello, suele entenderse que este último es una generalización del problema de rankings de Kemeny.

 Para resolver el problema de rankings de Kemeny, en la tesis se han desarrollado una serie de algoritmos genéticos que obtienen muy buenos resultados al compararlos con los algoritmos del estado del arte. De hecho, se obtiene significancia estadística en gran parte de las pruebas realizadas. Se han llevado a cabo pruebas usando el conocido Modelo de Mallows tanto para el muestreo inicial como para la estimación de sus parámetros. Asimismo, también se ha estudiado el Modelo de Mallows generalizado, una versión más compleja del anterior (mayor número de parámetros a estimar). 

Para el problema de agregación de rankings, se ha desarrollado en la tesis una generalización del popular algoritmo Borda, muy empleado en la resolución del problema de rankings de Kemeny dado su equilibrio entre eficacia y rapidez. Dado que este algoritmo está pensado para permutaciones, hemos adaptado el algoritmo para trabajar con ordenaciones que presentan empates o son incompletos. 

Actualmente estamos estudiando el problema en el que cada ordenación está etiquetada con k atributos y se pretende conseguir la agregación mediante aprendizaje automático.