Data mining techniques for discovering partial orders

Thumbnail Image

Files

master_Ukkonen_Antti_2004.pdf (28.37 MB)

URL

Journal Title

Journal ISSN

Volume Title

Helsinki University of Technology | Master's thesis
Location:
P1 Ark Aalto
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2004

Department

Tietotekniikan osasto

Major/Subject

Informaatiotekniikka

Mcode

T-122

Degree programme

Language

en

Pages

77 s.

Series

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

Description

Supervisor

Mannila, Heikki

Thesis advisor

Mannila, Heikki

Keywords

data mining, tiedon louhinta, partial order, osittainjärjestys, ranking, järjestys, clustering, klusterointi, frequent itemset, kattava joukko, simulated annealing, simuloitu jäähdytys

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-2020120451173

Collections

[dipl] Teknillinen korkeakoulu / TKK