Uncodemy - India's Best IT Training Institute in Noida

Clustering in Machine Learning: Unsupervised Learning for Grouping Data

Bambam Kumar/ 5 days
0
5 min read

Clustering-in-Machine-Learning-Unsupervised-Learning-for-Grouping-Data

What is Clustering?

Clustering is a technique in machinery learning where we group data points based on how similar they are to each other. This is known as Cluster Analysis, and it falls under Unsupervised Learning . Unlike supervised learning, where we have labeled data and a target variable to predict, clustering deals with unlabeled data—meaning we don’t have predefined categories for the data.

The goal of clustering is to organize data into groups (called clusters) that are similar within the group but different from other groups. To decide how similar data points are, we use methods like Euclidean distance, Cosine similarity, or Manhattan distance. These helps determine which data points should be grouped together.

For example, imagine a graph with data points where we can clearly see 3 distinct groups or clusters based on how close the points are to each other. However, it’s important to note that clusters don’t always have to be circular in shape. In some cases, clusters can have irregular or arbitrary shapes, and there are algorithms designed to identify these non-circular clusters as well.

In short, clustering helps us understand the natural structure in data by grouping similar items together, whether they form circular clusters or more complex shapes.

Types of Clustering

Clustering can be divided into two main types based on how we assign data points to clusters:

Hard Clustering

In hard clustering, each data point belongs to only one cluster, with no overlap. For example, if we have four data points and need to group them into two clusters, each point will be assigned to either one cluster or the other. There’s no gray area—each data point is clearly in one cluster.
Example:
- Data Point A → Cluster 1 (C1)
- Data Point B → Cluster 2 (C2)
- Data Point C → Cluster 2 (C2)
- Data Point D → Cluster 1 (C1)

Soft Clustering

In soft clustering, things are a bit more flexible. Instead of assigning a data point to just one cluster, we calculate the probability or likelihood that a data point belongs to each cluster. So, a data point might belong to more than one cluster, but with different probabilities.
Example:
- Data Point A → 91% likely in Cluster 1 (C1), 9% likely in Cluster 2 (C2)
- Data Point B → 30% likely in Cluster 1 (C1), 70% likely in Cluster 2 (C2)
- Data Point C → 17% likely in Cluster 1 (C1), 83% likely in Cluster 2 (C2)
- Data Point D → 100% likely in Cluster 1 (C1), 0% likely in Cluster 2 (C2)

Uses of Clustering

Clustering algorithms have a wide range of uses in different fields. Here are some common ways they are applied:

Market Segmentation

Businesses use clustering to divide their customers into groups based on their behavior or characteristics. This helps them create personalized ads to target specific audiences more effectively.

Market Basket Analysis

Retailers analyze sales data to find out which items are often bought together. For example, a study in the USA found that diapers and beer were frequently bought together by fathers, which helped store owners in their product placement strategies.

Social Network Analysis

Social media platforms use clustering to analyze your online behavior and suggest friends or content based on your interests and activities.

Medical Imaging

Doctors use clustering in medical imaging to identify areas of concern, like detecting abnormal regions in X-rays or MRIs. This helps in diagnosing diseases like cancer or other medical conditions.

Anomaly Detection

Clustering can help detect unusual patterns in data, such as identifying fraud in financial transactions or finding outliers in real-time data streams.

Simplifying Large Datasets

When working with large datasets, clustering can simplify the data by assigning each data point to a cluster. Instead of dealing with the individual details of each point, you can work with the simpler cluster ID, which makes complex data easier to manage and analyze.

Types and Methods of Clustering Algorithms

Clustering is a machine learning technique used to analyze unstructured data by grouping similar data points together. The way these clusters are formed depends on factors like the data points’ proximity to each other, the shortest distance between them, and their overall density. Clustering works by measuring how related or similar the objects are using a metric known as the similarity measure. These similarity metrics are easier to define when there are fewer features, but as the number of features increases, it becomes more challenging to create effective similarity measures. Different clustering algorithms use various techniques to group data from datasets based on their specific approach.

There are different approaches or types of clustering algorithms used for grouping data. Here are the main types:

Centroid-based Clustering (Partitioning methods)
Density-based Clustering (Model-based methods)
Connectivity-based Clustering (Hierarchical clustering)
Distribution-based Clustering

types-of-clustering-algorithms

We will be going through each of these types in brief.

Centroid-based Clustering (Partitioning Methods)

Partitioning methods are some of the simplest clustering algorithms. These methods group data points based on how close they are to each other. The most common similarity measures used for these algorithms are Euclidean distance, Manhattan distance, or Minkowski distance. The data is split into a set number of clusters, and each cluster is represented by a central point (a vector of values). Data points that are similar to this central point are grouped together into that cluster.

However, one major challenge with these methods is that we need to decide in advance how many clusters (denoted as “k”) we want. This can be done through intuition or using techniques like the Elbow Method to determine the best number of clusters. Despite this, centroid-based clustering is still widely used. K-means and K-medoids are two popular algorithms in this category.

K-Means Cluster Analysis is a popular clustering algorithm used to group data points into a specified number of clusters (denoted as K ). Here’s how it works in simple steps:

Initialize: Choose K initial cluster centers (centroids) randomly.
Assign: Each data point is assigned to the nearest centroid, forming clusters.
Update: Recalculate the centroids by finding the mean of all points in each cluster.
Repeat: Steps 2 and 3 are repeated until the centroids no longer change significantly, meaning the clusters are stable.

K-Medoids Cluster Analysis is similar to , but instead of using the mean of data points to represent the center of a cluster, it uses actual data points, known as medoids . Here’s a simplified explanation of how it works:

Initialize: Select K data points randomly as the initial medoids (the center of each cluster).
Assign: Each data point is assigned to the nearest medoid, forming clusters.
Update: Recalculate the medoids by choosing the point within each cluster that minimizes the sum of the distances to all other points in that cluster.
Repeat: Steps 2 and 3 are repeated until the medoids no longer change significantly.

Density-based Clustering (Model-based Methods)

Density-based clustering, a model-based approach, groups data points based on their density. Unlike centroid-based clustering, which requires the number of clusters to be predefined and is sensitive to initial conditions, density-based clustering determines the number of clusters automatically and is more robust to starting points. This method is particularly effective for handling clusters of various sizes and shapes, making it ideal for datasets with irregular or overlapping clusters. It focuses on local density, allowing it to distinguish clusters with different structures, and can handle both dense and sparse areas in the data.

In comparison, centroid-based methods like K-means struggle with arbitrary-shaped clusters. Since these methods require a fixed number of clusters and are highly sensitive to the initial positioning of centroids, the results can vary significantly. Additionally, centroid-based algorithms tend to form spherical or convex clusters, which limits their ability to handle complex or irregularly shaped clusters.

Overall, density-based clustering addresses these limitations by automatically determining cluster sizes, being resistant to initialization issues, and efficiently capturing clusters with different shapes and sizes. The most widely used algorithm in this category is DBSCAN (Density-Based Spatial Clustering of Applications with Noise).

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based clustering algorithm that groups data points based on their density. It is effective at finding clusters of arbitrary shapes and can handle noise (outliers) in the data.

Here’s how it works:

Core Points:A data point is considered a “core point” if it has a minimum number of points (MinPts) within a specified radius (ε).
Directly Density-Reachable:Points within the ε distance of a core point are considered part of the same cluster.
Density-Reachable:Points that are not core points but are within ε of a core point are also included in the cluster.
Noise:Points that are not part of any cluster (i.e., they don’t meet the density criteria) are considered noise or outliers.

Connectivity-based Clustering (Hierarchical Clustering)

Hierarchical clustering is a method that groups related data points into hierarchical clusters. Initially, each data point is treated as its own separate cluster. These individual clusters are then combined with the most similar ones to form larger clusters, eventually creating one large cluster that contains all the data points.

Imagine you are organizing a collection of items based on their similarity. In hierarchical clustering, each item starts as its own cluster at the base of a tree structure, called a dendrogram. The algorithm then analyzes how similar the items are to each other and progressively merges the closest clusters into larger ones. The process continues until all the items are merged into one final cluster at the top of the tree.

One of the appealing features of hierarchical clustering is the ability to explore different levels of granularity. By cutting the dendrogram at a specific height, you can decide how many clusters you want. The closer two items are within a cluster, the more similar they are to each other, similar to how items in a family tree are grouped based on their relationships. The nearest relatives are clustered together, and the wider branches represent more general connections.

There are two main approaches to hierarchical clustering:

Divisive Clustering
Agglomerative Clustering

Divisive Clustering (Top-down Approach)

Divisive clustering works in the opposite direction to agglomerative clustering. In this approach, all data points start together in a single large cluster. The goal is to split this large cluster into smaller sub-clusters, one by one, based on their similarities.

Here’s how it works:

Step 1: Start with all data points grouped together in one cluster.
Step 2: The algorithm then examines the largest cluster and splits it into two smaller, more similar groups.
Step 3: This process continues recursively. Each time, the algorithm divides the largest cluster into smaller clusters.
Step 4: The process stops when each data point is in its own individual cluster or when the desired number of clusters is achieved.

This method is less commonly used compared to agglomerative clustering because it’s more computationally expensive, as it requires more analysis to identify the best way to split each cluster.

Agglomerative Clustering (Bottom-up Approach)

Agglomerative clustering is the most common hierarchical clustering method. Unlike divisive clustering, it starts with each data point as its own individual cluster and progressively merges the closest clusters together. It’s a bottom-up approach.

Here’s how it works:

Step 1: Initially, each data point is treated as a separate cluster.
Step 2: The algorithm calculates the similarity between each pair of clusters and merges the two most similar clusters into one.
Step 3: This merging process continues, with the algorithm combining the closest clusters at each step, until all the data points are grouped into one final cluster.
Step 4:A dendrogram (tree-like diagram) is created to visualize how clusters are combined over time.

Distribution-based Clustering

In distribution-based clustering, data points are grouped based on their likelihood of belonging to the same probability distribution, such as Gaussian, binomial, or others. The algorithm assumes that data points are generated from one or more statistical distributions, and each cluster is treated as a separate distribution. Data points that are more likely to belong to a particular distribution are grouped together, with the likelihood decreasing as the data points move further from the cluster’s central point, which represents the cluster’s center.

One challenge with density-based and boundary-based approaches is that some algorithms require predefining the number of clusters or the form of the clusters. These methods also require selecting tuning parameters or hyperparameters, and choosing them incorrectly can lead to unexpected results.

In comparison, distribution-based clustering offers more flexibility, accuracy, and better-defined cluster structures than proximity and centroid-based methods. However, a key limitation is that many distribution-based algorithms are best suited for simulated or well-structured data, where most data points fit a preset distribution, and they may struggle with real-world, complex datasets. The most widely used algorithm in this category is the Gaussian Mixture Model (GMM).

The Gaussian Mixture Model (GMM) is a popular distribution-based clustering algorithm that assumes the data is generated from a mixture of several Gaussian (normal) distributions. Each cluster in GMM is represented by a Gaussian distribution with its own mean and variance.

Here’s how it works in short:

Assumption: GMM assumes that the data points are drawn from multiple Gaussian distributions, each corresponding to a cluster.
Model:Each cluster has a mean (center), variance (spread), and a probability distribution.
Expectation-Maximization (EM): GMM uses the EM algorithm to iteratively refine the parameters (mean, variance, and weight of each distribution). It does this by:

Expectation step (E-step):Estimating the probability of each data point belonging to each Gaussian distribution (cluster).
Maximization step (M-step):Updating the parameters of the Gaussians based on these probabilities.