Clustering

I veiledet læring har hvert punkt en fasit $y$, og vi kan telle hvor ofte modellen treffer. I clustering finnes ingen slik fasit. Vi har bare features, for eksempel strømforbruk natt og dag for 500 husstander, og spør hvilke punkter som hører sammen. Nesten alle metodene bygger på et avstandsmål, oftest euklidsk avstand. De skiller seg i hvordan de gjør avstander om til grupper, og det gir fire familier du bør kunne skille:

• •Sentroidebasert: hver klynge oppsummeres med et midtpunkt, en sentroide, og hvert punkt tilhører nærmeste midtpunkt. Eksempler: k-means og k-medoids, som bruker et faktisk datapunkt som midtpunkt.
• •Tetthetsbasert: en klynge er et sammenhengende område der punktene ligger tett, adskilt fra andre klynger av glisne områder. Eksempler: DBSCAN, OPTICS og HDBSCAN.
• •Hierarkisk: punktene slås sammen (eller deles opp) trinn for trinn, og resultatet er et tre av klynger på alle nivåer. Eksempel: agglomerativ clustering med dendrogram.
• •Fordelingsbasert: dataene antas å være trukket fra en blanding av sannsynlighetsfordelinger, og hver klynge er én fordeling. Eksempel: Gaussisk blandingsmodell (GMM).

Familiene gjør ulike antakelser om hvordan en klynge ser ut, så to metoder kan gi helt forskjellige svar på de samme dataene. Det finnes ingen «riktig» clustering uavhengig av antakelsene, og eventuelle labels kan bare brukes etterpå, til ekstern evaluering.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

X, fasit = make_moons(n_samples=200, noise=0.06, random_state=4172)
eps = 0.2  # @param 0.05..0.6 0.05
k = 2  # @param 2..6
km = KMeans(n_clusters=k, n_init=10, random_state=4172).fit(X).labels_
db = DBSCAN(eps=eps, min_samples=5).fit(X).labels_

# Fasiten brukes bare til å evaluere etterpå, aldri under clusteringen.
print(f"k-means: ARI mot fasit = {adjusted_rand_score(fasit, km):.2f}")
print(f"DBSCAN:  ARI mot fasit = {adjusted_rand_score(fasit, db):.2f}, "
      f"{len(set(db) - {-1})} klynger og {np.sum(db == -1)} støypunkter")

fig, ax = plt.subplots(1, 2)
for a, navn, lab in [(ax[0], f"k-means, k = {k}", km), (ax[1], f"DBSCAN, eps = {eps}", db)]:
    for c in np.unique(lab):                 # én farge per klynge fra standardpaletten
        a.scatter(X[lab == c, 0], X[lab == c, 1], s=12)
    a.set_title(navn)
plt.tight_layout()
plt.show()

k-means deler halvmånene med en rett linje, fordi den bare spør hvilket midtpunkt som er nærmest. DBSCAN følger tettheten rundt buen og finner begge månene. Buede, sammenflettede former er vanskelige for sentroidebaserte metoder, mens tetthetsbaserte metoder følger formen. Legg også merke til at fasiten bare brukes til å regne ut ARI etterpå. Det er ekstern evaluering, ikke trening.

k-means antar at det finnes $k$ klynger, og at hver klynge kan oppsummeres med sentroiden sin, gjennomsnittet av punktene i klyngen (ƒsentroide). Målet er å gjøre klyngene så kompakte som mulig, målt som summen av kvadrerte avstander fra hvert punkt til sentroiden det er tildelt (ƒk-means-målet):

Å finne den beste løsningen direkte er for dyrt, så Lloyds algoritme veksler mellom to enkle steg:

1. 1.Tilordne: hvert punkt går til sentroiden med minst kvadrert avstand.
2. 2.Flytte: hver sentroide flyttes til gjennomsnittet av punktene som nå tilhører den.

Stegene gjentas til tilordningen slutter å endre seg. Hvorfor virker det? Med sentroidene låst er nærmeste sentroide det beste valget for hvert punkt, så tilordningen kan ikke øke $J$. Med tilordningen låst er gjennomsnittet det punktet som gir minst sum av kvadrerte avstander, så flyttingen kan heller ikke øke $J$. Målet synker eller står stille i hver runde og må stoppe etter endelig mange steg. Det garanterer et lokalt minimum, ikke det globale.

Fordi alt bygger på euklidsk avstand, må featurene være på sammenlignbar skala. Måles én feature i kroner (0 til 50 000) og en annen i antall besøk (0 til 20), avgjør kronebeløpet nesten alene hvem som er nærmest. Standardiser derfor først, med mindre de store tallene faktisk skal veie tyngre.

Fordi k-means bare finner et lokalt minimum, avhenger svaret av hvor sentroidene starter. Det finnes tre vanlige strategier:

• •Tilfeldig: velg $k$ tilfeldige datapunkter som startsentroider. Det er enkelt, men to startpunkter kan havne i samme klynge, og Lloyd-stegene klarer ikke alltid å flytte en sentroide over til en annen klynge. Resultatet varierer fra kjøring til kjøring.
• •Lengst unna: velg første tilfeldig, og deretter alltid punktet som ligger lengst fra sentroidene som allerede er valgt. Det sprer sentroidene, men er grådig og, etter første valg, deterministisk: en uteligger ute ved kanten er per definisjon lengst unna og blir valgt hver gang, og da går en hel sentroide med til ett punkt.
• •{{term:kmeans-pluss-pluss}}: velg første tilfeldig, og trekk hvert neste senter med sannsynlighet proporsjonal med $D(x{)}^2$, den kvadrerte avstanden til nærmeste senter som allerede er valgt (ƒk-means++-sannsynlighet).

k-means++ kombinerer det beste fra de to andre. Kvadreringen gjør fjerne punkter mye mer sannsynlige, så sentrene spres utover. Men trekningen er fortsatt tilfeldig, og en ekte klynge består av mange punkter som til sammen har stor sannsynlighetsmasse. Én uteligger har høy sannsynlighet hver for seg, men en fjern klynge med femti punkter har som regel høyere samlet sannsynlighet. Derfor blir uteliggeren valgt bare i en del av trekningene, ikke hver gang som med «lengst unna». Helt immun er k-means++ likevel ikke: ligger uteliggeren svært langt unna og klyngene er små, kan den få en stor del av sannsynligheten. I praksis kjører man derfor algoritmen flere ganger med ulike frø (n_init i scikit-learn) og beholder løsningen med lavest $J$.

k-means velger ikke $k$ selv. Antallet klynger er en hyperparameter du må bestemme. Det fristende er å velge den $k$ som gir lavest $J$, men $J$ synker nesten alltid når $k$ øker, og blir $0$ når hvert punkt har sin egen sentroide. Vi trenger kriterier som straffer unødvendig mange klynger.

Albuemetoden plotter $J$ mot $k$ og ser etter knekkpunktet der kurven går fra bratt til flat. Før knekken deler hver nye sentroide en ekte klynge i to og gir stor gevinst. Etter knekken deler den bare opp klynger som allerede er gode. I praksis er knekken ofte uklar.

{{term:silhuett}} måler for hvert punkt hvor godt det passer i egen klynge sammenlignet med nærmeste andre klynge (ƒsilhuett):

Her er $a(i)$ snittavstanden til de andre punktene i egen klynge, og $b(i)$ er snittavstanden til punktene i den nærmeste andre klyngen. Verdien ligger mellom $-1$ og $1$: nær $1$ betyr godt plassert, nær $0$ betyr på grensen, og negativ betyr at punktet trolig ligger i feil klynge. Vi velger gjerne den $k$ som gir høyest gjennomsnittlig silhuett.

Albue og silhuett er ulike metrikker og kan peke på ulike $k$. Det er ikke en feil, men et tegn på at strukturen ikke er entydig, og da avgjør bruken: en butikk som har råd til tre kampanjer, trenger tre segmenter.

Når passer k-means? Når klyngene er kompakte og omtrent sfæriske, med lignende størrelse, og avstanden mellom punkter innad i en klynge er mindre enn avstanden mellom klyngene. Den sliter med langstrakte eller buede former, klynger med svært ulik tetthet og uteliggere, fordi et gjennomsnitt trekkes mot ekstreme punkter og hvert punkt tvinges inn i en klynge.

DBSCAN spør ikke hvilket midtpunkt som er nærmest, men hvor tett det er rundt hvert punkt. To parametre styrer alt: radiusen $\epsilon$ og minimumsantallet minPts (min_samples i scikit-learn). Nabolaget $N_{\epsilon }(x)$ er alle punkter innen avstand $\epsilon$ fra $x$ (ƒDBSCAN-nabolag), og punktet selv teller med. Hvert punkt får én av tre roller:

• •Kjernepunkt (kjernepunkt): har minst minPts punkter i nabolaget sitt.
• •Kantpunkt: har for få naboer til å være kjerne selv, men ligger innen $\epsilon$ fra et kjernepunkt.
• •Støypunkt (støypunkt): er verken kjerne eller innen $\epsilon$ fra en kjerne.

Klyngene bygges ved å følge kjeder. To punkter havner i samme klynge når de er tetthetsnåbare: det går en kjede av kjernepunkter mellom dem der hvert steg er høyst $\epsilon$ langt. To punkter kan altså ligge langt fra hverandre og likevel høre til samme klynge, så lenge det går en tett sti mellom dem. Det er derfor DBSCAN kan følge halvmåner og spiraler som k-means kutter i stykker. Kantpunkter blir med i klyngen, men forlenger ikke kjeden, siden de ikke har nok naboer selv.

Tre egenskaper følger direkte. DBSCAN trenger ikke $k$: antallet klynger faller ut av tettheten. Den er robust mot uteliggere, fordi et isolert punkt bare blir støy (label -1) i stedet for å dra en sentroide ut av posisjon. Og den er følsom for $\epsilon$. For lav $\epsilon$ bryter kjedene og gir mange småklynger og mye støy. For høy $\epsilon$ bygger bro over glisne områder, og alt smelter sammen til én klynge. Én felles $\epsilon$ passer også dårlig når klyngene har svært ulik tetthet, og fordi $\epsilon$ måles i feature-rommet, må featurene skaleres først.

Hierarkisk clustering lager ikke én oppdeling, men en hel familie av dem. Den agglomerative varianten starter med hvert punkt som egen klynge og slår hele tiden sammen de to klyngene som ligger nærmest hverandre, til alt er én klynge. Hvordan avstanden mellom to klynger måles, kalles linkage:

• •Single linkage: korteste avstand mellom et punkt i hver klynge. Følger kjeder, som DBSCAN, men kan lenke sammen grupper via én tynn bro.
• •Complete linkage: lengste avstand mellom et punkt i hver klynge. Gir kompakte klynger.
• •Ward: sammenslåingen som øker summen av kvadrerte avstander til sentroidene minst, altså samme mål som k-means.

Resultatet tegnes som et dendrogram. Bladene er punktene, og høyden der to grener møtes, er avstanden da de ble slått sammen. Antall klynger velges etterpå ved å kutte dendrogrammet med en vannrett linje: antall grener linjen krysser, er antall klynger. En lang loddrett strekning uten sammenslåinger betyr at klyngene under den er godt adskilt.

Den fordelingsbaserte familien er representert ved Gaussisk blandingsmodell. Den antar at dataene kommer fra $k$ normalfordelinger med hver sin middelverdi, kovariansmatrise og vekt, og tilpasser dem med EM-algoritmen. Til forskjell fra k-means gir den myk tilhørighet: et punkt mellom to klynger kan få 70 % sannsynlighet for den ene og 30 % for den andre. Fordi hver komponent har sin egen kovarians, kan klyngene være elliptiske og ha ulik spredning. k-means svarer omtrent til et grensetilfelle med like, runde komponenter og hard tilordning.