Maschinelles Lernen und Data Mining in der Bioinformatik

 Am Mittwoch den 2.12.2009 findet wegen des Dies Academicus keine Vorlesung und Übung statt.

Methoden des Maschinellen Lernens und Data Minings wurden in den letzten Jahren immer mehr zu Schlüsseltechniken in der Bioinformatik. Das Maschinelle Lernen beschäftigt sich mit Algorithmen, die durch Erfahrung ihre Fähigkeit, eine Aufgabe zu lösen, verbessern können. Als Data Mining bezeichnet man den Datenanalyseschritt im Prozess der Entdeckung neuen Wissens in Datenbanken (Knowlege Discovery in Databases). Algorithmen des Maschinellen Lernens werden häufig im Data Mining eingesetzt. Ziel dieser Vorlesung ist, Techniken des Maschinellen Lernens und Data Minings sowie deren aktuelle Anwendungen in der Bioinformatik systematisch vorzustellen.

Zeugen der explosionsartigen Entwicklung auf dem Forschungsgebiet sind mehr als 40 Artikel, die unter diesen Stichwörtern seit Anfang des Jahres 2003 im Bioinformatics-Journal publiziert wurden. Der Grund für die besondere Bedeutung dieser Techniken für die Bioinformatik liegt darin, dass für die Beantwortung wichtiger wissenschaftlicher Fragen enorme Mengen experimenteller und anderer Daten (z.B. Text) analysiert werden müssen. Die Anwendungsmöglichkeiten umfassen u.a.:

• die Analyse von Genexpressionsdaten,
• die Klassifikation von Tumortypen und Toxicogenomics,
• die Erkennung entfernter Homologien,
• Sekundärstrukturvorhersage,
• Single-Nucleotide Polymorphisms (SNPs), und
• die Analyse von Proteomikdaten.

Die Vorlesung ist gemäß der zur Verfügung stehenden Techniken strukturiert. Im Anschluß an die Erklärung der jeweiligen Technik wird deren Anwendung in realen Projekten präsentiert. Die Beschreibung der Anwendung ist dabei der aktuellen Bioinformatikliteratur entnommen.

Der Schwerpunkt der Lehrveranstaltung liegt auf Mustern und Modellen, die von menschlichen Experten inspiziert und interpretiert werden können. Methoden, die ausschließlich Black-Box Modelle liefern, werden in der Vorlesung nicht behandelt. Für die  Vorlesung nehmen wir des weiteren an, dass die Daten in einer Tabelle gegeben sind, wobei jede Zeile einer Beobachtung  entspricht. Die Analyse strukturierter Daten wird Gegenstand einer Vorlesung im Wintersemester sein. Nicht behandelt werden Techniken, die bereits an anderer Stelle ausführlich erklärt wurden, z.B. Hidden Markov Models (HMMs) und Neuronale Netze (ANNs), wobei Support Vector Machines (SVMs) bestimmte Arten von Neuronalen Netzen darstellen können. Der genaue Aufbau der Vorlesung ist durch inhaltliche und technische Zusammenhänge motiviert. Die Übung wird sowohl theoretische als auch praktische Aspekte der Vorlesung vertiefen. Im praktischen Teil wird eine Data-Mining-Workbench auf reale biologische Daten angewendet. Die Veranstaltung ist so angelegt, dass interessierte Studierende des Studiengangs Informatik problemlos folgen können sollten und neben einer umfangreichen Einführung in das Maschinelle Lernen und Data Mining auch deren zahlreichen Anwendungen in der Bioinformatik kennenlernen können.

Die in der Vorlesung behandelten Themen und Techniken sind im Detail:

• Overview of course and definitions
• Overview from a biological perspective
• Concept learning: version spaces, find-S, candidate elimination algorithm
• Introduction to data mining, levelwise algorithm/Apriori, borders, episode rules, heuristic search, measures (j-measure, conviction, leverage, lift, etc.), complexity, FP trees, MaxMiner, constraint-based mining, condensed representations
• Clustering (hierarchical agglomerative/divisive, CobWeb, k-means, model-based/EM, CLICK, SOMs)
• Evaluation and validation (hold-out, cross-validation, ROC and lift curves, numeric error measures, etc)
• Bayesian learning: Naive Bayes, Bayesian networks (representation, d-separation, inference, junction tree algorithm, learning, EM, structural EM)
• Instance-based learning: k-nearest neighbor, kd-trees, locally weighted regression, radial-basis function networks, case-based reasoning, lazy learning
• Support vector machines
• Decision trees (C4.5, CART), regression trees, pruning methods
• Rule learning (C4.5 rules, AQ, CN2, IREP, RIPPER, PART, SLS, theory)
• Computational learning theory, bias and variance
• Ensemble methods (bagging, boosting, stacking, random forests, SLIPPER)
• Genetic algorithms (basic algorithm, schema theorem, genetic programming, Baldwin effect)

Bücher:

• Machine Learning, T. Mitchell, McGraw Hill, 1997.
• Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, I. Witten, E. Frank, Morgan Kaufmann Publishers, 2000.
• Principles of Data Mining, D. Hand, P. Smyth, H. Mannila, MIT Press, 2000.
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction, T. Hastie, R. Tibshirani, J.H. Friedman, Springer, 2001.

Die Beschreibungen der Anwendungen in der Bioinformatik stammen direkt aus der aktuellen Literatur (Bioinformatics-Journal, Journal of Molecular Biology, Journal of Computational Biology, PNAS, etc).