Klyngeanalyse (clustering)

k-means er standardmetoden til opdeling. Givet k minimerer den summen af kvadrerede afstande til klyngernes centroider inden for hver klynge med Lloyds algoritme: Hvert punkt tildeles den nærmeste centroide, hver centroide genberegnes som gennemsnittet af sine punkter, og det gentages, til tildelingerne ikke ændrer sig. Hver iteration koster O(n·k·d). Det globale optimum er NP-svært at finde, selv med to klynger, så resultatet afhænger af initialiseringen; k-means++ (Arthur og Vassilvitskii, 2007) vælger spredte startcentroider med sandsynlighed proportional med den kvadrerede afstand og er i forventning O(log k)-konkurrencedygtig med den optimale opdeling, og implementeringer kører flere genstarter og beholder den bedste. k-means antager nogenlunde kugleformede klynger af ens størrelse i euklidisk rum og er følsom over for afvigere og skalering af features.

Andre familier bygger på andre antagelser. Hierarkisk agglomerativ klyngeanalyse starter med hvert punkt for sig og slår gentagne gange det nærmeste par klynger sammen, hvor linkage-kriteriet (single, complete, average eller Wards minimumvarians) definerer "nærmest"; resultatet er et dendrogram, der kan skæres på ethvert niveau. Den tæthedsbaserede DBSCAN (Ester m.fl., 1996) tager en radius eps og en mindste nabolagsstørrelse minPts, vokser klynger fra kernepunkter i tætte områder, finder klynger af vilkårlig form og markerer spredte punkter som støj; HDBSCAN fjerner behovet for én global eps. Gaussiske mixture-modeller tilpasset med EM-algoritmen giver bløde, sandsynlighedsbaserede tildelinger og elliptiske klynger. Spektral klyngeanalyse arbejder på egenvektorerne af en similaritetsgraf.

Valget af antal klynger er et skøn. Albuemetoden leder efter et knæk i kurven for fejlen inden for klyngerne; silhouette-koefficienten (Rousseeuw, 1987) sammenligner hvert punkts gennemsnitlige afstand til egen klynge med afstanden til den nærmeste anden klynge, fra -1 til 1; informationskriterier som BIC bruges til mixture-modeller. Disse indeks måler geometrisk adskillelse, ikke nytte. Kleinberg (2002) beviste, at ingen klyngefunktion kan opfylde tre naturlige aksiomer (skalainvarians, rigdom og konsistens) på én gang, hvilket formaliserer, hvorfor forskellige algoritmer med rette kan være uenige.

I praksis afhænger resultatet mere af repræsentationen end af algoritmen. Features skal skaleres eller standardiseres, kategoriske data kræver passende afstandsmål, og data i mange dimensioner lider under afstandskoncentration, så tekst og billeder laves som regel først om til embeddings og sammenlignes med cosinus-similaritet, ofte efter dimensionsreduktion. Klyngemærkerne er også ustabile: En ny kørsel med et andet seed eller en lidt anden stikprøve kan blande medlemskabet om, så stabiliteten bør tjekkes, før klynger bruges til beslutninger.

Klyngeanalyse forveksles undertiden med klassifikation, fordi begge danner grupper, men klassifikation placerer input i foruddefinerede, navngivne klasser lært fra eksempler, mens klyngeanalyse opdager grupper, hvis betydning må fortolkes bagefter. Når klynger bruges til at segmentere eller profilere kunder eller borgere, kan segmenterne udgøre profilering efter databeskyttelsesforordningens artikel 4, nr. 4.