Overzicht van hiërarchische clusteranalyse
Voordat we verder gaan en inzicht krijgen in hiërarchische clusteranalyse, moeten we eerst proberen te begrijpen wat een cluster is? En wat is clusteranalyse? Een cluster is een verzameling gegevensobjecten; de gegevenspunten binnen een cluster lijken meer op elkaar en verschillen van de gegevenspunten in het andere cluster. Clusteranalyse is in feite een groepering van deze gegevenspunten in het cluster. Clustering is een type niet-gecontroleerd machine learning-algoritme, waarvoor geen gegevensset met trainingslabels bestaat. Er zijn verschillende soorten clusteringanalyses, een dergelijk type is hiërarchische clustering.
Hiërarchische clustering helpt bij het maken van clusters in een juiste volgorde / hiërarchie. Voorbeeld: het meest voorkomende dagelijkse voorbeeld dat we zien, is hoe we onze bestanden en mappen op onze computer rangschikken volgens een juiste hiërarchie.
Soorten hiërarchische clustering
Hiërarchische clustering is verder onderverdeeld in twee typen, namelijk Agglomeratieve clustering en Divisive Clustering (DIANA)
Agglomeratieve clustering
In dit geval van clustering wordt de hiërarchische ontbinding gedaan met behulp van een bottom-up strategie, waarbij het begint met het maken van atomaire (kleine) clusters door één gegevensobject tegelijk toe te voegen en ze vervolgens samenvoegt om een groot cluster aan het einde te vormen, waar dit cluster aan alle beëindigingsvoorwaarden voldoet. Deze procedure is iteratief totdat alle gegevenspunten onder één groot cluster zijn ondergebracht.
AGNES (AGglomerative NESting) is een type agglomeratieve clustering die de gegevensobjecten combineert in een cluster op basis van gelijkenis. Het resultaat van dit algoritme is een boomstructuur met de naam Dendrogram. Hier gebruikt het de afstandsstatistieken om te beslissen welke gegevenspunten met welk cluster moeten worden gecombineerd. Kortom, het construeert een afstandsmatrix en controleert op het paar clusters met de kleinste afstand en combineert ze.
De bovenstaande afbeelding toont Agglomerative versus Divisive clustering
Op basis van hoe de afstand tussen elk cluster wordt gemeten, kunnen we 3 verschillende methoden hebben
- Enkele koppeling : waarbij de kortste afstand tussen de twee punten in elk cluster wordt gedefinieerd als de afstand tussen de clusters.
- Volledige koppeling : in dit geval beschouwen we de langste afstand tussen de punten in elk cluster als de afstand tussen de clusters.
- Gemiddelde koppeling: hier nemen we het gemiddelde tussen elk punt in het ene cluster naar elk ander punt in het andere cluster.
Laten we het nu hebben over de sterke en zwakke punten in AGNES; dit algoritme heeft een tijdcomplexiteit van ten minste O (n 2 ), dus het doet het niet goed bij het schalen, en een ander belangrijk nadeel is dat wat er is gedaan, nooit ongedaan kan worden gemaakt, dwz als we een cluster in een eerdere fase van het algoritme, kunnen we de uitkomst niet wijzigen / wijzigen. Maar dit algoritme heeft ook een positieve kant, omdat er veel kleinere clusters worden gevormd, het kan nuttig zijn bij het ontdekkingsproces en het produceert een ordening van objecten, wat erg handig is bij visualisatie.
Divisive Clustering (DIANA)
Diana staat in feite voor Divisive Analysis; dit is een ander type hiërarchische clustering, waar het in principe werkt volgens het principe van top-downbenadering (omgekeerd van AGNES), waarbij het algoritme begint met het vormen van een groot cluster en het recursief het meest ongelijksoortige cluster in twee verdeelt en het gaat door totdat we ' alle vergelijkbare datapunten horen thuis in hun respectieve clusters. Deze verdeeldheid algoritmen resulteren in zeer nauwkeurige hiërarchieën dan de agglomeratieve benadering, maar ze zijn rekenkundig duur.
De bovenstaande afbeelding toont stapsgewijs splitsende clusters
Meerfasen hiërarchische clustering
Om de kwaliteit van clusters die zijn gegenereerd door de bovengenoemde hiërarchische clusteringstechnieken te verbeteren, integreren we onze hiërarchische clusteringstechnieken met andere clusteringstechnieken; dit wordt multifaseclustering genoemd. De verschillende soorten meerfasenclustering zijn als volgt:
- BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)
- ROCK (RObust Clustering met behulp van links)
- KAMELEON
1. Evenwichtig Iteratief verminderen en clusteren met behulp van hiërarchieën
Deze methode wordt voornamelijk gebruikt voor het clusteren van een grote hoeveelheid numerieke gegevens door onze hiërarchische / microclustering in de beginfase en macroclustering / iteratieve verdeling in de latere fase te integreren. Deze methode helpt bij het oplossen van het schaalbaarheidsprobleem waarmee we te maken hadden in AGNES en het onvermogen om ongedaan te maken wat in de vorige stap was gedaan. BIRCH gebruikt twee belangrijke concepten in zijn algoritme
een. Clusteringfunctie (helpt bij het samenvatten van het cluster)
CF wordt gedefinieerd als (n- aantal gegevenspunten in het cluster, de lineaire som van n punten, de kwadratische som van n punten). Door het kenmerk van een cluster op deze manier op te slaan, voorkomt u dat u gedetailleerde informatie hierover opslaat. CF is additief van aard voor verschillende clusters.
CF 1 + CF 2 =
b. Clustering functieboom (helpt bij het weergeven van een cluster als een hiërarchie)
CF-boom is een gebalanceerde boom met vertakkingsfactor B (maximaal aantal kinderen) en drempel T (maximaal aantal subclusters die kunnen worden opgeslagen in bladknooppunten).
Het algoritme werkt in principe in 2 fasen; in fase 1 scant het de database en bouwt een CF-boom in het geheugen en in fase 2 gebruikt het het cluster-algoritme dat helpt bij het clusteren van de bladknopen door het verwijderen van de uitbijters (schaarse clusters) en groepeert de cluster met maximale dichtheid. Het enige nadeel van dit algoritme is dat het alleen het numerieke gegevenstype verwerkt.
2. Robuust clusteren met behulp van link's
Link wordt gedefinieerd als het aantal gemeenschappelijke buren tussen twee objecten. ROCK-algoritme is een type clusteringalgoritme dat dit concept van koppeling met de categorische gegevensset gebruikt. Zoals we weten, bieden de op afstand gemeten clusteringalgoritmen geen hoogwaardige clusters voor de categorische gegevensset, maar in het geval van ROCK houdt het ook rekening met de buurten van de gegevenspunten, dwz als twee gegevenspunten dezelfde omgeving hebben, zijn ze waarschijnlijk in hetzelfde cluster. Het algoritme zal in de eerste stap een spaarzame grafiek construeren waarbij rekening wordt gehouden met de gelijkenismatrix met het concept van de buurt- en gelijkenisdrempel. In de tweede stap wordt de agglomeratieve hiërarchische clusteringstechniek op de schaarse grafiek gebruikt.
3. Kameleon
Dit type hiërarchisch clusteringalgoritme maakt gebruik van het concept van dynamische modellering. Vraagt u zich af waarom het dynamisch wordt genoemd? Het wordt dynamisch genoemd omdat het de mogelijkheid heeft om zich automatisch aan te passen aan de interne clusterkarakteristieken door de clusterovereenkomst te evalueren, dat wil zeggen hoe goed de gegevenspunten binnen een cluster en in de nabijheid van clusters zijn verbonden. Een van de nadelen van kameleon is dat de verwerkingskosten te hoog zijn (O (n 2 ) voor n objecten is de tijdcomplexiteit in het slechtste geval).
Afbeeldingsbron - Google
Conclusie
In dit artikel hebben we geleerd wat een cluster is en wat clusteranalyse is, verschillende soorten hiërarchische clusteringstechnieken hun voor- en nadelen. Elk van de technieken die we hebben besproken, heeft zijn eigen plus en min, dus voordat we verder gaan met een algoritme, moeten we onze gegevens begrijpen met de juiste verkennende gegevensanalyse en het algoritme voorzichtig kiezen.
Aanbevolen artikelen
Dit is een handleiding voor hiërarchische clusteranalyse. Hier bespreken we het overzicht, agglomeratieve clustering, divisive Clustering (DIANA) en multifase hiërarchische clustering. U kunt ook de volgende artikelen bekijken voor meer informatie
- Hiërarchische clustering in R
- Clustering Algoritme
- clusters
- Clustering methoden
- Clustering in machine learning
- Hiërarchische clustering | Agglomerative & Divisive Clustering