Unit 10: Groups Nobody Labelled

Where do labels come from?

People. Somebody looked at every fruit and wrote "apple" next to it, and that is slow, expensive and often impossible. Nobody has labelled every photo on the internet, or every song, or what every shopper is like.

So here is the fruit again with the answers torn off. Six pairs of numbers, and nothing else.

Python

fruits = [[150, 2], [170, 3], [140, 1], [180, 7], [165, 8], [190, 9]]

for f in fruits:
    print(f)

It prints

[150, 2]
[170, 3]
[140, 1]
[180, 7]
[165, 8]
[190, 9]

You can still see the two clumps

Three fruits are light and smooth. Three are heavy and bumpy. No label says so — it is just that things near each other on the grid tend to be the same sort of thing.

Finding those clumps without being told is called clustering, and learning with no labels at all is unsupervised learning.

The middle of a group

Everything below needs one idea: the centre of a group is the average of its points. Add up each column, divide by how many there are, and you have the spot the group sits around — which may be where no actual fruit is.

Python

group = [[150, 2], [170, 3], [140, 1]]

weight = sum(f[0] for f in group) / len(group)
bump = sum(f[1] for f in group) / len(group)
print(round(weight, 1), round(bump, 1))

It prints

153.3 2.0

And scaling still matters

Distances are about to decide everything, so grams must not shout over bumpiness — the trap from unit 2. Every point below is squashed to between 0 and 1 first, using the same scale you wrote there.

Python

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

for f in [[150, 2], [190, 9]]:
    print(scale(f))

It prints

[0.2, 0.125]
[1.0, 1.0]

Start with two guesses

Decide how many groups you want — call it k — and drop that many centres anywhere at all. Ours start in opposite corners of the grid, at 0, 0 and 1, 1.

They are wrong. That is fine. The whole method is a way of being less wrong each round.

Step one: everybody joins the nearer centre

Measure each fruit to both centres and put it with whichever is closer. That is the distance from unit 2, doing its third job in this track.

Python

import math

fruits = [[150, 2], [170, 3], [140, 1], [180, 7], [165, 8], [190, 9]]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

centres = [[0.0, 0.0], [1.0, 1.0]]
groups = [[], []]
for f in fruits:
    point = scale(f)
    near = 0
    if distance(point, centres[1]) < distance(point, centres[0]):
        near = 1
    groups[near].append(f)

print("group 1:", groups[0])
print("group 2:", groups[1])

It prints

group 1: [[150, 2], [170, 3], [140, 1]]
group 2: [[180, 7], [165, 8], [190, 9]]

Step two: every centre moves to the middle of its group

The corners were only ever a guess. Now that each centre has some fruit, it slides to the average of it — into the middle of the clump it collected.

Python

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

groups = [
    [[150, 2], [170, 3], [140, 1]],
    [[180, 7], [165, 8], [190, 9]],
]

centres = []
for group in groups:
    weight = sum(scale(f)[0] for f in group) / len(group)
    bump = sum(scale(f)[1] for f in group) / len(group)
    centres.append([round(weight, 2), round(bump, 2)])

print(centres)

It prints

[[0.27, 0.12], [0.77, 0.88]]

Then do it again

Assign, move, assign, move. Each round the centres sit better and the groups change less, until a round comes along where nothing moves at all — and then no later round can change anything either, so you stop.

This is k-means: k centres, each one the mean of its group.

The whole thing, until it stops

Assign and move in a loop, and stop when the new centres are identical to the old ones. Two rounds is all this fruit needs.

Python

import math

fruits = [[150, 2], [170, 3], [140, 1], [180, 7], [165, 8], [190, 9]]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def assign(centres):
    groups = []
    for c in centres:
        groups.append([])
    for f in fruits:
        point = scale(f)
        near = 0
        for i in range(len(centres)):
            if distance(point, centres[i]) < distance(point, centres[near]):
                near = i
        groups[near].append(f)
    return groups

def move(groups, centres):
    out = []
    for i in range(len(groups)):
        if len(groups[i]) == 0:
            out.append(centres[i])
            continue
        weight = sum(scale(f)[0] for f in groups[i]) / len(groups[i])
        bump = sum(scale(f)[1] for f in groups[i]) / len(groups[i])
        out.append([round(weight, 2), round(bump, 2)])
    return out

centres = [[0.0, 0.0], [1.0, 1.0]]
for step in range(10):
    groups = assign(centres)
    new = move(groups, centres)
    print("round", step + 1, [len(g) for g in groups], new)
    if new == centres:
        print("settled")
        break
    centres = new

It prints

round 1 [3, 3] [[0.27, 0.12], [0.77, 0.88]]
round 2 [3, 3] [[0.27, 0.12], [0.77, 0.88]]
settled

Look what it found

The apples in one group and the oranges in the other — and the word "apple" appears nowhere in the program, because it was never in the data.

Python

import math

fruits = [[150, 2], [170, 3], [140, 1], [180, 7], [165, 8], [190, 9]]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

centres = [[0.27, 0.12], [0.77, 0.88]]
groups = [[], []]
for f in fruits:
    point = scale(f)
    near = 0
    if distance(point, centres[1]) < distance(point, centres[0]):
        near = 1
    groups[near].append(f)

for group in groups:
    print(group)

It prints

[[150, 2], [170, 3], [140, 1]]
[[180, 7], [165, 8], [190, 9]]

It found groups, not meanings

The program has no idea that group 1 is apples. It has "group 1". A person looks at it, sees the fruit is light and smooth, and writes the word — and everything anybody believes about that group after that comes from the person, not the maths.

Hold on to that when somebody tells you an AI "discovered" a category.

Why it always stops

Each round can only shorten the total distance from every point to its own centre — assigning to the nearer centre cannot make it longer, and moving to the middle is the spot with the smallest total. A number that only goes down, and cannot go below zero, has to come to rest.

Comparing the centres rounded to two places is what makes "nothing moved" a safe test to write; comparing raw decimals for exact equality is usually a mistake.

The same fruit, two centres dropped badly

Both starting centres land down in apple country this time. The method runs exactly as before, settles exactly as before — and gives a different answer.

Python

import math

fruits = [[150, 2], [170, 3], [140, 1], [180, 7], [165, 8], [190, 9]]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def assign(centres):
    groups = []
    for c in centres:
        groups.append([])
    for f in fruits:
        point = scale(f)
        near = 0
        for i in range(len(centres)):
            if distance(point, centres[i]) < distance(point, centres[near]):
                near = i
        groups[near].append(f)
    return groups

def move(groups, centres):
    out = []
    for i in range(len(groups)):
        if len(groups[i]) == 0:
            out.append(centres[i])
            continue
        weight = sum(scale(f)[0] for f in groups[i]) / len(groups[i])
        bump = sum(scale(f)[1] for f in groups[i]) / len(groups[i])
        out.append([round(weight, 2), round(bump, 2)])
    return out

centres = [[0.0, 0.0], [0.2, 0.13]]
for step in range(10):
    groups = assign(centres)
    new = move(groups, centres)
    if new == centres:
        break
    centres = new

for group in assign(centres):
    print(group)

It prints

[[150, 2], [140, 1]]
[[170, 3], [180, 7], [165, 8], [190, 9]]

A heavy apple has joined the oranges

It settled, and it settled somewhere worse. Nothing went wrong: from where those centres started, every round really did improve on the last, and it arrived somewhere it cannot improve on by moving a little.

That is the local minimum from unit 6, in a different costume. "It converged" never means "it is right".

What people do about it is unglamorous: run it several times from different starting points and keep the tidiest answer.

And k is your guess, not its discovery

Ask for three groups from fruit that comes in two kinds, and you get three groups. It has no way to object.

Python

import math

fruits = [[150, 2], [170, 3], [140, 1], [180, 7], [165, 8], [190, 9]]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def assign(centres):
    groups = []
    for c in centres:
        groups.append([])
    for f in fruits:
        point = scale(f)
        near = 0
        for i in range(len(centres)):
            if distance(point, centres[i]) < distance(point, centres[near]):
                near = i
        groups[near].append(f)
    return groups

def move(groups, centres):
    out = []
    for i in range(len(groups)):
        if len(groups[i]) == 0:
            out.append(centres[i])
            continue
        weight = sum(scale(f)[0] for f in groups[i]) / len(groups[i])
        bump = sum(scale(f)[1] for f in groups[i]) / len(groups[i])
        out.append([round(weight, 2), round(bump, 2)])
    return out

centres = [[0.0, 0.0], [0.5, 0.5], [1.0, 1.0]]
for step in range(10):
    groups = assign(centres)
    new = move(groups, centres)
    if new == centres:
        break
    centres = new

for group in assign(centres):
    print(group)

It prints

[[150, 2], [140, 1]]
[[170, 3], [165, 8]]
[[180, 7], [190, 9]]

That middle group is nonsense

A light smooth fruit and a light bumpy one, filed together because a human asked for three piles and three piles is what the arithmetic produced.

k is a hyperparameter, like the learning rate in unit 4 — chosen by a person, before any learning happens, and quietly deciding what the answer can be.

What this gets used for

Grouping shoppers by what they buy, songs by how they sound, or a night sky by which dots move together. It is genuinely useful, and it is genuinely unsupervised — nobody labelled any of it.

And then somebody names the groups. "People like this usually pay late." The maths found a clump; the sentence about people was written by a human, and unit 8 will have more to say about that.