search query: @author Ukkonen, Antti / total: 2
reference: 2 / 2
« previous | next »
Author: | Ukkonen, Antti |
Title: | Data mining techniques for discovering partial orders |
Tiedonlouhintamenetelmiä osittainjärjestysten etsintään | |
Publication type: | Master's thesis |
Publication year: | 2004 |
Pages: | 77 s. Language: eng |
Department/School: | Tietotekniikan osasto |
Main subject: | Informaatiotekniikka (T-122) |
Supervisor: | Mannila, Heikki |
Instructor: | Mannila, Heikki |
Digitized copy: | https://aaltodoc.aalto.fi/handle/123456789/92338 |
OEVS: | Digitized archive copy is available in Aaltodoc
|
Location: | P1 Ark Aalto | Archive |
Keywords: | data mining partial order ranking clustering frequent itemset simulated annealing tiedon louhinta osittainjärjestys järjestys klusterointi kattava joukko simuloitu jäähdytys |
Abstract (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 record number: 28100
+ add basket
« previous | next »
INSSI