Gručenje

Drugi del: Razlaga gruč, silhuete, metoda voditeljev

To interaktivno učno gradivo je del spremljevalnega gradiva za strokovno usposabljanje Podatkovna analitika in odkrivanje skupin v podatkih, ki ponuja sklop znanj in veščin za kompetenčni profil Podatkovni analitik (EQF 6), razvit v sklopu evropskega projekta ARISA. Zapiski pokrivajo ključne koncepte in pristope raziskovalne analize podatkov, strojnega učenja in vizualne analitike. Na strokovnem usposabljanju boste skozi praktično delo spoznali, kako z vizualnim programiranjem in uporabo orodja Orange odkrivati vzorce in pridobiti vpogled v podatke s pomočjo metod podatkovnega rudarjenja.

Gradivo sta pripravila Blaž Zupan in Janez Demšar. Ajda Pretnar Žagar in Erika Funa sta gradivo prevedli v slovenščino. Cenimo vso pomoč članov Laboratorija za bioinformatiko na Univerzi v Ljubljani, Slovenija.

Gradivo je na voljo pod licenco Creative Commons CC BY-NC-ND.

Obravnavani koncepti

V tem poglavju bomo obravnavali naslednje koncepte s področja gručenja podatkov:

Razlaga gruč – Ko so podatki združeni v gruče, je ključno razložiti pomen nastalih skupin tako, da določimo, katere značilke najbolj prispevajo k oblikovanju gruč. To lahko dosežemo z razvrščanjem značilk glede na razlike v njihovih porazdelitvah med gručami. Velikokrat za številske značilke uporabimo t-statistiko in mero ANOVA, za kategorične pa test hi-kvadrat.
Prostorska interpretacija gručenja – Uporaba kart za vizualizacijo razporeditve gruč glede na lokacijo in odkrivanje prostorskih vzorcev. Pri tem pristopu razlago gručenja podpremo s prostorskimi informacijami. Interpretacija gruč pogosto vključuje zunanje podatke.
Uporaba domenskega znanja pri gručenju – V praksi je treba rezultate gručenja preveriti z domenskim znanjem. Pri gručenju (živali ali držav) je, na primer, ključno, da gruče interpretiramo na podlagi resničnih značilnosti, da dobimo smiselne vpoglede.
Wardova metoda povezovanja – Hierarhična metoda gručenja, ki minimizira varianco znotraj gruč pri združevanju, kar pogosto vodi do bolj kompaktnih in smiselnih gruč. Poznamo tudi druge metode povezovanja, povprečno, enojno in popolno povezavo.
Silhuetni koeficient – Metoda za ocenjevanje kakovosti gručenja, ki primerja podobnost znotraj gruče (kako blizu so si točke v gruči) z ločenostjo med gručami (kako daleč so od točk v drugih gručah). Vrednosti segajo od -1 (slabo gručenje) do 1 (dobro definirane gruče). Silhuetni koeficient se izračuna za vsako podatkovno točko, končna ocena za celoten nabor podatkov pa je povprečje vseh posameznih vrednosti.
Osamelci in predstavniki v gručenju – Nekatere podatkovne točke se dobro ujemajo z gručo (predstavniki), druge pa so bližje drugim gručam ali sploh ne pripadajo nobeni (osamelci). Odkrivanje odstopajočih vrednosti lahko temelji na silhuetnem koeficientu.
Metoda k-voditeljev za gručenje – Iterativna metoda gručenja na podlagi centroidov, ki razdeli podatke v k gruč tako, da izmenično dodeljuje točke najbližji gruči in posodablja centre gruč.
Izbira optimalnega števila gruč (k) – Namesto da vnaprej določimo k, lahko uporabimo silhuetni koeficient, da ugotovimo optimalno število gruč za tehnike, kot je metoda voditeljev. Ta pristop je uporaben tudi pri drugih metodah gručenja, vključno s hierarhičnim gručenjem, za določitev smiselnega števila gruč.
Inicializacija k-means++ – Tehnika za izboljšano izbiro začetnih centrov gruč, ki zmanjšuje možnost ujetja v lokalne optimume in pospeši konvergenco algoritma.
Lokalni in globalni optimum – Lokalni optimum je rešitev, ki je optimalna znotraj določenega območja, vendar ni najboljša možna rešitev na splošno. Globalni optimum je absolutno najboljša rešitev v celotnem prostoru iskanja. Pri gručenju lahko algoritmi, kot je metoda voditeljev, konvergirajo k lokalnemu optimumu, kar pomeni, da najdejo dobro, a ne nujno optimalno razporeditev podatkovnih točk. Za izboljšanje rezultatov lahko izvedemo več ponovitev z različnimi začetnimi pogoji ali uporabimo naprednejše metode inicializacije (npr. k-means++).
Pomanjkljivosti metode voditeljev – Ta metoda bo vedno našla gruče, tudi če v podatkih dejanske gručenosti ni. Slabo se obnese pri nekonveksnih oblikah, različno velikih gručah in podatkih z neenakomerno gostoto.

Chapters

Chapter 1: Zemljevidi

Nekaj poglavij nazaj smo si že ogledali podatke o indeksu človeškega razvoja (HDI). Zdaj pa poglejmo, ali nam gručenje teh podatkov razkrije kaj novega ali zanimivega. Skupine držav, ki jih najdemo z gručenjem, bomo poskusili prikazati na zemljevidu sveta.

Orange vključuje dodatek Geo, ki ga moramo najprej namestiti. Dodatke najdemo v meniju Options in Add-ons, kjer izberemo možnost Geo. Ko kliknemo na OK, se dodatek namesti, Orange pa se ponovno zažene.

V orodni vrstici imamo zdaj novo skupino gradnikov: Geo.

Podatke o indeksu človeškega razvoja naložimo z gradnikom Datasets – v iskalno vrstico lahko preprosto vpišemo hdi. Z dvoklikom na ustrezno vrstico podatke naložimo. Preden nadaljujemo, jih najprej pregledamo v gradniku Data Table.

Ti podatki vključujejo 188 držav, opisanih z 52 družbeno-ekonomskimi kazalniki. Za iskanje zanimivih skupin držav bomo najprej izračunali razdalje med pari držav. Uporabili bomo gradnik Distances, kjer izberemo Evklidsko razdaljo in poskrbimo, da so značilke normalizirane. Ker imajo kazalniki zelo različne vrednostne razpone, je normalizacija nujna za primerljivost.

Za hierarhično gručenje dodamo gradnik Hierarchical Clustering. Izberemo Wardovo metodo povezovanja (Ward linkage) in veje dendrograma označimo z imeni držav. Wardova metoda povezuje gruče tako, da zmanjšuje varianco znotraj gruč, in pogosto ustvari dendrograme z bolj razločno strukturo.

Rezultat gručenja je zanimiv: nekatere afriške države, kot so Eswatini, Lesoto in Bocvana, so v isti gruči. Islandija, Norveška in Švedska so združene skupaj. Tudi nekatere države nekdanje Sovjetske zveze tvorijo svojo skupino. Poskusite poiskati te gruče v dendrogramu! Če dendrogram odzumiramo, lahko poiščemo rez, ki države razdeli v štiri gruče.

Poglejmo zdaj te štiri gruče na zemljevidu sveta. Najprej na izhod Hierarchical Clustering priključimo gradnik Geocoding, ki samodejno uporabi ime države kot identifikator. Z dodatkom Data Table lahko preverimo, da zdaj vsaka vrstica vsebuje oznako gruč, pridobljeno s hierarhičnim gručenjem, ter zemljepisno širino in dolžino, ki ju doda Geocoding.

Te podatke nato posredujemo gradniku Choropleth Map. Kot spremenljivko za vizualizacijo izberemo Cluster, združevanje nastavimo na Mode. Poskrbimo, da se Latitude in Longitude bereta iz istoimenskih spremenljivk in da je Detail nastavljen na najnižjo raven.

In tukaj so – gruče držav sveta na zemljevidu!

Zanimivo! Države, ki jih običajno štejemo za razvite, so v isti gruči. Države Južne Amerike so skupaj z nekaterimi azijskimi državami, medtem ko najdemo pas podsaharske Afrike v drugi gruči.

Fascinantno je, da podatki niso vsebovali nobene geolokacijske informacije, pa so gruče, ki smo jih našli, kljub temu povezane z geografskim položajem držav. Naš svet je res razdeljen v regije, med katerimi so velike razlike.

Smo rekli "razlike"? Doslej avtorji tega besedila nismo kaj dosti pojasnili, kaj te gruče sploh so. Katere družbeno-ekonomske spremenljivke so značilne za posamezne gruče? So nekateri kazalniki bolj značilni za posamezne gruče kot drugi? Kateri kazalniki najbolje opišejo gruče?

Toliko vprašanj. Čas je, da se poglobimo v razlago gručenja.

Chapter 2: Razlaga gruč

Hierarhično gručenje, tema prejšnjih poglavij, je enostavna in učinkovita metoda za iskanje skupin v podatkih. Oglejmo si, kaj smo se naučili na primeru šolskih ocen. Podatki vključujejo 16 študentov in 7 predmetov. Izračunali smo evklidske razdalje med pari študentov in nato gruče ustvarili z metodo povezovanja. Uporabimo Wardovo metodo minimalne variance, ki povezuje gruče tako, da so točke v nastali gruči čim bližje središču. Ideja te metode je, da so točke znotraj gruče čim bolj skupaj.

Spodaj je delotok in rezultat gručenja:

Naš problem tokrat ni algoritem za gručenje, ampak kako interpretirati strukturo gručenja. Zakaj so Phill, Bill in Lea v isti gruči? Kaj imajo skupnega?

Gradnik Hierarchical Clustering oddaja dva signala: izbrane podatke in celoten nabor podatkov, ki vključuje dodaten stolpec s podatkom o izboru. Poglejmo najprej gradnik Data Table. Izberemo gručo s Phillom, Billom in Leo, nato pa ponovno povežemo Hierarchical Clustering z Data Table tako, da se prenese celoten nabor podatkov. V Data Table se zdaj pojavi stolpec Selected, ki označuje, kateri študenti so bili izbrani v gručenju. Med izbranimi so Phill, Bill in Lea.

Zdaj želimo ugotoviti, kateri predmeti ločijo izbrane študente od ostalih. Nekaj podobnega smo že naredili v poglavju o porazdelitvi podatkov, kjer smo želeli ugotoviti, kateri družbeno-ekonomski dejavniki vplivajo na dolgoživost. Ključni gradnik tam je bil Box Plot.

Dodajmo torej Box Plot na izhod gradnika Hierarchical Clustering in ponovno povežimo signal, da se prenese celoten nabor podatkov. V Box Plot nastavimo "Selected" kot lastnost za podskupine (Subgroup) in označimo Order by relevance to subgroups.

Na vrhu seznama spremenljivk najdemo zgodovino, angleščino in francoščino. Oglejmo si podrobneje predmet zgodovina. Phill, George in ostali iz skupine imajo povprečje 74, vsi ostali pa zgolj 19. V angleščini je povprečje gruče še višje – 92, v primerjavi z 32 pri ostalih. Podobno velja tudi za francoščino.

Izbrana gruča študentov je torej zelo dobra v družboslovnih predmetih. Kaj pa skupina, ki vključuje Freda, Nasha in Katherine? Njihove ocene iz zgodovine so slabe – komaj 16, a v matematiki dosegajo povprečno oceno 83, poleg tega so boljši od ostalih tudi v fiziki. Zdi se, da gre za navdušence nad naravoslovjem.

Preostala je še ena gruča – Ana in Henry. Njuna posebnost? Šport.

S kombinacijo Hierarchical Clustering + Box Plot lahko raziščemo vsako gručo ali podgručo v podatkih. Klik na vejo dendrograma posodobi Box Plot, ki s svojim urejenim seznamom lastnosti pomaga opisati gručo.

Box Plot uporablja Studentov t-test, da uredi lastnosti glede na razliko med porazdelitvijo znotraj gruče in izven nje. Na primer: lastnost, ki najbolje loči trenutno izbrano gručo, je biologija, s t-statistiko 5.2.

Razlaga gruč z Orangeovim Box Plotom je preprosta. Presenetilo nas je, kako enostavno je bilo opisati skupine dijakov v podatkih. Enak delotok bi lahko uporabili tudi za druge podatkovne nabore in gručenja – na primer za opredelitev skupin držav v naših družbeno-ekonomskih podatkih.

A to nalogo prepuščamo vam. 😉

Chapter 3: Silhuete

Niso vsi podatki enaki. Nekateri so bolj zgoščeni, drugi izstopajo. Nekateri so tipični primeri (angl. inliers), drugi odstopajo (outliers). Poglejmo si te pojme v kontekstu gručenja in ustvarimo podatkovni nabor s tremi gručami: modro, rdečo in zeleno, ki je nekoliko odmaknjena. Uporabili bomo gradnik Paint Data.

Podatki v zeleni gruči so bolje ločeni od drugih dveh. Pri modri in rdeči pa se več točk nahaja na meji med gručama. Želimo kvantitativno oceniti, kako dobro posamezna točka pripada svoji gruči.

Povprečno medskupinsko razdaljo A izračunamo kot povprečje razdalj do točk v isti gruči.

Za to bomo uvedli t.i. oceno silhuete. Naš cilj: silhueta 1 pomeni, da je podatkovna točka trdno umeščena v svojo gručo. Če pa je silhueta 0, točka leži na meji med gručama.

Za dano podatkovno točko (recimo modro točko na sliki levo) izračunamo razdalje do vseh drugih točk v isti gruči in izračunamo povprečno razdaljo. To označimo z A. Manjši kot je A, bolje je, saj to nakazuje zgoščeno gručo.

Po drugi strani želimo, da je ta točka daleč od druge najbližje gruče (recimo rdeče). Izračunamo razdalje do vseh točk v tej sosednji gruči in ponovno vzamemo povprečje. To označimo z B. Večji kot je B, bolje je.

Točka je torej dobro umeščena v svojo gručo, če je B precej večji od A. Izračunamo razliko B − A in jo normaliziramo z večjo od obeh vrednosti:

$S = \frac{B - A}{\max \{A, B\}}$

Voilà, S je silhuetna ocena.

Povprečno medskupinsko razdaljo B izračunamo kot povprečje razdalj do točk v drugi najbližji gruči.

Orange ima gradnik Silhouette Plot, ki prikazuje vrednosti silhuetne ocene za vsako podatkovno točko. Silhouette Plot predpostavlja, da podatki že vključujejo lastnost, ki označuje pripadnost gruči – v našem primeru se imenuje Class.

V prikazu silhuet lahko izberemo posamezno točko in preverimo njen položaj v razsevnem diagramu. Spodaj smo izbrali tri točke – po eno iz vsake gruče – ki imajo najslabše silhuetne ocene, in jih v Orangeu prikazali na razsevnem diagramu.

Računanje silhuet in vizualizacija tipičnih primerov in osamelcev je smiselna pri podatkih z dvema spremenljivkama, kjer rasevni diagram pokaže celotno informacijo. Pri večdimenzionalnih podatkih (recimo z več tisoč izrazi genov) pa razsevni diagram prikaže le dve dimenziji hkrati, zato lahko točki, ki se zdita blizu, v resnici nista.

Za primer večdimenzionalnih podatkov poglejmo živalske podatke (Zoo) iz gradnika Datasets. Kateri so trije sesalci, ki najbolj izstopajo? Zakaj? Zakaj imajo nekatere živali v tem naboru negativne silhuete? Kaj to pomeni?

Chapter 4: Metoda voditeljev (k-means)

Hierarhično gručenje ni primerno za večje podatkovne nize zaradi velikosti matrike razdalj: pri 30.000 primerih bi ta matrika vsebovala skoraj milijardo elementov. Če shranjujemo decimalke, ki zavzamejo po 32 bitov, bi za tako matriko potrebovali kar 32 TB delovnega pomnilnika! Alternativa, ki se temu izogne, je metoda voditeljev (k-means).

Vidimo, da kvadratna matrika razdalj, potrebna pri hierarhičnem gručenju, tukaj odpade. Namesto tega hranimo matriko razdalj med vsemi točkami in k središči. Ker je k majhen, taka matrika zlahka ostane v pomnilniku.

Postopek metode voditeljev najprej naključno izbere k središč (število k določimo vnaprej). Nato algoritem izmenično ponavlja dva koraka:

Vsako točko pripiše najbližjemu središču (nastane k gruč).
Ponovno izračuna središča glede na pripisane točke.

Ta dva koraka se ponavljata, dokler algoritem ne konvergira. Tudi pri zelo velikih podatkovnih nizih običajno zadostuje nekaj deset ali sto iteracij.

V Orangeu lahko ta algoritem ponazorimo z izobraževalnim gradnikom Interactive k-Means. Eksperimentiranje omogoča gradnik Paint Data, kjer lahko narišemo, na primer, pet skupin točk. Gradnik začne s tremi središči, dodajamo jih lahko s klikom na graf in odstranjujemo pa s ponovnim klikom.

Metodo voditeljev zaženemo s pritiskom na tipko Enter ali gumb Recompute Centroids and Reassign Membership. Opazimo lahko njeno hitro konvergenco. Rezultat gručenja za zgoraj narisane podatke je prikazan spodaj.

Zdaj pa poskusimo večkrat ponovno zagnati algoritem z novimi naključnimi začetnimi središči. Opazujmo, kako središča "zasedajo teritorij". Zabavno, kajne?

V dvodimenzionalnih podatkih zadostuje le nekaj iteracij. Pri več dimenzijah in točkah postopek traja dlje, a načelo ostaja enako.

Kako določimo število gruč k? Preprosto: izberemo tisto, ki da najboljšo razporeditev. A kaj pomeni "najboljša"? Želimo majhne razdalje znotraj gruče in velike razdalje med gručami. Hja, to že vemo: iščemo gručenje z visokimi silhuetnimi ocenami. Z drugimi besedami: za dano gručenje izračunamo povprečno silhueto vseh točk. Višja kot je, boljše je gručenje.

Ko znamo oceniti kakovost gručenja, lahko metodo voditeljev poženemo z različnimi vrednostmi k (število gruč) in izberemo tisti k, ki ima najvišjo povprečno silhueto. Tokrat se poslovimo od izobraževalnega gradnika in povežemo Paint Data z gradnikom k-Means. Iskanje optimalnega k nastavimo med 2 in 8 glede na silhueto.

Deluje kot čarovnija.

Razen, kadar ne. Obstaja namreč nekaj težav:

Rezultat metode voditeljev je močno odvisen od začetne izbire središč. Če imamo smolo, lahko algoritem obtiči v lokalnem optimumu. To rešimo tako, da algoritem večkrat poženemo z različnimi začetnimi pogoji in izberemo najboljši rezultat. Ali pa začetna središča izberemo tako, da so točke čim bolj narazen. Ali pa rahlo naključno – in postopek ponovimo desetkrat. Ta pristop se imenuje KMeans++, in ga uporablja Orange.
Silhueta ni popolna: včasih gručenja ne oceni pravilno. Noben ocenjevalnik ni idealen.
Metoda voditeljev bo vedno našla gruče, tudi če jih v podatkih ni.

Čas je za eksperimentiranje: uporabimo gradnik Paint Data, podatke pošljemo v k-Means z avtomatskim določanjem k in dodamo Scatter Plot. Spreminjajmo število gruč. So gruče smiselne? Ali lahko narišemo podatke, kjer metoda voditeljev odpove? Ali kjer deluje odlično?

Chapter 5: Metoda voditeljev na podatkih o živalih

V tej lekciji ni veliko novega. Le sestavljamo gradnike, ki smo jih že spoznali, in z njimi sestavimo nov delotok. A prav je, da se ozremo nazaj in se zavemo, koliko smo se že naučili.

Naša naloga bo uporabiti podatkovni niz o živalih (Zoo), najti gruče in ugotoviti, kaj predstavljajo. Podatke dobimo iz gradnika Datasets. Vključujejo 100 živali, opisanih s 16 značilnostmi. V podatkih so tudi imena živali in tip živali, ki je shranjen v stolpcu class.

Za trenutek se bomo pretvarjali, da ne vemo, kateri tip živali pripada kateri vrstici, zato bomo stolpec type odstranili z gradnikom Select Columns.

Gradnik k-Means nam sporoča, da obstaja štiri ali pet gruč – razlike v silhuetni oceni med tema vrednostma k pa so zelo majhne. Sedaj poskusimo ugotoviti, katere vrste živali so v kateri gruči in po katerih značilnostih se ločijo.

Gruče bi lahko analizirali s pomočjo Select Rows, a raje bomo uporabili Box Plot – enega za izbiro gruče, drugega za njeno analizo in karakterizacijo.

Gradnik k-Means doda stolpec, ki za vsak primer v podatkih pove, kateri gruči pripada. Ta stolpec se imenuje Cluster. Box Plot prikaže število primerov v vsaki gruči in omogoča prikaz po posameznih vrsticah, razvrščenih po istem stolpcu Cluster:

Ta prvi Box Plot bomo uporabili za izbiro gruče. Kliknemo na enega od štirih stolpcev (štiri gruče smo nastavili v gradniku k-Means), in Box Plot odpošlje podatke, ki pripadajo izbrani gruči. A nas ne zanima le izbrani del, temveč bomo v naslednji Box Plot poslali celoten podatkovni niz.

Ne pozabimo ustrezno povezati obeh Box Plotov! Ko drugi Box Plot dobi celoten niz, bo dodal stolpec Selected, ki označuje, ali posamezna vrstica pripada izbrani gruči. Delotok izgleda tako:

Zdaj pa k zabavnemu delu! Izberemo prvo gručo in ugotovimo, da so zanjo najbolj značilne lastnosti mleko, dlaka in jajca. Vse živali v tej gruči torej dajejo mleko, imajo dlako in ne ležejo jajc. Seveda – sesalci!

V drugi (rdeči) gruči imajo živali plavuti, so brez nog in živijo v vodi. Ribe. A tu so tudi živali s štirimi nogami in brez plavuti – torej je ta gruča mešana.

Tretja gruča je bolj jasna: živali imajo perje in dve nogi. Ptice.

V četrti gruči so živali brez hrbtenice in brez repa. Ta gruča je nekoliko bolj zahtevna, a po premisleku ugotovimo, da gre verjetno za žuželke ali nevretenčarje.

Na tej točki lahko naredimo še veliko zanimivih stvari. Tukaj je nekaj idej:

Povežimo izhod zadnjega Box Plota z gradnikom Data Table in preverimo, katere živali imajo določene lastnosti – torej, kako se imenujejo.
Preverimo odstopajoče primere. Na primer: dve živali dajeta mleko, a nista v gruči sesalcev. Kateri živali sta to?
Vrnimo se nazaj na Select Columns, stolpec type prestavimo med meta lastnosti in preverimo porazdelitev tipov živali v izbrani gruči.