Skip to content
W3S101

Unsupervised Learning: Clustering

AI with Python - Unsupervised Learning: Clustering

Section titled “AI with Python - Unsupervised Learning: Clustering”

Unsupervised machine learning algorithms operate without explicit guidance in the form of labeled data. Instead of predicting a known outcome, they aim to discover inherent structures, patterns, or relationships within the data itself. This makes them a cornerstone of exploratory data analysis and true artificial intelligence, where systems learn from observation.

In unsupervised learning, there are no predefined ‘correct answers’ or a ‘teacher’ to guide the learning process. The algorithms must independently identify interesting patterns, groupings, or anomalies in the provided dataset.

What is Clustering?

Section titled “What is Clustering?”

Clustering is a fundamental unsupervised learning technique. It involves partitioning a set of observations (data points) into subsets, called ‘clusters,’ such that observations within the same cluster are more similar to each other (according to a chosen similarity metric) than to those in other clusters. The primary goal is to group data based on shared characteristics, revealing underlying structures.

Imagine sorting a mixed pile of fruits. Clustering would be like grouping them into apples, bananas, oranges, etc., based on their visual and textural properties, without prior knowledge of fruit types. In data, these properties are features.

Textual description of a clustering visual: Imagine a scatter plot with data points. Clustering algorithms would draw boundaries or assign colors to these points, grouping them into distinct regions. For example, one region might contain a dense collection of blue points, another red points, and a third green points, visually separated from each other.

Common Clustering Algorithms

Section titled “Common Clustering Algorithms”

Several algorithms exist for clustering data, each with its strengths and weaknesses. We’ll explore a few popular ones using Python’s scikit-learn library.

K-Means Clustering

Section titled “K-Means Clustering”

K-Means is one of the most widely used and simplest clustering algorithms. It’s a ‘flat’ or ‘partitional’ clustering method. A key assumption is that you pre-specify the number of clusters, ‘K’.

The algorithm iteratively performs the following steps:

  1. Specify K: Choose the desired number of clusters.
  2. Initialize Centroids: Randomly select K data points as initial cluster centroids (or use a smarter initialization like ‘k-means++’).
  3. Assign Points: Assign each data point to the cluster whose centroid is nearest (e.g., using Euclidean distance).
  4. Update Centroids: Recalculate the centroid of each cluster as the mean of all data points assigned to it.
  5. Repeat: Repeat steps 3 and 4 until the centroids no longer move significantly or a maximum number of iterations is reached.

Let’s implement K-Means in Python. First, install necessary libraries if you haven’t:

pip install scikit-learn matplotlib seaborn numpy

Import packages and generate sample data:

import matplotlib.pyplot as plt
import seaborn as sns
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs # Updated import


# Generate synthetic 2D data with 4 distinct clusters
X, y_true = make_blobs(n_samples=500, centers=4,
                       cluster_std=0.60, random_state=0)


# Visualize the generated data
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], s=50, cmap='viridis')
plt.title('Generated Data for Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

The plot will show four distinct groups of points in a 2D space, which our K-Means algorithm will try to identify.

Now, apply K-Means:

# Initialize KMeans with K=4 clusters
# n_init='auto' is recommended for scikit-learn versions >= 1.4 to use an intelligent default
# For older versions, n_init=10 is a common default for 'k-means++'
kmeans = KMeans(n_clusters=4, init='k-means++', n_init='auto', random_state=0)


# Fit K-Means to the data and predict cluster labels
kmeans.fit(X)
y_kmeans = kmeans.predict(X) # Or equivalently: y_kmeans = kmeans.labels_


# Get the cluster centers
centers = kmeans.cluster_centers_


# Visualize the clustering results
plt.figure(figsize=(10, 7))
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis', alpha=0.7, label='Data Points')
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, marker='X', label='Centroids')
plt.title('K-Means Clustering Results (K=4)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.show()

This visualization will show the original data points colored by their assigned cluster, with the final cluster centroids marked (e.g., with red ‘X’s). You should see that K-Means has successfully identified the four groups.

Practical Applications of K-Means: Customer segmentation, document clustering, image compression.

Mean Shift Clustering

Section titled “Mean Shift Clustering”

Mean Shift is another powerful clustering algorithm that, unlike K-Means, does not require specifying the number of clusters beforehand. It’s a density-based algorithm that aims to find ‘modes’ or peaks in the data distribution.

The basic steps are:

  1. Initialize Windows: Place a window (e.g., a circle in 2D) around each data point.
  2. Compute Mean: For each window, calculate the mean of the data points within it.
  3. Shift Window: Shift the center of the window to this calculated mean.
  4. Repeat: Repeat steps 2 and 3 until the window positions converge (no longer move significantly).
  5. Assign Clusters: Points whose windows converge to the same location (mode) are assigned to the same cluster.

Let’s implement Mean Shift:

from sklearn.cluster import MeanShift, estimate_bandwidth


# Generate different sample data for Mean Shift
centers_ms = [[1, 1], [5, 5], [3, 10]]
X_ms, _ = make_blobs(n_samples=300, centers=centers_ms, cluster_std=0.8, random_state=42)


plt.figure(figsize=(8, 6))
plt.scatter(X_ms[:, 0], X_ms[:, 1], s=50)
plt.title('Generated Data for Mean Shift')
plt.show()

The plot will show data points, potentially forming a few groups.

# Estimate bandwidth (a crucial parameter for Mean Shift)
# Bandwidth determines the size of the window.
# quantile can be adjusted, 0.2-0.3 often works well.
bandwidth = estimate_bandwidth(X_ms, quantile=0.2, n_samples=len(X_ms))


# Initialize MeanShift
# If bandwidth is not provided, it's estimated, but providing it can give more control.
mean_shift = MeanShift(bandwidth=bandwidth, bin_seeding=True) # bin_seeding can speed up


# Fit Mean Shift to the data
mean_shift.fit(X_ms)
labels_ms = mean_shift.labels_
cluster_centers_ms = mean_shift.cluster_centers_


n_clusters_estimated = len(np.unique(labels_ms))
print(f"Estimated number of clusters by Mean Shift: {n_clusters_estimated}")
print(f"Cluster centers:\n{cluster_centers_ms}")


# Visualize the Mean Shift clustering results
plt.figure(figsize=(10, 7))
colors = ['r', 'g', 'b', 'c', 'm', 'y', 'k']
for i in range(len(X_ms)):
    plt.scatter(X_ms[i, 0], X_ms[i, 1], color=colors[labels_ms[i] % len(colors)], s=50, alpha=0.7)


plt.scatter(cluster_centers_ms[:, 0], cluster_centers_ms[:, 1],
            marker='X', s=200, linewidths=3, color='black', zorder=10, label='Cluster Centers')
plt.title(f'Mean Shift Clustering Results (Estimated {n_clusters_estimated} clusters)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.show()

Expected output (textual):

Estimated number of clusters by Mean Shift: (e.g., 3)
Cluster centers:
[[x1 y1]
 [x2 y2]
 [x3 y3]]

The visualization will show data points colored by their assigned cluster, with the algorithm-identified cluster centers. The number of clusters is determined automatically by Mean Shift.

Practical Applications of Mean Shift: Image segmentation, object tracking, data point mode finding.

Measuring Clustering Performance: Silhouette Analysis

Section titled “Measuring Clustering Performance: Silhouette Analysis”

Real-world data rarely comes with pre-defined clusters, making it challenging to assess the quality of a clustering result, especially when the true number of clusters is unknown. Silhouette Analysis is a common method to evaluate clustering quality by measuring how well-separated the clusters are.

Silhouette Score

Section titled “Silhouette Score”

The silhouette score for a single data point measures how similar it is to its own cluster compared to other clusters. It ranges from -1 to +1:

  • Score near +1: The sample is far away from neighboring clusters (good clustering).
  • Score near 0: The sample is on or very close to the decision boundary between two neighboring clusters.
  • Score near -1: The sample may have been assigned to the wrong cluster (poor clustering).

The overall silhouette score for a clustering result is the average of the silhouette scores for all samples.

The formula for a single sample ‘i’ is: s(i) = (b(i) - a(i)) / max(a(i), b(i))

  • a(i): The mean intra-cluster distance (average distance from ‘i’ to all other points in its own cluster).
  • b(i): The mean nearest-cluster distance (average distance from ‘i’ to all points in the next nearest cluster).

Calculating Silhouette Score to Find Optimal K for K-Means

Section titled “Calculating Silhouette Score to Find Optimal K for K-Means”

We can use the silhouette score to help determine an optimal number of clusters (K) for algorithms like K-Means. We’ll iterate through different values of K, perform K-Means, and calculate the silhouette score for each.

from sklearn.metrics import silhouette_score


# Using the data X from the K-Means example
possible_k_values = range(2, 10) # Test K from 2 to 9
silhouette_scores = []


for k_val in possible_k_values:
    kmeans_eval = KMeans(n_clusters=k_val, init='k-means++', n_init='auto', random_state=0)
    cluster_labels_eval = kmeans_eval.fit_predict(X)


    # Calculate silhouette score
    score = silhouette_score(X, cluster_labels_eval)
    silhouette_scores.append(score)
    print(f"For K = {k_val}, Silhouette Score = {score:.4f}")


# Plot silhouette scores for different K
plt.figure(figsize=(8, 5))
plt.plot(possible_k_values, silhouette_scores, marker='o')
plt.title('Silhouette Scores for Different Values of K (K-Means)')
plt.xlabel('Number of Clusters (K)')
plt.ylabel('Silhouette Score')
plt.grid(True)
plt.show()


# Find the K with the highest silhouette score
optimal_k = possible_k_values[np.argmax(silhouette_scores)]
print(f"\nOptimal number of clusters based on Silhouette Score: {optimal_k}")

Expected output (textual):

For K = 2, Silhouette Score = 0.xxxx
For K = 3, Silhouette Score = 0.xxxx
For K = 4, Silhouette Score = 0.xxxx (likely highest for the make_blobs example with 4 centers)
...
For K = 9, Silhouette Score = 0.xxxx


Optimal number of clusters based on Silhouette Score: 4

The plot will show the silhouette score on the y-axis for different K values on the x-axis. Typically, you’d look for a peak in this plot, which suggests an optimal K. For our make_blobs data with 4 centers, K=4 should yield the highest score.

Note: The Silhouette Score is just one metric. The ‘Elbow Method’ (plotting inertia vs. K) is another common heuristic for K-Means. Domain knowledge is also crucial for choosing K.

Finding Nearest Neighbors

Section titled “Finding Nearest Neighbors”

Finding the nearest neighbors of a data point is a fundamental operation in many machine learning algorithms, particularly in instance-based learning and recommendation systems. The K-Nearest Neighbors (KNN) algorithm, in its various forms, relies on this concept.

The goal is to find the ‘K’ data points in a given dataset that are closest (according to a distance metric like Euclidean distance) to a new, unseen input point.

Let’s use sklearn.neighbors.NearestNeighbors:

from sklearn.neighbors import NearestNeighbors


# Sample dataset
A = np.array([
    [3.1, 2.3], [2.3, 4.2], [3.9, 3.5],
    [3.7, 6.4], [4.8, 1.9], [8.3, 3.1],
    [5.2, 7.5], [4.8, 4.7], [3.5, 5.1],
    [4.4, 2.9]
])


# Number of neighbors to find
k_neighbors = 3


# Test data point for which we want to find neighbors
test_point = np.array([[3.3, 2.9]]) # Must be 2D for kneighbors


# Visualize the input data and the test point
plt.figure(figsize=(8, 6))
plt.scatter(A[:, 0], A[:, 1], marker='o', s=100, color='black', label='Data Points')
plt.scatter(test_point[0, 0], test_point[0, 1], marker='x', s=150, color='red', label='Test Point')
plt.title('Input Data and Test Point')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True)
plt.show()

The plot shows our dataset and the red ‘x’ marking the test point.

# Initialize and fit the NearestNeighbors model
# algorithm='auto' will choose the most appropriate algorithm (e.g., 'ball_tree', 'kd_tree', 'brute')
nn_model = NearestNeighbors(n_neighbors=k_neighbors, algorithm='auto')
nn_model.fit(A)


# Find the K nearest neighbors for the test point
distances, indices = nn_model.kneighbors(test_point)


print(f"\n{k_neighbors} Nearest Neighbors for point {test_point[0]}:")
for i in range(k_neighbors):
    print(f"{i+1}. Point: {A[indices[0][i]]}, Distance: {distances[0][i]:.4f}")


# Visualize the nearest neighbors
plt.figure(figsize=(10, 7))
plt.scatter(A[:, 0], A[:, 1], marker='o', s=100, color='black', label='Data Points')
plt.scatter(test_point[0, 0], test_point[0, 1], marker='x', s=150, color='red', label='Test Point')
plt.scatter(A[indices[0], 0], A[indices[0], 1], marker='o', s=250,
            edgecolor='blue', facecolors='none', linewidths=2, label=f'{k_neighbors} Nearest Neighbors')
plt.title(f'{k_neighbors}-Nearest Neighbors')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True)
plt.show()

Expected output (textual):

3 Nearest Neighbors for point [3.3 2.9]:
1. Point: [3.1 2.3], Distance: 0.6325
2. Point: [4.4 2.9], Distance: 1.1000
3. Point: [3.9 3.5], Distance: 0.8485
(Note: Order might vary slightly based on tie-breaking in distances, but the points should be correct.)

The second plot will highlight the K nearest neighbors to the test point, typically by drawing circles around them or using a different color.

K-Nearest Neighbors (KNN) Classifier

Section titled “K-Nearest Neighbors (KNN) Classifier”

The K-Nearest Neighbors (KNN) classifier is a simple yet effective instance-based learning algorithm used for classification tasks. It classifies a new data point based on the majority class of its ‘K’ nearest neighbors in the training data.

Concept of KNN Classifier

Section titled “Concept of KNN Classifier”

The core idea is: “Tell me who your neighbors are, and I’ll tell you who you are.”

  1. Choose K: Select the number of nearest neighbors (K) to consider.
  2. Calculate Distances: For a new, unclassified data point, calculate its distance (e.g., Euclidean) to all points in the training dataset.
  3. Identify Neighbors: Find the K training data points that are closest to the new point.
  4. Majority Vote: Assign the class label to the new data point that is most frequent among these K neighbors. (For regression, the average of the neighbors’ values might be used).

KNN is a non-parametric, lazy learning algorithm. ‘Non-parametric’ means it doesn’t make strong assumptions about the underlying data distribution. ‘Lazy learning’ means it doesn’t build an explicit model during training; all computation is deferred until classification.

Example: KNN Classifier for Digit Recognition

Section titled “Example: KNN Classifier for Digit Recognition”

We’ll use the load_digits dataset from scikit-learn, which contains images of handwritten digits (0-9).

from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
import matplotlib.pyplot as plt
import numpy as np


# Load the digits dataset
digits = load_digits()
X_digits = digits.data  # Feature matrix (flattened 8x8 images)
y_digits = digits.target # Target labels (0-9)


print(f"Data shape: {X_digits.shape}") # (1797 samples, 64 features)
print(f"Target shape: {y_digits.shape}")


# Display a few sample digits
fig, axes = plt.subplots(2, 5, figsize=(10, 5), subplot_kw={'xticks':[], 'yticks':[]})
for i, ax in enumerate(axes.flat):
    ax.imshow(X_digits[i].reshape(8, 8), cmap='binary')
    ax.set_title(f"Label: {y_digits[i]}")
plt.suptitle('Sample Digits from the Dataset')
plt.tight_layout(rect=[0, 0, 1, 0.96])
plt.show()

This will display 10 sample digit images with their true labels.

# Split data into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X_digits, y_digits, test_size=0.3, random_state=42, stratify=y_digits)


print(f"Training samples: {X_train.shape[0]}")
print(f"Testing samples: {X_test.shape[0]}")


# Initialize KNN classifier (e.g., with K=5 neighbors)
knn_classifier = KNeighborsClassifier(n_neighbors=5)


# Train the classifier (for KNN, this mostly involves storing the training data)
knn_classifier.fit(X_train, y_train)


# Make predictions on the test set
y_pred = knn_classifier.predict(X_test)


# Evaluate the classifier
accuracy = accuracy_score(y_test, y_pred)
print(f"\nKNN Classifier Accuracy on Digits: {accuracy * 100:.2f}%")


# Let's look at a few test predictions
fig, axes = plt.subplots(3, 4, figsize=(12, 10), subplot_kw={'xticks':[], 'yticks':[]})
for i, ax in enumerate(axes.flat):
    if i < len(X_test):
        ax.imshow(X_test[i].reshape(8, 8), cmap='binary')
        true_label = y_test[i]
        pred_label = y_pred[i]
        ax.set_title(f"True: {true_label}, Pred: {pred_label}", color='green' if true_label == pred_label else 'red')
plt.suptitle('Sample Test Predictions (KNN Classifier)')
plt.tight_layout(rect=[0, 0, 1, 0.96])
plt.show()

Expected output (textual):

Data shape: (1797, 64)
Target shape: (1797,)
Training samples: 1257
Testing samples: 540


KNN Classifier Accuracy on Digits: (e.g., 98.xx % - will vary slightly but should be high)

The second plot will show some test digit images with their true labels and the KNN classifier’s predicted labels. Correct predictions will be titled in green, incorrect ones in red. You should see very high accuracy for this task with KNN.

Considerations for KNN: Choosing an appropriate K (often via cross-validation), feature scaling (important as KNN relies on distances), and its computational cost during prediction for large datasets (as it needs to compare with all training points).

Further Learning Resources: