Data mining techniques for discovering partial orders

Abstract

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ä.