Prezentare generală a analizei de clustering ierarhice
Înainte de a merge mai departe și de a înțelege despre analiza ierarhică de clustering, mai întâi să încercăm să înțelegem ce este un cluster? Și ce este analiza clusterului? Un cluster este o colecție de obiecte de date; punctele de date dintr-un cluster sunt mai asemănătoare între ele și diferite ale punctelor de date din celălalt cluster. Analiza clusterului este practic o grupare a acestor puncte de date în cluster. Clusteringul este un tip de algoritm de învățare automată nesupravegheat, în care nu există seturi de date etichetate pentru instruire. Există diferite tipuri de analiză de clustering, un astfel de tip este clusteringul ierarhic.
Gruparea ierarhică va ajuta la crearea de clustere într-o ordine / ierarhie adecvată. Exemplu: cel mai obișnuit exemplu zilnic pe care îl vedem este modul în care ordonăm fișierele și folderele din computerul nostru printr-o ierarhie adecvată.
Tipuri de grupări ierarhice
Clusterizarea ierarhică este în continuare clasificată în două tipuri, adică clustering aglomerativ și clustering diviziv (DIANA)
Gruparea aglomerativă
În acest caz de aglomerare, descompunerea ierarhică se face cu ajutorul strategiei de jos în sus, unde se începe prin crearea de grupuri atomice (mici), prin adăugarea unui obiect de date simultan și apoi le îmbină pentru a forma un cluster mare la sfârșit., unde acest cluster îndeplinește toate condițiile de reziliere. Această procedură este iterativă până când toate punctele de date sunt aduse sub un singur cluster mare.
AGNES (AGglomerative NESting) este un tip de aglomerare de grup care combină obiectele de date într-un cluster bazat pe similaritate. Rezultatul acestui algoritm este structurat pe baza unui arbore numit Dendrogram. Aici folosește valorile distanței pentru a decide care puncte de date trebuie combinate cu ce cluster. Practic, construiește o matrice de distanță și verifică perechea de grupuri cu cea mai mică distanță și le combină.
Figura de mai sus arată aglomerarea vs. grupări divizate
Pe baza modului în care se măsoară distanța dintre fiecare cluster, putem avea 3 metode diferite
- O singură legătură : În cazul în care distanța cea mai scurtă dintre cele două puncte din fiecare grup este definită ca distanța dintre clustere.
- Legătură completă : În acest caz, vom considera distanța cea mai lungă dintre punctele din fiecare cluster ca distanța dintre cluster.
- Legătură medie: Aici vom lua media între fiecare punct dintr-un cluster la fiecare alt punct din celălalt cluster.
Acum să discutăm despre punctele forte și slăbiciunea în AGNES; acest algoritm are o complexitate de timp de cel puțin O (n 2 ), prin urmare, nu merge bine la scalare, iar un alt dezavantaj major este că orice s-a făcut nu poate fi niciodată anulat, adică Dacă grupăm în mod incorect vreun cluster în faza anterioară a algoritmul atunci nu vom putea modifica rezultatul / modificarea acestuia. Dar acest algoritm are și o latură strălucitoare, deoarece există multe clustere mai mici care se formează, poate fi de ajutor în procesul de descoperire și produce o ordonare a obiectelor care este foarte utilă în vizualizare.
Clustering diviziv (DIANA)
Diana înseamnă practic Analiza Divizivă; acesta este un alt tip de clustering ierarhic în care funcționează practic pe principiul abordării de sus în jos (invers al AGNES), unde algoritmul începe prin formarea unui cluster mare și divizează recursiv cel mai diferit cluster în două și continuă până când ” toate punctele de date similare aparțin grupurilor respective. Acești algoritmi divizivi au ca rezultat ierarhii extrem de exacte decât abordarea aglomerativă, dar sunt costisitoare din punct de vedere al calculului.
Figura de mai sus prezintă procesul de grupare divizivă pas cu pas
Gruparea Ierarhică Multifazică
Pentru a îmbunătăți calitatea clusterelor generate de tehnicile de clustering ierarhice menționate mai sus, integrăm tehnicile noastre de clustering ierarhic cu alte tehnici de clustering; aceasta se numește clustering multifazic. Diferitele tipuri de clustering multifazic sunt următoarele:
- BIRCH (reducerea echitabilă și clusterizarea iterativă folosind Ierarhiile)
- ROCK (clustering RObust folosind link-uri)
- CAMELEON
1. Reducerea și gruparea iterativă echilibrată folosind Ierarhiile
Această metodă este utilizată în principal pentru clusterizarea unei cantități uriașe de date numerice prin integrarea clusterării noastre ierarhice / micro în faza inițială și a compartimentării macro / iterative la faza ulterioară. Această metodă ajută la depășirea problemei de scalabilitate cu care ne-am confruntat în AGNES și incapacitatea de a anula ceea ce a fost făcut înainte de pas. BIRCH folosește două concepte importante în algoritmul său
A. Funcția de clustering (ajută la rezumarea clusterului)
CF este definit ca (n- număr de puncte de date din cluster, suma liniară a n puncte, suma pătrată a n puncte). Stocarea caracteristicii unui cluster în acest fel ajută la evitarea stocării informațiilor detaliate despre acesta, iar CF-ul este de natură aditivă pentru diferite clustere.
CF 1 + CF 2 =
b. Arborele de funcții de clustering (ajută la reprezentarea unui cluster ca o ierarhie)
Arborele CF este un arbore echilibrat cu factorul B de ramificare (numărul maxim de copii) și pragul T (numărul maxim de sub-clustere care pot fi stocate în nodurile frunzelor).
Algoritmul funcționează practic în 2 faze; în faza 1 scanează baza de date și construiește un arbore CF în memorie, iar în faza 2 folosește algoritmul de clustering care ajută la aglomerarea nodurilor frunzelor prin îndepărtarea outliers-urilor (cluster-uri rare) și grupează clusterul cu densitate maximă. Singurul și unicul dezavantaj al acestui algoritm este că gestionează doar tipul de date numerice.
2. Clustering robust folosind link-uri
Legătura este definită ca numărul de vecini comuni între două obiecte. Algoritmul ROCK este un tip de algoritm de clustering care utilizează acest concept de legătură cu setul de date categorice. După cum știm că algoritmii de clustering măsurați la distanță nu oferă clustere de înaltă calitate pentru setul de date categorice, dar, în cazul ROCK, consideră vecinătatea punctelor de date, adică dacă două puncte de date au același cartier, atunci acestea sunt cel mai probabil aparține aceluiași grup. Algoritmul va construi un grafic rar în primul pas ținând cont de matricea de asemănare cu conceptul de prag de vecinătate și de similaritate. În a doua etapă, se folosește tehnica de aglomerare ierarhică de clustering pe graficul redus.
3. Chameleon
Acest tip de algoritm de ierarhizare de clustering folosește conceptul de modelare dinamică. Te întrebi de ce se numește dinamic? Se numește dinamic, deoarece are capacitatea de a se adapta la caracteristicile interne ale clusterului, evaluând similaritatea clusterului, adică cât de bine conectați punctele de date dintr-un cluster și la proximitatea clusterilor. Unul dintre dezavantajele cameleonului este că costul procesării este prea mare (O (n 2 ) pentru n obiecte este cea mai proastă complexitate de timp).
Sursa imaginii - Google
Concluzie
În acest articol, am învățat ce este un cluster și ce este analiza clusterului, diferite tipuri de tehnici ierarhice de clustering avantajele și dezavantajele acestora. Fiecare dintre tehnicile pe care le-am discutat are propriul plus și minus, prin urmare, înainte de a merge mai departe cu un algoritm, trebuie să înțelegem datele noastre cu o analiză adecvată a datelor exploratorii și să alegem algoritmul cu prudență.
Articole recomandate
Acesta este un ghid pentru analiza ierarhică de clustering. Aici discutăm prezentarea de ansamblu, aglomerarea de aglomerare, clustering diviziv (DIANA) și clustering ierarhic multifazic. De asemenea, puteți consulta următoarele articole pentru a afla mai multe
- Gruparea Ierarhică în R
- Algoritmul de clustering
- clustere
- Metode de clustering
- Gruparea în învățarea mașinilor
- Gruparea Ierarhică | Gruparea aglomerativă și divizivă