Mathematik-Gebäude, Seminarraum M511

Partitionen hochdimensionaler Punktmengen in Cluster, die bestimmte Separationseigenschaften erfüllen, werden in einem breiten Anwendungsfeld benötigt, das vom Operations Research zum Machine Learning reicht. Für viele Praxisprobleme müssen die Cluster zudem Größenrestriktionen erfüllen. Wir studieren geometrische Körper, die mit solchen Clustering-Problemen zusammenhängen, um Einblick in ihre kombinatorische Struktur zu erhalten:
Wir charakterisieren die Ecken von ``Schwerpunktpolytopen`` als zugehörig zu Clusterings vorgeschriebener Größen, die eine besonders starke Separationseigenschaft erfüllen: Sie erlauben ein verallgemeinertes Voronoi Diagramm, genannt Power Diagramm, des zu Grunde liegenden Raums, so dass jeder Cluster in seiner eigenen Zelle liegt. Wir zeigen wie solch ein Clustering durch lineare Optimierung über einem ``Partitionspolytop`` berechnet werden kann. Eine spezielle Darstellung von Power Diagrammen erlaubt uns zudem die Berechnung eines zugehörigen Power Diagramms ebenfalls als lineares Optimierungsproblem zu modellieren. Abschließend zeigen wir auf, wie die entwickelten Algorithmen auf allgemeinere Clustering-Probleme übertragen werden können und wie unser geometrischer Ansatz dazu benutzt werden kann, Clusterings zusätzlicher wünschenswerter Eigenschaften zu finden.

Dr. Steffen Borgwardt

TU München