Klyngeanalyse - Cluster analysis

Klyngeanalyse eller gruppering er oppgaven med å gruppere et sett med objekter på en slik måte at objekter i samme gruppe (kalt en klynge ) er mer like (på en eller annen måte) til hverandre enn de i andre grupper (klynger). Det er en hovedoppgave med utforskende dataanalyse og en vanlig teknikk for statistisk dataanalyse , brukt på mange felt, inkludert mønstergjenkjenning , bildeanalyse , informasjonsinnhenting , bioinformatikk , datakomprimering , datagrafikk og maskinlæring .

Klyngeanalyse i seg selv er ikke en spesifikk algoritme , men den generelle oppgaven som skal løses. Det kan oppnås med forskjellige algoritmer som er vesentlig forskjellige i deres forståelse av hva som utgjør en klynge og hvordan man effektivt finner dem. Populære forestillinger om klynger inkluderer grupper med små avstander mellom klyngemedlemmer, tette områder i datarommet, intervaller eller bestemte statistiske fordelinger . Klynger kan derfor formuleres som et flerobjektivt optimaliseringsproblem . Den passende klyngealgoritmen og parameterinnstillingene (inkludert parametere som avstandsfunksjonen som skal brukes, en tetthetsterskel eller antall forventede klynger) avhenger av det individuelle datasettet og beregnet bruk av resultatene. Klyngeanalyse som sådan er ikke en automatisk oppgave, men en iterativ prosess for kunnskapsoppdagelse eller interaktiv flerobjektiv optimalisering som innebærer prøving og feil. Det er ofte nødvendig å endre databehandlingen og modellparametere til resultatet oppnår de ønskede egenskapene.

I tillegg til begrepet clustering , er det en rekke begreper med lignende betydninger, inkludert automatisk klassifisering , numerisk taksonomi , botryologi (fra gresk βότρυς "drue"), typologisk analyse og samfunnsdeteksjon . De subtile forskjellene er ofte i bruken av resultatene: mens i data mining er de resulterende gruppene et spørsmål om interesse, i automatisk klassifisering er den resulterende diskriminerende kraften av interesse.

Klyngeanalyse kom fra antropologi av Driver og Kroeber i 1932 og ble introdusert for psykologi av Joseph Zubin i 1938 og Robert Tryon i 1939 og ble kjent brukt av Cattell fra 1943 for egenskapsteori -klassifisering i personlighetspsykologi .

Definisjon

Forestillingen om en "klynge" kan ikke defineres nøyaktig, noe som er en av grunnene til at det er så mange klynge -algoritmer. Det er en fellesnevner: en gruppe dataobjekter. Imidlertid bruker forskjellige forskere forskjellige klyngemodeller, og for hver av disse klyngemodellene kan det igjen gis forskjellige algoritmer. Tanken om en klynge, som den finnes av forskjellige algoritmer, varierer betydelig i dens egenskaper. Å forstå disse "klyngemodellene" er nøkkelen til å forstå forskjellene mellom de forskjellige algoritmene. Typiske klyngemodeller inkluderer:

• Tilkoblingsmodell s: for eksempelbyggerhierarkisk klyngemodeller basert på avstandstilkobling.
• Centroid modell s: for eksempel representererk-middelalgoritmenhver klynge av en enkelt gjennomsnittsvektor.
• Distribusjonsmodell s: klynger modelleres ved hjelp av statistiske distribusjoner, for eksempelmultivariate normalfordelinger sombrukes avalgoritmen for forventningsmaksimering.
• Tetthetsmodell s:DBSCANogOPTICSdefinererfor eksempelklynger som tilkoblede tette områder idatarommet.
• Underrom modell s: ibiclustering(også kjent som ko-gruppering eller to-modus-clustering), blir klynger modellert med både klynge medlemmer og relevante attributter.
• Gruppe modell s: noen algoritmer gir ikke en raffinert modell for sine resultater og bare gi den gruppering informasjon.
• Grafbasert modell s: enklikk, det vil si et delsett med noder i engrafslik at hver to noder i delsettet er forbundet med en kant, kan betraktes som en prototypisk form for klynge. Avslapninger av det komplette kravet til tilkobling (en brøkdel av kantene kan mangle) er kjent som kvasiklikker, som iHCS-grupperingsalgoritmen.
• Signerte grafmodeller : Hver bane i en signert graf har et tegn fra produktet av skiltene på kantene. Under forutsetningene om balanse teori kan kanter endre tegn og resultere i en todelt graf. Det svakere "clusterability axiom" (ingen syklus har nøyaktig en negativ kant) gir resultater med mer enn to klynger, eller subgrafer med bare positive kanter.
• Neural modell s: den mest kjenteuten tilsyn neurale nettverker detselvorganiserende kartog disse modellene kan vanligvis karakteriseres som ligner på en eller flere av de ovennevnte modeller, og herunder subrom modeller når nevrale nettverk implementerer en form forPrincipal Component AnalysisellerUavhengig komponentanalyse.

En "klynging" er i hovedsak et sett med slike klynger, som vanligvis inneholder alle objektene i datasettet. I tillegg kan det spesifisere forholdet mellom klyngene til hverandre, for eksempel et hierarki av klynger som er innebygd i hverandre. Klynger kan grovt skilles som:

• Hard gruppering : hvert objekt tilhører en klynge eller ikke
• Soft clustering (også:uklar klynge): hvert objekt tilhører hver klynge til en viss grad (for eksempel en sannsynlighet for å tilhøre klyngen)

Det er også mulig å skille bedre, for eksempel:

• Streng partisjoneringsklynge : hvert objekt tilhører nøyaktig en klynge
• Strenge partisjoneringsklynger med ekstremer : objekter kan også tilhøre ingen klynge, og regnes somekstreme
• Overlappende klynger (også:alternativ klynger,klynger medflere visninger): objekter kan tilhøre mer enn én klynge; vanligvis involverer harde klynger
• Hierarkisk klynge: objekter som tilhører en barneklynge tilhører også den overordnede klyngen
• Klynger i mellomrom : mens en overlappende klynge, innenfor et unikt definert delrom, forventes det ikke at klynger overlapper hverandre

Algoritmer

Som angitt ovenfor, kan gruppering algoritmer kategoriseres basert på deres klyngemodell. Oversikten nedenfor viser bare de mest fremtredende eksemplene på klyngealgoritmer, siden det muligens er over 100 publiserte klyngealgoritmer. Ikke alle tilbyr modeller for sine klynger og kan derfor ikke lett kategoriseres. En oversikt over algoritmer forklart i Wikipedia finnes i listen over statistiske algoritmer .

Det er ingen objektivt "korrekt" klyngealgoritme, men som det ble bemerket, er "klynging i øyet til betrakteren." Den mest passende klyngealgoritmen for et bestemt problem må ofte velges eksperimentelt, med mindre det er en matematisk grunn til å foretrekke en klyngemodell fremfor en annen. En algoritme som er designet for en slags modell, vil vanligvis mislykkes på et datasett som inneholder en radikalt annen type modell. For eksempel kan ikke k-midler finne ikke-konvekse klynger.

Tilkoblingsbasert klynge (hierarkisk klynge)

Tilkoblingsbasert klynge, også kjent som hierarkisk klynge , er basert på kjernetanken om at objekter er mer relatert til objekter i nærheten enn til objekter lenger unna. Disse algoritmene forbinder "objekter" for å danne "klynger" basert på avstanden deres. En klynge kan i stor grad beskrives med den maksimale avstanden som trengs for å koble deler av klyngen. På forskjellige avstander vil det dannes forskjellige klynger, som kan representeres ved hjelp av et dendrogram , som forklarer hvor det vanlige navnet " hierarkisk klynge " kommer fra: Disse algoritmene gir ikke en enkelt partisjonering av datasettet, men gir i stedet et omfattende hierarki av klynger som smelter sammen med hverandre på bestemte avstander. I et dendrogram markerer y-aksen avstanden klyngene smelter sammen med, mens objektene plasseres langs x-aksen slik at klyngene ikke blandes.

Tilkoblingsbasert gruppering er en hel familie av metoder som er forskjellige med hensyn til avstandenes beregning. Bortsett fra det vanlige valget av avstandsfunksjoner , må brukeren også bestemme koblingskriteriet (siden en klynge består av flere objekter, er det flere kandidater for å beregne avstanden) for å bruke. Populære valg er kjent som single-linkage clustering (minimum av objektavstander ), komplett linkage clustering (maksimum av objektavstander ) og UPGMA eller WPGMA ("Unweighted or Weighted Pair Group Method with Arithmetic Mean", også kjent som gjennomsnittlig kobling gruppering). Videre kan hierarkisk gruppering være agglomerativ (starter med enkeltelementer og samler dem i klynger) eller deler (starter med det komplette datasettet og deler det i partisjoner).

Disse metodene vil ikke produsere en unik partisjonering av datasettet, men et hierarki som brukeren fremdeles trenger å velge passende klynger fra. De er ikke veldig robuste mot ekstremer, som enten vil dukke opp som flere klynger eller til og med få andre klynger til å slå seg sammen (kjent som "kjedefenomen", spesielt med enkeltkoblingsklynger ). I det generelle tilfellet er kompleksiteten for agglomerativ klynge og for splittende klynger , noe som gjør dem for trege for store datasett. For noen spesielle tilfeller er optimale effektive metoder (av kompleksitet ) kjent: SLINK for enkelkobling og CLINK for fullstendig kobling. I data mining -samfunnet er disse metodene anerkjent som et teoretisk grunnlag for klyngeanalyse, men anses ofte som foreldede. De ga imidlertid inspirasjon til mange senere metoder, for eksempel tetthetsbasert gruppering. ${\ displaystyle {\ mathcal {O}} (n^{3})}$${\ displaystyle {\ mathcal {O}} (2^{n-1})}$${\ displaystyle {\ mathcal {O}} (n^{2})}$

• Eksempler på koblingsklynger
• 

  Enkeltkobling på gaussiske data. På 35 klynger begynner den største klyngen å fragmentere seg i mindre deler, mens den før var koblet til den nest største på grunn av enkeltkoblingseffekten.

• 

  Enkeltkobling på tetthetsbaserte klynger. 20 klynger ekstrahert, hvorav de fleste inneholder enkeltelementer, siden koblingsklynger ikke har en forestilling om "støy".

Sentroidbasert gruppering

I sentroidbasert klynge er klynger representert av en sentral vektor, som kanskje ikke nødvendigvis er medlem av datasettet. Når antallet av klynger er festet til k , k Vaskeren gruppering gir en formell definisjon som et optimaliseringsproblem: finne k klyngen sentre og tildele gjenstandene til nærmeste klyngen sentrum, slik at de kvadrerte avstander fra klyngen er minimalisert.

Selve optimaliseringsproblemet er kjent for å være NP-hardt , og derfor er den vanlige tilnærmingen å bare søke etter omtrentlige løsninger. En spesielt kjent omtrentlig metode er Lloyds algoritme , ofte bare referert til som " k-betyr algoritme " (selv om en annen algoritme introduserte dette navnet ). Den finner imidlertid bare en lokal optimal , og kjøres vanligvis flere ganger med forskjellige tilfeldige initialiseringer. Variasjoner av k -midler inkluderer ofte slike optimaliseringer som å velge det beste av flere kjøringer, men også å begrense sentroidene til medlemmer av datasettet ( k -medoider ), velge medianer ( k -medians klynger ), velge de første sentrene mindre tilfeldig ( k -means ++ ) eller tillate en uklar klyngeoppgave ( uklar c -betyr ).

De fleste k Vaskeren-type algoritmer krever antall klynger - k - skal spesifiseres på forhånd, noe som er ansett å være en av de største ulempene med disse algoritmene. Videre foretrekker algoritmene klynger av omtrent samme størrelse, ettersom de alltid vil tilordne et objekt til nærmeste sentroid. Dette fører ofte til feil kuttede grenser for klynger (noe som ikke er overraskende siden algoritmen optimaliserer klyngesentre, ikke klyngegrenser).

K-midler har en rekke interessante teoretiske egenskaper. Først deler det datarommet inn i en struktur kjent som et Voronoi -diagram . For det andre er det konseptuelt nær klassifisering av nærmeste nabo, og som sådan er det populært innen maskinlæring . For det tredje kan det sees på som en variant av modellbasert klynging, og Lloyds algoritme som en variant av forventnings-maksimeringsalgoritmen for denne modellen som er diskutert nedenfor.

• k -betyr klyngeeksempler
• 

  k -betyr skiller data inn i Voronoi -celler, som forutsetter klynger av samme størrelse (ikke tilstrekkelig her)

• 

  k -midler kan ikke representere tetthetsbaserte klynger

Sentroid -baserte klyngeproblemer som k -midler og k -medoider er spesielle tilfeller av det ubegrensede, metriske lokaliseringsproblemet , et kanonisk problem i operasjonsforskningen og beregningsmessige geometri -miljøer . I et grunnleggende anleggslokaliseringsproblem (hvorav det er mange varianter som modeller mer utførlige innstillinger), er oppgaven å finne de beste lagerstedene for å betjene et gitt sett med forbrukere optimalt. Man kan se på "lagre" som klyngesentroider og "forbrukersteder" som dataene som skal grupperes. Dette gjør det mulig å anvende de velutviklede algoritmiske løsningene fra lokaliseringslitteraturen til det sentroidbaserte klyngeproblemet som nå anses.

Distribusjonsbasert gruppering

Klyngemodellen som er nærmest relatert til statistikk er basert på distribusjonsmodeller . Klynger kan da enkelt defineres som objekter som mest sannsynlig tilhører samme fordeling. En praktisk egenskap ved denne tilnærmingen er at denne ligner veldig på måten kunstige datasett genereres: ved å sampler tilfeldige objekter fra en distribusjon.

Selv om det teoretiske grunnlaget for disse metodene er utmerket, lider de av et sentralt problem kjent som overmontering , med mindre det settes begrensninger på modellkompleksiteten. En mer kompleks modell vil vanligvis kunne forklare dataene bedre, noe som gjør det vanskelig å velge riktig modellkompleksitet.

En fremtredende metode er kjent som gaussiske blandingsmodeller (ved hjelp av algoritmen for forventnings-maksimering ). Her er datasettet vanligvis modellert med et fast (for å unngå overmontering) antall Gauss -fordelinger som initialiseres tilfeldig og hvis parametere er iterativt optimalisert for å passe bedre til datasettet. Dette vil konvergere til et lokalt optimalt , så flere kjøringer kan gi forskjellige resultater. For å oppnå en hard gruppering blir objektene ofte tilordnet den gaussiske fordelingen de mest sannsynlig tilhører; for myke klynger er dette ikke nødvendig.

Distribusjonsbasert klynge produserer komplekse modeller for klynger som kan fange sammenheng og avhengighet mellom attributter. Imidlertid legger disse algoritmene en ekstra belastning på brukeren: for mange virkelige datasett kan det være at det ikke er noen kortfattet matematisk modell (f.eks. Forutsatt at Gauss -fordelinger er en ganske sterk antagelse om dataene).

• Eksempler på klynging av Gauss -blandinger
• 

  På Gauss-distribuerte data fungerer EM bra, siden den bruker gaussere til modelleringsklynger

• 

  Tetthetsbaserte klynger kan ikke modelleres ved hjelp av gaussiske fordelinger

Tetthetsbasert gruppering

I tetthetsbasert klynge er klynger definert som områder med høyere tetthet enn resten av datasettet. Objekter i sparsomme områder - som kreves for å skille klynger - regnes vanligvis som støy og grensepunkter.

Den mest populære tetthetsbaserte gruppemetoden er DBSCAN . I motsetning til mange nyere metoder har den en veldefinert klyngemodell som kalles "tetthetstilgjengelighet". I likhet med koblingsbasert klynge, er den basert på tilkoblingspunkter innenfor visse avstandsterskler. Den forbinder imidlertid bare punkter som tilfredsstiller et tetthetskriterium, i den opprinnelige varianten definert som et minimum antall andre objekter innenfor denne radius. En klynge består av alle tetthetstilkoblede objekter (som kan danne en klynge med en vilkårlig form, i motsetning til mange andre metoder) pluss alle objekter som er innenfor disse objektene. En annen interessant egenskap ved DBSCAN er at kompleksiteten er ganske lav - det krever et lineært antall rekkeforespørsler på databasen - og at den vil oppdage i hovedsak de samme resultatene (den er deterministisk for kjerne- og støypunkter, men ikke for grensepunkter) i hvert løp, derfor er det ikke nødvendig å kjøre det flere ganger. OPTICS er en generalisering av DBSCAN som fjerner behovet for å velge en passende verdi for områdeparameteren , og produserer et hierarkisk resultat relatert til det for koblingsklynger . DeLi-Clu, Density-Link-Clustering kombinerer ideer fra single-linkage clustering og OPTICS, eliminerer parameteren helt og tilbyr ytelsesforbedringer i forhold til OPTICS ved å bruke en R-tree index. ${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$

Den viktigste ulempen med DBSCAN og OPTICS er at de forventer at en slags tetthetsfall vil oppdage klyngegrenser. På datasett med for eksempel overlappende Gauss -distribusjoner - et vanlig brukstilfelle i kunstige data - vil klyngegrensene som produseres av disse algoritmene ofte se vilkårlige ut, fordi klyngetettheten synker kontinuerlig. På et datasett som består av blandinger av gaussere, er disse algoritmene nesten alltid bedre enn metoder som EM -klynger som er i stand til å modellere denne typen data nøyaktig.

Mean-shift er en grupperingstilnærming der hvert objekt flyttes til det tetteste området i nærheten, basert på estimering av kjernetetthet . Etter hvert konvergerer objekter til lokal tetthet. I likhet med k-betyr clustering, kan disse "tetthetsattraktorene" tjene som representanter for datasettet, men middel-shift kan oppdage vilkårlige formede klynger som ligner på DBSCAN. På grunn av den dyre iterative prosedyren og tetthetsestimering, er middelforskyvning vanligvis tregere enn DBSCAN eller k-Means. Dessuten hindres anvendeligheten av middelskiftalgoritmen på flerdimensjonale data av den ujevne oppførselen til estimatet for kjernetetthet, noe som resulterer i overfragmentering av klynghaler.

• Tetthetsbaserte klyngeeksempler
• 

  Tetthetsbasert gruppering med DBSCAN .

• 

  DBSCAN antar klynger med lignende tetthet, og kan ha problemer med å skille nærliggende klynger

• 

  OPTICS er en DBSCAN -variant som forbedrer håndteringen av forskjellige tetthetsgrupper

Rutenettbasert gruppering

Den rutenettbaserte teknikken brukes for et flerdimensjonalt datasett. I denne teknikken lager vi en rutenettstruktur, og sammenligningen utføres på rutenett (også kjent som celler). Den nettbaserte teknikken er rask og har lav beregningskompleksitet. Det er to typer rutenettbaserte gruppemetoder: STING og CLIQUE. Trinn som inngår i nett-baserte clustering algoritme er:

1. Del datarommet i et begrenset antall celler.
2. Velg tilfeldig en celle 'c', der c ikke skal krysses på forhånd.
3. Beregn tettheten til 'c'
4. Hvis tettheten på 'c' er større enn terskeltettheten
   1. Merk celle 'c' som en ny klynge
   2. Beregn tettheten til alle naboene til 'c'
   3. Hvis tettheten til en nabocelle er større enn terskeltettheten, legger du til cellen i klyngen og gjentar trinn 4.2 og 4.3 til det ikke er noen nabo med en tetthet som er større enn terskeltettheten.
5. Gjenta trinn 2,3 og 4 til alle cellene er krysset.
6. Stoppe.

Nylige utviklinger

De siste årene har det blitt lagt mye arbeid på å forbedre ytelsen til eksisterende algoritmer. Blant dem er CLARANS og BIRCH . Med det siste behovet for å behandle større og større datasett (også kjent som store data ), har viljen til å handle semantisk betydning av de genererte klyngene for ytelse vært økende. Dette førte til utviklingen av forhåndsklyngemetoder som baldakineklynger , som effektivt kan behandle enorme datasett, men de resulterende "klyngene" er bare en grov forhåndspartisjonering av datasettet for deretter å analysere partisjonene med eksisterende langsommere metoder som som k-betyr gruppering .

For høydimensjonale data mislykkes mange av de eksisterende metodene på grunn av dimensjonalitetens forbannelse , noe som gjør bestemte avstandsfunksjoner problematiske i høydimensjonale rom. Dette førte til nye klynge-algoritmer for høydimensjonale data som fokuserer på klynger i mellomrom (der bare noen attributter brukes, og klyngemodeller inkluderer de relevante attributtene for klyngen) og korrelasjonsklynger som også ser etter vilkårlig rotert ("korrelert") underrom klynger som kan modelleres ved å gi en sammenheng mellom attributtene deres. Eksempler på slike grupperingsalgoritmer er CLIQUE og SUBCLU .

Ideer fra tetthetsbaserte klyngemetoder (spesielt DBSCAN / OPTICS- algoritmefamilien) har blitt tilpasset underromsgruppering (HiSC, hierarkisk delromsklynger og DiSH) og korrelasjonsklynger (HiCO, hierarkisk korrelasjonsklynger, 4C ved bruk av "korrelasjonstilkobling" og ERiC som utforsker hierarkiske tetthetsbaserte korrelasjonsklynger).

Flere forskjellige klyngesystemer basert på gjensidig informasjon er blitt foreslått. Den ene er Marina Meilăs variasjon av informasjonsmåling ; en annen gir hierarkisk klynge. Ved å bruke genetiske algoritmer kan et bredt spekter av forskjellige tilpasningsfunksjoner optimaliseres, inkludert gjensidig informasjon. Også trosformidling , en nylig utvikling innen informatikk og statistisk fysikk , har ført til opprettelsen av nye typer klynge -algoritmer.

Evaluering og vurdering

Evaluering (eller "validering") av klyngeresultater er like vanskelig som selve klyngingen. Populære tilnærminger innebærer " intern " evaluering, der gruppering er oppsummert til en enkelt kvalitetspoeng, " ekstern " evaluering, der gruppering blir sammenlignet med en eksisterende "grunn sannhet" klassifisering, " manuell " evaluering av en menneskelig ekspert og " indirekte " "evaluering ved å evaluere bruken av klyngen i den tiltenkte applikasjonen.

Interne evalueringstiltak lider av problemet at de representerer funksjoner som de selv kan se på som et klyngemål. For eksempel kan man samle datasettet av Silhouette -koeffisienten; bortsett fra at det ikke er kjent effektiv algoritme for dette. Ved å bruke et slikt internt mål for evaluering, sammenligner man heller likheten mellom optimaliseringsproblemene, og ikke nødvendigvis hvor nyttig klyngingen er.

Ekstern evaluering har lignende problemer: Hvis vi har slike "ground truth" -etiketter, trenger vi ikke å samles; og i praktiske applikasjoner har vi vanligvis ikke slike etiketter. På den annen side gjenspeiler etikettene bare en mulig partisjonering av datasettet, noe som ikke betyr at det ikke eksisterer en annen, og kanskje enda bedre, gruppering.

Ingen av disse tilnærmingene kan derfor til syvende og sist dømme den faktiske kvaliteten på en gruppering, men dette trenger menneskelig evaluering, som er svært subjektiv. Likevel kan slik statistikk være ganske informativ for å identifisere dårlige klynger, men man bør ikke avvise subjektiv menneskelig vurdering.

Intern evaluering

Når et klyngeresultat evalueres basert på dataene som ble gruppert i seg selv, kalles dette intern evaluering. Disse metodene tildeler vanligvis den beste poengsummen til algoritmen som produserer klynger med høy likhet i en klynge og lav likhet mellom klynger. En ulempe ved å bruke interne kriterier i klyngeevaluering er at høy score på et internt mål ikke nødvendigvis resulterer i effektive informasjonshentingsprogrammer. I tillegg er denne evalueringen partisk mot algoritmer som bruker samme klyngemodell. For eksempel optimaliserer k-clustering naturligvis objektavstander, og et avstandsbasert internt kriterium vil sannsynligvis overvurdere den resulterende gruppering.

Derfor er de interne evalueringstiltakene best egnet for å få litt innsikt i situasjoner der en algoritme fungerer bedre enn en annen, men dette skal ikke innebære at en algoritme gir mer gyldige resultater enn en annen. Gyldighet målt ved en slik indeks avhenger av påstanden om at denne typen struktur eksisterer i datasettet. En algoritme designet for noen slags modeller har ingen sjanse hvis datasettet inneholder et radikalt annet sett med modeller, eller hvis evalueringen måler et radikalt annet kriterium. For eksempel kan k-betyr gruppering bare finne konvekse klynger, og mange evalueringsindekser antar konvekse klynger. På et datasett med ikke -konvekse klynger er verken bruk av k -midler eller et evalueringskriterium som forutsetter konveksitet, forsvarlig.

Mer enn et dusin interne evalueringstiltak eksisterer, vanligvis basert på intuisjonen om at elementer i samme klynge skal være mer like enn elementer i forskjellige klynger. For eksempel kan følgende metoder brukes til å vurdere kvaliteten på gruppering algoritmer basert på interne kriterier:

• Davies - Bouldin indeks

Den Davies-Bouldin indeksen kan beregnes ved hjelp av følgende formel:

${\ displaystyle DB = {\ frac {1} {n}} \ sum _ {i = 1}^{n} \ max _ {j \ neq i} \ left ({\ frac {\ sigma _ {i}+ \ sigma _ {j}} {d (c_ {i}, c_ {j})}} \ høyre)}$

hvor n er antall klynger, er sentroid av klynge , er gjennomsnittlig avstand mellom alle elementer i klynge til sentroid , og er avstanden mellom sentroider og . Siden algoritmer som produserer klynger med lave intra-cluster-avstander (høy intra-cluster-likhet) og høye inter-cluster-distanser (lav inter-cluster-likhet) vil ha en lav Davies-Bouldin-indeks, vil clustering-algoritmen som produserer en samling klynger med den minste Davies - Bouldin -indeksen regnes som den beste algoritmen basert på dette kriteriet.${\ displaystyle c_ {i}}$${\ displaystyle i}$${\ displaystyle \ sigma _ {i}}$${\ displaystyle i}$${\ displaystyle c_ {i}}$${\ displaystyle d (c_ {i}, c_ {j})}$${\ displaystyle c_ {i}}$${\ displaystyle c_ {j}}$

• Dunn indeks

Dunn-indeksen tar sikte på å identifisere tette og godt atskilte klynger. Det er definert som forholdet mellom den minimale avstanden mellom klyngene og den maksimale avstanden mellom klyngene. For hver klyngepartisjon kan Dunn -indeksen beregnes med følgende formel:

${\ displaystyle D = {\ frac {\ min _ {1 \ leq i <j \ leq n} d (i, j)} {\ max _ {1 \ leq k \ leq n} d^{\ prime} ( k)}} \ ,,}$

hvor d ( i , j ) representerer avstanden mellom klynger i og j , og d '( k ) måler avstanden mellom klyngen k . Mellomklyngeavstanden d ( i , j ) mellom to klynger kan være et hvilket som helst antall avstandsmål, for eksempel avstanden mellom sentroidene til klyngene. På samme måte kan avstanden mellom klyngene d '( k ) måles på forskjellige måter, for eksempel maksimal avstand mellom et hvilket som helst par av elementer i klynge  k . Siden interne kriterier søker etter klynger med høy likhet mellom klynger og lav likhet mellom klynger, er algoritmer som produserer klynger med høy Dunn-indeks mer ønskelig.

• Silhuettkoeffisient

Silhuettkoeffisienten kontrasterer gjennomsnittlig avstand til elementer i samme klynge med gjennomsnittlig avstand til elementer i andre klynger. Objekter med høy silhuettverdi regnes som godt gruppert, objekter med lav verdi kan være ekstreme. Denne indeksen fungerer godt med k -midler clustering, og brukes også til å bestemme det optimale antallet klynger.

Ekstern evaluering

I ekstern evaluering evalueres klyngeresultater basert på data som ikke ble brukt til gruppering, for eksempel kjente klassetiketter og eksterne benchmarks. Slike referanser består av et sett med forhåndsklassifiserte gjenstander, og disse settene er ofte laget av (ekspert) mennesker. Dermed kan referansesettene betraktes som en gullstandard for evaluering. Denne typen evalueringsmetoder måler hvor nær klyngen er på forhåndsbestemte referanseklasser. Imidlertid har det nylig blitt diskutert om dette er tilstrekkelig for reelle data, eller bare på syntetiske datasett med en faktisk grunnleggende sannhet, siden klasser kan inneholde intern struktur, kan attributtene som er tilstede ikke tillate separasjon av klynger eller klassene kan inneholde avvik . I tillegg, fra et kunnskapsoppdagelses synspunkt, er reproduksjon av kjent kunnskap ikke nødvendigvis det tiltenkte resultatet. I det spesielle scenariet med begrenset klynging , der metainformasjon (for eksempel klassetiketter) brukes allerede i klyngeprosessen, er oppbevaring av informasjon for evalueringsformål ikke-trivial.

En rekke tiltak er tilpasset fra varianter som brukes til å evaluere klassifiseringsoppgaver. I stedet for å telle antall ganger en klasse ble riktig tilordnet et enkelt datapunkt (kjent som sanne positiver ), vurderer slike par -tellende beregninger om hvert par datapunkter som virkelig er i samme klynge er spådd å være i samme klynge.

Som med intern evaluering finnes det flere eksterne evalueringstiltak, for eksempel:

• Renhet : Renhet er et mål på i hvilken grad klynger inneholder en enkelt klasse. Beregningen kan tenkes på følgende måte: For hver klynge teller du antall datapunkter fra den vanligste klassen i klyngen. Ta nå summen over alle klynger og divider med det totale antallet datapunkter. Formelt, gitt et sett med klynger og noen sett med klasser , begge partisjoneringsdatapunkter , kan renhet defineres som:${\ displaystyle M}$${\ displaystyle D}$${\ displaystyle N}$

${\ displaystyle {\ frac {1} {N}} \ sum _ {m \ in M} \ max _ {d \ in D} {| m \ cap d |}}$

Dette tiltaket straffes ikke med å ha mange klynger, og flere klynger vil gjøre det lettere å produsere høy renhet. En renhetsscore på 1 er alltid mulig ved å sette hvert datapunkt i sin egen klynge. Renhet fungerer heller ikke bra for ubalanserte data, der selv dårlig utførte klyngealgoritmer vil gi en høy renhetsverdi. For eksempel, hvis et datasett i størrelse 1000 består av to klasser, en som inneholder 999 poeng og den andre inneholder 1 punkt, vil hver mulig partisjon ha en renhet på minst 99,9%.

• Rand indeks

Rand -indeksen beregner hvor like klyngene (returnert av klynge -algoritmen) er referanseklassifiseringene. Det kan beregnes ved hjelp av følgende formel:

${\ displaystyle RI = {\ frac {TP+TN} {TP+FP+FN+TN}}}$

hvor er antallet sanne positive, er antallet sanne negative , er antallet falske positiver , og er antallet falske negativer . Forekomstene som telles her er antall riktige parvise tildelinger. Det vil si at antall par punkter som er gruppert sammen i den forutsagte partisjonen og i bakken sannhetspartisjonen, er antall par av punkter som er gruppert sammen i den forutsagte partisjonen, men ikke i den jordede sannhetspartisjonen etc. Hvis datasettet er av størrelse N, da .${\ displaystyle TP}$${\ displaystyle TN}$${\ displaystyle FP}$${\ displaystyle FN}$${\ displaystyle TP}$${\ displaystyle FP}$${\ displaystyle TP+TN+FP+FN = {\ binom {N} {2}}}$

Et problem med Rand -indeksen er at falske positive og falske negativer er like vektet. Dette kan være en uønsket egenskap for noen klynge -applikasjoner. F-målet adresserer denne bekymringen, det samme gjør den sjansekorrigerte justerte Rand-indeksen .

• F-mål

F-målet kan brukes til å balansere bidraget fra falske negativer ved å veie tilbakekalling gjennom en parameter . La presisjon og tilbakekalling (begge eksterne evalueringstiltak i seg selv) defineres som følger: ${\ displaystyle \ beta \ geq 0}$

${\ displaystyle P = {\ frac {TP} {TP+FP}}}$

${\ displaystyle R = {\ frac {TP} {TP+FN}}}$

hvor er presisjonshastigheten og er tilbakekallingshastigheten . Vi kan beregne F-målet ved å bruke følgende formel: ${\ displaystyle P}$${\ displaystyle R}$

${\ displaystyle F _ {\ beta} = {\ frac {(\ beta ^{2} +1) \ cdot P \ cdot R} {\ beta ^{2} \ cdot P+R}}}$

Når , . Med andre ord, tilbakekalling har ingen innvirkning på F-målet når , og økende tildeler en økende mengde vekt til tilbakekalling i det endelige F-målet.${\ displaystyle \ beta = 0}$${\ displaystyle F_ {0} = P}$${\ displaystyle \ beta = 0}$${\ displaystyle \ beta}$

Det blir heller ikke tatt i betraktning og kan variere fra 0 oppover uten begrensning.${\ displaystyle TN}$

• Jaccard -indeks

Jaccard -indeksen brukes til å kvantifisere likheten mellom to datasett. Den Jaccard-indeksen tar på en verdi mellom 0 og 1. En indeks på 1 betyr at de to datasett er identiske, og en indeks på 0 angir at datasettene ikke har noen felles elementer. Jaccard -indeksen er definert av følgende formel:

${\ displaystyle J (A, B) = {\ frac {| A \ cap B |} {| A \ cup B |}} = {\ frac {TP} {TP+FP+FN}}}$

Dette er ganske enkelt antall unike elementer som er felles for begge settene delt på det totale antallet unike elementer i begge settene.

Det blir heller ikke tatt i betraktning og kan variere fra 0 oppover uten begrensning.${\ displaystyle TN}$

• Terningindeks

Terningens symmetriske mål dobler vekten mens den fortsatt ignoreres : ${\ displaystyle TP}$${\ displaystyle TN}$

${\ displaystyle DSC = {\ frac {2TP} {2TP+FP+FN}}}$

• Fowlkes – Mallows indeks

Fowlkes – Mallows -indeksen beregner likheten mellom klyngene som returneres av klyngealgoritmen og referanseklassifiseringene. Jo høyere verdien av Fowlkes - Mallows -indeksen, jo mer like er klyngene og referanseklassifiseringene. Den kan beregnes ved hjelp av følgende formel:

${\ displaystyle FM = {\ sqrt {{\ frac {TP} {TP+FP}} \ cdot {\ frac {TP} {TP+FN}}}}}}$

hvor er antallet sanne positiver , er antallet falske positiver , og er antallet falske negativer . Den indeks er den geometriske middelverdi av den presisjon og tilbakekalling og , og er således også kjent som G-mål, mens F-tiltaket er deres harmoniske middelverdien. Videre er presisjon og tilbakekalling også kjent som Wallaces indekser og . Chance normaliserte versjoner av tilbakekalling, presisjon og G-mål tilsvarer Informedness , Markedness og Matthews Correlation og forholder seg sterkt til Kappa .${\ displaystyle TP}$${\ displaystyle FP}$${\ displaystyle FN}$${\ displaystyle FM}$ ${\ displaystyle P}$${\ displaystyle R}$${\ displaystyle B^{I}}$${\ displaystyle B^{II}}$

• Den gjensidige informasjonen er et informasjonsteoretisk mål på hvor mye informasjon som deles mellom en gruppering og en grunn-sannhetsklassifisering som kan oppdage en ikke-lineær likhet mellom to klynger. Normalisert gjensidig informasjon er en familie av korrigerte-for-sjanse-varianter av dette som har redusert skjevhet for varierende klyngetall.
• Forvirringsmatrise

En forvirringsmatrise kan brukes til raskt å visualisere resultatene av en klassifiserings (eller klynge) algoritme. Den viser hvor forskjellig en klynge er fra gullstandardklyngen.

Klyngetendens

Å måle klyngetendens er å måle i hvilken grad klynger finnes i dataene som skal klynges, og kan utføres som en innledende test, før du prøver å klynge. En måte å gjøre dette på er å sammenligne dataene med tilfeldige data. I gjennomsnitt bør tilfeldige data ikke ha klynger.

• Hopkins statistikk

Det er flere formuleringer av Hopkins -statistikken . En typisk er som følger. La være settet med datapunkter i dimensjonalt rom. Vurder et tilfeldig utvalg (uten erstatning) av datapunkter med medlemmer . Generer også et sett med jevnt tilfeldig distribuerte datapunkter. Definer nå to avstandsmål, å være avstanden til fra nærmeste nabo i X og å være avstanden til fra nærmeste nabo i X. Vi definerer deretter Hopkins -statistikken som: ${\ displaystyle X}$${\ displaystyle n}$${\ displaystyle d}$${\ displaystyle m \ ll n}$${\ displaystyle x_ {i}}$${\ displaystyle Y}$${\ displaystyle m}$${\ displaystyle u_ {i}}$${\ displaystyle y_ {i} \ i Y}$${\ displaystyle w_ {i}}$${\ displaystyle x_ {i} \ i X}$

${\ 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 bør ensartede tilfeldige data ha en tendens til å ha verdier nær 0,5, og gruppert data bør ha en tendens til å ha verdier nærmere 1.

Imidlertid vil data som inneholder bare en enkelt Gauss også score nær 1, ettersom denne statistikken måler avvik fra en ensartet fordeling, ikke multimodalitet , noe som gjør denne statistikken stort sett ubrukelig i bruk (ettersom ekte data aldri er eksternt enhetlig).

applikasjoner

Biologi, beregningsbiologi og bioinformatikk

Plante og dyr økologi

Klyngeanalyse brukes til å beskrive og gjøre romlige og tidsmessige sammenligninger av lokalsamfunn (samlinger) av organismer i heterogene miljøer. Det brukes også i plantesystematikk for å generere kunstige fylogenier eller klynger av organismer (individer) på arten, slekten eller høyere nivå som deler en rekke attributter.

Transkriptomikk

Clustering brukes til å bygge grupper av gener med beslektede ekspresjonsmønstre (også kjent som coexpressed gener) som i HCS clustering algoritme . Ofte inneholder slike grupper funksjonelt beslektede proteiner, for eksempel enzymer for en bestemt vei , eller gener som er ko-regulert. Eksperimenter med høy gjennomstrømning ved bruk av uttrykte sekvensmerker (EST -er) eller DNA -mikroarrayer kan være et kraftig verktøy for genomkommentarer - et generelt aspekt ved genomikk .

Sekvensanalyse

Sekvensgruppering brukes til å gruppere homologe sekvenser i genfamilier . Dette er et veldig viktig konsept innen bioinformatikk , og evolusjonær biologi generelt. Se evolusjon ved genduplisering .

Plattformer for genotyping med høy gjennomstrømning

Klyngealgoritmer brukes til å automatisk tildele genotyper.

Menneskelig genetisk klynging

Likheten mellom genetiske data brukes i gruppering for å utlede populasjonsstrukturer.

Medisin

Medisinsk bildebehandling

På PET-skanninger kan klyngeanalyse brukes til å skille mellom forskjellige typer vev i et tredimensjonalt bilde for mange forskjellige formål.

Analyse av antimikrobiell aktivitet

Klyngeanalyse kan brukes til å analysere mønstre av antibiotikaresistens, for å klassifisere antimikrobielle forbindelser i henhold til deres virkningsmekanisme, for å klassifisere antibiotika i henhold til deres antibakterielle aktivitet.

IMRT -segmentering

Clustering kan brukes til å dele et flytekart i forskjellige regioner for konvertering til leverbare felt i MLC-basert strålebehandling.

Forretning og markedsføring

Markedsundersøkelser

Klyngeanalyse er mye brukt i markedsundersøkelser når man arbeider med multivariate data fra undersøkelser og testpaneler. Markedsforskere bruker klyngeanalyse for å dele den generelle befolkningen av forbrukere i markedssegmenter og for bedre å forstå forholdet mellom forskjellige grupper av forbrukere/potensielle kunder , og for bruk i markedssegmentering , produktposisjonering , utvikling av nye produkter og valg av testmarkeder.

Gruppering av shoppingvarer

Clustering kan brukes til å gruppere alle shoppingvarene som er tilgjengelige på nettet i et sett med unike produkter. For eksempel kan alle elementene på eBay grupperes i unike produkter (eBay har ikke begrepet SKU ).

Verdensveven

Sosialt nettverksanalyse

I studiet av sosiale nettverk kan gruppering brukes til å gjenkjenne lokalsamfunn innenfor store grupper mennesker.

Søkeresultatgruppering

I prosessen med intelligent gruppering av filer og nettsteder kan gruppering brukes til å lage et mer relevant sett med søkeresultater sammenlignet med vanlige søkemotorer som Google . Det er for tiden en rekke nettbaserte klyngeverktøy som Clusty . Den kan også brukes til å returnere et mer omfattende sett med resultater i tilfeller der et søkeord kan referere til vidt forskjellige ting. Hver distinkte bruk av begrepet tilsvarer en unik klynge av resultater, slik at en rangeringsalgoritme kan returnere omfattende resultater ved å velge toppresultatet fra hver klynge.

Slippy kartoptimalisering

Flickrs kart over bilder og andre kartsider bruker gruppering for å redusere antall markører på et kart. Dette gjør det både raskere og reduserer mengden visuelt rot.

Informatikk

Programvareutvikling

Clustering er nyttig i programvareutvikling, da det bidrar til å redusere eldre egenskaper i kode ved å reformere funksjonalitet som har blitt spredt. Det er en form for restrukturering og er derfor en måte for direkte forebyggende vedlikehold.

Bildesegmentering

Clustering kan brukes til å dele et digitalt bilde i forskjellige regioner for grenseregistrering eller gjenkjenning av objekter .

Evolusjonære algoritmer

Klynger kan brukes til å identifisere forskjellige nisjer i populasjonen av en evolusjonær algoritme, slik at reproduksjonsmulighet kan fordeles jevnere mellom de utviklende artene eller underartene.

Anbefalersystemer

Anbefalersystemer er designet for å anbefale nye varer basert på en brukers smak. Noen ganger bruker de grupperingsalgoritmer for å forutsi brukerens preferanser basert på preferansene til andre brukere i brukerens klynge.

Markov -kjeden Monte Carlo -metoder

Clustering brukes ofte til å lokalisere og karakterisere ekstrema i målfordelingen.

Anomali deteksjon

Anomalier/outliers er vanligvis - det være seg eksplisitt eller implisitt - definert med hensyn til klyngestruktur i data.

Naturlig språkbehandling

Clustering kan brukes til å løse leksikalsk tvetydighet .

Samfunnsvitenskap

Sekvensanalyse i samfunnsvitenskap

Klyngeanalyse brukes til å identifisere mønstre for familielivsbaner, profesjonelle karrierer og daglig eller ukentlig tidsbruk for eksempel.

Kriminalitetsanalyse

Klyngeanalyse kan brukes til å identifisere områder der det er større tilfeller av bestemte typer kriminalitet. Ved å identifisere disse forskjellige områdene eller "hot spots" der en lignende forbrytelse har skjedd over en periode, er det mulig å håndtere rettshåndhevelsesressurser mer effektivt.

Utdanningsdatamining

Klyngeanalyse brukes for eksempel til å identifisere grupper av skoler eller elever med lignende egenskaper.

Typologier

Fra undersøkelsesdata bruker prosjekter som de som er utført av Pew Research Center klyngeanalyse for å skille typologier av meninger, vaner og demografi som kan være nyttige i politikk og markedsføring.

Andre

Feltrobotikk

Klyngealgoritmer brukes til robotisk situasjonsbevissthet for å spore objekter og oppdage ekstremheter i sensordata.

Matematisk kjemi

For å finne strukturell likhet, etc., ble for eksempel 3000 kjemiske forbindelser gruppert i løpet av 90 topologiske indekser .

Klimatologi

For å finne værregimer eller foretrukne havnivåstrykk atmosfæriske mønstre.

Finansiere

Klyngeanalyse har blitt brukt til å gruppere aksjer i sektorer.

Petroleumsgeologi

Klyngeanalyse brukes til å rekonstruere manglende kjernedata i bunnhullet eller manglende loggkurver for å evaluere reservoaregenskaper.

Geokjemi

Klyngingen av kjemiske egenskaper på forskjellige prøvesteder.

Se også

Spesialiserte typer klyngeanalyser

• Automatiske gruppering algoritmer
• Balansert gruppering
• Klynging av høydimensjonale data
• Konseptuell klynger
• Konsensusklynger
• Begrenset gruppering
• Fellesskapsdeteksjon
• Klynging av datastrøm
• HCS -klynger
• Sekvensgruppering
• Spektral klynger

Teknikker som brukes i klyngeanalyse

• Kunstig nevrale nettverk (ANN)
• Nærmeste nabosøk
• Nabolagskomponentanalyse
• Latent klasseanalyse
• Affinitetsspredning

Dataprojeksjon og forbehandling

• Dimensjonsreduksjon
• Hovedkomponentanalyse
• Flerdimensjonal skalering

Annen

• Klyngevektet modellering
• Forbannelse over dimensjonalitet
• Bestemme antall klynger i et datasett
• Parallelle koordinater
• Strukturert dataanalyse

Referanser