K-Nearest Neighbor (KNN) Algorithm
&
K-Means Clustering algorithm
1 / 35
Introduction
K-Nearest Neighbour is one of the simplest Machine Learning
algorithms based on the Supervised Learning technique.
2 / 35
K-NN Algorithm
▶ K-NN algorithm assumes the similarity between the new
case/data and available cases and puts the new case into the
category that is most similar to the available categories.
▶ K-NN algorithm stores all the available data and classifies a
new data point based on the similarity.
▶ K-NN algorithm can be used for Regression as well as for
Classification but mostly it is used for the Classification
problems.
3 / 35
Characteristics of K-NN
▶ It is also called a lazy learner algorithm because it does not
learn from the training set immediately instead it stores the
dataset and at the time of classification, it performs an action
on the dataset.
4 / 35
Example
Suppose we have an image of a creature that looks similar to a cat
and a dog, but we want to know whether it is a cat or a dog. We
can use the KNN algorithm, as it works on a similarity measure.
The model will find similar features of the new data set to the
cats’ and dogs’ images and classify it accordingly.
5 / 35
Why do we need a K-NN Algorithm?
Suppose there are two categories, i.e., Category A and Category B,
and we have a new data point x1 , so this data point will lie in
which of these categories. To solve this type of problem, we need a
K-NN algorithm.
6 / 35
How does K-NN work?
The K-NN working can be explained on the basis of the below
algorithm:
1. Select the number K of the neighbors
2. Calculate the Euclidean distance of K number of neighbors
3. Take the K nearest neighbors as per the calculated Euclidean
distance.
4. Among these K neighbors, count the number of the data
points in each category.
5. Assign the new data points to that category for which the
number of the neighbor is maximum.
6. Our model is ready.
7 / 35
q
d= (x2 − x1 )2 + (y2 − y1 )2 (1)
8 / 35
9 / 35
10 / 35
▶ By calculating the Euclidean distance we got the nearest
neighbors, as three nearest neighbors in category A and two
nearest neighbors in category B.
▶ As we can see the 3 nearest neighbors are from category A,
hence this new data point must belong to category A.
11 / 35
Selecting the Value of K
▶ Firstly, we will choose the number of neighbors, so we will
choose the k = 5. Next, we will calculate the Euclidean
distance between the data points.
▶ There is no particular way to determine the best value for ”K”.
▶ The most preferred value for K is 5.
▶ A very low value for K such as K=1 or K=2, can be noisy and
lead to the effects of outliers.
▶ Large values for K are good, but may have some difficulties.
12 / 35
Distance Metrics Used in KNN Algorithm
KNN uses distance metrics to identify the nearest neighbor. These
neighbors are used for classification and regression tasks. The
following distance metrics are commonly used:
▶ Euclidean Distance:
q
Distance(d) = (x2 − x1 )2 + (y2 − y1 )2 (2)
It represents the straight-line distance between two points in a
plane or space.
▶ Manhattan Distance:
n
X
d(x, y ) = |xi − yi | (3)
i=1
It measures the total distance traveled if only horizontal and
vertical movements are allowed.
13 / 35
Minkowski Distance:
n
!1
X p
p
d(x, y ) = |xi − yi | (4)
i=1
A generalization of both Euclidean and Manhattan distances:
▶ When p = 2, it reduces to Euclidean distance.
▶ When p = 1, it reduces to Manhattan distance.
14 / 35
Advantages of KNN Algorithm
▶ It is simple to implement.
▶ It is robust to the noisy training data.
▶ It can be more effective if the training data is large.
15 / 35
Disadvantages of KNN Algorithm
▶ Always needs to determine the value of K which may be
complex sometimes.
▶ The computation cost is high because of calculating the
distance between the data points for all the training samples.
16 / 35
17 / 35
Voting for Classification or Taking Average for Regression
Voting for Classification:
▶ When classifying a data point into a category (e.g., spam or
not spam), the K-NN algorithm considers the K closest points
in the dataset, known as neighbors.
▶ The algorithm determines which category appears most among
the neighbors and assigns the data point to that category.
▶ This process is called majority voting.
Taking Average for Regression:
▶ In regression, the algorithm still looks for the K closest points.
▶ Instead of voting for a class as in classification, it computes
the average of the values of these K neighbors.
▶ This average serves as the predicted value for the new data
point.
18 / 35
K-Means Clustering algorithm.
19 / 35
K-Means Clustering
▶ K-Means is an unsupervised learning algorithm for clustering
unlabeled data.
▶ It groups data into K clusters based on similarity.
▶ K is the number of clusters chosen in advance.
▶ It is a centroid-based method that minimizes the distance
between data points and their cluster centroids.
20 / 35
Working of K-Means
1. Choose the number of clusters K .
2. Initialize K centroids (randomly or from data points).
3. Assign each data point to the nearest centroid.
4. Update centroids as the mean of assigned points.
5. Repeat steps 3 and 4 until assignments do not change.
21 / 35
Main Tasks and Objective
▶ Find optimal centroids.
▶ Assign each data point to the closest cluster.
▶ Ensure clusters are compact and well separated.
22 / 35
Visual Understanding
▶ Consider two features x1 and x2 .
▶ Plot the data in 2D space.
▶ Choose K = 2 clusters.
▶ Initialize two centroids and apply the K-Means steps.
Illustration of the K-Means clustering process
23 / 35
Unlabelled Data
24 / 35
Selection of random K (= 2) points or centroids
25 / 35
Assign each data point to its closest centroid
26 / 35
Calculate the mean and place a new centroid of each
cluster.
27 / 35
Repeat the same procedure, which means reassigning each
data point to the new closest centroid of each cluster
28 / 35
29 / 35
30 / 35
Finish
31 / 35