Lecture 06: Cluster Analysis (Unsupervised Learning)

Source Material: materials/DA08 - Clustering.pdf / materials/DA08 - Clustering.md
Course: Introduction to Data Analytics (CE KMITL)
Topics: Unsupervised Clustering, Distance Metrics, K-Means Algorithm, Sum of Squared Errors (SSE), DBSCAN, Cluster Validation, Dimensionality Reduction (PCA/SVD)

1. Overview of Cluster Analysis

1.1 What is Clustering?

Cluster Analysis (Clustering) is an unsupervised learning technique that partitions an unlabelled dataset into natural subgroups (clusters). Unlike supervised learning (regression and classification), clustering algorithms do not receive target output labels ($y$). Instead, the objective is discovered purely from patterns, relationships, and geometric structures in the feature space.

• Intra-cluster similarity: Data objects assigned to the same cluster should be as close or similar to one another as possible (minimized intra-cluster distance).
• Inter-cluster dissimilarity: Data objects belonging to different clusters should be as distinct and separated as possible (maximized inter-cluster distance).

1.2 Ambiguity in Cluster Boundaries

The true number of clusters in a dataset is often inherently ambiguous. For example, depending on the scale of observation or business context:

• Viewing data globally may suggest 2 clusters.
• Viewing intermediate sub-structures may suggest 4 clusters.
• Viewing fine-grained local density peaks may suggest 6 clusters.

This ambiguity necessitates formal mathematical distance metrics and objective validation criteria.

1.3 Taxonomy of Clustering Approaches

Clusterings and clustering algorithms can be categorized across several key dimensions:

2. Distance and Proximity Metrics

Clustering algorithms rely on proximity measures to quantify similarity or dissimilarity between data points $\mathbf{x} = (x_1, x_2, \dots, x_d)$ and $\mathbf{y} = (y_1, y_2, \dots, y_d)$ in a $d$-dimensional feature space.

2.1 Euclidean Distance ($L_2$ Norm)

The standard straight-line geometric distance between two points:

$$d_{\text{Euclidean}}(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_2 = \sqrt{\sum_{i=1}^d (x_i - y_i)^2}$$

2.2 Manhattan Distance ($L_1$ Norm / City Block)

The grid-based rectilinear distance:

$$d_{\text{Manhattan}}(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_1 = \sum_{i=1}^d |x_i - y_i|$$

2.3 General Minkowski Distance ($L_p$ Norm)

A generalized metric family parameterized by $p \ge 1$:

$$d_{\text{Minkowski}}(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_p = \left( \sum_{i=1}^d |x_i - y_i|^p \right)^{1/p}$$

When $p = 1$, it becomes Manhattan distance; when $p = 2$, it becomes Euclidean distance; when $p \to \infty$, it becomes Chebyshev distance ($\max_i |x_i - y_i|$).

Pre-processing Prerequisite: Because distance formulas sum squared or absolute feature differences, variables with larger raw magnitudes dominate the distance calculations. Continuous features must be normalized (via Min-Max scaling or Z-score standardization) prior to clustering.

3. K-Means Clustering Algorithm

3.1 Algorithm Overview

K-Means (commonly implemented via Lloyd’s Algorithm) is an iterative, partitional, center-based clustering algorithm. Given an unlabelled dataset $X = \{\mathbf{x}_1, \dots, \mathbf{x}_n\}$ and a pre-specified number of clusters $K$, the algorithm partitions $X$ into $K$ disjoint clusters $\{C_1, C_2, \dots, C_K\}$.

3.2 Objective Cost Function: Sum of Squared Errors (SSE)

The mathematical objective of K-Means is to find cluster assignments and centroids that minimize the Sum of Squared Errors (SSE):

$$\text{SSE} = \sum_{i=1}^K \sum_{\mathbf{x} \in C_i} \text{dist}(\mathbf{x}, \mathbf{c}_i)^2 = \sum_{i=1}^K \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \mathbf{c}_i\|_2^2$$

where:

• $K$ is the number of clusters.
• $C_i$ is the set of data points belonging to cluster $i$.
• $\mathbf{c}_i$ is the centroid (mean vector) of cluster $C_i$:

$$\mathbf{c}_i = \frac{1}{|C_i|} \sum_{\mathbf{x} \in C_i} \mathbf{x}$$

The recomputation of $\mathbf{c}_i$ as the arithmetic mean mathematically guarantees the minimization of SSE for Euclidean distance.

3.3 Step-by-Step 1D Worked Example

Consider a 1-dimensional dataset containing 5 points:

$$D = \{0, 2, 3, 7, 9\}$$

We want to partition $D$ into $K = 2$ clusters: Cluster $A$ and Cluster $B$.

Initial Setup (Round 0)

• Random initial centroid locations: $c_A = 1.0$, $c_B = 4.0$.

Consolidated Iteration Walkthrough Table

The table below deduplicates and synthesizes the progressive iteration sequence into a single unified step-by-step record:

SSE Evaluation of the Final Clustering:

For Cluster $A$ with centroid $c_A = 1.67$:

$$\text{SSE}_A = (0 - 1.67)^2 + (2 - 1.67)^2 + (3 - 1.67)^2 = 2.7889 + 0.1089 + 1.7689 \approx 4.67$$

For Cluster $B$ with centroid $c_B = 8.0$:

$$\text{SSE}_B = (7 - 8.0)^2 + (9 - 8.0)^2 = (-1.0)^2 + (1.0)^2 = 1.0 + 1.0 = 2.0$$

Total Final SSE:

$$\text{SSE}_{\text{total}} = \text{SSE}_A + \text{SSE}_B \approx 4.67 + 2.0 = 6.67$$

3.4 Limitations of K-Means

While computationally fast ($O(n \cdot K \cdot I \cdot d)$ where $I$ is iterations), K-Means has several well-documented drawbacks:

1. Vulnerability to Initial Seeds: Bad initial centroids can trap the algorithm in poor local minima or create empty clusters. (Remedy: K-Means++ initialization).
2. Differing Cluster Sizes & Densities: K-Means assumes clusters have roughly equal variance and density. When a dense cluster sits next to a sparse cluster, K-Means splits the sparse cluster or merges parts of both.
3. Non-Globular (Non-Convex) Shapes: K-Means uses Euclidean distance, which inherently forms convex Voronoi cells. It fails on concentric circles, interlocking spirals, or crescent shapes.
4. Sensitivity to Outliers: Extreme points dramatically distort the arithmetic mean calculation of centroids.

3.5 Selecting the Optimal Number of Clusters ($K$)

1. The Elbow Method

Plot the objective cost ($\text{SSE}$) as a function of $K$:

• As $K$ increases from $1$ to $n$, SSE monotonically decreases (reaching $0$ when $K = n$).
• We look for an elbow point: the value of $K$ where the rate of decrease drops sharply, indicating diminishing returns for adding further clusters.

2. The Silhouette Coefficient

The Silhouette Coefficient measures how well each point is matched to its own cluster compared to neighboring clusters without requiring ground truth labels.

For each data point $i$:

1. $a(i)$: The average distance from point $i$ to all other points in the same cluster (intra-cluster distance).
2. $b(i)$: The minimum average distance from point $i$ to all points in any other single cluster (nearest-cluster distance).

The silhouette score $s(i)$ for point $i$ is:

$$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$$

Interpretation of $s(i)$:

• $s(i) \approx +1$: The point is well inside its own cluster and far from neighbors ($b(i) \gg a(i)$).
• $s(i) \approx 0$: The point lies on or very near the decision boundary between two clusters ($b(i) \approx a(i)$).
• $s(i) \approx -1$: The point has likely been assigned to the wrong cluster ($a(i) \gg b(i)$).

The global Mean Silhouette Score across all points provides an effective metric to select the optimal $K$.

4. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

4.1 Foundational Concept

DBSCAN identifies clusters as contiguous regions of high point density separated by regions of low density. Unlike K-Means, DBSCAN:

• Does not require specifying the number of clusters $K$ in advance.
• Can discover clusters of arbitrary, non-globular shapes.
• Explicitly detects and isolates noise points and outliers.

4.2 Key Hyperparameters

DBSCAN requires two essential parameters:

1. $\varepsilon$ (Eps / Radius): The maximum neighborhood distance to scan around any given point.
2. $\text{MinPts}$ (Minimum Points): The minimum number of points required within the $\varepsilon$-neighborhood of a point (including the point itself) to form a dense region.

The $\varepsilon$-neighborhood of point $p$ is defined as:

$$N_\varepsilon(p) = \{q \in D \mid \text{dist}(p, q) \le \varepsilon\}$$

4.3 Point Classifications

DBSCAN categorizes every data point into one of three distinct types:

1. Core Point: A point $p$ is a Core Point if its $\varepsilon$-neighborhood contains at least $\text{MinPts}$ points:

   $$|N_\varepsilon(p)| \ge \text{MinPts}$$

   Core points reside in the interior of a cluster.

2. Border Point: A point $p$ is a Border Point if it has fewer than $\text{MinPts}$ neighbors ($|N_\varepsilon(p)| < \text{MinPts}$), but falls within the $\varepsilon$-neighborhood of at least one Core Point $q \in N_\varepsilon(p)$. Border points form the outer boundaries of clusters.

3. Noise Point (Outlier): A point that is neither a Core Point nor a Border Point. It belongs to no cluster.

4.4 Density Reachability and Connectivity

To formally group points into clusters, DBSCAN establishes connectivity relations:

1. Directly Density-Reachable: Point $p$ is directly density-reachable from point $q$ with respect to $\varepsilon$ and $\text{MinPts}$ if:

   • $q$ is a Core Point.
   • $p \in N_\varepsilon(q)$ (i.e., $\text{dist}(p, q) \le \varepsilon$).

2. Density-Reachable: Point $p$ is density-reachable from point $q$ if there exists an ordered chain of points $p_1, p_2, \dots, p_m$ where $p_1 = q$ and $p_m = p$ such that each $p_{i+1}$ is directly density-reachable from $p_i$. (This relation is asymmetric when ending on a border point).

3. Density-Connected: Point $p$ is density-connected to point $q$ if there exists a common core point $o$ such that both $p$ and $q$ are density-reachable from $o$. (This relation is symmetric).

A DBSCAN Cluster is defined as a maximal set of density-connected points.

4.5 Algorithmic Steps of DBSCAN

1. Label all points as Core, Border, or Noise based on their $\varepsilon$-neighborhood point count.
2. Eliminate all Noise points from initial cluster consideration.
3. For each unvisited Core point $p$:
   • Spawn a new cluster $C$.
   • Find all points that are density-connected to $p$ (using Breadth-First or Depth-First neighborhood expansion) and add them to $C$.
4. Assign each Border point to the cluster of its closest Core point.
5. Remaining unassigned points are designated as Noise.

4.6 Comparative Summary: K-Means vs. DBSCAN

5. Cluster Validation Concepts

Cluster validation evaluates the objective quality, validity, and statistical reliability of clustering results.

5.1 The Three Validation Indices

1. External Index: Measures the agreement between the discovered cluster labels and an externally provided set of true class labels (ground truth).

   • Examples: Entropy, Purity, Rand Index, Adjusted Mutual Information (AMI).
   • Useful when evaluating clustering algorithms on labeled benchmark datasets.

2. Internal Index: Evaluates the goodness of a clustering structure using only the data itself, without reference to any external labels.

   • Examples: Sum of Squared Errors (SSE), Silhouette Coefficient, Davies-Bouldin Index, Calinski-Harabasz Index.

3. Relative Index: Used to compare two different clusterings generated by varying parameter values (e.g., comparing $K=2$ vs $K=3$, or comparing K-Means vs DBSCAN). Often implemented using an internal or external index as the criterion.

5.2 Measuring Cluster Validity via Matrix Correlation

A classic internal validation approach correlates the Proximity Matrix with an Ideal Similarity Matrix:

1. Proximity Matrix ($P$): An $n \times n$ matrix where entry $P_{ij} = \text{dist}(\mathbf{x}_i, \mathbf{x}_j)$ records the pairwise distance between points.
2. Ideal Similarity Matrix ($Y$): An $n \times n$ matrix defined by cluster assignments:

$$Y_{ij} = \begin{cases} 1 & \text{if } \mathbf{x}_i \text{ and } \mathbf{x}_j \text{ belong to the same cluster} \\ 0 & \text{if } \mathbf{x}_i \text{ and } \mathbf{x}_j \text{ belong to different clusters} \end{cases}$$

3. Correlation Calculation: Compute Pearson’s correlation coefficient between the upper triangular entries ($n(n-1)/2$ pairs) of $P$ and $Y$:
   • A strong correlation indicates that points belonging to the same cluster are geometrically close, while points in different clusters are distant.
   • Ordering the similarity matrix rows and columns according to cluster labels produces a clear block-diagonal pattern for well-separated clusters.

6. Dimensionality Reduction: PCA and SVD

6.1 The Curse of Dimensionality

Real-world datasets often possess hundreds or thousands of features (e.g., text document term vectors, genetic markers, image pixel matrices). High dimensionality causes severe problems:

• Data Sparsity: The volume of the feature space grows exponentially, causing all points to become equidistant from each other (rendering distance-based metrics meaningless).
• Computational Bottlenecks: Time complexity scales with feature count $d$.
• Redundancy and Noise: Many features are correlated or irrelevant, obscuring genuine cluster boundaries.

6.2 Latent Factor Models and SVD

Dimensionality reduction assumes that the observed high-dimensional data actually resides near a lower-dimensional latent subspace.

Singular Value Decomposition (SVD) factorizes an $n \times d$ centered data matrix $X$ into three matrices:

$$X = U \Sigma V^T$$

where:

• $U$ is an $n \times n$ orthogonal matrix (left singular vectors representing data points in latent space).
• $\Sigma$ is an $n \times d$ diagonal matrix containing singular values (measuring the variance explained by each factor).
• $V^T$ is a $d \times d$ orthogonal matrix (right singular vectors representing feature loadings).

6.3 Principal Component Analysis (PCA)

Principal Component Analysis (PCA) is an unsupervised linear technique that projects data onto orthogonal axes (Principal Components) that successively maximize the variance of the data:

1. The 1st Principal Component ($PC_1$) aligns with the direction of maximal variance.
2. The 2nd Principal Component ($PC_2$) is orthogonal to $PC_1$ and maximizes remaining variance.

# Practical Dimensionality Reduction Pipeline with Scikit-Learn
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

# 1. Standardize features (essential prior to PCA)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 2. Reduce dimensionality to 2 Principal Components for 2D visualization
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_scaled)

# 3. Cluster in the reduced latent space
kmeans = KMeans(n_clusters=3, random_state=42)
labels = kmeans.fit_predict(X_pca)

By reducing high-dimensional data (such as the 4D Iris dataset or 1000D customer embeddings) to 2D or 3D, PCA enables direct human visualization of discovered clusters while eliminating noise.

7. Review and Key Takeaways

1. Clustering groups unlabelled data such that intra-cluster similarity is maximized and inter-cluster similarity is minimized.
2. K-Means iteratively assigns points to the nearest centroid and recomputes centroids as the mean of assigned points, minimizing the Sum of Squared Errors (SSE).
3. The Elbow Method and Silhouette Coefficient provide objective criteria to determine the optimal cluster count $K$.
4. DBSCAN discovers clusters of arbitrary shapes and isolates outliers based on density parameters ($\varepsilon$ and $\text{MinPts}$), categorizing points as Core, Border, or Noise.
5. Cluster validity is measured via External Indices (against true labels), Internal Indices (SSE, Silhouette, Proximity-Similarity Correlation), and Relative Indices.
6. PCA mitigates the curse of dimensionality by projecting data onto orthogonal directions of maximum variance prior to clustering and visualization.