Oversigt over hierarkisk klynge-analyse

Før vi går videre og forstår om hierarkisk klynge-analyse, lad os først prøve at forstå, hvad der er en klynge? Og hvad er klyngeanalyse? En klynge er en samling af dataobjekter; datapunkterne i en klynge ligner hinanden mere og er forskellige med datapunkterne i den anden klynge. Klyngeanalyse er dybest set en gruppering af disse datapunkter i klyngen. Clustering er en type uovervåget maskinlæringsalgoritme, hvor der ikke er nogen træningsmærkede datasæt. Der er forskellige typer klynge-analyse, en sådan type er hierarkisk klynge.

Hierarkisk klyngering vil hjælpe med at skabe klynger i en rigtig rækkefølge / hierarki. Eksempel: det mest almindelige dagligdagse eksempel, vi ser, er, hvordan vi bestiller vores filer og mapper på vores computer efter et rigtigt hierarki.

Typer af hierarkisk klynge

Hierarkisk klynge klassificeres yderligere i to typer, dvs. Agglomerativ klynge og opdelende klynger (DIANA)

Agglomerativ gruppering

I dette tilfælde af klynge udføres den hierarkiske nedbrydning ved hjælp af bottom-up-strategi, hvor det starter med at oprette atomiske (små) klynger ved at tilføje et dataobjekt ad gangen og derefter flette dem sammen for at danne en stor klynge i slutningen, hvor denne klynge opfylder alle opsigelsesbetingelser. Denne procedure er iterativ, indtil alle datapunkter er bragt under en enkelt stor klynge.

AGNES (AGglomerative NESting) er en type agglomerativ klynge, der kombinerer dataobjekterne i en klynge baseret på lighed. Resultatet af denne algoritme er en træbaseret struktureret kaldet Dendrogram. Her bruger den afstandsmetrikerne til at bestemme, hvilke datapunkter der skal kombineres med hvilken klynge. Grundlæggende konstruerer den en afstandsmatrix og kontrollerer for par klynger med den mindste afstand og kombinerer dem.

Ovenstående figur viser Agglomerative vs. Divisive clustering

Baseret på hvordan afstanden mellem hver klynge måles kan vi have 3 forskellige metoder

  • Enkelt kobling : Hvor den korteste afstand mellem de to punkter i hver klynge defineres som afstanden mellem klyngerne.
  • Komplet sammenkobling : I dette tilfælde betragter vi den længste afstand mellem punkterne i hver klynge som afstanden mellem klyngerne.
  • Gennemsnitlig kobling: Her tager vi gennemsnittet mellem hvert punkt i en klynge til hvert andet punkt i den anden klynge.

Lad os nu diskutere om styrker og svagheder i AGNES; denne algoritme har en tidskompleksitet på mindst O (n 2 ), og det klarer sig derfor ikke godt i skalering, og en anden større ulempe er, at alt, hvad der er blevet gjort, aldrig kan fortrydes, dvs. hvis vi forkert grupperer en klynge i tidligere fase af algoritmen, så vil vi ikke være i stand til at ændre resultatet / ændre det. Men denne algoritme har også en lys side, da der er mange mindre klynger, der kan dannes, det kan være nyttigt i opdagelsesprocessen, og det producerer en rækkefølge af objekter, som er meget nyttige i visualisering.

Divisive Clustering (DIANA)

Diana står dybest set for Divisive Analysis; dette er en anden type hierarkisk klynge, hvor det dybest set fungerer på princippet om top-down tilgang (invers af AGNES), hvor algoritmen begynder med at danne en stor klynge, og den rekursivt deler den mest forskellige klynge i to, og den fortsætter, indtil vi ' alle de lignende datapunkter hører hjemme i deres respektive klynger. Disse opdelende algoritmer resulterer i meget nøjagtige hierarkier end den agglomerative tilgang, men de er beregningsdygtige.

Ovenstående figur viser Opdelende klynger trin for trin proces

Flerfase hierarkisk klynge

For at forbedre kvaliteten af ​​klynger genereret af ovennævnte hierarkiske klyngeteknikker integrerer vi vores hierarkiske klyngeteknikker med andre klyngeteknikker; dette kaldes flerfase-klynger. De forskellige typer flerfase-klynger er som følger:

  • BIRCH (Balanced Iterativ reduktion og klynge ved hjælp af hierarkier)
  • ROCK (RObust Clustering ved hjælp af links)
  • CHAMELEON

1. Afbalanceret itterativ reduktion og klynge ved hjælp af hierarkier

Denne metode bruges hovedsageligt til klynge af enorme mængder numeriske data ved at integrere vores hierarkiske / mikroklynger i den indledende fase og makroklynger / iterativ partitionering i den senere fase. Denne metode hjælper med at overvinde skalerbarhedsproblemet, vi stod overfor i AGNES og manglende evne til at fortryde, hvad der blev gjort i før trin. BIRCH bruger to vigtige koncepter i sin algoritme

en. Clustering-funktion (hjælper med at opsummere klyngen)

CF er defineret som (n- antal datapunkter i klyngen, den lineære sum af n punkter, kvadratsummen af ​​n point). Opbevaring af en klyngs funktion på denne måde hjælper med at undgå at gemme detaljerede oplysninger om det, og CF er additiv i naturen til forskellige klynger.

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

b. Klyngefunktionstræ (hjælper med at repræsentere en klynge som et hierarki)

CF-træ er et afbalanceret træ med forgreningsfaktor B (maksimalt antal børn) og tærskel T (maks. Antal underklynger, der kan opbevares i bladknudepunkter).

Algoritmen fungerer dybest set i 2 faser; i fase 1 scanner den databasen og bygger et CF-træ i hukommelsen, og i fase 2 bruger den klynge-algoritmen, som hjælper med at klynge bladknudene ved at fjerne outliers (sparse klynger) og grupperer klyngen med maksimal tæthed. Den eneste ulempe ved denne algoritme er, at den kun håndterer den numeriske datatype.

2. Robust klynge ved hjælp af link

Link defineres som antallet af fælles naboer mellem to objekter. ROCK-algoritme er en type klynge-algoritme, der bruger dette begreb af forbindelse med det kategoriske datasæt. Som vi ved, at den målte afstandsklynge-algoritmer ikke giver højkvalitetsklynger til det kategoriske datasæt, men i tilfælde af ROCK, betragter det også kvartererne til datapunkterne, dvs. hvis to datapunkter har det samme kvarter, er de sandsynligvis hører til i den samme klynge. Algoritmen konstruerer en sparsom graf i det første trin under hensyntagen til lighedsmatrixen med begrebet kvarter og lighedstærskel. I det andet trin bruger den den agglomerative hierarkiske klyngeteknik på den sparsomme graf.

3. Kameleon

Denne type hierarkisk klynge-algoritme bruger begrebet dynamisk modellering. Spekulerer på hvorfor kaldes det dynamisk? Det kaldes dynamisk, fordi det har evnen til at tilpasse sig de interne klyngeegenskaber automatisk ved at evaluere klyngens lighed, dvs. hvor godt forbundet datapunkterne i en klynge og i nærheden af ​​klynger. En af ulemperne ved kamæleon er, at forarbejdningsomkostningerne er for høje (O (n 2 ) for n-objekter er værst-tidskompleksiteten).

Billedkilde - Google

Konklusion

I denne artikel har vi lært, hvad en klynge er, og hvad er klyngeanalyse, forskellige typer hierarkiske klyngeteknikker, deres fordele og ulemper. Hver af de teknikker, vi diskuterede, har deres egne plus og minus, og derfor skal vi, inden vi går videre med en algoritme, forstå vores data med korrekt efterforskende dataanalyse og vælge algoritmen med forsigtighed.

Anbefalede artikler

Dette er en guide til hierarkisk klynge-analyse. Her diskuterer vi oversigten, agglomerativ clustering, divisive Clustering (DIANA) og flerfase hierarkisk clustering. Du kan også se på de følgende artikler for at lære mere

  1. Hierarkisk klynge i R
  2. Clustering algoritme
  3. klynger
  4. Clustering Methods
  5. Klynge i maskinlæring
  6. Hierarkisk klynge | Agglomerativ og opdelende klynge

Kategori:

Big Data