The K-nearest neighbors algorithm predicts from the labels or responses of the training observations closest to the query under a chosen distance.
With fixed neighbor positions, independent equal-variance errors and weights , the displayed variance is minimized at , with value . Its bias is . Larger nearest-point weight often reduces smoothing bias, but neither the bias nor the variance is universally monotone over . If the nearest point is the target, the squared bias is .
// Target: probability-and-statistics.bigb
The classifier that assigns the query the label of its closest training feature, using feature-measurable nearest-neighbour tie-breaking. Its misclassification risk need not converge to Bayes risk, even with infinitely many independent and identically distributed random variables as training data.
For binary classification, write and assume feature-measurable nearest-neighbour tie-breaking. If , then the expected conditional misclassification risk of the one-nearest-neighbour classifier tends to . Couple each label and an oracle label using one uniform variable. Their disagreement has the preceding expected absolute difference. The oracle and the test label are conditionally independent Bernoulli random variables of parameter , so their disagreement probability is exactly . The difference of classification in statistical learning error probabilities is at most the coupling disagreement.
Under the hypotheses for the one-nearest-neighbour asymptotic risk, the limiting risk satisfies . Put : then since . Integrate, using the definition of Bayes risk. Constant gives limiting risk and Bayes risk , so the lower comparison is not generally equality.
For a fixed query, order training features by their distances and break equal distances by a rule depending only on features, such as original index. If auxiliary uniforms are independent of the features, the uniform selected by the resulting index remains uniform conditional on all features: sum over the possible selected indices. Label-dependent tie-breaking can invalidate Bernoulli coupling by a shared uniform random variable and the usual one-nearest-neighbour asymptotic risk.
The L-nearest-neighbour classifier estimates each class probability by its empirical frequency among the nearest training covariates and predicts a class of greatest estimated probability.
One-nearest-neighbour classification assigns a query the label of its single nearest training observation. Under local regularity, its limiting conditional error is .
Articles by others on the same topic
The K-nearest neighbors (KNN) algorithm is a simple and widely-used machine learning algorithm primarily used for classification and regression tasks. It is a type of instance-based learning, meaning it makes predictions based on the instances (data points) that are stored in the training set. ### Key Concepts: 1. **Instance-based learning**: KNN stores all of the training instances and makes decisions based on the instances it finds most similar to new data.
