T-61.2010 Datasta tietoon Syksy 2009 Tietokoneharjoitukset / Jukka Parviainen 20091210 Lyhyesti -------------------------------------------------------------------- Joulu- ja tammikuun tenteissä kysytään yksi tehtävä tietokoneharjoitusten aiheista. Koska tietokoneharjoitukset tukevat kurssin luentoja ja paperilaskareita, vastaukset voi pitkälti tuottaa ilman tietokoneharjoituksiakin. Itse Matlab-koodia ei kysytä. Esimerkkejä tentin viimeisen tehtävän esseeaiheista: - äänisignaalin käsittely ja analysointi: kierros 1, demot 4-5 - ominaiskasvot ja pääkomponenttianalyysi: kierros 2 - luokittelu, kNN: kierros 3, demot 3-4 - ryhmittely, hierarkinen / c-means (==k-means): kierros 4 - kattavat joukot: kierros 5 Esseevaihtoehtoja tulee kaksi, joista toiseen vastataan. Pitkästi -------------------------------------------------------------------- Yleistä -------------------------------------------------------------------- Tietokoneharjoituksia järjestettiin viisi kierrosta. Yhteensä kahden tunnin opetustapahtumia oli 19 kpl. Harjoituksilla saattoi korvata pienen harjoitustyön. Korvaajia oli 87 (+muutama?). Harjoitusten tarkoituksena oli tukea annettua opetusta: - esittelemällä Matlab-ohjelmisto ja sen peruskäyttö o Matlab on saatavilla TKK:n kelluvilla lisensseillä niin Windows- kuin Linux-koneista o Matlabin graafinen käyttöliittymä, mm. työhakemistopolku keskellä ylhäällä alasvetolaatikkossa, varsinainen komentoikkuna o Matlab-koodi kannattaa tallentaa ja ajaa omassa editorissa o Matlabissa skriptit (makrot, eräajot) ja funktiot (palauttaa muuttujia, ottaa sisäänsä muuttujia) o peruskomentoja, ohjausrakenteita (if, for) - esittelemällä Matlabin "GNU-klooni" Octave o kierros TK5 o peruskoodi ja -toiminta identtistä Matlabin kanssa - esittämällä muutamia paperilaskaritehtäviä ratkaistuna tietokoneen avustuksella - demoamalla muutamia tehtäviä o suurempi datamäärä kuin paperilla "viitsisi" laskea o mutta usein "käytäntöä" huomattavasti pienempi Tietokoneharjoitusten sisältö -------------------------------------------------------------------- Kierros #1. * Aiheet: Datamatriisin käsittely. Äänisignaalin käsittely. * Nopassa T1.zip kohdassa "Viikkoharjoitukset" * Luentokalvot: Luku 3 * Paperilaskarit - H1/1 konvoluutiosumma (suodattaminen) - H1/2 Fourier-muunnos (signaalista spektri) * Datamatriisin X käsittely - Tunnuslukuja: minimi, maksimi, keskiarvo, varianssi. - Histogrammi - Pisteiden piirtäminen kaksi muuttujaa kerrallaan - Korrelaatiokertoimet * Äänisignaalin x(t) käsittely - konvoluutio: operaatio kahdelle sekvenssille tuottaen kolmannen - konvoluutio: äänisignaalin osalta tarkoittaa syötesignaalin suodattamista suotien impulssivasteella, mikä tuottaa vastesignaalin - signaalista esitettiin visualisointeja: aaltomuoto (ajan funktiona), spektri (taajuuden funktiona), spektrogrammi (ajan ja taajuuden funktiona) - demottiin kun yksittäinen häiriösinisignaali voitiin vaimentaa kaistanestosuotimella; tämä voitiin toteuttaa konvoluutiosumman avulla, jossa häiriöllinen ääni ja suotimen impulssivaste konvoloitiin ja saatiin suodatettu ääni Kierros #2. * Aihe: Pääkomponenttianalyysi. * Nopassa T2.zip kohdassa "Viikkoharjoitukset" * Luentokalvot: Luku 4 * Paperilaskarit - H2/1 PCA:n laskeminen "käsin" - H2/2 taustaa: PCA:n 1. suunta maksimoi vaihtelun (varianssin) * Pääkomponenttianalyysi: - voidaan käyttää mm. datan dimension pienentämiseen (kompressointi) ja dekorrelointiin - tässä datana H2/1, 2/3-ulotteinen sekä kasvokuvagalleria - päävaiheet: (1) keskiarvon poistaminen X-matriisista eli origo keskelle datapilveä, (2) kovarianssimatriisin laskeminen keskiarvoistetusta datasta, (3) ominaisarvojen ja -vektorien laskeminen kovarianssimatriisista - ominaisarvot (merkitään lambda): geometrisesti esittävät ellipsoidin sivujen pituudet, neliöjuuri(lambda), kts. luentokalvot Luku 4 kalvo 9/34 - ominaisarvot: vaihtelun selittävyysaste s s = 100% (SUM(lambda_mukaan)) / (SUM(lambda_kaikki)) - ominaisvektorit: tässä ominaiskasvot, Luku 4 kalvo 30/34 - voidaan poimia N kpl suurimpia ominaisarvoja vastaavia ominaisvektoreita (kasvoja) ja projisoida data niitä vastaan (Y = W'X), Luku 4 kalvo 31/34 - voidaan projisoida kaikkia ominaisvektoreita vastaan, jolloin dekorreloidaan data (Y = V'X) * Kasvokuvagalleria: - yksi kasvokuva 19x19 pikseliä eli yhteensä 361 pikselä - kuvattu "samoissa valaistustilanteissa" ja rajattu samalla tavalla - galleriassa 92 kuvaa, mukana 1-5 kuvaa samasta henkilöstä * Kasvokuvatutkimuksesta "hauskaa": http://www.faceresearch.org/demos/average/ Valitse päitä ja keskiarvoista! * Markus Koskela kertoi luennolla to 19.11. kuvantunnistamisen haasteista Kierros #3. Pienimmän neliösumman sovitus. Luokittelu. * Aiheet: Pienimmän neliösumman sovitus. Luokittelu. * Nopassa T3.zip kohdassa "Viikkoharjoitukset" * Luentokalvot: Luku 5. Luku 6. * Paperilaskarit - (H3/1) regressio - H3/3 kNN * Pienimmän neliösumman sovitus: - liittyen regressioon - tietyin oletuksin suurimman uskottavuuden menetelmän tulos - sovitetaan data johonkin malliin, demoissa polynomikäyrä - lasketaan virhettä datapisteen etäisyydestä käyrään y-akselin suunnassa - summataan kaikki neliölliset virheet ja minimoidaan tätä - saadaan polynomifunktion kertoimet selville - voidaan selittää (ennustaa) jotain muuttujaa muiden avulla * Luokittelu - kNN = k nearest neighbor eli valitaan k kpl lähimpiä naapureita määräämään mihin luokkaan luokiteltava piste kuuluu - yleensä data jaetaan opetus- ja testiainestoon minkä perusteella voidaan laskea luokitteluvirhe - luokitteluvirhe: väärin luokiteltujen pisteiden suhteellinen määrä Kierros #4. Ryhmittelyanalyysi: hierarkkinen ja dynaaminen ryhmittely (c-means == k-means). * Aiheet: Ryhmittely * Nopassa T4.zip kohdassa "Viikkoharjoitukset" * Luentokalvot: Luku 6. * Paperilaskarit - (H4/1) - H4/2 hierarkinen ryhmittely - (H4/3) taustaa c-means virhekriteerin pienenemiselle * Hierarkinen ryhmittely - Luku 6 kalvo alk. 30/55, esimerkki kalvo 48/55 - algoritmin aikana luodaan ryhmittelypuu (dendrogrammi), josta voidaan jälkikäteen valita ryhmien (klusterien) lukumäärä - alussa jokainen piste on oma ryhmänsä, sitten ryhmiä yhdistellään kunnes kaikki kuuluvat samaan ryhmään - etäisyysmitta (euklidinen) - ryhmien yhdistelymitta (single=lyhin, average, complete=pisin), visuaaliset esimerkit Luku 6 kalvo 49/55, ja valinnan vaikutuksesta esimerkki Luku 6 kalvo 50-54/55 * k-means ryhmittely: - Luku 6 kalvo, esimerkki kalvo 55/55 - k-means == c-means - valitaan ryhmien lukumäärä k - arvotaan ryhmien k keskipistettä - kaksivaiheinen iteraatio: pisteiden yhdistäminen ryhmiin ja uuden ryhmäkeskipisteen (massakeskipiste) laskeminen * Kasvokuvien ryhmittely - esimerkkinä kasvokuvadata sekä 2-ulotteisena että 361-ulotteisena Kierros #5. Kattavat joukot ja tasoittainen algoritmi (apriori). * Aiheet: Tasoittainen algoritmi. Keskukset ja auktoriteetit. * Nopassa kierros T5 kohdassa "Viikkoharjoitukset" * Luentokalvot: Luku 8 ja 9 * Paperilaskarit - H5/1 - (H5/2) - H5/4 * 0-1-matriisi onko joku muuttuja paikalla jossain havainnossa - kauppakassin tuotteet - tekstidokumentin sanat - 'bag of words' * kattaviin joukkoihin liittyy kynnysarvo N - Luku 8 kalvo 24/60 - etsitään kaikki joukot, jotka esiintyvät vähintään N kertaa aineistossa - kombinatorisesti haastava etenkin pienillä N:n arvoilla * tasoittainen algoritmi kattavien joukkojen etsintään - Luku 8 kalvo 29/60 -> - periaate: joukko voi olla kattava vain jos kaikki sen alijoukot ovat kattavia; tällä voidaan karsia haettavien kandidaattijoukkojen lukumäärää - yhden muuttujan kokoiset joukot: mitkä niistä esiintyvät ainakin N kertaa? -> kattavat 1:n kokoiset - 1:n kokoisista joukoista generoidaan potentiaaliset 2:n kokoiset joukot (kandidaatit) - lasketaan, mitkä 2:n kokoisista kandidaateista esiintyy N kertaa - valmistellaan k:n kokoisista kattavista joukoista (k+1)-kokoiset ehdokkaat - lasketaan (k+1)-kokoisista, mitkä esiintyvät vähintään N kertaa - toistetaan kunnes ei enää löydy uusia kattavia joukkoja - KAIKKI erikokoiset kattavat joukot on lopullinen kattavien joukkojen joukko * Keskukset ja auktoriteetit - Luku 9 kalvo 12/32 -> - etsii webbisivujen relevanssia niihin osoittavien ja niistä lähtevien linkkien perusteella - kullakin webbisivulla kaksi painoa: auktoriteetti- ja keskuspaino; nämä voidaan laskea iteratiivisesti - periaate: hyvä keskus osoittaa hyviin auktoriteetteihin. Hyviin auktoriteetteihin tulee linkkejä hyvistä keskuksista - Matlab-koodin esimerkkitilanne Luku 9 kalvo 29-31/32