haku: @keyword tiedon louhinta / yhteensä: 16
viite: 8 / 16
Tekijä: | Ukkonen, Antti |
Työn nimi: | Data mining techniques for discovering partial orders |
Tiedonlouhintamenetelmiä osittainjärjestysten etsintään | |
Julkaisutyyppi: | Diplomityö |
Julkaisuvuosi: | 2004 |
Sivut: | 77 s. Kieli: eng |
Koulu/Laitos/Osasto: | Tietotekniikan osasto |
Oppiaine: | Informaatiotekniikka (T-122) |
Valvoja: | Mannila, Heikki |
Ohjaaja: | Mannila, Heikki |
Digitoitu julkaisu: | https://aaltodoc.aalto.fi/handle/123456789/92338 |
OEVS: | Digitoitu arkistokappale on julkaistu Aaltodocissa
|
Sijainti: | P1 Ark Aalto | Arkisto |
Avainsanat: | data mining partial order ranking clustering frequent itemset simulated annealing tiedon louhinta osittainjärjestys järjestys klusterointi kattava joukko simuloitu jäähdytys |
Tiivistelmä (fin): | Olkoon jonkin mielivaltaisen prosessin lopputulos joukko S joukon SIGMA alkioiden järjestyksiä. Nämä järjestykset voivat koskea kaikkia SIGMA:n alkioita tai vain jotakin sen osajoukkoa. Oletetaan, että kaikki järjestykset joukossa S ovat tuntemattomien osittainjärjestysten generoimia. Järjestys on osittainjärjestyksen P generoima, mikäli se on P:n lineaarinen laajennus tai voidaan muodostaa sellaisesta jättämällä joitakin SIGMA:n alkioita pois. Tässä diplomityössä suunnitellaan algoritmeja näiden piilevien osittainjärjestysten etsintään. Menetelmillä ei ole osittainjärjestyksistä a priori tietoa ja ne käsittelevät ainoastaan joukkoa S. Yhden ja useamman osittainjärjestyksen etsintä tehdään erikseen. Yhden osittainjärjestyksen löytämiseksi esitellään algoritmi GREEDY-ORDER. Tämä algoritmi maksimoi kustannusfunktiota lisäämällä konstruoitavaan osittainjärjestykseen vain sellaiset järjestetyt parit (i, j), joiden frekvenssi on suurempi kuin päinvastaisella järjestyksellä (j, i). Useamman osittainjärjestyksen etsintä ratkaistaan ryhmittelemällä S ensin siten, että samaan ryhmään kuuluvat järjestykset ovat saman osittainjärjestyksen generoimia. Lopuksi GREEDY-ORDER algoritmia sovelletaan kuhunkin ryhmään. Ryhmittelyä varten esitetään kaksi menetelmää. Ensimmäinen vaihtoehto perustuu syötettä S esittävän tietokannan suljettujen kattavien joukkojen laskentaan ja näiden perusteella määriytyvän joukon peitto-ongelman ratkaisemiseen. Toinen menetelmä perustuu paikalliseen hakuun kaikkien mahdollisten ryhmittelyjen joukosta. Haussa pyritään maksimoimaan sopivaa painofunktiota, mikä tapahtuu joko hill climbing -algoritmilla tai simuloidulla jäähdytyksellä. |
ED: | 2005-02-24 |
INSSI tietueen numero: 28100
+ lisää koriin
INSSI