K-Nearest Neighbour Classification

The k-nearest neighbour algorithm (k-NN) is a non-parametric classification method which classifies objects based on the closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification. The k-nearest neighbour algorithm is amongst the simplest of all machine learning algorithms: an object is classified by a majority vote of its neighbours, with the object being assigned to the class most common amongst its k nearest neighbours (k is a positive integer, typically small).

For the application of SAR image classification, the training examples are image data for user selected pixels, each with a class label. The training phase of the algorithm consists only of storing the image data and class labels of the training samples.

In the classification phase, an unlabeled pixel is classified by assigning the label which is most frequent among the k training samples closest to the pixel. Here k is a user-defined constant.

Commonly used distance metrics include Euclidean distance, Mahalanobis distance and Diagonal Mahalanobis distance. Often, the classification accuracy of k-NN can be improved significantly if the distance metric is learned with specialized algorithms such as Large Margin Nearest Neighbour or Neighbourhood components analysis.

A drawback of the basic "majority voting" classification occurs when the class distribution is skewed. That is, examples of a more frequent class tend to dominate the prediction of the new example, because they tend to be common among the k nearest neighbours due to their large number. To overcome this problem, different kinds of weight functions are introduced. The goal of weight functions is to cause distant neighbours to have less effect on the majority vote than the closer neighbours.

After the k nearest neighbours of a test sample is found, these can be evaluated using different weighting methods. For each neighbouring pixel, the pixel’s weight is added to the total weight of that pixel’s class. At the end, the class with the largest total weight wins. Commonly used weight functions include Fraction, Stairs, Inverse distance and Inverse square distance.