91 Clustering Interview Questions and Answers (2026)

Hard clustering assigns each point to exactly one cluster. Soft (fuzzy or probabilistic) clustering gives each point a degree of membership in every cluster, so a point can partially belong to several.

• Hard clustering:

  • Output is a single label per point (e.g. k-means, DBSCAN, agglomerative).

  • Simple to interpret, but it hides uncertainty: a point on a boundary is labeled as confidently as one at a cluster's core.

• Soft clustering:

  • Output is a membership vector per point, usually summing to 1.

  • Gaussian Mixture Models give posterior probabilities ("responsibilities") from EM. Fuzzy c-means gives membership weights controlled by a fuzziness parameter m.

  • Captures overlapping clusters and ambiguity explicitly.

• Relationship between the two:

  • Any soft result can be hardened with argmax. k-means is roughly the limit of a GMM with equal spherical covariances shrinking to zero.

  • In scikit-learn, GaussianMixture.predict_proba gives soft output and predict gives hard output.

• When to prefer soft clustering: overlapping segments (e.g. customers with mixed interests), downstream use of confidence scores, or anomaly flagging of low-membership points.

Classification is supervised: it learns a mapping to predefined labels from labeled examples. Clustering is unsupervised: it discovers groups in unlabeled data based on similarity, with no ground truth defining the groups.

• Data and goal:

  • Classification needs (x, y) pairs and predicts y for new x.

  • Clustering only sees x and finds structure. The clusters have no names until a human interprets them.

• Number of groups:

  • In classification, the classes are fixed by the labels.

  • In clustering, the number of groups must be chosen (k in k-means) or inferred (DBSCAN, HDBSCAN).

• Evaluation:

  • Classification uses accuracy, F1, or AUC against true labels.

  • Clustering uses internal metrics (silhouette, Davies–Bouldin), external metrics when labels exist (ARI, NMI), or business usefulness.

• They are often combined:

  • Cluster first, then label the clusters and train a classifier on them.

  • Cluster IDs can also serve as features for a supervised model.

Clustering algorithms are usually grouped by how they define a cluster: around a center, through a hierarchy of merges, as a dense region, as a probability distribution, or via graph connectivity.

• Partitioning / centroid-based:

  • Examples: k-means, k-medoids (PAM), mini-batch k-means.

  • Fast and scalable. They need k up front and favor convex, similarly sized clusters.

• Hierarchical:

  • Agglomerative (bottom-up) or divisive (top-down), producing a dendrogram.

  • The linkage choice (single, complete, average, Ward) shapes the clusters. No k is needed until you cut the tree. Typically O(n²) memory or worse.

• Density-based:

  • Examples: DBSCAN, HDBSCAN, OPTICS, Mean Shift.

  • Find arbitrary shapes and label noise. They are sensitive to density parameters (eps, min_samples) and struggle when clusters have very different densities (HDBSCAN helps).

• Distribution / model-based:

  • Gaussian Mixture Models fitted with EM.

  • Give soft assignments and elliptical clusters. Model selection is possible via BIC/AIC.

• Graph-based / spectral:

  • Spectral clustering embeds data with eigenvectors of a similarity graph's Laplacian, then runs k-means. Community detection methods (Louvain, Leiden) also belong here.

  • Handle non-convex shapes, but they are costly on large n.

• Others worth naming: grid-based (STING, CLIQUE), BIRCH for streaming or large data, and deep clustering (DEC).

Despite the shared "k", they solve different problems. k-means is an unsupervised clustering algorithm where k is the number of clusters. k-NN is a supervised (or lazy) predictor where k is the number of neighbors consulted to label a new point.

• k-means:

  • Iteratively assigns points to the nearest centroid, then recomputes the centroids. This minimizes within-cluster sum of squares.

  • Has a real training phase and outputs k centroids plus a cluster per point. No labels are needed.

• k-NN:

  • No training: it stores the labeled data. At query time it finds the k closest points and votes (classification) or averages (regression).

  • Cost sits at prediction time. KD-trees, ball trees, or approximate NN indexes speed it up.

• What they share: Both depend on a distance metric, so both need feature scaling and both suffer in high dimensions.

• Choosing k:

  • k-means: elbow method or silhouette score.

  • k-NN: cross-validated predictive performance. Small k means high variance; large k means high bias.

Both algorithms rely on raw distances. A feature with a large numeric range dominates the distance and effectively decides the clusters on its own, regardless of how informative it actually is.

• Example: Take income (0–200,000) and age (0–100). A 1-unit income gap is trivial, yet the income axis is 2,000× wider, so clusters are split almost purely by income.

• k-means: It minimizes squared Euclidean distance, so large-variance features dominate the objective quadratically.

• DBSCAN: A single eps radius applies to all dimensions. Unscaled, that radius is huge on some axes and tiny on others, so no single eps makes sense.

• Common choices:

  • StandardScaler: z-scores, the usual default.

  • MinMaxScaler: bounded range, but sensitive to outliers.

  • RobustScaler: median/IQR, better with outliers.

• Caveat: scaling is itself a weighting decision. Equalizing variance assumes all features matter equally, so domain knowledge may justify deliberate reweighting.

K-means minimizes the within-cluster sum of squares (WCSS, also called inertia): the total squared Euclidean distance from each point to the centroid of its assigned cluster.

• What it implies:

  • For fixed assignments, the mean is the point minimizing squared distance, which is why centroids are means.

  • Equivalent to minimizing within-cluster variance, and (since total variance is fixed) maximizing between-cluster variance.

  • Favors compact, roughly spherical, similar-sized clusters.

• Optimization properties:

  • Finding the global minimum is NP-hard; Lloyd's algorithm only reaches a local minimum.

  • Each assignment and update step never increases J, guaranteeing convergence.

• In scikit-learn the final value is KMeans.inertia_; it always decreases with more clusters, so it can't choose k alone (hence elbow/silhouette).

Because k-means minimizes squared distances and uses the mean as the centroid, a single far-away point contributes a huge squared error and drags its centroid toward it, distorting the whole cluster.

• Squared loss amplifies large errors: A point 10× farther contributes 100× the cost, so the optimizer works hard to reduce it.

• The mean is not robust:

  • Its breakdown point is 0: one extreme value can move it arbitrarily far.

  • The shifted centroid then misassigns legitimate points near the cluster boundary.

• Forced assignment:

  • Every point must belong to some cluster; there is no noise label, so outliers can't be ignored.

  • Outliers can even capture a whole cluster of their own, wasting one of the k.

• Initialization: k-means++ favors far points, so outliers are likely to be picked as seeds.

• Remedies:

  • Detect and remove or cap outliers first; use robust scaling.

  • K-medoids (medoids, any distance) or k-medians (L1 loss) are more robust.

  • DBSCAN/HDBSCAN explicitly label noise.

Lloyd's algorithm alternates between assigning points to their nearest centroid and recomputing centroids as cluster means, repeating until assignments stop changing. Each step lowers the within-cluster sum of squares.

1. Initialize: Choose k initial centroids (random points or, better, k-means++).

2. Assignment step:

   • Assign each point to the centroid with the smallest squared Euclidean distance (a Voronoi partition).

   • Optimal for fixed centroids.

3. Update step:

   • Set each centroid to the mean of its assigned points.

   • Optimal for fixed assignments. Handle empty clusters (e.g. reseed with the farthest point).

4. Repeat until convergence: Stop when assignments don't change, centroid movement < tolerance, or max iterations reached.

• Properties:

  • Cost per iteration: O(n·k·d); usually converges in few iterations.

  • Guaranteed to converge (finite partitions, monotone objective) but only to a local minimum, so results depend on initialization.

Lloyd's algorithm only converges to a local minimum that depends on the starting centroids, so you run it several times from different seeds and keep the run with the lowest within-cluster sum of squares (inertia).

• Why restarts are needed:

  • The objective is non-convex; bad seeds can put two centroids in one true cluster and one centroid spanning two clusters.

  • Lloyd's steps can't escape that configuration since each step only decreases cost locally.

• How the final solution is chosen:

  • Compare runs by the objective itself (inertia), for the same k; pick the minimum.

  • In scikit-learn this is n_init: the best run's inertia_ is kept.

  • Inertia is valid here because k is fixed; it can't compare different k.

• Interaction with k-means++: Smarter seeding reduces the number of restarts needed but doesn't eliminate variance.

• Bonus diagnostic: if different runs give very different partitions with similar inertia, the cluster structure is weak or k is wrong.

Fit k-means for a range of k, plot within-cluster sum of squares (WCSS, or inertia) against k, and pick the "elbow": the k after which adding clusters gives sharply diminishing reductions in WCSS.

• Procedure:

  1. Scale features. k-means is distance-based, so unscaled features distort the clusters.

  2. For k = 1…K, run k-means with several restarts (n_init) and record inertia_.

  3. Plot WCSS vs k. Look for where the curve bends from steep to flat.

• Intuition:

  • Below the true k, each new cluster splits a real group and WCSS drops a lot.

  • Above it, new clusters just subdivide existing groups, so the gains are small.

• Making it less subjective: detect the knee automatically (Kneedle, kneed.KneeLocator), or use the point of maximum second difference.

• Cross-check with silhouette score, the gap statistic, or domain needs.

A silhouette value measures how much closer a point is to its own cluster than to the nearest other cluster. Near +1 means well assigned, near 0 means on a boundary, and near −1 means probably in the wrong cluster.

• Near +1:

  • a(i) ≪ b(i): the point is tight with its own cluster and far from the next one.

  • This is a confident, well-separated assignment.

• Near 0:

  • a(i) ≈ b(i): the point lies on or near the boundary between two clusters.

  • The assignment is ambiguous, which often signals overlapping clusters.

• Near −1:

  • a(i) > b(i): the point is closer, on average, to a neighboring cluster.

  • It is likely misassigned. Many such points suggest a wrong k or an unsuitable algorithm.

• Averaging over all points gives the overall score. As a rough guide, above ~0.5 is reasonable structure and below ~0.25 is weak structure.

Both build a hierarchy (dendrogram) of nested clusters but in opposite directions: agglomerative is bottom-up (start with singletons, repeatedly merge the closest pair), divisive is top-down (start with one cluster, repeatedly split).

• Agglomerative (AGNES):

  • Each step merges the two clusters with the smallest linkage distance: single, complete, average, or Ward.

  • Cost: naive O(n³), O(n²) time/memory with efficient implementations (SLINK, nearest-neighbor chain) and a distance matrix.

  • Decisions are local and greedy; early merges can't be undone.

  • By far the most common in practice (sklearn.cluster.AgglomerativeClustering, scipy.cluster.hierarchy.linkage).

• Divisive (DIANA):

  • Each step splits one cluster into two (e.g. DIANA's splinter group, or bisecting K-Means).

  • Exhaustive optimal splitting is exponential (2^(n−1) bipartitions), so heuristics are required.

  • Sees global structure first, so top-level splits can be more accurate; you can stop early if only a few clusters are needed.

• Choosing between them:

  • Need fine-grained structure or a full dendrogram on moderate n: agglomerative.

  • Care about the few top-level groups, or large n with bisecting K-Means: divisive.

  • Either way, cut the dendrogram at a height or cluster count to get a flat clustering.

The vertical axis of a dendrogram is the merge distance (dissimilarity), so you cut horizontally where there is a large vertical gap between successive merges: that gap means you would have to join clusters that are far apart, so the clusters below it are well separated.

• Reading the tree:

  • Leaves are observations; each horizontal bar is a merge drawn at the height (distance) where it happened.

  • Horizontal position of leaves is arbitrary. Similarity is read from merge height, not from how close two leaves sit on the x-axis.

  • A horizontal line at height h crosses k vertical branches, which gives k clusters.

• Choosing the cut:

  1. Largest-gap heuristic: find the longest vertical stretch with no merges and cut through it. This is the most stable k across a range of thresholds.

  2. Elbow on merge heights: plot the sorted merge distances and look for a sudden jump. This is the hierarchical analogue of the k-means elbow.

  3. Distance threshold: cut at a domain-meaningful distance, e.g. fcluster(Z, t, criterion='distance') in SciPy or distance_threshold in scikit-learn.

  4. Validate the candidate k values with internal metrics (silhouette) or with business usefulness.

• Caveats:

  • The heights depend on the linkage method. Ward produces exaggerated top-level gaps; single linkage produces compressed, chained trees.

  • A single flat cut assumes all clusters share a similar scale. Clusters of very different density may need non-uniform (dynamic) cuts.

The two methods define the distance between clusters differently:

• Single linkage uses the closest pair of points across the two clusters (min).

• Complete linkage uses the farthest pair (max).

So single linkage merges clusters that touch anywhere, while complete linkage merges them only when the whole union stays compact.

• Single linkage: d(A,B) = min d(a,b):

  • It can follow elongated or non-convex shapes, such as rings and spirals.

  • It suffers from chaining: noise points can bridge distinct clusters into one long cluster.

  • It is equivalent to building a minimum spanning tree and cutting its longest edges, which makes it efficient (O(n²)).

• Complete linkage: d(A,B) = max d(a,b):

  • It favors compact, roughly spherical clusters of similar diameter.

  • It resists chaining.

  • It is sensitive to outliers, because one far point inflates the distance.

  • It can split large natural clusters.

• Effect on the dendrogram:

  • Single linkage gives low, compressed merge heights with a skewed, staircase-like tree.

  • Complete linkage gives more balanced trees with clearer gaps.

• Rule of thumb:

  • Use single linkage for shape and connectivity-based structure in clean data.

  • Use complete linkage when you want tight, well-bounded groups.

Neither kind of point is a core point. The difference is whether a core point is nearby. A border point lies within eps of at least one core point, so it joins that cluster. A noise point is not within eps of any core point, so it belongs to no cluster.

• Core point (for context): Has at least min_samples points within eps. In scikit-learn this count includes the point itself.

• Border point:

  • Its own neighborhood is too sparse to be core, but it is density-reachable from a core point.

  • It gets a cluster label but cannot expand the cluster: no further points are reached through it.

  • If it is reachable from cores of two clusters, its assignment depends on processing order. This is DBSCAN's main source of nondeterminism.

• Noise point (outlier):

  • Not core, and not reachable from any core point.

  • Labeled -1 in scikit-learn's labels_.

• Both labels are sensitive to parameters. Increasing eps or lowering min_samples turns noise into border points, and border points into core points.

DBSCAN defines a cluster as a maximal set of density-connected points. It marks points with dense neighborhoods as core points, grows clusters by chaining core points that lie within eps of each other, attaches nearby sparse points as border points, and leaves the rest as noise.

• Two parameters define density:

  • eps: the neighborhood radius.

  • min_samples: the minimum number of points in that radius for a point to count as dense (core).

• Key relations:

  • Directly density-reachable: q is in the eps-neighborhood of core point p.

  • Density-reachable: there is a chain of core points leading from p to q.

  • Density-connected: p and q are both reachable from some common core point. Clusters are built from this relation.

• Algorithm:

  1. Pick an unvisited point and find its eps-neighbors.

  2. If it is not core, mark it noise for now. It may later become a border point.

  3. If it is core, start a new cluster and expand it breadth-first. Add all neighbors, and keep expanding through any neighbor that is itself core.

  4. Repeat until every point has been visited.

• Consequences:

  • There is no k to set, clusters can take arbitrary shapes, and outliers are detected natively.

  • A single global density threshold means it struggles when clusters have very different densities.

  • Runtime is about O(n log n) with a spatial index and O(n²) in the worst case or in high dimensions.

A Gaussian mixture model (GMM) is a probabilistic model that treats the data as generated by a weighted sum of K Gaussians: p(x) = Σₖ πₖ 𝒩(x | μₖ, Σₖ). It is usually fit with EM and gives soft cluster assignments plus a full density estimate.

• Generative story:

  • Pick a latent component z with probability πₖ, then draw x from 𝒩(μₖ, Σₖ).

  • The parameters are the mixing weights π (summing to 1), the means μₖ and the covariances Σₖ.

• Fitting:

  • Expectation-Maximization alternates two steps. The E-step computes responsibilities P(z=k | x). The M-step re-estimates π, μ and Σ.

  • Each iteration increases the likelihood, but EM converges only to a local optimum, so use multiple initializations (e.g. n_init).

• Compared with k-means:

  • GMM gives soft assignments and supports elliptical clusters of different sizes and orientations.

  • K-means is the limit of a GMM with equal spherical covariances shrinking to zero, which produces hard assignments.

• Covariance choices: In scikit-learn, covariance_type can be full, tied, diag or spherical. These trade flexibility against the number of parameters.

• Uses and caveats:

  • Uses: density estimation, anomaly detection (flag low likelihood), and soft clustering.

  • K must be chosen (AIC/BIC or a Bayesian GMM).

  • Covariances can collapse onto single points, making the likelihood unbounded. Regularize with reg_covar.

  • It assumes roughly Gaussian-shaped clusters.

One-hot vectors put every pair of distinct categories at the same distance (√2) and produce binary dimensions that k-means then averages. The resulting centroids are fractional, have no categorical meaning, and the distances carry little information.

• Distances become uninformative:

  • "red" vs "blue" is just as far apart as "red" vs "crimson", so there is no notion of graded similarity.

  • With several categorical columns, distances collapse into a few discrete values, producing many ties and unstable assignments.

• Centroids are meaningless: The mean of one-hot vectors is something like [0.4, 0.6, 0]. That is a proportion, not a category, and squared error to it does not reflect real category mismatch.

• Weighting distortions: High-cardinality features add many dimensions. Mixed with scaled numeric features, binary columns weigh in arbitrarily relative to the numeric ones.

• Better alternatives:

  • k-modes: uses Hamming mismatch and modes as centers, suited to purely categorical data.

  • k-prototypes: handles mixed numeric and categorical data.

  • Gower distance with k-medoids or hierarchical clustering.

  • Learned embeddings, or target/frequency encodings when categories have meaningful similarity.

The metric defines what "similar" means, so it directly shapes the clusters. Euclidean favors compact, round groups. Manhattan measures axis-wise differences and is more robust to large single-feature deviations. Cosine ignores magnitude and groups points by direction.

• Euclidean (L2):

  • Straight-line distance. Squaring large differences makes it sensitive to outliers.

  • It is the metric k-means implicitly optimizes, giving spherical, convex clusters.

• Manhattan (L1):

  • Sum of absolute differences. Neighborhoods are diamond-shaped (axis-aligned).

  • Less dominated by one extreme feature, and somewhat better behaved in higher dimensions.

  • The natural center is the median, so pair it with k-medians or k-medoids.

• Cosine:

  • Measures the angle between vectors, so [1,2] and [10,20] are identical.

  • Ideal for text (TF-IDF), embeddings, and user-behavior profiles, where length reflects volume rather than meaning.

  • Spherical k-means is ordinary k-means on L2-normalized vectors (normalized Euclidean is monotonic with cosine).

• Practical implications:

  • The algorithm must match the metric: standard k-means assumes Euclidean, while k-medoids, DBSCAN, and agglomerative clustering accept arbitrary metrics.

  • Other options: Mahalanobis for correlated features, Hamming/Jaccard for binary or set data, Gower for mixed data.

In high dimensions, distances concentrate: the nearest and farthest neighbors of a point end up nearly the same distance away. "Close" versus "far" loses meaning, and algorithms that group by distance lose their signal. This is a core part of the curse of dimensionality.

• Distance concentration:

  • For many distributions, (max dist − min dist) / min dist → 0 as dimensions grow, so contrast vanishes.

  • Squared distance sums many per-dimension terms, so the variance relative to the mean shrinks.

• Sparsity: Volume grows exponentially, so data becomes sparse. Density estimates (DBSCAN's eps neighborhoods) become empty or include everything.

• Irrelevant features add noise: When only a few dimensions carry cluster structure, the many noisy ones swamp them in the distance sum.

• Mitigations:

  • Dimensionality reduction (PCA, or UMAP before HDBSCAN) and feature selection.

  • Better-suited metrics: cosine on normalized embeddings, or L1 over L2.

  • Subspace or projected clustering (CLIQUE, PROCLUS), or model-based methods with regularized covariances.

Use either a distance that handles mixed types natively (Gower distance with a medoid or hierarchical method) or an algorithm built for mixed data (k-prototypes), rather than one-hot encoding everything and running plain k-means.

• Why naive k-means fails:

  • One-hot columns are 0/1, so Euclidean distance and centroid means become hard to interpret (a mean of 0.3 for "is_red" isn't a category).

  • High-cardinality categoricals blow up dimensionality and dominate or vanish depending on scaling.

• Option 1: Gower distance + distance-based clustering:

  • Numeric: range-normalized absolute difference; categorical: 0/1 mismatch; average across features (optionally weighted).

  • Feed the precomputed matrix to k-medoids (PAM), hierarchical clustering, or DBSCAN with metric='precomputed'.

  • Cost: O(n²) memory, so it suits small to medium datasets.

• Option 2: k-prototypes:

  • Combines k-means (means, squared distance) on numeric features with k-modes (modes, mismatch count) on categoricals.

  • A weight γ balances the two parts: tuning it matters.

  • Scales linearly; available in the kmodes Python package.

• Option 3: encode then cluster:

  • FAMD (PCA for mixed data) or learned embeddings/autoencoders map everything to a continuous space, then use k-means or GMM.

  • Option 4: model-based approaches (latent class / mixture models with per-type likelihoods).

• Practical concerns:

  • Scale numeric features so they don't dominate; decide feature weights deliberately.

  • Validate with silhouette on the same distance, plus cluster profiling for business sense.

K-means++ picks the first center uniformly at random, then picks each next center with probability proportional to its squared distance from the nearest already-chosen center. This spreads seeds out and gives an expected O(log k) approximation to the optimal k-means cost.

1. Choose the first center uniformly at random from the data points.

2. For each point x, compute D(x): distance to the nearest chosen center.

3. Sample the next center with probability D(x)² / Σ D(x)².

4. Repeat steps 2–3 until k centers are chosen, then run standard Lloyd iterations.

• Why D² sampling: Far-away regions (likely uncovered clusters) are favored, but it's randomized, so it doesn't always pick the single farthest point (which would be an outlier).

• Practical notes:

  • Seeding costs O(n·k·d); scikit-learn's init='k-means++' is the default and adds greedy trials per step.

  • Still somewhat sensitive to outliers; k-means|| is a parallel variant for large data.

The k-means objective (within-cluster sum of squares) is non-convex with many local minima. Lloyd's algorithm is a greedy coordinate descent: each step only lowers the cost from where it currently is, so it stops at the first fixed point it reaches. Which fixed point that is depends on the initialization.

• The objective is non-convex:

  • It jointly optimizes discrete assignments and continuous centroids. The assignment space is combinatorial (about k^n partitions).

  • Finding the global optimum is NP-hard, even for k=2 in general dimension or for 2-D data with general k.

• Lloyd's steps are locally greedy:

  1. The assignment step is optimal for fixed centroids.

  2. The update step (mean) is optimal for fixed assignments.

  3. Alternating these never increases the cost, but it cannot escape a configuration where neither step helps. Example: two centroids sharing one true cluster while another centroid covers two true clusters.

• The result depends on initialization: Different seeds converge to different partitions with different inertia.

• Mitigations:

  • Use k-means++ seeding.

  • Run multiple restarts (n_init in scikit-learn) and keep the run with the lowest inertia.

  • These improve the odds of a good solution but do not guarantee the global optimum.

K-means implicitly assumes clusters are roughly spherical (isotropic), similar in size, and similar in density or spread. It assigns each point to the nearest centroid under Euclidean distance, so every cluster boundary is a straight hyperplane equidistant between centroids.

• Shape: spherical and convex:

  • Euclidean distance to a mean treats every direction equally, so elongated, curved, or ring-shaped clusters get cut incorrectly.

  • The partition is a Voronoi diagram, so each cluster is a convex cell.

• Size: similar extent and point counts:

  • Boundaries sit halfway between centroids. A large, wide cluster therefore "loses" its edge points to a small neighboring one.

  • Minimizing SSE also favors splitting big clusters rather than respecting small ones.

• Density/variance: similar spread: There is no per-cluster variance term. A tight cluster next to a diffuse one gets a boundary in the wrong place.

• Probabilistic view: K-means is the hard-assignment limit of a Gaussian mixture with equal, shared spherical covariance σ²I and (implicitly) equal mixing weights.

• Other implicit assumptions:

  • Features are on comparable scales, so you should standardize first.

  • There are no heavy outliers, since means are sensitive to them.

  • k is known in advance.

• When these assumptions break, consider alternatives:

  • GMM with full covariance for elliptical or unequal clusters.

  • DBSCAN/HDBSCAN for arbitrary shapes and varying density.

  • Spectral clustering for non-convex shapes.

Each Lloyd iteration costs O(n·k·d), where n is the number of points, k the number of clusters, and d the dimensionality. The assignment step dominates this cost. Total runtime is O(n·k·d·i) for i iterations.

• Assignment step: O(nkd): For each of n points, compute the distance to each of k centroids. Each distance costs O(d).

• Update step: O(nd): Each point contributes once to its centroid's sum, followed by k divisions.

• Memory: O((n+k)d)

• Iteration count:

  • In practice i is usually small (tens).

  • In the worst case it can be superpolynomial (2^Ω(√n)), so implementations cap max_iter.

• Speedups:

  • Elkan's algorithm uses the triangle inequality to skip distance computations.

  • Mini-batch k-means costs O(b·k·d) per step for batch size b.

  • Initialization with k-means++ costs O(nkd) once.

K-means assigns each point to its nearest centroid, so every cluster is a convex Voronoi cell separated by linear boundaries. Non-convex shapes (moons) and concentric rings cannot be represented as convex cells around a single center. Minimizing squared distance to a mean therefore slices them geometrically instead of following their structure.

• Convex-cell limitation: The boundary between two centroids is the perpendicular bisector hyperplane. The intersection of such half-spaces is always convex.

• Concentric rings:

  • Both rings share roughly the same mean (the center), so a centroid cannot distinguish them.

  • K-means instead splits the plane into wedges or halves, each containing parts of both rings.

• Interleaved moons: The tips of one moon lie closer to the other moon's centroid, so they are misassigned.

• Objective mismatch: SSE rewards compactness around a point, not connectivity. The "correct" partition can have higher SSE than a wrong straight cut.

• Fixes:

  • Density-based methods (DBSCAN/HDBSCAN) follow connected dense regions.

  • Spectral clustering embeds a similarity graph so rings and moons become separable, then runs k-means in that space.

  • Kernel k-means or feature transforms help too: for rings, using the radius r=√(x²+y²) makes them linearly separable.

  • Single-linkage hierarchical clustering also follows chained structure.

An empty cluster has no points, so its mean is undefined. The standard fix is to re-seed that centroid somewhere useful, typically at a point that is currently poorly served, and then continue iterating.

• Re-seeding strategies:

  1. Farthest point: move the centroid to the point with the largest distance to its assigned centroid. This also reduces SSE the most locally (scikit-learn's approach).

  2. Split the largest or highest-SSE cluster: place the centroid at a point (or a perturbation of the centroid) from the cluster contributing most to error.

  3. Random data point: simple, but may land in a dense region and empty again.

• Other options:

  • Keep the old centroid unchanged. This is simple, but the centroid may stay dead.

  • Drop the cluster and continue with k−1, if k is not strict.

  • Restart with a different initialization.

• Prevention:

  • Use k-means++ initialization, which spreads seeds across the data.

  • Initialize centroids from actual data points, not random coordinates.

  • Remove extreme outliers and duplicates.

  • Reconsider k: frequent empty clusters suggest k is too large for the data.

k-modes keeps the k-means loop (assign points, update centers, repeat) but swaps out the two pieces that need numbers: Euclidean distance becomes a simple matching dissimilarity, and the mean becomes the per-attribute mode.

• Distance: simple matching (Hamming-style):

  • d(x, y) is the number of attributes where x and y disagree, so no arbitrary numeric encoding of categories is needed.

  • Averaging one-hot vectors would produce meaningless fractional "centroids" and distances that depend on the encoding.

• Center update: the mode:

  • For each attribute, the center takes the most frequent category among its members.

  • The mode exactly minimizes total matching dissimilarity, just as the mean minimizes squared Euclidean distance. So the cost never increases and the algorithm converges to a local optimum.

• Practical issues:

  • Sensitive to initialization: use frequency-based schemes (Huang, Cao) and several restarts.

  • Ties in modes and in assignments are common, so results can be unstable.

  • Every mismatch counts equally, so rare categories get no special weight.

• Mixed data: k-prototypes combines k-means cost on numeric features with k-modes cost on categorical features, balanced by a weight γ.

Mini-Batch K-Means trades a small loss in clustering quality (somewhat higher inertia, noisier centroids) for large gains in speed and memory, because each update uses a small random batch instead of the full dataset.

• What you gain:

  • Per-iteration cost is O(b·k·d) instead of O(n·k·d), which is often orders of magnitude faster on large n.

  • Low memory use, and it supports streaming or online learning (partial_fit).

• What you lose:

  • Updates are stochastic, so centroids jitter and settle near, rather than exactly at, a Lloyd fixed point. Inertia is typically slightly worse.

  • Results depend more on random seed and batch order.

  • Small or rare clusters may be under-sampled, which can produce poor or empty centers.

• Knobs: a larger batch_size improves quality but reduces the speedup. reassignment_ratio handles dead centers.

• Rule of thumb: use it when n is large enough that full k-means is too slow or the data doesn't fit in memory.

Choose k-medoids when you need robustness to outliers, a non-Euclidean or custom dissimilarity, or cluster centers that are real, interpretable data points. Accept that it is much more expensive than k-means.

• Outliers and noise: A mean is dragged by extreme points. A medoid must be an actual member that minimizes total (usually unsquared) distance, so it behaves more like a median.

• Arbitrary distances:

  • It works with Manhattan, Gower (mixed types), edit distance, DTW for time series, or a precomputed dissimilarity matrix.

  • k-means is only principled with squared Euclidean distance.

• Interpretability: Each center is a real exemplar (a real customer, document, or trajectory), not an average that may be impossible, such as 2.3 children.

• When to stay with k-means:

  • Large n: PAM is roughly O(n²) or worse per iteration and needs pairwise distances. Use CLARA, CLARANS, or FasterPAM if you need medoids at scale.

  • Clean, numeric, roughly spherical clusters, where k-means is faster and works well.

k-means' update step relies on the fact that the arithmetic mean minimizes the sum of squared Euclidean distances. k-medoids instead selects centers from the data points themselves, so it only ever needs pairwise dissimilarities. That works for any metric.

• Why k-means is tied to squared Euclidean distance:

  • Both steps (assign to nearest center, recompute the mean) decrease the same objective only when the distance is squared Euclidean. This generalizes to Bregman divergences.

  • With other metrics (L1, cosine, edit distance) the mean is no longer the minimizer. The update can increase the cost, and convergence is no longer guaranteed. For L1 the right center is the median, giving k-medians.

  • For non-vector data (strings, graphs, sets) a "mean" may not even exist in the space.

• Why k-medoids is metric-agnostic:

  • The center update is a discrete search: pick the member (or swap) that minimizes the total dissimilarity d(x, m).

  • Each accepted step lowers the cost for any dissimilarity function, so it converges. It doesn't even strictly need the triangle inequality.

  • It can therefore run directly on a precomputed distance matrix.

• Cost of this flexibility: the search over candidate medoids is far more expensive than computing a mean.

Standard K-Means recomputes each centroid as the exact mean of all its assigned points every iteration. Mini-Batch K-Means draws a small random batch, assigns only those points, and nudges each centroid toward them with a per-centroid learning rate that decays as the centroid accumulates points.

• Batch (Lloyd) update: Assign all n points, then set c_j = mean of the points in cluster j. This is deterministic given the assignments, and each pass is O(nkd).

• Mini-batch update (Sculley, 2010):

  1. Sample b points and assign each to its nearest current centroid.

  2. For each point x assigned to j: increment the count n_j, set η = 1/n_j, and update c_j ← (1 − η)·c_j + η·x.

  3. Repeat for many batches until centroid change or inertia stabilizes.

• Interpretation:

  • This is a running average over every point the centroid has ever seen, equivalent to SGD on the k-means objective.

  • Early batches move centroids a lot. As counts grow, updates shrink, which stabilizes convergence.

The elbow method is a visual heuristic on a curve that always decreases. On real data the bend is often ambiguous or absent, and the method inherits all of k-means' assumptions, so it should be one signal among several, not the deciding rule.

• Ambiguity and subjectivity:

  • WCSS decreases monotonically (reaching 0 at k = n), so there is no true minimum to find.

  • Smooth curves with no clear elbow are common, and different people will pick different k.

• Inherits k-means assumptions:

  • It favors spherical, similarly sized, similar-density clusters. It misleads on elongated, nested, or imbalanced structure.

  • It is sensitive to feature scaling, outliers, and dimensionality, since distances concentrate in high dimensions.

• No statistical grounding:

  • It can't say "there are no clusters" (k = 1), and it doesn't compare against a null reference distribution.

  • Random initialization adds noise to the curve unless you use multiple restarts.

• Better complements:

  • Silhouette score and Davies–Bouldin index (both account for separation).

  • Gap statistic: compares WCSS to a uniform reference.

  • BIC/AIC with Gaussian mixtures, and stability under resampling.

  • Business or domain usefulness of the resulting segments.

A silhouette plot shows every point's silhouette value, grouped by cluster and sorted, next to a line for the overall average. A wrong k shows up as clusters that fall short of the average, contain many negative values, or have badly uneven sizes and shapes.

• How to read the plot:

  • Each cluster appears as a "knife" shape. Its width (thickness) is the cluster size, and its length is how high the per-point silhouettes go.

  • A dashed vertical line marks the mean silhouette across all points.

• Warning signs of a bad k:

  • Whole clusters sit below the average line: those clusters are weakly separated.

  • Many negative values: those points are closer to a neighboring cluster than to their own, so they are likely misassigned.

  • Highly uneven thickness or sharply tapering knives: the partition doesn't match the real structure.

• Diagnosing the direction of the error:

  • k too small: one very thick cluster with a long low tail. Two true groups have been merged, so internal distance a(i) is inflated.

  • k too large: several thin clusters with low or negative scores. A true group has been split, so the nearest-cluster distance b(i) is small.

• Practice: draw the plot for several k values. Prefer the k where all clusters pass the average line with similar, mostly positive profiles, not just the k with the highest mean score.

The plain Rand index isn't corrected for chance: even random labelings score high, and that baseline shifts with the number and size of clusters. ARI subtracts the expected score under random labeling, so 0 means "no better than chance" and scores are comparable across settings.

• Problem with the Rand index:

  • RI = fraction of point pairs on which two labelings agree (same/same or different/different).

  • With many clusters, most pairs are "different" in both labelings, so agreement is high by default. Random partitions can reach RI ≈ 0.8–0.9.

  • Because the baseline depends on k and cluster sizes, comparing RI across different k is misleading.

• The adjustment:

  • ARI = (RI − E[RI]) / (max RI − E[RI]).

  • The expectation comes from a permutation (hypergeometric) model with the cluster sizes held fixed.

• Resulting properties:

  • 1 means a perfect match.

  • ≈ 0 means a random labeling, regardless of k.

  • Negative means worse than chance.

  • Symmetric and invariant to label permutation (sklearn.metrics.adjusted_rand_score).

• Caveat: it needs ground-truth labels, so it is an external metric and cannot be used for unlabeled model selection.

The Calinski-Harabasz (variance ratio) index measures how well separated clusters are relative to how compact they are. It is the ratio of between-cluster dispersion to within-cluster dispersion, adjusted for degrees of freedom, and higher is better.

• Formula:

  • CH = [tr(B) / (k − 1)] / [tr(W) / (n − k)].

  • tr(B): size-weighted squared distances of cluster centroids from the global centroid.

  • tr(W): sum of squared distances of points to their own centroid.

• Interpretation:

  • It is analogous to an ANOVA F-statistic: large values mean dense, well-separated clusters.

  • To choose k, compare CH across candidate values and look for a peak.

• Pros:

  • Very fast: O(n·d), with no pairwise distances.

  • Needs no labels (sklearn.metrics.calinski_harabasz_score).

• Cons:

  • Centroid- and variance-based, so it favors convex, spherical clusters (k-means-like).

  • Misleading for density-based or irregularly shaped clusters.

  • Undefined for k = 1.

For point i, compare a(i), its mean distance to its own cluster, with b(i), its mean distance to the nearest other cluster. Then compute s(i) = (b(i) − a(i)) / max(a(i), b(i)).

1. Cohesion a(i): The average distance from i to all other points in its own cluster.

2. Separation b(i):

   • For each other cluster, compute the average distance from i to its points.

   • Take the minimum: that cluster is i's "neighboring" cluster.

3. Combine:

   • s(i) = (b − a) / max(a, b), which always falls in [−1, 1].

   • Example: a = 2, b = 8 gives s = 6/8 = 0.75.

• Details:

  • By convention, s(i) = 0 if i is alone in its cluster.

  • Any distance metric works.

  • Cost is O(n²) because it needs pairwise distances.

  • silhouette_samples returns per-point values, and silhouette_score returns their mean.

The Davies-Bouldin index scores each cluster against its most similar cluster, where similarity is combined spread divided by centroid distance. It then averages these worst-case ratios, so lower is better and 0 is ideal.

1. Scatter Si: The average distance of cluster i's points to its centroid.

2. Separation Mij: The distance between the centroids of clusters i and j.

3. Similarity Rij = (Si + Sj) / Mij: High when two clusters are wide and close together, i.e. when they overlap.

4. DB = (1/k) Σi maxj≠i Rij: Each cluster is judged against its worst neighbor, and the results are averaged.

• Pros:

  • Cheap, because it uses centroids only.

  • Needs no labels (sklearn.metrics.davies_bouldin_score).

• Cons:

  • Assumes convex, centroid-represented clusters, so it is poor for DBSCAN-style shapes.

  • Sensitive to the distance metric and to feature scaling.

Internal metrics score a clustering using only the data and the cluster assignments (compactness vs. separation). External metrics compare the assignments against known ground-truth labels. Use internal metrics when no labels exist; use external metrics for benchmarking against a labeled reference.

• Internal metrics:

  • Examples: silhouette, Davies-Bouldin, Calinski-Harabasz, within-cluster SSE.

  • Measure geometric quality: points close to their own cluster and far from others.

  • Bias: they encode an assumption of what a "good" cluster is (usually convex, distance-based), so they can reward the wrong structure.

• External metrics:

  • Examples: Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), V-measure, purity, Fowlkes-Mallows.

  • Measure agreement between the partition and the labels, invariant to cluster ID permutation.

  • Limitation: labels are rarely available in real clustering problems, and labels may reflect only one of several valid groupings.

• Related: relative/stability evaluation: Compare runs with different k or algorithms, or check consistency under resampling, when neither labels nor a trusted geometric criterion exist.

• In practice: combine internal metrics with domain validation (do the clusters mean something actionable?).

NMI measures how much information the cluster assignment shares with the true labels, normalized to [0, 1]: 1 means the clustering perfectly determines the labels (up to renaming), 0 means they are independent.

• Mutual information I(C; Y):

  • Built from the contingency table of clusters C vs. classes Y: I = H(Y) − H(Y|C).

  • It is the reduction in uncertainty about the true class once you know the cluster.

• Normalization:

  • Raw MI grows with the number of clusters and has no fixed upper bound, so divide by a mean of entropies: e.g. arithmetic mean (H(C)+H(Y))/2, geometric sqrt(H(C)H(Y)), or max.

  • With the arithmetic mean, NMI equals V-measure.

• Properties:

  • Invariant to label permutation; allows different numbers of clusters and classes.

  • Not adjusted for chance: random clusterings with many clusters still get NMI > 0, so prefer adjusted_mutual_info_score (AMI) when k is large or varies.

V-measure is the harmonic mean of homogeneity and completeness, two entropy-based scores that pull in opposite directions, so it is high only when both are high.

• Homogeneity h: each cluster contains only one class:

  • h = 1 − H(Y|C) / H(Y).

  • Trivially maximized by putting every point in its own cluster.

• Completeness c: all members of a class land in one cluster:

  • c = 1 − H(C|Y) / H(C).

  • Trivially maximized by putting everything in one cluster.

• Combination:

  • V = (1+β)·h·c / (β·h + c); with β = 1 it's the plain harmonic mean 2hc/(h+c).

  • Harmonic mean punishes imbalance, so neither degenerate solution scores well.

  • β > 1 weights completeness more; β < 1 weights homogeneity more.

• Notes:

  • Equivalent to NMI with arithmetic-mean normalization.

  • Not chance-adjusted: inflated for many small clusters. sklearn: homogeneity_completeness_v_measure.

Purity only checks that each cluster is dominated by one class; it never penalizes splitting a class into many clusters. So as k approaches n, every cluster becomes a singleton, which is trivially 100% pure, and purity hits 1.0 for a useless clustering.

• Definition:

  • Purity = (1/n) Σ over clusters of max_class |cluster ∩ class|.

  • Each cluster is credited with its majority-class count.

• Why it breaks:

  • Smaller clusters are more likely to be pure, so purity increases monotonically (in tendency) with k.

  • It measures homogeneity only; there is no completeness term for keeping a class together.

  • So it cannot be used to compare clusterings with different k.

• Better alternatives:

  • Metrics balancing both sides: V-measure, NMI, F-measure.

  • Chance-adjusted metrics: ARI, AMI, which score near 0 for trivial/random partitions.

Chaining is when single linkage merges two clearly distinct clusters because a thin sequence of intermediate points links them. Each step in that chain is short, so the result is a long, straggly cluster rather than compact groups.

• Why it happens:

  • Single linkage uses the minimum pairwise distance, so a single close pair is enough to merge two clusters.

  • The overall spread of the clusters is ignored.

  • A few noise or bridge points between dense groups act as stepping stones.

• Symptoms:

  • One giant cluster absorbs most points, while many tiny or singleton clusters remain.

  • The dendrogram looks like a staircase: points join one at a time at low heights, with no clear gaps.

• Upside: The same property lets single linkage recover elongated or non-convex shapes when the data is clean.

• Mitigations:

  • Use complete, average or Ward linkage instead.

  • Remove outliers before clustering.

  • Use density-aware methods (DBSCAN, HDBSCAN). HDBSCAN is essentially robust single linkage built on mutual reachability distance.

Standard agglomerative clustering needs the full pairwise distance matrix, which is O(n²) memory. It also repeatedly searches and updates that matrix, which costs O(n²) to O(n³) time. Both explode beyond tens of thousands of points.

• Memory:

  • n(n−1)/2 distances are stored.

  • 100k points means about 5×10⁹ entries, roughly 40 GB in float64.

• Time:

  • A naive implementation does n−1 merges, each scanning O(n²) pairs, so O(n³) in total.

  • Priority queues or the nearest-neighbor-chain algorithm bring this to O(n² log n) or O(n²).

  • SLINK reaches O(n²) for single linkage. Even that remains quadratic.

• Greedy and non-revisable:

  • Every merge is final, so the full hierarchy must be built.

  • Unlike k-means, there is no cheap mini-batch or streaming update.

• Workarounds:

  • Use a sparse connectivity graph (k-NN graph via connectivity in scikit-learn's AgglomerativeClustering) so only neighbors are considered.

  • Pre-cluster first, then run hierarchical clustering on the summaries: BIRCH (CF-tree), or k-means with many centroids.

  • Sample the data, build the tree, then assign the remaining points to the nearest cluster.

  • Use HDBSCAN, which uses spatial indexes and an MST.

The two criteria differ in what they measure:

• Average linkage merges the pair of clusters with the smallest mean pairwise distance between their points.

• Ward's linkage merges the pair whose union causes the smallest increase in total within-cluster sum of squares (variance).

Average linkage is a distance-based compromise between single and complete linkage. Ward is an objective-based criterion, like greedy k-means.

• Average linkage (UPGMA):

  • d(A,B) = (1/|A||B|) Σ d(a,b).

  • Works with any dissimilarity (cosine, Manhattan, a precomputed matrix).

  • Moderately robust to outliers. It avoids chaining but is less strict than complete linkage.

  • Can produce clusters of uneven size.

• Ward's linkage:

  • Merge cost = (|A||B| / (|A|+|B|)) · ‖μ_A − μ_B‖².

  • It relies on centroids and squared Euclidean distance, so it is only valid with Euclidean geometry.

  • Produces compact, spherical, similarly sized clusters.

  • The size factor penalizes merging large clusters, which tends to give clean, balanced dendrograms.

• When to use which:

  • Ward is the default for numeric, scaled features when you expect k-means-like blobs.

  • Average linkage suits non-Euclidean metrics (text with cosine, gene expression with correlation).

Complete linkage tends to produce compact, roughly spherical (convex) clusters of similar diameter. It merges only when every point in the combined cluster is within the merge distance of every other point.

• Why:

  • The cluster distance is the maximum pairwise distance, so each merge bounds the diameter of the new cluster.

  • Elongated clusters are penalized because their far ends are distant.

• Consequences:

  • Tight, well-separated groups with no chaining.

  • Tends to split large or elongated natural clusters into several pieces.

  • Fails on non-convex shapes (moons, rings).

  • Sensitive to outliers: one far point inflates the max distance and can delay or distort merges.

• Contrast:

  • Single linkage gives stringy, chained shapes.

  • Ward also gives compact blobs, but it balances variance rather than diameter.

Ward minimizes the increase in within-cluster sum of squared deviations from centroids. Centroids and variance decomposition are only meaningful in Euclidean space, so its merge cost and the Lance–Williams update it relies on assume squared Euclidean distances.

• The objective is Euclidean by construction:

  • The merge cost is (|A||B|/(|A|+|B|))·‖μ_A − μ_B‖².

  • It requires a mean (centroid) that minimizes squared distances. This holds for the Euclidean norm, not for Manhattan or cosine.

• Variance decomposition:

  • Total SS = within-cluster SS + between-cluster SS. This identity (König–Huygens) holds only for squared Euclidean distance.

  • With other metrics the merge cost no longer equals an increase in any well-defined error.

• The update formula breaks:

  • The Lance–Williams update for Ward computes new distances from old ones.

  • With non-Euclidean input it can yield inconsistent results, such as non-monotone merge heights (inversions in the dendrogram).

• In practice:

  • scikit-learn's AgglomerativeClustering(linkage='ward') only accepts metric='euclidean'.

  • SciPy's linkage(method='ward') assumes Euclidean distances.

  • For other metrics use average or complete linkage, or embed the data into a Euclidean space first (e.g. L2-normalize vectors so Euclidean distance tracks cosine).

Mean shift treats the data as samples from a density, estimated with a kernel density estimate (KDE). It moves each point uphill to a local maximum (mode) of that density. Points that converge to the same mode form one cluster, so the number of clusters equals the number of modes. That number is controlled by the kernel bandwidth, not by a preset k.

• The shift step:

  • For the current position x, compute the kernel-weighted mean of the points in its window: m(x) = Σ K(xᵢ−x)·xᵢ / Σ K(xᵢ−x).

  • The mean-shift vector m(x) − x points along the gradient of the KDE. Move x to m(x).

  • Repeat until the shift is negligible. This is gradient ascent with an adaptive step size.

• Forming clusters:

  1. Run the procedure from every point, or from seeds such as binned points.

  2. Merge converged positions that lie within about one bandwidth of each other. These merged positions are the cluster centers.

  3. Assign each point to the mode it converged to, or to the nearest center.

• Bandwidth replaces k:

  • A small bandwidth gives a bumpy density with many modes and many clusters. A large bandwidth gives a smooth density with few clusters.

  • scikit-learn's estimate_bandwidth picks it from quantiles of nearest-neighbor distances.

• Trade-offs: mean shift finds non-spherical clusters and is robust to outliers, but it costs about O(n²) per iteration and degrades in high dimensions, where KDE is unreliable.

For every point, compute the distance to its k-th nearest neighbor, with k tied to min_samples. Sort these distances and plot them. Points inside clusters have small, slowly rising k-distances, while noise points have large ones. Set eps at the "knee", where the curve bends sharply upward.

• Steps:

  1. Choose min_samples first, since k should match it.

  2. Compute each point's k-NN distance.

  3. Sort the distances in ascending order and plot them against point index.

  4. Read the y-value at the elbow or knee and use it as eps.

• Why it works: With eps at the knee, points to the left have k neighbors within eps and become core points. Points past the knee sit in sparse regions and become noise.

• Practical details:

  • scikit-learn's NearestNeighbors returns the point itself as its first neighbor when you query the training data. Query n_neighbors=min_samples and take the last column so the count matches DBSCAN's definition, which includes the point itself.

  • The knee is subjective. A tool such as kneed can locate it automatically. Validate a few candidate values with silhouette score, the noise fraction, or domain inspection.

  • Several knees suggest clusters of different densities, where one global eps won't fit. Consider OPTICS or HDBSCAN.

  • Scale features first, because eps is a distance.

DBSCAN produces a flat clustering for one fixed density threshold (eps). OPTICS generalizes it by ordering the points so the density structure is captured for all eps values up to a maximum. Clusters of varying density can then be extracted from a single run.

• DBSCAN:

  • Parameters are eps and min_samples. The output is labels plus noise.

  • One global density threshold means sparse clusters become noise or dense neighboring clusters merge when densities differ.

  • It is fast and simple, but results are sensitive to eps.

• OPTICS (Ordering Points To Identify the Clustering Structure):

  • Core distance: the smallest radius at which a point becomes core, which is the distance to its min_samples-th neighbor.

  • Reachability distance of p from o: max(core_dist(o), d(o,p)).

  • It visits points in order of smallest reachability and records that value for each point, producing a reachability plot. Valleys in the plot are clusters, and the depth of a valley reflects the cluster's density.

  • Clusters are extracted by a horizontal cut, which is equivalent to DBSCAN at that eps (cluster_method='dbscan'), or by the steepness-based xi method. The xi method handles varying density and gives hierarchical structure.

  • max_eps only bounds the search, and its default is infinity. It is not a sensitive clustering parameter.

• Trade-offs:

  • OPTICS is more robust to parameter choice and reveals hierarchy, but it is slower in practice and its output needs an extraction step to become flat labels.

  • HDBSCAN is a related modern alternative that also handles varying density and selects stable clusters automatically.

DBSCAN wins when clusters are defined by dense, connected regions rather than by distance to a centroid. Typical cases are non-convex shapes, data with noise or outliers, and situations where the number of clusters is unknown, provided the clusters have similar density and the data is low-dimensional.

• Arbitrary or non-convex shapes: Examples include moons, rings, elongated or snake-like regions. k-means assumes convex, roughly spherical clusters that split space into Voronoi cells, so it cuts these shapes apart.

• Noise and outliers: DBSCAN labels sparse points as noise (-1). k-means forces every point into a cluster, and outliers drag the centroids.

• Unknown number of clusters: k emerges from the density structure, so there is no need for elbow or silhouette searches over k.

• Uneven cluster sizes: k-means tends to equalize cluster sizes and splits large clusters. DBSCAN does not care about size.

• Spatial and geographic data: Examples are GPS hotspots and points of interest. DBSCAN supports any metric (for example metric='haversine'), whereas k-means is tied to Euclidean means.

• Where k-means still wins:

  • Clusters with very different densities, where one eps fails (use HDBSCAN instead).

  • High-dimensional data, where distances concentrate and density loses meaning.

  • Very large datasets that need a cheap, scalable algorithm (MiniBatch k-means), and tasks that need centroids, for example vector quantization.

min_samples sets how many points (including the point itself in scikit-learn) must fall within eps for a point to be core. Pick it first, using dimensionality, noise level, and the smallest cluster size you care about. Then tune eps for it with a k-distance plot.

• Rules of thumb:

  • Use min_samples ≥ D + 1, where D is the number of dimensions.

  • A common default is min_samples = 2·D (Sander et al.). The original paper used 4 for 2-D data.

  • Use larger values for large, noisy, or high-dimensional datasets.

• What changing it does:

  • Higher values mean a stricter density requirement, more noise points, fewer and denser clusters, and more robustness to spurious clusters.

  • Lower values mean more clusters and less noise. At 1 or 2, every point is core and DBSCAN degenerates to single linkage cut at eps, which brings chaining.

• Domain view: Set it near the minimum group size that is meaningful, for example the number of visits needed to call a location a hotspot.

• Tune it jointly with eps:

  • The two parameters are coupled. Redraw the k-distance plot with k equal to the new min_samples whenever you change it.

  • Check the outcome through the noise fraction, the number of clusters, cluster stability across nearby values, and silhouette or DBCV scores.

The E-step computes responsibilities. Holding the current parameters fixed, it finds the posterior probability that each component k generated each point xᵢ: a soft assignment of every point to every component.

• Formula (Bayes' rule):

  • γᵢₖ = πₖ 𝒩(xᵢ | μₖ, Σₖ) / Σⱼ πⱼ 𝒩(xᵢ | μⱼ, Σⱼ)

  • Each row of γ sums to 1.

• Interpretation:

  • γ is the expected value of the latent indicator zᵢₖ. It fills in the missing cluster labels in expectation.

  • Nₖ = Σᵢ γᵢₖ is the effective number of points in component k. The M-step uses it.

  • γ defines the expected complete-data log-likelihood (the Q function) that the M-step maximizes.

• Numerics:

  • Compute in log space with logsumexp to avoid underflow in high dimensions.

  • The log-normalizer, summed over points, is the log-likelihood. It is used for the convergence check.

• Contrast with k-means: there the assignment step is hard, setting γ to 1 for the nearest centroid and 0 otherwise.

Fit GMMs over a range of K, compute each model's AIC or BIC, and pick the K with the lowest value. Both criteria reward likelihood but penalize the number of free parameters, which guards against simply adding components until the data is overfit.

• Definitions (lower is better):

  • AIC = 2p − 2 ln L̂

  • BIC = p ln n − 2 ln L̂

  • Here p is the number of free parameters, n the number of samples, and L̂ the maximized likelihood.

• Counting p (d dimensions, full covariance):

  • (K−1) weights + K·d means + K·d(d+1)/2 covariance terms.

  • With diag or tied covariances p is smaller, so you can also use BIC to choose covariance_type.

• AIC vs BIC:

  • BIC's penalty grows with ln n. It is stricter, prefers fewer components, and is consistent: it recovers the true K if the model is correct.

  • AIC targets predictive fit and tends to choose more components. That suits density estimation better than finding interpretable clusters.

• Practical tips:

  • Use several initializations (n_init) so a poor local optimum doesn't distort the curve.

  • Look for an elbow or plateau, not just the strict minimum.

  • If the clusters aren't Gaussian, both criteria favor extra components to approximate their shapes.

  • Alternative: BayesianGaussianMixture prunes unneeded components automatically.

The M-step updates all three parameter sets of each component: mixing weight πₖ, mean μₖ and covariance Σₖ. Each update is a closed-form maximum-likelihood estimate in which every point is weighted by its E-step responsibility γᵢₖ.

• Effective counts: Nₖ = Σᵢ γᵢₖ

• Updates:

  1. Weights: πₖ = Nₖ / n (the fraction of total responsibility).

  2. Means: μₖ = (1/Nₖ) Σᵢ γᵢₖ xᵢ (the responsibility-weighted average).

  3. Covariances: Σₖ = (1/Nₖ) Σᵢ γᵢₖ (xᵢ − μₖ)(xᵢ − μₖ)ᵀ, using the new μₖ.

• Why closed form:

  • With responsibilities fixed, the expected complete-data log-likelihood splits into separate weighted Gaussian MLE problems, one per component.

  • The weights come from a Lagrange multiplier that enforces Σπₖ = 1.

• Variations:

  • Constrained covariance types change the Σ update: diag keeps only the diagonal, tied pools a single Σ across components, and spherical uses one variance per component.

  • Add reg_covar to the diagonal so Σₖ cannot collapse to a singular matrix.

• Guarantee: each E+M iteration never decreases the log-likelihood, so EM converges, though only to a local optimum.

They are increasingly flexible constraints on each component's covariance matrix. Each step up lets clusters take on richer shapes, but adds parameters, which raises the risk of overfitting and of singular covariances.

• Spherical: Σ_k = σ_k² I:

  • One variance per component, so each cluster is a round ball with its own radius.

  • 1 parameter per component; this is the closest to k-means.

• Diagonal: Σ_k = diag(σ_k1², ..., σ_kd²):

  • Each feature has its own variance, giving axis-aligned ellipses. Features are assumed uncorrelated within a cluster.

  • d parameters per component; a good default in high dimensions.

• Tied: one full Σ shared by all components:

  • All clusters share the same shape and orientation and differ only in location.

  • d(d+1)/2 parameters in total. Decision boundaries between components are linear, as in LDA.

• Full: each component has its own unrestricted Σ_k:

  • Arbitrary rotated ellipses of different sizes, with quadratic boundaries.

  • K·d(d+1)/2 parameters. It needs the most data and is the most prone to singularity.

• Choosing between them:

  • Compare BIC/AIC across covariance_type values in sklearn's GaussianMixture.

  • Constrained types are faster and more stable on small or high-dimensional data. Full fits best when you have enough data and the features are correlated.

Prefer a GMM when clusters are not equal-sized spheres, when they overlap, or when you need probabilistic (soft) assignments or a density model. k-means implicitly assumes spherical, similarly sized, hard-partitioned clusters.

• Cluster shape and size:

  • A GMM with full covariances captures elongated, correlated, differently sized clusters.

  • k-means uses Euclidean distance to centroids, so it splits ellipses wrongly and favours equal-variance clusters.

• Soft assignments:

  • Responsibilities p(k | x) express uncertainty for points in overlapping regions.

  • They are useful for downstream decisions or for mixed-membership interpretation.

• Density estimation: A GMM gives p(x), which supports anomaly detection (low-likelihood points) and sampling.

• Principled model selection: A likelihood exists, so BIC/AIC can choose K and the covariance type.

• When to stick with k-means:

  • Very large data, roughly spherical clusters, or speed and simplicity matter most.

  • A GMM costs more per iteration (covariance estimation and inversion) and can be unstable in high dimensions.

The GMM log-likelihood is non-convex and has many local maxima. EM only guarantees a monotone increase in likelihood, so it converges to whichever local optimum (or degenerate solution) is reachable from the starting point.

• Why the surface is multimodal:

  • Label symmetry: any permutation of the components gives the same likelihood, producing K! equivalent optima.

  • Beyond that, genuinely different partitions can each be local maxima.

• EM is a local hill-climber: The E-step and M-step coordinate-ascend a lower bound on the likelihood. They never move "downhill" to escape a basin.

• Typical failure modes from bad starts:

  • Two components share one true cluster while another component spans two clusters.

  • A component starves (near-zero weight) or collapses onto a single point, giving a singular covariance.

  • Convergence is slow when components start heavily overlapping.

• Mitigations:

  • Initialise from k-means or k-means++ (init_params='kmeans' in sklearn).

  • Run multiple restarts (n_init) and keep the highest likelihood.

  • Regularise covariances (reg_covar) or use a Bayesian GMM with priors.

Choose spectral clustering when clusters are defined by connectivity rather than compactness. Typical cases are non-convex shapes like rings or moons, manifolds, or data you only have as a similarity graph, where k-means' straight-line Voronoi boundaries fail.

• Non-convex or manifold-shaped clusters:

  • Spectral embedding via Laplacian eigenvectors "unrolls" connected structures so they become separable.

  • k-means only finds convex, roughly spherical regions around centroids.

• Only an affinity is available: Graphs, kernels, or custom similarities (text, social networks, images as pixel graphs) work directly, with no need for vector-space means.

• Graph-cut interpretation: It approximates normalized cut, i.e. a balanced partition with few cross-cluster edges.

• When k-means is better:

  • Large n: building the affinity matrix and eigendecomposition cost up to O(n²) memory and O(n³) time without sparse or approximate methods.

  • Compact blob clusters, or when you need to assign new points cheaply (spectral clustering has no native out-of-sample step).

  • Spectral clustering is sensitive to the affinity choice (σ, k neighbours).

• Note: spectral clustering usually runs k-means as its final step, but in the eigenvector space.

Spectral clustering builds a similarity graph and computes its Laplacian. It then embeds points using the Laplacian's k smallest eigenvectors and runs k-means in that embedding.

1. Build the similarity graph: Form an affinity matrix W (e.g. Gaussian kernel, k-NN, or ε-neighbourhood).

2. Compute the degree matrix and Laplacian:

   • The degree matrix is D = diag(sum_j W_ij).

   • The unnormalized Laplacian is L = D - W.

   • Normalized variants are L_sym = I - D^-1/2 W D^-1/2 or L_rw = I - D^-1 W.

3. Eigendecompose:

   • Take the eigenvectors of the k smallest eigenvalues and stack them as columns of U (n × k).

   • The eigengap heuristic suggests k: look for a large jump after the k-th eigenvalue.

4. Normalise rows (for L_sym, Ng–Jordan–Weiss): Scale each row of U to unit length.

5. Cluster the rows:

   • Run k-means on the n rows of U.

   • Point i gets the label of row i.

You define a pairwise similarity between points, usually a Gaussian kernel on distances, and then sparsify it into a graph using an ε-neighbourhood, k-nearest-neighbour, or fully connected rule. Points are nodes and similarities are edge weights.

• Similarity function:

  • Gaussian (RBF) kernel: w_ij = exp(-||x_i - x_j||² / 2σ²).

  • Alternatives include cosine similarity (text, embeddings) or any domain-specific kernel.

  • Scale features first, because distances drive everything.

• Graph construction rules:

  • ε-neighbourhood: connect pairs closer than ε. This is simple, but struggles when clusters have different densities.

  • k-NN: connect each point to its k nearest neighbours. The relation is asymmetric, so symmetrize with "or" (standard k-NN graph) or "and" (mutual k-NN, which is sparser and better separates clusters of different density).

  • Fully connected: keep all kernel weights. Locality is controlled only by σ, and the graph is dense at O(n²).

• Choosing scale parameters:

  • σ heuristics: the median pairwise distance, or the mean distance to the k-th neighbour.

  • Local scaling (Zelnik-Manor & Perona): w_ij = exp(-d_ij² / (σ_i σ_j)), where σ_i is the distance to point i's k-th neighbour. This adapts to varying density.

  • For k-NN graphs, k ≈ log(n) is a common starting point. Ensure the graph is connected (or has exactly the intended components).

• Practical notes:

  • Sparse graphs (k-NN, ε) allow sparse eigensolvers and scale far better.

  • In sklearn, use SpectralClustering(affinity='rbf', gamma=...) or affinity='nearest_neighbors', n_neighbors=....

Profile each cluster by what makes it different from the overall population, give it a descriptive name and size, and translate those differences into concrete actions: stakeholders need personas and decisions, not distances and silhouette scores.

• Build the profile:

  • Compare per-cluster means/medians and category shares against the global baseline (index or lift, e.g. "2.3× more mobile usage").

  • Include business variables not used in clustering (revenue, churn, region) to make it relevant.

  • Report cluster size and value share so smaller segments aren't overlooked or overhyped.

• Find the drivers:

  • Train a shallow decision tree on cluster labels to extract simple rules.

  • Or a classifier plus SHAP / feature importance to rank distinguishing features.

• Communicate:

  • Name personas ("Price-sensitive weekend shoppers") and show 2–3 defining traits each.

  • Use visuals: radar/bar charts of indexed features, representative example customers.

  • Lead with "so what": recommended action per segment.

• Be honest about limits:

  • Clusters are a modeling choice, not ground truth; boundaries are fuzzy and may shift over time.

  • Avoid showing raw t-SNE/UMAP plots as evidence; they can mislead about distances and sizes.

Test for clustering tendency: compare the data against a uniform random reference (Hopkins statistic, gap statistic), inspect visual evidence (VAT, projections, distance distributions), and check whether clusters are stable. Clustering algorithms always return clusters, so this check prevents imposing structure on noise.

• Hopkins statistic:

  • Compares nearest-neighbor distances of real points with those of uniformly sampled points in the data space.

  • H ≈ 0.5 means random-like; H near 1 means clusterable (under the common convention).

• Gap statistic:

  • Compares log within-cluster dispersion against its expectation under a null reference for each k.

  • If the best k is 1, there is no evidence of structure.

• Visual checks:

  • VAT/iVAT: a reordered dissimilarity matrix shows dark diagonal blocks when clusters exist.

  • PCA/UMAP/t-SNE plots (treat t-SNE with caution: it can create apparent clusters).

  • Pairwise distance histogram: multimodality hints at groups.

• Quality and stability signals:

  • Low silhouette scores (e.g. < 0.25) for every k suggest weak structure.

  • Bootstrap/subsample and compare assignments (ARI): real clusters reappear, noise clusters don't.

  • Density methods (DBSCAN/HDBSCAN) labeling most points as noise is also informative.

• Caveat: results depend on scaling and feature choice; structure may exist only in a subset of features.

Reduce dimensionality when there are many (noisy, correlated, or sparse) features that make distances less meaningful or clustering slow. The risk is discarding exactly the variation that separates clusters, or introducing distortions that create fake ones.

• When it helps:

  • Curse of dimensionality: in high dimensions pairwise distances concentrate, so nearest and farthest neighbors look alike.

  • Noise and redundancy: PCA drops low-variance noise and decorrelates features.

  • Sparse data (text TF-IDF): truncated SVD/LSA before k-means.

  • Speed and memory for distance-based or density methods.

  • Nonlinear manifolds: UMAP to ~10–50 dims, then HDBSCAN is a common pipeline.

• Risks:

  • Variance ≠ separability: PCA keeps high-variance directions, but the cluster-separating direction may have low variance.

  • Distortion: t-SNE/UMAP warp density and inter-cluster distances, and can fragment or invent clusters; t-SNE in particular is meant for visualization, not clustering input.

  • Hyperparameter sensitivity: number of components, n_neighbors, min_dist change the result.

  • Interpretability loss: clusters are defined on components, not original features.

  • Scaling dependence: PCA on unscaled data is dominated by large-unit features.

• Mitigations:

  • Pick components by explained variance plus downstream stability, not a fixed number.

  • Compare clusterings with and without reduction (ARI); profile clusters on original features.

Each of Lloyd's two steps never increases the within-cluster sum of squares (SSE). SSE is bounded below by 0, and there are only finitely many possible partitions. So the cost must stop decreasing, and the algorithm reaches a fixed point in finitely many iterations.

• Objective: J = Σ_i ||x_i − μ_{c(i)}||²

• The assignment step does not increase J: With centroids fixed, moving each point to its nearest centroid minimizes its own term.

• The update step does not increase J: With assignments fixed, the mean is the unique minimizer of the sum of squared Euclidean distances (set the gradient to zero).

• Finiteness argument:

  1. Centroids are fully determined by the partition, and there are at most k^n partitions.

  2. J is monotone non-increasing. With a consistent tie-breaking rule, no partition can repeat, otherwise J would have to have decreased and then returned to the same value.

  3. So the algorithm must terminate when assignments stop changing.

• Caveats:

  • It converges to a local optimum (a fixed point), not the global one.

  • The guarantee relies on squared Euclidean distance plus the mean. With other distances (e.g. L1) the mean is no longer optimal, which is why k-medians and k-medoids exist.

  • The worst-case number of iterations can be exponential, though it is fast in practice.

K-means++ samples each new seed with probability proportional to D(x)², the squared distance to the nearest already-chosen seed. This makes it likely to place a seed in every well-separated true cluster. Arthur & Vassilvitskii (2007) proved the expected cost is O(log k) times the optimum, even before any Lloyd iterations. Uniform random seeding has no such bound: it can pick several seeds in one cluster and none in another, giving arbitrarily bad cost.

• Why uniform seeding fails:

  • With k far-apart clusters, the chance of hitting each one exactly once is small, roughly k!/k^k for equal sizes.

  • A missed cluster forces some centroid to cover two distant groups. The cost ratio is unbounded as the separation grows, and Lloyd's algorithm often cannot fix it.

• Why D² sampling helps:

  • Points in uncovered clusters are far from the current seeds, so they carry most of the probability mass.

  • Squaring the distance aligns sampling with the SSE objective: the regions contributing most cost are most likely to get a seed.

• Proof sketch:

  1. The first seed is uniform from an optimal cluster A. Its expected cost on A is 2·OPT(A).

  2. A D²-sampled seed that lands in an uncovered optimal cluster gives expected cost of at most 8·OPT on that cluster, by a triangle-inequality argument.

  3. An inductive potential argument bounds the cost of uncovered clusters, contributing a harmonic-sum factor H_k ≈ ln k.

  4. The result is E[cost] ≤ 8(ln k + 2)·OPT.

• Practical notes:

  • The bound holds in expectation for seeding alone. Lloyd iterations can only lower the cost further.

  • Seeding costs O(nkd). k-means|| parallelizes it for large data.

  • It is sensitive to outliers, since far points get high sampling probability.

Heavily imbalanced clusters usually mean the data violates k-means' assumptions or the pipeline is distorting distances. Common causes are unscaled features, outliers, a poor choice of k or initialization, or genuinely non-spherical or imbalanced structure. Diagnose which cause applies, then fix the data or switch to a better-suited method.

• Diagnose:

  1. Inspect the tiny clusters: if they are a handful of extreme points, they are outliers capturing their own centroids.

  2. Check feature scales: one high-variance feature (e.g. revenue next to ratios) can dominate distance and collapse structure into one blob.

  3. Visualize with PCA or UMAP, coloring points by cluster, to see whether the big cluster contains sub-structure or is a genuinely dense mass.

  4. Compare runs across seeds and k: unstable assignments point to an initialization or k problem.

  5. Look at per-cluster silhouette and SSE: a huge cluster with low silhouette is under-split.

  6. Check data quality: duplicates, sentinel values (0, −999), skewed features, or sparse high-dimensional features where distances concentrate.

• Fix the data:

  • Standardize features (StandardScaler), and log-transform skewed ones.

  • Remove or cap outliers, or cluster with them excluded and assign them afterwards.

  • Reduce dimensionality (PCA) or drop noisy features.

• Fix the algorithm setup:

  • Use k-means++ with a larger n_init.

  • Re-select k using the elbow method, silhouette, or gap statistic. Bisecting k-means can split the big cluster further.

• Change the method if the structure isn't spherical:

  • GMM with full covariance for unequal sizes and spreads.

  • HDBSCAN for varying density; it labels outliers as noise.

  • K-medoids for robustness to outliers.

• Sanity check: Imbalance can be real (e.g. most customers are typical). Validate the clusters against domain meaning before forcing balance.