Recientemente, se han propuesto diversos clasificadores basados en un tipo de vecindad denominada envolvente, que permiten obtener excelentes resultados: reglas de decisión basadas en grafos de proximidad y clasificación por vecindad de centroide más próximo. Sin embargo, uno de los principales inconvenientes de estas alternativas a la regla de los k vecinos más próximos se refiere a su elevado coste computacional.

Así, los principales objetivos de este proyecto pueden resumirse en los siguientes puntos:

1. Desarrollo de algoritmos eficientes para el cálculo de los vecinos de centroide más próximo, así como para la búsqueda de la vecindad de grafo. Básicamente, el trabajo desarrollado hasta ahora se ha centrado en el estudio de la efectividad de estos esquemas alternativos, pero no existe ningún análisis teórico o empírico que nos guie para aumentar la eficiencia de los mismos.
2. Utilización de la regla del vecino más próximo sobre casos reales. En este sentido, cabe apuntar que se han propuesto dos algoritmos para diseñar redes neuronales y árboles de decisión a partir de la descomposición del espacio de características, permitiendo clasificar de forma totalmente equivalente a como lo hace la regla del vecino más próximo, aunque evitando el cálculo de distancias (desde el punto de vista computacional, esta tarea representa la parte más compleja de la regla del vecino más próximo). No obstante, el inconveniente práctico de estas estructuras se centra en el tamaño de las mismas, es decir, en el elvado número de neuronas en la red y la excesiva altura del árbol. En consecuencia, el segundo objetivo básico de este proyecto es la reducción de la dimensión de aquellas estructuras a partir de una implementación basada en ciertas técnicas heurísticas.