Weighting Features in k Nearest Neighbor

Classification on Feature Projections1

Aynur Akku?s and H. Altay G?uvenir

Department of Computer Engineering and Information Science
Bilkent University
Email : fakkus, [email protected]

BU-CEIS-9616

Abstract

This paper proposes two methods for learning feature weights to improve the classification accuracy of the k-NNFP algorithm. In the k-NNFP algorithm, instances are stored as their projections on each feature dimension. The classification of unseen examples are made on the basis of feature projections by a majority voting among the k ( k >= 1) predictions of each feature separately. We have treated all features as equivalent in this algorithm. However, all features may not have equal relevancy, even some features may be completely irrelevant. In order to determine features' relevances, the best method is to assign them weights. The first method is based on the assumption of homogeneous feature projections for which the number of consequent values of feature projections of a same class supports an evidence for increasing the probability of correct classification in the k-NNFP algorithm. The second method is based on the individual accuracies of features. In this approach, the k-NNFP algorithm is run on the basis of a single feature, once for each feature. The resulting accuracy is taken as the weight of that feature since it is a measure of contribution to classification for that feature. Empirical evaluation of these feature weighting methods in the k-NNFP algorithm on real world datasets is given.

1 Introduction

One of the central problems when classifying objects is discriminating between features that are relevant to the target concept and that are irrelevant. Many researchers have addressed the

1This project is supported by TUBITAK (Scientific and Technical Research Council of Turkey) under Grant EEEAG-153.