Unsupervised Learning - Clustering & Dimensionality

In supervised learning, algorithms learn under the direct guidance of ground-truth target annotations. However, the vast majority of digital, scientific, and enterprise data generated globally lacks human labels. Annotating millions of high-dimensional observations with gold-standard labels is labor-intensive, economically prohibitive, and frequently infeasible.

Unsupervised learning operates without external target feedback. Its mathematical objective is to discover intrinsic geometric manifolds, latent density distributions, and structural groupings directly from unannotated feature vectors X ⊆ ℝ^d. This guide delivers a comprehensive, university-grade examination of the two foundational pillars of unsupervised learning: clustering (partitioning observations into coherent taxonomic subsets) and dimensionality reduction (compressing high-dimensional spaces into lower-dimensional representations while preserving geometric and topological invariants).

Foundations of Unsupervised Learning & The Geometry of Data#

Let the input dataset S = {x^(1), x^(2), ..., x^(m)} consist of m observations sampled from an unknown data-generating distribution P(X) in ℝ^d without corresponding target labels y. Unsupervised learning addresses four primary canonical tasks:

1. Clustering: Discovering a discrete partitioning of the m instances into K disjoint subsets {C_1, C_2, ..., C_K} such that instances within the same cluster exhibit high mutual similarity while instances in disparate clusters exhibit high dissimilarity.
2. Dimensionality Reduction: Finding an embedding mapping function f: ℝ^d → ℝ^k (where k ≪ d) that projects data into a lower-dimensional space while preserving variance, pairwise geodesic distances, or neighborhood topology.
3. Density Estimation: Learning the continuous probability density function p(x) that generated the data (e.g., Gaussian Mixture Models, Kernel Density Estimation).
4. Anomaly & Outlier Detection: Identifying instances whose local density or distance to neighboring data manifolds is statistically anomalous under P(X).

+---------------------------------------------------------------------------------------+
|                               Unsupervised Learning Taxonomy                          |
+---------------------------------------------------------------------------------------+
|                                                                                       |
|   Unlabeled Dataset X in ℝ^d                                                          |
|         |                                                                             |
|         +-----------------------+-----------------------+                             |
|         |                       |                       |                             |
|         v                       v                       v                             |
|   [ Clustering ]          [ Dimensionality ]      [ Density Estimation ]              |
|   - Partition: K-Means    - Linear: PCA, SVD      - Gaussian Mixture Models (GMM)     |
|   - Density: DBSCAN       - Non-Linear Manifolds: - Kernel Density Estimation (KDE)   |
|   - Hierarchical: Ward      t-SNE, UMAP                                               |
|                                                                                       |
+---------------------------------------------------------------------------------------+

Partition-Based Clustering: K-Means & K-Means++#

K-Means is the most widely deployed clustering algorithm in computational science. It formalizes clustering as an optimization problem: finding K cluster centroid vectors {μ_1, μ_2, ..., μ_K} in ℝ^d that minimize the total Within-Cluster Sum of Squares (WCSS), also termed Inertia:

J(C, μ) = ∑ [k = 1 to K] ∑ [x^(i) ∈ C_k] ||x^(i) - μ_k||^2

where C_k denotes the set of instances assigned to cluster k, and ||x^(i) - μ_k||^2 is the squared Euclidean distance.

Lloyd's Algorithm (Alternating Minimization)#

Direct combinatorial minimization of J(C, μ) is an NP-hard problem. Lloyd's algorithm provides an efficient iterative heuristic that alternates between two steps until convergence:

1. Expectation Step (Assignment Step):

Holding the centroids {μ_k} fixed, assign each observation x^(i) to its nearest centroid, partitioning the feature space into Voronoi cells:

```

c^(i) = argmin [k ∈ {1, ..., K}] ||x^(i) - μ_k||^2

```

1. Maximization Step (Update Step):

Holding the cluster assignments {c^(i)} fixed, recalculate each centroid μ_k as the component-wise arithmetic mean (center of mass) of all instances assigned to cluster C_k:

```

μ_k = (1 / |C_k|) · ∑ [x^(i) ∈ C_k] x^(i)

```

Because both steps strictly decrease (or leave unchanged) the objective function J(C, μ) and the number of distinct cluster assignments is finite (K^m), Lloyd's algorithm is mathematically guaranteed to converge in a finite number of iterations. However, it converges to a local minimum rather than the global optimum; the quality of the final clustering depends heavily on the initial centroid positions.

K-Means++ Initialization#

Standard random initialization frequently places initial centroids close together, yielding poor local minima. Arthur and Vassilvitskii (2007) introduced K-Means++, which spreads out initial centroids probabilistically:

1. Select the first centroid μ_1 uniformly at random from the training instances S.
2. For each instance x^(i), compute D(x^(i)), the shortest Euclidean distance from x^(i) to the closest centroid already chosen.
3. Select the next centroid μ_k from S with probability proportional to the squared distance:

```

P(x^(i)) = D(x^(i))^2 / [ ∑ [j = 1 to m] D(x^(j))^2 ]

```

1. Repeat steps 2 and 3 until all K centroids have been selected.
2. Proceed with standard Lloyd's algorithm iterations.

K-Means++ guarantees an expected approximation ratio of E[J] ≤ 8 · (ln(K) + 2) · J_optimal, dramatically accelerating convergence and preventing degenerate clusters.

Determining Optimal K: Elbow Method & Silhouette Analysis#

Because K is an extrinsic hyperparameter, practitioners use quantitative validation criteria to select K:

1. The Elbow Method: Plots Inertia J against candidate values of K. As K increases, J monotonically decreases (reaching J = 0 when K = m). The optimal K is selected at the point of maximum curvature (the 'elbow'), where additional clusters yield diminishing returns in variance reduction.
2. The Silhouette Coefficient: Measures how well-separated and cohesive clusters are. For an instance x^(i) belonging to cluster C_A:

* Let a(i) be the mean intra-cluster distance from x^(i) to all other points in C_A:

```

a(i) = (1 / (|C_A| - 1)) · ∑ [j ∈ C_A, j ≠ i] ||x^(i) - x^(j)||

```

* Let b(i) be the minimum mean distance from x^(i) to points in any other cluster C_B (where B ≠ A):

```

b(i) = min [B ≠ A] [ (1 / |C_B|) · ∑ [j ∈ C_B] ||x^(i) - x^(j)|| ]

```

* The Silhouette Coefficient s(i) is:

```

s(i) = (b(i) - a(i)) / max( a(i), b(i) ) ∈ [-1, +1]

```

* s(i) ≈ +1: Point is far from neighboring clusters and tightly bound to its own cluster (excellent assignment).

* s(i) ≈ 0: Point lies on the decision boundary between two clusters.

* s(i) ≈ -1: Point is closer to a neighboring cluster than its assigned cluster (misclustered).

Density-Based Clustering: DBSCAN#

While K-Means assumes convex, spherical clusters of roughly equal variance, real-world data structures frequently form non-convex, manifold, or arbitrary geometric shapes (e.g., concentric rings, spirals, dense topological filaments). Furthermore, K-Means forces every observation—including severe outliers—into a cluster.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) defines clusters as contiguous regions of high point density separated by regions of low density.

+---------------------------------------------------------------------------------------+
|                                DBSCAN Core Topology                                   |
+---------------------------------------------------------------------------------------+
|                                                                                       |
|             ( * )  ( * )                                                              |
|          ( * )  ( Core )  ( * )  <--- Core Point: |N_ε(p)| >= MinPts                  |
|             ( * )     \                                                               |
|                        ( Border ) <--- Border Point: |N_ε(p)| < MinPts,               |
|                                       but reachable from Core                         |
|                                                                                       |
|                                     x ( Noise / Outlier )                             |
|                                                                                       |
+---------------------------------------------------------------------------------------+

Core Definitions#

DBSCAN is parametrized by two hyperparameters: neighborhood radius ε > 0 and minimum points MinPts ∈ ℕ.

1. ε-Neighborhood: The open ball of radius ε centered at point p:

```

N_ε(p) = { q ∈ S | dist(p, q) ≤ ε }

```

1. Core Point: A point p is a core point if its ε-neighborhood contains at least MinPts points:

```

|N_ε(p)| ≥ MinPts

```

1. Directly Density-Reachable: Point q is directly density-reachable from point p if p is a core point and q ∈ N_ε(p). (Note: this relationship is asymmetric if q is not a core point).
2. Density-Reachable: Point q is density-reachable from p if there exists a chain of points p_1, p_2, ..., p_n where p_1 = p, p_n = q, and each p_(i+1) is directly density-reachable from p_i.
3. Density-Connected: Points p and q are density-connected if there exists an intermediate point o such that both p and q are density-reachable from o.
4. Cluster: A maximal set of density-connected points.
5. Noise Point: Any point that is neither a core point nor density-reachable from any core point.

Advantages & Trade-Offs#

• Advantages: Discovers arbitrary non-linear cluster shapes; automatically discovers the number of clusters K; explicitly isolates and removes noise/outliers.
• Limitations: Struggles when clusters possess significantly different local densities; O(m^2) distance computation complexity (reduced to O(m log m) with spatial index trees like k-d trees or Ball trees).

Hierarchical Clustering#

Hierarchical clustering constructs a nested tree of clusters called a Dendrogram, eliminating the need to pre-specify K in advance.

Agglomerative (Bottom-Up) Mechanics#

Agglomerative hierarchical clustering begins with each observation x^(i) in its own singleton cluster: C_i = {x^(i)}. At each iteration, the two clusters exhibiting the minimum inter-cluster distance are merged, repeating until a single cluster contains all m instances.

The inter-cluster distance between two clusters C_A and C_B depends on the linkage criterion:

1. Single Linkage (Minimum Distance):

```

d_single(C_A, C_B) = min [x ∈ C_A, z ∈ C_B] ||x - z||

```

Sensitive to outliers; produces elongated, stringy clusters (the chaining effect).

1. Complete Linkage (Maximum Distance):

```

d_complete(C_A, C_B) = max [x ∈ C_A, z ∈ C_B] ||x - z||

```

Forces compact, spherical clusters of roughly equal diameter; sensitive to noise.

1. Average Linkage (UPGMA):

```

d_avg(C_A, C_B) = (1 / (|C_A| · |C_B|)) · ∑ [x ∈ C_A] ∑ [z ∈ C_B] ||x - z||

```

Robust compromise balancing single and complete linkage.

1. Ward's Linkage (Minimum Variance):

Measures the increase in total within-cluster sum of squares resulting from merging C_A and C_B:

```

Δ J_Ward = [ (|C_A| · |C_B|) / (|C_A| + |C_B|) ] · ||μ_A - μ_B||^2

```

Produces balanced, spherical clusters and is mathematically consistent with K-Means objectives.

Dimensionality Reduction: Principal Component Analysis (PCA)#

High-dimensional feature spaces present severe computational and statistical challenges known collectively as the Curse of Dimensionality:

• In high dimensions, sample data becomes extremely sparse; data points cluster along the outer boundaries of the bounding hypercube.
• Pairwise Euclidean distances become equidistant: lim [d → ∞] (dist_max - dist_min) / dist_min = 0, degrading distance-based metrics (k-NN, K-Means).
• High multicollinearity increases parameter variance in supervised models.

Principal Component Analysis (PCA) is an orthogonal linear transformation that maps data from ℝ^d into a lower-dimensional subspace ℝ^k (k ≤ d) such that the first principal component accounts for the largest possible variance in the data, each succeeding component accounts for the highest possible remaining variance under the constraint of being mutually orthogonal to all preceding components.

Derivation 1: Maximum Variance Projection#

Let X ∈ ℝ^(m × d) be the centered data matrix (where each feature column has zero empirical mean: ∑_i x^(i) = 0). The sample covariance matrix Σ ∈ ℝ^(d × d) is:

Σ = (1 / m) · X^T X

We seek a unit projection vector u_1 ∈ ℝ^d (with ||u_1||_2 = u_1^T u_1 = 1) that maximizes the sample variance of the projected data points:

Projection: z_1^(i) = u_1^T x^(i)
Sample Variance: Var(z_1) = (1 / m) · ∑ [i = 1 to m] (u_1^T x^(i))^2
                          = (1 / m) · u_1^T (X^T X) u_1
                          = u_1^T Σ u_1

We formulate this as a constrained optimization problem via the method of Lagrange multipliers:

Maximize:   L(u_1, λ_1) = u_1^T Σ u_1 - λ_1 · (u_1^T u_1 - 1)

Setting the partial derivative with respect to u_1 to zero:

∇_(u_1) L = 2 · Σ u_1 - 2 · λ_1 · u_1 = 0
Σ u_1 = λ_1 · u_1

This is the canonical eigenvalue equation. The optimal projection vector u_1 is an eigenvector of the covariance matrix Σ, and the variance along this direction is exactly the corresponding eigenvalue λ_1:

Var(z_1) = u_1^T Σ u_1 = u_1^T (λ_1 u_1) = λ_1 · (u_1^T u_1) = λ_1

To maximize variance, u_1 must be the eigenvector corresponding to the largest eigenvalue λ_1.

Derivation 2: Minimum Reconstruction Error#

Equivalently, PCA can be derived as finding the k-dimensional linear subspace that minimizes the total squared Euclidean reconstruction error between original points x^(i) and their projected approximations x_hat^(i) = U_k U_k^T x^(i):

Minimize:   J_recon = (1 / m) · ∑ [i = 1 to m] ||x^(i) - U_k U_k^T x^(i)||^2

Both formulations yield the exact same subspace spanned by the top k eigenvectors of Σ.

Spectral Decomposition & Explained Variance Ratio#

Because Σ is a real, symmetric, positive semi-definite matrix, the Spectral Theorem guarantees that Σ can be diagonalized into an orthonormal basis of eigenvectors:

Σ = V Λ V^T

where V = [v_1, v_2, ..., v_d] is the orthogonal matrix of eigenvectors (V^T V = I) and Λ = diag(λ_1, λ_2, ..., λ_d) with sorted eigenvalues λ_1 ≥ λ_2 ≥ ... ≥ λ_d ≥ 0.

The Explained Variance Ratio (EVR) of principal component j measures the fraction of total dataset variance captured by that component:

EVR_j = λ_j / [ ∑ [i = 1 to d] λ_i ]

The cumulative explained variance across k components is:

Cumulative EVR(k) = [ ∑ [j = 1 to k] λ_j ] / [ ∑ [i = 1 to d] λ_i ]

Practitioners select k such that Cumulative EVR exceeds a target retention threshold (e.g., 90% or 95%).

Singular Value Decomposition (SVD) Connection#

In modern scientific packages (e.g., NumPy, scikit-learn), PCA is rarely computed via explicit covariance matrix inversion. Instead, it is computed via the Singular Value Decomposition (SVD) of the centered data matrix X:

X = U S V^T

where U ∈ ℝ^(m × m) is orthogonal, S ∈ ℝ^(m × d) contains non-negative singular values s_i along its diagonal, and V ∈ ℝ^(d × d) is orthogonal.

The covariance matrix can be rewritten as:

Σ = (1 / m) · X^T X = (1 / m) · (V S^T U^T) (U S V^T) = (1 / m) · V (S^T S) V^T

Since S^T S = diag(s_1^2, s_2^2, ..., s_d^2), the right singular vectors V are identical to the principal component eigenvectors, and the eigenvalues relate to singular values by:

λ_i = s_i^2 / m

Computing SVD directly on X avoids forming the d × d covariance matrix, preventing numerical precision loss and catastrophic rounding errors.

Non-Linear Dimensionality Reduction: Manifold Learning#

PCA is strictly a linear transformation; it cannot unfold curved, twisted, or non-linear low-dimensional manifolds embedded within high-dimensional space (such as the classic 'Swiss Roll').

+---------------------------------------------------------------------------------------+
|                               Linear vs. Non-Linear Embeddings                        |
+---------------------------------------------------------------------------------------+
|  PCA (Linear Projection): Collapses folds, destroying neighborhood proximity          |
|  t-SNE / UMAP (Manifold): Unfolds the manifold, preserving local neighborhood topology|
+---------------------------------------------------------------------------------------+

t-Distributed Stochastic Neighbor Embedding (t-SNE)#

t-SNE (van der Maaten and Hinton, 2008) converts Euclidean distances between points into conditional probabilities representing similarities:

1. High-Dimensional Probabilities (Gaussian):

The probability that point x_i picks x_j as its neighbor under a Gaussian distribution:

```

p_(j|i) = exp( - ||x_i - x_j||^2 / (2 σ_i^2) ) / [ ∑ [k ≠ i] exp( - ||x_i - x_k||^2 / (2 σ_i^2) ) ]

p_ij = (p_(j|i) + p_(i|j)) / (2 m)

```

where the bandwidth σ_i is set dynamically via user-specified perplexity.

1. Low-Dimensional Probabilities (Student-t Distribution):

In the lower-dimensional map space (y_i, y_j ∈ ℝ^2), similarities are modeled using a heavy-tailed Cauchy (Student-t with 1 degree of freedom) distribution:

```

q_ij = (1 + ||y_i - y_j||^2)^(-1) / [ ∑ [k] ∑ [l ≠ k] (1 + ||y_k - y_l||^2)^(-1) ]

```

The heavy tails resolve the Crowding Problem: points at moderate distances in high dimensions have ample room to separate in 2D space without collapsing together.

1. Kullback-Leibler (KL) Divergence Minimization:

The coordinates {y_i} are optimized by minimizing the KL divergence between distributions P and Q via gradient descent:

```

KL(P || Q) = ∑ [i ≠ j] p_ij · ln( p_ij / q_ij )

```

Note on t-SNE: t-SNE preserves local neighborhood clustering exceptionally well, making it the gold standard for visual cluster exploration. However, global distances between distant clusters in a t-SNE plot are largely arbitrary and non-interpretable.

Checkpoint Practice Problems#

Problem 1 (K-Means Voronoi Assignment & Centroid Update): A 1D dataset consists of m = 6 points:

S = { 2, 4, 10, 12, 20, 22 }

We wish to partition S into K = 2 clusters. Initial centroids are chosen as:

μ_1 = 3, μ_2 = 18

1. Execute the Expectation (Assignment) Step: Assign each of the 6 data points to the closest centroid (using absolute distance |x - μ|).
2. Execute the Maximization (Update) Step: Compute the updated centroid coordinates μ_1_new and μ_2_new.
3. Compute the Within-Cluster Sum of Squares (Inertia) J for the new clustering.

Solution:

1. Assignment Step:

* x = 2: |2 - 3| = 1, |2 - 18| = 16 -> Cluster 1

* x = 4: |4 - 3| = 1, |4 - 18| = 14 -> Cluster 1

* x = 10: |10 - 3| = 7, |10 - 18| = 8 -> Cluster 1

* x = 12: |12 - 3| = 9, |12 - 18| = 6 -> Cluster 2

* x = 20: |20 - 3| = 17, |20 - 18| = 2 -> Cluster 2

* x = 22: |22 - 3| = 19, |22 - 18| = 4 -> Cluster 2

Assignments:

```

Cluster 1 (C_1) = { 2, 4, 10 }

Cluster 2 (C_2) = { 12, 20, 22 }

```

1. Centroid Update Step:

```

μ_1_new = (2 + 4 + 10) / 3 = 16 / 3 ≈ 5.3333

μ_2_new = (12 + 20 + 22) / 3 = 54 / 3 = 18.0

```

1. Compute Inertia J:

* For C_1 (μ_1 = 16/3):

(2 - 16/3)^2 = (-10/3)^2 = 100/9

(4 - 16/3)^2 = (-4/3)^2 = 16/9

(10 - 16/3)^2 = (14/3)^2 = 196/9

Sum_1 = (100 + 16 + 196) / 9 = 312 / 9 = 104 / 3 ≈ 34.667

* For C_2 (μ_2 = 18):

(12 - 18)^2 = (-6)^2 = 36

(20 - 18)^2 = (2)^2 = 4

(22 - 18)^2 = (4)^2 = 16

Sum_2 = 36 + 4 + 16 = 56

* Total Inertia J:

```

J = 34.667 + 56 = 90.667

```

Problem 2 (Silhouette Coefficient for Cluster Assignment): A 2D dataset contains two clusters:

• Cluster A: Point A_1 = [0, 0]^T, Point A_2 = [0, 2]^T
• Cluster B: Point B_1 = [3, 0]^T, Point B_2 = [3, 2]^T

Compute the exact Silhouette Coefficient s(A_1) for Point A_1.

Solution:

1. Compute mean intra-cluster distance a(A_1):

Cluster A has only one other point: A_2 = [0, 2]^T.

```

dist(A_1, A_2) = √[ (0 - 0)^2 + (0 - 2)^2 ] = √4 = 2.0

a(A_1) = 2.0

```

1. Compute mean nearest-cluster distance b(A_1) to Cluster B:

* dist(A_1, B_1) = √[ (0 - 3)^2 + (0 - 0)^2 ] = √9 = 3.0

* dist(A_1, B_2) = √[ (0 - 3)^2 + (0 - 2)^2 ] = √[ 9 + 4 ] = √13 ≈ 3.60555

```

b(A_1) = (dist(A_1, B_1) + dist(A_1, B_2)) / 2

= (3.0 + 3.60555) / 2 = 6.60555 / 2 ≈ 3.3028

```

1. Compute Silhouette Coefficient s(A_1):

```

max( a(A_1), b(A_1) ) = max( 2.0, 3.3028 ) = 3.3028

s(A_1) = (b(A_1) - a(A_1)) / max(a, b)

= (3.3028 - 2.0) / 3.3028

= 1.3028 / 3.3028 ≈ 0.3945

```

Point A_1 has a positive silhouette score of approximately +0.395, indicating valid cluster membership.

Problem 3 (PCA Covariance Matrix & Explained Variance Ratio): A centered 2D dataset has empirical sample covariance matrix:

Σ = [ [ 5, 2 ],
      [ 2, 2 ] ]

1. Compute the eigenvalues λ_1 and λ_2 of Σ.
2. Find the normalized first principal component eigenvector v_1 corresponding to the larger eigenvalue λ_1.
3. Compute the Explained Variance Ratio (EVR) of the first principal component.

Solution:

1. Characteristic Equation det(Σ - λ I) = 0:

```

det [ [5 - λ, 2 ],

[2, 2 - λ] ] = 0

(5 - λ)(2 - λ) - (2)(2) = 0

10 - 7λ + λ^2 - 4 = 0

λ^2 - 7λ + 6 = 0

```

Factoring the quadratic:

```

(λ - 6)(λ - 1) = 0

λ_1 = 6, λ_2 = 1

```

1. Find Eigenvector v_1 for λ_1 = 6:

```

(Σ - 6 I) v_1 = 0

[ [5 - 6, 2 ], [ [v_11], = [ [0],

[2, 2 - 6] ] [v_12] ] [0] ]

[ [-1, 2], [ [v_11], = [ [0],

[ 2, -4] ] [v_12] ] [0] ]

```

From row 1: -v_11 + 2 v_12 = 0 ===> v_11 = 2 v_12.

Let v_12 = 1; then v_11 = 2. Unnormalized vector: [2, 1]^T.

Normalize to unit length:

```

||v_1|| = √(2^2 + 1^2) = √5

v_1 = [ 2 / √5, 1 / √5 ]^T ≈ [ 0.8944, 0.4472 ]^T

```

1. Compute Explained Variance Ratio (EVR):

```

Total Variance = λ_1 + λ_2 = 6 + 1 = 7

EVR_1 = λ_1 / Total Variance = 6 / 7 ≈ 0.8571 (85.71%)

```

The first principal component captures 85.71% of the total variance in the dataset.

Problem 4 (DBSCAN Density Classification): Given five points in a 1D metric space:

P_1 = 1.0, P_2 = 1.8, P_3 = 2.5, P_4 = 5.0, P_5 = 9.0

The DBSCAN parameters are set to:

ε = 1.0, MinPts = 3 (where the neighborhood includes the point itself).

1. Determine the ε-neighborhood N_ε(P_i) for each of the five points.
2. Identify all Core Points, Border Points, and Noise Points.
3. Formulate the resulting clusters.

Solution:

1. Compute pairwise distances and neighborhoods (with ε = 1.0):

P_1 (1.0)*:

dist(P_1, P_2) = 0.8 ≤ 1.0. All others > 1.0.

N_ε(P_1) = { P_1, P_2 } -> Size = 2.

P_2 (1.8)*:

dist(P_2, P_1) = 0.8 ≤ 1.0.

dist(P_2, P_3) = |1.8 - 2.5| = 0.7 ≤ 1.0.

N_ε(P_2) = { P_1, P_2, P_3 } -> Size = 3.

P_3 (2.5)*:

dist(P_3, P_2) = 0.7 ≤ 1.0. All others > 1.0.

N_ε(P_3) = { P_2, P_3 } -> Size = 2.

P_4 (5.0)*:

dist to nearest point is |5.0 - 2.5| = 2.5 > 1.0.

N_ε(P_4) = { P_4 } -> Size = 1.

P_5 (9.0)*:

dist to nearest is |9.0 - 5.0| = 4.0 > 1.0.

N_ε(P_5) = { P_5 } -> Size = 1.

1. Classify points (MinPts = 3):

Core Points (|N_ε| ≥ 3): P_2* (size = 3).

Border Points* (|N_ε| < 3, but in neighborhood of a core point):

P_1 ∈ N_ε(P_2) -> P_1 is a Border Point*.

P_3 ∈ N_ε(P_2) -> P_3 is a Border Point*.

Noise Points* (|N_ε| < 3, not in neighborhood of any core point):

P_4 is Noise*.

P_5 is Noise*.

1. Formulate Clusters:

Cluster 1*: { P_1, P_2, P_3 } (P_2 is the core, connecting border points P_1 and P_3).

Noise*: { P_4, P_5 }.