Voted-Perceptron based Distance Metric Learning in k Nearest Neighbor

Ali Mustafa Qamar 1
1 MRIM - Modélisation et Recherche d’Information Multimédia [Grenoble]
LIG - Laboratoire d'Informatique de Grenoble, Inria - Institut National de Recherche en Informatique et en Automatique
Abstract : This thesis is related to distance metric learning for kNN classification. We use the k nearest neighbor (kNN) which is a well known classical algorithm in machine learning. The contribution of this work lies in using the k nearest neighbor algorithm with the Freund and Schapire’s voted-perceptron algo- rithm combined with its Collins’ incremental variant. The proposed algorithm can work with linear separable as well as non-linear separable data. A vector is learned for each class during the training phase in such a way that the k nearest neighbors belong to the same class. These vectors are subsequently used for classifying unseen examples. The implementation is done in the incremental setting so that the inclusion of new examples does not trigger the training phase for all of the stored examples as in the case of batch learning. A user relevance feedback mechanism is also developed to improve the training data. Experiments are carried out on different datasets and the performance is assessed against state of the art kNN algorithm. Different distance and similarity metrics are used for comparison.
Type de document :
[Research Report] 2007
Liste complète des métadonnées
Contributeur : Marie-Christine Fauvet <>
Soumis le : vendredi 28 février 2014 - 16:13:21
Dernière modification le : jeudi 11 janvier 2018 - 01:49:06


  • HAL Id : hal-00954107, version 1



Ali Mustafa Qamar. Voted-Perceptron based Distance Metric Learning in k Nearest Neighbor. [Research Report] 2007. 〈hal-00954107〉



Consultations de la notice