5.1 Introduction

In pattern recognition, the k-nearest neighbors algorithm (or k-NN for short) is a nonparametric method used for classification and regression [1]. In both cases, the input consists of the k closest training examples in the feature space. The output depends on whether k-NN is used for classification or regression:

• ■ In k-NN classification, the output is a class membership. An object is classified by a majority vote of its neighbors, with the object being assigned to the class most common among its k-NN (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor.

• ■ In k-NN regression, the output is the property value for the object. This value is the average of the values of its k-NN.

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-NN algorithm is among the simplest of all machine learning algorithms.

For both classification and regression, it can be useful to assign weight to the contributions of the neighbors, so that the nearer neighbors contribute more to the average than the more distant ones. For example, a common weighing scheme consists of giving each neighbor a weight of 1/d, where d is the distance to the neighbor.

The neighbors are taken from a set of objects for which the class (for k-NN classification) or the object property value (for k-NN regression) is known. This can be thought of as the training set for the algorithm, though no explicit training step is required.

A shortcoming of the k-NN algorithm is that it is sensitive to the local structure of the data. The algorithm has nothing to do with and is not to be confused with k-means, another popular machine learning technique.

5.2 Example

Suppose that we have a two-dimensional data, consisting of circles, squares, and diamonds as in Figure 5.1.

Each of the diamonds is desired to be classified as either a circle or a square. Then, the k-NN can be a good choice to do the classification task.

The k-NN method is an instant-based learning method that can be used for both classification and regression.

Suppose that we are given a set of data points {(x₁, C₁),(x₂, C₂), …, (x_N, C_N)}, where each of the points x_j, j = 1, …, N has m attributes a_j1, a_j2, …, a_jm and C₁, …, C_N are taken from some discrete or continuous space K.

It is clear that

with f(x_j) = C_j, where X = {x₁, …, x_N} is a subset of some space Y.

Given an unclassified point x_s = (a_s1, a_s2, …, a_sm) ∊ Y, we would like to find C_s ∊ K such that f(x_s) = C_s. At this point, we have two scenarios [2]:

1. The space K is discrete and finite: in this case we have a classification problem, C_s ∊ K where K = {C₁, …, C_N}, where and the k-NN method sets f(x_s) to be the major vote of the k-NN of x_s.

2. The space K is continuous: In this case, we have a regression problem and the k-NN method sets $f\left(x_s\right)=(1/k){\mathrm{\sum }}_{j=1}^{k}f\left(x_{s_j}\right)$, where {x_s1, x_s2, …, x_sk} is the set of k-NN of x_s. That is, f(x_s) is the average of the values of the k-NN of point x_s.

The k-NN method belongs to the class of instance-based supervised learning methods. This class of methods does not create an approximating model from a training set as happens in the model-based supervised learning methods.

To determine the k-NN of a point x_s, a distant measure must be used to determine the k closest points to point x_s: {x_s1, x_s2, …, x_sk}. Assuming that d(x_s, x_j), j = 1, …, N, measures the distance between x_s and x_j, and {x_si: i = 1, …, k} is the set of k-NN of x_s according to the distant metric d. Then, the approximation $f\left(x_s\right)=(1/k){\mathrm{\sum }}_{j=1}^{k}f\left(x_{s_j}\right)$ assumes that all the k-neighboring points have the same contribution to the classification of the point x_s.

5.3 k-Nearest Neighbors in MATLAB^®

MATLAB enables the construction of a k-NN method through the method “ClassifyKNN.fit,” which receives a matrix of attributes and a vector of corresponding classes. The output of the ClassifyKNN.fit is a k-NN model.

The default number of neighbors is 1, but it is possible to change this number through setting the attribute “NumNeighbors” to the desired value.

The following MATLAB script applies the k-NN classifier to the ecoli dataset:

clear; clc;
EcoliData = load(‘ecoliData.txt’); % Loading the
ecoli dataset
EColiAttrib = EcoliData(:, 1:end-1); % ecoli
attributes
EColiClass = EcoliData(:, end); % ecoli classes
%knnmodel = ClassificationKNN.
fit(EColiAttrib(1:280,:), EColiClass(1:280),...
% ‘NumNeighbors’, 5, ‘DistanceWeight’, ‘Inverse’);
% fitting the
% ecoli data with the k-nearest neighbors method
% The above line changes the number of neighbors
to 4
knnmodel = ClassificationKNN.
fit(EColiAttrib(1:280,:), EColiClass(1:280),...
‘NumNeighbors’, 5)
Pred = knnmodel.predict(EColiAttrib(281:end,:));
knnAccuracy = 1-find(length(EColiClass(281:end)-Pred))/length(EColiClass(281:end));
knnAccuracy = knnAccuracy * 100

The results are as follows:

      knnmodel =
       ClassificationKNN
        PredictorNames: {‘x1’ ‘x2’ ‘x3’ ‘x4’ ‘x5’
         ‘x6’ ‘x7’}
         ResponseName: ‘Y’
          ClassNames: [1 2 3 4 5 6 7 8]
        ScoreTransform: ‘none’
         NObservations: 280
           Distance: ‘euclidean’
         NumNeighbors: 5
       Properties, Methods
      knnAccuracy =

98.2143

Another approach assumes that a closer point to x_s shall have more contribution to the classification of x_s. Therefore, came the idea of the weighted weights, which is assumed to be proportional to the closeness of the point from x_s. Now, if {x_s1, x_s2, …,x_sk} denotes the k-NN of x_s, let

It is obvious that ${\mathrm{\sum }}_{i=1}^{k}w(x_s,x_{si})=1.$ Finally, f(x_s) is approximated as

MATLAB enables the use of weighted distance through changing the attribute “DistanceWeights” from “equal” to either “Inverse” or “SquaredInverse.” This is done by using

knnmodel = ClassificationKNN.
fit(EColiAttrib(1:280,:), EColiClass(1:280),...
‘NumNeighbors’, 5, ‘DistanceWeight’, ‘Inverse’);

Applying the KNN classifier with a weighted distance provides the following results:

knnAccuracy =
98.2143

which is the same as the model with equal distance.

References

1. Hastie, T., Tibshirani, R., and Friedman, J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Ed., New York: Springer-Verlag, February 2009.

2. Vapnik, V. N. The Nature of Statistical Learning Theory. 2nd Ed., New York: Springer-Verlag, 1999.