Tecnologías Específicas

Computación

Descripcion y Objetivos

El problema de la agregación de rankings consiste en dado un conjunto de rankings (órdenes), obtener un
ranking de consenso que sea el que resuma la opinión de todos los evaluadores. Es un problema que tiene
p.e. aplicación en la fusión de las listas de páginas webs o productos obtenidas por distintos buscadores o
sistemas de recomendación.
En la literatura, la versión más trabajada siempre produce un ranking completo y sin empates, es decir, una
permutación de los objetos a ordenar. Si que se es más flexible en cuanto a los rankings de entrada, que
pueden ser completos/incompletos y/o sin/con empates.
Recientemente ha ganado interés el problema conocido como "bucket order", el cuál también permite que
haya items empatados en le ranking de salida, indicando así, que teniendo en cuenta las opiniones
expresadas en los rankings de entrada, el consenso es que no hay una preferencia clara sobre esos
objetos.
En este TFG el objetivo es implementar algoritmos ya publicados para aproximar este problema, como es el
estándar de facto, BPA, y una modificación basada en técnicas de minería de datos, que hace un clustering
previo de los objetos, arrancando así BPA sobre un conjunto de buckets (items ya empatados) en lugar de
sobre los objetos individuales. Se realizarán pruebas sobre un conjunto de bases de datos representativo
obtenido de la web de referencia (preflib) y se propondrán posibles mejoras que introduzcan beneficios en
forma de eficiencia/eficacia a los algoritmos considerados.

 

Metodología y Competencias

1) Revisar la literatura y comprender el problema del bucket order.
2) Seleccionar un conjunto de bases de datos con los que trabajar.
3) Implementar el algoritmo BPA y hacer las pruebas iniciales sobre los datasets seleccionados.
4) Estudiar el algoritmo de preprocesamiento basado en clustering e implementarlo.
5) Realizar pruebas sobre el benchmark seleccionado en (2). Ajuste de parámetros.
6) Estudio e implementación de posibles modificaciones al algoritmo de clustering.

7) Posibles extensiones: Aplicar algoritmos de tipo metaehurístico sobre los items preprocesados en
clusters.
8) Implementación y pruebas.
9) Escritura del TFG.

 

COMPETENCIAS de la intensificación desarrolladas en el TFG:

[CM1] Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.

[CM3] Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

[CM7] Capacidad para conocer y desarrollar técnicas de aprendizaje computacional y diseñar e implementar aplicaciones y sistemas que las utilicen, incluyendo las dedicadas a extracción automática de información y conocimiento a partir de grandes volúmenes de datos.
 

 

Medios a utilizar

PCs ordinarios, bibliografía, compiladores C, java, etc.
Todo disponible en la ESII.

 

Bibliografía

A. Ukkonen, K. Puolamaki, A. Gionis, H. Mannila: A Randomized Approximation Algorithm for Computing
Bucket Orders. Information Processing Letters 109 (2009), 356-359.

A. Gionis, H. Mannila, K. Puolamaki, and A. Ukkonen, Algorithms for Discovering Bucket Orders from Data,
12th International Conference on Knowledge Discovery and Data Mining (KDD) 2006, p. 561-566.

Juan A. Aledo, José A. Gámez, Alejandro Rosete. El problema del ordenamiento óptimo de buckets usando
metaheurísticas. Actas de la XVII Conferencia de la Asociación Española para la Inteligencia Artificial, pp.
231-240