Multiple hypothesis testing in data mining

Loading...
Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2012-05-11
Checking the digitized thesis and permission for publishing
Instructions for the author

Date

2012

Major/Subject

Mcode

Degree programme

Language

en

Pages

170

Series

Aalto University publication series DOCTORAL DISSERTATIONS, 51/2012

Abstract

Data mining methods seek to discover unexpected and interesting regularities, called patterns, in presented data sets. However, the methods often return a collection of patterns for any data set, even a random one. Statistical significance testing can be applied in these scenarios to select the surprising patterns that do not appear as clearly in random data. As each pattern is tested for significance, a set of statistical hypotheses are considered simultaneously. The multiple comparison of several hypotheses simultaneously is called multiple hypothesis testing, and special treatment is required to adequately control the probability of falsely declaring a pattern statistically significant. However, the traditional methods for multiple hypothesis testing can not be used in data mining scenarios, because these methods do not consider the problem of varying set of hypotheses, which is inherent in data mining. This thesis provides an introduction to the problem and reviews some published work on the subject. The focus is in multiple hypothesis testing and specifically in data mining. The problems with traditional multiple hypothesis testing methods in data mining scenarios are discussed, and a solution to these problems is presented. The solution uses randomization, which involves drawing samples of random data sets and using the data mining algorithm with them. The results on the random data sets are then compared with the results on the original data set. Randomization is introduced and discussed in general, and possible randomization schemes in different data mining scenarios are presented. The solution is applied in iterative data mining and biclustering scenarios. Experiments are carried out to display the utility in these applications.

Tiedonlouhinnan menetelmillä pyritään löytämään annetusta aineistosta yllättäviä ja mielenkiintoisia säännönmukaisuuksia, joita kutsutaan hahmoiksi. Useat menetelmät kuitenkin löytävät hahmoja kaikista aineistoista, jopa täysin satunnaisista. Näissä tilanteissa voidaan käyttää tilastollista testausta valitsemaan yllättävät hahmot, jotka eivät esiinny yhtä vahvasti satunnaisessa aineistossa. Monen hahmon tilastollista merkittävyyttä testatessa käsitellään samalla yhdenaikaisesti joukkoa tilastollisia hypoteesejä. Usean hypoteesin yhdenaikaista testausta kutsutaan monen hypoteesin testaamiseksi, joka vaatii erityistoimenpiteitä, jotta väärien johtopäätösten todennäköisyyttä voidaan hallita. Kuitenkaan tyypillisiä monen hypoteesin testausmenetelmiä ei voida käyttää tiedonlouhinnassa, koska ne eivät ota huomioon tiedonlouhinnassa tyypillistä vaihtelevan hypoteesijoukon ongelmaa. Tämä väitöskirja esittelee ongelman ja tarkastelee aiheeseen liittyviä julkaisuja. Kirja keskittyy monen hypoteesin testaamiseen erityisesti tiedonlouhinnan tilanteissa. Tyypillisten monen hypoteesin testaamiseen käytettävien menetelmien ongelmia tiedonlouhinnassa käsitellään, ja ongelmiin esitetään ratkaisu. Tämä perustuu satunnaistukseen, jossa luodaan satunnaisia aineistoja ja käytetään tiedonlouhinnan menetelmää näihin aineistoihin. Saatuja tuloksia verrataan alkuperäisestä aineistosta saatuihin tuloksiin. Satunnaistaminen esitellään yleisesti ja käsitellään mahdollisia satunnaistamismenetelmiä erilaisissa tiedonlouhinnan tilanteissa. Esitettyä ratkaisua käytetään iteratiivisessa tiedonlouhinnassa ja kaksoisryhmittelyssä, joissa kokeellisesti myös osoitetaan ratkaisun hyöty.

Description

Supervising professor

Mannila, Heikki, Prof
Rousu, Juho, Prof

Thesis advisor

Puolamäki, Kai, Dr

Keywords

data mining, multiple hypothesis testing, statistical significance testing, biclustering, tiedonlouhinta, monen hypoteesin testaus, tilastollinen testaus, kaksoisryhmittely

Other note

Parts

  • [Publication 1]: Sami Hanhijärvi. 2011. Multiple hypothesis testing in pattern discovery. In: Tapio Elomaa, Jaakko Hollmén, and Heikki Mannila (editors). Proceedings of the 14th International Conference on Discovery Science (DS 2011). Espoo, Finland. 5-7 October 2011. Berlin / Heidelberg, Germany. Springer. Lecture Notes in Artificial Intelligence, Subseries of Lecture Notes in Computer Science, volume 6926, pages 122-134. ISBN 978-3-642-24476-6. ISSN 0302-9743.
  • [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. ACM. Pages 379-388. ISBN 978-1-60558-495-9. © 2009 Association for Computing Machinery (ACM). By permission.
  • [Publication 3]: Sami Hanhijärvi, Gemma C. Garriga, and Kai Puolamäki. 2009. Randomization techniques for graphs. In: Proceedings of the 9th SIAM International Conference on Data Mining (SDM 2009). Sparks, Nevada, USA. 30 April - 2 May 2009. Society for Industrial and Applied Mathematics. Pages 780-791. © 2009 Society for Industrial and Applied Mathematics (SIAM). By permission.
  • [Publication 4]: Kai Puolamäki, Sami Hanhijärvi, and Gemma C. Garriga. 2008. An approximation ratio for biclustering. Information Processing Letters, volume 108, number 2, pages 45-49. © 2008 Elsevier. By permission.
  • [Publication 5]: Sami Hanhijärvi and Aleksi Kallio. 2012. Biclustering gene expression data with minimum description length. Technical report. Espoo, Finland: Aalto University, School of Science, Department of Information and Computer Science. 38 pages. Aalto University publication series SCIENCE + TECHNOLOGY 9/2012. Aalto-ST-9/2012. ISBN 978-952-60-4590-0. ISSN 1799-490X. © 2012 by authors.

Citation