Si bien es uno de los Algoritmos de clasificación supervisada más considerados y exitosos, el clasificador k-nearest Neighbor (kNN) generalmente representa una baja eficiencia debido a que es un método basado en instancias., En este sentido, la búsqueda de similitud aproximada (ASS) se erige como una posible alternativa para mejorar esos problemas de eficiencia a expensas de reducir típicamente el rendimiento del clasificador. En este trabajo tomamos como punto inicial una estrategia ASS basada en la agrupación. A continuación, mejoramos su rendimiento resolviendo problemas relacionados con instancias ubicadas cerca de los límites del clúster ampliando su tamaño y considerando el uso de redes neuronales profundas para aprender una representación adecuada para la tarea de clasificación en cuestión., Los resultados obtenidos utilizando una colección de ocho conjuntos de datos diferentes muestran que el uso combinado de estas dos estrategias implica una mejora significativa en el rendimiento de precisión, con una reducción considerable en el número de distancias necesarias para clasificar una muestra en comparación con la regla básica de kNN.