MTAT.03.169 Data Mining Research Seminar
MTAT.03.169 Andmekaevanduse uurimisseminar

Andmed on kopeeritud arhiveerimise eesmärgil. Originaal materjalid on võetud aadressilt.
Materials are copied for arciving purposes. The original source was taken from the address.

  • Seminarid: Neljapäeviti 12:15, Liivi 2-511
  • Organiseerija: Jaak Vilo

Sissejuhatus

Andmekaevandus (Data Mining, DM, vahel ka Knowledge Discovery from Databases, KDD) on suhteliselt noor uurimisvaldkond mis on saanud mõjutusi eri aladelt nagu statistika, andmebaaside teooria, masinõppimine, algoritmiline arvutiteadus ning paljud erinevad rakendusvaldkonnad kust on tavaliselt pärit tegelikud analüüsivajadused. Andmekaevanduse eesmärk on leida andmetest seaduspärasusi, trende, reegleid või muid aspekte mis osutuvad mingis mõttes huvitavaks, üllatavaks või millele lihtsalt pole varajasemalt mõeldud. Kui need leitud infokillud esitada mõistlikult lõppkasutajale kasutades visualiseerimist, olulisuse järgi sortimist või muid tehnikaid siis aitab see eeldatavasti kasutajal paremini mõista andmete olemust. Üheks iseloomulikuks omaduseks andmekaevanduses võrreldes näiteks traditsioonilisema masinõppimisega on tavaliselt andmete väga suur maht. Järelikult on vaja analüüsimeetodeid mis oleksid rakendatavad ka reaalselt tere suure andmekogu peal mitte ainult väikeses skaalas. Tüüpilisi andmekaevanduse meetodeid on assotsiatsioonireeglite otsimine kasutades näiteks apriori algoritmi ja selle variante või ka sagedaste episoodide otsimist ajas mõõdetud sündmuste loendist.

Tavaliselt jagatakse andmeanalüüsi (ka DM) meetodid juhitud (supervised) ja juhtimata (unsupervised) või ka osaliselt juhitud (semisupervised) meetoditeks. Tüüpilised juhtimete analüüsimeetodid on klasteranalüüs, aga samuti ka assotsiatsioonireeglite ja mustrite otsimine (pattern discovery). Masinõppimise meetodid on tavaliselt juhitud, st seal tuleb leida reegleid teatud klasside, mis on ette antud, eristamiseks. Näiteks otsustuspuud, -listid, -reelid, närvivõrgud (NN), reeglite hierarhiad ja eranditega reeglid, või hiljuti ka väga laialdaselt levinud kernelmeetodid nagu Support Vector Machines (SVM).

Tüüpiline andmekaevanduse projekt ise on protsess mis koosneb sammudest:

  • Rakendusvaldkonna vajaduste ja andmete tausta väljaselgitamine
  • Andmete kogumine, puhastamine ja esitamine analüüsi võimaldavale kujule, näiteks andmelattu (Data Warehouse)
  • Andmete omaduste ruumi väljavalik (feature space selection)
  • Teadmiste otsimise ja esitamise formalismi valik (NN, klasterdus, otsustuspuud, regulaaravaldised stringidele jne)
  • Kriteeriumide valik tulemuste headuse hindamiseks lühima kirjelduse printsiip MDL, täpsus, täielikkus, ROC graafikud, jne
  • Analüüsialgoritmi väljaarendus või valik ning kasutus reaalsete andmete peal
  • Analüüsitulemuste järeltöötlus leitud reegleid võib olla tuhandeid, inimesele tuleks esitada kõige olulisemad, samuti visualiseerimismeetodite arendamine
  • Saadud tulemuste esitamine tõlgendamiseks erialaspetsialistile tõlgendamiseks

Sageli on vaja eri sammude järel tagasi minna varajasemate juurde, protsess pole alati lineaarne. Rääkides andmekaevandusest arvutiteaduse seisukohast saab eristada neli etappi.

  1. Tulemuste esitamise "keele" või formalismi valik
  2. Tulemuste headuse hindamise kriteeriumide valik
  3. Algoritm andmete analüüsiks, ehk parimate reeglite otsimine punkti 1 otsimisruumis, vastavalt punkti 2 kriteeriumidele.
  4. Andmebaaside ja andmete haldamise probleemid efektiivseks reeglite otsimiseks

Assotsiatsioonireeglid

Tüüpiline andmekaevanduse näide on ostukorvi analüüs. Näiteks, olgu poes ostetud selliseid tarbeid:

klient1t1 t3 t6 t7
klient2t3 t6 t8 t9
klient3t3 t9
klient4t5 t9
......

Tüüpiline assotsiatsioonireegel on:

t3 & t6 => t9 (tugi: 10%, usaldus 80%)

Seda tuleks tõlgendada, et 10% klientidest on ostnud tooteid t3 ja t6 ning lisaks 80% juhtudest mil on ostetud t3 ja t6 on sama isik ostnud veel toodet t9.

Assotsiatsioonireegli saab kätte näiteks teades, et alamhulk {t3,t6} esineb andmebaasis näiteks 1000 korda ning alamhulk {t3,t6,t9} 800 korda. Seega on ülesanne koostada algoritm kuidas kiiresti leida kõik sagedased alamhulgad...

Masinõppimine

Masinõppimises antakse tavaliselt näited ning masin peab õppima reeglid. Näiteks võib tuua õppida ära käsitsi kirjutatud numbrite ära tundmise, patsiendi diagnossi määramine tunnuste põhjal jne. Näiteks allolevatest andmetest võiks õppida reegleid ennustamaks kas hakkab sadama vihma või mitte...

nrtemppilvisustuulõhurõhkvihm
1kõrgepilvestugev700jah
2kõrgepilvitunõrk770ei
3madalpilveskeskm760ei (lumi)
4keskmpilvitukeskm720ei

Tüüpiline "lihtne" masinõppimise meetod on otsustuspuud ja listid. Otsustuspuude puhul hakatakse sisuliselt jagama ainestikku rekursiivselt väiksemateks osadeks, ning jätkatakse kuni puu lehes saab teha otsuse, kumba klassi näide kuulub. Puu tippudes testitakse näiteks atribuutide väärtusi.

Tüüpiline probleem õppimisel on "üleõppimine", st puu tehakse näiteks nii spetsiifiliseks et tegelikult kaob ennustamise võime. Selle vastu on meetode kuidas vältida üleõppimist või pügada juba õpitud otsustuspuud lihtsalt väiksemaks.

Hierarhilised reeglid lähtuvad teisest intuitsioonist - et on olemas reeglid mis kehtivad üldjoontes, kuid millele leidub alati erandeid. Hierarhilised reeglite hulgad luvbavad esitada just neid erandeid. Samas klassifitseerimise ajal võib olla kahte eri tüüpi erandeid - kas püüda kõigepealt välja erandid (globaalne erand) ja siis klassifitseerida üldisemate reeglite järgi, või teha vastupidi - kõigepealt kasutada reeglit ning siis erandreeglit. Pange táhele et ühel juhul on erand globaalne ja teisel lokaalne.

Lineaarne eraldamine - perceptron, SVM, linear regression etc. Eeldab et andmepunktide vahele saab tõmmata lihtsalt sirgjoone (ehk hypertasandi paljumõõtmelises ruumis). Pertseptron, ehk lihtne ühe sõlmega närvivõrk teebki lihtsalt tasandiga eraldamist. Tihti on võimalik tõmmata PALJU eraldusjooni. Milline on neist parim? Tihti on kasulik maksimeerida marginaali eraldusjoonest tegelike andmepunktideni.

Bayesi reegel lubab hinnata mudeli headust: parim mudel on see mis ise pole liiga ebatõenäoline ning lisaks kirjeldab hästi andmeid. Bayesi reegel:

          P( D | M ) · P( M ) 

P( M | D ) = --------------------

             P( D ) 

Hindamise kriteeriumid. Kui rääkida masinõppimise meetodi headusest siis tuleb kuidagi seda osata hinnata. Eesmärk on üldiselt õppida klassifitseerima uusi, seni nägemata andmeid. Selleks et seda oskust hinnata tuleb meil tavaliselt kasutada õpetamise andmeid reegli õpetamiseks ning testandmeid testimiseks. Muidugi ei tohi need kattuda. Kuna andmeid pole alati piisavalt siis tehakse mitmekordset ülekontrolli, st. õpitaks reegleid korduvalt ja hinnatakse alati allesjäänud osa peal klassifitseerija headust. Jäta üks válja "leave one out jacknife" on meetod mis lubab ühe kaupa seda testida. Samas on vaja siis õppida palju kordi. Ning jääb küsimus, mis juhtub siis kui klassifitseerijad on tavaliselt erinevad üksteisest. Pange táhele, et vajalik on ka et õpetamise andmed oleks sõltumatud omavahel. Precision, recall, false positive rate, false negative rate, jne.

MDL printsiip (lühima kirjelduse printsiip) on suguluses Bayesi reegliga. Sisuliselt hinnatakse seda, et kui usutav on ennustav reegel ning kui hästi see kodeerib andmeid. Tuleneb see vanast teaduslikust printsiibist (Occhami habemenuga - kahest samavõrd heast teooriast parem on see mis on lihtsam).

ROC - Receiver Operator Curve - lubab hinnata klassifitseerijat ka siis kui on võimalik olla oma otsustustes kas rohkem või vähem põhjalik. Tegelikult tuleks optimeerida mingit kulufunktsiooni. Näiteks kõikide inimeste saatmine mingile meditsiinilisele uuringule on kallis, arst peaks suutma hinnata riskigruppi võimalikult täpselt. Kui risk on väike pole asi hull kui keegi jääb skriiningust välja. Samas kui risk on suur siis kahju kui keegi jääb välja võib olla suur.

Võimendamine (boosting) on meetod mis kombineerib palju "nõrku" ennustajaid et tõsta nende usaldusväärsust kombinatsioonis.

Muid meetodeid

Induktiivne loogiline programmeerimine on meetod mis lubab pöörata ümber loogilise programmeerimise teoreemitõestuse sammu... (vt. materjale).

Närvivõrgud said uue hoo sisse peale mitmetasemeliste (peidetud tasemed) närvivõrkude võidukäiku (sest perceptron ei oska "isegi" XOR tehet ära õppida).

Rakendusi

Struktureerimata andmete (tekstide) kaevandamine eesmärgiga leida seoseid, klassifitseerida, jne. Bioinformaatika on ala mis uurib bioloogiliste andmete analüüsi - neid andmeid on palju ja see on väga viljakas eriala rikkalike huvitavate probleemide poolest.

Meditsiini-informaatikas võib pidada peamiseks eesmärgiks õppida meditsiini-andmetest inimese tervisega seonduvat informatsiooni, õppida andme automaatselt diagnoose jne. Aga ka andmete haldamise kning isikute privaatsuse küsimused on seal väga tähtsal kohal.

Edit: header| contents| footer| sidebar