UNIT 09 Machine Learning & Applied AI Track

Clustering Algorithms & Segmentation

Comprehensive theoretical mastery and production implementations of geometric partitioning, density discovery, hierarchical agglomeration, graph spectrum Laplacians, and customer persona segmentation.

01

Distance Metrics & Geometric Foundations

Every clustering algorithm operates on pairwise dissimilarity. Dissimilarity quantifies the geometric or probabilistic separation between feature vectors in a metric space. Formally, a metric on a set X is a real-valued function d: X × X → R that satisfies four fundamental axioms for all x, y, z in X:

Metric Space Axioms

  • Non-Negativity: d(x, y) ≥ 0, bounded from below.
  • Identity of Indiscernibles: d(x, y) = 0 ⇔ x = y.
  • Symmetry: d(x, y) = d(y, x).
  • Triangle Inequality: d(x, z) ≤ d(x, y) + d(y, z) (prevents shortcut violations).

Engineering Significance

When the triangle inequality holds, clustering algorithms can leverage spatial indexing structures (such as k-d trees, Ball trees, and VP-trees) to prune neighbor searches from brute-force O(N^2) down to O(N log N). Non-metric divergence measures (such as KL divergence) violate symmetry and the triangle inequality.

Core Distance Metrics in Machine Learning

Metric Mathematical Formulation Iso-Distance Contour Geometry Optimal Production Use Cases
Euclidean (L_2 Norm) d_2(x, y) = √{Sum i=1^D (x_i - y_i)^2} = x - y₂ Hypersphere (circular in 2D) Continuous, physical coordinates; standard isotropic K-Means; isotropic GMM.
Manhattan (L_1 Norm) d_1(x, y) = Sum i=1^D |x_i - y_i| = x - y₁ Cross-polytope / Diamond in 2D Grid layouts (taxicab routing), sparse feature vectors, high-dimensional datasets resistant to hubness.
Minkowski (L_p Norm) d_p(x, y) = (Sum i=1^D |x_i - y_i|^p right)1/p p < 1: Concave star; p=1: Diamond; p=2: Circle; p → infty: Square (L_infty). Generalization metric; p < 1 fractional norms combat distance concentration in ultra-high dimensions.
Cosine Distance d cos(x, y) = 1 - (x · y / x₂ y₂) = 1 - cos(θ) Angular ray projection (length-invariant) Text embeddings (TF-IDF, Word2Vec, BERT), customer browsing clickstreams, high-cardinality recommendation vectors.
Mahalanobis Distance D_M(x, y) = √{(x - y)^T Σ-1 (x - y)} Rotated hyper-ellipsoid aligned with covariance eigenvectors Correlated multi-sensor signals, multivariate anomaly detection, scale-invariant clustering without pre-scaling.
System Architecture • Decision Flow for Metric Selection
Input Assessment
Feature Modality
Continuous continuous vs sparse high-dimensional vs correlated multi-variate.
➔
Correlation Check
Covariance Structure
Are features independent or correlated? If collinear, apply Mahalanobis or PCA whitening.
➔
Magnitude Check
Length Invariance
Does vector magnitude encode quantity or noise? If direction dominates, choose Cosine distance.
➔
Execution Engine
Metric Ingestion
Instantiate distance kernel across clustering loss functions and spatial tree structures.
02

K-Means Clustering & Seeding Mechanics

K-Means is a centroid-based, iterative partitioning algorithm that divides N observations into K disjoint, non-empty clusters C = {C_1, C_2, dots, C_K }. The optimization objective minimizes the Within-Cluster Sum of Squares (WCSS), also called Inertia:

Cluster Assignment Step:
Assign each sample point x_i to Cluster k whose centroid μ_k has the smallest Euclidean distance to x_i across all clusters
➔
Step 2
Distance Sampling
For every point x, compute D(x) = minj x - μ_j₂, the distance to its nearest existing centroid.
➔
Step 3
Weighted Selection
Select next centroid μm+1 with probability proportional to D(x)^2: P(x) = (D(x)^2 / Sum x' D(x')^2).
➔
Step 4
Lloyd Initialization
Repeat Steps 2 & 3 until all K centroids are chosen; initiate Lloyd's alternating optimization.
03

Cluster Validation: Elbow Method & Silhouette Analysis

Because unsupervised clustering algorithms operate without true ground-truth labels (y), determining the optimal number of clusters (K) requires internal validation metrics evaluating cluster cohesion (compactness) and separation (isolation).

The Elbow Method (WCSS Inflection)

The Elbow method plots Inertia (WCSS) against candidate values of K in [2, K max]. Because adding centroids provides additional degrees of freedom to minimize squared distances, WCSS strictly decreases monotonically as K → N, reaching zero when K=N.

Formulation:
Inflection Criterion: Δ J(K) gg Δ J(K+1)

The optimal K corresponds to the "elbow point" where the rate of decrease drops sharply, marking diminishing returns. Caveat: On real continuous data with overlapping density gradients, the curve is often smooth, leaving the elbow ambiguous.

Silhouette Coefficient Analysis

Pioneered by Peter Rousseeuw (1987), the Silhouette Coefficient provides an unambiguous score s(i) in [-1, +1] for every individual sample x_i, balancing intra-cluster cohesion against inter-cluster separation.

Formulation:
s(i) = (b(i) - a(i) / max(a(i), b(i)))

Where a(i) is the mean distance from x_i to all other points in its own cluster, and b(i) is the mean distance to all points in the nearest neighboring cluster.

Detailed Interpretation of the Silhouette Metric

Evaluation Metric Optimization Objective Mathematical Definition Algorithmic Pros & Cons
Inertia (WCSS) Minimization (Elbow Inflection) Sum k=1^K Sum x in C_k x - μ_k^2 Extremely fast O(NK); biased toward spherical clusters; strictly non-increasing with K.
Silhouette Score Maximization (max_K Mean_s) (1 / N) Sum i=1^N (b(i) - a(i) / max(a(i), b(i))) Objective scale [-1, +1]; penalizes over-clustering; computationally expensive O(N^2).
Davies-Bouldin Index Minimization (min_K R) (1 / K) Sum i=1^K maxj ≠ i ( (σ_i + σ_j / d(μ_i, μ_j)) right) Fast computation; evaluates worst-case cluster overlap; assumes Euclidean metric spaces.
Calinski-Harabasz Index Maximization (Variance Ratio) (Tr(B_K) / (K - 1) / Tr(W_K) / (N - K)) Ratio of between-cluster to within-cluster dispersion; very fast; prefers convex clusters.
04

K-Medoids & Partitioning Around Medoids (PAM)

While K-Means calculates an artificial virtual centroid as the arithmetic mean μ_k, K-Medoids restricts each cluster center to be an actual observed data point from the dataset, called a medoid (m_k in D).

The Outlier Vulnerability in K-Means

Because K-Means minimizes squared Euclidean errors (x - μ^2), an extreme outlier with large distance d exerts a quadratic pulling force (d^2) on the centroid. This drags μ_k away from the true cluster core and severely distorts the Voronoi partitioning boundaries.

The PAM Robustness Advantage

K-Medoids minimizes total un-squared pairwise dissimilarity: Sum i in C_k d(x_i, m_k). The medoid acts as a multi-dimensional median. Extreme outliers cannot drag a medoid away from the dense cluster center, providing high robustness and support for non-Euclidean metrics (Manhattan, Cosine, Gower).

The PAM (Partitioning Around Medoids) Algorithm

  1. Build Phase: Greedily select K initial medoids that minimize total dissimilarity across the dataset.
  2. Swap Phase (Iterative Optimization): For each medoid m_i and each non-medoid candidate point x_h:
    • Compute the total cost change Δ Tih if m_i and x_h are swapped.
    • If the best swap reduces total cost (Δ Tih < 0), execute the swap (Swap current medoid m_i with non-medoid point x_h).
    • Repeat until no swap can further decrease total system dissimilarity.
Complexity Trade-off & CLARA Scaling
Standard PAM requires O(K(N-K)^2) per iteration, making it intractable for massive datasets (N > 50,000). For industrial scale, CLARA (Clustering Large Applications) samples small representative subsets of size 40 + 2K, executes PAM on each subset, and selects the medoid set minimizing overall dataset dissimilarity.
05

Hierarchical & Agglomerative Clustering

Hierarchical Clustering builds a nested tree of partitions without requiring a pre-specified cluster count K. Algorithms follow one of two paradigms:

Linkage Criteria: Distance Between Sets

The decision of which two clusters A and B to merge depends on the Linkage Criterion D(A, B):

Linkage Method Mathematical Formulation Geometric Behavior Susceptibility & Trade-offs
Single Linkage (Min) D(A, B) = mina in A, b in B d(a, b) Detects arbitrary non-elliptical shapes; minimal spanning tree connectivity. Chaining Effect: A slender bridge of noise points can cause two distinct clusters to merge prematurely.
Complete Linkage (Max) D(A, B) = maxa in A, b in B d(a, b) Enforces compact, spherical clusters with small maximum diameters. Highly sensitive to outliers on the cluster periphery; breaks down elongated continuous manifolds.
Average Linkage (UPGMA) D(A, B) = (1 / |AB|) Sum a in A Sum b in B d(a, b) Balances single and complete linkage; robust middle ground. Sensitive to monotonic non-linear metric transformations; intermediate computational complexity.
Ward's Minimum Variance Δ ESSAB = (|AB| / |A| + |B|) μ_A - μ_B₂² Minimizes the increase in total within-cluster variance at each merge step. Requires Euclidean distances; produces highly uniform, compact clusters; industry standard for general tabular data.
Hierarchical Dendrogram Cutting Architecture
Leaf Nodes (N=6)
Singleton Points
{x1}, {x2}, {x3}, {x4}, {x5}, {x6} initialized at merge height h=0.
➔
Pairwise Merge
Linkage Computation
Iteratively merge closest pairs based on Ward's minimal variance increase.
➔
Dendrogram Tree
Cophenetic Alignment
Vertical branch heights represent exact distance D(A, B) at merge instance.
➔
Horizontal Cut
Threshold Extraction
Draw horizontal line at threshold h^*. Number of intersected vertical lines yields optimal K.
06

DBSCAN: Density-Based Spatial Clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) operates on a spatial density paradigm: clusters are dense regions in feature space separated by regions of low density. It discovers clusters of arbitrary shapes and isolates anomalies as noise without requiring a pre-specified cluster count K.

Hyperparameters & Fundamental Point Classifications

DBSCAN relies on two parameters: ε (Epsilon) (the neighborhood radius) and MinPts (minimum points required within the radius). For each point x in D, the ε-neighborhood is defined as:

Formulation: Formulation: N_ε(x) = { x' in D : x - x' ≤ ε }

1. Core Point

|N_ε(x)| ≥ MinPts. The point resides in a dense region and can originate and expand a cluster.

2. Border Point

|N_ε(x)| < MinPts, but x in N_ε(p) where p is a Core point. It belongs to the cluster but cannot expand it.

3. Noise Point

Neither a Core nor a Border point. It is classified as an anomaly/noise point (assigned label -1).

Density Reachability & Connectivity

Production Parameter Selection Heuristic (The k-Distance Graph)
To select ε systematically, set k = MinPts - 1 (rule of thumb: MinPts ≥ 2 × D). Compute the distance to each point's k-th nearest neighbor across the entire dataset. Sort these distances in descending order and plot them. The optimal ε is located at the sharp "knee" or "elbow" of the k-distance curve.
07

Spectral Clustering & Graph Laplacians

When data forms complex, non-convex manifolds (such as concentric circles or spirals), both centroid-based (K-Means) and distance-variance methods fail because they impose convex geometries. Spectral Clustering solves this by reformulating clustering as a Graph Cut problem on an undirected weighted similarity graph G = (V, E, W).

1. Affinity & Degree Matrices

Nodes represent data points. Edge weights represent pairwise affinity using the Gaussian Radial Basis Function (RBF):

Formulation: Formulation: Wij = exp( -(x_i - x_j^2 / 2σ^2) right) quad for i ≠ j, quad Wii = 0

The diagonal Degree Matrix D contains the total weight of edges incident to each node: Dii = Sum j=1^N Wij.

2. Graph Laplacians

Unnormalized Laplacian

Formulation:
L = D - W

Symmetric, positive semi-definite matrix. The multiplicity of eigenvalue 0 equals the number of connected components in the graph.

Symmetric Normalized

Formulation:
Lsym = D-1/2 L D-1/2 = I - D-1/2 W D-1/2

Normalized for node degrees. Minimizes the Normalized Cut (NCut) objective, preventing tiny isolated clusters.

Random Walk Laplacian

Formulation:
Lrw = D-1 L = I - D-1 W

Directly models transition probabilities of a Markov random walk jumping between data points.

Spectral Clustering Pipeline (Shi-Malik / Ng-Jordan-Weiss)
Step 1
Affinity Graph
Construct Gaussian RBF affinity matrix W and diagonal degree matrix D.
➔
Step 2
Laplacian Matrix
Compute symmetric normalized Laplacian Lsym = I - D-1/2 W D-1/2.
➔
Step 3
Eigenspace Projection
Extract eigenvectors u_1, dots, u_K corresponding to the K smallest eigenvalues of Lsym.
➔
Step 4
K-Means in Eigenspace
Normalize rows of eigenvector matrix U to unit length; run standard K-Means to cluster the embedded points.
08

Production Customer Segmentation & Benchmark Pipeline

In enterprise commerce, customer segmentation transforms raw transaction logs into distinct behavioral cohorts for personalized marketing, retention automation, and credit risk scoring. This end-to-end production pipeline implements:

customer_segmentation_pipeline.py 
# =====================================================================
# DevAscent Academy: Production Customer Segmentation & Clustering Benchmark
# Requires: numpy, pandas, scikit-learn
# =====================================================================

import numpy as np
import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN
from sklearn.metrics import silhouette_score, calinski_harabasz_score, davies_bouldin_score

def run_customer_segmentation_benchmark():
    # -----------------------------------------------------------------
    # 1. Synthesize Production RFM (Recency, Frequency, Monetary) Dataset
    # -----------------------------------------------------------------
    np.random.seed(42)
    n_samples = 1500

    # Cohort 1: VIP Champions (Low Recency, High Frequency, High Monetary)
    c1_recency = np.random.exponential(scale=10, size=300) + 1
    c1_frequency = np.random.normal(loc=35, scale=6, size=300).clip(15, 60)
    c1_monetary = np.random.normal(loc=4500, scale=800, size=300).clip(2000, 8000)

    # Cohort 2: Loyal Mid-Tier (Moderate Recency, Moderate Frequency, Moderate Monetary)
    c2_recency = np.random.exponential(scale=45, size=600) + 5
    c2_frequency = np.random.normal(loc=12, scale=3, size=600).clip(4, 25)
    c2_monetary = np.random.normal(loc=950, scale=250, size=600).clip(400, 2000)

    # Cohort 3: Churn Risk / Hibernating (High Recency, Low Frequency, Low Monetary)
    c3_recency = np.random.normal(loc=180, scale=40, size=600).clip(60, 365)
    c3_frequency = np.random.poisson(lam=2, size=600).clip(1, 5)
    c3_monetary = np.random.exponential(scale=120, size=600) + 20

    # Assemble Raw DataFrame
    df = pd.DataFrame({
        'Recency_Days': np.concatenate([c1_recency, c2_recency, c3_recency]),
        'Frequency_Orders': np.concatenate([c1_frequency, c2_frequency, c3_frequency]),
        'Monetary_Spend': np.concatenate([c1_monetary, c2_monetary, c3_monetary])
    })

    print(f"[Dataset] Generated {len(df)} Customer Profiles with RFM Modalities.")
    
    # -----------------------------------------------------------------
    # 2. Skewness Correction & Feature Standardization
    # -----------------------------------------------------------------
    # Monetary and Recency features exhibit heavy positive skew; apply log1p
    df_transformed = np.log1p(df)
    
    scaler = StandardScaler()
    X_scaled = scaler.fit_transform(df_transformed)

    # -----------------------------------------------------------------
    # 3. K-Means Elbow & Silhouette Evaluation Sweep (K=2 to K=7)
    # -----------------------------------------------------------------
    print("\n--- [Phase 1] K-Means Clustering Validation Sweep ---")
    best_k = 3
    best_silhouette = -1.0
    sweep_results = []

    for k in range(2, 8):
        km = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
        labels = km.fit_predict(X_scaled)
        
        sil = silhouette_score(X_scaled, labels)
        ch = calinski_harabasz_score(X_scaled, labels)
        db = davies_bouldin_score(X_scaled, labels)
        
        sweep_results.append({
            'K': k, 'Inertia_WCSS': round(km.inertia_, 2),
            'Silhouette': round(sil, 4), 'Calinski_Harabasz': round(ch, 1),
            'Davies_Bouldin': round(db, 4)
        })
        
        if sil > best_silhouette:
            best_silhouette = sil
            best_k = k

    sweep_df = pd.DataFrame(sweep_results)
    print(sweep_df.to_string(index=False))
    print(f"\n[Validation] Optimal Cluster Count Identified: K={best_k} (Peak Silhouette: {best_silhouette})")

    # -----------------------------------------------------------------
    # 4. Multi-Algorithm Benchmarking on Standardized Space (K=3)
    # -----------------------------------------------------------------
    print("\n--- [Phase 2] Multi-Algorithm Model Comparison (K=3) ---")
    
    # Model 1: K-Means++
    km_optimal = KMeans(n_clusters=best_k, init='k-means++', n_init=10, random_state=42)
    labels_km = km_optimal.fit_predict(X_scaled)
    
    # Model 2: Agglomerative Hierarchical (Ward's Minimum Variance)
    agg = AgglomerativeClustering(n_clusters=best_k, linkage='ward')
    labels_agg = agg.fit_predict(X_scaled)

    # Model 3: DBSCAN (Density Spatial Partitioning)
    dbscan = DBSCAN(eps=0.75, min_samples=10)
    labels_db = dbscan.fit_predict(X_scaled)
    db_core_mask = labels_db != -1
    db_noise_count = np.sum(~db_core_mask)

    benchmark_rows = [
        {
            'Algorithm': 'K-Means++',
            'Clusters': len(np.unique(labels_km)),
            'Silhouette': round(silhouette_score(X_scaled, labels_km), 4),
            'Davies-Bouldin': round(davies_bouldin_score(X_scaled, labels_km), 4),
            'Notes': 'Convex spherical partitioning'
        },
        {
            'Algorithm': "Agglomerative (Ward)",
            'Clusters': len(np.unique(labels_agg)),
            'Silhouette': round(silhouette_score(X_scaled, labels_agg), 4),
            'Davies-Bouldin': round(davies_bouldin_score(X_scaled, labels_agg), 4),
            'Notes': 'Variance-minimizing bottom-up tree'
        },
        {
            'Algorithm': 'DBSCAN (eps=0.75)',
            'Clusters': len(np.unique(labels_db[db_core_mask])),
            'Silhouette': round(silhouette_score(X_scaled[db_core_mask], labels_db[db_core_mask]), 4),
            'Davies-Bouldin': round(davies_bouldin_score(X_scaled[db_core_mask], labels_db[db_core_mask]), 4),
            'Notes': f'Non-parametric; isolated {db_noise_count} noise samples'
        }
    ]

    bench_df = pd.DataFrame(benchmark_rows)
    print(bench_df.to_string(index=False))

    # -----------------------------------------------------------------
    # 5. Business Persona Profiling (Translating Clusters to Action)
    # -----------------------------------------------------------------
    print("\n--- [Phase 3] Actionable Customer Persona Profiles (K-Means) ---")
    df['Cluster_ID'] = labels_km
    profile_df = df.groupby('Cluster_ID').agg({
        'Recency_Days': 'mean',
        'Frequency_Orders': 'mean',
        'Monetary_Spend': ['mean', 'count']
    }).round(2)
    
    profile_df.columns = ['Avg_Recency_Days', 'Avg_Frequency_Orders', 'Avg_Monetary_Spend', 'Customer_Count']
    
    # Assign Domain Personas
    persona_map = {}
    for cid in profile_df.index:
        rec = profile_df.loc[cid, 'Avg_Recency_Days']
        freq = profile_df.loc[cid, 'Avg_Frequency_Orders']
        if freq > 25 and rec < 20:
            persona_map[cid] = "VIP Champions (Target: Exclusive Perks & Early Access)"
        elif rec > 100:
            persona_map[cid] = "At-Risk Hibernating (Target: Win-Back Discount Campaigns)"
        else:
            persona_map[cid] = "Steady Mid-Tier (Target: Cross-Sell & Upsell Loyalty)"

    profile_df['Strategic_Persona'] = [persona_map.get(cid, "Standard Cohort") for cid in profile_df.index]
    print(profile_df.to_string())

if __name__ == '__main__':
    run_customer_segmentation_benchmark()
09

Engineering Viva Voce & Technical Interviews

Q1 • Distance Metrics Why is the Euclidean distance metric problematic in high-dimensional feature spaces, and why does the Manhattan or fractional distance perform better?
As dimensionality D → infty, the Curse of Dimensionality causes distance concentration: the difference in Euclidean distance between the nearest neighbor and the farthest neighbor approaches zero relative to the distance itself (limD → infty (D max - D min / D min) → 0). Because the Euclidean metric squares coordinate differences ((x_i - y_i)^2), a few noisy dimensions dominate the summation. The Manhattan (L_1) metric does not square differences, providing better contrast and relative variance in higher dimensions.
Q2 • K-Means Convergence Can Lloyd's algorithm enter an infinite loop? What mathematical property guarantees termination?
No, Lloyd's algorithm cannot enter an infinite loop. There are a finite number of ways to partition N data points into K clusters (K^N possible configurations). In both the assignment step and the update step, the objective function JWCSS strictly decreases or remains unchanged. Because the objective function is bounded from below by zero and strictly non-increasing over a finite state space, the sequence of partitions cannot cycle and must terminate in a finite number of iterations at a local minimum or saddle point.
Q3 • K-Means++ Initialization Explain the mathematical mechanism of K-Means++ and why it guarantees an O( log K) competitive ratio.
Standard K-Means picks K initial centroids uniformly at random, which often places multiple initial centroids within a single dense cluster. K-Means++ selects the first centroid randomly, and then selects subsequent centroids with probability proportional to the squared distance to the nearest existing centroid: P(x) = (D(x)^2 / Sum D(x')^2). Points far from all existing centroids are chosen with high probability, spreading seeds across distinct clusters. Arthur and Vassilvitskii proved that this seeding guarantees an expected approximation ratio E[JWCSS] ≤ 8( ln K + 2) Joptimal.
Q4 • Silhouette Coefficient What does a negative Silhouette score indicate for a data point, and what causes an entire cluster to exhibit an average negative score?
The silhouette score is s(i) = (b(i) - a(i) / max(a(i), b(i))). A negative score (s(i) < 0) occurs when a(i) > b(i), meaning the average distance from x_i to points in its own assigned cluster exceeds the average distance to points in the nearest neighboring cluster. For an individual point, this indicates a boundary outlier. When an entire cluster exhibits a negative average silhouette score, it signals severe structural mis-clustering: two true natural clusters have likely been merged, or an artificial cluster boundary was forced through the dense core of a single natural cohort.
Q5 • K-Medoids vs K-Means Why is K-Medoids (PAM) computationally more demanding than K-Means, and under what specific data conditions is K-Medoids required?
In K-Means, updating a centroid requires only the sample mean, taking O(N D) time per iteration. In K-Medoids (PAM), testing whether a non-medoid point should replace a current medoid requires evaluating all pairwise distance deltas across the entire dataset, taking O(K(N - K)^2) per iteration. K-Medoids is required when: (1) the dataset contains extreme outliers that would distort the arithmetic mean, (2) the distance metric is non-Euclidean (e.g., Manhattan, Cosine, or Gower's distance for mixed categorical-continuous data), or (3) the cluster exemplar must be an interpretable, actual physical record (e.g., a real patient's medical profile).
Q6 • Linkage Criteria What is the "chaining phenomenon" in Agglomerative Hierarchical clustering, and which linkage criterion is immune to it?
The chaining phenomenon occurs predominantly in Single Linkage (D(A, B) = min d(a, b)). Because Single Linkage merges clusters based solely on their closest single pair of points, a thin sequence of noise points bridging two distinct natural clusters causes them to merge into one elongated, straggly cluster. Complete Linkage (D(A, B) = max d(a, b)) and Ward's Minimum Variance Linkage are immune to chaining because they measure diameter and variance increase respectively, penalizing elongated chains and enforcing compact clusters.
Q7 • DBSCAN Boundary Conditions Why is DBSCAN non-deterministic for certain boundary points, and how does point processing order impact border assignments?
While Core points and Noise points are strictly deterministic in DBSCAN, Border points that fall within the ε-neighborhood of two or more distinct Core points belonging to different clusters are assigned to whichever cluster visits them first during graph traversal. Because standard DBSCAN processes points sequentially based on dataset index order, altering the order of input rows can reassign shared border points between adjacent clusters.
Q8 • Spectral Clustering Why does Spectral Clustering succeed on concentric ring datasets where K-Means and GMM completely fail?
Both K-Means and Gaussian Mixture Models (GMM) assume that clusters have convex shapes (hyperspheres or hyperellipsoids) and partition space using linear or quadratic Voronoi surfaces. Concentric rings have identical centroids at the origin, so radial distance cannot separate them with convex boundaries. Spectral Clustering constructs an affinity graph W connecting nearby neighbors along the ring manifold. The generalized eigenvectors of the Graph Laplacian Lsym embed these graph connections into an eigenspace where the concentric rings become orthogonal, linearly separable clusters.