Cluster-analyse

Evaluering (eller «validering») av klynging resultatene er så vanskelig som klynger seg selv. Populære tilnærminger innebærer «intern» evaluering, der clustering er oppsummert til en enkelt kvalitetspoeng, «eksterne» evaluering, der clustering er i forhold til en eksisterende «ground truth» klassifisering, «manuell» evaluering av en menneskelig ekspert, og «indirekte» evaluering ved å evaluere nytten av klynging i sin tiltenkte bruksområde.,

Intern evaluering tiltak lider av problemet at de representerer funksjoner som i seg selv kan bli sett på som en gruppering mål. For eksempel kan en klynge data set av Silhuetten koeffisient; bortsett fra at det er ingen kjent effektiv algoritme for dette. Ved å bruke slike et internt mål for evaluering, en heller sammenligner likheten av optimalisering problemer, og ikke nødvendigvis hvor nyttig klynging er.,

Ekstern evaluering har lignende problemer: hvis vi har en slik «ground truth», etiketter, så vi ville ikke trenger å klynge, og i praktiske anvendelser vi vanligvis ikke har slike merkelapper. På den annen side, etiketter bare reflektere en mulig oppdeling av datasettet, som ikke innebærer at det ikke finnes en annen, og kanskje enda bedre, clustering.

ingen av disse tilnærmingene kan derfor til syvende og sist bedømme den faktiske kvaliteten på en clustering, men dette trenger menneskelig vurdering, som er svært subjektiv., Uansett, en slik statistikk kan være ganske lærerikt å identifisere dårlige clusterings, men man skal ikke avvise subjektive menneskelige evaluering.

Interne evaluationEdit

Når en clustering resultatet er evaluert basert på data som ble samlet seg, dette kalles intern evaluering. Disse metodene er vanligvis tilordne den beste poengsummen til den algoritmen som produserer klynger med høy likheten i en klynge og lave likheten mellom klynger., En ulempe med å bruke interne kriterier i klyngen vurdering er at høy score på et internt tiltak, ikke nødvendigvis vil føre til effektiv informasjonsgjenfinning programmer. I tillegg, denne evalueringen er forutinntatt mot algoritmer som bruker samme cluster-modell. For eksempel, k-betyr clustering naturlig optimaliserer objekt avstander, og en avstand-baserte interne kriteriet vil trolig overrate den resulterende clustering.,

Derfor, den interne evaluering tiltak som er best egnet for å få innsikt i situasjoner der en algoritme fungerer bedre enn en annen, men dette skal ikke innebære at en algoritme produserer mer gyldige resultater enn en annen. Gyldigheten målt ved en slik indeks avhenger hevder at denne form for struktur finnes i datasettet. En algoritme er utformet for noen form for modeller har ingen sjanse hvis datasettet inneholder en radikalt annerledes sett av modeller, eller hvis evalueringen måler en radikalt annerledes kriteriet., For eksempel, k-betyr clustering kan bare finne konveks klynger, og mange evaluering indekser anta konveks klynger. På et datasett med ikke-konvekse klynger verken bruk av k-means, eller av en vurdering kriterium som forutsetter convexity, er lyden.

Mer enn et dusin av intern evaluering tiltak finnes, vanligvis basert på intuisjon som elementer i samme klynge bør være mer likt enn elementer i ulike klynger., følgende formel: D B = 1 n ∑ i = 1 n max j ≠ i ( σ jeg + σ j d ( p i , p j ) ) {\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\maks _{j\neq jeg}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)} der n er antall klynger, c jeg {\displaystyle c_{i}} er centroid av klyngen jeg {\displaystyle jeg} , σ jeg {\displaystyle \sigma _{i}} er gjennomsnittlig avstand for alle elementer i klyngen jeg {\displaystyle jeg} for å centroid c jeg {\displaystyle c_{i}} , og d ( p i , p j ) {\displaystyle d(c_{i},c_{j})} er avstanden mellom centroids c jeg {\displaystyle c_{i}} og c j {\displaystyle c_{j}} ., Siden algoritmer som produserer klynger med lave intra-klyngen avstander (høy intra-klyngen likhet) og høy inter-klyngen avstander (lav inter-klyngen likhet) vil ha en lav Davies–Bouldin indeksen clustering algoritmen som produserer en samling av klynger med de minste Davies–Bouldin indeksen er regnet som den beste algoritmen er basert på dette kriteriet.

• Dunn indeks

Den Dunn indeksen har som mål å identifisere tett og godt adskilt klynger. Det er definert som forholdet mellom minimal inter-klyngen avstand til maksimal intra-klyngen avstand., For hver klynge partisjon Dunn indeks kan beregnes ved følgende formel: D = min 1 ≤ i < j ≤ n d ( i , j ) max 1 ≤ k ≤ n d ‘ ( k ) , {\displaystyle D={\frac {\min _{1\leq jeg<j\leq n}l(i,j)}{\maks _{1\leq k\leq n}d^{\prime }(k)}}\,,} der d(i,j) representerer avstanden mellom klynger i og j, og d ‘(k) tiltak intra-klyngen avstand av klyngen k. Inter-klyngen avstanden d(i,j) mellom to klynger kan være et hvilket som helst antall avstand tiltak, slik som avstand mellom centroids av klynger., På samme måte, intra-klyngen avstand d ‘(k) kan måles på ulike måter, for eksempel maksimal avstand mellom alle par av elementer i klyngen k. Siden interne kriteriet søke klynger med høy intra-klyngen likhet og lav inter-klyngen likhet, algoritmer som produserer klynger med høy Dunn indeks er mer ønskelig.

• Silhouette koeffisient

silhuetten koeffisient kontraster gjennomsnittlig avstand til elementer i samme klynge med gjennomsnittlig avstand til elementer i andre klynger., Objekter med et høyt silhouette verdien anses som godt samlet, gjenstander med en lav verdi kan være uteliggere. Denne indeksen fungerer godt med k-betyr clustering, og er også brukt til å finne den optimale antall klynger.

Ekstern evaluationEdit

I ekstern evaluering, clustering resultatene er evaluert basert på data som ikke ble brukt for clustering, slik som kjent klasse etiketter og eksterne standarder. Slike milepæler består av et sett med pre-klassifisert elementer, og disse settene er ofte laget av (ekspert) mennesker., Dermed benchmark sett kan betraktes som gull-standarden for evaluering. Disse typer evaluering metoder for å måle hvor nær klynging er til forhåndsbestemte benchmark klasser. Men, det har nylig vært diskutert hvorvidt dette er tilstrekkelig for ekte data, eller bare på syntetiske datasett med en saklig bakken sannheten, siden klasser kan inneholde interne struktur, egenskaper til stede kan ikke tillater separasjon av grupper eller klasser kan inneholde avvik., I tillegg, fra en knowledge discovery point of view, gjengivelse av kjent kunnskap ikke nødvendigvis være det ønskede resultat. I spesielle scenario av begrenset clustering, der meta-informasjon (for eksempel klasse etiketter) brukes allerede i clustering prosessen, holde ut av informasjon for evaluering formål er ikke-trivielt.

En rekke tiltak er tilpasset fra varianter brukes til å evaluere klassifisering oppgaver., I stedet for å telle antall ganger en klasse ble korrekt tildelt ett enkelt datapunkt (kjent som sanne positive), slike par telle beregninger vurdere om hvert par av data poeng som er virkelig i samme klynge som er spådd å være i samme klynge.

Som med intern evaluering, flere ekstern evaluering tiltak finnes,:125-129 for eksempel:

• Renhet: Renhet er et mål på i hvilken grad klynger inneholde en enkelt klasse. Beregningen kan være tenkt som følger: For hver klynge, telle antall datapunkter fra den mest vanlige klasse i sa klyngen., Nå tar summen over alle klynger og divideres med totalt antall datapunkter. Formelt gitt noen sett av klynger M {\displaystyle M} og noen sett med klasser D {\displaystyle D} , både partisjonering N {\displaystyle N} data poeng, renhet kan være definert som:

1 N ∑ m ∈ M maks d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\i M}\maks _{d\i D}{|m\cap d|}} Dette tiltaket ikke straffe det å ha mange klynger, og mer klynger vil gjøre det lettere å produsere en høy renhet. En renhet score på 1 er alltid mulig ved å sette hvert datapunkt i sin egen klynge., Også, renhet fungerer ikke bra for ubalanserte data, der selv med dårlig resultat clustering algoritmer vil gi en høy renhet verdi. For eksempel, hvis du har en størrelse på 1000-datasettet består av to klasser, en som inneholder 999 poeng, og den andre inneholder 1 poeng, så alle mulige partisjon vil ha en renhet på minst 99,9%.

• Rand indeks

Rand index beregner hvor like de klynger (returnert av clustering algoritmen) er å benchmark klassifikasjoner., Det kan beregnes ved hjelp av følgende formel: R-I = T P + T N i T T P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} der T P {\displaystyle TP} er antall sanne positive, T N {\displaystyle TN} er antall sanne negative, F P {\displaystyle FP} er antall falske positiver, og F N {\displaystyle FN} er antallet falske negativer. Forekomster som telles her er antall korrekte parvis oppdrag., Det er T P {\displaystyle TP} er antall par av punkter som er gruppert sammen i spådd partisjon og i bakken sannheten partisjon, F P {\displaystyle FP} er antall par av punkter som er gruppert sammen i spådd partisjonen, men ikke i bakken sannheten partisjon etc. Hvis datasettet er av størrelse N, deretter T P + T N + F P + F N = ( N-2 ) {\displaystyle TP+TN+FP+FN={\binom {N}{2}}} .

Ett problem med Rand-indeksen er at falske positiver og falske negativer er likt vektet. Dette kan være en uønsket karakteristisk for noen clustering programmer., F-måle-adresser denne bekymringen, som gjør sjanse-korrigert justert Rand-indeksen.

• F-mål

F-mål kan brukes til å balansere bidrag falske negativer ved vekting recall gjennom en parameteren β ≥ 0 {\displaystyle \beta, \geq 0} . La presisjon og recall (både ekstern evaluering av tiltak i seg selv) være definert som følger: S = T P i T T S + F P {\displaystyle P={\frac {TP}{TP+FP}}} R = T P i T T S + F N {\displaystyle R={\frac {TP}{TP+FN}}} der P {\displaystyle P} er presisjon pris og R {\displaystyle R} er recall pris., Vi kan beregne F-målet ved hjelp av følgende formel: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ S + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot S+R}}} Når β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Med andre ord, tilbakekalling har ikke innvirkning på F-tiltak når β = 0 {\displaystyle \beta =0} , og øke β {\displaystyle \beta } tildeler en økende mengde vekt å huske i det siste F-mål. Også T N {\displaystyle TN} er ikke tatt hensyn til, og kan variere fra 0 og oppover uten bundet.,

• Jaccard indeks

Den Jaccard indeksen brukes til å kvantifisere likheten mellom to datasett. Den Jaccard indeksen tar på en verdi mellom 0 og 1. En indeks over 1 innebærer at de to datasett er identiske, og en indeks på 0 indikerer at datasett har noen felles elementer. Den Jaccard indeksen er definert ved følgende formel: J ( A , B ) = | A ∩ B | | A ∪ B | = T P i T T S + F P + F N {\displaystyle J(A,B)={\frac {|En\cap B|}{|En\cup B|}}={\frac {TP}{TP+FP+FN}}} Dette er rett og slett antall unike elementer som er felles for begge sett delt på totalt antall unike elementer i begge settene., Også T N {\displaystyle TN} er ikke tatt hensyn til, og kan variere fra 0 og oppover uten bundet.

• Terninger indeks

Terningen symmetrisk mål dobler vekt på T P {\displaystyle TP} mens de fortsatt ignorere T N {\displaystyle TN} : D S C = 2 T P 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}

• Fowlkes–Mallows indeks

Den Fowlkes–Mallows index beregner likheten mellom klynger som returneres av clustering algoritmen og benchmark-klassifikasjoner., Jo høyere verdien av Fowlkes–Mallows stikkordregister mer lik klynger og benchmark-klassifikasjoner. Det kan beregnes ved hjelp av følgende formel: F M = T P i T T S + F P ⋅ T S T P + F N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}} der T P {\displaystyle TP} er antall sanne positive, F P {\displaystyle FP} er antall falske positiver, og F N {\displaystyle FN} er antallet falske negativer., F M {\displaystyle FM} indeks er det geometriske gjennomsnittet av precision og recall P {\displaystyle P} og R {\displaystyle R} , og er dermed også kjent som G-tiltak, mens F-mål er deres harmoniske mener. Videre, presisjon og recall er også kjent som Wallace indekser B i {\displaystyle B^{I}} og B i i {\displaystyle B^{II}} . Sjansen normalisert versjoner av recall, presisjon og G-tiltak svarer til Informedness, Markedness og Matthews Korrelasjon og forholder seg sterkt til Kappa.,

• gjensidig informasjon er en informasjonsteoretiske mål på hvor mye informasjon er delt mellom en clustering og en jord-sannheten klassifisering som kan oppdage en ikke-lineær likheten mellom to clusterings. Normalisert gjensidig informasjon er en familie av korrigert for sjansen varianter av denne som har en redusert tilbøyelighet til varierende klynge tall.
• Forvirring matrix

En forvirring matrix kan brukes til raskt å visualisere resultatene av en klassifisering (eller clustering) algoritmen. Det viser hvor forskjellig en klynge er fra gold standard klyngen.,

Klynge tendencyEdit

for Å måle klynge tendensen er å måle i hvilken grad klynger finnes i dataene til å være samlet, og kan utføres som en første test, før du prøver clustering. En måte å gjøre dette på er å sammenligne data mot tilfeldige data. I gjennomsnitt, tilfeldige data som ikke bør ha klynger.

• Hopkins statistikk

Det er flere formuleringer av Hopkins statistikk. En typisk er som følger. La X {\displaystyle X} være et sett av n {\displaystyle n} data poeng i d {\displaystyle d} dimensjonale rommet., Vurdere et tilfeldig utvalg (uten tilbakelegging) av m ≪ n {\displaystyle m\ll n} data poeng med medlemmer x jeg {\displaystyle x_{i}} . Også generere et sett Y {\displaystyle Y} av m {\displaystyle m} jevnt tilfeldig fordelt data poeng. Nå angi to avstand tiltak, u i {\displaystyle u_{i}} for å være avstand av y i ∈ Y {\displaystyle y_{i}\i Y} fra sin nærmeste nabo i X og w i {\displaystyle w_{i}} for å være avstand av x i ∈ X {\displaystyle x_{i}\X} fra sin nærmeste nabo i X., Vi så definere Hopkins statistikk som: H = ∑ i = 1 m u i d ∑ i = 1 m u i d + ∑ i = 1 m w i d , {\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,} Med denne definisjonen, uniform tilfeldige data bør tendens til å ha verdier nær 0.5, og samlet data bør tendens til å ha verdier nærmere 1., Imidlertid data som kun inneholder ett enkelt Variabelt vil også score nær 1, som denne statistikken måler avvik fra en uniform fordeling, ikke multimodality, noe som gjør denne statistikken i stor grad ubrukelig i programmet (som reelle data aldri er eksternt uniform).