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

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.