K-Means++ Seeding And Spread-Out Starts

Why the Starting Centers Matter

K-means repeatedly assigns observations to their nearest center and then updates each center to the mean of its assigned observations. As established in the earlier material on k-means, these steps seek to reduce the within-cluster sum of squares (WCSS). The starting centers matter because the first assignments depend on them. If several starting centers are close together, a spread-out part of the data may initially have no nearby center.

Random initialization chooses starting centers without using the geometry of the data. K-means++ changes the selection rule after the first center: observations farther from the centers already chosen receive greater sampling probability. This tends to spread the seeds across the data, while retaining randomness. It is a way to construct a more informed start, not a guarantee of the best final clustering.

The method uses the same Euclidean distance and squared-error objective as ordinary k-means. The data and distance scale must therefore be appropriate for the problem. K-means++ does not itself standardize variables or resolve questions about which features should have more influence.

Definition: For observations \(\mathbf{x}_1,\ldots,\mathbf{x}_n\) and a chosen number \(k\) of clusters, k-means++ selects the first center uniformly from the observations. For each subsequent center, it selects observation \(\mathbf{x}_i\) with probability proportional to \(D_i^2\), where \(D_i\) is the Euclidean distance from \(\mathbf{x}_i\) to its nearest already-selected center. The selected observation itself becomes a starting center.

The Distance-Weighted Sampling Rule

Suppose the current set of selected centers is \(S\). For each observation, calculate its distance to every center in \(S\), and let \(D_i\) be the smallest of those distances. The probability of choosing observation \(i\) as the next center is

P(\text{choose } \mathbf{x}_i\mid S) = \frac{D_i^2}{\displaystyle\sum_{r=1}^{n}D_r^2}.

The denominator is the total squared distance from the observations to their nearest selected center. It normalizes the nonnegative weights so that the probabilities sum to one. An observation already at a selected center has \(D_i=0\), so it has zero probability of being selected again while any positive weights remain.

To implement the rule by hand, calculate all the \(D_i^2\) values, add them, divide each value by the total, and use a stated random draw or cumulative probability intervals to identify the selected observation. Repeat the calculation after adding each new center: the distances and probabilities can change at every step.

Choose the first center.
Select one of the \(n\) observations uniformly, so each observation has probability \(1/n\) at this step.

Calculate nearest-center distances.
For each observation, find its Euclidean distance to the closest center selected so far, then square that distance.

Normalize the weights and draw.
Divide each squared distance by the sum of all squared distances, and sample one observation using these probabilities.

Continue until there are \(k\) centers.
After each selection, recalculate nearest-center distances before making the next draw.

Why the Squared Distance Appears

The justification starts from the objective k-means is trying to reduce. Given the currently selected centers, assign each observation to its nearest one. The current total squared distance to those centers is

\Phi(S)=\sum_{i=1}^{n}D_i^2.

Each observation contributes \(D_i^2\) to this current quantity. Therefore, assigning sampling weight \(D_i^2\) gives more chance to observations that currently contribute more to the squared-distance total. Normalizing those contributions produces valid probabilities:

\sum_{i=1}^{n}\frac{D_i^2}{\sum_{r=1}^{n}D_r^2} = \frac{\sum_{i=1}^{n}D_i^2}{\sum_{r=1}^{n}D_r^2} =1, \qquad \text{if } \sum_{r=1}^{n}D_r^2>0.

This explains the rule, but it does not mean that selecting an observation reduces WCSS by exactly its squared distance: the next center changes nearest-center assignments, and its effect depends on all the data. The rule makes high-contribution regions more likely to receive a seed; it does not calculate the optimal next center directly.

Worked Example: A One-Dimensional Second-Center Draw

Consider four observations at \(0,2,8,10\), and set \(k=2\). Suppose the first uniformly selected center is \(2\). A random number \(U=0.80\) is used for the second-center draw, with cumulative probability intervals ordered as \(0,2,8,10\). Find the second center and the WCSS for these two initial centers.

Method. Use squared distances from the first center as sampling weights. This avoids treating distance itself, rather than squared distance, as the k-means++ weight.

Step 1: Calculate squared distances to \(2\). The squared distances for observations \(0,2,8,10\) are respectively

(0-2)^2=4,\quad (2-2)^2=0,\quad (8-2)^2=36,\quad (10-2)^2=64.

Their total is \(4+0+36+64=104\). Thus the selection probabilities, in the same order, are \(4/104\), \(0/104\), \(36/104\), and \(64/104\). The cumulative probabilities are approximately \(0.0385,\ 0.0385,\ 0.3846,\ 1.0000\).

Step 2: Use the draw. Since \(0.3846 < 0.80 \leq 1.0000\), the draw selects observation \(10\). The two initial centers are \(2\) and \(10\).

Step 3: Check their WCSS. The nearest-center squared distances for observations \(0,2,8,10\) are \(4,0,4,0\), respectively. Therefore the initial WCSS is \(4+0+4+0=8\).

As a contrast, centers \(0\) and \(2\) would give squared distances \(0,0,36,64\), for a WCSS of \(100\). The example shows why a spread-out start can matter, but the k-means++ draw is probabilistic: it favors a distant observation without ensuring that every draw produces a good result.

Updating the Weights After Each Draw

The weights are not fixed once the first center is chosen. Each new center can sharply reduce the distances for observations near it, changing the distribution used for the next draw. In two or more dimensions, calculate Euclidean distances using all coordinates included in the clustering.

Worked Example: Selecting Three Centers in Two Dimensions

Five observations have coordinates \(A=(0,0)\), \(B=(2,0)\), \(C=(0,2)\), \(D=(8,0)\), and \(E=(10,0)\). Set \(k=3\). Suppose the first draw selects \(A\), the next random number is \(U=0.70\), and the third draw uses \(U=0.80\). For each draw, use the listed order \(A,B,C,D,E\). Find all three centers and the initial WCSS.

Method. Recalculate each observation’s squared distance to its nearest selected center before each draw. This avoids reusing the first set of probabilities after the centers have changed.

Step 1: Weights after selecting \(A\). The squared distances to \(A\) are \(0,4,4,64,100\), since, for example, \(D\)'s squared distance is \((8-0)^2+(0-0)^2=64\). The total is \(172\). The probabilities are therefore \(0/172,4/172,4/172,64/172,100/172\). Their cumulative values are approximately \(0.0000,0.0233,0.0465,0.4186,1.0000\). Since \(0.4186 < 0.70 \leq 1.0000\), the second center is \(E\).

Step 2: Update the weights using \(A\) and \(E\). The nearest-center squared distances for \(A,B,C,D,E\) are now \(0,4,4,4,0\). For \(D\), for example, the squared distance to \(E\) is \((8-10)^2=4\), which is less than its squared distance \(64\) to \(A\). The total weight is \(12\), so \(B,C,D\) each have probability \(4/12=1/3\), while \(A,E\) have probability zero. The cumulative probabilities are \(0,1/3,2/3,1,1\). Because \(2/3 < 0.80 \leq 1\), the third center is \(D\).

Step 3: Compute the initial WCSS. With centers \(A,E,D\), observation \(B\) is nearest to \(A\), at squared distance \(4\), and \(C\) is nearest to \(A\), also at squared distance \(4\). Observations \(A,D,E\) each have squared distance zero to a center. The WCSS is \(4+4=8\).

The total weight fell from \(172\) to \(12\) after choosing \(E\), because that center is close to the observations at \(D\) and \(E\). The remaining draw then sampled among \(B,C,D\), the observations still contributing positive squared distance.

Repeated Values, Edge Cases, and Limits

The sampling rule applies to observations, not just to distinct coordinate values. If several observations have identical coordinates, they have the same distance to every center and therefore the same individual weight. On the first draw, identical observations can increase the chance that their shared location is selected because each is a separate candidate. After that location is selected as a center, all observations at that location have zero weight.

The formula requires a positive total squared distance. If every observation is already at a selected center, then \(\sum_iD_i^2=0\) and the probability formula has a zero denominator. This occurs, for example, when the number of selected centers equals the number of distinct data locations. If fewer than \(k\) distinct locations exist, it is not possible to obtain \(k\) distinct coordinate centers from the data. Implementations may handle such cases with a special rule; the ordinary positive-weight sampling formula does not define another draw.

Worked Example: Duplicate Values and a Zero-WCSS Start

The one-dimensional observations are \(0,0,4,4,10,10\), with \(k=3\). Suppose the first draw selects the first observation at \(0\). For the second draw use \(U=0.50\), with the observations in the order shown. For the third draw use \(U=0.75\). Find the three centers and check the final WCSS.

Method. Treat the six rows as six observations, including repeated values, and recalculate the distance weights after each draw. This avoids counting a repeated coordinate as only one observation when the sampling rule is over the data rows.

Step 1: Select the second center. From center \(0\), the squared distances are \(0,0,16,16,100,100\). Their sum is \(232\), so the probabilities are \(0,0,16/232,16/232,100/232,100/232\). The cumulative probability after the two observations at \(4\) is \(32/232\approx0.1379\); after the first observation at \(10\), it is \(132/232\approx0.5690\). Thus \(0.1379 < 0.50 \leq 0.5690\), and the draw selects the first \(10\).

Step 2: Select the third center. With centers \(0\) and \(10\), the squared distances are \(0,0,16,16,0,0\), with total \(32\). Each observation at \(4\) has probability \(16/32=0.5\); all other observations have probability zero. The cumulative probability after the first \(4\) is \(0.5\), and after the second \(4\) it is \(1\). Since \(0.5 < 0.75 \leq 1\), the draw selects the second \(4\).

Step 3: Check the result. The centers are \(0,10,4\). Every observation equals one of these centers, so all six nearest-center squared distances are zero and the WCSS is \(0\).

This start gives zero WCSS because the data have exactly three distinct locations and the three centers cover all of them. If another center were requested, the total weight would be zero and the usual sampling formula would not apply.

What the Method Does—and Does Not—Promise

The practical benefit is targeted initialization: after the first center, regions that remain far from the selected centers are more likely to receive a seed. This can reduce the risk of placing all the starting centers close together. The method remains random, however, and the initial centers are only the input to the subsequent k-means assignment and update steps.

K-means++ does not guarantee that the final clustering has the smallest possible WCSS. Nor does one favorable-looking set of seeds prove that the resulting clusters are substantively appropriate. Interpret the method as a principled way to choose starting centers, not as a replacement for checking the data, the chosen value of \(k\), or the resulting assignments. This initialization technique is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.

Use squared distance. The weight is \(D_i^2\), not \(D_i\).
Recompute after every center. A new center can change the nearest-center distance for many observations.
Keep the sampling unit clear. Repeated rows are separate observations even when their coordinates match.
Check the denominator. If the total squared distance is zero, the standard probability formula cannot be used for another draw.
Do not infer a guarantee. Spread-out seeds can be helpful, but k-means++ does not ensure globally optimal final clusters.

Key takeaway: Choose the first observation uniformly, then repeatedly sample an observation with probability \(D_i^2/\sum_rD_r^2\), recalculating \(D_i\) as the distance to its nearest selected center at every step.

Check Your Understanding

For each question, treat the stated random number as a draw on the cumulative intervals in the listed observation order.

There are observations at \(1,3,9\). The first center is \(3\). What is the probability of selecting \(9\) as the second center? (Answer: \(0.9000\))
Points \(P=(0,0)\), \(Q=(0,3)\), and \(R=(4,0)\) have first center \(P\). What are the squared-distance weights, and which point is selected by \(U=0.50\) in order \(P,Q,R\)? (Answer: weights \(0,9,16\); select \(R\))
Observations in order are \(1,1,5,9\). The first center is the first \(1\). The second draw uses \(U=0.10\). Which observation is selected, and what is its selection probability? (Answer: \(5\), with probability \(16/80=0.2000\))
Suppose all observations have the same coordinates and one center has already been selected. What is the total squared-distance weight, and can the ordinary k-means++ rule choose another center using its probability formula? (Answer: total weight \(0\); no, the formula has a zero denominator)
Observations are \(0,4,5\), the first center is \(0\), and the second draw uses \(U=0.60\) in the listed order. Which point becomes the second center, and what is the WCSS for those two centers? (Answer: \(5\); WCSS \(=1\))

What You'll Learn