# k Nearest Neighbours: k > 1

## Intro

This time we want to find the nearest k neighbours to the test object.

For classification, we simply take a vote between them. In regression, we predict with the average of their labels.

## Deciding k

To decide what size k to use, we can use cross validation.

For a large training set, we can use cross validation with 10 folds.

## Computational Aspects

A large k can be computationally expensive.

Computing one distance takes time $O(p)$ where $p$ is the dimension of the objects (i.e. number of numeric attributes).

For each object in the test set, we need to calculate $n$ distances. The total time required to calculate distances for each test object is $O(np)$.

### Curse of Dimensionality

As the number of observations needed increases exponentially with each attribute.