K-Means Initialization and Local Minima

Why Initialization Matters

K-means does not search all possible partitions before choosing one. Lloyd’s algorithm alternates between assigning each profile to its nearest center and updating centers to the means of their assigned profiles. The objective cannot increase during these steps, but it is not a convex function of all cluster assignments and centers together. Consequently, the solution can depend on the starting centers: different starts can lead to different fixed partitions with different objective values.

This matters in genomic data because a clustering is often used to describe groups of samples or profiles. A partition that appears only for one favorable initialization may be less convincing as a summary than a partition repeatedly recovered under the same analysis choices. Repeated fits diagnose sensitivity to initialization; they do not establish that the groups are biologically real or determine the appropriate number of clusters.

Definition: For $n$ profiles $x_1,\ldots,x_n$ in $p$-dimensional Euclidean space and $k$ nonempty clusters $C_1,\ldots,C_k$, the k-means within-cluster sum of squares (WCSS) is $$ W(C_1,\ldots,C_k)=\sum_{j=1}^{k}\sum_{i\in C_j}\|x_i-\bar{x}_{C_j}\|^2, $$ where $\bar{x}_{C_j}=|C_j|^{-1}\sum_{i\in C_j}x_i$ is the mean profile in cluster $j$. A Lloyd fixed point is a state in which each profile is assigned to a nearest center and each center is the mean of its assigned profiles. Such a state is a coordinatewise optimum: changing assignments alone or centers alone cannot lower WCSS. It need not be the global minimum over all partitions.

The Euclidean distances in this definition depend on the feature representation and scaling. The earlier material on centering and scaling, and on distance concentration in high dimensions, is relevant: initialization cannot repair a distance measure that gives disproportionate influence to some features or poorly separates profiles.

Two Ways to Choose Starting Centers

With random-start initialization, a common procedure selects $k$ distinct observed profiles uniformly at random as the initial centers. Another implementation samples starting coordinates from a specified distribution. These are not equivalent procedures, so an analysis should record which one was used. Random starts are simple, but several chosen profiles may lie close together, leaving other parts of the data poorly represented at the outset.

The k-means++ initialization procedure also begins with an observed profile, chosen uniformly at random. After that, it selects each new profile with probability proportional to its squared distance from the nearest center already selected. If $D(x_i)$ is that distance, the selection probability is $D(x_i)^2/\sum_{\ell=1}^{n}D(x_\ell)^2$. Thus profiles far from the existing seeds are more likely to be added. The procedure aims to spread the initial centers across the data; it does not guarantee the global optimum, nor does it guarantee that each meaningful group receives a seed.

Worked Example: A k-Means++ Selection Step

Suppose four hypothetical, one-dimensional genomic profiles have values $0,2,8,10$ in a single normalized expression coordinate, and we want $k=2$. Assume the first k-means++ center selected is $0$. The squared distances from the four profiles to their nearest selected center are $0,4,64,100$, whose sum is $168$.

The probability of selecting profile $10$ as the second center is $100/168=0.5952$. The probabilities for $2$ and $8$ are $4/168=0.02381$ and $64/168=0.3810$, respectively; profile $0$ has probability zero because it is already a center. The probabilities sum to $1$. A random choice among the remaining three observations would instead give each probability $1/3$. K-means++ makes a distant point more likely, but it can still choose $8$, and subsequent Lloyd steps can still end in a suboptimal solution.

Why Lloyd Fits Can Differ

A short calculation explains both the attraction and the limitation of Lloyd’s procedure. First hold the assignments fixed. For one cluster with $m$ profiles and mean $\bar{x}$, the sum of squared distances to any proposed center $c$ satisfies

\sum_{i=1}^{m}\|x_i-c\|^2 = \sum_{i=1}^{m}\|x_i-\bar{x}\|^2 + m\|c-\bar{x}\|^2.

To verify this identity, write $x_i-c=(x_i-\bar{x})+(\bar{x}-c)$, expand the squared norm, and sum. The cross term is zero because $\sum_i(x_i-\bar{x})=0$. The final term is nonnegative and equals zero at $c=\bar{x}$, so the mean minimizes the cluster’s squared-error contribution.

Next hold the centers fixed. Assigning each profile to its nearest center minimizes that profile’s squared-distance contribution among the available clusters. Therefore, with nonempty clusters and exact assignment and update steps, neither step increases WCSS. This is a descent argument, not a proof of global optimality: each step improves only one part of a coupled problem while holding the other part fixed.

For finite data and a deterministic tie rule that keeps a profile in its current cluster when its current center is among the nearest, the assignment process terminates at a fixed point. If an assignment changes, the profile must have a strictly closer center, so the objective decreases; there are only finitely many possible assignments. Ties require care because arbitrary tie-breaking can otherwise move profiles without lowering the objective.

Worked Example: Two Different Fixed Points

Consider nine hypothetical one-dimensional profiles with values $0,1,2,5,6,7,10,11,12$. Use two clusters and assign an exact tie to the first center. Starting centers $2$ and $10$ have midpoint $6$. The initial assignment is $\{0,1,2,5,6\}$ and $\{7,10,11,12\}$. The updated means are $ (0+1+2+5+6)/5=2.8 $ and $ (7+10+11+12)/4=10 $. Their midpoint is $6.4$, so the assignment remains unchanged: this is a fixed point.

Its WCSS is $ (7.84+3.24+0.64+4.84+10.24)+(9+0+1+4)=26.80+14=40.80 $. For example, the first term is the sum of squared deviations of $0,1,2,5,6$ from $2.8$.

Now start at centers $2$ and $12$. The midpoint is $7$, and the stated tie rule assigns $7$ to the first center. The resulting partition is $\{0,1,2,5,6,7\}$ and $\{10,11,12\}$. Its updated means are $3.5$ and $11$, with midpoint $7.25$, so this partition also remains fixed. Its WCSS is $ (12.25+6.25+2.25+2.25+6.25+12.25)+(1+0+1)=41.50+2=43.50 $.

These are distinct fixed points reached from different starts. The second has higher WCSS than the first, so it cannot be the global minimum for these data. The example demonstrates why convergence alone does not certify that a fit has found the best partition.

Empty Clusters and Practical Remedies

An empty cluster occurs when no profile is assigned to one of the $k$ centers. This can happen during initialization if seeds coincide, or during an assignment step if a center attracts no profiles. The mean of an empty cluster is undefined, so the usual center-update step cannot be applied to it. Empty clusters are not evidence that the data contain fewer than $k$ groups; they are a computational event that must be handled explicitly.

Implementations use several remedies. A common choice is to reseed the empty center at a profile far from its currently assigned center, then continue the iterations. Another is to move a profile from a large cluster, often one far from its center, into the empty cluster. Some implementations retain the old center or drop the empty cluster. Retaining a center may leave it empty again; dropping it changes the effective number of clusters. Reseeding or moving profiles can alter WCSS, so the simple nonincrease argument above applies to the ordinary assignment-and-mean steps, not automatically to every empty-cluster intervention. Record the remedy and check that the run subsequently reaches a valid, nonempty solution if $k$ nonempty clusters are required.

Other warning signs include sensitivity to small changes in starting centers, runs stopping at substantially different WCSS values, or clusters that repeatedly become tiny or empty. Such behavior can arise from a difficult objective landscape, duplicated or near-duplicated profiles, or a geometry poorly suited to the intended interpretation. It is useful to inspect cluster sizes, convergence status, and the partition itself, not just the lowest objective value.

Worked Example: Reading Repeated-Fit Results

Suppose the nine profiles in the preceding example are fit with $k=2$ using 12 random starts and, separately, 12 k-means++ starts. The following is a hypothetical run summary; the two methods use the same profiles, feature scaling, tie rule, and convergence settings.

Initialization	Fits at WCSS 40.80	Fits at WCSS 43.50	Lowest WCSS
Random starts	9 of 12	3 of 12	40.80
K-means++	11 of 12	1 of 12	40.80

For the random-start fits, the mean WCSS across runs is $ (9\times40.80+3\times43.50)/12=(367.20+130.50)/12=41.475 $. For the k-means++ fits it is $ (11\times40.80+1\times43.50)/12=(448.80+43.50)/12=41.025 $. In this hypothetical summary, k-means++ more often reaches the lower of these two observed objectives. It does not prove that k-means++ will always do better, or that $40.80$ is the global optimum.

The two observed partitions differ only in which cluster contains profile $7$. To compare partitions across runs, cluster labels should not be compared literally: “cluster 1” and “cluster 2” can switch names without changing the partition. Instead, compare which pairs of profiles are grouped together, or use a label-invariant partition comparison. If repeated fits yield different pair groupings, report that the partition is sensitive to initialization rather than presenting one run as uniquely determined.

Choosing and Reporting an Initialization Strategy

K-means++ is a useful default when the goal is to obtain well-spread initial centers, while random starts remain a simple baseline. Neither method removes the need for repeated fits. A practical analysis can run each method multiple times, retain the converged fit with the smallest WCSS among the attempted runs, and report the number of starts, the initialization method, empty-cluster handling, and the range or distribution of final WCSS values. If distinct partitions have similar WCSS, the solution may be sensitive even when the objective values look nearly identical.

A lower WCSS is meaningful only in comparisons made on the same profiles, features, scaling, distance definition, and fixed $k$. It is not by itself evidence that the chosen $k$ is appropriate; the separate question of selecting $k$ requires other criteria. Nor does repeated initialization assess how partitions would change under new samples or perturbations of the data. It isolates sensitivity to starting centers under the specified dataset and fitting procedure.

A common mistake is to treat the converged fit from one run as the answer because Lloyd’s algorithm has stopped. Convergence means only that another assignment-and-update cycle does not change that fit. The correction is to distinguish convergence from global optimality: use repeated starts, compare final objectives and partitions, and describe the observed sensitivity.

Key takeaway: Initialization changes the route through k-means’ nonconvex objective. K-means++ often spreads seeds more effectively than uniform random starts, but neither guarantees the global solution. Repeated fits reveal whether the partition depends on the start; empty clusters require an explicit, documented remedy.

Check Your Understanding

Answer each question, then compare with the solutions below.

For profiles at $0,2,8,10$, if the first k-means++ center is $0$, what is the probability that $10$ is selected second?
Why does updating a nonempty cluster center to its mean not increase its squared-error contribution?
For the nine-profile example, what is the WCSS of the partition with clusters $\{0,1,2,5,6\}$ and $\{7,10,11,12\}$?
What does it mean if repeated starts converge to different partitions with similar WCSS?
Why must an empty cluster be handled before applying the ordinary mean-update step?

Solutions. (1) The squared distances from $0$ are $0,4,64,100$, totaling $168$, so the probability is $100/168=0.5952$. (2) The identity $ \sum_i\|x_i-c\|^2=\sum_i\|x_i-\bar{x}\|^2+m\|c-\bar{x}\|^2 $ shows that the mean minimizes the sum. (3) The cluster deviations give $26.80$ and $14.00$, so WCSS is $40.80$. (4) The fit is sensitive to initialization in its assignments, even though its objective is similar across runs; the partitions should be compared without relying on cluster-label names. (5) A cluster with no assigned profiles has no defined sample mean, so the ordinary update cannot calculate its center.