k-Nearest Neighbors(k-NN)

The k-nearest neighbors algorithm is a non-parametric, supervised learning classifier, which uses 'feature similarity' to predict the values of any new data points. In a sentence, given a set of already labeled points, a positive integer k, and a distance measure d(e.g., Euclidean, Hamming, etc), for a new input point p, k-NN labels p as the most present class among its k neighbors that are in the labeled set.

Figure 1 : Visual presentation of simulated working example. Class 1,2 and 3 are denoted by red, green, and blue colors, respectively. Dots represent test data and triangles are training data. k=6. ^[1]

Pros and Cons

Advantages

• Easy to implement due to its simplicity and accuracy
• Adapts easily as new training samples are added since all training data is stored in memory
• Only requires a k value and a distance metric

Challenges

• Does not scale well and can be costly from both a time and money perspective
• Does not perform well with high-dimensional data inputs
• Lower values of k can overfit the data, whereas higher values of k tend to average the values over a greater area and then underfit the data ^[2]

Application Scenario

• Data preprocessing
• Recommendation Engines
• Finance
• Healthcare
• Pattern Recognition

References