evaluering (eller “validering”) af klyngeresultater er lige så vanskelig som selve klyngedannelsen. Populære metoder indebærer “intern” evaluering, hvor clustering er sammenfattet til et enkelt kvalitetsresultat, som er “eksterne” evaluering, hvor clustering er i forhold til en eksisterende “ground truth” klassificering, “manuel” evaluering af en menneskelig ekspert, og “indirekte” evaluering ved at evaluere nytten af klyngedannelse i dets tilsigtede anvendelse.,
interne evalueringsforanstaltninger lider af problemet, at de repræsenterer funktioner, der selv kan ses som et klyngemål. For eksempel kunne man klynge datasættet ved hjælp af Silhuetkoefficienten; bortset fra at der ikke er nogen kendt effektiv algoritme til dette. Ved at bruge en sådan intern foranstaltning til evaluering sammenligner man snarere ligheden mellem optimeringsproblemerne, og ikke nødvendigvis hvor nyttig klyngen er.,
ekstern evaluering har lignende problemer: hvis vi har sådanne “ground truth” – etiketter, behøver vi ikke at klynge; og i praktiske anvendelser har vi normalt ikke sådanne etiketter. På den anden side afspejler etiketterne kun en mulig opdeling af datasættet, hvilket ikke indebærer, at der ikke findes en anden, og måske endnu bedre, klyngedannelse.
ingen af disse tilgange kan derfor i sidste ende bedømme den faktiske kvalitet af en klynge, men dette har brug for menneskelig evaluering, hvilket er meget subjektivt., Ikke desto mindre kan sådanne statistikker være ret informative til at identificere dårlige klynger, men man bør ikke afvise subjektiv menneskelig evaluering.
Indre evaluationEdit
Når en gruppering resultatet er vurderet baseret på de data, der blev grupperet sig selv, dette kaldes interne evaluering. Disse metoder tildeler normalt den bedste score til algoritmen, der producerer klynger med høj lighed inden for en klynge og lav lighed mellem klynger., En ulempe ved at bruge interne kriterier i klyngeevaluering er, at høje score på en intern foranstaltning ikke nødvendigvis resulterer i effektive applikationer til informationssøgning. Derudover er denne evaluering partisk over for algoritmer, der bruger den samme klyngemodel. For eksempel, K-betyder clustering optimerer naturligt objektafstande, og et afstandsbaseret internt kriterium vil sandsynligvis overgå den resulterende klyngedannelse.,
derfor er de interne evalueringsforanstaltninger bedst egnede til at få et indblik i situationer, hvor en algoritme udfører bedre end en anden, men dette indebærer ikke, at en algoritme giver mere gyldige resultater end en anden. Gyldighed som målt ved et sådant indeks afhænger af påstanden om, at denne form for struktur findes i datasættet. En algoritme designet til en slags modeller har ingen chance, hvis datasættet indeholder et radikalt andet sæt modeller, eller hvis evalueringen måler et radikalt andet kriterium., For eksempel kan k-betyder klyngedannelse kun finde konvekse klynger, og mange evalueringsindekser antager konvekse klynger. På et datasæt med ikke-konvekse klynger er hverken brugen af k-midler eller et evalueringskriterium, der antager konveksitet, lyd.
Der findes mere end et dusin interne evalueringsforanstaltninger, normalt baseret på intuitionen om, at elementer i den samme klynge skal være mere ens end elementer i forskellige klynger., følgende formel: D = 1 n ∑ i = 1 n max j ≠ i ( σ i + σ j d ( c i , c j ) ) {\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq jeg}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{jeg},c_{j})}}\right)}, hvor n er antallet af klynger, k {\displaystyle c_{jeg}} er barycentrum af klyngen i {\displaystyle jeg} , σ i {\displaystyle \sigma _{i}} er den gennemsnitlige afstand af alle elementer i klyngen i {\displaystyle jeg på} for at barycentrum k {\displaystyle c_{i}} , og d ( c i , c j ) {\displaystyle d(c_{jeg},c_{j})} er afstanden mellem centroids k {\displaystyle c_{jeg}} og c j {\displaystyle c_{j}} ., Da algoritmer, der producerer klynger med lave intra-cluster afstande (høj intra-cluster lighed) og høj inter-klynge afstande (lav inter-klynge lighed) vil have en lav Davies–Bouldin indeks, clustering algoritme, der producerer en samling af klynger med den mindste Davies–Bouldin indekset betragtes som den bedste algoritme, der er baseret på dette kriterium. Dunn-indekset har til formål at identificere tætte og godt adskilte klynger. Det er defineret som forholdet mellem den minimale inter-cluster Afstand til maksimal intra-cluster afstand., For hver klynge partition, Dunn-indekset 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 i<j\leq n}d(i,j)}{\antal _{1\leq k\leq n}d^{\prime }(k)}}\,,}, hvor d(i,j) repræsenterer den afstand mellem klynger i og j, og d ‘(k) foranstaltninger intra-cluster afstand i cluster k. Inter-klynge afstand d(i,j) mellem to klynger kan være hvilket som helst antal af afstand foranstaltninger, såsom afstanden mellem centroids af klynger., På samme måde, intra-cluster afstand d(k) kan måles på forskellige måder, sådan som den maksimale afstand mellem ethvert par af elementer i cluster k. Da indre kriterium søge klynger med høj intra-cluster lighed og lave inter-klynge lighed, algoritmer, der producerer klynger med høj Dunn-indekset er mere ønskeligt.
- Silhuet koefficient
silhuet koefficient, der kontrasterer den gennemsnitlige afstand til elementer i den samme klynge med den gennemsnitlige afstand til elementer i andre klynger., Objekter med en høj silhuetværdi betragtes som godt grupperet, objekter med en lav værdi kan være outliers. Dette indeks fungerer godt med K-betyder klyngedannelse, og bruges også til at bestemme det optimale antal klynger.
ekstern evaluationEdit
i ekstern evaluering evalueres klyngeresultater baseret på data, der ikke blev brugt til klyngedannelse, såsom kendte klassemærker og eksterne benchmarks. Sådanne benchmarks består af et sæt af præ-klassificerede elementer, og disse sæt er ofte skabt af (ekspert) mennesker., Benchmark-sætene kan således betragtes som en guldstandard til evaluering. Disse typer evalueringsmetoder måler, hvor tæt klyngen er på de forudbestemte benchmarkklasser. Imidlertid, det er for nylig blevet drøftet, om dette er tilstrækkeligt til reelle data, eller kun på syntetiske datasæt med en faktuel grundsandhed, da klasser kan indeholde intern struktur, de tilstedeværende attributter tillader muligvis ikke adskillelse af klynger, eller klasserne kan indeholde afvigelser., Ud fra et videnopdagelsessynspunkt er reproduktion af kendt viden muligvis ikke nødvendigvis det tilsigtede resultat. I det specielle scenarie med begrænset klyngedannelse, hvor meta-information (såsom klassemærker) allerede bruges i klyngeprocessen, er hold-out af information til evalueringsformål ikke-triviel.
en række foranstaltninger tilpasses fra varianter, der bruges til at evaluere klassificeringsopgaver., I stedet for at tælle antallet af gange en klasse blev korrekt tildelt et enkelt datapunkt (kendt som sande positive), vurderer sådanne partællingsmetrics, om hvert par datapunkter, der virkelig er i den samme klynge, forudsiges at være i den samme klynge.
som med intern evaluering findes der flere eksterne evalueringsforanstaltninger:125-129 for eksempel:
- renhed: renhed er et mål for, i hvilket omfang klynger indeholder en enkelt klasse. Dens beregning kan tænkes som følger: for hver klynge tæller antallet af datapunkter fra den mest almindelige klasse i nævnte klynge., Tag nu summen over alle klynger og divider med det samlede antal datapunkter. Formelt, da nogle sæt af klynger M {\displaystyle M}, og nogle klasser, D {\displaystyle D} , både partitionering N {\displaystyle N} datapunkter, renhed kan defineres som:
1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\sum _{m\i M}\max _{d\i D}{|m\cap d|}} Denne foranstaltning ikke straffe der mange klynger, og flere klynger vil gøre det lettere at producere en høj renhed. En renhed score på 1 er altid muligt ved at sætte hvert datapunkt i sin egen klynge., Renhed fungerer heller ikke godt for ubalancerede data, hvor selv dårligt udførte klyngealgoritmer vil give en høj renhedsværdi. For eksempel, hvis en størrelse 1000 datasæt består af to klasser, den ene indeholder 999 point og den anden indeholder 1 point, vil hver mulig partition have en renhed på mindst 99,9%.
- Rand-indeks
Rand-indekset beregner, hvor lignende klyngerne (returneret af klyngealgoritmen) er til benchmark-klassificeringerne., Det kan beregnes ved hjælp af følgende formel: R = T S + T N T P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}, hvor T P {\displaystyle TP} er antallet af sande positive, T N {\displaystyle TN} er antallet af sandt negative, F P {\displaystyle FP} er antallet af falske positiver, og F N {\displaystyle FN} er antallet af falske negativer. De tilfælde, der tælles her, er antallet af korrekte parvise opgaver., Der er, T P {\displaystyle TP} er antallet af par af punkter, der er grupperet sammen i den forudsagte partition og i jorden sandheden partition, F P {\displaystyle FP} er antallet af par af punkter, der er grupperet sammen i den forudsagte partition, men ikke i jorden sandheden partition, osv. Hvis datasættet er af størrelse N, er T P + T N + F P + F N = ( N 2 ) {\displaystyle TP+TN+FP+FN={\binom {N}{2}}} .
et problem med Rand-indekset er, at falske positiver og falske negativer er lige vægtede. Dette kan være en uønsket egenskab for nogle klyngeapplikationer., F-foranstaltningen adresserer denne bekymring, ligesom det chance-korrigerede justerede Rand-indeks.
- f-measure
f-measure kan bruges til at afbalancere bidrag falske negativer ved vægtning tilbagekaldelse gennem en parameter β 0 0 {\displaystyle \beta \ge .0}. Lad præcision og recall (både ekstern evaluering foranstaltninger, der i sig selv) være defineret som følger: S = T P T P + F P {\displaystyle P={\frac {TP}{TP+FP}}} R = T P T P + F N {\displaystyle R={\frac {TP}{TP+FN}}} hvor P {\displaystyle P} er den præcision, hastighed og R {\displaystyle R} er den husker sats., Vi kan beregne F-mål ved hjælp af følgende formel: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ P + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}} Når β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Med andre ord har tilbagekaldelse ingen indflydelse på f-foranstaltningen , når β = 0 {\displaystyle \beta =0}, og stigende β {\displaystyle \beta } tildeler en stigende mængde vægt til tilbagekaldelse i den endelige F-foranstaltning. Også t n {\displaystyle TN} tages ikke i betragtning og kan variere fra 0 opad uden bundet.,
- Jaccard inde.
Jaccard inde. bruges til at kvantificere ligheden mellem to datasæt. Jaccard-indekset får en værdi mellem 0 og 1. Et indeks på 1 betyder, at de to datasæt er identiske, og et indeks på 0 indikerer, at datasættene ikke har fælles elementer. Den Jaccard-indekset er defineret ved følgende formel: J ( A , B ) = | A ∩ B | | A ∪ B | = T P T P + F P + F N {\displaystyle J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}} Det er simpelthen antallet af unikke elementer som er fælles for begge sæt divideret med det samlede antal unikke elementer i begge sæt., Også t n {\displaystyle TN} tages ikke i betragtning og kan variere fra 0 opad uden bundet.
- Terninger index
Terningerne symmetrisk foranstaltning fordobler vægt på T P {\displaystyle TP}, mens du stadig ignorerer T N {\displaystyle TN} : D S C = 2 T S 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}
- Fowlkes–Mallows index
Den Fowlkes–Mallows index beregner lighed mellem de klynger, der returneres af clustering algoritme og benchmark klassifikationer., Jo højere værdien af Fo .lkes-Mallo .s indekset mere ens klynger og benchmark klassifikationer er. Det kan beregnes ved hjælp af følgende formel: F M = T P T P + F P ⋅ T P T P + F N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}}, hvor T P {\displaystyle TP} er antallet af sande positive, F P {\displaystyle FP} er antallet af falske positiver, og F N {\displaystyle FN} er antallet af falske negativer., F M {\displaystyle FM} – indekset er den geometriske middelværdi af precision og recall P {\displaystyle P} og R {\displaystyle R} , og er derfor også kendt som G-foranstaltning, mens F-foranstaltning er deres harmonisk gennemsnit. Desuden er præcision og tilbagekaldelse også kendt som indicesallace ‘ s indekser B i {\displaystyle B^{i}} og B i i {\displaystyle B^{II}} . Chance normaliseret versioner af recall, precision og G-foranstaltning, der svarer til Informedness, Markedness og Matthews Sammenhæng og forholde sig kraftigt til Kappa.,
- den gensidige information er et informationsteoretisk mål for, hvor meget information der deles mellem en klyngedannelse og en jord-sandhedsklassifikation, der kan registrere en ikke-lineær lighed mellem to klynger. Normaliseret gensidig information er en familie af korrigerede-for-chance-varianter af dette, der har en reduceret bias for forskellige klyngetal.
- forvirring Matri.
en forvirring Matri. kan bruges til hurtigt at visualisere resultaterne af en klassificering (eller clustering) algoritme. Det viser, hvor forskellig En klynge er fra guldstandardklyngen.,
Cluster tendencyEdit
At måle cluster tendens er at måle, i hvilken grad klynger findes i data til at blive grupperet, og kan udføres som en indledende test, før du forsøger klyngedannelse. En måde at gøre dette på er at sammenligne dataene med tilfældige data. I gennemsnit bør tilfældige data ikke have klynger.Hopkins statistik der er flere formuleringer af Hopkins statistik. En typisk er som følger. Lad {{\displaystyle}} være sæt af n {\displaystyle n} datapunkter i d {\displaystyle d} dimensionelle rum., Overvej en tilfældig prøve (uden udskiftning) af M {n {\displaystyle M\ll n} datapunkter med medlemmer i i {\displaystyle ._ {i}} . Generer også et sæt y {\displaystyle Y} af m {\displaystyle m} ensartet tilfældigt fordelte datapunkter. Nu definere to afstanden foranstaltninger, u {\displaystyle u_{jeg}} til at være den afstand af y i ∈ Y {\displaystyle y_{jeg}\i Y} fra sin nærmeste nabo i X og w i {\displaystyle w_{jeg}} til at være den afstand af x i ∈ X {\displaystyle x_{i}\i X} fra sin nærmeste nabo i X., Vi så definere Hopkins statistik, som: H = ∑ i = 1 n u i u ∑ i = 1 m u n d i + ∑ i = 1 m y n d i {\displaystyle H={\frac {\sum _{i=1}^{m}{u_{jeg}^{d}}}{\sum _{i=1}^{m}{u_{jeg}^{d}}+\sum _{i=1}^{m}{w_{jeg}^{d}}}}\,,} Med denne definition, uniform tilfældig data bør tendens til at have værdierne tæt på 0.5, og grupperede data bør tendens til at have værdier, der er tættere på 1., Imidlertid vil data, der kun indeholder en enkelt Gauss, også score tæt på 1, da denne statistik måler afvigelse fra en ensartet fordeling, ikke multimodalitet, hvilket gør denne statistik stort set ubrugelig i applikationen (da reelle data aldrig er fjernt ensartet).