Section outline

  • Splošno

    Skrči vse Razširi vse

    Predavatelj in asistent: Blaž Zupan (blaz.zupan@fri.uni-lj.si)

    Spletna stran predmeta, kot se je izvajal leta 2017/18. V šolskem letu 2019/20 se ta predmet ne izvaja!

    Kaj pričakujemo od študentov? Sprotno in pravočasno izdelavo in oddajo poročil domačih nalog in projektov (teh bo predvidoma vseh skupaj okoli osem), sprotno kodiranje, sprotno branje literature (priprava na predavanja). Vprašanja med predavanji (še posebej, če kaj ni jasno, a tudi, ko bi radi zvedeli kaj več). Obiskovanje konzultacijskih vaj (ko se kaj zalomi pri domačih nalogah, ali pa tudi, da preveriti, ali je vaša rešitev v redu). Pravočasna izdelava domačih nalog: najbolje se jih je lotiti takoj po predstavitvi domačih nalog na predavanjih.

    Potrebna predznanja: Pogoj za vpis predmeta Odkrivanje znanj iz podatkov je opravljen predmet Uvod v odkrivanje znanj iz podatkov  (staro ime: Poslovna inteligenca) oziroma obiskovanje tega predmeta v istem šolskem letu. Pri predmetu Odkrivanje znanj iz podatkov bomo kombinirali znanja, ki ste jih pridobili pri predmetih s področja umetne inteligence, strojnega učenja in inteligentnih sistemov, ter v praksi osvežili vaše spretnosti iskanja in uporabe literature, uporabe primernih (predvsem odprtokodih) programskih orodij in knjižnic, ter sposobnost samostojnega reševanja kompleksnih problemov. Pričakujemo tudi, da znate dobro programirati; uporabljali bomo Python verzijo 3.5, po potrebi (a ne pri predavanjih in vajah), pa tudi kakšne ostale jezike. Za tiste, ki omenjenih predznanj nimate, bo predmet precej zahteven, saj si boste morali pridobiti ustrezna znanja sproti z branjem dodatne literature.

    Ocenjevanje: domače naloge (100%). Za pozitivno oceno pri predmetu je potrebno zbrati vsaj 60,5% točk iz domačih nalog. Posamezne naloge niso prenosljive v naslednje šolsko leto. Na celo števlio zaokrožene skupne odstotne točke se prevedejo v oceno pri predmetu: do 60 -> 5, od 61 do 68 -> 6, od 69 do 76 -> 7, od 77 do 84 -> 8, od 85 do 92 -> 9, od 93 do 100 -> 10.

    Ocenjevanje domačih nalog: Oddana programska koda bo ocenjena z avtomatskimi testi. V primeru, da bo domača naloga zahtevala tudi poročilo, naj bo le-to napisano v LaTeXu (predloga, primer). Domače naloge imajo strogi rok. Za vsak dan zamude se ocena množi z 0,9. Primer: študent je za nalogo, ki jo je oddal dva in pol dni po roku, prejel 75 točk. Končna ocena naloge je 75*(0,9^3) = 54,7 točk. V primeru, da z oddajo naloge zamudite več kot en teden, se naloga šteje kot neopravljena (0 točk). Ocena naloge je sestavljena iz ocene za vsebino (90%) in strukturo/pravopis (10%). Kakršnokoli prepisovanje bo strogo kaznovano: naloge, ki bodo vsebovale neavtorske elemente, bodo ocenjene z 0% (torej, tako naloga prepisovalca kot tistega, ki je dal nalogo v prepis), kršitev pa bo posredovana disciplinski komisiji FRI.

    Osnovna literatura:

    • zapiski predavatelja, objavljeni na tej spletni strani
    • ostala gradiva, objavljena pri posameznih lekcijah na tej spletni strani

    Priporočena dodatna gradiva:

    • Leskovec J, Rajaraman A, Ullman J (2015) Mining of Massive Datasets. Predvsem poglavja o zmanjševanju dimenzij podatkov.
    • Tan P-N, Steinbach M in Kumar V (2006) Introduction to Data Mining. Vsebuje lep uvod v to, kaj odkrivanje znanj iz podatkov je in kaj ni. Odličen pregled nekaterih tehnik. Zelo podrobno in tehnično predstavljene tehnike razvrščanja v skupine / clustering.
    • Bishop CM (2006) Pattern recognition and machine learning, Springer. Za "profesionalce". Biblija strojnega učenja. Kar nekaj poglavij bomo privzeli po tej knjigi.

    Tekmovanje: če bo le možno, se bomo tekom predmeta udeležili kakšnih mednarodnih tekmovanj na tekmovalnih portalih, kot je na primer Kaggle.

    Orodja:

    • Python 3
    • matplotlib (izris grafov)
    • scipy in numpy (linearna algebra, statistični izračuni)
    • PyCharm (priporočeni urejevalnik kode)
    • Orange 3 (uporabljali bomo večinoma skriptni del) 
    • scikit-learn (knjižnica za strojno učenje)
    • IPython Notebook (luštno okolje za skriptanje, delo z grafi in pisanje zapiskov, bolj za predavatelja kot za študente)

    Novice, razprave, vprašanja: na forumu.

  • PCA in potenčna metoda, singularni razcep

    Metoda glavnih komponent (angl. principal component analysis) je nenadzorovana tehnika, namenjena zmanjšanju dimenzionalnosti podatkov, izločanju šuma in prikazu podatkov v dvo ali tro-dimenzionalnih vizualizacijah. PCA je linearna transformacija, ki podatke iz atributnega prostora, kjer so atributi med sabo lahko odvisni preslika v prostor medsebojno neodvisnih atributov. Osnovni postopek za gradnjo glavnih komponent ne upošteva vrednosti razredne spremenljivke. V postopku konstrukcije te transformacije podatke centriramo, izračunamo kovariančno matriko in poiščemo njene lastne vektorje in vrednosti. Lastni vektorji določajo nov koordinatni sistem, v katerega preslikamo podatke, lastne vrednosti pa deležu pojasnjene variance podatkov. Glavne komponente so torej tiste z največjimi lastnimi vrednosti. Tipično nas zanima le nekaj glavnih komponent, s katerimi na primer razložimo do 80% ali 90% variance. Za izris razsevnega diagrama s podatki pa navadno uporabimo prvi dve glavni komponenti, torej tisti z največjima lastnima vrednostima. Na predavanju se predvsem ukvarjamo s postopkom hitrega izračuna prvih nekaj glavnih komponent in deleža celotne variance, ki nam jih te pojasnijo.

    Metoda glavnih komponent je poseben primer uporabe singularnega razcepa matrike (angl. singluar-value decomposition). Cilj tega je predstavitev matrike podatkov X s sistemom matrik UDVT, kjer sta matriki U in V ortonormalni in je matrika D diagonalna. Pokažemo, da matrika U ustreza lastnim vektorjem matrike XXT, matrika V lastnim vektorjem matrike XTX, elementi na diagonali matrike D pa so koreni pripadajočih lastnih vrednosti in, glede na podatke X, torej ustrezajo korenom pojasnene variance komponente, ki je predstavljena z lastnim vektorjem. Sistem UDV lahko tudi zmanjšamo tako, da upoštevamo samo glavne komponente in tako dobimo zmanjšano matriko profilov primerov in profilov atributov.

    		 Osnovna literatura
    • Leskovec J, Rajaraman A, Ullman J (2015) Mining of Massive Datasets. Poglavja 11.1, 11.2 in 11.3 o lastnih vektorjih, PCA in SVD.

  • Vlaganje primerov v nižjedimenzionalne prostore

    Visoko dimenzionalne podatke še najraje predstavimo grafično, v vizualizaciji. Najbolj običajne, morda tudi najbolj preproste, so točkovne vizualizacije. Z metodo glavnih komponent smo lahko visoko dimenzionalne podatke preslikali v dve dimenziji ter pri tem skušali pojasniti čim več variance vhodne matrike. Preslikava PCA je linearna, njena prednost pa, da smo na testni množici pridobili predpis (matriko), s katerim lahko preslikamo nove podatke v dvodimenzionalni prostor. Namesto tovrstnih preslikav lahko primere iz originalnega (visoko dimenzionalnega) prostora vložimo v nižje dimenzionalni prostor. Tu nas bo seveda največkrat zanimalo vlaganje v dve dimenziji. Določiti moramo, kakšne vložitve nas zanimajo. Na predavanju spoznamo dve. Večrazredno lestvičenje (angl. multi-dimensional scaling) skuša v prostoru vložitve ohraniti razdalje med primeri iz originalnega prostora. Pri stohastični vložitvi sosedov (angl. stochastic neighbour embedding, SNE ali, v izboljšani verziji t-distributed stochastic neighbour embedding) pa nas zanima samo ohranjanje lokalnosti: če je razdalja med dvemi primeri v originalnem prostoru bila majhna, naj bi ta primera bila blizu drug drugega tudi v prostoru vložitev. Vložitve za metodi MDS in t-SNE pridobimo iterativnimi postopki optimizacije lege primerov v prostoru vložitev. Za vložitev ne pridobimo predpisa, oziroma ga ne moremo opisati z neko matrično transformacijo. Prednost teh metod pa je, da lahko namesto s podatki delajo z razdaljami med primeri in da tipično poiščejo vložitve, kjer so med sabo različni primeri bolje ločeni kot na primer v projekcijah z glavnimi komponentami. Osnovna literatura

  • Naprednejše tehnike gručenja

    Od naprednih tehnik gručenja bi si želeli, da lahko odkrijejo skupine poljubnih oblik, da znajo obravnavati šumne primere in da te izključijo iz skupin, da so odvisne od čim manj parametrov in da so hitre. Ena od takih tehnik je DBSCAN, ki temelji na iskanju gostih regij primerov. Gostoto primerov sicer določata dva parametra sosednosti eps in potrebnega števila točk v eps-soseščini minPts, a so na dosedanjih eksperimentih potrdili, da je DBSCAN precej odporen na spremembe parametra minPts in da je primerno vrednost parametra eps moč pridobiti kar iz podatkov. Prednost tega algoritma je tudi enostavna implementacija. Med naprednimi algoritmi omenimo tudi louvainsko gručenje, ki pa uporablja omrežja. Podatke za to gručenje je potrebno pretvoriti v omrežje, kjer so primeri vozlišča, povezave v omrežju tipično ustvarjene za pare najbližjih vozlišč, uteži povezav pa ustrezajo izbrani meri podobnosti med primeri. Literatura

  • Ansambli

    Ob odsotnosti razsvetljenega diktatorja je pač veliko bolje, da o problemu vprašamo nekaj ekspertov, potem pa njihova mnenja agregiramo v končno. Podoben pristop lahko uporabimo tudi v strojnem učenju. Iz učnih podatkov se naučimo niza napovednih modelov in njegove napovedi na testni množici agregiramo s povprečenjem. Želeli bi si, da so ti modeli med sabo različni, torej, da pogledajo na podatke iz različnih zornih kotov. To dosežemo ali z vzorčenjem učne množice za vsak model posebej (metoda imenovana bagging), s ponaključenjem algoritmov strojnega učenja, ali s kombinacijo teh dveh pristopov (na primer pri naključnih drevesih). Na predavanjih pokažemo, da so regresijska drevesa precej občutljiva na celo manjše spremembe v učni množici, da pa za metode, kot je linearna regresija, to ne velja, saj manjše spremembe v podatkih le malo vplivajo na naučene vrednosti parametrov modela. Podobno stabilna kot linearna regresija je na primer tehnika k-najbližjih sosedov. A se tudi te, stabilne metode, da "ponaključiti" in sicer tako, da raznolikost modelov dosežemo z vsakokratnim naključnim izborom podmnožice atributov.

    Ostane nam le še, da razmislimo, ali je agregacija s povprečenjem napovedi posameznih modelov res najboljši pristop. Morda pa bi se lahko iz zbirke napovedi modelov in dejanskih vrednosti razreda lahko naučili, kako kombinirati napovedi modelov. To počne stacking. Podatke za učenje modela, ki kombinira napovedi, pridobimo s prečnim preverjanjem in se naučimo modela za kombiniranje napovedi iz napovedi na testnih primerih in pravih vrednosti razreda. S to funkcijo kombiniramo napovedi modela, ki se jih naučimo na celotni učni množici.     		Osnovna literatura
    Literatura
    Koda s predavanj

  • Večrazredna klasifikacija, regresija softmax

    Pričnemo z večrazredno klasifikacijo oziroma z razmišljanjem, kako bi logistično regresijo lahko uporabili na podatkov, kjer ima razredna spremenljivka več kot dve vrednosti. Predstavimo ad hoc, inženirsko rešitev, ki same logistične regresije ne spreminja ampak raje spreminja podatke, in pa dobro teoretično osnovano rešitev, ki logistično regresijo razširi v multinomsko regresijo, ali regresijo softmax. Osnovna literatura

  • Nevronske mreže: vzvratno razširjanje napake

    Za predstavitev kompleksnejših konceptov v podatkih lahko razširimo atributni opis (t.im. feature engineering) ali pa povečamo izrazno moč in s tem tudi kompleksnost modelov. Nevronske mreže so primer slednje rešitve. Osnovno nevronsko mrežo gradimo iz hierarhij enot, ki so v osnovi enake logistični regresiji. Torej sprejmejo vhode iz enot na prejšnjem nivoju, utežijo njihove aktivacijske vrednosti, utežene vrednosti seštejejo in transformirajo z aktivacijsko, na primer logistično funkcijo. Posamezen nivo v nevronski mreži je torej podoben regresiji softmax. Za iskanje primernih uteži, ki minimizirajo kriterijsko funkcijo, uporabimo gradientni sestop, za izračun gradientov pa verižno pravilo oziroma pristop vzratnega razširjanja napake (angl. back propagation).

    		Zapiski
    Literatura
    Dodatni viri

  • Metoda podpornih vektorjev

    Metodo podpornih vektorjev (SVM, support vector machines) predstavimo kot tehniko, s katero želimo poiskati ravnino, ki bi kar najbolje postavila mejo med primeri različnih razredov. Tehniko izpeljemo ob predpostavki, da je problem klasifikacijski in dvorazreden ter da taka ravnina obstaja in pravilno razmeji vse primere iz učne množice. Iščemo razmejitev z največjo rezervo oziroma najširšim pasom med pozitivnimi in negativnimi primeri. Pri izpeljavi uporabimo tehniko Lagrangeovih multiplikatorjev, ki problem iskanja najširšega pasu prevede v dualni problem iskanja Largangeovih multiplikatorjev oziroma uteži primerov. Kriterijska funkcija za slednje pa vsebuje samo skalarne produkte parov učnih primerov. Za domene z bolj kompleksnimi ločitvenimi mejami lahko v splošnem razširimo opisni jezik primerov. Pri SVM-ju to pomeni, da skalarni produkt izvedemo v transformiranem prostoru. Ker nas tako pri učenju in klasifikaciji zanimajo samo skalarni produkti vektorjev, lahko te nadomestimo s t.im. jedrom, ki je funkcija nad parom vektorjev. Trik z jedrom pravi, da za SVM potrebujemo le jedro in da nas sama transformacijska funkcija, ki preslika primere iz osnovnega v novi, razširjeni prostor, sploh ne zanima. Med najbolj znanimi jedri omenimo polinomsko in jedro RBF. Za slednje je zanimivo, da vrača število, ki bi sicer bilo skalarni produkt med vektorjema v neskončnem atributnem prostoru.

    		Literatura
    Dodatni viri