K-Means und K-Medoids in der Bildkompression: Ein praxisnaher Leitfaden für ISYE 6740

Einführung in die Clusteranalyse für die Bildkompression

Die Clusteranalyse ist ein zentrales Verfahren des maschinellen Lernens, das in vielen Bereichen Anwendung findet – von der Bildverarbeitung bis hin zur Marktsegmentierung. In dieser Lektion konzentrieren wir uns auf die Algorithmen K-Means und K-Medoids, die du in deiner Hausaufgabe ISYE 6740 implementieren wirst. Stell dir vor, du möchtest ein Foto von deinem letzten Schulausflug komprimieren, um Speicherplatz zu sparen. Genau das ermöglichen diese Verfahren: Sie reduzieren die Anzahl der Farben im Bild, indem sie ähnliche Pixel zu Clustern zusammenfassen und durch eine repräsentative Farbe ersetzen.

Die Aktualität dieser Technik zeigt sich auch in der KI-gestützten Bildbearbeitung, wie sie in Apps wie Instagram oder TikTok verwendet wird. Selbst moderne Spiele-Engines nutzen ähnliche Verfahren, um Texturen effizient zu speichern. In diesem Tutorial lernst du die mathematischen Grundlagen, die Implementierung und die Optimierung dieser Algorithmen – genau das, was du für die Lösung der Aufgaben 1 bis 4 benötigst.

K-Means: Der Klassiker unter den Clustering-Verfahren

Minimierung der Distortion-Funktion

Der K-Means-Algorithmus zielt darauf ab, die Distortion-Funktion zu minimieren:

J = Σ_n Σ_k r_nk ||x_n - μ_k||²

Hierbei ist r_nk ein Indikator, der angibt, ob Datenpunkt x_n zum Cluster k gehört, und μ_k ist der Mittelpunkt (Centroid) des Clusters. Die euklidische Distanz wird als Ähnlichkeitsmaß verwendet. Durch Ableiten der Funktion nach μ_k und Nullsetzen erhält man die optimale Aktualisierungsregel:

μ_k = (Σ_n r_nk x_n) / (Σ_n r_nk)

Das bedeutet, der neue Centroid ist der Durchschnitt aller ihm zugeordneten Punkte. Diese Herleitung ist ein klassischer Beweis, den du in Teil (a) deiner Hausaufgabe führen wirst.

Konvergenz zu einem lokalen Optimum

Ein wichtiges Merkmal von K-Means ist, dass der Algorithmus garantiert nach endlich vielen Schritten ein lokales Optimum erreicht. Der Beweis (Teil b) basiert auf der Monotonie der Distortion: Jeder Schritt (Zuordnung der Punkte und Aktualisierung der Centroids) verringert den Wert von J oder lässt ihn gleich. Da es nur endlich viele mögliche Zuordnungen gibt, muss der Algorithmus konvergieren.

In der Praxis siehst du das zum Beispiel bei der Farbkompression eines Fotos: Nach wenigen Iterationen ändern sich die Farben kaum noch. Ein aktuelles Beispiel: Stell dir vor, du verarbeitest ein Bild von einem E-Sport-Event wie der Fortnite-WM 2025. Die leuchtenden Farben der Spieler-Outfits werden durch K-Means auf wenige repräsentative Töne reduziert – und das in Sekundenschnelle.

Hierarchisches Clustering im Vergleich zu K-Means

In der Vorlesung wurde auch das bottom-up hierarchische Clustering besprochen. Dabei werden iterativ die beiden ähnlichsten Cluster zusammengeführt. Die Wahl des Distanzmaßes zwischen Clustern beeinflusst das Ergebnis maßgeblich. Die drei gängigsten Metriken sind:

• Single Linkage: minimale Distanz zwischen zwei Punkten der Cluster
• Complete Linkage: maximale Distanz
• Average Linkage: durchschnittliche Distanz aller Punktpaare

In Teil (c) der Hausaufgabe sollst du überlegen, welche Metrik am ehesten zu K-Means-ähnlichen Clustern führt. Die Antwort ist Average Linkage, da K-Means die Summe der quadrierten Abstände minimiert, was dem Durchschnitt nahekommt. Bei den Two Moons-Daten (Teil d) hingegen versagen alle drei Metriken, weil die Cluster nicht konvex sind. Hier helfen nur spezielle Verfahren wie Spektral-Clustering.

Dieses Wissen ist auch für aktuelle KI-Trends relevant: In der Personalisierung von Newsfeeds (z. B. bei TikTok) werden ähnliche Clustering-Methoden genutzt, um Nutzer zu gruppieren – oft mit Average Linkage, um robuste Gruppen zu erhalten.

K-Medoids: Eine robuste Alternative

Während K-Means auf euklidischen Räumen und Mittelwerten basiert, eignet sich K-Medoids besser für kategoriale Daten oder wenn Ausreißer die Centroids verzerren würden. Der Algorithmus wählt einen tatsächlichen Datenpunkt als Repräsentanten (Medoid) und minimiert die Summe der Abstände zu allen Punkten im Cluster.

Implementierung in MATLAB

In deiner Hausaufgabe implementierst du sowohl K-Means (mykmeans.m) als auch K-Medoids (mykmedoids.m). Die Funktionen erhalten als Eingabe die Pixelmatrix (jede Zeile: R, G, B) und die gewünschte Anzahl Cluster K. Die Ausgabe ist ein Spaltenvektor mit Clusterzuweisungen und eine Matrix der Centroids (für K-Means) bzw. Medoids.

Ein Beispiel: Du hast ein 320x240 Pixel großes Bild deines letzten Schulprojekts. Mit K=16 Farben komprimiert, wird die Datei deutlich kleiner – ideal für eine Präsentation in der Schule oder zum Teilen in der WhatsApp-Gruppe.

Wahl des Distanzmaßes

Bei K-Medoids kannst du verschiedene Distanzmaße ausprobieren, z. B. Manhattan-Distanz oder cosine similarity. In deinem Bericht solltest du erklären, warum du dich für ein bestimmtes Maß entschieden hast. Ein Tipp: Für Bilder mit vielen Farbverläufen eignet sich die euklidische Distanz gut, während bei cartoonartigen Grafiken (wie in Videospielen) die Manhattan-Distanz oft bessere Ergebnisse liefert.

Initialisierung und Konvergenz

Die Wahl der initialen Centroids/Medoids beeinflusst das Ergebnis stark. Ein schlechter Start kann zu einem suboptimalen lokalen Optimum führen. In der Praxis verwendet man oft K-Means++ zur Initialisierung. In deinem Experiment (Teil 4 des Berichts) wirst du sehen, dass unterschiedliche Startpunkte zu verschiedenen Farbpaletten führen – manchmal mit überraschend schönen Ergebnissen, die an Pixel-Art erinnern.

Praktische Tipps für die Hausaufgabe

• Teste mit kleinen Bildern: Beginne mit einer Auflösung von 100x100 Pixeln, um die Rechenzeit zu reduzieren.
• Visualisiere die Zwischenschritte: Zeichne die Distortion über die Iterationen – so siehst du, ob der Algorithmus konvergiert.
• Vergleiche K-Means und K-Medoids: Welcher Algorithmus liefert für dein Bild die bessere Kompression? Welcher ist schneller?
• Dokumentiere deine Entscheidungen: Im Bericht solltest du begründen, warum du bestimmte Parameter gewählt hast.

Fazit

Die Algorithmen K-Means und K-Medoids sind nicht nur für deine Hausaufgabe relevant, sondern auch für viele reale Anwendungen – von der Bildkompression in sozialen Medien bis hin zur Analyse von Finanzdaten. Indem du die mathematischen Grundlagen verstehst und die Implementierung selbst durchführst, erwirbst du Fähigkeiten, die in der Datenwissenschaft und KI-Entwicklung sehr gefragt sind.

Viel Erfolg bei der Bearbeitung! Wenn du weitere Fragen hast, schau in die Assignment Chef-Community oder frage deinen Tutor.