Knowledge mining using robust clustering

Abstract

FM Sami Äyrämö tutki väitöstyössään suurten digitaalisten tietomassojen tehokasta hyödyntämistä ja siihen sovellettavia laskennallisesti älykkäitä niin kutsuttuja tiedonlouhintamenetelmiä (data mining). Aihe on ajankohtainen, sillä informaatiojärjestelmien nopea kehittyminen ja yleistyminen johtavat entistä useammin ”datatulvaan": digitaalisessa muodossa kerätään tietoa niin paljon, että oleellinen informaatio voi hukkua epäoleellisen ja moninkertaisen tiedon sekaan.Väitöstyönsä päätuloksena Äyrämö esittelee luotettavan, laskennallisesti tehokkaan ja käyttäjälle yksinkertaisen klusterointimenetelmän, joka ei ota kantaa sovelluskohteeseen ja on siten hyvin yleiskäyttöinen. Menetelmän pohjana Äyrämö on käyttänyt niin sanottuja prototyyppipohjaisia osittavia klusterointialgoritmeja.Usein tietovarastot ovat liian suuria selailtavaksi manuaalisesti tietokoneella. Datan klusteroinnin tavoitteena on löytää datasta ryhmiä eli klustereita, joiden sisällä havainnot ovat mahdollisimman samanlaisia ja erot ryhmien välillä mahdollisimman suuria. Näin voidaan yksittäisten havaintojen sijaan tarkastella joko ryhmien tai niitä parhaiten kuvaavien havaintojen eli prototyyppien ominaisuuksia.Äyrämön menetelmässä luotettavuus on saavutettu soveltamalla prototyyppien laskentaan niin sanottuja robusteja moniulotteisia estimaatteja, jotka eivät reagoi yhtä herkästi datassa esiintyvään virheisiin ja puutteisiin kuin perinteisemmät vaihtoehdot.Osaksi klusterointimenetelmää Äyrämö on kehittänyt niin kutsuttuun SOR-menetelmään perustuvan iteratiivisen algoritmin, jolla prototyyppiestimaatteja voidaan tehokkaasti ja tarkasti approksimoida. Klusterointimenetelmä kaikkine komponentteineen on toteutettu niin, että loppukäyttäjän ei tarvitse tehdä monimutkaisia esikäsittelyoperaatioita, kuten puuttuvien arvojen ennustamista, ennen varsinaista ryhmittelyä. Menetelmään on myös toteutettu alustusmenetelmä, joka automatisoi menetelmää tuottamalla ryhmittelyalgoritmin parametreille mahdollisimman hyvät alkuarvaukset.

This work is devoted to the development of scalable and robust algorithms for data mining and knowledge discovery problems. The main interest lies in so-called prototype-based clustering methods that are implemented using iterative relocation algorithms. Different elements of prototype-based data clustering are discussed and basic algorithms are described. In order to support the usability of the new methods and algorithms, a modified knowledge mining process model is also proposed. The refined model is based on the well-known knowledge discovery process, but it emphasizes more domain analysis and ''black box'' nature of data mining. Significance and importance of knowledge mining are clarified by outlining the current body of the existing knowledge with real applications.As the main outcome of this thesis, a highly automated robust clustering method is presented. The method consists of a number of separately developed and tested elements such as initialization, prototype estimation, and missing data strategy. Non-smooth nature of the robust statistics is rigorously considered from the point of view of non-smooth optimization. Numerical and statistical properties, such as robustness, scalability, computational and statistical efficiency, of the presented methods are tested and illustrated through a number of numerical experiments. The results are completed with some analytic results and illustrative real-world examples. Furthermore, in order to estimate the correct number of clusters, a new proposal of a cluster validity index is given.