Clusteranalyse

evaluatie (of “validatie”) van clustering resultaten is net zo moeilijk als de clustering zelf. Populaire benaderingen omvatten “interne” evaluatie, waarbij de clustering wordt samengevat tot een enkele kwaliteitsscore, “externe” evaluatie, waarbij de clustering wordt vergeleken met een bestaande “ground truth” classificatie, “handmatige” evaluatie door een menselijke expert, en “indirecte” evaluatie door het evalueren van het nut van de clustering in de beoogde toepassing.,

interne evaluatiemaatregelen hebben te kampen met het probleem dat zij functies vertegenwoordigen die op zichzelf als een clustering-doelstelling kunnen worden beschouwd. Bijvoorbeeld, zou men de gegevensverzameling door de silhouetcoëfficiënt kunnen clusteren; behalve dat er geen gekend efficiënt algoritme voor dit is. Door een dergelijke interne maat voor evaluatie te gebruiken, vergelijkt men eerder de gelijkenis van de optimalisatieproblemen, en niet noodzakelijkerwijs hoe nuttig de clustering is.,

externe evaluatie heeft soortgelijke problemen: als we zulke “ground truth” labels hebben, dan zouden we niet hoeven te clusteren; en in praktische toepassingen hebben we meestal geen dergelijke labels. Aan de andere kant weerspiegelen de labels slechts één mogelijke partitionering van de dataset, wat niet betekent dat er geen andere, en misschien zelfs betere, clustering bestaat.

geen van deze benaderingen kan dus uiteindelijk de werkelijke kwaliteit van een clustering beoordelen, maar dit vereist een menselijke evaluatie, die zeer subjectief is., Niettemin kunnen dergelijke statistieken vrij informatief zijn in het identificeren van slechte clusterings, maar men moet subjectieve menselijke evaluatie niet negeren.

interne evaluatiedit

wanneer een clusteringsresultaat wordt geëvalueerd op basis van de gegevens die zelf geclusterd zijn, wordt dit interne evaluatie genoemd. Deze methodes wijzen gewoonlijk de beste score aan het algoritme toe dat clusters met hoge gelijkenis binnen een cluster en lage gelijkenis tussen clusters produceert., Een nadeel van het gebruik van interne criteria bij clusterevaluatie is dat hoge scores op een interne maatregel niet noodzakelijk resulteren in effectieve toepassingen voor het ophalen van informatie. Bovendien is deze evaluatie gericht op algoritmen die hetzelfde clustermodel gebruiken. K-betekent bijvoorbeeld dat clustering op natuurlijke wijze objectafstanden optimaliseert, en een op afstand gebaseerd intern criterium zal de resulterende clustering waarschijnlijk overrate.,

daarom zijn de interne evaluatiemaatregelen het meest geschikt om enig inzicht te krijgen in situaties waarin het ene algoritme beter presteert dan het andere, maar dit betekent niet dat het ene algoritme meer valide resultaten oplevert dan het andere. Validiteit zoals gemeten door een dergelijke index hangt af van de bewering dat dit soort structuur bestaat in de dataset. Een algoritme ontworpen voor een soort van modellen heeft geen kans als de dataset bevat een radicaal andere set van modellen, of als de evaluatie meet een radicaal ander criterium., Bijvoorbeeld, K-betekent het clusteren kan slechts bolle clusters vinden, en vele evaluatieindexen veronderstellen bolle clusters. Op een gegevensverzameling met niet-convexe clusters is noch het gebruik van k-middelen, noch van een evaluatiecriterium dat convexiteit veronderstelt, gezond.

Er bestaan meer dan een dozijn interne evaluatiemetingen, meestal gebaseerd op de intuïtie dat items in dezelfde cluster meer op elkaar zouden moeten lijken dan items in verschillende clusters., volgende formule: D = 1 n ∑ i = 1 n max j ≠ i ( σ i + σ j d ( c i , c j ) ) {\displaystyle DB={\frac {1}{n}}\som _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)}, waarbij n het aantal clusters, c i {\displaystyle c_{i}} is het zwaartepunt van cluster i {\displaystyle i} σ i {\displaystyle \sigma _{i}} is de gemiddelde afstand van alle elementen in cluster i {\displaystyle i} om het zwaartepunt c i {\displaystyle c_{i}} en d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} is de afstand tussen de middelpunten c i {\displaystyle c_{i}} en c j {\displaystyle c_{j}} ., Aangezien algoritmen die clusters produceren met lage intra-cluster afstanden (hoge intra-cluster gelijkenis) en hoge inter-cluster afstanden (lage Inter–cluster gelijkenis) een lage Davies–Bouldin index zullen hebben, wordt het clustering algoritme dat een verzameling clusters produceert met de kleinste Davies-Bouldin index beschouwd als het beste algoritme op basis van dit criterium.

• Dunn index

de Dunn index is bedoeld om dichte en goed gescheiden clusters te identificeren. Het wordt gedefinieerd als de verhouding tussen de minimale interclusterafstand tot de maximale intraclusterafstand., Voor elk cluster partitie, de Dunn ‘ index kan worden berekend met de volgende formule: 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)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,} waar d(i,j) staat voor de afstand tussen de clusters i en j, en d(k) de maatregelen die de intra-cluster afstand van cluster-k). De inter-cluster-afstand d(i,j) tussen twee clusters worden een aantal van afstand maatregelen, zoals de afstand tussen de middelpunten van de clusters., Evenzo, kan de intra-clusterafstand d ‘ (k) op een verscheidenheid manieren, zoals de maximumafstand tussen om het even welk paar elementen in cluster k worden gemeten. aangezien het interne criterium clusters met hoge intra-cluster gelijkenis en lage Inter-cluster gelijkenis zoekt, zijn de algoritmen die clusters met hoge Dunn-index produceren wenselijker.

• Silhouetcoëfficiënt

de silhouetcoëfficiënt contrasteert de gemiddelde afstand tot elementen in dezelfde cluster met de gemiddelde afstand tot elementen in andere clusters., Objecten met een hoge silhouetwaarde worden als goed geclusterd beschouwd, objecten met een lage waarde kunnen uitschieters zijn. Deze index werkt goed met k-means clustering, en wordt ook gebruikt om het optimale aantal clusters te bepalen.

externe evaluatiedit

bij externe evaluatie worden de resultaten van clustering geëvalueerd op basis van gegevens die niet voor clustering zijn gebruikt, zoals bekende klassenlabels en externe benchmarks. Dergelijke benchmarks bestaan uit een set van vooraf geclassificeerde items, en deze sets worden vaak gemaakt door (deskundige) mensen., Zo kunnen de benchmarksets worden gezien als een gouden standaard voor evaluatie. Deze soorten evaluatiemethoden meten hoe dicht de clustering bij de vooraf bepaalde benchmarkklassen ligt. Onlangs is echter besproken of dit geschikt is voor echte gegevens, of alleen op synthetische gegevensreeksen met een feitelijke waarheid, aangezien klassen interne structuur kunnen bevatten, de aanwezige attributen mogelijk geen scheiding van clusters toestaan of de klassen anomalieën kunnen bevatten., Bovendien, vanuit het oogpunt van kennisontdekking, kan de reproductie van bekende kennis niet noodzakelijk het beoogde resultaat zijn. In het speciale scenario van beperkte clustering, waar meta-informatie (zoals klasselabels) al in het clustering-proces wordt gebruikt, is de hold-out van informatie voor evaluatiedoeleinden niet-triviaal.

een aantal maatregelen zijn aangepast aan de varianten die worden gebruikt om classificatietaken te evalueren., In plaats van het tellen van het aantal keren dat een klasse correct was toegewezen aan een enkel gegevenspunt (bekend als true positieven), beoordelen dergelijke paartelling metrics of elk paar gegevenspunten dat zich echt in hetzelfde cluster bevindt, wordt voorspeld dat het zich in hetzelfde cluster bevindt.

net als bij interne evaluatie bestaan er verschillende externe evaluatiemaatstaven: 125-129 bijvoorbeeld:

• zuiverheid: zuiverheid is een maat voor de mate waarin clusters één klasse bevatten. De berekening ervan kan als volgt worden gedacht: Tel voor elke cluster het aantal gegevenspunten uit de meest voorkomende klasse in de genoemde cluster., Neem nu de som over alle clusters en deel door het totale aantal gegevenspunten. Formeel gezien enkele clusters M {\displaystyle M} en enkele klassen D {\displaystyle D} , zowel partitioneren N {\displaystyle N} data punten, zuiverheid kan worden gedefinieerd als:

1 N ∑ m ∈ M max d ∈ D | m ∩ d | {\displaystyle {\frac {1}{N}}\som _{m\in M}\max _{d\in D}{|m\cap d|}} Deze maatregel niet bestraffen met vele clusters, en meer clusters zal het gemakkelijker maken om een hoge zuiverheid. Een zuiverheidsscore van 1 is altijd mogelijk door elk gegevenspunt in zijn eigen cluster te plaatsen., Zuiverheid werkt ook niet goed voor onevenwichtige data, waar zelfs slecht presterende clustering algoritmen een hoge zuiverheid waarde zal geven. Bijvoorbeeld, als een dataset met grootte 1000 uit twee klassen bestaat, één met 999 punten en de andere met 1 punt, dan zal elke mogelijke partitie een zuiverheid hebben van ten minste 99,9%.

• Rand index

de Rand index berekent hoe vergelijkbaar de clusters (geretourneerd door het clustering algoritme) zijn met de benchmark classificaties., Het kan worden berekend met behulp van de volgende formule: R I = T P + T N T P + F P + F N + T n {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} waar T P {\displaystyle TP} het aantal echte positieven is, T N {\displaystyle TN} het aantal echte negatieven, F P {\displaystyle FP} het aantal valse positieven, en F N {\displaystyle FN} is het aantal valse negatieven. De instanties die hier worden geteld zijn het aantal correcte paarsgewijze toewijzingen., Dat wil zeggen, T P {\displaystyle TP} is het aantal paren van punten die samen zijn geclusterd in de voorspelde partitie en in de ground truth partitie, F P {\displaystyle FP} is het aantal paren van punten die samen zijn geclusterd in de voorspelde partitie, maar niet in de ground truth partitie etc. Als de dataset grootte N heeft, dan T P + T N + F P + F N = (N 2 ) {\displaystyle TP+TN + FP+FN = {\binom {N}{2}}} .

een probleem met de Rand-index is dat false positieven en false negatieven gelijk worden gewogen. Dit kan een ongewenst kenmerk zijn voor sommige clustering toepassingen., De F-maatregel pakt dit probleem aan, evenals de chance-corrected adjusted Rand index.

• F-maat

de F-maat kan worden gebruikt om de bijdrage van valse negatieven te balanceren door het terugroepen te wegen via een parameter β ≥ 0 {\displaystyle \beta \geq 0} . Laat precisie en terugroepactie (beide externe evaluatiematen op zich) als volgt gedefinieerd worden: P = 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}}} waarin P {\displaystyle P} de precisiesnelheid is en R {\displaystyle R} de terugroepactiesnelheid., We kunnen de F-maat berekenen met behulp van de volgende formule: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ P + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}} wanneer β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . Met andere woorden, recall heeft geen invloed op de F-maat wanneer β = 0 {\displaystyle \beta =0} , en toenemende β {\displaystyle \beta } wijst een toenemende hoeveelheid gewicht toe aan recall in de uiteindelijke F-maat. Ook T n {\displaystyle TN} wordt niet in aanmerking genomen en kan variëren van 0 naar boven zonder gebonden.,

• Jaccard-index

de Jaccard-index wordt gebruikt om de gelijkenis tussen twee datasets te kwantificeren. De Jaccard-index heeft een waarde tussen 0 en 1. Een index van 1 betekent dat de twee datasets identiek zijn, en een index van 0 geeft aan dat de datasets geen gemeenschappelijke elementen hebben. De Jaccard-index wordt gedefinieerd door de volgende formule: 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}}}} dit is gewoon het aantal unieke elementen gedeeld door het totale aantal unieke elementen in beide verzamelingen., Ook T n {\displaystyle TN} wordt niet in aanmerking genomen en kan variëren van 0 naar boven zonder gebonden.

• dobbelstenen index

de dobbelstenen symmetrische maat verdubbelt het gewicht op T P {\displaystyle TP} terwijl T N {\displaystyle TN} nog steeds wordt genegeerd : D S C = 2 T P 2 T P + F P + F N {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}

• Fowlkes–Mallows index

mallows index berekent de gelijkenis tussen de clusters geretourneerd door de clustering algoritme en de benchmark classificaties., Hoe hoger de waarde van de Fowlkes–Mallows index hoe meer vergelijkbaar de clusters en de benchmark classificaties zijn. Het kan worden berekend met behulp van de volgende formule: 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}}}}} waar T P {\displaystyle TP} het aantal echte positieven is, F P {\displaystyle FP} het aantal valse positieven, en F N {\displaystyle FN} is het aantal valse negatieven., De F M {\displaystyle FM} index is het geometrisch gemiddelde van de precisie en recall P {\displaystyle P} en R {\displaystyle R}, en is dus ook bekend als de G-maat, terwijl de F-Maat hun harmonisch gemiddelde is. Bovendien staan precisie en recall ook bekend als Wallace ‘ s indices B I {\displaystyle B^{I}} en B I I {\displaystyle B^{II}} . Toevallige genormaliseerde versies van recall, precisie en G-maat komen overeen met Informedness, Markedness en Matthews correlatie en hebben sterk betrekking op Kappa.,

• de wederzijdse informatie is een informatietheoretische maat voor hoeveel informatie wordt gedeeld tussen een clustering en een grondwaarheidsclassificatie die een niet-lineaire gelijkenis tussen twee clusteringen kan detecteren. Genormaliseerde Wederzijdse informatie is een familie van gecorrigeerde-voor-kans varianten hiervan die een verminderde bias voor variërende clusteraantallen heeft.
• Verwarmingsmatrix

een verwarmingsmatrix kan worden gebruikt om snel de resultaten van een classificatie (of clustering) algoritme te visualiseren. Het laat zien hoe verschillend een cluster is van de gouden standaard cluster.,

cluster tendencyEdit

het meten van clusterneiging is het meten in welke mate clusters bestaan in de gegevens die geclusterd moeten worden, en kan worden uitgevoerd als een eerste test, alvorens te clusteren. Een manier om dit te doen is om de gegevens te vergelijken met willekeurige gegevens. Gemiddeld zouden willekeurige gegevens geen clusters moeten hebben.

• Hopkins statistiek

er zijn meerdere formuleringen van de Hopkins statistiek. Een typische is als volgt. Zij X {\displaystyle X} de verzameling van n {\displaystyle n} datapunten in D {\displaystyle d} dimensionale ruimte., Overweeg een willekeurige steekproef (zonder vervanging) van M ≪ n {\displaystyle m\ll n} gegevenspunten met leden x i {\displaystyle x_{i}} . Genereer ook een verzameling Y {\displaystyle Y} van M {\displaystyle m} gelijkmatig willekeurig verdeelde gegevenspunten. Definieer nu twee afstandsmaten, u i {\displaystyle u_{i}} als de afstand van y I ∈ Y {\displaystyle y_{i}\in Y} van zijn dichtstbijzijnde buur in X en w i {\displaystyle w_{i}} als de afstand van x i ∈ X {\displaystyle x_{i}\in X} van zijn dichtstbijzijnde buur in X., Vervolgens definiëren we de Hopkins-statistiek Als: 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}+\sum _{i=1}^{m} {w_{i}^{d}}}}\,,} met deze definitie zouden uniforme willekeurige gegevens waarden in de buurt van 0,5 moeten hebben, en geclusterde gegevens zouden waarden in de buurt van 1 moeten hebben., Echter, gegevens die slechts een enkele Gaussian zal ook scoren dicht bij 1, omdat deze statistiek meet afwijking van een uniforme verdeling, niet multimodaliteit, waardoor deze statistiek grotendeels nutteloos in toepassing (als echte gegevens nooit is op afstand uniform).