kjernepunkt

Kjernepunkt er et begrep innen tetthetsbasert clustering, særlig i DBSCAN-algoritmen. Det beskriver et datapunkt som har minst et forhåndsdefinert antall naboer innenfor en fastsatt avstand, vanligvis kalt epsilon (ε). Mer formelt er et punkt p et kjernepunkt hvis nabolaget ε(p) inneholder minst minPts punkter, der ε(p) inkluderer p selv.

Dersom et punkt ikke oppfyller kravet, kan det være et grenselpunkt hvis det ligger i nabolaget til minst ett kjernepunkt, eller støy hvis det ikke er tetthetstilgjengelig fra noen kjernepunkt. I praksis betyr dette at grenspunkter ikke er kjernepunkter, men tilhører likevel en klynge gjennom sin tilknytning til kjernepunkter. Støypunkter regnes som us tilhørende noen klynge.

DBSCAN bruker kjernepunkter til å oppdage klynger basert på tetthet: kjernepunkter som er tetthetskoblet (density-connected) med hverandre danner en klynge, og grenspunkter tilhører en klynge gjennom tilknytning til disse kjernepunktene. Algoritmen identifiserer klynger ved å utforske naboer av kjernepunkter og utvide klynger så lenge tettheten opprettholdes. Utover DBSCAN brukes relaterte konsepter av kjernepunkter i varianter som OPTICS og HDBSCAN, hvor forskjeller i tetthet og sammenheng gir alternative klyngeformer og stratifikasjoner.

Kompleksitet og praktisk bruk: å finne kjernepunkter krever ofte nabolokalisering mellom punkter, noe som kan være kostbart uten effektive nabolokaliseringsteknikker som k-d trær eller indekser for romlige nabolag. Parametrene ε og minPts bestemmer antallet og sammensetningen av klynger og påvirker robusthet mot støy og uteliggere.