Ülevaade hierarhilisest klastrianalüüsist

Enne kui asume hierarhilisest klastrianalüüsist aru saama, proovime kõigepealt mõista, mis on klaster? Ja mis on klastrianalüüs? Klaster on andmeobjektide kogum; klastri andmepunktid on üksteisega sarnasemad ja erinevad teise klastri andmepunktidest. Klastrianalüüs on põhimõtteliselt nende andmepunktide rühmitamine klastrisse. Klasterdamine on teatud tüüpi juhendamata masinõppe algoritm, kus puuduvad koolitusega märgistatud andmekogumid. Klastrianalüüsi on erinevat tüüpi, üks selline tüüp on Hierarhiline klastrimine.

Hierarhiline klasterdamine aitab klastrite loomisel õiges järjekorras / hierarhias. Näide: kõige tavalisem igapäevane näide, mida me näeme, on see, kuidas me oma arvutis olevad failid ja kaustad õige hierarhia järgi tellime.

Hierarhilise rühmituse tüübid

Hierarhiline klaster jagatakse täiendavalt kahte tüüpi, st aglomeratiivne klasterdamine ja jagatav klaster (DIANA)

Aglomeratiivne klasterdamine

Sellisel rühmitamise korral toimub hierarhiline lagundamine alt-üles strateegia abil, kus see algab aatomiliste (väikeste) klastrite loomisega, lisades ühe andmeobjekti korraga, ja liidab need seejärel kokku, moodustades lõpus suure klastri, kus see klaster vastab kõigile lõpetamistingimustele. See protseduur on korduv, kuni kõik andmepunktid koondatakse ühte suurde klastrisse.

AGNES (AGglomerative NESting) on ​​teatud tüüpi aglomeratiivne klasterdamine, mis ühendab andmeobjektid sarnasuse alusel klastriteks. Selle algoritmi tulemuseks on puupõhine struktureeritud nimi Dendrogram. Siin kasutab ta vahemaa mõõdikuid, et otsustada, millised andmepunktid tuleks millise klastriga ühendada. Põhimõtteliselt konstrueerib see kauguse maatriksi ja kontrollib väikseima vahemaaga klastrite paari ning ühendab need.

Ülaltoodud joonis näitab aglomeratiivseid ja jagatud rühmitusi

Selle põhjal, kuidas iga klastri vaheline kaugus mõõdetakse, võib meil olla 3 erinevat meetodit

  • Üksikühendus : kus igas klastris on kahe punkti vahel kõige lühem vahemaa klastrite vaheline kaugus.
  • Täielik seos : sel juhul arvestame klastrite vahekauguseks väikseimat vahemaad punktide vahel igas klastris.
  • Keskmine seotus: siin võtame ühe klastri iga punkti ja teise klastri teise punkti keskmise.

Nüüd arutame AGNESi tugevate ja nõrkade külgede üle; selle algoritmi ajaline keerukus on vähemalt O (n 2 ), seega ei lähe see skaleerimisega hästi, ja veel üheks oluliseks puuduseks on see, et mida iganes on tehtud, ei saa kunagi tagasi võtta, st kui rühmitame mis tahes klastri valesti algoritmi, siis ei saa me tulemust muuta ega seda muuta. Kuid sellel algoritmil on ka helge külg, kuna moodustatakse palju väiksemaid klastrid, see võib olla abiks avastamisprotsessis ja see annab objektide järjekorra, mis on visualiseerimisel väga kasulik.

Jagavad klastrid (DIANA)

Diana tähistab põhimõtteliselt lahusolevat analüüsi; see on teist tüüpi hierarhiline klasterdamine, kus põhimõtteliselt töötab see ülalt-alla lähenemise põhimõttel (AGNES-i pöördvõrdeline), kus algoritm algab suure klastri moodustamisega ja see jagab rekursiivselt kõige erinevama klastri kaheks ja jätkub, kuni me ' Kõik sarnased andmepunktid kuuluvad vastavatesse klastritesse. Need jagavad algoritmid annavad ülitäpse hierarhia kui aglomeratiivne lähenemisviis, kuid on arvutuslikult kallid.

Ülaltoodud joonisel on jagatud rühmitamine samm-sammult

Mitmefaasiline hierarhiline rühmitus

Ülalnimetatud hierarhiliste rühmitamistehnikate abil loodud klastrite kvaliteedi parandamiseks integreerime oma hierarhilised klastritehnikad teiste klastritehnikatega; seda nimetatakse mitmefaasiliseks rühmitamiseks. Mitmefaasilised rühmitused on erinevad:

  • BIRCH (tasakaalustatud iteratiivne redutseerimine ja klasterdamine hierarhiate abil)
  • ROCK (linkide abil rühmitamine RObustiga)
  • CHAMELEON

1. Tasakaalustatud iteratiivne redutseerimine ja klasterdamine hierarhiate abil

Seda meetodit kasutatakse peamiselt tohutu hulga numbriliste andmete rühmitamiseks, integreerides meie hierarhilise / mikroklastri algfaasis ja makrorühmituse / iteratiivse jaotuse hilisemas faasis. See meetod aitab üle saada mastaapsuse probleemist, millega me AGNESis kokku puutusime, ja võimetusest tühistada enne toimingut tehtud toimingud. BIRCH kasutab oma algoritmis kahte olulist mõistet

a. Klastrifunktsioon (aitab klastri kokku võtta)

CF on defineeritud kui (n - klastris olevate andmepunktide arv, n-punkti lineaarne summa, n-punkti ruudusumma). Klastri funktsiooni sellisel viisil hoidmine aitab vältida selle kohta üksikasjaliku teabe salvestamist ning CF on olemuselt erinevate klastrite jaoks aditiivne.

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

b. Klastrifunktsioonide puu (aitab klastrit esindada hierarhiana)

CF-puu on tasakaalustatud puu, millel on harutegur B (maksimaalne laste arv) ja lävega T (maksimaalne alamklastrite arv, mida saab lehesõlmedesse hoida).

Algoritm töötab põhimõtteliselt kahes faasis; 1. faasis skannib andmebaasi ja ehitab mällu CF-puu ning 2. faasis kasutab klasterdamisalgoritmi, mis aitab lehe sõlmede rühmitamisel eemaldada välimised väärtused (hõredad klastrid) ja rühmitada klastri maksimaalse tihedusega. Selle algoritmi ainus puudus on see, et see käitleb ainult numbrilisi andmetüüpe.

2. Tugev rühmitamine, kasutades linke

Link on määratletud kui ühiste naabrite arv kahe objekti vahel. ROCK algoritm on teatud tüüpi klasterdamisalgoritm, mis kasutab seda kategoorilise andmestikuga lingi kontseptsiooni. Kuna me teame, et kaugusega mõõdetud rühmitamise algoritmid ei anna kategoorilise andmestiku jaoks kvaliteetseid klastrid, kuid ROCK puhul arvestab see ka andmepunktide naabruskondadega, st kui kahel andmepunktil on sama naabruskond, siis nad on tõenäoliselt kuuluvad samasse klastrisse. Algoritm konstrueerib esimeses etapis hõreda graafiku, võttes arvesse sarnasuse maatriksit naabruskonna ja sarnasuse läve mõistega. Teises etapis kasutab see hõredal graafil asuvat aglomeratiivset hierarhilist rühmitustehnikat.

3. kameeleon

Seda tüüpi hierarhilise rühmituse algoritm kasutab dünaamilise modelleerimise kontseptsiooni. Huvitav, miks seda nimetatakse dünaamiliseks? Seda nimetatakse dünaamiliseks, kuna sellel on võime klastri sisemiste karakteristikutega automaatselt kohaneda, hinnates klastri sarnasust, st seda, kui hästi on andmepunktid klastris omavahel ühendatud ja klastrite läheduses. Üks kameeleoni puudusi on see, et töötlemiskulud on liiga suured (n objekti jaoks on O (n 2 ) halvim aeg).

Kujutise allikas - Google

Järeldus

Selles artiklis oleme õppinud, mis on klaster ja mis on klastrianalüüs, eri tüüpi hierarhilised klastritehnikad, nende eelised ja puudused. Igal meie arutatud tehnikal on oma plussid ja miinused, seega peame enne algoritmi väljatöötamist mõistma oma andmeid korraliku uuritava andmete analüüsiga ja valima algoritmi ettevaatlikult.

Soovitatavad artiklid

See on hierarhilise klastrianalüüsi juhend. Siin käsitleme ülevaadet, aglomeratiivset klastrit, jagavat klastrit (DIANA) ja mitmefaasilist hierarhilist klastrimist. Lisateabe saamiseks võite vaadata ka järgmisi artikleid

  1. Hierarhiline rühmitus R-s
  2. Klasterdamisalgoritm
  3. klastrid
  4. Klastrimismeetodid
  5. Klastrid masinõppes
  6. Hierarhiline rühmitus | Aglomeratiivne ja lõhestav klasterdamine

Kategooria:

Suured andmed