k-NEAREST NEIGHBOR LEARNING

• The most basic instance-based method is the K- Nearest Neighbor Learning. This algorithm assumes all instances correspond to points in the n-dimensional space Rⁿ.
• The nearest neighbors of an instance are defined in terms of the standard Euclidean distance.
• Let an arbitrary instance x be described by the feature vector

((a1(x), a2(x), ………, an(x))

Where, ar(x) denotes the value of the r^th attribute of instance x.

• Then the distance between two instances xi and xj is defined to be d(xi , xj ) Where,

• In nearest-neighbor learning the target function may be either discrete-valued or real- valued.

 Let us first consider learning discrete-valued target function of the form

f : Rⁿ à V

Where, V is the finite set {v1, . . . vs }

The k- Nearest Neighbor algorithm for approximation a discrete-valued target function is given below:

• The  value  𝑓̂(xq)  returned  by  this  algorithm  as  its  estimate  of  f(xq)  is  just  the  most common value of f among the k training examples nearest to xq.
• If k = 1, then the 1- Nearest Neighbor algorithm assigns to 𝑓̂(xq) the value f(xi). Where xi is the training instance nearest to xq.
• For larger values of k, the algorithm assigns the most common value among the k nearest training examples.

• Below figure illustrates the operation of the k-Nearest Neighbor algorithm for the case where the instances are points in a two-dimensional space and where the target function is Boolean valued.

• The positive and negative training examples are shown by “+” and “-” respectively. A query point xq is shown as well.
• The 1-Nearest Neighbor algorithm classifies xq as a positive example in this figure, whereas the 5-Nearest Neighbor algorithm classifies it as a negative example.

• Below figure shows the shape of this decision surface induced by 1- Nearest Neighbor over the entire instance space. The decision surface is a combination of convex polyhedra surrounding each of the training examples.

• For every training example, the polyhedron indicates the set of query points whose classification will be completely determined by that training example. Query points outside the polyhedron are closer to some other training example. This kind of diagram is often called the Voronoi diagram of the set of training example

The K- Nearest Neighbor algorithm for approximation a real-valued target function is given below f : Rⁿ à V