In order to classify an unseen (query) vector q with the k-Nearest Neighbors method (k-NN) one computes a similarity function between q and training vectors in a database. In the basic variant of the k-NN algorithm the predicted class of q is estimated by taking the majority class of the q’s k-nearest neighbors. Various similarity functions may be applied leading to different classification results. In this paper a heterogeneous similarity function is constructed out of different 1-component metrics by minimization of the number of classification errors the system makes on a training set. The HSFL-NN system, which has been introduced in this paper, on five tested datasets has given better results on unseen samples than the plain k-NN method with the optimally selected k parameter and the optimal homogeneous similarity function.