Zurück

Einführung in Machine Learning mit Python - K-Means Clustering

Einführung - k-Means

Das ist der dritte Teil einer Serie von Blogbeiträgen über Machine Learning mit Python. In diesem Tutorial beschäftigen wir uns mit unbeaufsichtigtem Lernen (unsupervised learning) und werden hierbei Clusteranalyse mit dem K-means Algorithmus implementieren. Für das Tutorial sind Grundkenntnisse in Python sowie ein Blick in die vorherigen Tutorials empfehlenswert.

Was ist Clusteranalyse

Clusteranalyse ist ein unbeaufsichtigtes Verfahren, das bei Machine Learning und Data Mining verwendet wird, wobei man Gruppen von ähnlichen Objekten in unbeschrifteten Daten finden will. Diese Art von Analyse findet z.B. Anwendung in verschiedenen Bereichen, wie Marketing (neue Kundengruppen auf Basis ihrer Einkäufe zu identifizieren), Biologie (Klassifizierung von Individuen oder Gen-Sequenzierung), Sozialwissenschaften (Kriminalitäts-Hotspots identifizieren) und viele weitere.

K-Means

K-Means steht für K-Mittelwerte und ist ein iterativer Algorithmus in der Clusteranalyse. Als Eingabe bekommt der Algorithmus eine Zahl K und den Datensatz (Sammlung von Merkmale für jede Stichprobe) und versucht danach K unterschiedliche Gruppen im Datensatz zu erkennen.

Initialisierung

Der erste Schritt ist, die Zentroiden der Cluster zu initialisieren. Am häufigsten nimmt man entweder K zufällige Stichproben aus dem Datensatz oder K zufällige Punkte dazwischen.

Verteilung der Daten unter den Clustern

Der nächste Schritt ist, jede Stichprobe in ein Cluster einzufügen. Am häufigsten verwendet man das Quadrat des euklidischen Abstands als Metrik.

*Gegeben sind Vektoren p=(p1, p2 .. pn) und q=(q1, q2 .. qn), dann ist der euklidische Abstand

Das heißt, für jede Stichprobe wird das nächstliegende Zentroid gewählt.

Aktualisierung der Mittelwerte

Im letzten Schritt werden die neuen Mittelwerte für jeden Cluster berechnet.

Iteration

Die letzten zwei Schritte werden so oft wiederholt, bis der Algorithmus ein Stoppkriterium erreicht. Das kann eine Obergrenze der Iterationen sein oder eine Untergrenze der Veränderung der Koordinaten der Zentroiden. Der Algorithmus konvergiert immer, es kann aber sein, dass es keine optimale Lösung ist. In diesem Fall muss man den Algorithmus mehrfach ausführen.

Implementierung mit Python und sklearn

Den kompletten Code finden Sie in dem Github Repository

Für die Implementierung verwenden wir die folgenden Python-Bibliotheken:

  • sklearn und numpy für algebraische Berechnungen und für eine Implementierung von K-means
  • matplotlib für dreidimensionale Datendarstellung
import numpy as np
from random import randint
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

Die Bibliotheke Scikit-Learn enthält Implementierungen einer Vielfalt von Machine Learning Algorithmen. Das Modul sklearn.cluster enthält viele Clustering Algorithmen. Wir verwenden die Klasse KMeans als bereitgestellte Implementierung des K-Means Algorithmus.

Das sind die wichtigsten Parameter für die Initialisierung der KMeans Klasse:

  • n_clusters - eigenlich der K Parameter, sprich die gewünschte Anzahl an Clustern
  • init - (k-means++, random oder [ndarray]) - Das Verfahren für die Anfangskoordinaten der Zentroiden.
    • falls k-means++ - "smarte" Wahl der Zentrumskoordinaten, beschleunigt die Konvergenz
    • falls random - zufällige Generierung der Zentrumskoordinaten
    • [ndarray] - selbstdefinierte Zentrumskkordinaten
  • n_init - wie oft wird der Initialisierungsalgorithmus ausgeführt bevor das beste Ergebnis zurückgegeben wird
  • max_iter - die maximale Anzahl von Iterationen bevor der Algorithmus endet.

Wichtige Methoden der KMeans Klasse:

  • fit(X) - Führt K-Means clustering aus
  • predict(X) - ergibt die Klasse (Cluster), einer oder mehrerer Stichproben
  • score(X) - Eine Metrik für den Abstand zwischen den Clusterzentren und den dazugehörigen Stichproben

Wichtige Attribute der KMeans Klasse:

  • cluster_centers_ - ein Array das die Zentrumkoordinaten jedes Clusters darstellt
  • labels_ - ein Array mit der Clusterbezeichnung für jedes Eingabeelement

Datensatz

Jetzt benötigen wir einen Datensatz und generieren einen mit sklearn. Die Funktion make_blobs aus dem Modul sklearn.datasets kann gaußsche Flecken generieren. Das bedeutet, dass die Stichproben im Zentrum der Flecke dichter aneinander liegen als jene am Rand. Die Funktion verrät uns zwei Arrays - die Stichproben und deren Merkmale sowie die Klassen der Stichproben. Die Klassen benötigen wir für diese Aufgabe nicht.

Außerdem legen wir den Parameter random_state fest, damit wir bei jedem Programmverlauf die gleichen Cluster haben und so die Parameter besser konfigurieren können.

Wir möchten diese Daten plotten und benötigen dafür eine entsprechende Funktion.

# Funktion, die zweidimensionalen Daten plottet
def plot2d(x,y, colors=None):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(x,y, c=colors)
    plt.show()

# Datensatz generieren
data, classes = make_blobs(n_samples=1000, centers=5, random_state=7)
plot2d(data[:,0], data[:,1])
 
 

Wie wählt man eine K?

Es ist offensichtlich, wie viele Cluster vorhanden sind, wir gehen aber davon aus, dass wir diese Information nicht haben. Bei hochdimensionalen Daten kann man nur schwer den Datensatz plotten und die Cluster durch Betrachten erkennen. Wir verwenden den sogenannten elbow-point (Ellenbogen-Punkt).

Wir führen das Clustering für unterschiedliche Parameter K aus und verwenden die Summe der Quadratsabstände der Stichproben zum nächstliegenden Zentroid. Natürlich wird der Abstand durch das Erhöhen des Parameters K sinken. Es gibt aber einen Punkt, ab welchem die Senkungsrate stark abnimmt. Das ist der sogenannte Ellenbogen-Punkt und auch der perfekte K Parameter für den spezifischen Datensatz.

# Funktion, die ein Liniendiagramm zeichnet
def plot_cluster_score(x, y, k=None):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(x,y,'-')
    
    if k:
        plt.title("Clustering score for K=%d" % k)
        plt.xlabel("Iteration")
    else:
        plt.title("Clustering score for different K")
        plt.xlabel("K Parameter")
        
    plt.ylabel("Error")
    plt.xticks(x)
    plt.grid(linewidth=1)
    plt.show()

# Iteration um das perfekte K zu finden 
# und das Ergebnis zu plotten
scores = []
for i in range(1,11):
    print("Clustering mit K=%d" % (i))
    kmeans = KMeans(n_clusters=i)
    kmeans.fit(data)
    scores.append([i, kmeans.score(data)])

# einfacher Daten zu plotten wenn sie ein numpy-array sind, aber
# einfacher Daten in einer python-Liste hinzufügen
scores = np.array(scores)
plot_cluster_score(scores[:,0], scores[:,1])
 
Clustering mit K=1
Clustering mit K=2
Clustering mit K=3
Clustering mit K=4
Clustering mit K=5
Clustering mit K=6
Clustering mit K=7
Clustering mit K=8
Clustering mit K=9
Clustering mit K=10
 
 

Es ist zu sehen, dass k=5 für diesen Datensatz am besten geeignet ist. Deswegen erstellen wir eine Variable K_PARAM = 5, die wir für die weiteren Schritte nutzen und zusätzlich einfach verändern können.

Validierung

Da die Koordinaten der Zentroiden bei jedem Verlauf zufällig initialisiert werden, kann es passieren, dass die Endergebnisse auch unterschiedlich sind. Bei großen Abweichungen kann das bedeuten, dass die Daten nicht für Clustering durch K-means geeignet sind. Deswegen werden wir das Clustering 10 Mal durchführen und dann die Summe der Quadratsabstände für jede Iteration plotten. Je flacher die Linie ist, desto stabiler der Algorithmus für diesen Datensatz.

# K-Parameter hier setzen
K_PARAM = 5

# Iterieren um festzustellen, wie sich die Summe der Abstände
# sich für die nächste 10 Iteration verändert
scores = []
for i in range(10):
    kmeans = KMeans(n_clusters=K_PARAM)
    kmeans.fit(data)
    scores.append([i, kmeans.score(data)])

# Mit einem schlechten K Parameter Cluster finden,
# um die Grafiken zu vergleichen
bad_scores = []
for i in range(10):
    kmeans = KMeans(n_clusters=7)
    kmeans.fit(data)
    bad_scores.append([i, kmeans.score(data)])

scores = np.array(scores)
bad_scores = np.array(bad_scores)

plot_cluster_score(scores[:,0], scores[:,1], k=K_PARAM)
plot_cluster_score(bad_scores[:,0], bad_scores[:,1], k=7)
 
 
 

Man sieht, dass der Fehler im ersten Diagramm stabil ist. Das bedeutet, dass der K-Parameter gut passt. Im zweiten Diagramm variiert der Fehler von Iteration zu Iteration, was bedeutet, dass das Ergebnis mehr von den Startkoordinaten abhängt, was besagt, dass dieser K-Parameter nicht gut passt oder dass unsere Daten sich nicht clustern lassen.

Jetzt haben wir einen guten K-Parameter und können deswegen das Clustering ein letztes Mal ausführen und das Endergebnis plotten.

# Clustering zum letzten mal Ausführen und
# Endergebnis in unterschiedliche Farben plotten
kmeans = KMeans(n_clusters=K_PARAM)
kmeans.fit(data)

# Clusters und deren Zentroide plotten
plt.scatter(data[:,0], data[:,1], c=kmeans.labels_)
plt.scatter(kmeans.cluster_centers_[:,0], 
            kmeans.cluster_centers_[:,1],
            c=np.arange(K_PARAM),
            marker='*',
            s=100, 
            linewidths=2,
            edgecolors='black')
plt.show()
 
 

Man sieht, dass der Algorithmus die verschiedenen Gruppen sehr gut erkannt hat.

Feature Engineering und Validierung

Da Clusteranalyse eine Art unbeaufsichtigtes Lernen ist, gibt es in der Praxis keine Testdaten, mit denen wir eine Klassifikationsgüte bestimmen können, deswegen muss man selbst Maßnahmen ergreifen, um zu prüfen, ob die Ergebnisse des Algorithmus Sinn machen.

Der hier verwendete Datensatz wurde zufällig generiert und hat deswegen keinen Bezug zur realen Welt, zusätzlich haben wir alle Merkmale des Datensatzes als Parameter eingesetzt. In der Praxis muss man sich auf sein Domainwissen und seine Erfahrung verlassen, um nur zur aktuellen Aufgaben relevante Merkmale für die Analyse zu verwenden. Das nennt man Feature Engineering.

Nachdem man den K-Means Algorithmus ausgeführt hat, muss man das Endergebnis validieren. Machen die erkannten Cluster im Kontext der bestimmten Domain Sinn? Datenvisualisierung ist oft eine gute Methode, allerdings nicht sehr effektiv für hochdimensionale Daten. Wie sieht das Ergebnis aus, wenn man andere Clustering-Algorithmen verwendet? Dies ist alerdings ein sehr breites Thema und sprengt den Rahmen dieses Blogbeitrags. Es gibt jedoch ein informatives Dokument über unterschiedliche Clustering Algorithmen und die Validierung ihrer Ergebnisse. (Link siehe unten)

Dokumentaition

Resourcen

  • Git-Repository: Link
  • Clustering Tutorial auf Englisch: Link
  • On Clustering Validation Techniques - Paper by Maria Halkidiki, Yannis Batistakis, Michalis Vazirgiannis - Link

Sonstige Links

Kommentare
Trackback-URL:

Noch keine Kommentare. Seien Sie der Erste.

Ancud IT-Beratung GmbH
Glockenhofstraße 47 
90478 Nürnberg 

Tel.: +49 911 2525 68-0