Felix Happach gewinnt Award

Mit dem Paper "Good Clusterings Have Large Volume" holt sich Doktorand Felix Happach den zweiten Preis beim Student Paper Prize der INFORMS (Institute for Operations Research and the Management Sciences) Optimization Society. Die Gesellschaft fördert den Austausch zwischen Praxis und Forschung mit dem Ziel, Optimierungsverfahren und -software zu entwickeln, die mathematische Probleme lösen.

Das Paper "Good Clusterings Have Large Volume" von Felix Happach und Steffen Borgwardt von der CU Denver erscheint demnächst beim INFORMS-Journal "Operations Research". Hauptresultat ist ein neues Qualitätsmaß für Clusterings, welches erstmals das besondere Verhalten bestimmter Clustering-Algorithmen erklärt.

Was ist Clustering?

Beim Clustering versuchen Mathematiker, eine Menge von Datenpunkten in ähnliche Teile zu partitionieren und dabei meist eine gegebene Zielfunktion zu maximieren oder minimieren. So lassen sich Ähnlichkeiten innerhalb großer Datenbestände erkennen. Damit ermöglichen Clustering-Algorithmen etwa maschinelles Lernen.

Ein einfaches Beispiel dafür ist die Handschrifterkennung: Ein Computer erhält Bilder von handgeschriebenen Buchstaben und die Information, um welchen Buchstaben es sich handelt. Die Bilder werden dann geclustert: ein Cluster für jeden Buchstaben. Anschließend kann der Computer bei einem neuen Bild verschiedene Kriterien - wie Form oder Anzahl der Striche - abgleichen und so das Bild einem Cluster zuordnen. Je mehr Bilder der Computer am Anfang hat, desto besser erkennt er später, um welchen Buchstaben es sich handelt.

Einer der bekanntesten und am meisten genutzten Algorithmen, um Clustering-Probleme zu lösen, ist der "k-means Algorithmus". Dieser liefert zwar in der Praxis in wenigen Schritten sehr gute Ergebnisse, theoretisch kann er jedoch beliebig schlecht werden. Dieses Verhalten war bisher mathematisch nicht zu erklären.

Good Clusterings Have Large Volume

Das Paper "Good Clusterings Have Large Volume" untersucht die Eigenschaften von optimalen Clusterings mithilfe eines hochdimensionalen geometrischen Objekts - eines Polytops. Anhand der Struktur dieses Polytops leiten Felix Happach und Steffen Borgwardt ein neues Qualitätsmaß her, das Volumen eines Clusters.

Dieses Maß spiegelt das widersprüchliche Verhalten des k-means Algorithmus wider und liefert gleichzeitig ein geometrisches Verfahren, um ein optimales Clustering anhand des Polytops zu berechnen. Langfristig könnten sich daraus vielleicht neue Algorithmen ergeben.

Felix Happach forscht auf dem Gebiet der kombinatorischen Optimierung und promoviert bei Andreas S. Schulz, Professor für Operations Research. Dieser hat ihn auch für den INFORMS Optimization Society Student Paper Prize nomiert. Für den zweiten Platz erhält er neben der Auszeichnung ein Preisgeld von 250 $.