Why the Initial Centers Matter
K-means is an iterative procedure: it assigns observations to the nearest centers, recalculates each center as the mean of its assigned observations, and repeats. Before the first assignment, however, the centers must be supplied. When those centers are chosen randomly, the first partition depends on the particular random draw.
This randomness concerns the algorithm’s starting point, not uncertainty about an observation’s measured value. For a fixed data set and fixed initial centers, the first assignments are determined by distances, apart from ties. Different initial centers can put the same observations in different first clusters, which can in turn change the centers calculated at the first update.
One common approach is to choose \(k\) observations at random and use their feature vectors as the initial centers. Another is to generate center locations randomly within the feature space. These are distinct procedures: a selected observation is an actual data point, while a generated location need not coincide with any observation. Unless stated otherwise, examples below use ordinary Euclidean distance on the displayed coordinates and specify the chosen initial centers.
When \(k\) observations are sampled uniformly without replacement from \(n\) distinct observations, each of the \(\binom{n}{k}\) possible subsets has the same probability. The actual center locations—and therefore the first partition—are random before the draw. Once the centers have been drawn, the assignment rule is deterministic, except for ties.
Distance Determines the First Assignment
For each observation, calculate its squared distance to each initial center and choose the smallest. Squared distances give the same nearest center as ordinary distances because squaring preserves the order of nonnegative distances. They also avoid square roots. In two dimensions, for \(x=(x_1,x_2)\) and \(\mu=(\mu_1,\mu_2)\), the squared distance is \((x_1-\mu_1)^2+(x_2-\mu_2)^2\).
With two centers, the set of points equally far from the centers forms the boundary between their nearest-center regions. A short derivation shows why the boundary is a perpendicular bisector. For centers \(a\) and \(b\), a point \(x\) is tied when the squared distances are equal:
Cancel \(x\mathbin{\cdot}x\) and rearrange to obtain \(2x\mathbin{\cdot}(b-a)=b\mathbin{\cdot}b-a\mathbin{\cdot}a\). This is a linear equation in \(x\), so the tie boundary is a line in two dimensions (a hyperplane in higher dimensions). In one dimension, it is the midpoint \((a+b)/2\). The nearer-center regions lie on opposite sides of this boundary.
Worked Example: Assigning a Two-Dimensional Data Set
A hypothetical portfolio study represents six policy groups by points \(A=(0,0)\), \(B=(1,0)\), \(C=(0,2)\), \(D=(4,0)\), \(E=(5,0)\), and \(F=(4,2)\). For \(k=2\), suppose \(A\) and \(D\) are selected uniformly as the initial observations. Find the first partition, update the centers once, and calculate the resulting within-cluster sum of squares (WCSS), the sum of squared distances from observations to their cluster means.
Method. Compare each point’s squared Euclidean distance to \(\mu_1^{(0)}=A=(0,0)\) and \(\mu_2^{(0)}=D=(4,0)\). The calculations are:
| Point | Distance squared to \(A\) | Distance squared to \(D\) | First assignment |
|---|---|---|---|
| A=(0,0) | \(0^2+0^2=0\) | \((-4)^2+0^2=16\) | Cluster 1 |
| B=(1,0) | \(1^2+0^2=1\) | \((-3)^2+0^2=9\) | Cluster 1 |
| C=(0,2) | \(0^2+2^2=4\) | \((-4)^2+2^2=20\) | Cluster 1 |
| D=(4,0) | \(4^2+0^2=16\) | \(0^2+0^2=0\) | Cluster 2 |
| E=(5,0) | \(5^2+0^2=25\) | \(1^2+0^2=1\) | Cluster 2 |
| F=(4,2) | \(4^2+2^2=20\) | \(0^2+2^2=4\) | Cluster 2 |
Thus the first partition is \(C_1=\{A,B,C\}\) and \(C_2=\{D,E,F\}\). There are no ties: every row has a strictly smaller squared distance for its assigned center.
Update. The mean of \(A,B,C\) is \(\mu_1^{(1)}=((0+1+0)/3,(0+0+2)/3)=(1/3,2/3)\). The mean of \(D,E,F\) is \(\mu_2^{(1)}=((4+5+4)/3,(0+0+2)/3)=(13/3,2/3)\).
Check the WCSS. In cluster 1, the squared distances to \((1/3,2/3)\) are \(5/9\) for \(A\), \(5/9\) for \(B\), and \(20/9\) for \(C\). Their sum is \(30/9=10/3\). In cluster 2, the squared distances to \((13/3,2/3)\) are \(5/9\) for \(D\), \(5/9\) for \(E\), and \(20/9\) for \(F\), also totaling \(10/3\). The updated WCSS is \(10/3+10/3=20/3\).
Common mistake to avoid: Do not calculate this WCSS using the initial centers \(A\) and \(D\). Those centers determine the assignments; after the update, WCSS is measured from the cluster means. The computed value \(20/3\) checks the updated partition and centers.
Different Starts, Different First Partitions
The effect of random initialization can be seen by holding the observations fixed and changing only the starting centers. In one dimension, the boundary between two distinct centers is their midpoint. This makes the first assignments easy to compare, but the same principle applies in higher dimensions using squared Euclidean distances.
Worked Example: Comparing Two Random Starts
A hypothetical data set consists of the one-dimensional observations \(0,3,4,7,10\), with \(k=2\). Compare the first partitions for the two possible starts \((0,7)\) and \((0,10)\). For each partition, calculate the cluster means and WCSS after the mean update.
Start 1: centers 0 and 7. The midpoint is \((0+7)/2=3.5\). The squared-distance comparisons put 0 and 3 with center 0, since their distances are \(0<49\) and \(9<16\). They put 4, 7, and 10 with center 7, since their distances to 7 are \(9<16\), \(0<49\), and \(9<100\), respectively. The partition is \(\{0,3\}\) and \(\{4,7,10\}\).
The updated means are \((0+3)/2=1.5\) and \((4+7+10)/3=7\). The first cluster contributes \((0-1.5)^2+(3-1.5)^2=2.25+2.25=4.5\) to WCSS. The second contributes \((4-7)^2+(7-7)^2+(10-7)^2=9+0+9=18\). The updated WCSS is \(4.5+18=22.5\).
Start 2: centers 0 and 10. The midpoint is \((0+10)/2=5\). The comparisons put 0, 3, and 4 with center 0: the respective squared distances are \(0<100\), \(9<49\), and \(16<36\). They put 7 and 10 with center 10: the respective comparisons are \(49>9\) and \(100>0\). The partition is \(\{0,3,4\}\) and \(\{7,10\}\).
The updated means are \((0+3+4)/3=7/3\) and \((7+10)/2=8.5\). The first cluster contributes \((0-7/3)^2+(3-7/3)^2+(4-7/3)^2=(49+4+25)/9=78/9=26/3\). The second contributes \((7-8.5)^2+(10-8.5)^2=2.25+2.25=4.5\). The updated WCSS is \(26/3+4.5=52/6+27/6=79/6\), or \(13.1667\) to four decimal places.
The starts produce different first partitions even though the observations and \(k\) are unchanged. Their updated WCSS values are \(22.5\) and \(79/6\), respectively. This comparison concerns the two partitions calculated here; it does not establish what any further iterations will produce.
Common mistake to avoid: Do not assign the observation 4 by comparing its ordinary distances without checking the midpoint or the squared distances. With centers 0 and 10, its squared distances are 16 and 36, so it belongs to the center at 0. The boundary is 5, not 4 or 6.
Chance of a Particular Initial Partition
When the initial centers are sampled uniformly from observed points, a probability calculation can quantify how likely a specified start is. The calculation must use the stated sampling rule. In particular, sampling \(k\) observations without replacement gives equally likely subsets, not ordered lists of centers, unless the problem explicitly treats the order as relevant.
Worked Example: Probability of a Split Across the Gap
A hypothetical data set has one-dimensional values \(0,2,5,9\). Two distinct observations are selected uniformly without replacement as the initial centers. Find the probability that the first assignment separates the two lower values from the two higher values, giving clusters \(\{0,2\}\) and \(\{5,9\}\).
Method. There are \(\binom{4}{2}=6\) equally likely unordered pairs of initial centers. For each pair, use its midpoint as the assignment boundary.
- Centers \((0,2)\): boundary 1, giving \(\{0\}\) and \(\{2,5,9\}\).
- Centers \((0,5)\): boundary 2.5, giving \(\{0,2\}\) and \(\{5,9\}\).
- Centers \((0,9)\): boundary 4.5, giving \(\{0,2\}\) and \(\{5,9\}\).
- Centers \((2,5)\): boundary 3.5, giving \(\{0,2\}\) and \(\{5,9\}\).
- Centers \((2,9)\): boundary 5.5, giving \(\{0,2\}\) and \(\{5,9\}\).
- Centers \((5,9)\): boundary 7, giving \(\{0,2,5\}\) and \(\{9\}\).
Four of the six equally likely pairs give the requested split. Therefore the probability is \(4/6=2/3\), or \(0.6667\) to four decimal places.
Check. The two pairs lying wholly within one side of the gap produce a singleton cluster at an endpoint. The other four pairs put the boundary between 2 and 5, as required.
Common mistake to avoid: Do not count the ordered pairs \((0,5)\) and \((5,0)\) as separate outcomes when the selection is an unordered sample of two centers. Counting ordered pairs would give 12 outcomes and 8 favorable outcomes, which happens to yield the same probability here, but the sample space must match the stated sampling rule.
What to Keep Separate
Random initialization determines the centers used for the first assignment; it does not itself determine the final clustering. After assigning observations, the algorithm updates the centers to the cluster means. Later assignments use those updated centers, not the original random choices. Consequently, an initial center should not be confused with a final cluster mean.
Also distinguish two calculations:
- Assignment: compare an observation’s distances to the current centers and assign it to a nearest one.
- WCSS: sum squared distances from observations to their cluster means for a specified partition.
These calculations use squared distances, but they need not use the same reference points. In the first assignment, the reference points are the initial centers. After the update, the WCSS is calculated from the new means. If a problem specifies a tie, apply its tie-breaking rule; do not silently assign the observation to whichever cluster makes later arithmetic easier.
Check Your Understanding
For each problem, use squared Euclidean distance and state the first partition before carrying out any requested update.
- For the one-dimensional observations \(1,3,8\), the initial centers are 1 and 8. Find the assignment boundary and the first partition. (Answer: boundary \(4.5\); clusters \(\{1,3\}\) and \(\{8\}\).)
- For \(A=(1,1)\), \(B=(2,1)\), \(C=(5,2)\), and \(D=(6,2)\), take \(A\) and \(C\) as initial centers. Calculate the squared distances needed to assign \(B\) and \(D\), and give the full partition. (Answer: \(B\) has squared distances 1 and 10; \(D\) has squared distances 26 and 1; clusters \(\{A,B\}\) and \(\{C,D\}\).)
- For values \(0,2,5,9\), use initial centers 0 and 5. Give the first partition and the updated mean of each cluster. (Answer: clusters \(\{0,2\}\) and \(\{5,9\}\); updated means 1 and 7.)
- From the observations \(0,1,9,10\), choose two distinct initial centers uniformly without replacement. What is the probability that the first partition is \(\{0,1\}\) and \(\{9,10\}\)? (Answer: \(4/6=2/3=0.6667\) to four decimal places.)
- For \(0,2,6,10\), use initial centers 0 and 10. Find the first partition, update its centers, and calculate the updated WCSS. (Answer: clusters \(\{0,2\}\) and \(\{6,10\}\); updated means 1 and 8; WCSS \(=1+1+4+4=10\).)