DISTANCE BASED ALGORITHMS
Distance based algorithms are methods of classification that each item that is
mapped to the same class may be thought of as more similar to other items in the
class than it is to the items found in the other classes. Therefore, similarity (or
distance) measures may be used to identify the “alikeness” of different items in the
database.
The two standard approaches are as follows :
1. Simple Approach (IR Approach)
2. K nearest neighbors
Simple Approach (IR Approach): Simple approach is that after the
representative vector (Centroids or Medoids) for each class is determined, it
is used to place each item in the class where it is most similar (closest) to the
center of the class.
Definition: Given a database D={ti,t2,t3,….,tn} of tuples where each tuple
ti={ti1,ti2,….tik} contains numeric values add a set of classes C = {C1,
…..,Cm} where each class Cj = {Cj1,Cj2,….Cjk} has numeric values,the
classification problem is to assign each ti to the class such that (ti,Cj)≥sim(ti,Cl)
VCl€C where Cl ≠Cj.
We can determine a representative for each class by calculating the center of
each region .Thus class A is represented by (4,7.5), class B (2,2.5),class
C(6,2.5).A simple classification technique ,then, would be to place each item in
the class where it is most similar (closest) to the center of that class. The
representative for the class may be found in other ways .
For example, in pattern recognition problems, a predefined pattern can be
used to represent each class. Once similarity measure is defined ,each item to be
classified will be compared to each predefined pattern. The item will be placed
in the class with the largest similarity value.
K nearest neighbors: K nearest neighbors (KNN) assumes that the entire training
set includes not only the data in the set but also the desired classification for each
item. In effect, the training database becomes the model. When a classification is
to be made for a new item , its distance to each item in the training set must be
determined. Only the K closest entries in the training set are considered further.
The new item is then placed in the class that contains the most items from this set
of K closest items.
K Nearest Neighbour is a simple algorithm that stores all the available
cases and classifies the new data or case based on a similarity measure. It
is mostly used to classifies a data point based on how its neighbours are
classified.
‘k’ in KNN is a parameter that refers to the number of nearest neighbours
to include in the majority of the voting process.
Let’s say k = 5 and the new data point is classified by the majority of
votes from its five neighbours and the new point would be classified as
red since four out of five neighbours are red.
1. There is no structured method to find the best value for “K”. We need to find
out with various values by trial and error and assuming that training data is
unknown.
2. Choosing smaller values for K can be noisy and will have a higher influence on
the result.
3) Larger values of K will have smoother decision boundaries which mean lower
variance but increased bias. Also, computationally expensive.
4) Another way to choose K is though cross-validation. One way to select the cross-
validation dataset from the training dataset. Take the small portion from the training
dataset and call it a validation dataset, and then use the same to evaluate different
possible values of K. This way we are going to predict the label for every instance
in the validation set using with K equals to 1, K equals to 2, K equals to 3. and then
we look at what value of K gives us the best performance on the validation set and
then we can take that value and use that as the final setting of our algorithm so we
are minimizing the validation error .
5) In general, practice, choosing the value of k is k = sqrt(N) where N stands for
the number of samples in your training dataset.
How does KNN Algorithm works?
In the classification setting, the K-nearest neighbor algorithm essentially boils down
to forming a majority vote between the K most similar instances to a given
“unseen” observation. Similarity is defined according to a distance metric between
two data points. A popular one is the Euclidean distance method
Other methods are Manhattan, Minkowski, and Hamming distance methods.
Advantages
1. Simple to implement
2. Flexible to feature/distance choices
3. Naturally handles multi-class cases
4. Can do well in practice with enough representative data
DISADVANTAGES
1. Need to determine the value of parameter K (number of nearest neighbors)
2. Computation cost is quite high because we need to compute the distance of
each query instance to all training samples.
3. Storage of data
4. Must know we have a meaningful distance function.