Question bank — K-Means clustering algorithm

T/F: K-Means always returns the clustering with the lowest possible $J$. ::: False — it only reaches a local minimum. The path it takes depends on where the initial centroids landed, so a bad start can freeze it in a poor valley of the $J$ landscape (see figure below). T/F: Every iteration of K-Means either lowers $J$ or leaves it unchanged. ::: True — the assignment step can only move a point to a closer centroid (never farther), and the update step moves each centroid to the mean, which provably minimizes squared distance for a fixed group. Neither step can raise $J$. T/F: If two runs use different random initializations, they must converge to the same clusters. ::: False — different starts can land in different local minima and give genuinely different partitions. This is exactly why sklearn runs it ~10 times and keeps the lowest-$J$ result. T/F: Once assignments stop changing, the centroids are also guaranteed not to move. ::: True — centroids are the mean of their assigned points, so if the same points stay assigned, the mean is identical. Stable assignments ⇒ stable centroids. T/F: K-Means can leave a cluster with zero points assigned to it. ::: True — a centroid can "lose" all its points during assignment (an empty cluster). Then its mean is undefined ($0/0$), and implementations must re-seed it (e.g. at the farthest point) or drop it. T/F: Increasing $K$ can make $J$ go up. ::: False — $J$ is monotonically non-increasing in $K$; more centroids give points more nearby options, so $J$ only falls (reaching $0$ when $K=n$, one centroid per point). This is why you can't pick $K$ by minimizing $J$ — see 2.5.02-Choosing-K-Elbow-Silhouette. T/F: K-Means uses labels from the data to form its groups. ::: False — it is unsupervised; it never sees a target label. It only uses the geometry of the points themselves. T/F: Scaling one feature from metres to kilometres leaves the clustering unchanged. ::: False — K-Means uses raw Euclidean distance, so a feature with a larger numeric range dominates the distance. Rescaling changes which points look "close" and can flip the whole partition; standardize first. T/F: K-Means and running one full step of Expectation–Maximization on Gaussians are secretly related. ::: True — K-Means is the "hard-assignment" limit of EM for equal-covariance spherical Gaussians: instead of soft membership probabilities, each point is given 100% to its nearest centroid.

"I lowered $J$ by picking $K=n$, so that clustering is the best." ::: The error: $J=0$ at $K=n$ because every one of the $n$ points is its own cluster — that's overfitting, not insight. $J$ measures tightness, not usefulness; you need the elbow or silhouette instead. "K-Means failed on my ring-shaped data — it must be buggy." ::: No bug: K-Means assigns each point to the nearest centroid, which carves space into straight-edged (Voronoi) regions (see figure). A ring is non-convex, so no single centroid can capture it — you need DBSCAN or spectral clustering. "The update step sets each centroid to the median of its points." ::: Wrong — it's the mean. The mean is exactly the point that minimizes the sum of squared distances (the thing $J$ sums); the median minimizes sum of absolute distances, which is a different algorithm (K-Medians). "I used Manhattan distance in the assignment step but kept the mean update — that's fine." ::: Inconsistent: the mean only minimizes squared Euclidean distance. If you assign by another metric, the mean is no longer the optimal centroid, so $J$ can rise and the convergence guarantee breaks. "K-Means++ changes the update step to make it faster." ::: No — K-Means++ only changes initialization (spreading starting centroids far apart). The assignment and update steps are identical to plain Lloyd's algorithm. "My algorithm oscillated forever between two assignments." ::: This shouldn't happen with proper tie-breaking, because $J$ is non-increasing and bounded below by $0$, so it must settle. Endless oscillation signals a tie in the $\arg \min$ being resolved inconsistently between iterations.

Why does the centroid come out as the mean rather than some other summary? ::: Setting the derivative of $\sum \Vert x_i-\mu {\Vert }^2$ to zero gives $\sum (x_i-\mu )=0$, i.e. $\mu =\frac{1}{|C|}\sum x_i$. The squared penalty is what makes the mean optimal. Why do we square the distance instead of just using distance? ::: Squaring makes $J$ smooth and differentiable, which is what lets the mean fall out cleanly as the minimizer. It also penalizes far-off points quadratically, pulling centroids toward dense regions. Why is the assignment step the computational bottleneck? ::: It compares all $n$ points against all $K$ centroids in $d$ dimensions — $O(nKd)$ work — whereas the update just sums each point once, $O(nd)$. Distances dominate. Why does running K-Means several times help? ::: Because it only finds a local minimum, multiple random starts explore different valleys of the $J$ landscape; keeping the lowest-$J$ run is a cheap hedge against a bad initialization. Why is standardizing features often recommended before K-Means? ::: Euclidean distance treats all features equally in raw units, so a large-range feature silently dominates. Standardizing (mean 0, variance 1) gives each feature a fair say in "closeness." Why does K-Means implicitly assume spherical, similar-sized clusters? ::: Its decision boundaries are perpendicular bisectors between centroids (straight Voronoi cuts), which best fit blob-like groups of comparable spread. Elongated or unequal-density groups violate that geometry. Why is convergence guaranteed even though the problem is NP-hard? ::: Convergence to a minimum is easy — each step lowers a bounded objective. Finding the global minimum is the NP-hard part, and Lloyd's algorithm doesn't promise that.

What happens if two centroids start at the exact same location? ::: They'll receive identical distances to every point, so ties must be broken; typically one grabs everything and the other becomes empty (see figure), effectively wasting a cluster. K-Means++ avoids this by spacing seeds apart. What if all $n$ data points are identical? ::: Every distance is zero, so $J=0$ immediately and any assignment is "optimal." The clustering is meaningless because there's no structure to find. What if you set $K=1$? ::: There's a single cluster whose centroid is the global mean $\mu$ of all points. Then $J={\sum }_{i=1}^n\Vert x_i-\mu {\Vert }^2$ — the total squared deviation from the mean (not an average). If you define variance as $\text{Var}=\frac{1}{n}\sum \Vert x_i-\mu {\Vert }^2$, then equivalently $J=n\cdot \text{Var}$. No partitioning happens — it's just the dataset's center of mass. What if you set $K$ larger than the number of distinct points? ::: Some centroids can't get any unique points and become empty clusters; you'll get fewer effective clusters than $K$ unless duplicates are split arbitrarily. A point sits exactly halfway between two centroids — where does it go? ::: It's a tie in the $\arg \min$; the implementation must break it by a fixed rule (e.g. lowest index). The choice is arbitrary but must be consistent across iterations, or the algorithm can loop. An outlier lies far from every cluster — what does it do to the result? ::: Because distance is squared, the outlier tugs its assigned centroid strongly toward itself, distorting that cluster's center. K-Means is not robust to outliers; consider removing them or using a median-based method. What if the true clusters have very different densities? ::: K-Means tends to split the dense cluster and merge parts of sparse ones, since it balances squared distance, not density. Density-based DBSCAN handles this far better. Two features are perfectly correlated (redundant) — does that break K-Means? ::: It doesn't break, but that direction is effectively double-weighted in distance, biasing clusters along it. Decorrelating (e.g. PCA) or dropping the duplicate feature restores balance.