Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Cluster analysis: K-means and K-medoids

K-means and K-medoids are partitioning clustering methods: K-means uses cluster centroids (means) to minimize sum of squared Euclidean distances and is fast but sensitive to outliers; K-medoids uses actual data points (medoids) to minimize sum of pairwise dissimilarities and is robust to noise.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Clustering groups similar data so engineers can find patterns without labels (unsupervised learning). K-means and K-medoids are common partitioning methods used in customer segmentation, image compression, anomaly detection, and preprocessing for supervised models (see also: Normalisation and distance measures, Data reduction and discretisation).

Key ideas

Start with definitions.

  • Cluster: a set of data points considered similar by some measure (e.g., distance).
  • Partitioning clustering: dividing the dataset into a fixed number k of non-overlapping clusters so every point belongs to exactly one cluster.
  • Centroid: the arithmetic mean of points in a cluster; not necessarily a data point.
  • Medoid: the data point inside a cluster whose average dissimilarity to all other points in the cluster is minimal.
  • Objective function: a mathematical function expressing clustering quality; clustering algorithms try to minimize it.

K-means (Lloyd's algorithm) summary and assumptions:

  • K-means partitions n points in d-dimensional real space into k clusters by minimizing the within-cluster sum of squared errors (SSE) using Euclidean distance. Assumes numeric (interval/ratio) attributes and Euclidean geometry.
  • Algorithm steps (Lloyd's):
    1. Choose k initial centroids (randomly or by heuristic).
    2. Assignment step: assign each point to the nearest centroid (Voronoi partitioning).
    3. Update step: compute each cluster's centroid as the mean of its points.
    4. Repeat 2–3 until assignments do not change or a maximum number of iterations reached.
  • Properties: each iteration does not increase SSE; algorithm converges to a local minimum (not guaranteed global) because there are finitely many partitions and SSE decreases or stays same each step. Finding the globally optimal k-means clustering is NP-hard in general, so practical implementations often use multiple random restarts or k-means++ initialization to improve results.

Derivation (why centroid = mean minimizes SSE):

  • For a cluster C with points x₁,..,x_m in R^d, SSE(C, μ) = Σ_{i=1..m} ||x_i - μ||^2.
  • Differentiate SSE with respect to μ and set to zero: ∂/∂μ Σ||x_i - μ||^2 = -2 Σ (x_i - μ) = 0 ⇒ μ = (1/m) Σ x_i.
  • Therefore the arithmetic mean is the minimiser of SSE for that cluster.

K-medoids (PAM and variants) summary and assumptions:

  • K-medoids chooses k actual data points (medoids) to minimize total dissimilarity (sum of distances) between each point and its cluster medoid. Works with any dissimilarity measure (can be non-Euclidean), so it is more robust to outliers and noise.
  • PAM (Partitioning Around Medoids) algorithm steps:
    1. Initialize: choose k medoids (random or heuristic).
    2. Assignment: assign each point to nearest medoid.
    3. Update: for each medoid m and each non-medoid o, consider swapping m with o; if swap reduces total cost (sum of distances to nearest medoid), perform the best swap. Repeat until no improving swap.
  • Properties: more robust to outliers because medoids are data points; higher computational cost than K-means for large n. For scalability on large n, see CLARA (sampling-based) and CLARANS (randomized search) variants.

What to draw for an exam diagram:

  • For K-means: draw a 2D scatter of points, mark two centroids (filled circles) and draw straight perpendicular bisector lines (Voronoi boundaries) between centroids; label centroids μ1, μ2 and clusters C1, C2.
  • For K-medoids: draw same scatter but mark medoids as actual data points (squares) and show cluster assignments by connecting points to their medoid.

Formulas

SSE = Σ_{j=1..k} Σ_{x ∈ C_j} ||x - μ_j||^2

  • μ_j: centroid (mean vector) of cluster C_j; x: data point vector (same units as the data features); SSE unit = (feature unit)^2; applies to K-means with Euclidean distance.

μ_j = (1/|C_j|) Σ_{x ∈ C_j} x

  • μ_j: centroid vector; |C_j|: number of points in cluster C_j; x: point vector; units = feature units; applies when minimizing SSE.

Cost_kmedoids = Σ_{j=1..k} Σ_{x ∈ C_j} d(x, m_j)

  • m_j: medoid of cluster C_j (a data point); d(·,·): dissimilarity measure (units depend on d; e.g., Euclidean/Manhattan: feature units; squared Euclidean: feature units^2; cosine dissimilarity: unitless); applies to K-medoids and PAM.

Assignment: cluster(x) = argmin_{j=1..k} d(x, representative_j)

  • representative_j is μ_j for K-means and m_j for K-medoids; d: distance function (Euclidean for K-means); assigns x to nearest representative.

Time(K-means) ≈ O(n · k · t · d)

  • n: number of points; k: clusters; t: iterations until convergence; d: feature dimension; unitless; rough upper-bound.

Time(PAM) per full swap search ≈ O(k · (n-k)^2 · d)

  • Typical PAM cost for the swap phase; n, k, d as above; unitless; indicates PAM scales poorly for large n and higher d.

Worked examples

Example 1 — K-means numerical trace (2D, k=2) Data points (units: arbitrary): A(1,1), B(1,2), C(4,4), D(5,4). Choose initial centroids μ1 = A = (1,1), μ2 = C = (4,4). Step 1 — assignment (Euclidean distance):

  • Dist(A,μ1)=0, Dist(A,μ2)=√(3^2+3^2)=4.242 ⇒ A→C1
  • Dist(B,μ1)=1, Dist(B,μ2)=√(3^2+2^2)=3.606 ⇒ B→C1
  • Dist(C,μ1)=4.242, Dist(C,μ2)=0 ⇒ C→C2
  • Dist(D,μ1)=5.000, Dist(D,μ2)=1.000 ⇒ D→C2 Step 2 — update centroids (means):
  • μ1 = mean of {A,B} = ((1+1)/2, (1+2)/2) = (1, 1.5)
  • μ2 = mean of {C,D} = ((4+5)/2, (4+4)/2) = (4.5, 4) Step 3 — reassign with new centroids (compute distances):
  • A to μ1: 0.5, to μ2: 4.610 ⇒ A→C1
  • B to μ1: 0.5, to μ2: 4.031 ⇒ B→C1
  • C to μ1: 3.905, to μ2: 0.5 ⇒ C→C2
  • D to μ1: 4.720, to μ2: 0.5 ⇒ D→C2 Assignments unchanged → converged. Compute final SSE:
  • Each point distance = 0.5 → squared = 0.25; total SSE = 4 × 0.25 = 1.0 (feature-unit^2).

Example 2 — K-medoids (PAM) small 1D trace Data (1D): 0, 1, 4, 8; choose k=2. Initial medoids m1=0, m2=8. Assignment to nearest medoid: cluster1 {0,1,4} (point 4 ties; assign to 0), cluster2 {8}. Compute medoid of cluster1 by minimal sum of absolute distances:

  • Sum if medoid=0: 0+1+4 = 5
  • medoid=1: 1+0+3 = 4 (minimal)
  • medoid=4: 4+3+0 = 7 So new medoids become 1 and 8. Total cost = distances to medoids: |0-1|+|1-1|+|4-1|+|8-8| = 1+0+3+0 = 4 (units). If there was an outlier 100 added, K-means centroid would shift much more than medoid; medoid stays an actual point so more robust.

Common mistakes

  • Using K-means with non-numeric or categorical attributes without defining distance/encoding; K-means requires numeric features and Euclidean distance for standard updates.
  • Confusing centroid with medoid — centroid may not be a data point; medoid always is.
  • Forgetting to state the distance metric when giving formulas; SSE uses Euclidean norm specifically.
  • Not checking for empty clusters after assignment; you must handle empty clusters (e.g., re-initialize centroid or remove cluster).
  • Arithmetic errors in mean calculation: always divide by the cluster size, not by total n.

For your exam

Possible question types:

  • Definitions and comparisons: define K-means, K-medoids, centroid, medoid; list advantages/disadvantages.
  • Algorithm trace: run K-means or PAM on small dataset (show iterations, assignments, centroid/medoid updates, final cost).
  • Derivation: show why the mean minimizes SSE (do the derivative proof).
  • Complexity and limitations: derive time complexity and discuss sensitivity to initialization/outliers, and methods to choose k (elbow, silhouette score, gap statistic).
  • Diagram: sketch clusters and Voronoi boundaries for K-means.

What full-marks answers include:

  • Clear definitions with bold naming (centroid vs medoid) and assumptions (data type, distance measure).
  • Complete algorithm steps with stopping condition.
  • Correct derivation for the centroid formula (show differentiation and result).
  • Correct iteration trace for numerical examples with units and final objective value.
  • Discussion of limitations (local minima, empty clusters, scaling, need for k) and brief remedies (multiple restarts, k-means++, use K-medoids for outliers).

Quick check

  1. What is the centroid of points (2,0) and (4,6)?
  2. Which method (K-means or K-medoids) is preferred with heavy outliers? Give one reason.
  3. Write the K-means objective function symbolically.

Answers: 1) centroid = (3, 3). 2) K-medoids — because medoids are actual data points and the method minimises sum of distances, so one outlier cannot drag a medoid far. 3) SSE = Σ_{j=1..k} Σ_{x ∈ C_j} ||x - μ_j||^2.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?