python kmeans

Python-kmeans

Python-Implementierung von K-Means-Clustering. k-means ist eine unbeaufsichtigte Lerntechnik, die versucht, ähnliche Datenpunkte in einer vom Benutzer angegebenen Anzahl von Gruppen zusammenzufassen. Das folgende Beispiel zeigt den Verlauf der Cluster für den Iris-Datensatz unter Verwendung des k-means++-Schwerpunktinitialisierungsalgorithmus.

Beschreibung

k-means versucht, eine vom Benutzer angegebene k(<N) Anzahl von Clustern aus einem Satz von N d-dimensionalen Vektoren mit reellen Werten zu identifizieren. Der Algorithmus fährt fort, indem er versucht, die Summe der quadrierten Abstände von einem Clusterzentrum zu den Clustermitgliedern zu minimieren. Der kanonische Algorithmus läuft in drei Phasen ab:

1. k zufällige Schwerpunkte (Clusterzentren) initialisieren;
2. Ordnen Sie Datenpunkte gemäß der Distanzmetrik (typischerweise euklidische Distanz) dem nächstgelegenen Cluster zu.
3. Aktualisieren Sie die Schwerpunkte auf den Mittelwert der Mitglieder des Clusters.
4. Wiederholen Sie die Schritte 2 und 3, bis sich die Zuweisungen aus Schritt 2 nicht ändern.

Die Ausgabe des Algorithmus ist eine Clusterzuweisung für jeden Datenpunkt und eine endgültige Ebene der „Verzerrung“. Der Algorithmus erzeugt keine nachweislich optimale Lösung, und anfängliche Clusterzentren können dazu führen, dass der Algorithmus in einer lokal optimalen Lösung stecken bleibt, die eindeutig suboptimal ist (siehe das grundlegende 2D-Beispiel im Abschnitt „Ergebnisse“).

Viele Forschungsarbeiten konzentrierten sich auf Folgendes:

• Auswahl erster Clusterzentren. K-Means++ ist eine bekannte Methode und in dieser Implementierung enthalten. Der Algorithmus wird im folgenden Unterabschnitt beschrieben.
• Berechnen von Entfernungen, dh unter Verwendung anderer als der euklidischen Maße, siehe hier.

K-Mittel++

Anstatt wie in Schritt 1 oben zufällige Schwerpunkte zu initialisieren, verteilt k-means++ die anfänglichen Schwerpunkte probabilistisch, um eine schlechte Anfangskonfiguration zu vermeiden. Der Algorithmus lautet:

1. Wählen Sie den ersten Schwerpunkt zufällig aus.
2. Berechnen Sie für jeden Datenpunkt x den Abstand d(x) von x zum nächstgelegenen Schwerpunkt, der bereits ausgewählt wurde.
3. Wählen Sie einen Datenpunkt als nächsten Schwerpunkt aus, indem Sie eine gewichtete Wahrscheinlichkeit verwenden, die proportional zu d(x)2 ist.

Diese Technik bevorzugt Datenpunkte, die nicht in der Nähe anderer Anfangsschwerpunkte liegen, und verwendet eine Auswahlrichtlinie, die an die Auswahl am Rouletterad (oder Fitness-Proportionalauswahl) erinnert, die häufig in genetischen Algorithmen verwendet wird.

Ressourcen

Grundlegender Algorithmus

• K-Means wird in den Top 10 Algorithmen für Data Mining beschrieben;

• K-Means wird in Informationstheorie, Inferenz und Lernalgorithmen beschrieben, Auszug hier;

• Professor Andrew Moore von der CMU hat hier einige gute Anmerkungen;

• Edureka-Beispiel unter Verwendung von Kriminalitätsdaten

Initialisierung von Clustern

• K-Means++ und das vollständige Papier finden Sie hier

• Eine vergleichende Studie effizienter Initialisierungsmethoden für den K-Means-Clustering-Algorithmus

Warum nicht SciPy verwenden?

SciPy verfügt über eine K-Means-Implementierung. Das Ziel dieser Arbeit besteht darin, eine reine Python-Implementierung zum Zweck des Lernens zu erstellen und anderen beim Erlernen des K-Means-Algorithmus zu helfen. Interessierte Leser mit nur minimaler Python-Erfahrung können diesen Code ohne die zusätzliche Komplexität einer Bibliothek wie SciPy lesen und überspringen. Es ist keinesfalls für den Produktionsgebrauch gedacht :)

Den Code ausführen

Abhängigkeiten

• Python 3.6.3
• matplotlib 2.1.1 – Installationsanweisungen finden Sie hier.

Ausführung

Führen Sie den Code mit dem Python-Interpreter aus:

python kmeans.py ./resources/<config.cfg>

Wobei config.cfg eine Nur-Text-Konfigurationsdatei ist. Das Format der Konfigurationsdatei ist ein Python-Dikt mit den folgenden Feldern:

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

Sie müssen Folgendes angeben:

• eine CSV-Datendatei;
• eine Teilmenge von Feldern, die aus der Datei projiziert werden sollen;
• die Anzahl der zu bildenden Cluster, k;
• die Teilmenge der im Clustering-Prozess verwendeten Attribute;
• Geben Sie optional eine anfängliche Clusterfunktion an (Standard = 'rand_init_centroids'). Interessierte Autoren müssen dem Code ihre eigene hinzufügen und sie hier angeben.
• eine Plotkonfiguration, die enthält
  • Präfix für PNG-Dateien, die während des Prozesses im Arbeitsverzeichnis erstellt werden. Wenn dies nicht angegeben ist, werden keine Bilder erstellt.
  • die einzelnen Grundstückskonfigurationen, begrenzt auf 2 Dimensionen pro Grundstück.

Ergebnisse

Iris-Datensatz

Der Iris-Datensatz (iris.config) von Lichman, M. (2013). UCI-Repository für maschinelles Lernen. Irvine, CA: University of California, School of Information and Computer Science., ist ein sehr bekannter Datensatz in der Community des maschinellen Lernens. Hier sind die Ergebnisse meiner zufälligen anfänglichen Cluster:

Grundlegende synthetische 2D-Daten

Diese Daten wurden zu Debugging-Zwecken generiert (siehe basic2d.config) und veranschaulichen die Auswirkungen einer schlechten Auswahl an anfänglichen Zufallsclustern. Die folgenden Ergebnisse zeigen eine anfängliche Schwerpunktkonfiguration, die verhindert, dass der Algorithmus die offensichtliche Clusterzuweisung erreicht. In diesem Fall bedeutet die Platzierung des roten Schwerpunkts, dass der blaue Schwerpunkt alle Datenpunkte im unteren linken und unteren rechten Quadranten erfasst.

Verbrechen

Der Kriminalitätsdatensatz (crime.config) stammt hier von Edureka.