4 Klyngeanalyse

Den verden vi lever i (inkludert den digitale) består ofte av mange ulike typer unike objekter eller objektegenskaper. Hvert menneske har f.eks. unike personligheter, unike musikkspillelister, og unike matpreferanser.

For å kunne forholde seg til informasjon er vi avhengig av å sortere objekter i ulike kategorier. Men det er ikke alltid klart hva som er de beste kategoriene eller hvor fint man skal sortere. Eksempler på slike kategorier er ulike dyrearter, ulike materialklasser, ulike konsument-arketyper, ulike typer vær, ulike personlighetstyper, ulike boksjangre, osv.

I mange sammenhenger er ikke merkelappene kjente, eller man ønsker å forbedre merkelappene slik at de faktisk stemmer med kvantitative data.

Det å lage slike kategorier basert på data kalles klyngeanalyse.

Dette handler om å se på egenskapene til objektene, og sortere de etter hvor like egenskaper de har.

Når vi gjør klyngeanalyse, må vi beskrive objektene med tall. For personer kan det være alder, høyde, og inntekt. For musikk-lister kan det være antall rockelåter, poplåter og jazzlåter. For materialer kan det være tetthet, båndgap og varmeledningsevne. For en investor eller aksjehandler kan det være volatilitet, forventet avkastning og hvor sterkt en aksje følger markedet. Slike tall kalles features, og danner en vektor som representerer objektet, f.eks. $x$.

Nå kan vi sammenligne to objekter trenger vi et mål på hvor like de er. En metode er å den vanlige 2-normen til å regne ut $\|x -y\|$. Man kan også bruke cosinus-likhet i.e. $x^\top y$

4.1 Grunnleggende konsepter

I klyngeanalyse sorterer man datapunktene, gitt av en liste med vektorer som ligner på hverandre i ulike kategorier, eller altså i ulike klynger.

Et sett av vektorer som danner en klynge kan f.eks. være

\[C_1 = \{(5,2), (3,4), (4, 4)\}\]. Til forskjell fra vektorer og matriser, så spiller ikke rekkefølgen noen rolle. $C'_1 = \{(3,4),(5,2), (4, 4)\}$ beskriver det samme settet, $C_1 \equiv C_1'$.

Om vi hadde et større sett \[C = \{(5,2), (3,4), (4, 4), (1, -8), (3,-10), (-1, -9)\}\]

så vil det kunne være naturlig å dele dette i klynger $C_1$ og

\[C_2 = \{(1, -8), (3,-10), (-1, -9)\}\,,\]

men en slik inndeling kan sjelden reflektere alle aspekter. $(3,-10)$ er f.eks. “nærmere” det første settet i den første koordinaten.

Representative vektorer For å danne klynger er det ofte nyttig med arketyper, eller representative vektorer som er typisk for klyngen. Den representative vektoren kan være identisk med ett (eller flere) av elementene i klyngen, men trenger ikke å være det.

Om vi har et sett av en representative vektor $z_{C_i}$ for de ulike klyngene, da kan vi velge å sortere alle elementer som er nærmest den representative vektoren. Nedenfor er et eksempel hvor vi gjør klyngeanalyse på et sett a 100 tilfeldige 2d datasett.

Vi har valgt 3 representative vektorer på forhånd, og vi går gjennom listen og sortere hver vektor i en klynge basert på hvilken vektor som er mest representativ.

using Random, LinearAlgebra, Plots

# Fix the random seed for reproducibility
Random.seed!(42)

# Generate random 2D data
N = 100
X = rand(2, N)  # each column is a 2D point

# Choose 3 representative vectors (archetypes)
Z = [0.2 0.8 0.5;   # x-coordinates
     0.2 0.2 0.8]   # y-coordinates

# Assign each point to the closest representative
assignments = zeros(Int, N)

for j in 1:N
    # Compute all distances from point j to the archetypes
    dists = [norm(X[:, j] - Z[:, i]) for i in 1:size(Z, 2)]
    # Pick the index of the closest archetype
    assignments[j] = argmin(dists)
end

# Plot: points colored by cluster, archetypes as stars
colors = [:red, :blue, :green]
scatter(X[1,:], X[2,:], c=assignments, legend=false, xlabel="x", ylabel="y")
scatter!(Z[1,:], Z[2,:], marker=:star, ms=12, c=:black)

Dette resulterer i:

Det er mulig å visualisere slike klyngedannelse med hjelp av Voronoi/celler. En Voronoi inndeling av rommet, svarer til å dele i rommet inn de delene som er nærmest vektor i et gitt liste av reprentative vektorer. For å danne salike Voronoi-celler kan man bruke biblioteket VoronoiDelanay, evt. så kan vi partisjonere rommet i et grid og bruke en heatmap, som gjort nedenfor:

I maskinlæring for materialvitenskap benyttes Voronoi-inndeling hvor referanse-vektorene typisk svarer til posisjonen til de ulike atomene.

Hvor god er denne klyngedannelsen? Om man visuelt inspiserer klyngende over, så vil man kanskje se for seg at man kunne gjort en bedre inndeling for hånd. Ulike kvantitative mål på hvor god en klynge er kan brukes, vi bruker det følgende loss-funksjonen for dette:

\[ J^{\mathrm{cluster}} = \frac{1}{N} \sum_i \| x_i - z_{C_i} \|^2 \,, \] altså summen av de kvadrerte avstandene til den “tilordnede” representative vektoren (delt på antall vektorer $N$). Dette kan også skrives som

\[ J^{\mathrm{cluster}} = \frac{1}{N} \sum_{C_i} \sum_{j\in C_i} \| x_j - z_{C_i} \|^2 \,, \]

I eksemplet over, så minimerte vi $x_i$ ved å tilordne den nærmeste klyngen, men vi også o optimere de representative vektorene for gitte klynger.

Når vi bruker den vanlige 2-normen, som over, er de optimale $z_{C_i}$ for gite klynger gitt av den gjennomsnittlige vektoren

\[ z_{C_i} = \frac{1}{N_{C_i}}\sum_j x_j \]

Men nå er det ikke lenger gitt at tilordningen av $x$ til de ulike representative vektorene er optimal.

4.2 K-means algoritmen.

Om vi fortsetter å iterere mellom å define representative vektorerer og danner klynger, så får vi k-means algoritmen:

Velg antall klynger $k$ og initialiser $k$ representative vektorer (ofte tilfeldig).
Tilordne punkter: For hvert datapunkt $x_j$, finn nærmeste representant $z_i$ ved å minimere avstanden $\|x_j - z_i\|$.
Oppdater representantene: For hver klynge $C_i$, sett den nye representanten til gjennomsnittet \[ z_i = \frac{1}{N_{C_i}} \sum_{x_j \in C_i} x_j. \]
Beregn loss-funksjonen: Summer de kvadrerte avstandene til nærmeste representant \[ J^{\mathrm{cluster}} = \frac{1}{N} \sum_i \sum_{x_j \in C_i} \|x_j - z_i\|^2. \]
Iterer: Gjenta steg 2–4 til representantene endres lite eller tapet $J^{\mathrm{cluster}}$ slutter å gå ned.

Merk: I k-mean algoritmen, vil resultatet avhenge av startverdiene, og det er ingen garanti for å finne den beste løsningen, definert ved det globale minimumet til $J^{\mathrm{cluster}}$$

Over ser vi resultatet an klyngedannelse med hjelp av k-mean. Vi har iterert i 8 steg, og loss-funksjonen slutter å forbedret seg etter 7. Over viser den firkantede boksen endelige optimale representativ vektor.

Iteration 1: loss = 0.07864428897930195 Iteration 2: loss = 0.07255032289524975 Iteration 3: loss = 0.06956284459531711 Iteration 4: loss = 0.06780284340584668 Iteration 5: loss = 0.06737702657105815 Iteration 6: loss = 0.06627466828524206 Iteration 7: loss = 0.06564602240131853 Iteration 8: loss = 0.06564602240131853

Tilhørende kode:

using Random, LinearAlgebra, Statistics, Plots

function voronoi_heatmap(Z; nx=200, ny=200, colors=[:red,:blue,:green])
    N_cluster = size(Z, 2)
    xs = range(0, 1, length=nx)
    ys = range(0, 1, length=ny)
    Zgrid = Array{Int}(undef, nx, ny)

    for ix in 1:nx, iy in 1:ny
        p = [xs[ix], ys[iy]]
        dists = [norm(p - Z[:, i]) for i in 1:N_cluster]
        Zgrid[ix, iy] = argmin(dists)
    end

    plt = heatmap(xs, ys, Zgrid',
                  color=colors, alpha=0.2, legend=false,
                  aspect_ratio=1, xlim=(0,1), ylim=(0,1),
                  clims=(1, N_cluster))
    return plt
end

# ---------------- Example usage ----------------
Random.seed!(42)

# Random data
N = 100
X = rand(2, N)

# Initial archetypes
Z = [0.2 0.8 0.5;
     0.2 0.2 0.8]

Z0 = copy(Z)

N_cluster = size(Z, 2)

# Number of k-means iterations
n_iter = 8
colors = [:red, :blue, :green]

for it in 1:n_iter
    # Step 1: Assign clusters
    assignments = zeros(Int, N)
    for j in 1:N
        dists = [norm(X[:, j] - Z[:, i]) for i in 1:N_cluster]
        assignments[j] = argmin(dists)
    end

    # Step 2: Compute new means
    Znew = zeros(2, N_cluster)
    for i in 1:N_cluster
        members = findall(assignments .== i)
        if !isempty(members)
            Znew[:, i] = vec(mean(X[:, members], dims=2))
        else
            # keep previous representative if cluster empty (avoid NaNs)
            Znew[:, i] = Z[:, i]
        end
    end

    # Step 3: Compute loss (mean squared distance)
    loss = mean([norm(X[:, j] - Z[:, assignments[j]])^2 for j in 1:N])
    println("Iteration $it: loss = $loss")

    # Plot current state
    plt = voronoi_heatmap(Z, colors=colors)
    scatter!(plt, X[1,:], X[2,:], c=[colors[a] for a in assignments])
    scatter!(plt, Z0[1,:], Z0[2,:], marker=:star, ms=9, c=:black)   # current reps
    scatter!(plt, Znew[1,:], Znew[2,:], marker=:square, ms=8,
             markerstrokecolor=:black, markercolor=:white)         # updated reps

    savefig(plt, "clusters_iter$(it).png")

    # Update representatives for next iteration (REPL-safe)
    global Z = copy(Znew)
end

Selv om denne iterasjonen har konvergert så er det ingen grunn til å anta at dette er den optimale klyngedannelsen.

I koden over kunne vi også inkludert er

Lage et konvergens-cutoff. For større datasett kan det kreve mange iterasjoner å konvergere (eller konvergens er ikke garantert), men gevinsten kan være marginal.
Algoritmen er veldig sensitivt til initial-vektorer. Man kunne for eksempel valgt flere ulike initielle representative vektorer (f.eks. tilfeldig) og velge den klyngedannelsen med lavest $J^{\mathrm{cluster}}$ kan velges.
Man kan variere antall initielle klynger. Flere klynger vil generelt sett gi lavere $J^{\mathrm{cluster}}$. Samtidig vil svært mange klynger redusere hensikten med å danne klynger. Det er derfor naturlig å se på antall klynger i forhold til gevinsten i $J^{\mathrm{cluster}}$.

Oppgave: Utforsk ulike initielle representative vektorer og se hvor lav $J^{\mathrm{cluster}}$ du klarer å få for et gitt antall klynger. Hvor mange klynger vil du anbefale? Du kan prøve manuelt eller ved å utvide koden.

4.3 Klyngedannelse av håndskrevne tall

Et klassisk datasett i maskinlæring er håndskrevne tall, og disse kan lastes ned direkte fra MNIST. Men vi kan også få de MLDatasets bibliotket i Julia, som nedenfor:

using MLDatasets, Random, Plots

# Load data
train = MNIST(:train)
X = train.features
y = train.targets

# Pick 12 random digits
Random.seed!(123)
idxs = rand(1:size(X, 3), 12)

# Make one heatmap per image
plots = [
    heatmap(X[:, :, idx]', c=:grays, axis=nothing,
            aspect_ratio=1)
    for idx in idxs
]

p = plot(plots..., layout=(3,4), size=(800,600))
display(p)
savefig(p, "mnist_examples.png")

Vi kan nå bruke k-means til å prøve å oppdage representative vektorer. Det kan være naturlig å tenke at man bør bruke Frobenius-normen for å finne forskjellen en bilde-matrise og en representativ matrise for tallet.
Men i praksis så kan man like greit linearisere matrisen og gjøre den til et vektor og benytte 2-normen. Dette vil gi den samme effektive avstanden mellom datapunkt.

I det følgende koden bruker vi Julia sitt Clustering-bibliotek:

using MLDatasets, Random, Statistics, Clustering, Plots

# Load both training and test sets
train = MNIST(:train)
test  = MNIST(:test)

X = Float64.(cat(train.features, test.features; dims=3))  # 28×28×70000
y = vcat(train.targets, test.targets)

# Flatten
Xmat = reshape(X, :, size(X, 3)) 

# Run k-means
k = 20
Random.seed!(40)
R = kmeans(Xmat, k; maxiter=20)

println("Cluster sizes: ", counts(R))

# Reshape cluster centers
centers_img = [reshape(R.centers[:, i], 28, 28) for i in 1:k]

# Plot centers (no colorbars)
plots = [heatmap(centers_img[i]', c=:grays, axis=nothing,
                 aspect_ratio=1, colorbar=false) for i in 1:k]

p = plot(plots..., layout=(4,5), size=(800,400))
display(p)
savefig(p, "mnist_kmeans_centers_all.png")

Hele databasen er inkludert (både trening og test) og dette ga følgende resultat med 20 initelle vektorer

Representaive images generated from MNIST (imperfect results())

Her kan vi si at modellen har oppdaget flere tall fra dataene, som 0, 1, 8, 2 5, og 3. Men det er også “mystiske” symboler, som ikke ligner på kjente tall. Dette tyder på at vi ikke har funnet en gode representative vektorer, som kanskje fanger opp elementer av flere ulike tall.

Vi fikk altså ikke like gode resultater som i Boyd og Vanderberghe.

4.3.1 Diskusjon

Klyngedannelse er en svært viktig ML-metode som blir veldig godt illustrert av k-mean metoden. Men mange mange nyere metoder enn k-means finnes som blir brukt mye mer i praksis. Men k-mean kan ofte inngå i andre ML metoder.

Vi bemerker til slutt at hvis features vektorene har ulike dimensjoner (f.eks. høye i m og vekt i kg for en person), så bør man f.eks. standardisere tallene for å sikre at normen ikke blir dominert av noen få tall.