The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Multiple Hypothesis Testing in Data Mining

Sami Hanhijärvi

Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the School of Science for public examination and debate in Auditorium AS1 at the Aalto University School of Science (Espoo, Finland) on the 11th of May 2012 at 12 noon.

Overview in PDF format (ISBN 978-952-60-4605-1)   [418 KB]
Dissertation is also available in print (ISBN 978-952-60-4604-4)

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.

This thesis consists of an overview and of the following 5 publications:

  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.
  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.
  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.
  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.
  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.

Keywords: data mining, multiple hypothesis testing, statistical significance testing, biclustering

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2012 Aalto University

Last update 2012-10-31