#
Details

`feature vectors
n`

`
x`

_{ 1}= (

`
x`

_{ 11},…,

`
x`

_{ 1 p}), …,

`
x`

_{ n}= (

`
x`

_{ n 1},…,

`
x`

_{ np}) of size

`and a vector of class labels
p`

`= (
y`

`
y`

_{ 1},…,

`
y`

_{ n}), where

`
y`

_{ i}

`- 1} and
C`

`is the number of classes, describes the class to which the feature vector
C`

`
x`

_{ i}belongs, the problem is to build a kNN classifier.

`and a test observation
k`

`
x`

_{ 0}, the kNN classifier does the following:

- Identifies the setN
_{ 0}of thefeature vectors in the training data that are closest tokx_{ 0}according to the Euclidian distance - Estimates the conditional probability for the class
as the fraction of vectors injN_{ 0}whose labelsare equal toyj - Assigns the class with the largest probability to the test observationx
_{ 0}

##
Training Stage

##
Prediction Stage

Given kNN classifier and query vectors
`
x`

_{ 0}, ...,

`
x`

_{ r}, the problem is to calculate the labels for those vectors. To solve the problem for each given query vector

`
x`

_{ i}, the algorithm traverses the K-D tree to find feature vectors associated with a leaf node that are closest to

`
x`

_{ i}. During the search, the algorithm limits exploration of the nodes for which the distance between the query vector and respective part of the feature space is not less than the distance from the

`
k`

^{ th}neighbor. This distance is progressively updated during the tree traverse.