Oversikt over Hierarkisk Clustering Analyse

La oss prøve å forstå hva som er en klynge før vi går foran og forstår om hierarkisk klyngeanalyse. Og hva er klyngeanalyse? En klynge er en samling dataobjekter; datapunktene i en klynge er mer like hverandre og ulik datapunktene i den andre klyngen. Klyngeanalyse er i utgangspunktet en gruppering av disse datapunktene i klyngen. Clustering er en type uovervåket maskinlæringsalgoritme, der det ikke er noen treningsmerkede datasett. Det er forskjellige typer klyngebaseanalyser, en slik type er hierarkisk klynging.

Hierarkisk klynging vil hjelpe til med å lage klynger i riktig orden / hierarki. Eksempel: det vanligste hverdagseksemplet vi ser er hvordan vi bestiller filer og mapper på datamaskinen vår etter riktig hierarki.

Typer hierarkisk klynging

Hierarkisk klynging klassifiseres videre i to typer, dvs. Agglomerativ klynging og Divisive Clustering (DIANA)

Agglomerativ gruppering

I dette tilfellet med klynging gjøres den hierarkiske nedbrytningen ved hjelp av bottom-up-strategi der den starter med å lage atomiske (små) klynger ved å legge til ett dataobjekt om gangen og deretter slå dem sammen for å danne en stor klynge på slutten, hvor denne klyngen oppfyller alle avslutningsbetingelsene. Denne prosedyren er iterativ til alle datapunktene blir brakt under en eneste stor klynge.

AGNES (AGglomerative NESting) er en type agglomerativ gruppering som kombinerer dataobjektene til en klynge basert på likhet. Resultatet av denne algoritmen er en trebasert strukturert kalt Dendrogram. Her bruker den avstandsmålingene til å bestemme hvilke datapunkter som skal kombineres med hvilken klynge. I utgangspunktet konstruerer den en avstandsmatrise og ser etter par klynger med den minste avstanden og kombinerer dem.

Figuren over viser Agglomerative vs. Divisive clustering

Basert på hvordan avstanden mellom hver klynge måles kan vi ha 3 forskjellige metoder

  • Enkel kobling : Hvor den korteste avstanden mellom de to punktene i hver klynge er definert som avstanden mellom klyngene.
  • Fullstendig kobling : I dette tilfellet vil vi betrakte den lengste avstanden mellom punktene i hver klynge som avstanden mellom klyngene.
  • Gjennomsnittlig kobling: Her vil vi ta gjennomsnittet mellom hvert punkt i en klynge til hvert annet punkt i den andre klyngen.

La oss nå diskutere om styrkene og svakheten i AGNES; denne algoritmen har en tidskompleksitet på minst O (n 2 ), og det gjør det derfor ikke bra med skalering, og en annen stor ulempe er at det som har blitt gjort aldri kan gjøres ugjort, dvs. hvis vi feil grupperer en klynge i tidligere fase av algoritmen, så vil vi ikke kunne endre utfallet / endre det. Men denne algoritmen har en lys side siden det er mange mindre klynger som dannes, det kan være nyttig i oppdagelsesprosessen, og den produserer en bestilling av objekter som er veldig nyttige i visualisering.

Divisive Clustering (DIANA)

Diana står i utgangspunktet for Divisive Analysis; dette er en annen type hierarkisk klynge der det i utgangspunktet fungerer etter prinsippet om ovenfra og ned tilnærming (invers av AGNES) der algoritmen begynner med å danne en stor klynge og den rekursivt deler den mest forskjellige klyngen i to og den fortsetter til vi ' alle de samme datapunktene hører hjemme i deres respektive klynger. Disse splittende algoritmene resulterer i svært nøyaktige hierarkier enn den agglomerative tilnærmingen, men de er beregningsdyktige.

Figuren over viser Delende klynging trinnvis prosess

Flerfase hierarkisk klynge

For å forbedre kvaliteten på klynger generert av ovennevnte hierarkiske klyngeteknikker, integrerer vi våre hierarkiske klyngeteknikker med andre klyngeteknikker; dette kalles flerfaseklynging. De forskjellige typene flerfaseklynger er som følger:

  • BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)
  • ROCK (RObust Clustering ved hjelp av lenker)
  • CHAMELEON

1. Balansert Iterativ Reduksjon og Clustering ved hjelp av hierarkier

Denne metoden brukes hovedsakelig for klynging av enorme mengder numeriske data ved å integrere vår hierarkiske / mikroklynger i den innledende fasen og makroklynger / iterativ partisjonering i den senere fasen. Denne metoden hjelper med å overvinne skalerbarhetsproblemet vi sto overfor i AGNES og manglende evne til å angre det som ble gjort i før trinn. BIRCH bruker to viktige konsepter i algoritmen

en. Klyngefunksjon (Hjelper med å oppsummere klyngen)

CF er definert som (n- antall datapunkter i klyngen, den lineære summen av n poeng, den firkantede summen av n poeng). Lagring av funksjonen til en klynge på denne måten hjelper deg med å unngå å lagre detaljert informasjon om den, og CF er additiv i naturen for forskjellige klynger.

CF 1 + CF 2 = 1+ n 2, LS 1 + LS 2, SS 1 + SS 2 >

b. Clustering-funksjonstreet (hjelper til med å representere en klynge som et hierarki)

CF-tre er et balansert tre med forgreningsfaktor B (maksimalt antall barn) og terskel T (maks antall underklynger som kan lagres i bladnoder).

Algoritmen fungerer i utgangspunktet i 2 faser; i fase 1 skanner den databasen og bygger et CF-tre i minnet, og i fase 2 bruker den klynge-algoritmen som hjelper til med å gruppere bladnodene ved å fjerne utliggerne (sparsomme klynger) og grupperer klyngen med maksimal tetthet. Den eneste ulempen med denne algoritmen er at den bare håndterer den numeriske datatypen.

2. Robust gruppering ved hjelp av lenker

Kobling er definert som antall vanlige naboer mellom to objekter. ROCK-algoritme er en type klynge-algoritme som bruker dette konseptet med kobling med det kategoriske datasettet. Som vi vet at avstandsmålte klyngebaserte algoritmer ikke gir høykvalitetsklynger for det kategoriske datasettet, men i tilfelle av ROCK, vurderer det også nabolagene til datapunktene, dvs. hvis to datapunkter har det samme nabolaget så er de mest sannsynlig å høre til i samme klynge. Algoritmen vil konstruere en sparsom graf i det første trinnet under hensyntagen til likhetsmatrisen med begrepet nabolag og likhetsterskelen. I det andre trinnet bruker den den agglomerative hierarkiske klyngeteknikken på den sparsomme grafen.

3. Kameleon

Denne typen hierarkiske klyngebaserte algoritmer bruker begrepet dynamisk modellering. Lurer du på hvorfor kalles det dynamisk? Det kalles dynamisk fordi det har muligheten til å tilpasse seg de interne klyngekarakteristikkene automatisk ved å evaluere klyngens likhet, dvs. hvor godt koblet datapunktene i en klynge og i nærheten av klyngene. En av ulempene med kameleon er at prosesseringskostnadene er for høye (O (n 2 ) for n-objekter er tidskompleksiteten i verste fall).

Bildekilde - Google

Konklusjon

I denne artikkelen har vi lært hva en klynge er og hva er klyngeanalyse, forskjellige typer hierarkiske klyngeteknikker fordeler og ulemper. Hver av teknikkene vi diskuterte har sitt eget pluss og minus, og før vi går videre med en algoritme, må vi forstå våre data med riktig utforskende dataanalyse og velge algoritmen med forsiktighet.

Anbefalte artikler

Dette er en guide til Hierarkisk Clustering Analyse. Her diskuterer vi oversikten, agglomerativ clustering, divisive Clustering (DIANA) og flerfase hierarkisk clustering. Du kan også se på følgende artikler for å lære mer

  1. Hierarkisk klynge i R
  2. Clustering algoritme
  3. klynger
  4. Clustering Methods
  5. Clustering in Machine Learning
  6. Hierarkisk klynging | Agglomerative & Divisive Clustering

Kategori:

Stor Data