4 des Machine-Learning-Adventskalenders.
In den ersten drei Tagen erkundeten wir Distanzbasierte Modelle für betreutes Lernen:
Bei all diesen Modellen war die Idee dieselbe: Wir messen Entfernungen und entscheiden über die Ausgabe basierend auf den nächstgelegenen Punkten oder nächstgelegenen Zentren.
Heute bleiben wir in derselben Ideenfamilie. Aber wir nutzen die Distanzen unbeaufsichtigt: k-bedeutet.
Nun eine Frage für diejenigen, die diesen Algorithmus bereits kennen: Welchem Modell ähnelt k-means eher, dem k-NN-Klassifikator oder dem Nearest Centroid-Klassifikator?
Und wenn Sie sich erinnern, gab es bei allen Modellen, die wir bisher gesehen haben, keine wirkliche „Trainings“-Phase oder Hyperparameter-Abstimmung.
- Für k-NN gibt es überhaupt kein Training.
- Für LDA, QDA oder GNB besteht Training lediglich darin, Mittelwerte und Varianzen zu berechnen. Und es gibt auch keine echten Hyperparameter.
Jetzt werden wir mit k-means einen Trainingsalgorithmus implementieren, der endlich wie „echtes“ maschinelles Lernen aussieht.
Wir beginnen mit einem winzigen 1D-Beispiel. Dann gehen wir zu 2D über.
Ziel von k-means
Im Trainingsdatensatz gibt es keine anfänglichen Etiketten.
Das Ziel von k-means ist es erstellen Sie können aussagekräftige Beschriftungen erstellen, indem Sie Punkte gruppieren, die nahe beieinander liegen.
Schauen wir uns die Abbildung unten an. Man erkennt deutlich zwei Gruppen von Punkten. Jeder Schwerpunkt (das rote Quadrat und das grüne Quadrat) liegt in der Mitte seines Clusters und jeder Punkt ist dem nächstgelegenen zugeordnet.
Dies vermittelt ein sehr intuitives Bild davon, wie k-means die Struktur nur anhand von Abständen erkennt.
Und hier bedeutet k die Anzahl der Zentren, die wir zu finden versuchen.
Beantworten wir nun die Frage: Welcher Algorithmus ist k-means näher, der k-NN-Klassifikator oder der Nearest Centroid-Klassifikator?
Lassen Sie sich nicht täuschen k in k-NN und k-means.
Sie bedeuten nicht dasselbe:
- In k-NN, k ist die Anzahl der Nachbarn, nicht die Anzahl der Klassen;
- In k-bedeutet, k ist die Anzahl der Schwerpunkte.
K-means liegt viel näher am Klassifikator für den nächstgelegenen Schwerpunkt.
Beide Modelle werden vertreten durch Schwerpunkteund für eine neue Beobachtung berechnen wir einfach die Entfernung zu jedem Schwerpunkt, um zu entscheiden, zu welchem Schwerpunkt er gehört.
Der Unterschied liegt natürlich darin Klassifikator für den nächstgelegenen Schwerpunktwir schon wissen die Schwerpunkte, weil sie aus beschrifteten Klassen stammen.
In k-bedeutetwir kennen die Schwerpunkte nicht. Das gesamte Ziel des Algorithmus besteht darin entdecken passende direkt aus den Daten.
Das Geschäftsproblem ist ein völlig anderes: Anstatt Etiketten vorherzusagen, versuchen wir es erstellen ihnen.
Und in k-means der Wert von k (die Anzahl der Schwerpunkte) ist unbekannt. Es wird also ein Hyperparameter dass wir abstimmen können.
k-bedeutet mit nur einer Funktion
Wir beginnen mit einem winzigen 1D-Beispiel, damit alles auf einer Achse sichtbar ist. Und wir werden die Werte so trivial wählen, dass wir die beiden Schwerpunkte sofort sehen können.
1, 2, 3, 11, 12, 13
Ja, 2 und 12.
Aber woher sollte der Computer das wissen? Die Maschine „lernt“, indem sie Schritt für Schritt rät.
Hier kommt der genannte Algorithmus Lloyd’s-Algorithmus.
Wir werden es in Excel mit der folgenden Schleife implementieren:
- Wählen Sie die Anfangsschwerpunkte
- Berechnen Sie den Abstand von jedem Punkt zu jedem Schwerpunkt
- Ordnen Sie jeden Punkt dem nächstgelegenen Schwerpunkt zu
- Berechnen Sie die Schwerpunkte als Durchschnitt der Punkte in jedem Cluster neu
- Wiederholen Sie die Schritte 2 bis 4, bis sich die Schwerpunkte nicht mehr bewegen
1. Wählen Sie die Anfangsschwerpunkte
Wählen Sie zwei erste Zentren aus, zum Beispiel:
Sie sollten innerhalb des Datenbereichs liegen (zwischen 1 und 13).
2. Berechnen Sie Entfernungen
Für jeden Datenpunkt x:
- Berechne den Abstand zu c_1,
- Berechnen Sie den Abstand zu c_2.
Normalerweise verwenden wir den absoluten Abstand in 1D.
Wir haben jetzt zwei Abstandswerte für jeden Punkt.
3. Cluster zuweisen
Für jeden Punkt:
- vergleiche die beiden Abstände,
- Ordnen Sie den Cluster des Kleinsten zu (1 oder 2).
In Excel ist dies einfach IF oder MIN basierte Logik.
4. Berechnen Sie die neuen Schwerpunkte
Für jeden Cluster:
- nimm die diesem Cluster zugewiesenen Punkte,
- Berechnen Sie ihren Durchschnitt,
- dieser Durchschnitt wird zum neuen Schwerpunkt.
5. Iterieren Sie, bis die Konvergenz erreicht ist
Jetzt können wir in Excel dank der Formeln einfach Fügen Sie die neuen Schwerpunktwerte ein in die Zellen der anfänglichen Schwerpunkte.
Die Aktualisierung erfolgt sofort und nachdem Sie dies einige Male durchgeführt haben, werden Sie feststellen, dass sich die Werte nicht mehr ändern. Dann ist der Algorithmus konvergiert.
Wir können jeden Schritt auch in Excel aufzeichnen, um zu sehen, wie sich die Schwerpunkte und Cluster im Laufe der Zeit entwickeln.
k-bedeutet mit zwei Funktionen
Lassen Sie uns nun zwei Funktionen verwenden. Der Vorgang ist genau der gleiche, wir verwenden einfach den euklidischen Abstand in 2D.
Sie können entweder das tun Kopieren und Einfügen der neuen Schwerpunkte als Werte (mit nur wenigen zu aktualisierenden Zellen),
oder Sie können anzeigen alle Zwischenschritte um die vollständige Entwicklung des Algorithmus zu sehen.
Visualisierung der beweglichen Schwerpunkte in Excel
Um den Prozess intuitiver zu gestalten, ist es hilfreich, Diagramme zu erstellen, die zeigen, wie sich die Schwerpunkte bewegen.
Leider sind Excel oder Google Sheets für diese Art der Visualisierung nicht ideal und die Organisation der Datentabellen wird schnell etwas komplex.
Wenn Sie ein vollständiges Beispiel mit detaillierten Darstellungen sehen möchten, können Sie diesen Artikel lesen, den ich vor fast drei Jahren geschrieben habe, in dem jeder Schritt der Schwerpunktbewegung klar dargestellt wird.
Wie Sie auf diesem Bild sehen können, wurde das Arbeitsblatt ziemlich unorganisiert, insbesondere im Vergleich zur vorherigen Tabelle, die sehr einfach war.
Auswahl des optimalen k: Die Ellbogenmethode
Jetzt ist es also möglich, es zu versuchen k = 2 Und k = 3 in unserem Fall, und berechnen Sie die Trägheit für jeden einzelnen. Dann vergleichen wir einfach die Werte.
Wir können sogar mit k=1 beginnen.
Für jeden Wert von k:
- wir führen k-Means bis zur Konvergenz durch,
- Berechnen Sie die Trägheitdas ist die Summe der quadrierten Abstände zwischen jedem Punkt und dem ihm zugewiesenen Schwerpunkt.
In Excel:
- Nehmen Sie für jeden Punkt den Abstand zu seinem Schwerpunkt und quadrieren Sie ihn.
- Summieren Sie alle diese quadrierten Abstände.
- Dies ergibt die Trägheit für dieses k.
Zum Beispiel:
- für k = 1 ist der Schwerpunkt nur der Gesamtmittelwert von x1 und x2,
- Für k = 2 und k = 3 entnehmen wir die konvergierten Schwerpunkte den Blättern, auf denen Sie den Algorithmus ausgeführt haben.
Dann können wir die Trägheit als Funktion von k darstellen, zum Beispiel für (k = 1, 2, 3).
Für diesen Datensatz
- von 1 auf 2 sinkt die Trägheit stark,
- Von 2 auf 3 ist die Verbesserung viel geringer.
Der „Ellbogen“ ist der Wert von k, nach dem die Trägheitsabnahme marginal wird. Im Beispiel wird darauf hingewiesen, dass k = 2 ausreichend ist.
Abschluss
K-means ist ein sehr intuitiver Algorithmus, wenn man ihn Schritt für Schritt in Excel sieht.
Wir beginnen mit einfachen Schwerpunkten, berechnen Entfernungen, weisen Punkte zu, aktualisieren die Schwerpunkte und wiederholen den Vorgang. Jetzt können wir sehen, wie „Maschinen lernen“, oder?
Nun, das ist erst der Anfang, wir werden sehen, dass verschiedene Modelle auf ganz unterschiedliche Weise „lernen“.
Und hier ist der Übergang für den morgigen Artikel: die unbeaufsichtigte Version des Klassifikator für den nächstgelegenen Schwerpunkt ist in der Tat k-bedeutet.
Was wäre also die unbeaufsichtigte Version von? LDA oder QDA? Wir werden dies im nächsten Artikel beantworten.
