k-Nearest Neighbours (k-NN) is supervised learning that has been used in many applications in the field of data mining and pattern recognition . It classifies objects based on closest training examples in the feature space. k-NN is a type of instance-based learning where the function is only approximated locally and all computation is deferred until classification. An object is classified by a majority vote of the closest k neighbours or the distance-weighted average of the closest k neighbours if the class is numeric. If k=1, then the object is simply assigned to the class or the value of that single nearest neighbour.

In general, the k-NN algorithm is composed of the following steps:

  • Determine parameter k, which is the number of nearest neighbours;
  • Calculate the distance between the query-object and all the training samples;
  • Sort the distance and determine the nearest k neighbours based on minimum distance;
  • Gather the category Y of the k nearest neighbours;
  • Use simple majority of the category of nearest neighbours (or the distance-weighted average if the class is numeric) as the prediction value of the query-instance.

According to (Witten et al. 2011), the advantages of k-NN are:

  • Robust to noisy training data, especially if the inverse square of weighted distance is used as the distance metric;
  • Effective in training procedure compare to the other algorithms; However, the disadvantages are:
  • Need to determine the value of k, which is the number of nearest neighbours;
  • k-NN is a type of distance based learning and which type of distance can produce the best result is not clear;
  • Computation cost is high because the algorithm needs to calculate the distance of each query-object to all training samples.

The k-NN was trained using the WT power data A and the classification was tested using a test data with k=10 as shown in Figure 1. We found that this test data is misidentified as OK because majority of the 10 nearest data to the test data are OK.


k-NN result with a data

References & Resources