Finding Structure Without Labels
Grouping Around Centres
Last timeDeciding What Close Means
Alternating between assigning each point to its nearest centre and moving each centre to the average of its points is the most used grouping method there is, and its shape assumption is built in.
Two steps, repeated
Pick a number of groups. Put that many centres somewhere. Then repeat two
steps until nothing moves.
Assign every point to whichever centre is nearest. Move every centre to the
average of the points assigned to it.
That is the whole method. It is the most used grouping procedure in existence,
it takes fifteen lines, and both of its serious limitations are consequences
of the first of those two steps.
| step | round | what the assignment changed | where the centres moved to | total spread |
|---|---|---|---|---|
| 1 | start | centres placed at two random points | (2.0, 3.0) and (6.0, 5.0) | 48.6 |
| 2 | 1 | 7 points to the first, 5 to the second | (2.6, 2.4) and (6.8, 6.1) | 21.3 |
| 3 | 2 | one point moved across | (2.3, 2.2) and (6.5, 5.8) | 19.1 |
| 4 | 3 | one point moved back | (2.4, 2.3) and (6.6, 5.9) | 19.0 |
| 5 | 4 | nothing changed | unchanged | 19.0 |
def group(points, k, rounds=100):
centres = [points[i] for i in random_distinct_indices(len(points), k)]
for _ in range(rounds):
assigned = [nearest(p, centres) for p in points] # step one
moved = []
for g in range(k):
held = [p for p, a in zip(points, assigned) if a == g]
moved.append(average(held) if held else centres[g]) # step two
if moved == centres: break
centres = moved
return centres, assigned
print("assign to the nearest centre, move each centre to its average, repeat until still")It must stop, and it need not be right
Each step can only make the total spread smaller or leave it alone.
Reassigning a point to a nearer centre reduces the total by definition. Moving
a centre to the average of its points is the position that minimises the
squared distances to them, so that step reduces the total too.
There are finitely many ways to assign points to groups, the total never
increases, and so the loop must stop.
That is a guarantee about termination and nothing more. It does not say the
arrangement reached is the best one, and usually it is not.
- the centre of group g, which is the average of its points
- how many points are in group g
- squared straight line distance, which is where the previous lesson enters
Read that quantity carefully and the behaviour of the method follows from it.
It rewards groups that are compact, which means roughly round, and because
squared distances grow fast it also prefers groups of similar size: a large
loose group contributes an enormous amount and the method will split it.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents