Entwicklung einer praxisnahen Theorie für Clusteringalgorithmen durch datengetriebene Modellierung und Analyse

• Antragsteller: Professor Dr. Johannes Blömer; Professor Dr. Christian Sohler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 47960847

Unter Clusteranalyse oder einfach Clustering versteht man die Partitionierung einer Menge von Objekten in Teilmengen von einander ahnlichen Objekten. Clustering-Algorithmen haben Anwendungen in der Datenkompression, Mustererkennung, Biologie, Analyse von Netzwerken, Stochastik, Textklassifikation und dem maschinellen Lernen, um nur einige Beispiele zu nennen. Die unterschiedlichen Anwendungen bestimmen auch, was unter ähnlichen Objekten zu verstehen ist. Einerseits existieren viele unterschiedliche in der Praxis erfolgreich eingesetzte Clustering-Algorithmen. Andererseits gibt es auch eine Vielzahl theoretischer Ergebnisse aus dem Bereich der theoretischen Informatik zum Clustering. Fast alle praktisch eingesetzten Algorithmen können jedoch nur unzureichend analysiert werden und die aus der Theorie stammenden Algorithmen sind nicht effizient genug für die Praxis. Wir wollen in diesem Projekt versuchen, diese Kluft zwischen Theorie und Praxis durch eine praxisorientierte Theorie für Clustering-Algorithmen zu schließen. Schwerpunkt soll dabei eine Modellierung und die hierauf aufbauende Algorithmenanalyse sein, die die Besonderheiten von Eingaben durch geeignete Parametrisierungen berücksichtigt.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering