K-Nearest Neighbours

http://www.geeksforgeeks.org/k-nearest-neighbours/

K-Nearest Neighbours is one of the most basic yet essential classification algorithms in Machine Learning. It belongs to the supervised learning domain and finds intense application in pattern recognition, data mining and intrusion detection.

It is widely disposable in real-life scenarios since it is non-parametric, meaning, it does not make any underlying assumptions about the distribution of data (as opposed to other algorithms such as GMM, which assume a Gaussian distribution of the given data).

We are given some prior data (also called training data), which classifies coordinates into groups identified by an attribute.

If we plot these points on a graph, we may be able to locate some clusters, or groups. Now, given an unclassified point, we can assign it to a group by observing what group its nearest neighbours belong to. This means, a point close to a cluster of points classified as ‘Red’ has a higher probability of getting classified as ‘Red’.

Intuitively, we can see that the first point (2.5, 7) should be classified as ‘Blue’ and the second point (5.5, 4.5) should be classified as ‘Red’.

Algorithm
Let m be the number of training data samples. Let p be an unknown point.

1. Store the training samples in an array of data points arr[]. This means each element of this array represents a tuple (x, y).

2. for i=0 to m:
     Calculate Euclidean distance d(arr[i], p).

3. Make set S of K smallest distances obtained. Each of these distances correspond to an already classified data point.
4. Return the majority label among S.

K can be kept as an odd number so that we can calculate a clear majority in the case where only two groups are possible (e.g. Red/Blue). With increasing K, we get smoother, more defined boundaries across different classifications. Also, the accuracy of the above classifier increases as we increase the number of data points in the training set.

struct Point

{

    int val;        // Group of point

    int x, y;       // Co-ordinate of point

    double distance;  // Distance from test point

};

 

// Used to sort an array of points by increasing

// order of distance

bool comparison(Point a, Point b)

{

     return (a.distance < b.distance);

}

 

// This function finds classification of point p using

// k nearest neighbour algorithm. It assumes only two

// groups and returns 0 if p belongs to group 0, else

// 1 (belongs to group 1).

int classifyAPoint(Point arr[], int n, int k, Point p)

{

    // Fill distances of all points from p

    for (int i = 0; i < n; i++)

        arr[i].distance =

            sqrt((arr[i].x - p.x) * (arr[i].x - p.x) +

                 (arr[i].y - p.y) * (arr[i].y - p.y));

 

    // Sort the Points by distance from p

    sort(arr, arr+n, comparison);

 

    // Now consider the first k elements and only

    // two groups

    int freq1 = 0;      // Frequency of group 0

    int freq2 = 0;      // Frequency of group 1

    for (int i = 0; i < k; i++)

    {

        if (arr[i].val == 0)

            freq1++;

        else if (arr[i].val == 1)

            freq2++;

    }

 

    return (freq1 > freq2 ? 0 : 1);

}