Projekt

Zurück zur Übersicht

Significant Pattern Mining

Titel Englisch Significant Pattern Mining
Gesuchsteller/in Borgwardt Karsten
Nummer 155913
Förderungsinstrument SNSF Starting Grants
Forschungseinrichtung Departement für Biosysteme und Ingenieurwissenschaften ETH Zürich (01.06.2014 - 01.06.2045 )
Hochschule ETH Zürich - ETHZ
Hauptdisziplin Informatik
Beginn/Ende 01.05.2015 - 30.04.2020
Bewilligter Betrag 1'420'850.00
Alle Daten anzeigen

Keywords (7)

Graph Mining, Correlation Search, Pattern Mining, Big Data, Computer Science , Multiple Testing, Data Mining

Lay Summary (Deutsch)

Lead
Unsere Gesellschaft setzt große Hoffnungen auf 'Big Data': Durch die Analyse großer Datenmengen sollen bisher unbekannte Zusammenhänge entdeckt werden, die zur Verbesserung fast aller Lebensbereiche, vom Verkehrwesen bis zur Gesundheitsversorgung, beitragen. Bei der Suche nach Mustern in Big Data gibt es jedoch ein gravierendes wiederkehrendes Problem: Welche Muster hat der Zufall in diesen gigantischen “Datenbergen” erzeugt und welche stellen statistisch-signifikante Beobachtungen dar? Es herrscht ein Mangel an statistisch-fundierten Ansätzen, um diese Unterscheidung effizient auf großen Datenmengen durchführen zu können. Dieses Projekt widmet sich der Entwicklung und Erforschung solcher Ansätze.
Lay summary

Inhalt und Ziel des Forschungsprojekts

Unsere Gesellschaft setzt große Hoffnungen auf Big Data: Durch die Analyse großer Datenmengen sollen bisher unbekannte Zusammenhänge entdeckt werden, die zur Verbesserung fast aller Lebensbereiche, vom Verkehrwesen bis zur Gesundheitsversorgung, beitragen.

Bei der Suche nach Mustern in Big Data  gibt es jedoch ein gravierendes wiederkehrendes Problem: Welche Muster hat der Zufall in diesen gigantischen “Datenbergen” erzeugt und welche stellen statistisch-signifikante Beobachtungen dar?   Es herrscht ein Mangel an statistisch-fundierten Ansätzen, um diese Unterscheidung effizient auf großen Datenmengen durchführen zu können.

In diesem Projekt wollen wir neue Algorithmen entwickeln, die statistisch-signifikante Muster in großen Datenmengen entdecken können. Der Schlüssel zum Erfolg werden neue Algorithmen sein, die besonders effizient zu berechnen sind, teure Zwischenschritte vermeiden, die Anzahl der potenziellen Muster frühzeitig reduzieren und Abhängigkeiten zwischen den Mustern geschickt ausnutzen, um die nötigen Berechnungen zu beschleunigen.

                

Wissenschaftlicher und gesellschaftlicher Kontext des Forschungsprojekts    

Unsere Arbeit wird neue Algorithmen hervorbringen, um Muster in Big Data zu erkennen, und daraus neues Wissen über die zugrundeliegenden Systeme zu generieren. Sie ist daher für eine Vielzahl von Disziplinen, die Big Data nutzen, von Bedeutung, von der Logistik über das Finanzwesen bis hin zur Gesundheitsversorgung.  Gleichzeitig ergänzt unser Projekt nationale Vorhaben zur Stärkung der Forschung über “Big Data” in der Schweiz, wie z.B. das nationale Forschungsprogramm “Big Data” des Staatssekretariats für Bildung, Forschung und Innovation (SBFI).
Direktlink auf Lay Summary Letzte Aktualisierung: 26.08.2015

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
Halting in Random Walk Kernels
Sugiyama Mahito, Borgwardt Karsten (2015), Halting in Random Walk Kernels, in Advances in Neural Information Processing Systems 28, Montréal, CanadaCurran Associates, Inc., Red Hook, NY.
Finding significant combinations of features in the presence of categorical covariates
Papaxanthos Laetitia, Llenares-López Felipe, Bodenham Dean, Borgwardt Karsten (2016), Finding significant combinations of features in the presence of categorical covariates, in Advances in Neural Information Processing Systems 29, BarcelonaCurran Associates, Inc., Red Hook, NY.
Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing
Llinares-López Felipe, Sugiyama Mahito, Papaxanthos Laetitia, Borgwardt Karsten (2015), Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing, in the 21th ACM SIGKDD International Conference, Sydney, NSW, AustraliaACM, New York.
Genome-wide detection of intervals of genetic heterogeneity associated with complex traits
Llinares-López Felipe, Grimm Dominik G., Bodenham Dean A., Gieraths Udo, Sugiyama Mahito, Rowan Beth, Borgwardt Karsten (2015), Genome-wide detection of intervals of genetic heterogeneity associated with complex traits, in Bioinformatics, 31(12), i240-i249.
Significant Subgraph Mining with Multiple Testing Correction
Sugiyama Mahito, López Felipe Llinares, Kasenburg Niklas, Borgwardt Karsten M. (2015), Significant Subgraph Mining with Multiple Testing Correction, in Proceedings of the 2015 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, Philadelphia, PA.
Genome-wide genetic heterogeneity discovery with categorical covariates
Llinares-López Felipe, Papaxanthos Laetitia, Bodenham Dean, Roqueiro Damian, Borgwardt Karsten (accepted), Genome-wide genetic heterogeneity discovery with categorical covariates, in Bioinformatics.

Zusammenarbeit

Gruppe / Person Land
Felder der Zusammenarbeit
Mahito Sugiyama, National Institute of Informatics Japan (Asien)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation

Wissenschaftliche Veranstaltungen

Aktiver Beitrag

Titel Art des Beitrags Titel des Artikels oder Beitrages Datum Ort Beteiligte Personen
Distinguished Speaker Series at the Center for Bioinformatics Einzelvortrag Combinatorial Association Mapping 10.05.2017 Saarbrücken, Deutschland Borgwardt Karsten
IBT seminar at the Institute for Biomedical Engineering at ETH Zürich Einzelvortrag Network Mining in Biology and Medicine 25.04.2017 Zürich, Schweiz Borgwardt Karsten
Alfried Krupp-Symposium "From Machine Learning to Personalized Medicine" Vortrag im Rahmen einer Tagung Significant Pattern Mining for Biomarker Discovery 21.10.2016 München, Deutschland Llinares Lopez Felipe
Felix Klein Conference "Mathematical Methods in Big Data" at the Fraunhofer Institute for Industrial Mathematics ITWM Vortrag im Rahmen einer Tagung Machine Learning for Personalized Medicine 30.09.2016 Kaiserslautern, Deutschland Borgwardt Karsten
ECCB workshop on "Complex Network Analysis for Precision Medicine" Vortrag im Rahmen einer Tagung Network Mining for Personalized Medicine 03.09.2016 The Hague, Niederlande Borgwardt Karsten
Computational Biology (BC2) seminar at the Biozentrum at the University of Basel Einzelvortrag Machine Learning for Personalized Medicine 25.04.2016 Basel, Schweiz Llinares Lopez Felipe
Computer Science Colloquium of the University of Basel Einzelvortrag Significant Pattern Mining 21.04.2016 Basel, Schweiz Borgwardt Karsten
Seminar at TU Dortmund Einzelvortrag Significant Pattern Mining 12.11.2015 Dortmund, Deutschland Borgwardt Karsten
Meeting of the Competence Center for Personalized Medicine of ETH Zürich & the University of Zürich at Kartause Ittingen Vortrag im Rahmen einer Tagung Machine Learning for Personalized Medicine 02.11.2015 Ittingen, Schweiz Borgwardt Karsten


Kommunikation mit der Öffentlichkeit

Kommunikation Titel Medien Ort Jahr
Medienarbeit: Printmedien, Online-Medien ETH Zürich ernennt Professor für Data Mining Netzwoche Deutschschweiz 2017
Medienarbeit: Printmedien, Online-Medien Augmented Science SNF Journal "Horizonte" Deutschschweiz Italienische Schweiz Romanische Schweiz Westschweiz 2017

Auszeichnungen

Titel Jahr
One of the "Top 40 under 40" in Science in Germany, according to Business Journal Capital 2015
One of the "Top 40 under 40" in Science in Germany, according to Business Journal Capital 2016

Abstract

Data Mining, the search for new knowledge in form of statistical depedencies and patterns in big data sets, is omnipresent in modern society, in science and technology as much as in industry and finance. One of its most important branches is Pattern Mining, that is finding groups of co-occuring elements in a collection of sets. For instance, keywords that co-occur in many documents may form a pattern, or groups of atoms that reoccur in molecules with a particular biological function. Data Mining has brought about a huge body of literature on how to efficiently discover such patterns, even in very large datasets. An unresolved open question is, however, to decide whether a given pattern is not only frequent, but statistically significantly enriched in a particular dataset or class of objects. This question is of essential relevance to all application domains of pattern mining, in particular the life sciences, as they are interested in selecting patterns for further experimental investigation and validation. It is our goal in this project to give an answer to this open problem of significant pattern mining. The reason why this important question remains unanswered so far is the multiple hypothesis testing problem: when assessing statistical significance, one has to account for the enormous number of hypotheses that were tested in the discovery process. While Statistics has developed numerous approaches to multiple hypotheses correction, their application is extremely difficult in Pattern Mining. This is due to the fact that even simple statistics, such as the number of tests, may be challenging to compute and that correcting for the huge number of tests performed may result in loss of statistical power in detecting true patterns. In this project, we propose strategies for Pattern Mining with multiple testing correction that preserve statistical power. Key to this breakthrough will be novel algorithms that avoid to compute expensive intermediate results, exclude non-testable hypotheses and exploit dependencies between tests. In this manner we plan to solve one of the big open problems in Data Mining.