Section 1.1: The Basics of Clustering

Clustering is a key unsupervised learning task in Machine Learning, differing from supervised learning due to the absence of labeled data. While classification algorithms like Random Forest or Support Vector Machines rely on labeled data points for training, clustering algorithms operate on unlabeled data, aiming to reveal the structures and patterns within the dataset.

To illustrate this concept, let’s consider a synthetic dataset representing three different species of flowers.

In this scatter plot, each flower species is depicted in a unique color. If the dataset includes labels for each data point, we can use a classification algorithm, such as Random Forest or SVM. However, in many real-world scenarios, the data we collect may lack labels.

In such cases, classification algorithms become ineffective. Instead, clustering algorithms excel at identifying groups of data points that share similar characteristics.

Identifying similarities and differences among data points can sometimes be straightforward; for instance, the cluster of points in the bottom-left corner is noticeably distinct from others. Yet, it can be challenging to separate the remaining instances into coherent groups, particularly when the number of classes in the dataset is unknown.

Moreover, clustering algorithms outperform human analysts significantly in segregating data classes, as they can evaluate multiple dimensions efficiently, leveraging all data features. In contrast, humans are limited to visualizing only two or occasionally three dimensions.

The table below summarizes the primary differences between clustering and classification approaches.

If you're interested in how the synthetic data above was generated, here’s a simple code snippet:

import numpy as np

import matplotlib.pyplot as plt

import seaborn as sns

# Set random seed for reproducibility

np.random.seed(42)

# Number of data points per cluster

num_points = 50

spread = 0.5

# Generate data for cluster 1

cluster1_x = np.random.normal(loc=1.5, scale=spread, size=num_points)

cluster1_y = np.random.normal(loc=0.5, scale=spread, size=num_points)

# Generate data for cluster 2

cluster2_x = np.random.normal(loc=4, scale=spread, size=num_points)

cluster2_y = np.random.normal(loc=1.2, scale=spread, size=num_points)

# Generate data for cluster 3

cluster3_x = np.random.normal(loc=6, scale=spread, size=num_points)

cluster3_y = np.random.normal(loc=2, scale=spread, size=num_points)

# Concatenate data from all clusters

x = np.concatenate([cluster1_x, cluster2_x, cluster3_x])

y = np.concatenate([cluster1_y, cluster2_y, cluster3_y])

# Plot 1

fig, ax = plt.subplots(figsize=(16, 8))

plt.scatter(cluster1_x, cluster1_y, color=sns.color_palette("hls", 24)[1], alpha=.9, s=140)

plt.scatter(cluster2_x, cluster2_y, color=sns.color_palette("hls", 24)[7], alpha=.9, s=140)

plt.scatter(cluster3_x, cluster3_y, color=sns.color_palette("hls", 24)[15], alpha=.9, s=140)

plt.legend(labels=['Flower A', 'Flower B', 'Flower C'], loc='lower right')

plt.title('Synthetic Data with 3 Clusters: Labels Available')

plt.xlabel('Petal length')

plt.ylabel('Petal width')

# Plot 2

fig, ax = plt.subplots(figsize=(16, 8))

plt.scatter(x, y, color='k', alpha=.9, s=140)

plt.title('Synthetic Data with 3 Clusters: Labels Not Available')

plt.xlabel('Petal length')

plt.ylabel('Petal width')

Section 1.2: Applications of Clustering

Clustering plays a vital role in various domains within Machine Learning and Data Science. Here are some notable applications:

1. Customer Segmentation: Commonly used in e-commerce and financial applications, clustering techniques categorize customers based on purchasing behaviors, preferences, or demographics.
2. Anomaly Detection: Clustering is a robust tool for identifying anomalies in fields like cybersecurity and finance. By clustering normal data patterns, outliers can be swiftly identified and addressed.
3. Genomic Clustering: In bioinformatics, clustering algorithms analyze genomic data to find similarities or differences in genetic material, aiding in the classification of genes into functional groups.

In summary, clustering algorithms are essential for extracting meaningful patterns from unlabeled data.

Section 2.1: K-Means Clustering

K-means clustering is a well-known unsupervised Machine Learning algorithm designed to partition data into K distinct clusters. The algorithm iteratively assigns data points to the nearest cluster centroid and updates the centroids based on the mean of the assigned points. This process continues until convergence, where the centroids change minimally or a predefined number of iterations is reached.

K-means aims to minimize the within-cluster sum of squares (WCSS), also referred to as inertia. Mathematically, the objective function can be defined as follows:

[

text{Inertia} = sum_{i=1}^{K} sum_{x in C_i} |x - mu_i|^2

]

where (C_i) represents the data points assigned to cluster (i), and (mu_i) denotes the centroid of cluster (i).

To effectively minimize inertia, K-means follows these steps:

1. Initialization: Randomly select K centroids.
2. Assignment: Assign each data point to the nearest centroid.
3. Update Centroids: Recalculate the centroids based on the mean of the assigned points.
4. Repeat: Continue steps 2 and 3 until convergence or a maximum number of iterations is reached.

Although K-means converges mathematically, it may not always reach the optimal solution due to local optima. To mitigate this issue, you can either manually choose initial centroids if you have a rough idea of their locations or run the K-means algorithm multiple times with different random initializations and keep the best result.

A critical aspect of K-means is determining the number of clusters, K. Various methods can assist in this decision, with the Elbow method being the most common. This method involves plotting WCSS against the number of clusters, K. As K increases, WCSS typically decreases; however, the rate of decrease slows down at a certain point, creating an "elbow" in the plot. The optimal number of clusters is usually identified at this elbow point.

Another advanced method is Silhouette analysis, which assesses clustering quality based on the cohesion and separation of clusters. Each data point has a silhouette score that indicates how similar it is to its cluster compared to others, ranging from -1 to 1.

Now, let’s shift gears and explore some hands-on coding to better understand K-means clustering. We will generate synthetic data representing five clusters and train a K-means model using the KMeans class from Scikit-Learn.

from sklearn.datasets import make_blobs

from sklearn.cluster import KMeans

import matplotlib.pyplot as plt

# Generate synthetic data

X, _ = make_blobs(n_samples=300, centers=5, cluster_std=0.4, random_state=42, center_box=(-4, 4))

# Apply K-means clustering

kmeans = KMeans(n_clusters=5, random_state=42)

kmeans.fit(X)

# Plot data points and cluster centroids

fig, ax = plt.subplots(figsize=(16, 8))

plt.scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap='gist_rainbow', alpha=0.7, s=180)

plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], marker='x', s=200, c='k', label='Centroids')

plt.title('K-Means Clustering')

plt.xlabel('Feature 1')

plt.ylabel('Feature 2')

ax.spines['top'].set_visible(False)

ax.spines['right'].set_visible(False)

ax.xaxis.set_ticks_position('none')

ax.yaxis.set_ticks_position('none')

The results of the model illustrate its effectiveness in capturing the five clusters and assigning centroids correctly.

Next, let’s apply the Elbow method to determine the optimal number of clusters.

This video titled "Unsupervised Machine Learning - Flat Clustering with KMeans with Scikit-learn and Python" provides an in-depth explanation of K-means clustering and its applications.

Despite its simplicity, K-means clustering does have limitations, such as its sensitivity to initial centroid placement and its assumption of spherical clusters, which can hinder performance on non-linear or irregular shapes.

Section 2.2: Exploring DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) addresses one of K-means' main limitations. Unlike K-means, which struggles with irregularly shaped clusters, DBSCAN employs a density-based approach to identify clusters of arbitrary shapes. It does not require a predefined number of clusters and is robust to noise and outliers.

DBSCAN relies on two parameters: epsilon (ε) and min_samples. Epsilon defines the maximum distance within which two points are considered neighbors, while min_samples specifies the minimum number of points required to form a dense region.

The DBSCAN process involves the following steps:

1. Initialization: Start with a random data point and determine its neighborhood (points within ε reach).
2. Core Point Identification: Identify core points with at least min_samples neighbors.
3. Cluster Expansion: Expand clusters by recursively adding reachable points.
4. Outlier Detection: Label points not included in any cluster as outliers.

Choosing appropriate values for epsilon and min_samples is critical for DBSCAN's effectiveness. Epsilon should be determined based on dataset density, and min_samples influences minimum cluster size.

Let’s see how to tune these parameters through a practical example:

from sklearn.datasets import make_moons

from sklearn.cluster import DBSCAN

import matplotlib.pyplot as plt

X, _ = make_moons(n_samples=1000, noise=0.05, random_state=42)

dbscan_1 = DBSCAN(eps=0.05, min_samples=5)

dbscan_1.fit(X)

dbscan_2 = DBSCAN(eps=0.2, min_samples=5)

dbscan_2.fit(X)

In this example, I generated synthetic data shaped like two half-circles using Scikit-Learn's make_moons function. The first instance of DBSCAN, with a smaller epsilon, detected seven clusters with numerous outliers, while increasing epsilon to 0.2 yielded a more appropriate result.

Let’s further examine DBSCAN’s performance with another synthetic dataset:

from sklearn.datasets import make_circles

from sklearn.cluster import DBSCAN

import matplotlib.pyplot as plt

X, _ = make_circles(n_samples=1000, noise=0.05, random_state=42, factor=.5)

dbscan_1 = DBSCAN(eps=0.05, min_samples=5)

dbscan_1.fit(X)

dbscan_2 = DBSCAN(eps=0.2, min_samples=5)

dbscan_2.fit(X)

As demonstrated, a smaller epsilon results in an excessive number of clusters, while a larger epsilon causes all data points to merge into one cluster. Hence, DBSCAN parameters must be carefully adjusted and combined with data visualization.

You can find the complete code for generating simulations and visualizations in my GitHub repository.

Section 2.3: Hierarchical Clustering

The last algorithm we will explore is Hierarchical Clustering, which operates by grouping data points into a hierarchy of clusters. This algorithm merges or divides clusters based on a distance metric until either a single cluster containing all data points is formed or a predefined number of clusters is reached.

There are two primary approaches to Hierarchical Clustering:

1. Agglomerative Clustering: Begins with each data point as its own cluster and iteratively merges the closest pairs.
2. Divisive Clustering: Starts with all data points in a single cluster and iteratively splits it into smaller clusters.

The steps followed by Hierarchical Clustering include:

1. Initialization: Treat each point as a cluster (agglomerative) or all points as one cluster (divisive).
2. Merge or Divide Clusters.
3. Distance Calculation.
4. Update Hierarchy.

Let’s illustrate this with a synthetic dataset generated using the make_blobs function:

from sklearn.datasets import make_blobs

from sklearn.cluster import AgglomerativeClustering

# Generate synthetic data

X, _ = make_blobs(n_samples=300, centers=5, cluster_std=0.4, random_state=42, center_box=(-4, 4))

# Apply agglomerative hierarchical clustering

agg_clustering = AgglomerativeClustering(n_clusters=5, linkage='ward')

agg_clustering.fit(X)

Upon fitting the Hierarchical Clustering model, we can visualize the resulting clusters.

We can also examine the model's dendrogram, which displays the entire hierarchy. Each leaf node represents a data point, and the height of each branch indicates the distance at which clusters are merged.

From the dendrogram, it is evident that at a distance of 5, exactly five clusters are formed, representing the optimal clustering for this dataset.