Kernmengen und Datenstromalgorithmen für das k-means Problem und verwandte Zielfunktionen im Clustering

Abstract

Das k-means Problem besteht aus der Berechnung von k Zentren, die die Summe der quadrierten Distanzen aller Punkte in einer Menge P zu ihrem nächsten Zentrum minimieren. Eine Kernmenge für P ist eine kleine gewichtete Punktmenge, die für alle möglichen Auswahlen von Zentren ähnliche Kosten hat. Eine Dimensionsreduktion verringert die Dimension der Eingabepunkte und erhält dabei die Kostenfunktion ebenfalls approximativ für alle möglichen Zentrenmengen. Die vorliegende Zusammenfassung beschreibt Ergebnisse aus [Sc14] zur Berechnung von Kernmengen und Dimensionsreduktionen für das k-means Problem und für verwandte Probleme.