Optimización del uso de pivotes en tareas de búsqueda y clasificación

• Autores: Raisa Socorro Llanes
• Directores de la Tesis: Luisa Micó Andrés (dir. tes.)
• Lectura: En la Universitat d'Alacant / Universidad de Alicante ( España ) en 2012
• Idioma: español
• Tribunal Calificador de la Tesis: René Alquézar Mancho (presid.) , José M. Iñesta Quereda (secret.) , Mª Angeles López Malo (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • La búsqueda por similitud (o vecindad) es una técnica utilizada en aquellos casos en que el objeto de consulta no se encuentra exactamente en la base de datos, por lo tanto es un fenómeno muy frecuente en aplicaciones de Reconocimiento de Patrones, Recuperación de Imágenes, Bases de Datos Multimedia, o Bioinformática entre otras. Este tipo de búsqueda consiste en recuperar de la base de datos los objetos más similares a una consulta, siendo la búsqueda del vecino más cercano y la búsqueda por rango las más utilizadas. El desarrollo de algoritmos eficientes para la búsqueda por similitud es un tema de investigación vigente desde hace muchos años. El objetivo de estos algoritmos es el de reducir el número de distancias a calcular cuando el coste de la distancia es muy elevado y/o evitar recorrer exhaustivamente toda la base de datos para encontrar la solución. El algoritmo AESA, propuesto por Vidal (1986), ha sido considerado por varias décadas el que menor número de distancias evalúa. En este tesis se explora y explota el uso de pivotes en algoritmos de búsqueda por similitud y clasificación para mejorar la eficiencia de estas tareas.

    Los principales aportes de esta tesis radican en el desarrollo de un conjunto de algoritmos eficientes basados en pivotes para la búsqueda de los vecinos más cercanos utilizando diferentes técnicas de selección de pivotes. Los algoritmos propuestos son extendidos para poder ser utilizados también en la búsqueda de los k vecinos más cercanos, la búsqueda por rango, y la búsqueda aproximado del vecino más cercano. Otro resultado importante es el empleo de los pivotes en un tarea de clasificación de caracteres manuscritos, utilizando estos pivotes para realizar una transformación del espacio de representación de los objetos a un espacio de vectores. Se propone además utilizar una estrategia de filtro-refinamiento a partir de las transformaciones para mejorar los resultados de clasificación. Todos los algoritmos propuestos en la tesis fueron validados experimentalmente.