Gručenje

Imamo nekaj reči (objektov, ljudi, besedil, besed ... česarkoli) in radi bi jih razdelili v skupine - tako, da bodo podobni v isti skupini in da si bodo skupine med seboj različne.

Načinov, kako to početi, je več, najpogostejša sta dva, za naše potrebe pa bo najbrž prikladen predvsem eden. Imenuje se hierarhično gručenje.

Ilustracija hierarhičnega gručenja

Za začetek predpostavimo - kasneje pa se bomo naučili narediti tudi drugače -, da je vsaka reč opisana z nekimi spremenljivkami.

Recimo, da smo učence Ano, Berto, Cilko, Danija, Emo, Franca in Gorazda prosili, da na lestvici od 0 do 100 ocenijo, kako so jim všeč akcijski filmi in romantične komedije. Rezultati so bili takšni:

ime     akcija    romantika
Ana     10        90
Berta   15        85
Cilka   10        35
Dani    100       30
Ema     15        25
Franc   80        15
Gorazd  30        30

Očitno je, da (smo si podatke izmislili tako, da) imamo tri skupine. Kako pa bi jih našli avtomatsko, z nekim postopkom, ki bo deloval tudi, ko bo podatkov več, predvsem pa bodo opisani z več spremenljivkami (recimo, da vsak učenec oceni pet žanrov) in jih ne bo mogoče kar tako narisati in pogledati?

Takole lahko naredimo.

  • Najprej rečemo, da imamo toliko skupin, kolikor je učencev, se pravi sedem.
  • Potem najdemo najbolj podoben par (ali skupino). To sta Ana in Berta. Združimo ju v eno skupino. Tako imamo še šest skupin.
  • Nato poiščemo drugi najbolj podoben par. To sta Cilka in Ema. Združimo ju; ostalo je še pet skupin (Ana-Berta, Cilka-Ema, Gorazd, Franc in Dani).
  • Spet poiščemo najbolj podoben par. To je zdaj skupina Cilka-Ema in Gorazd. Združimo ju v isto skupino. Zdaj imamo torej štiri skupine.
  • V naslednjem koraku združimo v skupino Danija in Franca. Ostale so še tri skupine.
  • Postopek se nadaljuje: kateri par izmed treh skupin (Ana-Berta, Cilka-Ema-Goraz in Dani-Franc) si je najbolj podoben? Takole, na oko, sta si bližji prvi dve skupini - čeprav se bomo morali o tem kasneje še malo pogovoriti.
  • Ostaneta še dve skupini. Združimo ju v eno samo.

Tako naj je postopek dal, ekhm, eno samo skupino. To zveni nesmiselno, ampak ni. Potrpite.

Takšno razporejanje v skupine znamo narisati. (Učeno temu rečemo: dendrogram.)

Dolžine črt v dendrogramu ustrezajo razdaljam: daljša ko je črta, bolj oddaljeni sta si bili skupini. Ko pogledamo takšen dendrogram vidimo, da so si skupine med seboj najprej podobne, potem pa se razdalje povečujejo. Združevanje bi bilo najbolj pametno prekiniti v točke, ko se začnejo razdalje drastično povečevati. Kje je to, se najlepše odločimo kar ročno.

Tehnični detajli

Različne razdalje

Tule je preprosta razlaga. Nekaj več o razdaljah pa v ločenem besedilu.

Kako izračunamo razdaljo med objekti, ki jih gručimo? Tule je bilo preprosto: imamo sliko, izmerimo. Na ta način smo računali evklidsko razdaljo. Če hočete majčkeno bolj po domače, po Pitagori. Ko opazujemo dve točki, si lahko predstavljamo pravokotni trikotnik: črta med točkama je njegova hipotenuza, kateti pa sta razdalji v vodoravni in navpični smeri. Pitagora nas uči, da bomo dolžino hipotenuze dobili kot koren vsote kvadratov dolžin katet. Da ne bi koga prehitro preplašili z matematiko, izračunajmo razdaljo med Francem in Danijem.

Franc   80        15
Dani    100       30

Po všečnosti akcijskih filmov se razlikujeta za 20, po romantiki pa za 15. Razdalja med njima (v grafu) je enaka \(\sqrt{20^2 + 15^2} = \sqrt{400 + 225} = \sqrt{625} = 25\).

Če bi učenci ocenjevali všečnost petih žanrov, bi računali enako, le da bi seštevali kvadrate petih razlik. (Še vedno računamo kvadrate in kvadratni koren, ne, morebiti, peti koren!)

Poleg evklidske obstajajo tudi druge razdalje. Zelo preprosta je Manhattanska. Ta si predstavlja, da med točkama ne moremo iti naravnost, ker smo v Manhattnu in nimamo helikopterja, pač pa moramo iti po avenijah in ulicah. Kakorkoli si izberemo pot po mreži, razdalja bo preprosto vsota (absolutnih vrednosti) razlik. Razdalja med Francem in Danijem bo preprosto 20 + 15.

Še ena razdalja, ki nam bo prišla kdaj prav, je kosinusna. Ta je nenavadna: ne zanima je, kako daleč so točke, temveč pod kakšnim kotom bi dve točki videl nekdo, ki bi stal v izhodišču, se pravi v točki (0, 0). Dve točki sta si tem bolj oddaljeni, čim večji je kot med njima. Z vidika kosinusne razdalje sta si, če za izhodiče izberemo Maribor, Velenje in Ljubljana čisto blizu, ker sta v isti smer, Ptuj in Slovenska Bistrica pa sta si daleč, ker je kot med njima (gledano iz Maribora), skoraj 90 stopinj.

Kosinusna razdalja je videti čudno, v resnici pa ima lepe matematične lastnosti in se po določenimi pogoji pravzaprav vede enako kot evklidska, "zračna" razdalja. Oziroma, še huje: tako kot bi želeli, da se vede evklidska.

Še ena zanimiva razdalja: recimo, da se ne bi omejili na žanre, temveč bi vsakemu učencu naročili, naj napiše nekaj svojih najljubših filmov. Eni bi napisali tri, eni bi jih napisali dvajset. Kako bi v takšnem primeru izračunali različnost (ali pa podobnost) med dvema učencema? (Tule delamo še en korak naprej, saj objektov nimamo opisanih s spremenljivkami, temveč drugače - v tem primeru je vsakemu objektu prirejena neka množica filmov.)

Dva sta si očitno podobna tem bolj, čim več istih filmov sta izbrala. Po drugi strani pa se lahko zgodi, da bosta dva napisala po dvajset filmov in bodo skupni samo trije, dva pa bosta napisala samo dva filma -- vendar ista dva. Torej moramo do podobnost, "število skupnih filmov" še nekako normirati. Preprosto: delimo jo s številom vseh filmov, ki sta jih napisala -- eden ali drugi ali oba. Če je \(\mathcal{A}\) množica vseh filmov, ki so všeč Ani in \(\mathcal{B}\) množica filmov, ki so všeč Berti, je podobnost med Ano in Berto enaka

\[ \frac{\mathcal{A} \cap \mathcal{B}}{\mathcal{A} \cup \mathcal{B} } \]

Ker za algoritem potrebujemo razdaljo, različnost, tole reč preprosto odštejemo od 1. "Razdalja" med Ano in Berto je

\[ 1 - \frac{\mathcal{A} \cap \mathcal{B}}{\mathcal{A} \cup \mathcal{B} } \]

To razdaljo sem si izmislil jaz in jo uporabil v svojem magisteriju. Mimogrede sem žal izvedel, da nisem prvi, zato je na Wikipediji ne boste našli pod geslom Demšarjeva razdalja temveč, Jaccardov indeks. Možakar me je prehitel za sto let. Nisem imel šans.

Normiranje

Še en detajlček: če je ena od spremenljivk teža v kilogramih, druga pa višina v metrih, bomo pri računanju razdalje upoštevali praktično samo prvo, saj so razlike v višini (v metrih) zanemarljive v primerjavi z razlikami v teži kilogramih. To očitno ni dobro: vse spremenljivke morajo biti na isti lestvici. Zato jih običajno normiramo, recimo tako, da jih stisnemo v interval med 0 in 1. Odštejemo najmanjšo težo in delimo z razliko med težo najtežjega in najlažjega, recimo.

Neštevilske spremenljivke

Včasih so reči opisane s kategorijami. Če mora vsak učenec napisati svoj najljubši predmet, potem rečemo, da je razdalja med matematiko in slovenščino enaka 1, prav tako med slovenščino in angleščino in prav tako med matematiko in fiziko. Če ima Ana rada telovadbo, Berta pa likovni, bo ta spremenljivka k razdalji med njima prispevala 1. Če imata obe radi telovadbo pa, seveda, 0.

Če znamo na kakšen pameten način izračunati dejansko različnost med predmeti (matematika je vseeno bolj podobna fiziki kot nemščini, da o francoščini ne govorimo), lahko to seveda upoštevamo. Ampak običajno ne kompliciramo.

Razdalje med skupinami

Kako določimo razdaljo med dvema skupinama? Ko smo ocenili, da sta si med tremi preostalimi skupinami učencev glede na všečnost filmov najbližji skupini Ana-Berta in Cilka-Ema-Gorazd, sem nakazal, da se imamo o tem še nekaj pogovoriti.

Vzemimo tole sliko. Kateri skupini sta si bližji: modra in rdeča ali rdeča in zelena.

Na prvo žogo: razdalja med modro in rdečo je manjša. Po drugi strani pa je že "sredina" modre gruče od rdeče oddaljena, uh, več kot sta si med seboj najbolj oddaljena elementa rdeče in zelene.

Imamo vsaj tri možnosti, kako računati razdaljo med skupinami.

  • Opazujemo razdaljo med najbližjima elementoma (single linkage). Kakorkoli logično to zveni: navadno ne deluje dobro, saj vodi v dooooolge, razpotegnjene gruče, ki se lahko vijejo čez cel teritorij.
  • Opazujemo razdaljo med najbolj oddaljenima elementoma (complete linkage). Tudi ne deluje dobro. To zna razsekati čisto lepo gručo na dva dela, če je prevelika.
  • Opazujemo poprečno razdaljo med pari elementov iz dveh gruč (average linkage). To je navadno OK.
  • Wardova metoda: ta deluje nekoliko drugače in sicer minimizira varianco (razpršenost) gruč.

Navadno je najboljša četrta izmed teh treh. Pri njej običajno v nekem koraku pride do izrazitega povečanja razdalj med gručami -- seveda, če so podatki dejansko gručasti.

Več o tem si lahko preberete [na Wikipediji])https://en.wikipedia.org/wiki/Hierarchical_clustering#Linkage_criteria).

V praksi pa: uporabite Average ali Ward in poglejte, ali dobite lepo sliko, na kateri se jasno vidi, koliko gruč imamo.