Unsupervised Learning - Clustering (K-Means)

1. Welcome and Icebreaker:

Welcome to Day 16! We’re shifting gears today and diving into the fascinating world of Unsupervised Learning, starting with one of its most popular techniques: Clustering, and specifically the K-Means algorithm.

To get us started, here’s a little thought experiment: Imagine you have a huge box of mixed Lego bricks of all different shapes, sizes, and colors, and you’re asked to organize them. How would you go about it without any specific instructions on how to categorize them? Share your initial thoughts or strategies!

This Lego analogy is quite close to what clustering aims to do – find inherent groupings in data without predefined labels. Perhaps some of you have encountered situations where you had a lot of data and wanted to find natural segments or groups within it. Feel free to share any such experiences or initial curiosities about how machines can learn to group things on their own.

2. Outline the Session:

Today, our main goal is to understand the concept of clustering and get a solid grasp of the K-Means algorithm.

Our Agenda:

1. Introduction to Unsupervised Learning:
   • What it is and how it differs from Supervised Learning.
   • Why it’s important.
2. Concept of Clustering:
   • Definition and goals of clustering.
   • Types of clustering (brief overview, focusing on partitional).
   • Applications of clustering.
3. K-Means Algorithm Deep Dive:
   • Intuition: How it works conceptually.
   • The Algorithm Steps: Initialization, Assignment, Update.
   • Choosing the value of K (the number of clusters).
   • Strengths and Weaknesses of K-Means.
4. Distance Metrics for K-Means.

Learning Outcomes: By the end of this session, you should be able to:

• Define unsupervised learning and explain its purpose.
• Describe what clustering is and identify its common use cases.
• Explain the K-Means algorithm step-by-step.
• Discuss methods for choosing an appropriate value for K.
• List the advantages and limitations of K-Means.
• Understand the importance of distance metrics in K-Means.

Structure of the Session: We’ll begin by contrasting unsupervised learning with what we’ve learned so far. Then, we’ll focus on clustering as a key unsupervised task. A significant portion of our time will be dedicated to understanding the mechanics of K-Means, including a conceptual walkthrough. We will also discuss practical considerations like selecting K and the algorithm’s pros and cons. We will refer to resources like Andrew Ng’s ML course and StatQuest for further exploration.

Interactivity: As always, your active participation is encouraged. Please ask questions, share your insights, and engage with the material. The practice task from lesson.md for today is to “Manually trace a few steps of K-Means on a small 2D dataset.” While we might not do a full manual trace for everyone in session, I want you to keep this in mind as we go through the steps, as it’s an excellent way to solidify understanding.

3. Concept Explanation:

So far in our journey, we’ve primarily focused on Supervised Learning. In supervised learning, our algorithms learn from data that is labeled. For example, in image classification, each image is tagged with what it represents (e.g., “cat,” “dog”), or in house price prediction, each house has a known sale price. The algorithm learns a mapping from input features to these known output labels.

Introduction to Unsupervised Learning:

Unsupervised Learning is a different paradigm. Here, the algorithm is given data that does not have any explicit labels or predefined outputs. The goal is to explore the data and find some inherent structure, patterns, or relationships within it. Instead of predicting a known target, unsupervised learning algorithms try to make sense of the data itself.

Think back to the Lego analogy: you weren’t told “these are the 2x2 red bricks,” “these are the long blue bricks.” You had to figure out meaningful ways to group them based on their characteristics (size, shape, color).

Why is Unsupervised Learning Important?

1. Discovering Hidden Patterns: It can reveal underlying structures in data that are not immediately obvious. This can lead to new insights and understanding.
2. Data Exploration: It’s often a first step in understanding a new dataset before applying supervised methods.
3. No Need for Labeled Data: Labeling data can be expensive, time-consuming, and sometimes requires domain expertise. Unsupervised methods can work with readily available unlabeled data.
4. Dimensionality Reduction: Some unsupervised techniques can reduce the number of features while preserving important information, which can be useful for visualization or as a preprocessing step for supervised learning.

Common unsupervised learning tasks include clustering, dimensionality reduction (like PCA, which we’ll cover next), and association rule mining.

Concept of Clustering:

Clustering is the task of grouping a set of objects (data points) in such a way that objects in the same group (called a cluster) are more similar to each other than to those in other groups (clusters). The primary goal is to partition the data into distinct groups based on similarity.

Key Goals of Clustering:

• Intra-cluster similarity: Data points within the same cluster should be as similar as possible.
• Inter-cluster dissimilarity: Data points in different clusters should be as dissimilar as possible.

Brief Overview of Clustering Types: While K-Means is our focus, it’s good to know that clustering isn’t a one-size-fits-all technique. There are various types:

• Partitional Clustering (e.g., K-Means, K-Medoids): Divides data objects into non-overlapping clusters. Each data object belongs to exactly one cluster. K-Means is a prime example.
• Hierarchical Clustering (e.g., Agglomerative, Divisive): Creates a tree of clusters (a dendrogram). Agglomerative starts with individual points as clusters and merges them, while divisive starts with one cluster and splits it.
• Density-Based Clustering (e.g., DBSCAN, OPTICS): Defines clusters as dense regions of data points separated by sparser regions.
• Grid-Based Clustering: Quantizes the object space into a finite number of cells that form a grid structure.
• Model-Based Clustering: Assumes that the data is a mixture of distributions (e.g., Gaussian Mixture Models).

Applications of Clustering: Clustering has a wide range of applications across various domains:

• Customer Segmentation: Grouping customers based on purchasing behavior, demographics, or website activity for targeted marketing.
• Document Analysis: Grouping similar documents together for topic modeling or information retrieval.
• Image Segmentation: Partitioning an image into multiple segments (clusters of pixels) to simplify its representation or identify objects.
• Anomaly Detection: Identifying outliers that don’t belong to any cluster or form very small clusters.
• Biology: Grouping genes with similar expression patterns, or classifying species.
• Social Network Analysis: Identifying communities within social networks.

K-Means Algorithm Deep Dive:

K-Means is one of the oldest, simplest, and most widely used partitional clustering algorithms. It aims to partition n observations into K clusters in which each observation belongs to the cluster with the nearest mean (cluster centroid or cluster center).

Intuition: Imagine you have a scatter plot of data points. K-Means tries to find K central points (centroids) and assigns each data point to the closest centroid. The centroids are then updated to be the actual mean of the points assigned to them. This process repeats until the centroids no longer move significantly, or the assignments don’t change.

The Algorithm Steps: K-Means is an iterative algorithm that proceeds as follows:

1. Step 1: Initialization - Choose the number of clusters, K, and initialize K centroids.

   • Choose K: This is a critical parameter. We’ll discuss how to choose K later. For now, assume K is given.
   • Initialize Centroids: There are several ways to initialize the K centroids:
     • Randomly select K data points from the dataset to be the initial centroids.
     • Randomly generate K points within the data range (not necessarily existing data points).
     • K-Means++ (More sophisticated): This is a common and often better approach. It tries to select initial centroids that are far apart from each other. The first centroid is chosen randomly from the data points. Subsequent centroids are chosen from the remaining data points with a probability proportional to the squared distance from the point’s closest existing centroid. This helps in faster convergence and often leads to better final clusters.

2. Step 2: Assignment Step - Assign each data point to the closest centroid.

   • For each data point in the dataset, calculate its distance to all K centroids.
   • Assign the data point to the cluster whose centroid is nearest (i.e., has the minimum distance).
   • The standard K-Means assignment step uses Euclidean distance, and its mean-centroid update minimizes squared Euclidean distance. A different metric cannot simply be substituted while keeping the same update rule.

3. Step 3: Update Step - Recalculate the centroids of the newly formed clusters.

   • For each cluster, update its centroid to be the mean of all data points assigned to that cluster in the previous step.
   • The new centroid is the component-wise mean of the points in the cluster.

4. Step 4: Repeat - Repeat Steps 2 (Assignment) and 3 (Update) until convergence.

   • Convergence is typically reached when:
     • The centroids no longer change their positions significantly between iterations.
     • The cluster assignments of the data points no longer change.
     • A maximum number of iterations is reached.

Objective Function (What K-Means Tries to Minimize): K-Means implicitly tries to minimize the Within-Cluster Sum of Squares (WCSS), also known as inertia. WCSS is the sum of squared distances between each data point and its assigned centroid: WCSS = Σ (for i=1 to K) Σ (for each point x in cluster i) ||x - centroid_i||^2 Each assignment and mean-update step attempts to reduce this squared-Euclidean WCSS objective. Manhattan distance requires a median-based update (often called K-medians); cosine-based clustering uses a different procedure, such as spherical K-Means. These are related methods, not drop-in metric changes.

Choosing the Value of K: Selecting the optimal number of clusters (K) is often the most challenging part of using K-Means, as it’s usually not known beforehand. There’s no single perfect method, but several techniques can help:

1. Elbow Method:

   • Calculate K-Means for a range of K values (e.g., K from 1 to 10 or more).
   • For each K, compute the WCSS (Within-Cluster Sum of Squares) or inertia.
   • Plot K against WCSS.
   • The plot typically shows WCSS decreasing as K increases. The idea is to find the “elbow point” on the curve – the point where adding another cluster doesn’t significantly reduce WCSS. This point is considered a good estimate for K.
   • Limitation: The elbow can sometimes be ambiguous and hard to identify clearly.

2. Silhouette Score (Silhouette Analysis):

   • The silhouette score measures how similar a data point is to its own cluster compared to other clusters. It provides a measure of how well-separated the clusters are.
   • The silhouette score for a single data point i is calculated as: s(i) = (b(i) - a(i)) / max(a(i), b(i))
     • a(i): The average distance from point i to all other points in the same cluster.
     • b(i): The average distance from point i to all points in the nearest neighboring cluster (the cluster i is not a part of, which has the smallest mean distance to i).
   • The silhouette score ranges from -1 to +1:
     • +1: The point is far away from neighboring clusters (well-clustered).
     • 0: The point is close to the decision boundary between two neighboring clusters.
     • -1: The point is probably assigned to the wrong cluster.
   • To choose K, you can calculate the average silhouette score for different values of K and choose the K that maximizes the average silhouette score.
   • This method is generally more robust than the elbow method but computationally more expensive.

3. Gap Statistic:

   • Compares the WCSS of your clustering to the WCSS of random data (null reference distribution).
   • It looks for the K value where the gap between the log(WCSS) of the observed data and the expected log(WCSS) under the null distribution is largest.
   • More computationally intensive but can be more effective than the elbow method.

4. Domain Knowledge / Business Requirements:

   • Sometimes, the number of clusters is dictated by the problem context or business needs. For example, a company might want to segment customers into 3 specific groups (e.g., low, medium, high value).

Strengths of K-Means:

• Simplicity and Ease of Implementation: It’s relatively straightforward to understand and implement.
• Efficiency: Computationally faster than many other clustering algorithms, especially for large datasets (complexity is O(nKi*d), where n=samples, K=clusters, i=iterations, d=dimensions). Scikit-learn’s implementation has further optimizations.
• Scalability: Scales well to large datasets.
• Good for Globular Clusters: Works well when clusters are roughly spherical, well-separated, and of similar sizes.
• Convergence: Guaranteed to converge (though not necessarily to the global optimum).

Weaknesses of K-Means:

• Need to Specify K: The number of clusters, K, must be predetermined, which can be a challenge.
• Sensitivity to Initialization: The initial placement of centroids can affect the final clustering results. Running K-Means multiple times with different random initializations (e.g., using n_init parameter in scikit-learn) and choosing the best result (lowest WCSS) is a common practice. K-Means++ initialization helps mitigate this but doesn’t eliminate it entirely.
• Assumes Spherical Clusters: K-Means struggles with clusters that are non-spherical (e.g., elongated, irregular shapes) or have varying densities because it uses the mean as the cluster center and Euclidean distance.
• Sensitivity to Outliers: Outliers can significantly pull centroids, distorting the clusters.
• Difficulty with Clusters of Different Sizes and Densities: Tends to produce clusters of roughly equal size and density.
• Curse of Dimensionality: Performance can degrade in high-dimensional spaces as Euclidean distance becomes less meaningful.
• Local Optima: K-Means can converge to a local optimum of WCSS, not necessarily the global optimum.

Distance Metrics for K-Means: Standard K-Means is defined with squared Euclidean distance, which pairs with updating each cluster center to its mean. Other similarity measures may be useful, but they require an algorithm with an update rule that matches the objective.

• Manhattan distance: A median-based update is used by K-medians.
• Cosine similarity: Spherical K-Means adapts the algorithm for direction-based similarity, often after normalizing vectors.
• Hamming distance: Useful for categorical or binary representations, but ordinary K-Means is not the matching algorithm because it relies on numerical means.

Important Note on Feature Scaling: Like KNN and SVMs, K-Means is sensitive to feature scaling. If features are on vastly different scales, features with larger values and variances will dominate the distance calculations. Therefore, it’s generally recommended to standardize or normalize your data before applying K-Means.

Summary of K-Means: K-Means is a foundational clustering algorithm that provides a good starting point for many unsupervised learning tasks. Its simplicity and efficiency make it attractive, but it’s important to be aware of its assumptions and limitations. Understanding how to choose K, the impact of initialization, and the nature of your data will help you use K-Means effectively.

4. Live Coding Demonstration:

Let’s illustrate K-Means using Python and scikit-learn. We’ll generate some synthetic data that has clear clusters and see how K-Means performs.

import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_blobs # For generating synthetic clustered data
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

# --- 1. Generate Synthetic Data ---
# We'll create data with a known number of clusters to see if K-Means can find them.
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.70, random_state=42)
# X: feature matrix, y_true: true cluster labels (we won't use y_true for K-Means training)

plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], s=50, c=y_true, cmap='viridis')
plt.title("Original Synthetic Data (True Clusters)")
# plt.show() # Uncomment to display if running locally

# --- 2. Preprocessing: Feature Scaling (Important!) ---
# Although make_blobs often generates fairly scaled data, it's good practice.
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- 3. Applying K-Means ---
# Let's assume we know K=4 for now.
K = 4
kmeans = KMeans(n_clusters=K, init='k-means++', n_init=10, random_state=42)
# n_clusters: The number of clusters to form as well as the number of centroids to generate.
# init='k-means++': Selects initial cluster centers in a smart way to speed up convergence.
# n_init=10: Number of times the k-means algorithm will be run with different centroid seeds. 
#            The final results will be the best output of n_init consecutive runs in terms of inertia.
# random_state: For reproducibility.

# Fit K-Means to the scaled data
kmeans.fit(X_scaled)

# Get cluster assignments and centroids
y_kmeans = kmeans.predict(X_scaled) # or kmeans.labels_
centroids = kmeans.cluster_centers_

# --- 4. Visualizing K-Means Results ---
plt.figure(figsize=(8, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], s=50, c=y_kmeans, cmap='viridis', alpha=0.7)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='X', s=200, c='red', edgecolor='black')
plt.title(f"K-Means Clustering (K={K})")
# plt.show() # Uncomment to display if running locally

print(f"K-Means (K={K}) Inertia (WCSS): {kmeans.inertia_:.2f}")

# --- 5. Choosing K: Elbow Method ---
print("\n--- Elbow Method for Choosing K ---")
inertia_values = []
possible_K_values = range(1, 11)

for k_val in possible_K_values:
    kmeans_temp = KMeans(n_clusters=k_val, init='k-means++', n_init=10, random_state=42)
    kmeans_temp.fit(X_scaled)
    inertia_values.append(kmeans_temp.inertia_)

plt.figure(figsize=(8, 6))
plt.plot(possible_K_values, inertia_values, marker='o')
plt.title('Elbow Method for Optimal K')
plt.xlabel('Number of Clusters (K)')
plt.ylabel('Inertia (WCSS)')
# plt.show() # Uncomment to display if running locally
# We expect to see an "elbow" around K=4 for this data.

# --- 6. Choosing K: Silhouette Score ---
print("\n--- Silhouette Score for Choosing K ---")
silhouette_scores = []
# Silhouette score is not well-defined for K=1, so start from K=2
possible_K_values_silhouette = range(2, 11)

for k_val in possible_K_values_silhouette:
    kmeans_temp = KMeans(n_clusters=k_val, init='k-means++', n_init=10, random_state=42)
    kmeans_temp.fit(X_scaled)
    score = silhouette_score(X_scaled, kmeans_temp.labels_)
    silhouette_scores.append(score)
    print(f"Silhouette Score for K={k_val}: {score:.4f}")

plt.figure(figsize=(8, 6))
plt.plot(possible_K_values_silhouette, silhouette_scores, marker='o')
plt.title('Silhouette Scores for Optimal K')
plt.xlabel('Number of Clusters (K)')
plt.ylabel('Average Silhouette Score')
# plt.show() # Uncomment to display if running locally
# We expect K=4 to have the highest silhouette score for this data.

# --- Example: K-Means with a "wrong" K ---
print("\n--- K-Means with a 'wrong' K (e.g., K=2) ---")
K_wrong = 2
kmeans_wrong_k = KMeans(n_clusters=K_wrong, init='k-means++', n_init=10, random_state=42)
kmeans_wrong_k.fit(X_scaled)
y_kmeans_wrong_k = kmeans_wrong_k.predict(X_scaled)
centroids_wrong_k = kmeans_wrong_k.cluster_centers_

plt.figure(figsize=(8, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], s=50, c=y_kmeans_wrong_k, cmap='viridis', alpha=0.7)
plt.scatter(centroids_wrong_k[:, 0], centroids_wrong_k[:, 1], marker='X', s=200, c='red', edgecolor='black')
plt.title(f"K-Means Clustering (K={K_wrong})")
# plt.show() # Uncomment to display if running locally
print(f"K-Means (K={K_wrong}) Inertia (WCSS): {kmeans_wrong_k.inertia_:.2f}")
print(f"K-Means (K={K_wrong}) Silhouette Score: {silhouette_score(X_scaled, y_kmeans_wrong_k):.4f}")

Explanation of Code:

1. Generate Data: We use make_blobs from sklearn.datasets to create synthetic 2D data with 4 distinct clusters. We also get y_true, the true labels, which we use only for plotting the original data, not for training K-Means.
2. Feature Scaling: We apply StandardScaler to the features X. This is crucial for K-Means as it relies on Euclidean distances.
3. Applying K-Means:
   • We initialize KMeans with n_clusters=4 (assuming we know the correct K for this first run).
   • init='k-means++' uses a smarter initialization technique.
   • n_init=10 runs the algorithm 10 times with different initial centroids and picks the best one (lowest inertia).
   • random_state ensures our results are reproducible.
   • We fit the model to our scaled data.
   • kmeans.labels_ (or kmeans.predict(X_scaled)) gives the cluster assignment for each data point.
   • kmeans.cluster_centers_ gives the coordinates of the final centroids.
   • kmeans.inertia_ gives the WCSS for the converged clustering.
4. Visualizing Results: We plot the data points, colored by their assigned K-Means cluster, and mark the final centroids.
5. Elbow Method:
   • We loop through a range of possible K values (1 to 10).
   • For each K, we run K-Means and store its inertia (WCSS).
   • We then plot K vs. Inertia. We look for an “elbow” in this plot, which suggests an optimal K. For our synthetic data, this should be around K=4.
6. Silhouette Score:
   • We loop through K values (starting from 2, as silhouette score is not defined for K=1).
   • For each K, we run K-Means and calculate the average silhouette_score for all samples.
   • We plot K vs. Silhouette Score. The K that maximizes the silhouette score is often a good choice. Again, for our data, K=4 should yield a high score.
7. Example with Wrong K: We demonstrate what happens if we choose a suboptimal K (e.g., K=2). The visualization will show how the data is forced into fewer clusters, and the inertia and silhouette score will likely be worse than for K=4.

This demonstration shows the basic workflow of applying K-Means, including important considerations like feature scaling and methods for choosing K.

5. Tasks:

Short Exercise: Manual K-Means Trace

Consider the following small 2D dataset (you can just imagine these points on a graph):

• P1: (1, 1)
• P2: (1, 2)
• P3: (2, 1)
• P4: (5, 4)
• P5: (5, 5)
• P6: (6, 5)

Let’s say we want to cluster these into K=2 clusters.

Instructions:

1. Initialization: Choose initial centroids. For simplicity, let’s pick P1 and P4 as the initial centroids:
   • Centroid C1 = (1, 1)
   • Centroid C2 = (5, 4)
2. First Assignment Step: For each data point (P1 to P6), calculate its Euclidean distance to C1 and C2. Assign each point to the cluster of the closest centroid.
   • Euclidean Distance Formula: sqrt((x2-x1)^2 + (y2-y1)^2)
3. First Update Step: Recalculate the new centroids for each of the two clusters based on the mean of the points assigned to them in Step 2.
4. Second Assignment Step: Using the new centroids from Step 3, re-assign all data points (P1 to P6) to their closest new centroid.
5. Second Update Step: Recalculate the centroids again based on the assignments from Step 4.

Jot down the cluster assignments and new centroid locations after each update. Do the centroids seem to be stabilizing? This manual trace will give you a very concrete understanding of how K-Means iteratively refines its clusters.

(You don’t need to run it until full convergence, just 1-2 full iterations of Assignment and Update will be very insightful.)

This concludes our introduction to K-Means clustering. It’s a powerful yet intuitive algorithm for finding groups in unlabeled data. Next, we’ll explore another key unsupervised learning technique: Principal Component Analysis (PCA) for dimensionality reduction.