K-Nearest Neighbors
- The Intuition Behind K-NN Algorithm
- How KNN works
- Steps Involved in the K-NN Algorithm
- Distance Metrics Used in KNN
- Choosing the K value
- Applications of the KNN Algorithm
- Advantages and Disadvantages
Regression as well as classification problems may be handled using the simple supervised machine learning algorithm K-Nearest Neighbours (K-NN). By comparing the new and old data points, this approach places the new example in a category comparable to the most similar ones already in existence. The main idea is to save predetermined data and classify incoming data according to how similar they are to the previously saved dataset.
Popularity of the K-Nearest Neighbours model is maintained by its stability and simplicity. Its non-parametric feature implies that it is independent of data distribution presumptions. Although applicable to both regression and classification, it predominantly finds use in classification problems. Termed a "lazy learner" algorithm, K-NN delays learning from the training set, instead storing data for on-the-spot classification when needed.
For instance, consider a
scenario with a variety of dog breed images used to train a K-NN model. When
presented with a new dog image, the K-NN algorithm identifies similarities
between its features and those of various dog breeds within the dataset. Based
on these shared features, the algorithm classifies the image into the most
similar breed category.
By emphasizing similarity
measures, the K-Nearest Neighbour algorithm proves valuable in scenarios where a new data point's
classification or regression depends heavily on its resemblance to existing
data. In this chapter the k nearest neighbour learning algorithm we learn.
Let's take a real-world example for KNN
In this k nearest neighbor example let's suppose there is a
mechanic he/she has a talent for fixing cars, but new electric vehicles stumped
them. The error codes were unlike those he/she had seen before. For her/him
diagnosing these electric vehicles felt like navigating a foreign language. Deciding
to get clever, he/she looked to KNN, a technique like having a team of expert
mechanics by him/her side.
Imagine KNN as a toolbox
filed with past cases. Each case is a car with its symptoms (error codes,
battery reading, etc.) and the mechanic’s diagnosis (problem identified). When
a new electric car with a puzzling error rolls in, KNN swings into action.
KNN doesn’t jump to conclusions,
instead, it considers the past cases in the toolbox. It analyzes the new car’s
symptoms and compares them to all the past cases. After that KNN picks a small
group, the K's nearest neighbors, the most similar cars based on their symptoms.
These K's closest
neighbors become like a consultation team for him/her. By looking at the
problems those similar cars had (their diagnoses), KNN helps the mechanic to
predict the most likely issue with the new car. It’s like having a group of
experts who’ve tackled similar problems before, whispering their insights to
mechanics.
This collaborative
approach proved valuable. Faced with an unfamiliar error code, mechanics could
consult their KNN toolbox, identify similar past cases, and make a
well-informed diagnosis. With KNN as their secret weapon, the mechanic became
the go-to electric car mechanic, their skills boosted by the help of KNN.
The intuition behind the KNN algorithm
In the above graph, we
can see two clusters or groups. Now if we have another point (also printed on
the graph) that is unclassified then we can easily assign it to a group. One
approach to accomplish this is by examining the group to which its nearest
neighbors belong. This means that the point in the above diagram will be ‘green’
because it is close to the green cluster.
Why do we need the KNN algorithm?
The widespread
utilization of the K-Nearest Neighbors (K-NN) algorithm stems from its
versatility and wide applicability. Its simplicity and straightforward
implementation are key factors driving its use. One of its standout features is
its lack of reliance on prediction about the underlying data distribution or
how data is scattered, making it suitable for various datasets, whether dealing
with numerical or categorical data in classification and regression tasks.
A significant advantage
lies in its non-parametric nature, leading to predictions grounded in the
similarity among data points within the dataset. Furthermore, K-NN exhibits a
higher tolerance for outliers compared to alternative algorithms.
To discover the K nearest neighbors, the K-NN approach typically uses the Euclidean distance as its distance metric of choice. A data point's class or value is determined by averaging or by taking into account the outcomes of its K nearest neighbors. Because of this adaptive strategy, the algorithm can identify various patterns in the data and forecast outcomes based on the local structure of the data.
How KNN work?
K-Nearest Neighbors
(K-NN) stands as a versatile and widely embraced algorithm due to its
adaptability across various applications. Its allure resides in its simplicity
and ease of implementation. Notably, it distinguishes itself by eschewing
assumptions about the inherent data distribution and rendering. It is suitable for
datasets of diverse natures encompassing numerical and categorical data in both
classification and regression domains.
Its non-parametric
nature forms a cornerstone for predictions, relying on the inherent
similarities among data points housed within the dataset. Another distinctive
trait is its robustness against outliers, surpassing the resilience of
alternative algorithms in this aspect.
By utilizing distance metrics, particularly the prevalent Euclidean distance, the K-NN algorithm identifies the K closest neighbors. Subsequently, the determination of a data point's classification or value involves a process of averaging or considering the majority vote among these K neighbors. This adaptive methodology empowers the algorithm to discern varied data patterns and make predictions rooted in the localized structure of the dataset.
Choosing the K data points from the dataset (X)
that show the shortest distance to the target data point (x) is the first step
in the K-Nearest Neighbors (K-NN) technique. The method in classification
problems finds the most common label (y) among these K nearest neighbors (x). To
determine the projected value for x in a regression job, the method first
calculates the mean, or weighted average or weight mean, of the y values
connected to the K nearest neighbors. Whether determining the most common label
in classification or estimating a continuous value in regression scenarios,
this technique allows the algorithm to generate well-informed predictions based
on the features of the nearest neighbors.
Steps involve in K-NN algorithm working
We can explain the
working of KNN in the following steps:
Step 1- The number of
neighbors, K, needs to be selected appropriately.
Step 2 – After that, we
need to calculate the Euclidean distance (or any other distance) of K number of
neighbors
Step 3 – Now we need to
take the K nearest neighbors as per our calculated Euclidean distance or any
other distance.
Step 4 – after
calculating these k neighbors, we need to count the number of the data points
in each category.
Step 5 – Now we need to
assign the new data points to that category which have a maximum number of
neighbors.
Step 6 – our model is ready to use.
Distance metrics used in the KNN
algorithm
The K-NN (K-Nearest
Neighbors) algorithm works by identifying the closest data points or clusters
to a given query point. This is achieved by using various distance metrics to
measure the closeness of data points. Let's look at one of these metrics:
Euclidean Distance represents the simplest distance measure between two points in a plane. It quantifies the Cartesian distance between these points, essentially illustrating the length of the straight line connecting the considered points. This metric serves to calculate the total displacement undergone between two states of an object or entities in a given space. Visualizing this distance helps in understanding the direct spatial relationship and proximity between data points within a plane or hyperplane.
Manhattan Distance – The
Manhattan distance, also known as the taxicab distance or city block distance,
is widely used when the entire distance traveled by an object needs to be
calculated rather than just moved. This metric is obtained by adding the
absolute differences in the coordinates of two points in a space with
dimensions n.
Minkowski Distance – One illustration of both
the geometric and Manhattan distances is the Minkowski distance. The Minkowski
distance is an extension of the Euclidean and Manhattan distances, and it is a
metric in a normed vector space. This distance measure encapsulates various
distance metrics within a single framework, providing a more generalized
approach to measuring distances between points in a vector space.
By the above formula, we can
say that when p = 2 then is it the same as the Euclidean distance formula, and when
p = 1 then we can get the formula of the Manhattan distance.
The above-described metrics
are the most common metrics that we can use for dealing with machine learning
problems, but we can also use other distance metrics as well if we like or the
problem needs it. Hamming distance is an example of such a metric which is quite
useful when we have problems that require overlapping comparisons between two
vectors whose contents can be Boolean as well as string values.
Choosing the K value for the KNN
algorithm
In the K-Nearest
Neighbors (K-NN) algorithm, the parameter "k" plays an important role
because it determines the number of neighbors considered when running the
algorithm. Choosing the right value of 'k' is key and should be guided by the
particularities of the input data. In situations where the data set is noisy or
contains a significant amount of outliers, choosing a larger value of k often
produces more accurate results.
For improved
classification accuracy, it's advantageous to choose an odd 'k' value, as this
helps prevent ties during the classification process. This choice can enhance
the decisiveness of the algorithm when assigning a class to the query point.
Employing cross-validation techniques serves as a valuable method for determining the most suitable 'k' value for a given dataset. By systematically assessing different 'k' values and their impact on the model's performance, cross-validation aids in identifying the optimal 'k' that maximizes the algorithm's accuracy and generalizability.
Applications of KNN algorithm
- Data Preprocessing – When diving into a machine learning problem, the initial step often involves Exploratory Data Analysis (EDA). In this phase, identifying missing values in the data prompts the need for imputation methods. Among these methods, the KNN Imputer stands out as a sophisticated and effective approach for handling missing data.
- Pattern Recognition – The effectiveness of the K-Nearest Neighbors (KNN) algorithm shines through in scenarios such as training it using the MNIST dataset. Upon evaluation, this model demonstrates notably high accuracy, showcasing the algorithm's prowess in pattern recognition tasks.
- Recommendation Engines – KNN finds prominent applications in recommendation engines. This algorithm's primary task involves assigning a new query point to an existing group, which has been formed using extensive datasets. In the realm of recommender systems, this capability proves crucial, enabling the allocation of users to specific groups based on their preferences. Subsequently, it facilitates personalized recommendations tailored to these groups' inclinations.
Advantages of the KNN algorithm
- Easy to implement – it is easy to implement because its complexity is not very high like other algorithms.
- Adapts Easily – Due to the KNN algorithm's ability to retain all data in memory, whenever a new example or data point is added, it can automatically adapt to the new information and contribute to future predictions.
- Few Hyperparameters: The KNN method requires only two parameters: the choice of 'k' and the choice of the distance metric for our evaluation measure. Due to the small number of hyperparameters, we can easily customize the algorithm.
Disadvantages of the KNN
algorithm
- Does not scale – due to the KNN's other name, the lazy algorithm. It got its moniker because this method uses a lot of processing power and data storage, which makes it resource- and time-intensive.
- Curse of Dimensionality – Peaking phenomena, which is caused by the curse of dimensionality, is a term used in KNN. The method has difficulty correctly identifying the data points we have a dataset that has high dimensionality, which is known as the "curse of dimensionality."
- Prone to overfitting – because the algorithm has the problem of dimensionality curse therefore the algorithm is prone to overfitting as well. Therefore, we need to add feature selection and dimensionality reduction techniques that can help to overcome this problem.
Summary
An easy-to-use yet
powerful technique for classification and regression issues is K-nearest
neighbors or CNN. Its task is to classify or assign a value to each new data
point in the training set by averaging its k nearest neighbors or by using the
majority vote. KNN can be slow when working with large datasets and is
sensitive to features that are irrelevant or noisy, but it is simple to
understand and performs well with small to medium-sized datasets. Despite being
an extremely helpful and user-friendly algorithm, it can also encounter issues
like overfitting and the curse of dimensionality.
Python Code
here is the k nearest neighbor Python code: -
