Show the implementation of k-nearest
neighbor.
In pattern
recognition, the k-nearest neighbors algorithm (k-NN) is a non-parametric method
for classification and regression,[1] that predicts objects' "values"
or class memberships based on the k closest training examples in the feature
space. 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. The k-nearest neighbor algorithm is amongst the simplest of all
machine learning algorithms: an object is classified by a majority vote of its
neighbors, with the object being assigned to the class most common amongst 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.
The same method
can be used for regression, by simply assigning the property value for the
object to be the average of the values of its k nearest neighbors. It can be
useful to weight the contributions of the neighbors, so that the nearer
neighbors contribute more to the average than the more distant ones. (A common
weighting scheme is to give each neighbor a weight of 1/d, where d is the
distance to the neighbor. This scheme is a generalization of linear
interpolation.)
The best choice
of k depends upon the data; generally, larger values of k reduce the effect of
noise on the classification
The special case where the class is predicted
to be the class of the closest training sample (i.e. when k = 1) is called the
nearest neighbor algorithm.
KNN 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 appropriate nearest neighbor search algorithm
makes KNN computationally tractable even for large data sets.
number of input
attributes affects processing time.
Comments
Post a Comment