Klusterointimenetelmät

Luokittelumenetelmät yrittävät luokitella annetun datan jonkun ennalta määritellyn luokan alle kun taas klusterointimenetelmät pyrkivät ryhmittelemään annetun datan eri ryhmiin. Luokittelumenetelmien toiminta perustuu siihen että annetusta datasta pyritään muodostamaan malli jonka perusteella ominaisuusavaruuden pisteet voidaan luokitella eri luokkiin kun taas klusterointimenetelmät yrittävät löytää syötetyn datan ominaisuusa-varuudesta luonnollisia ryhmiä sekä yhteyksiä ja muodostaa ryhmiä niiden perusteella.

Menetelmien vertailu oppimistuloksien ennakoinnin kontekstissa

Algoritmi Edut Haitat

K-lähin naapuri Yksinkertainen ja soveltuu erilai-siin ongelmiin hyvin. Helppo ym-märtää.

Käyttää paljon muistia. Ongelmas-ta riippuen kallis koska päätöksen perusteena voidaan käyttää kaikkea koulutusdataa. Tästä johtuen myös hidas, koska IO-operaatioita voi ol-la todelol-la paljon. Väärä etäisyysva-linta voi johtaa tuloksien virheelli-syyteen.

Tukivektorikone Pystyy luokittelemaan dataa vaik-ka luokkien rajat eivät olisivaik-kaan li-neaarisia. Tarvitsee epälineaarista

Syötettävän datan tulee olla numee-rista sekä yhtenäistä. Mallin tulkin-ta sekä parametrien valintulkin-ta voi olla haastavaa. Lisäksi isot poikkeamat datassa voivat aiheuttaa ongelmia.

Päätöspuut Yksinkertaisia ja helppoja ymmär-tää. Pystyvät käsittelemään erilai-sia arvoja samalla kertaa. Sietävät kohinaa ja puuttuvia attribuutteja.

Rajoitteena oletus että kaikki da-tapisteet voidaan luokitella kor-kea kohinan sietokyky sekä tulkin-nan helppous.

Matalamnpi tiedon esittämiskyky.

Neuroverkot Kykenee käsittelemään epätäydel-listä dataa sekä pystyy antamaan vastauksen vaikka verkon sisällä ta-pahtuisikin virheitä. joten datan esiprosessointi ei ole välttämätöntä.

Koulutus vaatii paljon dataa sekä on laskennallisesti raskas.

Taulukko 4.1:Koneoppimisen menetelmien vertailu

on aina tapauskohtainen ja datasta riippuvainen. Esittelen alla muutamia yleisimpiä klusterointimenetelmiä sekä niiden niiden käyttökohteita.

Agglomeratiivinen klusterointi

Agglomeratiivinen klusterointi (Agglomerative Clustering) joka tunnetaan myös nimellä Agglomerative Nesting (AGNES) on hierarkisen klusteroinnin yleisin tyyppi. Algoritmin toimintalogiikka on seuraava:

1. Se aloittaa klusteroinnin siitä lähtökohdasta että jokainen avaruuden piste on oma klusterinsa.

2. Jokaisella “kierroksella” näistä klustereista etsitään kaksi lähimmäistä ja muo-dostetaan niistä yksi isompi klusteri. Tätä prosessia toistetaan niin kauan kunnes jäljellä on vain yksi iso klusteri.

3. Tuloksena saadaan dendogrammi joka kuvaa pisteiden sijoittamisen klustereissa puumaisena visualisointina.

Toimintalogiikka osoittaa että algoritmi toimii “alhaalta ylös” -logiikalla, koska se käsittelee jokaista pistettä omana klusterina (dendogrammin lehtenä) ja etenee siitä kohti juurta (yhtä isoa klusteria). Agglomoeratiivisen klusteroinnoin vastakohta ”Jakava klusterointi” (Divisive clustering) toimii “ylhäältä alas” -logiikalla, muodostaen ensin yhden ison klusterin. Tämän jälkeen se jokaisella kierroksella jakaa kaikkein heterogee-nisimmän klusterin kahtia ja tätä prosessia toistetaan kunnes jokainen avaruudessa oleva piste on oma klusterinsa. Agglomeratiivisen klusteroinnin tapaan myös tässä tuloksena on dendogrammi josta nähdään eri pisteiden klusteroituminen. Erona näissä kahdessa menetelmässä on se, että agglomeratiivinen klusterointi on hyvä havaitsemaan pieniä klustereita kun taas “Jakava klusterointi” -menetelmä soveltuu paremmin tunnistamaan isoja klustereita.

BIRCH

Tasapainotettu iteratiivisesti hierarkian avulla supistava ja klusteroiva on ohjaamaton tiedonlouhinta-algoritmi jota käytetään hierarkiseen klusterointiin erityisesti isoilla

rajoitettujen resurssien avulla ja saada silti hyvän tuloksen. BIRCH:n tarvitseekin usein toimiakseen käydä annettu tietue vain kerran läpi.

Aiempiin klusterointialgoritmeihin nähden BIRCH:n toimintalogiikka on täysin poikkea-va. Aiemmin klusterointialgritmit toimivat siten että ne latasivat koko datasetin muistiin jonka jälkeen itse klusterointi voitiin aloittaa. Tämä toimii hyvin pienillä dataseteillä, mutta vähänkään suuremmilla tarvittavien laskentaresurssien määrä voi osoittautua liian suureksi. Tämän lisäksi monet aiemmat ratkaisut perustuivat siihen, että jokaisen klusterointipäätöksen kohdalla koko pisteavaruus käytiin läpi joka aiheuttaa sen, että klusterointi on resurssien näkökulmasta kallista.

DBSCAN

Tiheyspohjainen paikkakohtainen klusterointi kohinaa sisältäviin käyttötapauksiin on tiheyspohjainen ei-parametrinen algoritmi. DBSCAN on yksi useimmiten käytetyistä sekä paljon tieteellisissä julkaisuissa viitattu klusterointialgoritmi. Se klusteroi pisteava-ruuden pisteet jotka ovat keskenään lähekkän ja merkitsee poikkeamiksi sellaiset pisteet, jotka sijaitsevat muuhun pisteavaruuteen nähden erillään.

DBSCAN:n etuina pidetään muun muassa sitä ettei se vaadi K-means:n tapaan kluste-reiden määrän tietämistä etukäteen sekä että se pystyy löytämään jopa mielivaltaisen muotoisia klustereita. Eli esimerkiksi sellaisia, joka on kokonaan toisen klusterin ympä-röimä. Tämä on mahdollista siksi koska DBSCAN kestää hyvin kohinaa ja poikkeamia.

DBSCAN:n käyttö on lisäksi helppoa ja se vaatii syötteksi vain kaksi parametria. Tämän lisäksi DBSCAN:n etuna pidetään sitä ettei se juurikaan välitä missä järjestyksessä data on syötetty tietokantaan.

DBSCAN:n heikkouksina pidetään ettei se ole täysin deterministinen eli jos pisteava-ruuden piste voidaan saavuttaa useasta eri pisteestä, sen klusteroituminen voi määräytyä sattumanvaraisisien muuttujien perusteella esimerkiksi datan järjestyksen mukaan. Li-säksi DBSCAN pohjaa monen muun algoritmin tapaan Eukliidiseen etäisyyteen joka tuo mukanaan ”ulottuvuuksien kirouksen” (Curse of Dimensionality), jolla viitataan siihen, että korkean ulottuvuuden pisteavaruuksissa etäisyysalgoritmin kyky etäisyyden maarittämiseen heikkenee merkittävästi. Lisäksi DBSCAN ei kykene klusteroimaan hy-vin sellaisen pisteavaruuden pisteitä jonka avaruuden eri osien pistetiheydet poikkeavat toisistaan merkittävästi.

K-Means

K-means on yksi suosituimmista klusterointialgoritmeista pitkälti sen yksinkertaisuuden sekä nopeuden takia. K-means:n tavoitteena on ryhmitellä pisteavaruuden pisteet samankaltaisuuden perusteella ennalta määrättyyn määrään ryhmiä. Ryhmittelyn kautta K-means saattaa havaita datassa mahdollisesti piileviä kuvioita ja yhdistäviä tekijöitä.

K-means algoritmin toimintaperiaate on seuraava:

1. Se luo ennalta määritellyn määrän klustereiden keskipisteitä (Centroids) pis-teavaruuden satunnaisiin paikkoihin joita käytetään alkuarvoina klusteroinnin alussa.

2. Algoritmi käy pisteavaruuden pisteitä läpi ja muuttaa centroidien sijainteja sen perusteella.

3. Kohtaa 2. toistetaan kunnes klustereiden keskipisteiden sijainnit eivät enää muutu tai ennalta määrätty iteraatioiden lukumäärä täyttyy.

K-means toimii erittäin hyvin pienien pistemäärien kanssa, mutta se alkaa hidastua jos klusteroitavia pisteitä on paljon. Hidastumistakin suurempi heikkous on se että toimiakseen K-means vaatii että koko syötedata on pidettävä muistissa joka isoilla dataseteillä on hankalaa sekä kallista.

Mini-Batch K-Means

Mini Batch K-means (myöhemmin MBK) on esitetty K-means klusterointialgoritmin korvaajaksi isojen data määrien klusterointiin. Suurimpana erona perinteiseen K-means algoritmiin on se, että MBK pilkkoo syötedatan useampaan saman kokoiseen osaan sen sijaan että käyttäisi koko syötedataa. Tämä laskee iteraatiokohtaista laskentakapasitetti-tarvetta, koska jokaisella iteraatiolla ei käydä koko syötedataa läpi vaan vain osa siitä.

Tämä kuitenkin aiheuttaa sen, että klustereiden laatu/tarkkuus laskee hieman.

Mini Batch K-meansin toimintaperiaate on seuraava:

1. Se pilkkoo syötedatan ennalta määrätyn kokoisiin osiin jotka mahtuvat muistiin.

2. Jokaisella iteraatiolla valitaan pilkotuista osista sattumanvaraisesti yksi jonka

5. Kokeellisen osuuden esittely

Tutkielman toteutusosassa on tarkoituksena luoda helppokäyttöinen ja kevyt työkalu opiskelijadatan analysointiin. Työkalun tavoitteena on tarjota ominaisuudet opiskelija-datan visualisointiin sekä pienimuotoiseen oppimistulosten ennakointiin. Työkalu on tarkoitus toteuttaa web-pohjaisena jolloin käytettävien laitteiden kanta on mahdollisim-man laaja. Työkalun toiminnallisuuden lisäksi tavoitteena on luoda sen käyttöliittymästä sekä käytettävyydestä sellainen joka vetoaa opettajiin ja muihin käyttäjäkohderyhmän henkilöihin.

Työkalun perusidea on seuraava. Käyttäjä menee selaimellaan web-osoitteeseen jossa työkalu on saatavilla ja syöttää opiskelija datan työkaluun .csv-tiedostona. Työkalu purkaa ja analysoi tiedoston sisältämän datasetin ja visualisoi käyttäjälle opiskelijoiden keskinäisen sijoittumisen klusterointipuuna. Puusta käyttäjä voi havaita millä perusteella ryhmittely on tehty ja halutessaan tutkia tarkemmin opiskelijan tietoja. Käyttäjä voi halutessaan muokata työkalun asetuksia eli esimerkiksi vaihtaa käytettyjä algoritmeja ja parametreja. Työkalu tarjoaa kaksi erilaista algoritmia etäisyyden laskentaan jotka ovat Eukliidinen etäisyys (Kaava 5.1) ja Manhattan-etäisyys (Kaava 5.2). Parametrivalinnan sisältö perustuu syötettyyn dataan ja sen ominaisuuksiin. Asetusten vaihtaminen tehdään alasvetovalikoilla sekä valintalistoilla joten niiden muuttaminen on yksinkertaista. Ase-tusten tarjoamisen ideana on mahdollistaa käyttäjälle nähdä eri metodeilla tapahtuvien analysointien erot.

Työkalu valitsee automaattisesti annetusta datasta tyypiltään numeraaliset sekä totuusar-volliset ominaisuudet ja tarjoaa ne käyttäjälle listana josta hän voi valita mieleiset

ominaisuudet. Valinnan jälkeen työkalu suorittaa luokittelun ja visualisoinnin niiden pohjalta.

Toivonen ja kumppanit perehtyivät opiskelijadatan käsittelyyn käytettäviin työkaluihin tutkimuksessaan.[23] Tutkimuksessa havaittiin että opettajilla ei ole juurikaan mielen-kiintoa opetella uusia työkaluja joiden käyttö ja opettelu vaatii paljon vaivaa. Tämä johtui pitkälti siitä syystä että opetusjakson kesto per ryhmä ei ollut pitkä ja siihen suhteutettuna työkalusta saatava hyöty työmäärään nähden ei ollut merkittävä. Työkalun osalta tutkimuksessa todettiin että jos käyttäjä pystyy näkemään miksi käytetty algoritmi esimerkiksi luokitteli datan tietyllä tavalla, lisäsi se tuloksen luotettavuutta merkittävästi.

Lisäksi käyttäjien kiinnostusta lisäsi se jos työkalun/algoritmin asetuksia pystyi muok-kaamaan vapaasti ja näkemään muutoksen vaikutukset reaaliajassa. Työkalun antamien tulosten osalta havaittiin että päätöspuu on esitysmuotona helpoin ymmärtää, koska siinä luokittelun säännöt pysyvät yksinkertaisina ja helpommin ymmärrettävissä.

Käyttöliittymän ja käytettävyyden osalta havaittuna haasteena on opettajien vähäinen kiinnostus opetella uutta ja monimutkaista työkalua.

5.1 Tekninen kuvaus

Työkalu toteutetaan puhtaasti web-pohjaisena. Tällä tavoitellaan sitä, että työkalua pystyy käyttämään mahdollisimman laajalla laitekannalla, koska tällöin tekniset vaatimukset rajautuvat siihen että laitteessa on moderni selain. Lisäksi työkalu toteutetaan siten, että kaikki laskenta ja muu datan käsittely tapahtuu käyttäjän laitteella eikä mitään dataa lähetetä palvelimen suuntaan. Tältä osin käytettävän laitteen suorituskyky määrittää pitkälti kuinka sulavasti työkalu toimii. Kaiken työkalun tekemän laskennan olisi voinut ulkoistaa palvelimen puolelle ja siten parantaa suorituskykyä hitaammilla laitteilla sekä suurempia datasettejä käsiteltäessä. Tämä olisi kuitenkin tuonut todennäköisesti kysymyksiä sekä epäluottamusta palvelimelle siirretyn datan säilömisestä sekä työkalun yleisestä tietoturvasta, koska lähetettävä data saattaa sisältää sellaisia salassapidettäviä tietoja joiden tallentaminen ja säilyttäminen voi olla luvanvaraista. Tietoturvakysymysten lisäksi haluan työkalun olevan käytettävä myös silloin kun verkkoyhteyttä ei ole saatavissa tai se on todella hidas.

Työkalu toteutetaan PWA:na joka mahdollistaa sen, että se voidaan asentaa verkkosivulta laitteeseen jolloin se on laitteella käytettävissä kuten muutkin sovellukset. PWA-tekniikan

koska resursseja ei tarvitse ensimmäisen latauskerran jälkeen ladata enää palvelimelta vaan niitä voidaan käyttää laitteen suoraan laitteen välimuistista.

Koska työkalu on täysin web-pohjainen sen logiikka on tehty kokonaan JavaScriptillä ja käyttöliittymä käyttäen HTML:ää ja CSS:ää. Työkalu on rakennettu kokonaan Vue.js-frameworkin päälle. Vue.js on React:n kaltainen JavaScript-ohjelmistokehys (framework), joka tuo erityisesti käyttöliittymän tekoon uusia työkaluja ja tapoja. Työkalun kaikki logiikka toteutetaan käyttäen TypeScriptiä joka käännetään lopulta selaimessa ajettavaksi JavaScriptiksi. Syy TypeScriptin käyttöön on sen tuoma tyyppituki, joka helpottaa monimutkaisten datarakenteiden käsittelyä, koska tyypitys pitää huolen ettei niin sanottuja tyhmiä virheitä pääse syntymään. Käytän jatkossa työkalun ohjelmakoodiin viitatessani termiä JavaScript, koska se on lopullinen koodikieli joka suoritetaan ja sen tuomat lainalaisuudet pätevät myös TypeScriptin puolella.

Työkalun toimivuuden todentamista varten luodut testitapukset ovat tutkielman liiteo-siossa liite A.1.