Testing the significance of patterns with complex null hypotheses

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2012-02-18
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2012
Major/Subject
Mcode
Degree programme
Language
en
Pages
178
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 11/2012
Abstract
In data mining large amounts of data are searched through for useful information, pieces of which are called patterns. Significance testing is an important part of this task as the found patterns need to be assessed for their relevance and significance before further actions. Advances in science have brought along the need to evaluate the significance of complicated data patterns within complicated datasets. Significance testing has been historically conducted with specialized methods that cannot be adapted to new applications and many of these methods have problems with their theoretical justification. This thesis suggests using the framework of property-based randomization for building reliable and flexible significance testing tools that can be adapted and extended for a wide variety of applications. The concepts of representation-based randomization and iterative pattern mining are also discussed as ways to enlarge the scope of these tools. The final chapter of the thesis makes a review of the use of these general ideas in various applications such as databases and time series collections. The publications of the thesis are discussed along with selected introductions to other randomization methods that have been proposed.

Tiedonlouhinnassa käydään läpi suuria tietomääriä ja etsitään niistä hyödyllistä informaatiota. Merkitsevyystestaus on keskeinen osa tätä tehtävää, sillä löydettyjen tiedonjyvien oleellisuus ja merkitsevyys tulee tarkistaa ennen jatkotoimenpiteitä. Tieteen kehittyessä on muodostunut tarpeelliseksi etsiä entistä monimutkaisempia rakenteita tietojoukoista, joiden koko on samalla kasvanut. Historiallisesti merkitsevyystestaamista varten on usein käytetty erikoistuneita menetelmiä, joita on ollut vaikea sovittaa uusiin ongelmiin. Lisäksi monia näistä menetelmistä on vaikeaa perustella teoreettisesti. Tämä väitöskirja ehdottaa yleistä merkitsevyystestauksen mallia, jossa tietolähteen ominaisuuksille perustuvista nollamalleista rakennetaan erikoistuneita, mutta samalla luotettavia ja erityisen hyvin muokattavia merkitsevyystestausmenetelmiä. Tämän yleisen mallin käyttömahdollisuuksia laajennetaan vielä lisäksi esityspohjaisen satunnaistuksen ja iteratiivisen merkitsevyystestauksen ratkaisuilla. Työn viimeisessä osassa tämän yleisen mallin toimintaa esitellään monipuolisella joukolla sovelluksia esimerkiksi tietokannoille ja aikasarjakokoelmille. Väitöskirjan julkaisut esitellään yleisellä tasolla yhdistämällä niiden sisältö muihin ehdotettuihin satunnaistusmenetelmiin.
Description
Supervising professor
Mannila, Heikki
Thesis advisor
Kaski, Petteri
Keywords
data mining, significance testing, randomization, null hypothesis, null model, Markov chain Monte Carlo, frequent pattern, clustering, classification, time series, tiedonlouhinta, merkitsevyystestaus, satunnaistus, nollahypoteesi, nollamalli, MCMC, usein toistuva hahmo, ryvästys, luokittelu, aikasarjat
Other note
Parts
  • [Publication 1]: Markus Ojala, Niko Vuokko, Aleksi Kallio, Niina Haiminen, and Heikki Mannila. 2009. Randomization methods for assessing data analysis results on real-valued matrices. Statistical Analysis and Data Mining, volume 2, number 4, pages 209-230. doi:10.1002/sam.10042.
  • [Publication 2]: Sami Hanhijärvi, Markus Ojala, Niko Vuokko, Kai Puolamäki, Nikolaj Tatti, and Heikki Mannila. 2009. Tell me something I don't know: Randomization strategies for iterative data mining. In: John Elder, Françoise Soulié Fogelman, Peter Flach, and Mohammed Zaki (editors). Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2009). Paris, France. 28 June - 1 July 2009. New York, NY, USA. Association for Computing Machinery. Pages 379-388. ISBN 978-1-60558-495-9. doi:10.1145/1557019.1557065. © 2009 Association for Computing Machinery (ACM). By permission.
  • [Publication 3]: Niko Vuokko and Petteri Kaski. 2010. Testing the significance of patterns in data with cluster structure. In: Geoffrey I. Webb, Bing Liu, Chengqi Zhang, Dimitrios Gunopulos, and Xindong Wu (editors). Proceedings of the 10th IEEE International Conference on Data Mining (ICDM 2010). Sydney, Australia. 14-17 December 2010. IEEE. Pages 1097-1102. ISBN 978-1-4244-9131-5. doi:10.1109/ICDM.2010.61. © 2010 Institute of Electrical and Electronics Engineers (IEEE). By permission.
  • [Publication 4]: Niko Vuokko and Petteri Kaski. 2011. Significance of patterns in time series collections. In: Bing Liu, Huan Liu, Chris Clifton, Takashi Washio, and Chandrika Kamath (editors). Proceedings of the 11th SIAM International Conference on Data Mining (SDM 2011). Mesa, Arizona, USA. 28-30 April 2011. Philadelphia, Pennsylvania, USA. Society for Industrial and Applied Mathematics. Pages 676-686. ISBN 978-0-89871-992-5. doi:10.1137/1.9781611972818.58.
  • [Publication 5]: Aleksi Kallio, Niko Vuokko, Markus Ojala, Niina Haiminen, and Heikki Mannila. 2011. Randomization techniques for assessing the significance of gene periodicity results. BMC Bioinformatics, volume 12, 330, 14 pages. doi:10.1186/1471-2105-12-330. © 2011 by authors.
Citation