Algoritmos de búsqueda de vecinos más proximos en espacios métricos

Abstract

LA BUSQUEDA DEL VECINO MAS PROXIMO ES UNA TECNICA MUY UTILIZADA EN RECONOCIMIENTO DE FORMAS, DADO UN CONJUNTO DE PROTOTIPOS CUYA CLASIFICACION SE CONOCE, UNA MUESTRA SE CLASIFICARA EN LA CLASE DONDE SE ENCUENTRE EL PROTOTIPO CUYA DISTANCIA A LA MUESTRA ES MINIMA. EN ESTA TESIS SE PRESENTA UNA FAMILIA DE ALGORITMOS DE BUSQUEDA DE LOS VECINOS MAS PROXIMOS EN ESPACIOS METRICOS. ESTOS ALGORITMOS HAN SIDO DISEÑADOS PARA MEJORAR LAS PRESTACIONES DEL ALGORITMO AESA PROPUESTO POR VIDAL EN 1986. LAS CARACTERISTICAS PRINCIPALES DEL ALGORITMO AESA Y QUE LOS ALGORITMOS PROPUESTOS CUMPLEN SON: 1) CALCULA UN NUMERO MEDIO DE DISTANCIAS INDEPENDIENTES DEL TAMAÑO DEL CONJUNTO DE PROTOTIPOS PARA ENCONTRAR EL VECINO MAS PROXIMO Y 2) NO NECESITA LA REPRESENTACION DE DICHOS PROTOTIPOS EN UN ESPACIO VECTORIAL. LOS ALGORITMOS PROPUESTOS, ADEMAS, CONSIGUENESTE RESULTADO UTILIZANDO UN COSTE ESPACIAL LINEAL (FRENTE AL COSTE CUADRATICO) DEL ALGORTIMO AES CON RESPECTO ALK TAMAÑO DEL CONJUNTO DE PROTOTIPOS. ADEMAS, CON ELALGORITMO TLAESA, TAMBIEN SE REDUCE EL COSTE TAMBIEN SE REDUCE CON EL COSTYE TEMPORAL(NO ASOCIADO AL CALCULO DE LAS DISTANCIAS) A COTAS SUBLINEALES. POR ULTIMO, LOS ALGORITMOS PROPUESTOS SON APLICADOS A UN CASO REAL; CONCRETAMENTE, AL RECONOCIMIENTO DE CARACTERES MANUSCRITOS.