Översikt av hierarkisk klusteranalys

Innan vi går vidare och förstår om hierarkisk klusteranalys, låt oss först försöka förstå vad som är ett kluster? Och vad är klusteranalys? Ett kluster är en samling dataobjekt; datapunkterna i ett kluster liknar varandra och skiljer sig åt datapunkterna i det andra klustret. Klusteranalys är i princip en gruppering av dessa datapunkter i klustret. Clustering är en typ av oövervakad maskininlärningsalgoritm, där det inte finns några utbildningsmärkta datamängder. Det finns olika typer av klusteranalyser, en sådan typ är Hierarkisk klustering.

Hierarkisk klustering hjälper till att skapa kluster i rätt ordning / hierarki. Exempel: det vanligaste vardagliga exemplet vi ser är hur vi beställer våra filer och mappar i vår dator efter rätt hierarki.

Typer av hierarkisk gruppering

Hierarkisk klustering klassificeras vidare i två typer, dvs Agglomerativ klustering och Divisive Clustering (DIANA)

Agglomerativ gruppering

I detta fall av kluster görs den hierarkiska sönderdelningen med hjälp av bottom-up-strategi där det börjar med att skapa atomiska (små) kluster genom att lägga till ett dataobjekt i taget och sedan sammanfoga dem för att bilda ett stort kluster i slutet, där detta kluster uppfyller alla uppsägningsvillkor. Den här proceduren är iterativ tills alla datapunkter har tagits under ett enda stort kluster.

AGNES (AGglomerative NESting) är en typ av agglomerativ gruppering som kombinerar dataobjekten till ett kluster baserat på likhet. Resultatet av denna algoritm är en trädbaserad struktur som kallas Dendrogram. Här använder den avståndsmätningarna för att bestämma vilka datapunkter som ska kombineras med vilket kluster. I grund och botten konstruerar den en distansmatris och kontrollerar för par av kluster med det minsta avståndet och kombinerar dem.

Figuren ovan visar agglomerativ kontra dividerande kluster

Baserat på hur avståndet mellan varje kluster mäts kan vi ha 3 olika metoder

  • Enkel koppling : Där det kortaste avståndet mellan de två punkterna i varje kluster definieras som avståndet mellan klustren.
  • Komplett koppling : I det här fallet kommer vi att betrakta det längsta avståndet mellan punkterna i varje kluster som avståndet mellan klustren.
  • Genomsnittlig koppling: Här tar vi genomsnittet mellan varje punkt i ett kluster till varje annan punkt i det andra klustret.

Låt oss nu diskutera om styrkorna och svagheten i AGNES; denna algoritm har en tidskomplexitet på åtminstone O (n 2 ) varför den inte klarar sig bra i skalning, och en annan större nackdel är att allt som har gjorts kan aldrig ångras, dvs om vi felaktigt grupperar något kluster i tidigare skede av algoritmen då kommer vi inte att kunna ändra resultatet / modifiera det. Men denna algoritm har också en ljus sida eftersom det finns många mindre kluster som kan bildas, det kan vara till hjälp i upptäcktsprocessen och det producerar en beställning av objekt som är mycket användbart vid visualisering.

Divisive Clustering (DIANA)

Diana står i princip för Divisive Analysis; detta är en annan typ av hierarkisk kluster där det i grund och botten fungerar på principen om top-down-strategi (invers av AGNES) där algoritmen börjar med att bilda ett stort kluster och det rekursivt delar upp det mest olika klustret i två och det fortsätter tills vi ' alla liknande datapunkter hör hemma i deras respektive kluster. Dessa delande algoritmer resulterar i mycket exakta hierarkier än den agglomerativa metoden, men de är beräkningsvärda dyra.

Ovanstående figur visar delande kluster steg för steg-process

Flerfas-hierarkisk klustering

För att förbättra kvaliteten på kluster som genereras av ovan nämnda hierarkiska klusteringstekniker integrerar vi våra hierarkiska klusteringstekniker med andra klusteringstekniker; detta kallas för flerfasskluster. De olika typerna av flerfas-kluster är följande:

  • BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)
  • ROCK (RObust Clustering med länkar)
  • KAMELEONT

1. Balanserad iterativ reduktion och kluster med hjälp av hierarkier

Denna metod används huvudsakligen för att klustera en enorm mängd numeriska data genom att integrera vår hierarkiska / mikro-klustering i den inledande fasen och makroklustering / iterativ partitionering i den senare fasen. Den här metoden hjälper till att övervinna skalbarhetsproblemet vi mötte i AGNES och oförmågan att ångra det som gjordes i före steg. BIRCH använder två viktiga begrepp i sin algoritm

a. Clustering-funktion (hjälper till att sammanfatta klustret)

CF definieras som (n-antal datapunkter i klustret, den linjära summan av n punkter, kvadratsumman av n punkter). Att lagra funktionen hos ett kluster på detta sätt hjälper till att undvika att lagra detaljerad information om det och CF är tilläggs karaktär för olika kluster.

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

b. Klusterfunktionsträd (hjälper till att representera ett kluster som en hierarki)

CF-träd är ett balanserat träd med förgreningsfaktor B (maximalt antal barn) och tröskel T (maxantal underkluster som kan lagras i bladnoder).

Algoritmen fungerar i princip i två faser; i fas 1 skannar den databasen och bygger ett CF-träd i minnet och i fas 2 använder den klusteralgoritmen som hjälper till att klustera bladnoderna genom att ta bort outliers (glesa kluster) och grupperar klustret med maximal densitet. Den ena nackdelen med denna algoritm är att den endast hanterar den numeriska datatypen.

2. Robust kluster med hjälp av länkar

Länk definieras som antalet vanliga grannar mellan två objekt. ROCK-algoritm är en typ av klusteralgoritm som använder detta begrepp länk till det kategoriska datasättet. Som vi vet att de avståndsmätade klusteralgoritmerna inte ger högkvalitativa kluster för det kategoriska datasättet, men i fallet med ROCK, betraktar det även grannskapen i datapunkterna, dvs om två datapunkter har samma grannskap så är de mest troligt att tillhöra i samma kluster. Algoritmen kommer att konstruera en gles graf i det första steget med hänsyn till likhetsmatrisen med begreppet grannskap och likhetströskel. I det andra steget använder den den agglomerativa hierarkiska klusteringstekniken på den glesa grafen.

3. Kameleon

Denna typ av hierarkisk klusteralgoritm använder begreppet dynamisk modellering. Undrar varför kallas det dynamiskt? Det kallas dynamiskt eftersom det har förmågan att anpassa sig till de interna klusteregenskaperna automatiskt genom att utvärdera klusterens likhet, dvs hur väl anslutna datapunkterna i ett kluster och i närheten av kluster. En av nackdelarna med kameleont är att bearbetningskostnaden är för hög (O (n 2 ) för n-objekt är i värsta fall tidskomplexiteten).

Bildkälla - Google

Slutsats

I den här artikeln har vi lärt oss vad ett kluster är och vad som är klusteranalys, olika typer av hierarkiska klusteringstekniker deras fördelar och nackdelar. Var och en av de tekniker vi diskuterade har sina egna plus och minus, och därför måste vi förstå våra data med korrekt undersökande dataanalys och välja algoritmen med försiktighet innan vi går vidare med en algoritm.

Rekommenderade artiklar

Detta är en guide till hierarkisk klusteranalys. Här diskuterar vi översikten, agglomerativ gruppering, delande kluster (DIANA) och flerfas hierarkisk kluster. Du kan också titta på följande artiklar för att lära dig mer

  1. Hierarkisk gruppering i R
  2. Clustering algoritm
  3. kluster
  4. Clustering Methods
  5. Clustering in Machine Learning
  6. Hierarkisk klustering Agglomerativ & delande kluster

Kategori:

Big Data