K-Means-Algorithmus (Lehrtext)

Um bestimmte Phänomene der Realität zu untersuchen, bedient man sich üblicherweise geeigneter Messungen. In der Linguistik wird beispielsweise die Häufigkeit bestimmter Worte in Texten gezählt. In der Biologie werden vielleicht das Gewicht sowie weitere Parameter von Alpendohlen bestimmt.

Jede Einzelmessung besteht also aus einer festen Anzahl von Messdaten. Die Gesamtheit der so gewonnen Datenpunkte bildet dann eine Punktewolke, deren Struktur Auskunft über die  betrachteten Objekte geben kann. Oftmals zerfällt die Punktwolke in einzelne Bereiche, sogenannte Cluster. Im Fall der Linguistik,  lassen sich etwa die einzelnen Cluster den Texten  verschiedener Autoren zuordnen. Oder beim Beispiel mit den Alpendohlen entsprechen die Cluster eigenen Unterarten, die sich sonst, rein morphologisch, kaum unterschieden lassen.

Im vorliegenden Text wird ein besonders einfaches und durchsichtiges Verfahren der Clusteranalyse, der sogenannte K-Means Algorithmus,  erklärt und auf die Kompression von Bildern angewandt: Jedem Pixel eines Bildes lässt sich nämlich als Datenpunkt sein RGB-Code (Rot-Grün-Blau) zuordnen. Ersetzt man dann jeden gefundenen Farbcluster durch eine repräsentative Farbe, lässt sich das Bild mit wesentlich weniger Farben als im Original ohne grossen Qualitästverlust darstellen. Durch diese Datenkompression lässt sich Speicherplatz einsparen und die Übertragungsgeschwindigkeit entsprechend deutlich erhöhen.

Die Unterrichtssequenz zeigt an einem einfachen Beispiel eindrucksvoll die Macht mathematischer Ideen und die Omnipräsenz mathematischer Methoden im Alltag.

• Grundkenntnisse in Vektorgeometrie, Algorithmen und Informatik