What is k-NN in Machine Learning?

K-nearest neighbors (k-NN) is a machine learning algorithm that works on the principle that similar data points tend to have similar labels. During training, a k-NN algorithm requires a sample input dataset labeled with corresponding output values. It uses the data to plot an N-dimensional graph representing the input and output relationship. When given an unknown input, it plots the point and determines its category based on the graph's closest neighbors or point group. The closest neighbors are determined mathematically using various methods. The KNN algorithm is used for both classification and regression tasks.

k-NN allows data scientists to build a simple, interpretable, and adaptable supervised machine learning model.

Reduces model complexity

Unlike more complex models, k-NN uses only the k value and the distance metric to generalize the outcome. This results in a simpler model with interpretable results. The k-NN algorithm follows a series of steps to decide if the given data point belongs in one category or another.

Capable of handling non-linear data

The k-NN algorithm is non-parametric. In other words, the model doesn't make assumptions when analyzing data. Instead, it classifies new data by computing and comparing the distance of the new query point and all the data in the training samples. This also makes k-NN suitable for analyzing non-linear or noisy data.

Stores training data in memory

Unlike most machine learning models, the k-NN algorithm stores the training dataset in its memory and uses it to compare the input data. This means the k-NN algorithm only performs computation on the training data once it is fed with new data and is idle in the training phase.

Despite its seemingly simple architecture, the K-nearest neighbors (k-NN) algorithm is highly accurate in classification tasks. Data scientists have applied k-NN effectively in various real-world applications.

Credit scoring

AI systems determine the risks of credit applicants by automatically grouping them with borrowers who share similar characteristics with K-NN techniques. This allows the system to assign a credit score to the new applicant confidently.

Data preprocessing

Datasets for model training might contain missing values, which can cause the model to produce inaccurate or biased results. To overcome this, they use K-NN to replace the missing data with an approximated value. We call this technique data imputation.

Search and recommendation systems

The k-NN algorithm enables users to search for related products or get relevant recommendations. For example, an ecommerce website compares a user to other customers in its database. Then, it recommends products based on what customers with similar preferences bought.

Financial forecasting

Besides classification tasks, a k-NN model can also predict continuous values. When applied as a regression model, k-NN allows financial analysts to confidently make predictions based on previous data points.

Pattern recognition

k-NN excels at analyzing and identifying specific patterns to derive actionable insights. For example, it helps banks identify abnormal activities in transaction records and block suspicious transactions.

Computer vision

Computer vision applications require AI models capable of identifying and categorizing images into their respective classes. k-NN is one of the simplest models for segregating images into their respective categories. For example, you can equip a k-NN model with a training dataset containing images of cats and dogs. Then, k-NN compares new images to both subgroups and determines which they belong to.

k-NN works according to the principle of majority voting, which seeks sufficient qualifying neighboring data points to classify the input data. The model assigns a class label based on the most frequently detected class amongst the k neighbors. For example, if you use k-NN to classify an image into two categories, the required majority vote is more than 50%. However, classifying an image into one of four categories requires votes more significant than 25%.

The principle remains the same when using k-NN for regression tasks. The model compares the new data point with the average values of k nearest neighbors to make predictions. To better understand k-NN, consider the steps required to determine whether an image is a cat or a dog.

• The data scientist loads a training data set containing several labeled images of cats and dogs.

• Then, they decide the optimal value of k to produce the most accurate result.

• Once determined, the k-NN algorithm compares the new image against every image in the training data to determine its distance.

• Upon completion, the model selects a specific number of the nearest data points based on the k value. For example, if k equals 5, the algorithm groups the five nearest images to the input image.

• Finally, the algorithm finds the class to which most grouped images belong by counting each data point in the k-neighbors. Then, it returns the predicted class.

When predicting or classifying data with k-NN, data scientists must select an appropriate distance metric and the k value. We share how they do that below.

Estimating k

The k value determines the number of data points k-NN uses to classify the input data. There is no single k value that works optimally across different use cases. Setting a low k value results in low bias and high variance, which results in underfitting. A model that underfits cannot generalize effectively during training and real-world application. On the other hand, a higher k value causes the model to overfit. Overfitting is characterized by high bias and low variance. In this case, the model can generalize accurately during training but fails with unfamiliar real-world data. So, data scientists must elevate several k values before deciding the most optimal one. Generally, a higher k value allows the model to perform better with noisy data.

Identifying nearest neighbors

The k-NN model decides if data points qualify as the nearest neighbor by using the below distance metrics.

Euclidean distance

Euclidean distance measures the straight line between two data points in a two-dimensional space. Most k-NN algorithms use Euclidean distance to determine the nearest neighbors.

Manhattan distance

Manhattan distance calculates the distance from one data point to another. Rather than measuring the absolute difference between coordinates, it calculates the total distance traveled on the vertical and horizontal axes. Imagine taking a taxi ride from one block to another through the connected roads. That's why the Manhattan distance metric is also known as the taxicab distance.

Minkowski distance

The Minkowski distance is a general distance calculation formula where Euclidean and Manhattan distances were derived. Other variants of distance measurement can also be formed from the Minkowski formula.

Hamming distance

Hamming distance compares two parameters with a similar number of bits. It returns the number of mismatched bits between both parameters.

Approximate nearest neighbors (a-NN) is a machine learning technique that searches and classifies data without evaluating the labeled data set. Like k-NN, a-NN compares the distance between the input and training data to determine the former's class. However, a-NN doesn't repeat the calculation for every single data point. Instead, a-NN divides the training data into several blocks to reduce the search time. a-NN is more practical for applications comparing input data against millions of datasets that don't require highly accurate results.

As the number of data points reaches hundreds of millions or even billions, scaling a k-NN search system can be a major challenge. Organizations must increase computational resources to store and run the k-NN model to maintain generalizing performance.

The k-NN algorithm is also sensitive to the choice of k value. Choosing a less optimal k-value might result in overfitting or underfitting.

k-NN also doesn't perform accurately for high-dimensional data, which are datasets with many features, such as patient medical records. While techniques like feature selection and principal component analysis help k-NN analyze high-dimensional data, they might not be effective for larger datasets.

Amazon SageMaker is a fully managed service to prepare data and build, train, and deploy machine learning (ML) models for any use case with fully managed infrastructure, tools, and workflows. It provides several built-in supervised learning algorithms that can be used for either classification or regression problems.

The Amazon SageMaker k-nearest neighbors algorithm is a supervised algorithm. The algorithm consumes a test data set and emits a metric about the accuracy for a classification task or about the mean squared error for a regression task. These accuracy metrics compare the model predictions for their respective task to the ground truth provided by the empirical test data. To find the best model that reports the highest accuracy or lowest error on the test dataset, run a hyperparameter tuning job for k-NN.

Amazon OpenSearch Service is a managed service that makes it easy for you to perform interactive log analytics, real-time application monitoring, website search, and more. k-NN for Amazon OpenSearch Service lets you search for points in a vector space and find the "nearest neighbors" for those points by Euclidean distance or cosine similarity. Use cases include recommendations (for example, an "other songs you might like" feature in a music application), image recognition, and fraud detection.

Get started with k-NN on AWS by creating a free account today.