Klusteranalys

utvärdering (eller ”validering”) av klusterresultat är lika svårt som klustringen själv. Populära tillvägagångssätt innebär ”intern” utvärdering, där klustringen sammanfattas till ett enda kvalitetsresultat, ”extern” utvärdering, där klustringen jämförs med en befintlig” ground truth ” – klassificering,” Manuell ”utvärdering av en mänsklig expert och” indirekt ” utvärdering genom att utvärdera nyttan av klustringen i sin avsedda tillämpning.,

interna utvärderingsåtgärder lider av problemet att de representerar funktioner som själva kan ses som ett klustermål. Till exempel kan man klustera de data som ställs in av Silhouettekoefficienten; förutom att det inte finns någon känd effektiv algoritm för detta. Genom att använda en sådan intern åtgärd för utvärdering jämför man snarare likheten mellan optimeringsproblemen och inte nödvändigtvis hur användbar klustringen är.,

extern utvärdering har liknande problem: om vi har sådana ”ground truth” – etiketter behöver vi inte klustera; och i praktiska tillämpningar har vi vanligtvis inte sådana etiketter. Å andra sidan återspeglar etiketterna endast en möjlig uppdelning av datauppsättningen, vilket inte innebär att det inte finns någon annan, och kanske ännu bättre, klustring.

ingen av dessa tillvägagångssätt kan därför i slutändan bedöma den faktiska kvaliteten på en klustring, men detta behöver mänsklig utvärdering, vilket är mycket subjektivt., Ändå kan sådan statistik vara ganska informativ för att identifiera dåliga kluster, men man bör inte avvisa subjektiv mänsklig utvärdering.

Intern evaluationEdit

När ett klusterresultat utvärderas baserat på de data som grupperades i sig kallas detta intern utvärdering. Dessa metoder tilldelar vanligtvis den bästa poängen till den algoritm som producerar kluster med hög likhet inom ett kluster och låg likhet mellan kluster., En nackdel med att använda interna kriterier i klusterutvärdering är att höga poäng på en intern åtgärd inte nödvändigtvis leder till effektiva informationssökningsansökningar. Dessutom är denna utvärdering partisk mot algoritmer som använder samma klustermodell. Till exempel optimerar k-means clustering naturligt objektavstånd, och ett avståndsbaserat internt kriterium kommer sannolikt att överskrida den resulterande klustringen.,

därför är de interna utvärderingsåtgärderna bäst lämpade för att få insikt i situationer där en algoritm presterar bättre än en annan, men detta får inte innebära att en algoritm ger mer giltiga resultat än en annan. Giltigheten mätt med ett sådant index beror på påståendet att denna typ av struktur finns i datamängden. En algoritm utformad för någon form av modeller har ingen chans om datauppsättningen innehåller en radikalt annorlunda uppsättning modeller, eller om utvärderingen mäter ett radikalt annat kriterium., Till exempel kan k-means klustring bara hitta konvexa kluster, och många utvärderingsindex antar konvexa kluster. På en datauppsättning med icke-konvexa kluster är varken användningen av k-medel eller ett utvärderingskriterium som förutsätter konvexitet ljud.

Mer än ett dussin interna utvärderingsåtgärder finns, vanligtvis baserat på intuitionen att objekt i samma kluster ska vara mer lika än objekt i olika kluster., följande formel: D B = 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 i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)} där n är antalet kluster, C i {\displaystyle c_{i}} är Centroid av kluster i {\displaystyle i} , σ I {\displaystyle \Sigma _{I}} är det genomsnittliga avståndet för alla element i kluster i {\displaystyle i} till centroid C i {\displaystyle c_{i}} och D ( C i , C J ) {\displaystyle d(c_{i}, c_{j})} är avståndet mellan centroiderna C i {\displaystyle c_{i}} och C J {\displaystyle C_{J}} ., Eftersom algoritmer som producerar kluster med låga intra-cluster avstånd (hög intra-cluster likhet) och höga inter-cluster avstånd (låg inter-cluster likhet) kommer att ha en låg Davies–Bouldin index, clustering algoritm som producerar en samling av kluster med de minsta Davies–Bouldin index anses vara den bästa algoritmen baserat på detta kriterium.

• Dunn index

Dunn index syftar till att identifiera täta och väl separerade kluster. Det definieras som förhållandet mellan det minimala inter-cluster avståndet till maximal intra-cluster avstånd., För varje klusterpartition kan Dunn-indexet beräknas med följande 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)}{\max _{1\leq k\leq n}d^{\Prime }(k)}}\,,} där d(i, J) representerar avståndet mellan kluster i och J,och d ’(k) mäter klusterns intra-klusteravstånd k. avståndet mellan kluster D(I, J) mellan två kluster kan vara valfritt antal avståndsåtgärder,såsom avståndet mellan klusternas centroider., På samma sätt kan avståndet d ’(k) inom klustret mätas på olika sätt, till exempel det maximala avståndet mellan ett par element i kluster k. eftersom det interna kriteriet söker kluster med hög likhet mellan kluster och låg likhet mellan kluster, är algoritmer som producerar kluster med högt Dunn-index mer önskvärda.

• Siluettkoefficient

siluettkoefficienten kontrasterar det genomsnittliga avståndet till element i samma kluster med det genomsnittliga avståndet till element i andra kluster., Objekt med högt siluettvärde anses vara väl grupperade, föremål med lågt värde kan vara avvikare. Detta index fungerar bra med k-means kluster, och används också för att bestämma det optimala antalet kluster.

extern utvärderingredigera

i extern utvärdering utvärderas klusterresultat baserat på data som inte användes för klusterning, såsom kända klassetiketter och externa riktmärken. Sådana riktmärken består av en uppsättning förklassificerade föremål, och dessa uppsättningar skapas ofta av (expert) människor., Således kan riktmärkessatserna ses som en guldstandard för utvärdering. Dessa typer av utvärderingsmetoder mäter hur nära klustringen är till de förutbestämda riktmärkesklasserna. Det har dock nyligen diskuterats om detta är tillräckligt för verkliga data, eller bara på syntetiska datamängder med en faktisk Mark sanning, eftersom klasser kan innehålla intern struktur, de attribut som finns kanske inte tillåter separation av kluster eller klasserna kan innehålla anomalier., Dessutom, ur kunskapsupptäckningssynpunkt, kan reproduktionen av känd kunskap inte nödvändigtvis vara det avsedda resultatet. I det speciella scenariot med begränsad klustring, där metainformation (t.ex. klassetiketter) redan används i klustringsprocessen, är lagring av information för utvärderingsändamål inte trivial.

ett antal åtgärder anpassas från varianter som används för att utvärdera klassificeringsuppgifter., I stället för att räkna antalet gånger en klass korrekt tilldelades en enda datapunkt (känd som sant positiva), bedömer sådana parräkningsmått om varje par datapunkter som verkligen finns i samma kluster förutses vara i samma kluster.

liksom vid intern utvärdering finns det flera externa utvärderingsåtgärder:125-129 till exempel:

• renhet: Renhet är ett mått på i vilken utsträckning kluster innehåller en enda klass. Dess beräkning kan ses som följer: för varje kluster, räkna antalet datapunkter från den vanligaste klassen i nämnda kluster., Ta nu summan över alla kluster och dividera med det totala antalet datapunkter. Formellt, med tanke på en uppsättning kluster m {\displaystyle M} och en uppsättning klasser d {\displaystyle D} , både partitionering N {\displaystyle N} datapunkter, renhet kan definieras som:

1 N M M M max D D | m d | {\displaystyle {\frac {1}{n}}\sum _{m\in m}\max _{D\in d}{|m\cap d|}} denna åtgärd straffar inte att ha många kluster, och fler kluster gör det lättare att producera en hög renhet. En renhetspoäng på 1 är alltid möjligt genom att sätta varje datapunkt i sitt eget kluster., Renhet fungerar inte heller bra för obalanserad data, där även dåligt utför klustringsalgoritmer ger ett högt renhetsvärde. Till exempel, om en storlek 1000 dataset består av två klasser, en som innehåller 999 poäng och den andra som innehåller 1 poäng, kommer varje möjlig partition att ha en renhet på minst 99,9%.

• Randindex

Randindexet beräknar hur liknande klustren (som returneras av klusteralgoritmen) är till riktmärkesklassificeringarna., Det kan beräknas med följande formel: R i = T P + T N T P + F P + f n + t n {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} där t p {\displaystyle TP} är antalet sanna positiva, T n {\displaystyle TN} är antalet sanna negativa, F p {\displaystyle FP} är antalet falska positiva, och F n {\displaystyle TN} är antalet falska positiva, displaystyle FN} är antalet falska negativ. Instanserna som räknas här är antalet korrekta parvisa uppdrag., Det vill säga, T p {\displaystyle TP} är antalet par av punkter som är klustrade ihop i den förutspådda partitionen och i ground truth-partitionen är f p {\displaystyle FP} antalet par av punkter som är klustrade ihop i den förutspådda partitionen men inte i ground truth-partitionen etc. Om datauppsättningen är av storlek N, då T P + T N + F P + F N = ( N 2 ) {\displaystyle TP+TN+FP+FN={\binom {n}{2}}} .

ett problem med Randindexet är att falska positiva och falska negativ är lika viktade. Detta kan vara en oönskad egenskap för vissa klustringsapplikationer., F-åtgärden tar upp denna oro, liksom det chanskorrigerade justerade Randindexet.

• f-measure

f-measure kan användas för att balansera bidraget från falska negativ genom viktning återkallelse genom en parameter β ≥ 0 {\displaystyle \ beta \ geq 0}. Låt precision och återkallelse (båda externa utvärderingsåtgärder i sig) definieras enligt följande: 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}}} där p {\displaystyle P} är precisionsfrekvensen och r {\displaystyle R} är återkallningsfrekvensen., Vi kan beräkna f-åtgärden genom att använda följande formel: F β = ( β 2 + 1) p 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 andra ord har återkallelsen ingen inverkan på F-åtgärden när β = 0 {\displaystyle \beta =0} , och ökande β {\displaystyle \beta } allokerar en ökande mängd vikt att återkalla i den slutliga f-åtgärden. Även t n {\displaystyle tn} beaktas inte och kan variera från 0 uppåt utan bunden.,

• Jaccard index

Jaccard index används för att kvantifiera likheten mellan två datauppsättningar. Jaccard-indexet tar ett värde mellan 0 och 1. Ett index på 1 betyder att de två datauppsättningarna är identiska, och ett index på 0 indikerar att datauppsättningarna inte har några gemensamma element. Jaccard-indexet definieras med följande formel: J (A,B ) = | A B | | A | B | = T P + F P + f N {\displaystyle J(A, B)={\frac {|a\cap B|} {|A\cup B/}}}={\frac {TP} {TP+FP+FN}}} detta är helt enkelt antalet unika element som är gemensamma för båda uppsättningarna dividerat med det totala antalet unika element i båda uppsättningarna., Även t n {\displaystyle tn} beaktas inte och kan variera från 0 uppåt utan bunden.

• Dice index

dice symmetric measure fördubblar vikten på T p {\displaystyle TP} medan du fortfarande ignorerar 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 index

The Fowlkes–Mallows index computes likheten mellan klustren som returneras av klusterningsalgoritmen och riktmärkesklassificeringarna., Ju högre värdet av Fowlkes-Mallows index desto mer liknar klustren och riktmärkesklassificeringarna är. Det kan beräknas med följande formel: F M = T P T P + F P T P + f N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}} där T p {\displaystyle TP} är antalet sanna positiva, F p {\displaystyle FP} är antalet falska positiva, och F n {\displaystyle FN} är antalet falska positiva, och F n {\displaystyle antalet falska negativ., F m {\displaystyle FM} index är det geometriska medelvärdet av precisionen och återkallandet p {\displaystyle P} och R {\displaystyle r} , och är således också känt som g-measure, medan F-measure är deras harmoniska medelvärde. Dessutom är precision och återkallelse också känd som Wallaces index B i {\displaystyle B^{i}} och B i I {\displaystyle B^{II}} . Chans normaliserade versioner av recall, precision och G-mät motsvarar Informedness, Markedness och Matthews Samband och relaterar starkt till Kappa.,

• den ömsesidiga informationen är ett informationsteoretiskt mått på hur mycket information som delas mellan en klustring och en ground-truth-klassificering som kan upptäcka en icke-linjär likhet mellan två kluster. Normaliserad ömsesidig information är en familj av korrigerade slumpvarianter av detta som har en minskad bias för varierande klusternummer.
• förvirring matris

en förvirring matris kan användas för att snabbt visualisera resultaten av en klassificering (eller klustring) algoritm. Det visar hur olika Ett kluster är från gold standard cluster.,

kluster tendencyEdit

för att mäta kluster tendens är att mäta till vilken grad kluster finns i data som ska grupperas, och kan utföras som ett första test, innan du försöker kluster. Ett sätt att göra detta är att jämföra data mot slumpmässiga data. I genomsnitt bör slumpmässiga data inte ha kluster.

• Hopkins statistik

det finns flera formuleringar av Hopkins statistik. En typisk är som följer. Låt X {\displaystyle X} vara uppsättningen av n {\displaystyle n} datapunkter i d {\displaystyle D} dimensionellt utrymme., Tänk på ett slumpmässigt prov (utan ersättning) av m mur n {\displaystyle M\ll n} datapunkter med medlemmar X i {\displaystyle x_{i}} . Generera också en uppsättning Y {\displaystyle Y} Av M {\displaystyle M} jämnt slumpmässigt fördelade datapunkter. Definiera nu två avståndsåtgärder, u i {\displaystyle u_{i}} för att vara Avståndet till Y I {\displaystyle y_{i}\in Y} från närmaste granne i X och W i {\displaystyle w_{i}} för att vara Avståndet till X i x {\displaystyle x_{i}\in x} från närmaste granne i X., Vi definierar sedan Hopkins statistik 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 denna definition bör enhetliga slumpmässiga data tenderar att ha värden nära 0,5, och grupperade data bör tenderar att ha värden närmare 1., Men data som bara innehåller en enda Gaussisk kommer också att göra poäng nära 1, eftersom denna statistik mäter avvikelse från en enhetlig fördelning, inte multimodalitet, vilket gör denna statistik till stor del värdelös i ansökan (som verkliga data aldrig är fjärr enhetlig).