Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

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.

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.