Introduction

$ K$-Nearest neighbour algorithm [2,1] works in the following way:

  1. Given an input matrix training $ \mathbf{X} \in \mathbb{R}^{n \times p}$:

  2. For each of the $ n$ rows of input data matrix:

    1. Compute e.g. the Euclidean distance (of course other distance can be used) to the $ n-1$ other rows:

      $\displaystyle d(\mathbf{x,y})=\sqrt{\sum_{i=1}^p (x_i-y_i)^2}$    

    2. Set the class of row number $ i$ equal to the ``winning'' class of the $ K$ rows that lie closest (the $ K$-Nearest Neighbours).

Given an input vector $ \mathbf{x}_0$ whose class is unknown:

  1. Compute the distance to all rows of the training matrix $ \mathbf{X}$.
  2. Select the class of the input vector $ \mathbf{x}_0$ equal to the class of the row that it lies closest to.



Bjørn Kåre Alsberg 2006-04-06