programdemos/k-means/k-means.xtl

k-means, step by step: 300 points in five blobs, five centers. Each step gives every point the nearest center, then moves each center to the mean of its points (the Learn library's k_step: a few array expressions over all the points at once). From a poor start, five points of one blob, the centers travel across the plane to the blobs; from Learn's farthest-first start they barely need to.

source · imports ml: libs/Learn/src/Learn.xtl

The points: five blobs of 60, each its own center and spread

n : Int

value · line 12
n ← 300
Used in: i, X

i : Int

value · line 13
i ← o̲ffsets n
Used in: b

b : Int

value · line 14
b ← 1 + i d̲iv 60
Used in: cx, cy, spread

cx : Float

value · line 15
cx ← b s̲elect -0.6 0.5 0.0 -0.5 0.6
Used in: X

cy : Float

value · line 16
cy ← b s̲elect 0.5 0.6 -0.05 -0.6 -0.5
Used in: X

spread : Float

value · line 17
spread ← b s̲elect 0.12 0.16 0.1 0.2 0.08
Used in: X

ᵘn̲oise : Int -> Float

function · line 19

A little noise, the sum of two draws (so it bunches toward the middle).

ᵘn̲oise ← { m → (f̲loat (r̲oll! m r̲eshape 1001) + (r̲oll! m r̲eshape 1001) − 1002) ÷ 1000.0 }
Used in: X

X : Float

value · line 20
X ← o̲\ (2 c̲at n) r̲eshape (cx + spread × ᵘn̲oise n) c̲at cy + spread × ᵘn̲oise n

The map: a grid of g x g points over the square -1 .. 1

g : Int

value · line 23
g ← 40

c : Float

value · line 24
c ← -1.0 + 2.0 × (0.5 + f̲loat o̲ffsets g) ÷ f̲loat g
Used in: grid

grid : Float

value · line 25
grid ← o̲\ (2 c̲at g × g) r̲eshape (r̲avel (o̲ffsets g) 'r̲ight t̲able c) c̲at r̲avel (r̲ev c) 'l̲eft t̲able o̲ffsets g

Two starts, the same steps

k : Int

value · line 29
k ← 5
Used in: C0, F0

C0 : Float

value · line 31

A poor start: the first five points, all in the first blob.

C0 ← k t̲ake X

F0 : Float

value · line 33

Learn's start: the first point, then each time the farthest from those so far.

F0 ← k ᵐˡf̲arthest X

ᵘr̲ound : Float -> Float

function · line 36

The inertia (the sum of squared distances to the nearest center) after 0 to 10 steps, from each start: it never rises.

ᵘr̲ound ← { a → (f̲loat f̲loor 0.5 + 1000.0 × a) ÷ 1000.0 }

C10 : Float

value · line 40

The centers after 10 steps from the poor start, one per row.

C10 ← 10 '{ C → X ᵐˡk̲step C } p̲ower C0