Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Clustering, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Å gruppere observasjoner etter likhet uten å ha kjente klasselabels.
En algoritme som veksler mellom å tilordne punkter til nærmeste sentroide og å beregne nye sentroider.
En tetthetsbasert algoritme som kan finne uregelmessige clusterformer og merke spredte punkter som støy.
Et DBSCAN-punkt med minst det påkrevde antallet punkter i sitt lokale nabolag.
Et punkt som DBSCAN verken gjør til kjernepunkt eller kobler tetthetsmessig til et cluster.
Initialisering for k-means der hvert nye startsenter trekkes med sannsynlighet proporsjonal med , den kvadrerte avstanden til nærmeste senter som allerede er valgt. Sprer sentrene, men beholder tilfeldigheten.
Mål for hvor godt et punkt passer i klyngen sin: , der er snittavstanden innad i egen klynge og snittavstanden til nærmeste andre klynge. Ligger mellom og .
Clustering som slår sammen (agglomerativ) eller deler opp (divisiv) klynger trinn for trinn og viser resultatet som et dendrogram. Antall klynger velges etterpå ved å kutte dendrogrammet i en valgt høyde.
Fordelingsbasert clustering som modellerer dataene som en blanding av normalfordelinger og gir hvert punkt en sannsynlighet for hver klynge (myk tilhørighet).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
k-means-målet
k-means søker cluster og sentroider som minimerer summen av kvadrerte avstander innen clusterne.
Sentroide
Sentroiden er gjennomsnittet av punktene som for tiden tilhører cluster .
DBSCAN-nabolag
DBSCAN teller punkter innen radius for å avgjøre om et punkt ligger i et tett område.
k-means++-sannsynlighet
Sannsynligheten for at punktet blir neste startsenter. er avstanden til nærmeste senter som allerede er valgt, så fjerne punkter er mer sannsynlige.
Silhuett
Silhuetten til punkt . Nær betyr godt plassert, nær betyr på grensen, og negativ betyr trolig feil klynge.
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
Fire k-means-iterasjoner med NumPy
import numpy as np rng = np.random.default_rng(4172)venstre = rng.normal(loc=(-1.8, -0.5), scale=0.35, size=(25, 2))hoyre = rng.normal(loc=(1.6, 0.8), scale=0.45, size=(25, 2))X = np.vstack([venstre, hoyre])sentroider = X[[3, 31]].copy() for steg in range(4): avstand = np.linalg.norm(X[:, None, :] - sentroider[None, :, :], axis=2) cluster = avstand.argmin(axis=1) maal = np.sum((X - sentroider[cluster]) ** 2) print(f"steg {steg}: mål={maal:.3f}, sentroider={np.round(sentroider, 2)}") sentroider = np.vstack([X[cluster == k].mean(axis=0) for k in range(2)])Implementasjonen viser de to vekslende k-means-stegene: nærmeste sentroide (argmin) og nytt gjennomsnitt (mean). Målet faller eller står stille for hver full iterasjon.
k-means og DBSCAN på to halvmåner
import numpy as npimport matplotlib.pyplot as pltfrom sklearn.cluster import DBSCAN, KMeansfrom sklearn.datasets import make_moonsfrom 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.05k = 2 # @param 2..6km = 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()Prøv: Dra eps mellom 0,1 og 0,5 og se «DBSCAN» endre antall klynger og støypunkter; dra k og se om «k-means» ARI noen gang nærmer seg 1.
Linkage-valg og myk tilhørighet
import numpy as npfrom sklearn.cluster import AgglomerativeClusteringfrom sklearn.datasets import make_blobsfrom sklearn.mixture import GaussianMixture spredning = 1.0 # @param 0.3..2 0.1X, _ = make_blobs(n_samples=150, centers=[(0, 0), (4, 0), (2, 3.5)], cluster_std=[0.5, 0.5, spredning], random_state=4172) for linkage in ["single", "complete", "ward"]: etiketter = AgglomerativeClustering(n_clusters=3, linkage=linkage).fit_predict(X) print(f"{linkage:9s} klyngestørrelser: {np.sort(np.bincount(etiketter))[::-1]}") p = GaussianMixture(n_components=3, random_state=4172).fit(X).predict_proba(X)print(f"GMM: {np.sum(p.max(axis=1) < 0.9)} punkter har under 90 % tilhørighet til én klynge")print(f"mest usikre punkt: {np.round(p[np.argmin(p.max(axis=1))], 2)}")Prøv: Dra spredning opp mot 1,6 og se hvilken linkage som gir én kjempe i «klyngestørrelser», og «GMM: … punkter» med under 90 % tilhørighet vokse.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Utfør ett tilordnings- og flyttesteg i k-means og regn ut summen av kvadrerte avstander
- 02Regn ut k-means++-sannsynligheter med og forklar hvorfor metoden er mer robust mot uteliggere enn «lengst unna»
- 03Velg med albue og silhuett, og forklar hvorfor kriteriene kan gi ulike svar
- 04Klassifiser punkter som kjerne, kant eller støy i DBSCAN og forklar hva for lav og for høy gjør
- 05Plasser en metode i riktig familie (sentroide, tetthet, hierarki, fordeling) og les et dendrogram
- 06Velg clusteringmetode ut fra klyngenes form, støy og skala