Katsaus hierarkkiseen klusterointianalyysiin
Ennen kuin siirrymme eteenpäin ja ymmärrämme hierarkkisesta klusterointianalyysistä, yritämme ensin ymmärtää mikä on klusteri? Ja mitä klusterianalyysi on? Klusteri on kokoelma tietoobjekteja; klusterin datapisteet ovat samankaltaisia toistensa kanssa ja eroavat toisen klusterin datapisteistä. Klusterianalyysi on periaatteessa näiden tietopisteiden ryhmittely klusteriin. Klusterointi on eräänlainen ohjaamaton koneoppimisalgoritmi, jossa ei ole harjoitusmerkittyjä tietojoukkoja. Ryhmäanalyysejä on erityyppisiä, yksi tyyppi on hierarkkinen klusterointi.
Hierarkkinen klusterointi auttaa luomaan klustereita oikeassa järjestyksessä / hierarkiassa. Esimerkki: yleisin päivittäinen esimerkki, jonka näemme, on, kuinka tilaamme tiedostoja ja kansioita tietokoneellemme oikealla hierarkialla.
Hierarkkisen klusteroinnin tyypit
Hierarkkinen klusterointi luokitellaan edelleen kahteen tyyppiin eli agglomeratiiviseen klusterointiin ja jakavaan klusterointiin (DIANA)
Agglomeratiivinen klusterointi
Tässä klusteroinnissa hierarkkinen hajoaminen tapahtuu alhaalta ylöspäin -strategian avulla, jossa se alkaa luomalla atomisia (pieniä) klustereita lisäämällä yksi tietoobjekti kerrallaan ja yhdistämällä ne sitten yhteen muodostaen loppua suuren klusterin., jossa tämä klusteri täyttää kaikki lopettamisehdot. Tämä menettely on toistuva, kunnes kaikki datapisteet saatetaan yhdeksi suureksi klusteriksi.
AGNES (AGglomerative NESting) on eräänlainen taajamainen klusterointi, joka yhdistää tietoobjektit klusteriksi samankaltaisuuden perusteella. Tämän algoritmin tulos on puupohjainen rakenne, nimeltään Dendrogram. Tässä se käyttää etäisyysmittaria päättääkseen, mitkä datapisteet tulisi yhdistää mihin klusteriin. Pohjimmiltaan se rakentaa etäisyysmatriisin ja tarkistaa klusteriparin, jolla on pienin etäisyys, ja yhdistää ne.
Yllä oleva kuva esittää agglomeratiivista vs. jakavaa klusterointia
Sen perusteella, miten kunkin klusterin välinen etäisyys mitataan, meillä voi olla 3 erilaista menetelmää
- Yksittäinen kytkentä : Kun kunkin klusterin kahden pisteen välinen lyhin etäisyys määritellään klustereiden väliseksi etäisyydeksi.
- Täydellinen kytkentä : Tässä tapauksessa ryhdymme etäisyydeksi kunkin klusterin pisteiden pisin etäisyys.
- Keskimääräinen kytkentä: Tässä otamme keskiarvon kunkin klusterin pisteen välillä toisen klusterin jokaiseen pisteeseen.
Keskustelemme nyt AGNESin vahvuuksista ja heikkouksista; Tämän algoritmin aikakompleksisuus on vähintään O (n 2 ), joten se ei suoriudu skaalauksessa hyvin, ja eräs toinen suuri haitta on, että mitä tahansa on tehty, sitä ei voi koskaan peruuttaa, ts. jos ryhmittelemme väärin minkä tahansa klusterin väärin algoritmi, niin emme voi muuttaa tulosta / muokata sitä. Mutta tällä algoritmilla on myös valoisa puoli, koska muodostuu monia pienempiä klustereita. Se voi olla hyödyllinen löytöprosessissa ja tuottaa kohteiden tilauksen, joka on erittäin hyödyllinen visualisoinnissa.
Jakautuva klusterointi (DIANA)
Diana tarkoittaa periaatteessa erimielisyyttä; tämä on toisen tyyppinen hierarkkinen klusterointi, jossa se toimii periaatteessa ylhäältä alas -lähestymistavalla (käänteinen AGNES: lle), missä algoritmi alkaa muodostamalla suuri klusteri ja jakaa rekursiivisesti kaikkein erilaisimman klusterin kahteen osaan ja jatkuu, kunnes me ' kaikki samanlaiset datapisteet kuuluvat vastaaviin klusteriinsa. Nämä jakavat algoritmit johtavat erittäin tarkkoihin hierarkioihin kuin agglomeratiivinen lähestymistapa, mutta ne ovat laskennallisesti kalliita.
Yllä oleva kuva osoittaa jakautuvan klusteroinnin vaihe vaiheelta
Monivaiheinen hierarkkinen ryhmittely
Edellä mainittujen hierarkkisten klusterointitekniikoiden tuottamien klusterien laadun parantamiseksi integroimme hierarkkisen klusterointitekniikkamme muihin klusterointitekniikoihin; Tätä kutsutaan monivaiheiseksi klusteroitumiseksi. Eri tyyppiset monivaiheiset klusteroinnit ovat seuraavat:
- BIRCH (tasapainoinen iteratiivinen vähentäminen ja ryhmittely hierarkioiden avulla)
- ROCK (RObust-klusterointi linkkien avulla)
- KAMELEONTTI
1. Tasapainotettu toistuva vähentäminen ja ryhmittely hierarkioiden avulla
Tätä menetelmää käytetään pääasiassa valtavan määrän numeerisen datan klusterointiin integroimalla hierarkkinen / mikro-klusterointi alkuvaiheessa ja makroklusterointi / iteratiivinen osiointi myöhemmässä vaiheessa. Tämä menetelmä auttaa selviytymään skaalautuvuusongelmasta, joka kohdataan AGNESissä, ja kyvyttömyydestä kumota ennen askelta tehtyä. BIRCH käyttää algoritmissaan kahta tärkeää konseptia
a. Klusterointiominaisuus (auttaa ryhmittelyn tekemisessä)
CF määritetään (n - klusterin datapisteiden lukumäärä, n pisteen lineaarinen summa, n pisteen neliösumma). Klusterin ominaisuuden säilyttäminen tällä tavalla auttaa välttämään yksityiskohtaisen tiedon säilyttämistä siitä, ja CF on luonteeltaan additiivinen eri klustereille.
CF1 + CF2 =
b. Klusterointiominaisuuspuu (auttaa edustamaan klusteria hierarkiana)
CF-puu on tasapainoinen puu, jolla on haarautumiskerroin B (enimmäismäärä lapsia) ja kynnysarvo T (enimmäislukumäärä alaryhmiä, joita voidaan säilyttää lehtisolmuissa).
Algoritmi toimii periaatteessa kahdessa vaiheessa; vaiheessa 1 se skannaa tietokannan ja rakentaa muistiin tallennetun CF-puun ja vaiheessa 2 käyttää klusterointialgoritmia, joka auttaa ryhmittelemään lehtisolmuja poistamalla syrjäytykset (harvat klusterit) ja ryhmittelemällä klusterin suurimmalla tiheydellä. Tämän algoritmin ainoa haittapuoli on, että se käsittelee vain numeerista tietotyyppiä.
2. Vankka klusterointi linkkien avulla
Linkki määritellään kahden objektin välisten yhteisten naapureiden lukumääräksi. ROCK-algoritmi on eräänlainen klusterointialgoritmi, joka käyttää tätä linkin käsitettä kategorisen tietojoukon kanssa. Koska tiedämme, että etäisyydellä mitatut klusterointialgoritmit eivät tarjoa korkealaatuisia klustereita kategorialliselle aineistolle, mutta ROCK: n tapauksessa se ottaa huomioon myös datapisteiden naapurustot, ts. Jos kahdella datapisteellä on sama naapuruus, niin ne ovat kuuluvat todennäköisimmin samaan klusteriin. Algoritmi konstruoi ensimmäisessä vaiheessa hajanaisen kuvaajan ottaen huomioon samankaltaisuusmatriisin naapuruuden ja samankaltaisuuskynnyksen käsitteen kanssa. Toisessa vaiheessa se käyttää agglomeratiivista hierarkkista klusterointitekniikkaa harvassa kuvaajassa.
3. kameleontti
Tämän tyyppinen hierarkkinen klusterointialgoritmi käyttää dynaamisen mallinnuksen käsitettä. Mietitkö, miksi sitä kutsutaan dynaamiseksi? Sitä kutsutaan dynaamiseksi, koska sillä on kyky sopeutua sisäisiin klusterin ominaisuuksiin automaattisesti arvioimalla klusterin samankaltaisuutta, ts. Kuinka hyvin datapisteet yhdistettiin klusterin sisällä ja klusterien läheisyydessä. Yksi kameleonin haitoista on, että prosessointikustannukset ovat liian korkeat (O (n 2 ) n kohteelle on pahimmassa tapauksessa ajan monimutkaisuus).
Kuvalähde - Google
johtopäätös
Tässä artikkelissa olemme oppineet, mikä klusteri on ja mikä on klusterianalyysi, erityyppiset hierarkkiset klusterointitekniikat, niiden edut ja haitat. Jokaisella keskustelumme tekniikalla on omat plussa ja miinuksensa, joten ennen algoritmin jatkamista meidän on ymmärrettävä tietomme asianmukaisella tutkivalla data-analyysillä ja valittava algoritmi varoen.
Suositellut artikkelit
Tämä on opas hierarkkiseen klusterointianalyysiin. Tässä keskustellaan yleiskatsauksesta, agglomeratiivisesta klusteroinnista, jakavasta klusteroinnista (DIANA) ja monivaiheisesta hierarkkisesta klusteroinnista. Voit myös katsoa seuraavia artikkeleita saadaksesi lisätietoja
- Hierarkkinen ryhmittely R: ssä
- Rypytysalgoritmi
- klusterit
- Klusterointimenetelmät
- Klusterointi koneoppimisessa
- Hierarkkinen ryhmittely | Agglomeratiivinen ja jakautuva klusterointi