effort has been put into selecting or scaling features to improve classification. A particularly popular approach is the use of evolutionary algorithms to optimize feature scaling. Another popular approach is to scale features by the mutual information of the training data with the training classes. In binary (two class) classification problems, it is helpful to choose k to be an odd number as this avoids tied votes. One popular way of choosing the empirically optimal k in this setting is via bootstrap method. The -nearest neighbor classifier The most intuitive nearest neighbour type classifier is the one nearest neighbour classifier that assigns a point to the class of its closest neighbour in the feature space, that is . As the size of training data set approaches infinity, the one nearest neighbour classifier guarantees an error rate of no worse than twice the Bayes error rate (the minimum achievable error rate given the distribution of the data). The weighted nearest neighbour classifier The -nearest neighbour classifier can be viewed as assigning the nearest neighbours a weight and all others weight. This can be generalised to weighted nearest neighbour classifiers. That is, where the th nearest neighbour is assigned a weight , with . An analogous result on the strong consistency of weighted nearest neighbour classifiers also holds. Let denote the weighted nearest classifier with weights . Subject to regularity conditions, which in asymptotic theory are conditional variables which require assumptions to differentiate among parameters with some criteria. On the class distributions the excess risk has the following asymptotic expansion for constants and where and . The optimal weighting scheme , that balances the two terms in the display above, is given as follows: set , for and for . With optimal weights the dominant term in the asymptotic expansion of the excess risk is . Similar results are true when using a bagged nearest neighbour classifier. Properties k-NN is a special case of a variable-bandwidth, kernel density "balloon" estimator with a uniform kernel. The naive version of the algorithm is easy to implement by computing the distances from the test example to all stored examples, but it is computationally intensive for large training sets. Using an approximate nearest neighbor search algorithm makes k-NN computationally tractable even for large data sets. Many nearest neighbor search algorithms have been proposed over the years; these generally seek to reduce the number of distance evaluations