k-Means

Alternate assigning points to the nearest centroid and moving centroids to the mean, until nothing changes.

17 min read1535 wordscore10 viewsupdated 2026-10-07

Definition

k-means partitions nn points into kk clusters, each summarized by a centroid (its mean). It alternates two steps — assign every point to its nearest centroid, then move every centroid to the mean of its points — until the assignments stop changing. This is coordinate descent on the within-cluster sum of squares J=∑i∥xi−μc(i)∥2J=\sum_i\lVert x_i-\mu_{c(i)}\rVert^2.

At a glance

Task
Clustering (unsupervised): hard partition into exactly kk groups
Input → output
points x1,…,xn∈Rdx_1,\dots,x_n\in\mathbb{R}^d and kk → a label c(i)∈{1,…,k}c(i)\in\{1,\dots,k\} per point and kk centroids
Learns
kk centroids μ1,…,μk\mu_1,\dots,\mu_k — nothing else; the clusters are the Voronoi cells of the centroids
Training
O(nkd)O(nkd) per iteration, usually 5–50 iterations; times the number of restarts
Prediction
nearest centroid: O(kd)O(kd) per point
Hyperparameters
n_clusters kk, init (k-means++ or random), n_init restarts, max_iter, tol
Assumes
Euclidean distance is meaningful (features scaled); clusters are compact, convex, roughly spherical and of similar spread

The problem

You have unlabeled data — customers described by visit frequency and basket size, pixels by colour, documents by embedding — and suspect it falls into groups. You want to find those groups without being told what they are, and to describe each one by a single representative that you can inspect, store and compare new points against.

Searching over partitions directly is hopeless: the number of ways to split nn points into kk non-empty groups (a Stirling number of the second kind) is about kn/k!k^n/k! — for 100 points and 3 groups that is over 104610^{46}. Even the clean question "which partition minimizes squared distance to the group means?" is NP-hard in general. We need a fast method that finds a good partition, accepting that it may not be the best one.

Hierarchical methods (see hierarchical clustering and agglomerative clustering) build a whole tree of merges but cost O(n2)O(n^2) memory; k-means scales linearly in nn, which is why it is the default first clustering for large data.

The idea

It is a chicken-and-egg problem with an easy solution on each side. If you knew the centres, the obvious clustering would be: put each point with its nearest centre. If you knew the clusters, the obvious centre of each would be its average point. You know neither, so guess the centres, then alternate the two obvious moves. Each move can only make the clustering tighter, and there are finitely many clusterings, so the process must stop.

Vocabulary

Centroid
μj\mu_j, the mean of the points in cluster jj — a point in feature space that need not be a data point (contrast the medoid of k-medoids, which must be one)
Assignment
c(i)c(i), the index of the cluster point ii belongs to; k-means is a hard assignment (each point in exactly one cluster)
Inertia / WCSS
within-cluster sum of squares JJ, the objective; scikit-learn reports it as "inertia_"
Voronoi cell
the region of space closer to μj\mu_j than to any other centroid; the cells tile the space and their borders are straight lines (hyperplanes)
Lloyd's algorithm
the assign / update loop itself (Lloyd 1957, published 1982); "k-means" usually means this
Seeding
how the first centroids are chosen: random data points, or k-means++
Restart
one full run from a fresh seeding; keep the run with the lowest JJ
Local minimum
a clustering where neither step can lower JJ, though a different clustering has lower JJ

The math

Encode the clustering as an assignment cc and centroids μ\mu. k-means minimizes

J(c,μ)=∑i=1n∥xi−μc(i)∥2=∑j=1k∑i: c(i)=j∥xi−μj∥2J(c,\mu)=\sum_{i=1}^{n}\lVert x_i-\mu_{c(i)}\rVert^2=\sum_{j=1}^{k}\sum_{i:\,c(i)=j}\lVert x_i-\mu_j\rVert^2
xix_i
the ii-th data point, a vector in Rd\mathbb{R}^d
c(i)c(i)
cluster index assigned to point ii
μj\mu_j
centroid of cluster jj
∥⋅∥2\lVert\cdot\rVert^2
squared Euclidean distance: sum over features of squared differences
JJ
within-cluster sum of squares (inertia); lower = tighter clusters

JJ is hard to minimize jointly — cc is discrete — but easy to minimize in each block of variables with the other held fixed. That is exactly what the two steps do.

Assign step (fix μ\mu, optimize cc). JJ is a sum of independent terms, one per point, and point ii only affects its own term. So each point independently picks the centroid that makes its term smallest:

c(i)←arg⁡min⁡j ∥xi−μj∥2c(i)\leftarrow\arg\min_{j}\ \lVert x_i-\mu_j\rVert^2
arg⁡min⁡j\arg\min_j
the index j that minimizes the expression (ties: lowest index)

The border between two cells is where ∥x−μa∥2=∥x−μb∥2\lVert x-\mu_a\rVert^2=\lVert x-\mu_b\rVert^2. Expanding, the ∥x∥2\lVert x\rVert^2 terms cancel and we get 2(μb−μa)⊤x=∥μb∥2−∥μa∥22(\mu_b-\mu_a)^\top x=\lVert\mu_b\rVert^2-\lVert\mu_a\rVert^2 — a straight line (hyperplane), the perpendicular bisector of the two centroids. So k-means can only ever carve space into convex polygons.

Update step (fix cc, optimize μ\mu). Now JJ splits into one term per cluster. For cluster jj with point set SjS_j, set the gradient to zero:

∂∂μj∑i∈Sj∥xi−μj∥2=−2∑i∈Sj(xi−μj)=0 ⟹ μj=1∣Sj∣∑i∈Sjxi\frac{\partial}{\partial\mu_j}\sum_{i\in S_j}\lVert x_i-\mu_j\rVert^2=-2\sum_{i\in S_j}(x_i-\mu_j)=0\ \Longrightarrow\ \mu_j=\frac{1}{|S_j|}\sum_{i\in S_j}x_i
SjS_j
the set of points currently assigned to cluster jj
∣Sj∣|S_j|
number of points in cluster j

The function is a convex quadratic in μj\mu_j, so this stationary point is the global minimum: the mean is the point that minimizes the sum of squared distances. That is why the method is called k-means. (With absolute distances the minimizer would be the median — the idea behind k-medians; restricting centres to data points gives k-medoids.)

Variance decomposition. The total sum of squares around the grand mean xˉ\bar x splits exactly into a within-cluster and a between-cluster part:

∑i∥xi−xˉ∥2⏟TSS=∑j∑i∈Sj∥xi−μj∥2⏟J=WSS+∑j∣Sj∣ ∥μj−xˉ∥2⏟BSS\underbrace{\sum_i\lVert x_i-\bar x\rVert^2}_{\text{TSS}}=\underbrace{\sum_j\sum_{i\in S_j}\lVert x_i-\mu_j\rVert^2}_{J=\text{WSS}}+\underbrace{\sum_j|S_j|\,\lVert\mu_j-\bar x\rVert^2}_{\text{BSS}}
xˉ\bar x
mean of all n points
BSS\text{BSS}
between-cluster sum of squares: how far apart the centroids are, weighted by cluster size

TSS is fixed by the data, so minimizing JJ is the same as maximizing the separation between clusters. The ratio BSS/TSS\text{BSS}/\text{TSS} is the fraction of variance "explained" by the clustering.

What each hyperparameter does to the objective

k
The optimum J∗(k)J^*(k) is non-increasing in kk (adding a centroid can never hurt) and reaches 0 at k=nk=n. So JJ cannot choose kk by itself — look for the elbow where the drop flattens, or use silhouette / gap statistic.
init
Chooses the starting point of the descent, and therefore which local minimum you land in. k-means++ seeding gives E[J]≤8(ln⁡k+2) J∗\mathbb{E}[J]\le 8(\ln k+2)\,J^* before any Lloyd iteration.
n_init
Number of independent restarts; the final JJ is the minimum over runs, so it can only go down as n_init grows, at linear cost.
max_iter, tol
Stop after a fixed number of iterations or when the centroids move less than tol (relative to feature variance). Too loose a tolerance stops before the assignments settle.

k-means++ seeding. Pick the first centre uniformly from the data. Then pick each next centre with probability proportional to D(x)2D(x)^2, the squared distance from xx to the nearest centre already chosen. Far-away, not-yet-covered regions are very likely to get a centre; points next to an existing centre almost never are.

P(next centre=xi)=D(xi)2∑l=1nD(xl)2,D(x)=min⁡chosen μ∥x−μ∥P(\text{next centre}=x_i)=\frac{D(x_i)^2}{\sum_{l=1}^{n}D(x_l)^2},\qquad D(x)=\min_{\text{chosen }\mu}\lVert x-\mu\rVert
D(x)D(x)
distance from x to its nearest already-chosen centre (0 for chosen points)

Worked example: 12 customers, k = 3

Twelve customers described by two already-scaled features. By eye there are three groups — bottom-left (1–4), top (5–8) and bottom-right (9–12) — but the algorithm doesn't know that. We start from a deliberately poor seeding: μ1=(1,2)\mu_1=(1,2) and μ2=(2,1)\mu_2=(2,1) both inside the bottom-left group and μ3=(6,8)\mu_3=(6,8) in the top group, so the bottom-right group has no centroid at all.

#x1x_1x2x_2d2d^2 to μ1=(1,2)\mu_1=(1,2)d2d^2 to μ2=(2,1)\mu_2=(2,1)d2d^2 to μ3=(6,8)\mu_3=(6,8)assigned
1120261μ1\mu_1
2212065μ2\mu_2
3232441μ1\mu_1
4324245μ2\mu_2
56861650μ3\mu_3
67761612μ3\mu_3
77985892μ3\mu_3
88885854μ3\mu_3
982493740μ2\mu_2
1091654958μ2\mu_2
1193655334μ3\mu_3
12102816552μ3\mu_3
The data with the squared distances to the starting centroids. Highlighted: points 9–12, which have no centroid of their own and get split between μ2\mu_2 and μ3\mu_3.

Lloyd's algorithm by hand

  1. 1Iteration 1 · assign. Each row takes its smallest d2d^2 (bold). Clusters: μ1{1,3}\mu_1\{1,3\}, μ2{2,4,9,10}\mu_2\{2,4,9,10\}, μ3{5,6,7,8,11,12}\mu_3\{5,6,7,8,11,12\}. Summing the bold column: J=0+0+2+2+0+2+2+4+37+49+34+52=184J=0+0+2+2+0+2+2+4+37+49+34+52=184.
  2. 2Iteration 1 · update. Means: μ1=12[(1,2)+(2,3)]=(1.5,2.5)\mu_1=\tfrac12[(1,2)+(2,3)]=(1.5,2.5); μ2=14[(2,1)+(3,2)+(8,2)+(9,1)]=(5.5,1.5)\mu_2=\tfrac14[(2,1)+(3,2)+(8,2)+(9,1)]=(5.5,1.5); μ3=16(47,37)=(7.833,6.167)\mu_3=\tfrac16(47,37)=(7.833,6.167). With the same clusters, JJ drops to 92.66792.667. μ2\mu_2 has been dragged halfway across the plot by points 9 and 10.
  3. 3Iteration 2 · assign. Points 2 and 4 are now closer to μ1\mu_1 (d2=2.5d^2=2.5 vs 12.5 and 6.5) and point 12 is closer to μ2\mu_2 (20.520.5 vs 22.05622.056). Clusters: μ1{1,2,3,4}\mu_1\{1,2,3,4\}, μ2{9,10,12}\mu_2\{9,10,12\}, μ3{5,6,7,8,11}\mu_3\{5,6,7,8,11\}; J=77.111J=77.111.
  4. 4Iteration 2 · update. μ1=(2,2)\mu_1=(2,2), μ2=13(27,5)=(9,1.667)\mu_2=\tfrac13(27,5)=(9,1.667), μ3=15(37,35)=(7.4,7)\mu_3=\tfrac15(37,35)=(7.4,7); J=33.867J=33.867.
  5. 5Iteration 3 · assign. Only point 11 moves: d2=1.778d^2=1.778 to μ2\mu_2 vs 18.5618.56 to μ3\mu_3. Clusters are now the three visual groups; J=17.084J=17.084.
  6. 6Iteration 3 · update. μ1=(2,2)\mu_1=(2,2), μ2=(9,2)\mu_2=(9,2), μ3=(7,8)\mu_3=(7,8); J=12J=12 — every point is at squared distance 1 from its centroid.
  7. 7Iteration 4 · assign. No point changes cluster, so the centroids would not move either: converged after 3 updates. J=12J=12, and TSS =212=212 around the grand mean (6,4)(6,4), so BSS=200\text{BSS}=200 and the clustering explains 200/212=94.3%200/212=94.3\% of the variance.
  8. 8Predict a new customer q=(6,3)q=(6,3): d2d^2 to (2,2),(9,2),(7,8)(2,2),(9,2),(7,8) is 17, 10, 2617,\ 10,\ 26. Nearest is μ2\mu_2, so qq joins the bottom-right cluster.
IterationStepμ1\mu_1μ2\mu_2μ3\mu_3Points that movedJJ
1assign(1, 2)(2, 1)(6, 8)all 12184.000
1update(1.5, 2.5)(5.5, 1.5)(7.833, 6.167)—92.667
2assign2, 4, 1277.111
2update(2, 2)(9, 1.667)(7.4, 7)—33.867
3assign1117.084
3update(2, 2)(9, 2)(7, 8)—12.000
4assignnone → stop12.000
JJ after every half-step. It never increases — 184 → 12 — which is the convergence argument in action.
01234567891011012345678910drag the ✕ centroids · drag ◆ to classify a new point123456789101112J after each half-steppress Next stepbest J per k (elbow)21219221231048566k · ○ current J
Article start: μ₁ = (1,2), μ₂ = (2,1), μ₃ = (6,8). Two centroids sit in the same group. Press Next step.
iteration 0 · J = —
start:k:
new point ◆ (6.0, 3.0) → nearest centroid μ2 = (2.00, 1.00), d² = 20.00
fig.The 12 customers from the table. Press Next step to alternate assign and update from the article's start: J falls 184 → 92.667 → 77.111 → 33.867 → 17.084 → 12. Dashed arrows show where each centroid will jump (its cluster mean); dashed rings mark points about to switch cluster. Drag any centroid to re-seed by hand, try the stuck start (it ends at J = 90, a local minimum), re-seed with k-means++, change k and watch your J against the elbow curve (best J = 212, 92, 12, 10, 8, 6 for k = 1…6), and drag the diamond to classify a new point — once converged, (6, 3) joins μ₂ = (9, 2) with d² = 10.

Local minima and seeding

Start instead from μ=(1,2),(2,1),(3,2)\mu=(1,2),(2,1),(3,2) — all three centroids in the bottom-left group. After two iterations Lloyd settles on μ1=(1.5,2.5)\mu_1=(1.5,2.5), μ2=(2.5,1.5)\mu_2=(2.5,1.5), μ3=(8,5)\mu_3=(8,5): the bottom-left group is split in two and the top and bottom-right groups are merged into one cluster. J=90J=90, seven and a half times the optimum, and neither step can improve it: no point is closer to another centroid, and every centroid is at its mean.

How often does a random start fail here? Of the (123)=220\binom{12}{3}=220 ways to seed with three data points, 183 (83.2%) reach J=12J=12. k-means++ does much better: from a first centre at (1,2)(1,2), the squared distances sum to 560, and only 8/560=1.4%8/560=1.4\% of that mass is in the bottom-left group, versus 52.1% in the top and 46.4% in the bottom-right. Using scikit-learn's k-means++ with a single run, all 1000 seeds we tried reached J=12J=12. Restarts (n_init) handle the remaining bad luck.

▸ k-means · Lloyd's algorithmstep 1/8
iteration 0J = —
  1. 1μ₁ … μₖ ← k starting points
  2. 2repeat:
  3. 3 c(i) ← argminₖ ‖xᵢ − μₖ‖²
  4. 4 μₖ ← mean{ xᵢ : c(i) = k }
  5. 5until no c(i) changes

Place k = 3 centroids. Here two start inside the same cluster — a bad but common start.

fig.Lloyd's algorithm on 54 points in three blobs, from a poor start with two centroids in one blob. Shaded regions are the Voronoi cells of the current centroids; dashed lines show each update's move.

The algorithm, step by step

KMeans(X, k)

  1. 1Scale the features (standardize) so that no feature dominates the distance.
  2. 2Seed kk centroids with k-means++: first uniformly at random, each next one with probability ∝D(x)2\propto D(x)^2.
  3. 3Assign each point to its nearest centroid: compute the n×kn\times k matrix of squared distances and take the row-wise arg-min.
  4. 4Update each centroid to the mean of its points. If a cluster is empty, re-seed it (e.g. at the point farthest from its centroid).
  5. 5Repeat assign and update until no assignment changes, the centroids move less than tol, or max_iter is reached.
  6. 6Restart n_init times and keep the run with the lowest JJ.
  7. 7Predict a new point by its nearest centroid.

Complexity

Per iteration
O(nkd)O(nkd) for the distances, O(nd)O(nd) for the means
Total
O(nkd⋅T⋅n_init)O(nkd\cdot T\cdot \text{n\_init}) with TT iterations; TT is small in practice although the worst case is exponential
Memory
O(nd+kd)O(nd+kd) — no pairwise distance matrix, unlike hierarchical clustering or affinity propagation
Prediction
O(kd)O(kd) per point

Variants and practical tuning

VariantWhat changesWhen to use
Elkan's algorithmtriangle inequality bounds skip most distance computationsdense data, moderate k (scikit-learn algorithm="elkan")
Mini-batch k-meansupdates centroids from small random batches with a decaying learning ratemillions of points or streaming data; slightly higher J
Bisecting k-meansrepeatedly splits the cluster with the largest J in twolarge k; gives a hierarchy and more even cluster sizes
k-medoids (PAM)centres must be data points; any distancenon-Euclidean distances, robustness to outliers — see k-medoids
Spherical k-meanscosine similarity, centroids normalized to unit lengthtext / embedding vectors
Kernel k-meansdistances in a kernel feature spacenon-convex clusters; closely related to spectral clustering
Fuzzy c-meanssoft memberships with fuzzifier mpoints can belong partly to several groups (or use a GMM)
The k-means family. The first three are drop-in speedups of the same objective; the rest change the objective or the centres.
kbest JJdrop from k−1k-1silhouette
1212——
2921200.536
312800.753
41020.547
5820.365
Choosing kk on the worked example: the best JJ for each kk and the silhouette score of that clustering. Both point to k=3k=3.

The elbow: going from 2 to 3 clusters removes 80 units of JJ, going from 3 to 4 removes only 2. The silhouette of a point is (b−a)/max⁡(a,b)(b-a)/\max(a,b), where aa is its mean distance to its own cluster and bb to the nearest other cluster; the average is highest (0.753) at k=3k=3.

In code

python
1import numpy as np
2
3def kmeans_pp(X, k, rng):
4 centres = [X[rng.integers(len(X))]]
5 for _ in range(k - 1):
6 d2 = ((X[:, None] - np.array(centres)[None]) ** 2).sum(-1).min(1)
7 centres.append(X[rng.choice(len(X), p=d2 / d2.sum())]) # D² sampling
8 return np.array(centres, float)
9
10def lloyd(X, mu, max_iter=100):
11 mu = np.array(mu, float)
12 labels = None
13 for it in range(1, max_iter + 1):
14 d2 = ((X[:, None] - mu[None]) ** 2).sum(-1) # n × k squared distances
15 new = d2.argmin(1) # assign
16 if labels is not None and (new == labels).all():
17 break # converged
18 labels = new
19 for j in range(len(mu)): # update
20 if (labels == j).any():
21 mu[j] = X[labels == j].mean(0)
22 J = ((X - mu[labels]) ** 2).sum()
23 print(f"iter {it}: J = {J:.3f} centroids = {np.round(mu, 3).tolist()}")
24 return labels, mu, ((X - mu[labels]) ** 2).sum()
25
26def kmeans(X, k, n_init=10, seed=0):
27 rng = np.random.default_rng(seed)
28 runs = [lloyd(X, kmeans_pp(X, k, rng)) for _ in range(n_init)]
29 return min(runs, key=lambda r: r[2]) # keep the lowest J
30
31X = np.array([[1, 2], [2, 1], [2, 3], [3, 2], [6, 8], [7, 7],
32 [7, 9], [8, 8], [8, 2], [9, 1], [9, 3], [10, 2]], float)
33
34labels, mu, J = lloyd(X, [[1, 2], [2, 1], [6, 8]]) # the article's start
35print(labels, J) # [0 0 0 0 2 2 2 2 1 1 1 1] 12.0
36x_new = np.array([6, 3])
37print("new point ->", ((mu - x_new) ** 2).sum(1).argmin()) # 1
From scratch: k-means++ seeding, Lloyd's loop and restarts. Run on the article's start, it prints J = 92.667, 33.867, 12.000 and assigns (6, 3) to cluster 1 (μ₂).
python
1import numpy as np
2from sklearn.cluster import KMeans
3from sklearn.metrics import silhouette_score
4
5X = np.array([[1, 2], [2, 1], [2, 3], [3, 2], [6, 8], [7, 7],
6 [7, 9], [8, 8], [8, 2], [9, 1], [9, 3], [10, 2]], float)
7
8# 1) Reproduce the hand computation: fixed start, a single run.
9km = KMeans(n_clusters=3, init=np.array([[1, 2], [2, 1], [6, 8]]), n_init=1).fit(X)
10print(km.labels_, km.cluster_centers_.tolist(), km.inertia_, km.n_iter_)
11# [0 0 0 0 2 2 2 2 1 1 1 1] [[2.0, 2.0], [9.0, 2.0], [7.0, 8.0]] 12.0 4
12print(km.predict([[6, 3]])) # [1]
13
14# 2) The poor start gets stuck in a local minimum.
15bad = KMeans(n_clusters=3, init=np.array([[1, 2], [2, 1], [3, 2]]), n_init=1).fit(X)
16print(bad.inertia_) # 90.0
17
18# 3) In practice: k-means++ with restarts, and choosing k.
19for k in range(2, 6):
20 m = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=0).fit(X)
21 print(k, round(m.inertia_, 3), round(silhouette_score(X, m.labels_), 3))
22# 2 92.0 0.536 | 3 12.0 0.753 | 4 10.0 0.547 | 5 8.0 0.365
scikit-learn on the same data: the fixed start reproduces the hand computation (n_iter_ = 4 counts the final, unchanged assignment), the stuck start ends at 90, and k-means++ with restarts picks out the elbow.

Use when

  • +You need a fast, scalable clustering: linear in n, millions of points, mini-batch for streams.
  • +Clusters are compact, round-ish and similar in size, and a mean is a meaningful prototype.
  • +You want a codebook: vector quantization, colour quantization, coarse indexes for nearest-neighbour search, or to initialize a Gaussian mixture.
  • +You need to assign new points cheaply — one distance per centroid.

Avoid when

  • −Clusters are elongated, nested, non-convex or very different in size or density — use GMM, DBSCAN/HDBSCAN or spectral clustering.
  • −There are strong outliers: one far point drags a mean — use k-medoids or remove outliers first.
  • −Features are categorical or distance is not Euclidean — use k-modes or k-medoids.
  • −You have no idea what k is and want a hierarchy instead — use agglomerative clustering or HDBSCAN.

Where it's used

Customer segmentation

Group customers by recency, frequency and spend; each centroid is a readable "typical customer" for a marketing persona.

Colour quantization & compression

Cluster pixel colours into kk centroids (say 16) and store each pixel as a 4-bit index into that palette.

Vector search indexes

Inverted-file (IVF) indexes in FAISS and similar libraries use k-means centroids as coarse buckets, so a query only scans the few nearest buckets.

Bag of visual words / features

Cluster local image descriptors or embeddings; the cluster index becomes a discrete token or a feature for a downstream model.

Check yourself

Why is a centroid updated to the mean of its cluster's points?

Check yourself

With centroids (2, 2), (9, 2) and (7, 8), which centroid does the new point (6, 3) join?

Check yourself

k-means++ has placed its first centre at (1, 2) in the worked example (squared distances sum to 560). What is the probability that the second centre lands in the bottom-left group (points 1–4)?

Check yourself

Why can't you choose k by picking the value with the lowest inertia J?

Remember

  • ✓k-means minimizes the within-cluster sum of squares JJ by coordinate descent: assign each point to its nearest centroid, move each centroid to its mean.
  • ✓Each step can only lower JJ, so the algorithm always terminates — but at a local minimum (on the example, J=90J=90 versus the optimum 12).
  • ✓Seed with k-means++ (D² sampling) and run several restarts; keep the lowest J.
  • ✓Standardize features: Euclidean distance lets large-unit features decide the clusters.
  • ✓Choose k by the elbow, silhouette or gap statistic — J alone always prefers more clusters.
  • ✓Cells are convex (perpendicular bisectors), so k-means suits compact, round, similar-sized clusters; otherwise use GMM, DBSCAN or spectral clustering.
← back to ML Algorithms roadmap