Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

 dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, tietojenkäsittelytieteen laitos fi dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, institutionen för datavetenskap sv dc.contributor University of Helsinki, Faculty of Science, Department of Computer Science en dc.contributor.author Miettinen, Pauli dc.date.accessioned 2010-11-25T12:16:45Z dc.date.available 2010-11-25T12:16:45Z dc.date.issued 2009-05-20 dc.identifier.uri URN:ISBN:978-952-10-5498-3 fi dc.identifier.uri http://hdl.handle.net/10138/21376 dc.description.abstract Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data. en dc.description.abstract Ihmisten kyky tuottaa ja varastoida tietoa on kasvanut huimasti: yhä tarkemmat ja lukuisammat mittalaitteet tallentavat jatkuvasti tietoa ympäröivästä maailmasta ja yhtä lailla yhä useammat ihmiset tuottavat yhä enemmän sisältöä Internetiin esimerkiksi blogien ja keskustelupalstojen avulla. Mutta ihmisen kyky käsitellä informaatiota ei kasva samaan tahtiin informaation lisääntymisen kanssa. Internetin hakukoneet ovat tunnetuin menetelmä suurien tietomassojen hallintaan tarjoten käyttäjilleen mahdollisuuden hakea käyttäjää kiinnostavaa tietoa Internetistä. Mutta entä jos käyttäjä ei tiedä, minkälaista informaatiota hänellä on käytettävissään ja mikä siinä saattaisi kiinnostaa häntä? Tiedonlouhinta on tietojenkäsittelytieteen ala, joka pyrkii kehittämään menetelmiä sellaisen kiinnostavan tiedon löytämiseksi, josta käyttäjä ei ollut edes tietoinen. Väitöstyössä tutkitaan eräiden matriisihajotelmien käyttöä tiedonlouhinnassa. Matriiseja käytetään yleisesti tiedon esitys- ja tallennusmuotona. Mutta tällaiset matriisit ovat usein liian isoja ihmisten käsiteltäväksi. Matriisihajotelma esittää annetun matriisin useamman matriisin tulona. Jos nämä matriisit valitaan niin, että ne ovat riittävän pieniä ja helposti tulkittavia, voidaan alkuperäisestä datasta oppia paljon sellaista, minkä löytäminen dataa itseään tutkimalla olisi mahdollisesti ollut huomattavan vaikeaa. Väitöstyössä tutkitaan kolmea erilaista matriisihajotelmaa, jotka soveltuvat eri tilanteisiin. Työ on luonteeltaan perustutkimusta ja työn tulokset luonteeltaan kaksijakoisia. Yhtäältä väitöstyössä osoitetaan, että optimaalisten matriisihajotelmien löytäminen tehokkaasti on nykytietämyksen valossa mahdotonta, ja että jopa likimääräisten vastausten löytäminen on vaikeaa. Toisaalta tutkittujen matriisihajotelmien löytämiseksi esitetään tehokkaita algoritmeja, ja vaikka nämä algoritmit eivät edellisten tulosten nojalla voikaan olla optimaalisia, väitöstyössä suoritetut empiiriset kokeet osoittavat niiden toimivan hyvin sekä tarkoitusta varten luoduilla että todellisilla aineistoilla. fi dc.language.iso en dc.publisher Helsingin yliopisto fi dc.publisher Helsingfors universitet sv dc.publisher University of Helsinki en dc.relation.isformatof URN:ISBN:978-952-10-5497-6 fi dc.relation.isformatof Helsinki: 2009, Department of Computer Science, Series of Publications A. 1238-8645 fi dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv dc.subject tietojenkäsittelytiede fi dc.title Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms en dc.title.alternative Matriisihajotelmamenetelmiä tiedonlouhintaan : laskennallinen vaativuus ja algoritmeja fi dc.type.ontasot Väitöskirja (monografia) fi dc.type.ontasot Doctoral dissertation (monograph) en dc.type.ontasot Doktorsavhandling (monografi) sv dc.ths Mannila, Heikki dc.opn Orponen, Pekka dc.type.dcmitype Text