Basis Lab

Answers · How models work

Why does k-means split one long stretched-out group into two?

In shortBecause k-means keeps only one centre per group, so a long group's ends end up closer to a second centre and the group is cut across its length.

Because k-means describes a group only by one centre and gives that centre every point nearer to it than to any other centre. A long stretched group has ends that are far from one centre and closer to a second, so when two groups are asked for the method cuts the long group across its length rather than leaving it whole.

The arithmetic of a long group

Put ten points on a line at 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and ask for two groups. If one centre were allowed, its best position is the average 4.5, and the total squared distance from the points to it is 82.5. With two centres the assignment step sends 0 to 4 to one centre and 5 to 9 to the other. The move step puts the centres at the averages 2 and 7. Within the first half the squared distances from 2 are 4, 1, 0, 1, 4, which sum to 10; the second half gives the same 10. The total falls from 82.5 to 20. The number of groups is fixed at two, so the method never compares this with one group; the comparison shows where the two centres want to sit.

W=∑g=1k∑i∈g∥xi−cg∥2,W1=∑i=09(i−4.5)2=82.5,W2=∑i=04(i−2)2+∑i=59(i−7)2=10+10=20.W=\sum_{g=1}^{k}\sum_{i\in g}\lVert x_i-c_g\rVert^2,\qquad W_1=\sum_{i=0}^{9}(i-4.5)^2=82.5,\qquad W_2=\sum_{i=0}^{4}(i-2)^2+\sum_{i=5}^{9}(i-7)^2=10+10=20.
FIG 1Where the two centres land on ten points
group Agroup B4680point 02centre 24.5boundary 4.57centre 79point 9position along the stretched group
The boundary between the two groups is the midpoint 4.5 between the centres 2 and 7. The cut runs across the length of the stretched group, not along it.

This is the whole reason. The assignment step does not look at the shape of a group. It asks one question for each point: which centre is nearer? For two centres c1c_1 and c2c_2, the points that go to c1c_1 satisfy the inequality below. Expand the squares and the ∥x∥2\lVert x\rVert^2 terms cancel, leaving a half-plane. With more centres the region belonging to a centre is an intersection of half-planes, so its boundary is made of straight pieces. A straight boundary placed inside a long group must cut across it; it cannot bend to follow the group's length.

∥x−c1∥2≤∥x−c2∥2  ⟺  2x⋅(c2−c1)≤∥c2∥2−∥c1∥2.\lVert x-c_1\rVert^2\le\lVert x-c_2\rVert^2 \iff 2x\cdot(c_2-c_1)\le \lVert c_2\rVert^2-\lVert c_1\rVert^2.

The natural guess is that k-means is searching for the groups a person would draw, so a single long smear should count as one group. That guess fails because the method is not searching over shapes. It minimises the total squared distance to the centres with the number of groups fixed in advance. If you ask for two groups it must return two, and the cheapest way to return two for a long smear is two shorter pieces. It is not finding evidence of two groups; it is reducing a penalty that grows with the square of distance. The long group's ends are exactly the points that make that penalty large.

Why length is split and width is not

Suppose the same ten points have a small spread in the other direction. Two centres placed side by side across that small width would leave each group containing the full run from 0 to 9. Each group would still have the x deviations that gave 82.5, so the x part alone would be twice 82.5, which is 165. Centres placed along the length instead remove most of the x deviation, leaving 20. The objective has no term that rewards keeping a long group in one piece, so it takes the arrangement that makes the squared distances smaller. A long cluster has more room to reduce squared distance by being cut along its length than across its width.

Setting the number of groups to one prevents any split, and choosing k to match the number of groups you believe exist helps, but it does not guarantee a long group stays whole. If another arrangement, such as splitting the long group and merging two nearby compact groups, gives a smaller total squared distance, the loop will take it. Restarting from different centres changes which local minimum is reached. It does not change the set of possible shapes: every answer is made of nearest-centre regions with straight boundaries. The shape assumption is in the assignment rule, so more restarts cannot remove it.

The failure is not that the loop stopped too early. The loop did its job: it found two straight-sided regions that reduce the total squared distance. If the group is long, that is what the job looks like.

Worth keeping

  • k-means always returns exactly the number of groups you ask for; it never decides that a long group should stay whole.
  • The region belonging to a centre is the set of points closer to it than to any other centre, so its boundary is straight and cannot follow a stretched shape.
  • Restarting with different centres can change which split is found, but it cannot remove the shape assumption built into nearest-centre assignment.

Where this goes next

This question is one step of Finding Structure Without Labels, a course that works through its subject from the beginning. The page that teaches this part of it is Grouping Around Centres, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. How many principal components should I keep?There is no single correct number: keep the smallest number whose combined variation you can afford to lose, and report the share you discarded.
  2. How can I tell whether my clusters are real or just something the algorithm made up?Check whether clusters survive refitting on different rows and whether they predict a held-out column; a convincing 2D plot is weak evidence because such plots can invent clusters.
  3. How does DBSCAN decide that some points are noise and just leave them out?A point is left out when too few neighbours lie close to it and no dense point is close enough to attach it to a group.
  4. Why can't I just measure accuracy on data that has no labels?There is no accuracy to measure, because accuracy compares predictions with true answers and unlabelled data has none.
  5. Why does the model get stuck repeating the same sentence over and over?The model is not stuck in a memory loop: once it has written a phrase, that phrase is in its context and makes writing it again more likely, so a decoder that always picks the top word cannot leave.
  6. Why does diffusion add Gaussian noise instead of any random corruption?Diffusion adds Gaussian noise because Gaussian errors combine exactly: each step keeps the spread fixed and gives a closed-form noisy picture at any later step, which makes the reverse step learnable.

Read alongside