Pur essendo uno degli algoritmi di classificazione supervisionati più considerati e di successo, il classificatore k-Neighbor (kNN) generalmente descrive una scarsa efficienza dovuta, In questo senso, la ricerca di similarità approssimata (ASS) rappresenta una possibile alternativa per migliorare tali problemi di efficienza a scapito di ridurre in genere le prestazioni del classificatore. In questo documento prendiamo come punto iniziale una strategia ASS basata sul clustering. Miglioriamo quindi le sue prestazioni risolvendo problemi relativi a istanze situate vicino ai confini del cluster ingrandendone le dimensioni e considerando l’uso di reti neurali profonde per apprendere una rappresentazione adatta per il compito di classificazione in questione., I risultati utilizzando una raccolta di otto diversi set di dati mostrano che l’uso combinato di queste due strategie comporta un significativo miglioramento delle prestazioni di precisione, con una notevole riduzione del numero di distanze necessarie per classificare un campione rispetto alla regola di base kNN.