k Nearest Neighbours algorithm

In machine learning, k Nearest Neighbours or kNN is the simplest of all

machine learning algorithms. It is a non-parametric algorithm used for
classification and regression tasks. Non-parametric means there is no
assumption required for data distribution. So, kNN does not require any
underlying assumption to be made. In both classification and regression
tasks, the input consists of the k closest training examples in the feature
space. The output depends upon whether kNN is used for classification or
regression purposes.

 In kNN classification, the output is a class membership. The given

data point is classified based on the majority of type of its
neighbours. The data point is assigned to the most frequent class
among its k nearest neighbours. Usually k is a small positive integer.
If k=1, then the data point is simply assigned to the class of that
single nearest neighbour.

 In kNN regression, the output is simply some property value for the
object. This value is the average of the values of k nearest
neighbours.

kNN is a type of instance-based learning or lazy learning. Lazy learning

means it does not require any training data points for model generation.
All training data will be used in the testing phase. This makes training
faster and testing slower and costlier. So, the testing phase requires more
time and memory resources.

In kNN, the neighbours are taken from a set of objects for which the class
or the object property value is known. This can be thought of as the
training set for the kNN algorithm, though no explicit training step is
required. In both classification and regression kNN algorithm, we can
assign weight to the contributions of the neighbours. So, nearest
neighbours contribute more to the average than the more distant ones.

2. k Nearest Neighbours intuition

The kNN algorithm intuition is very simple to understand. It simply

calculates the distance between a sample data point and all the other
training data points. The distance can be Euclidean distance or Manhattan
distance. Then, it selects the k nearest data points where k can be any
integer. Finally, it assigns the sample data point to the class to which the
majority of the k data points belong.

Now, we will see kNN algorithm in action. Suppose, we have a dataset

with two variables which are classified as Red and Blue.
In kNN algorithm, k is the number of nearest neighbours. Generally, k is
an odd number because it helps to decide the majority of the class. When
k=1, then the algorithm is known as the nearest neighbour algorithm.

Now, we want to classify a new data point X into Blue class or Red class.
Suppose the value of k is 3. The kNN algorithm starts by calculating the
distance between X and all the other data points. It then finds the 3
nearest points with least distance to point X.

In the final step of the kNN algorithm, we assign the new data point X to
the majority of the class of the 3 nearest points. If 2 of the 3 nearest
points belong to the class Red while 1 belong to the class Blue, then we
classify the new data point as Red.

3. How to decide the number of neighbours in kNN

While building the kNN classifier model, one question that come to my
mind is what should be the value of nearest neighbours (k) that yields
highest accuracy. This is a very important question because the
classification accuracy depends upon our choice of k.

The number of neighbours (k) in kNN is a parameter that we need to

select at the time of model building. Selecting the optimal value of k in
kNN is the most critical problem. A small value of k means that noise will
have higher influence on the result. So, probability of overfitting is very
high. A large value of k makes it computationally expensive in terms of
time to build the kNN model. Also, a large value of k will have a smoother
decision boundary which means lower variance but higher bias.

The data scientists choose an odd value of k if the number of classes is

even. We can apply the elbow method to select the value of k. To optimize
the results, we can use Cross Validation technique. Using the cross-
validation technique, we can test the kNN algorithm with different values
of k. The model which gives good accuracy can be considered to be an
optimal choice. It depends on individual cases and at times best process is
to run through each possible value of k and test our result.

4. Eager learners vs lazy learners

Eager learners mean when giving training data points, we will construct a
generalized model before performing prediction on given new points to
classify. We can think of such learners as being ready, active and eager to
classify new data points.

Lazy learning means there is no need for learning or training of the model
and all of the data points are used at the time of prediction. Lazy learners
wait until the last minute before classifying any data point. They merely
store the training dataset and waits until classification needs to perform.
Lazy learners are also known as instance-based learners because lazy
learners store the training points or instances, and all learning is based on
instances.

Unlike eager learners, lazy learners do less work in the training phase and
more work in the testing phase to make a classification.

Applications of KNN (Very Short)

 Classification: spam detection, disease diagnosis, image

recognition.

 Regression: predicting house prices, rainfall, temperature.

 Recommendation systems: similar products/movies/songs.

 Anomaly detection: fraud detection, unusual sensor data.

 Finance: credit scoring, customer segmentation.

 Environment: LULC classification, flood susceptibility mapping.

Advantages of KNN

 Very easy to implement

 No training time (lazy learner)

 Works well with small datasets

 Good for classification with nonlinear boundaries

Limitations of KNN

 Slow for large datasets

 Sensitive to noise and outliers

 Performance depends heavily on choosing K

 Needs proper scaling (Standardization/Normalization)

K mean

What is K-Means Clustering?

K-means clustering is a popular unsupervised machine learning

algorithm used for partitioning a dataset into a pre-defined number of
clusters. The goal is to group similar data points together and discover
underlying patterns or structures within the data.

 Recall the first property of clusters – it states that the points within a
cluster should be similar to each other. So, our aim here is to
minimize the distance between the points within a cluster.
  There is an algorithm that tries to minimize the distance of the
points in a cluster with their centroid – the k-means clustering
technique.

 K-means is a centroid-based algorithm or a distance-based

algorithm, where we calculate the distances to assign a point to a
cluster. In K-Means, each cluster is associated with a centroid.

The main objective of the K-Means algorithm is to minimize the

sum of distances between the points and their respective cluster
centroid.

Optimization plays a crucial role in the k-means clustering algorithm. The

goal of the optimization process is to find the best set of centroids that
minimizes the sum of squared distances between each data point and its
closest centroid.

To learn more about clustering and other machine learning

algorithms (both supervised and unsupervised) check out
our GenAI Pinnacle Plus Program!

How K-Means Clustering Works?

Here’s how it works:

1. Initialization: Start by randomly selecting K points from the

dataset. These points will act as the initial cluster centroids.

2. Assignment: For each data point in the dataset, calculate the

distance between that point and each of the K centroids. Assign the
data point to the cluster whose centroid is closest to it. This step
effectively forms K clusters.

3. Update centroids: Once all data points have been assigned to

clusters, recalculate the centroids of the clusters by taking the mean
of all data points assigned to each cluster.

4. Repeat: Repeat steps 2 and 3 until convergence. Convergence

occurs when the centroids no longer change significantly or when a
specified number of iterations is reached.

5. Final Result: Once convergence is achieved, the algorithm outputs

the final cluster centroids and the assignment of each data point to
a cluster.

Objective of k means Clustering

The main objective of k-means clustering is to partition your data into a

specific number (k) of groups, where data points within each group are
similar and dissimilar to points in other groups. It achieves this by
minimizing the distance between data points and their assigned cluster’s
center, called the centroid.

Here’s an objective:

 Grouping similar data points: K-means aims to identify patterns

in your data by grouping data points that share similar
characteristics together. This allows you to discover underlying
structures within the data.

 Minimizing within-cluster distance: The algorithm strives

to make sure data points within a cluster are as close as possible to
each other, as measured by a distance metric (usually Euclidean
distance). This ensures tight-knit clusters with high cohesiveness.

 Maximizing between-cluster distance: Conversely, k-means

also tries to maximize the separation between clusters. Ideally, data
points from different clusters should be far apart, making the
clusters distinct from each other.

What is Clustering?

Cluster analysis is a technique in data mining and machine learning that

groups similar objects into clusters. K-means clustering, a popular method,
aims to divide a set of objects into K clusters, minimizing the sum of
squared distances between the objects and their respective cluster
centers.

Hierarchical clustering and k-means clustering are two popular techniques

in the field of unsupervised learning used for clustering data points into
distinct groups. While k-means clustering divides data into a predefined
number of clusters, hierarchical clustering creates a hierarchical tree-like
structure to represent the relationships between the clusters.

Clustering simply means the assigning of data points to groups based

upon how similar the points are to each other. A clustering algorithm
makes "birds of a feather flock together," so to speak.

When used for feature engineering, we could attempt to discover groups

of customers representing a market segment, for instance, or geographic
areas that share similar weather patterns. Adding a feature of cluster
labels can help machine learning models untangle complicated
relationships of space or proximity.

Cluster Labels as a Feature

Applied to a single real-valued feature, clustering acts like a traditional
"binning" or "discretization" transform. On multiple features, it's like
"multi-dimensional binning" (sometimes called vector quantization).

Left: Clustering a single feature. Right: Clustering across two features.

Added to a dataframe, a feature of cluster labels might look like this:

Longitu Latitud Cluste

de e r

-93.619 42.054 3

-93.619 42.053 3

-93.638 42.060 1

-93.602 41.988 0

It's important to remember that this Cluster feature is categorical. Here,

it's shown with a label encoding (that is, as a sequence of integers) as a
typical clustering algorithm would produce; depending on your model, a
one-hot encoding may be more appropriate.

The motivating idea for adding cluster labels is that the clusters will break
up complicated relationships across features into simpler chunks. Our
model can then just learn the simpler chunks one-by-one instead having
to learn the complicated whole all at once. It's a "divide and conquer"
strategy.

Clustering the YearBuilt feature helps this linear model learn its
relationship to SalePrice.

The figure shows how clustering can improve a simple linear model. The
curved relationship between the YearBuilt and SalePrice is too complicated
for this kind of model -- it underfits. On smaller chunks however the
relationship is almost linear, and that the model can learn easily.

k-Means Clustering

There are a great many clustering algorithms. They differ primarily in how
they measure "similarity" or "proximity" and in what kinds of features they
work with. The algorithm we'll use, k-means, is intuitive and easy to apply
in a feature engineering context. Depending on your application another
algorithm might be more appropriate.

K-means clustering measures similarity using ordinary straight-line

distance (Euclidean distance, in other words). It creates clusters by
placing a number of points, called centroids, inside the feature-space.
Each point in the dataset is assigned to the cluster of whichever centroid
it's closest to. The "k" in "k-means" is how many centroids (that is,
clusters) it creates. You define the k yourself.

You could imagine each centroid capturing points through a sequence of

radiating circles. When sets of circles from competing centroids overlap
they form a line. The result is what's called a Voronoi tessallation. The
tessallation shows you to what clusters future data will be assigned; the
tessallation is essentially what k-means learns from its training data.

The clustering on the Ames dataset above is a k-means clustering. Here is

the same figure with the tessallation and centroids shown.
K-means clustering creates a Voronoi tessallation of the feature space.

Let's review how the k-means algorithm learns the clusters and what that
means for feature engineering. We'll focus on three parameters from
scikit-learn's implementation: n_clusters, max_iter, and n_init.

It's a simple two-step process. The algorithm starts by randomly

initializing some predefined number (n_clusters) of centroids. It then
iterates over these two operations:

1. assign points to the nearest cluster centroid

2. move each centroid to minimize the distance to its points

It iterates over these two steps until the centroids aren't moving anymore,
or until some maximum number of iterations has passed (max_iter).
It often happens that the initial random position of the centroids ends in a
poor clustering. For this reason the algorithm repeats a number of times
(n_init) and returns the clustering that has the least total distance
between each point and its centroid, the optimal clustering.

The animation below shows the algorithm in action. It illustrates the

dependence of the result on the initial centroids and the importance of
iterating until convergence.

The K-means clustering algorithm on Airbnb rentals in NYC.

You may need to increase the max_iter for a large number of clusters
or n_init for a complex dataset. Ordinarily though the only parameter
you'll need to choose yourself is n_clusters (k, that is). The best
partitioning for a set of features depends on the model you're using and
what you're trying to predict, so it's best to tune it like any
hyperparameter (through cross-validation, say).

Example - California Housing

As spatial features, California Housing's 'Latitude' and 'Longitude' make

natural candidates for k-means clustering. In this example we'll cluster
these with 'MedInc' (median income) to create economic segments in
different regions of California.