Proposition - Optimalität von K-Means++

• Involvierte Definitionen:
  • K-Means++
  • Trägheitsmaß
• Veranstaltung: EML
• Referenz: @thimm2024 (Abschnitt 3.1.3)

⠀

Proposition: Optimalität von K-Means++

Der K-Means++ Algorithmus garantiert für den K-Means-Algorithmus eine durchschnittliche Güte wie folgt:

Das Trägheitsmaß eines mit K-Means++ initialisierten Clusterings ist maximal um den Faktor größer als das Trägheitsmaß des optimal möglichen Clusterings.