K-Means

Ein k-Means-Algorithmus ist ein Verfahren zur Vektorquantisierung, das auch zur Clusteranalyse verwendet wird. Dabei wird aus einer Menge von ähnlichen Objekten eine vorher bekannte Anzahl von k Gruppen gebildet. Der Algorithmus ist eine der am häufigsten verwendeten Techniken zur Gruppierung von Objekten, da er schnell die Zentren der Cluster findet. Dabei bevorzugt der Algorithmus Gruppen mit geringer Varianz und ähnlicher Größe.

Der Algorithmus hat starke Ähnlichkeiten mit dem EM-Algorithmus und zeichnet sich durch seine Einfachheit aus.[1] Erweiterungen sind der k-Median-Algorithmus und der k-Means++ Algorithmus.

Der Begriff „k-means“ wurde zuerst von MacQueen 1967 verwendet,[2] die Idee geht jedoch auf Hugo Steinhaus 1957 zurück.[3] Der heutzutage meist als „k-means-Algorithmus“ bezeichnete Standard-Algorithmus wurde 1957 von Lloyd zur Puls-Code-Modulation vorgeschlagen, aber erst 1982 in einer Informatik-Zeitschrift publiziert[4] und deckt sich weitestgehend mit der Methode von Forgy, die 1965 publiziert wurde.[5] Eine weitere Variante ist die von Hartigan und Wong, die unnötige Distanzberechnungen vermeidet, indem sie auch den Abstand zum zweitnächsten Mittelpunkt verwendet.[6][7] Die Algorithmen werden den genannten Personen oft falsch zugeordnet: Insbesondere wird oft der Algorithmus von Lloyd/Forgy beschrieben, als Quelle jedoch MacQueen genannt.

Ziel von k-Means ist es, den Datensatz so in ${\displaystyle k}$ Partitionen zu teilen, dass die Summe der quadrierten Abweichungen von den Cluster-Schwerpunkten minimal ist. Mathematisch entspricht dies der Optimierung der Funktion

${\displaystyle J=\sum _{i=1}^{k}\sum _{\mathbf {x} _{j}\in S_{i}}{\|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}}$

mit den Datenpunkten ${\displaystyle \mathbf {x} _{j}}$ und den Schwerpunkten ${\displaystyle {\boldsymbol {\mu }}_{i}}$ der Cluster ${\displaystyle S_{i}}$. Diese Zielfunktion basiert auf der Methode der kleinsten Quadrate und man spricht auch von Clustering durch Varianzminimierung,[8] da die Summe der Varianzen der Cluster minimiert wird. Da zudem ${\displaystyle \|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}$ die quadrierte Euklidische Distanz ist, ordnet k-Means effektiv jedes Objekt dem nächstgelegenen (nach Euklidischer Distanz) Clusterschwerpunkt zu. Umgekehrt ist das arithmetische Mittel ein Kleinste-Quadrate-Schätzer, optimiert also ebenfalls dieses Kriterium.

Da die Suche nach der optimalen Lösung schwer ist (NP-schwer), wird im Normalfall ein approximativer Algorithmus verwendet wie die Heuristiken von Lloyd oder MacQueen. Da die Problemstellung von k abhängig ist, muss dieser Parameter vom Benutzer festgelegt werden. Es existieren jedoch auch Ansätze, durch Verwendung eines zweiten Objektes diesen Parameter zu wählen (vgl. X-Means, Akaike-Informationskriterium, bayessches Informationskriterium und Silhouettenkoeffizient).

Der am häufigsten verwendete k-Means-Algorithmus ist der Lloyd-Algorithmus, der oft als „der k-means-Algorithmus“ bezeichnet wird, obwohl Lloyd diesen Namen nicht verwendet hat. Lloyds Algorithmus besteht aus drei Schritten:

1. Initialisierung: Wähle ${\displaystyle k}$ zufällige Mittelpunkte (Means): ${\displaystyle \mathbf {m} _{1}^{(1)},\ldots,\mathbf {m} _{k}^{(1)}}$ aus dem Datensatz.
2. Zuordnung: Jedes Datenobjekt wird demjenigen Cluster zugeordnet, bei dem die Cluster-Varianz am wenigsten erhöht wird. Mathematisch bedeutet das, dass jedes Objekt gemäß dem durch die Mittelpunkte erzeugten Voronoi-Diagramm zugeordnet wird.
   ${\displaystyle S_{i}^{(t)}=\left\{\mathbf {x} _{j}:{\big \|}\mathbf {x} _{j}-\mathbf {m} _{i}^{(t)}{\big \|}^{2}\leq {\big \|}\mathbf {x} _{j}-\mathbf {m} _{i^{*}}^{(t)}{\big \|}^{2}{\text{ für alle }}i^{*}=1,\ldots,k\right\}}$
3. Aktualisieren: Berechne die Mittelpunkte der Cluster neu:
   ${\displaystyle \mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\mathbf {x} _{j}}$

Die Schritte 2–3 werden dabei so lange wiederholt, bis sich die Zuordnungen nicht mehr ändern.

Der folgende Pseudocode beschreibt die Implementierung des Standard-Algorithmus. Die Initialisierung der Mittelpunkte, die Abstandsmetrik zwischen Punkten und Mittelpunkten sowie die Berechnung neuer Mittelpunkte können je nach Implementierung variieren. Die Funktion distance gibt den Abstand zwischen den angegebenen Punkten zurück. Die Funktion calculateCentroid gibt den Mittelpunkt der angegebenen Punkte zurück.

function kmeans(k, points)
{
    // Initialize centroids
    centroids = list of k starting centroids
    converged = false
    while (converged == false)
    {
        // Create empty clusters
        clusters = list of k empty lists
        
        // Assign each point to the nearest centroid
        for (i = 0; i < length(points); i++)
        {
            point = points[i]
            closestIndex = 0
            minDistance = distance(point, centroids[0])
            for (j = 1; j < k; j++)
            {
                d = distance(point, centroids[j])
                if (d < minDistance)
                {
                    minDistance = d
                    closestIndex = j
                }
            }
            clusters[closestIndex].append(point)
        }
        
        // Recalculate centroids as the mean of each cluster
        newCentroids = empty list
        for (i = 0; i < k; i++)
        {
            newCentroid = calculateCentroid(clusters[i])
            newCentroids.append(newCentroid)
        }
        
        // Check for convergence
        if (newCentroids == centroids)
        {
            converged = true
        }
        else
        {
            centroids = newCentroids
        }
    }
    return clusters
}

MacQueen führte mit dem Begriff „k-Means“ einen anderen Algorithmus ein:

1. Wähle die ersten ${\displaystyle k}$ Elemente als Clusterzentren
2. Weise jedes neue Element dem Cluster zu, bei dem sich die Varianz am wenigsten erhöht, und aktualisiere das Clusterzentrum

Während es ursprünglich – vermutlich – nicht vorgesehen war, kann man auch diesen Algorithmus iterieren, um ein besseres Ergebnis zu erhalten.

• k-Means ++ versucht, bessere Startpunkte zu finden.[9]
• Der Filtering-Algorithmus verwendet als Datenstruktur einen k-d-Baum.[10]
• Der k-Means-Algorithmus kann beschleunigt werden unter Berücksichtigung der Dreiecksungleichung.[11]
• Bisecting k-means beginnt mit ${\displaystyle k=2}$, und teilt dann immer den größten Cluster, bis das gewünschte k erreicht ist.
• X-means beginnt mit ${\displaystyle k=2}$ und erhöht ${\displaystyle k}$ so lange, bis sich ein sekundäres Kriterium (Akaike-Informationskriterium, oder bayessches Informationskriterium) nicht weiter verbessert.

k-Means optimiert die quadratischen Abweichungen von einem Mittelwert. Es kann daher nur mit numerischen Attributen verwendet werden, bei denen ein sinnvoller Mittelwert berechnet werden kann. Kategorielle Attribute (bspw. „Auto“, „LKW“, „Fahrrad“) können nicht verwendet werden, da hier kein Mittelwert berechnet werden kann.

Der Parameter ${\displaystyle k}$, die Anzahl der Cluster, muss im Voraus bekannt sein. Er kann jedoch auch experimentell bestimmt werden. Das Problem ist, dass die verschiedenen Cluster miteinander verglichen werden müssen und die Kostenfunktion mit steigendem ${\displaystyle k}$ monoton sinkt. Eine Lösung ist der Silhouettenkoeffizient, der eine von ${\displaystyle k}$ unabhängige Bewertung von Clusterungen liefert. Hierbei wird nicht nur geprüft, wie weit ein Punkt vom eigenen Clusterschwerpunkt entfernt ist, sondern es gehen auch die Entfernungen von anderen Clusterschwerpunkten in die Bewertung des Clustering mit ein.

Die Cluster im Datensatz müssen etwa gleich groß sein, da der Algorithmus den Datensatz stets an der Mitte zwischen zwei Clusterzentren partitioniert.

Der Datensatz darf nicht viel Rauschen bzw. nicht viele Ausreißer enthalten. Fehlerhafte Datenobjekte verschieben die berechneten Clusterzentren oft erheblich, und der Algorithmus hat keine Vorkehrungen gegen derartige Effekte (vgl. DBSCAN, das „Noise“-Objekte explizit vorsieht).

k-Means ist ein leistungsfähiger Algorithmus, jedoch nicht ohne Schwachstellen. Ein k-Means-Algorithmus muss nicht die beste mögliche Lösung finden. Die gefundene Lösung hängt stark von den gewählten Startpunkten ab. Der einfachste Ansatz ist, den Algorithmus mehrmals hintereinander mit verschiedenen Startwerten zu starten und die beste Lösung zu nehmen. Es gibt aber auch viele Überlegungen, wie eine geeignete Verteilung der Startwerte erreicht werden kann. Zu nennen sind unter anderem k-means++, aber auch mit dem Ziehen kleiner Stichproben können die Clusterzentren vor dem Start von k-means angenähert werden. Außerdem macht es einen Unterschied, ob man beliebige Clusterzentren wählt, oder jeden Punkt einem beliebigen Cluster zuordnet und dann die Clusterzentren ermittelt.

Ein weiterer Nachteil ist, dass die Anzahl der Clusterzentren ${\displaystyle k}$ im Voraus gewählt wird. Bei Verwendung eines ungeeigneten ${\displaystyle k}$ können sich komplett andere, unter Umständen unintuitive Lösungen ergeben. Bei einem „falschen“ ${\displaystyle k}$ kann kein gutes Clustering erfolgen. Die Lösung ist, verschiedene Werte für ${\displaystyle k}$ zu probieren und dann ein geeignetes zu wählen, zum Beispiel mit Hilfe des Silhouettenkoeffizienten, oder durch Vergleich der verschiedenen Clusteringkosten.

Gruppen in den Daten können sich, wie in dem gezeigten Schwertlilien-Beispiel, überlappen und nahtlos ineinander übergehen. In einem solchen Fall kann k-Means diese Gruppen nicht zuverlässig trennen, da die Daten nicht dem verwendeten Cluster-Modell folgen.

Des Weiteren sucht k-Means stets konvexe Cluster (bedingt durch die Minimierung des Abstandes zum Clusterschwerpunkt). Andere Algorithmen wie DBSCAN können auch beliebig geformte „dichtebasierte“ Cluster finden. Was ebenfalls von k-Means nicht unterstützt wird, sind hierarchische Cluster (also Cluster, die wiederum eine Clusterstruktur aufweisen), wie sie beispielsweise mit OPTICS gefunden werden können.

Als letztes wird in k-means jeder Punkt einem Cluster zugewiesen, es gibt keine Möglichkeit Ausreißer zu erkennen. Diese können das Ergebnis stark verfälschen. Abhilfe kann hier eine vorherige Noisereduktion schaffen, oder andere Algorithmen, wie DBSCAN, die automatisch Noise erkennen.

Im k-Median-Algorithmus wird im Zuweisungschritt statt der euklidischen Distanz die Manhattan-Distanz verwendet. Im Updateschritt wird der Median statt des Mittelwerts verwendet.[12][13]

Der k-Means++-Algorithmus wählt die Cluster-Schwerpunkte nicht zufällig, sondern nach folgender Vorschrift:

1. Wähle als ersten Cluster-Schwerpunkt zufällig ein Objekt aus
2. Für jedes Objekt berechne den Abstand ${\displaystyle D(x)}$ zum nächstgelegenen Cluster-Schwerpunkt
3. Wähle zufällig als nächsten Cluster-Schwerpunkt ein Objekt aus. Die Wahrscheinlichkeit, mit der ein Objekt ausgewählt wird, ist proportional zu ${\displaystyle D^{2}(x)}$, d. h. je weiter das Objekt von den bereits gewählten Cluster-Schwerpunkten entfernt ist, desto wahrscheinlicher ist es, dass es ausgewählt wird.
4. Wiederhole Schritt 2 und 3 bis ${\displaystyle k}$ Cluster-Schwerpunkte bestimmt sind
5. Führe nun den üblichen k-Means Algorithmus aus

In der Regel konvergiert der nachfolgende k-Means Algorithmus in wenigen Schritten. Die Ergebnisse sind so gut wie bei einem üblichen k-Means-Algorithmus, jedoch ist der Algorithmus typischerweise fast doppelt so schnell wie der k-Means-Algorithmus.[14]

Der Algorithmus PAM (Partitioning Around Medoids, Kaufman und Rousseeuw, 1990) – auch bekannt als k-Medoids[15] – kann als Variante des k-Means Algorithmus interpretiert werden, die mit beliebigen Distanzen konvergiert.

1. Wähle ${\displaystyle k}$ Objekte als Cluster-Schwerpunkte (Medoid) aus
2. Ordne jedes Objekt dem nächsten Cluster-Schwerpunkt zu
3. Für jeden Cluster-Schwerpunkt und jeden Nicht-Cluster-Schwerpunkt vertausche die Rollen
4. Berechne für jede Vertauschung die Summe der Distanzen oder Unähnlichkeiten
5. Wähle als neue Cluster-Schwerpunkte die Vertauschung, die die kleinste Summe liefert
6. Wiederhole 2.–5. solange, bis sich die Cluster-Schwerpunkte nicht mehr ändern

In der ursprünglichen Version von PAM macht hierbei der erste Schritt – die Wahl der initialen Medoiden – einen großen Teil des Algorithmus aus. Da in jeder Iteration stets nur die beste Vertauschung durchgeführt wird, ist der Algorithmus nahezu deterministisch (bis auf exakt gleiche Distanzen). Dadurch ist der Algorithmus aber auch meist sehr langsam.

Während k-means die Summe der Varianzen minimiert, minimiert k-Medoids die Distanzen. Insbesondere kann dieser Algorithmus mit beliebigen Distanzfunktionen verwendet werden, und konvergiert dennoch garantiert.

Die folgenden Bilder zeigen exemplarisch einen Durchlauf eines k-Means-Algorithmus zur Bestimmung von drei Gruppen:

Drei Clusterzentren wurden zufällig gewählt. Die durch Rechtecke repräsentierten Objekte (Datenpunkte) werden jeweils dem Cluster mit dem nächsten Clusterzentrum zugeordnet. Die eingefärbten Gebiete stellen ein Voronoi-Diagramm dar. Die Zentren (jeweilige Schwerpunkte) der Cluster werden neu berechnet. Die Objekte werden neu verteilt und erneut dem Cluster zugewiesen, dessen Zentrum am nächsten ist.

Der k-Means-Algorithmus hat Anwendungen in zahlreichen Bereichen. Er wird in verschiedensten Branchen eingesetzt, um Datensätze zu interpretieren und datengestützte Entscheidungen zu unterstützen. Seine wesentliche Stärke liegt in der Fähigkeit, Datenpunkte anhand ihrer Ähnlichkeit zu gruppieren, was sich flexibel auf unterschiedliche Anwendungsbereiche übertragen lässt.

In der Bildverarbeitung wird der k-Means-Algorithmus oft zur Segmentierung verwendet. Als Entfernungsmaß ist die euklidische Distanz häufig nicht ausreichend und es können andere Abstandsfunktionen, basierend auf Pixelintensitäten und Pixelkoordinaten verwendet werden. Die Ergebnisse werden zur Trennung von Vordergrund und Hintergrund und zur Objekterkennung benutzt. Der Algorithmus ist weit verbreitet und ist in gängigen Bildverarbeitungsbibliotheken wie OpenCV, Scikit-image[16] und itk implementiert.

Der Algorithmus wird häufig eingesetzt, um das Verbraucherverhalten zu analysieren und Kundengruppen mit ähnlichen Merkmalen zu identifizieren. Dies ermöglicht die Entwicklung zielgerichteter Marketingstrategien und personalisierter Kampagnen.[17]

Bei großen Datensätzen hilft der Algorithmus dabei, die Datendichte zu reduzieren, indem Datenpunkte um Schwerpunkte gruppiert werden. Das macht die Daten besser handhabbar und beschleunigt nachfolgende Analyseprozesse.[17]

Die Einteilung von Dokumenten in verschiedene Kategorien anhand von Schlagworten, Themen und Inhalten ist eine Klassifizierungsaufgabe, für die sich der Algorithmus hervorragend eignet. Zunächst werden die Dokumente vorverarbeitet und als Vektoren dargestellt. Dabei wird die Termhäufigkeit genutzt, um Begriffe zu identifizieren, die für die Klassifizierung relevant sind. Anschließend werden die Dokumentenvektoren geclustert, um Ähnlichkeiten zwischen verschiedenen Dokumentengruppen aufzudecken.[18]

Als Call Detail Records werden Informationen bezeichnet, die von Telekommunikationsunternehmen bei Telefonaten, Nachrichtenversand und Internetnutzung eines Kunden erfasst werden. In Verbindung mit demografischen Kundendaten liefern diese Informationen tiefere Einblicke in die Kundenbedürfnisse. Der k-Means-Algorithmus kann genutzt werden, um Kundensegmente anhand ihres Nutzungsverhaltens zu verschiedenen Tageszeiten zu identifizieren.[18]

Infrastrukturkomponenten großer Unternehmen, etwa in den Bereichen Netzwerk, Speicher oder Datenbanken, erzeugen enorme Mengen an Warnmeldungen. Da diese Meldungen auf potenzielle Betriebsstörungen hinweisen können, müssen sie manuell gesichtet und für nachgelagerte Prozesse priorisiert werden. Durch das Clustering der Daten lassen sich Erkenntnisse über Warnungskategorien und die durchschnittliche Reparaturzeit gewinnen sowie Vorhersagen zu Ausfällen treffen.[18]

Durch die Analyse von Daten zu Straftaten in bestimmten Stadtvierteln unter Berücksichtigung von Art und Ort des Delikts sowie deren Zusammenhang lassen sich wertvolle Erkenntnisse über kriminalitätsbelastete Gebiete innerhalb einer Stadt oder eines Stadtteils gewinnen.[18]

Cyber-Profiling ist ein Verfahren zur Erfassung von Daten über Einzelpersonen und Gruppen, um signifikante Zusammenhänge zu erkennen. Das Konzept des Cyber-Profilings leitet sich von Täterprofilen ab, die Strafverfolgungsbehörden Informationen zur Klassifizierung der am Tatort anwesenden Tätertypen liefern, oder es bezieht sich auf die Profilbildung von Personen in einem bestimmten Umfeld anhand von Nutzerdaten und Nutzerpräferenzen.[18]

Maschinelles Lernen spielt eine entscheidende Rolle bei der Betrugserkennung und findet vielfältige Anwendung, etwa bei Betrugsfällen mit Autos, im Gesundheitswesen oder im Versicherungswesen. Unter Verwendung historischer Daten zu betrügerischen Schadensmeldungen ist es möglich, neue Meldungen zu identifizieren, die Ähnlichkeiten mit Clustern aufweisen, welche auf Betrugsmuster hindeuten. Da Versicherungsbetrug für ein Unternehmen Schäden in Millionenhöhe verursachen kann, ist die Fähigkeit zur Betrugserkennung von entscheidender Bedeutung.[18]

Cyberangriffe haben sich weltweit zur größten Bedrohung für Computer und Computernetzwerke entwickelt. Daher ist es wichtig, Intrusion Detection Systeme zu integrieren, die Daten mit hoher Genauigkeit, d. h. mit korrekter Erkennung positiver und negativer Fälle, und mit geringer Fehlerrate, d. h. mit wenigen falsch-positiven und falsch-negativen Ergebnisse, sowie in kürzester Zeit analysieren können. In diesem Zusammenhang ist das auf k-Means-Clustering basierende Erkennungsmodell – ein Verfahren aus dem Bereich Data Mining – ein vielversprechender Ansatz.

Forscher im Bereich Cybersicherheit haben Frameworks zur Erkennung von Malware-Angriffen vorgeschlagen, die das Verhalten von Systemaktivitäten überwachen. Das Verhalten wird dabei vom Framework analysiert, und die Benutzer werden benachrichtigt, sobald Anzeichen für einen Angriff vorliegen. Dabei werden die Daten anhand ihrer Attribute in bestimmte Gruppen (Cluster) unterteilt. Die Erkennung von Eindringlingen in einem Netzwerk umfasst die Überwachung von Ereignissen in einem Computersystem oder Netzwerk sowie deren Analyse auf Anzeichen von Angriffen, die darauf abzielen, die Vertraulichkeit zu gefährden.

Clusteranalyse ist ein Verfahren, bei dem Objekte in sinnvolle Untergruppen zusammengefasst werden, sodass die Mitglieder desselben Clusters einander sehr ähnlich sind, während sich Mitglieder verschiedener Cluster deutlich voneinander unterscheiden. Daher eignen sich Clustering-Verfahren zur Klassifizierung von Protokolldaten und zur Erkennung von Eindringversuchen. Protokolldaten bieten eine weitere Möglichkeit, das Nutzerverhalten zu untersuchen. Da Internet-Aktivitätsprotokolle eine Form von Big Data darstellen, kann Data Mining insbesondere unter Verwendung des k-Means-Algorithmus als Lösung für die Analyse des Nutzerverhaltens dienen.

Im Allgemeinen bezeichnet die Cyber-Profiling-Analyse die Untersuchung von Daten, um festzustellen, welche Aktivitäten ein Nutzer während des Internetzugriffs ausübt. Eine Methode zur Unterstützung des Profiling-Prozesses ist der k-Means-Algorithmus. Mithilfe dieses Algorithmus lassen sich Daten nach der Anzahl der besuchten Websites gruppieren. Ziel dieser Gruppierung ist es, zu ermitteln, welche Websites der Nutzer häufig aufruft. Ein durchschnittlicher Nutzer verfügt über mehr als 100 Berechtigungen, deren manuelle Verwaltung sehr aufwendig sein kann. Durch den Einsatz von Clustering und des k-Means-Algorithmus, einem Modell des maschinellen Lernens, lassen sich Ausreißer beim Zugriff erkennen, indem das Verhalten dynamischer Nutzergruppen (Peergroups) analysiert wird.[19]

K-means und seine Varianten sind in verschiedener Open-Source-Software verfügbar.

• Dlib[20]
• ELKI enthält die Varianten von Lloyd und MacQueen, dazu verschiedene Strategien für die Startwerte wie k-means++, und Varianten des Algorithmus wie k-medians, k-medoids und PAM.
• GNU R enthält die Varianten von Hartigan, Lloyd und MacQueen, und zusätzliche Variationen im Erweiterungspaket „flexclust“.
• OpenCV enthält eine auf Bildverarbeitung optimierte Version von k-means (inkl. k-means++ seeding)
• Scikit-learn enthält k-means, inkl. Elkans Variante und k-means++.
• Weka enthält k-means (inkl. k-means++ seeding) und die Erweiterung x-means.

• David MacKay: Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003, ISBN 0-521-64298-1, Chapter 20. An Example Inference Task: Clustering, S. 284–292 (inference.phy.cam.ac.uk [PDF]). 
• Gary Bradski, Adrian Kaehler: Learning OpenCV Computer Vision with the OpenCV Library. O’Reilly, 2001, ISBN 978-0-596-51613-0. 

• Ke Chen, University of Manchester: K-means Clustering
• Frank Nielsen: Texture synthesis Clustering k-means Voronoi diagrams
• Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: The Effectiveness of Lloyd-type Methods for the k-Means Problem
• Sariel Har-Peled, Bardia Sadri: How Fast is the k-means Method?
• Mo¨ıse Blanchard, Adam Quinn Jaffe, Nikita Zhivotovskiy: Consistency and inconsistency in k-means clustering