Wiki gives this definition of KNN

In pattern recognition, the k-nearest neighbors algorithm (k-NN) is a non-parametric method used for classification and regression. 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 plurality vote of its neighbors, with the object
    being assigned to the class most common among its k nearest neighbors (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 k nearest neighbors.

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.

Both for classification and regression, a useful technique can be to assign weights 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 weighting scheme consists in giving each neighbor a weight of 1/d, where d is the distance to the neighbor.

and this explanation about "The weighted nearest neighbour classifier"

The k-nearest neighbour classifier can be viewed as assigning the k nearest neighbours a weight 1/k and all others 0 weight. This can be generalised to weighted nearest neighbour classifiers. That is, where the ith nearest neighbour is assigned a weight ${\displaystyle > w_{ni}}$, with ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$. An analogous result on the strong consistency of weighted nearest neighbour classifiers also holds.

Let $C_{n}^{wnn}$ denote the weighted nearest classifier with weights $\{w_{{ni}}\}_{{i=1}}^{n}$.

Subject to regularity conditions on the class distributions the excess risk has the following asymptotic expansion ${\mathcal {R}}_{{\mathcal {R}}}(C_{{n}}^{{wnn}})-{\mathcal {R}}_{{{\mathcal {R}}}}(C^{{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},$

and this formula

With optimal weights the dominant term in the asymptotic expansion of the excess risk is ${\mathcal {O}}(n^{{-{\frac 4{d+4}}}})$

Does $\mathcal {O}$ here mean the Big O notation or something else?


1 Answer 1


To further clarify the answer of @Mohith7548 , the O() notation in your KNN description refers to the rate of convergence of the statistical estimator. This is not about computational efficiency of algorithms, but rather, how far are the estimates output by the KNN algorithm expected to be from perfect estimates (i.e. the best possible predictions) for a dataset with sample size n and dimensionality d. As n grows to infinity, the KNN estimator should converge to the optimal predictor (under some basic regularity conditions), and the O() formula describes how fast this convergence happens as n increases. The convergence is slower with high-dimensional data, because statistical estimation of more numbers is harder (see "curse of dimensionality").

See "convergence in probability" to learn more about this topic of statistical convergence rates (which are different that computational complexity).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.