Inhaltsverzeichnis
1. Einleitung
2. Was macht der Ok-Means-Algorithmus?
3. Implementierung in Python
4. Bewertung und Interpretation
5. Schlussfolgerungen und nächste Schritte
Die meisten der weit verbreiteten Algorithmen für maschinelles Lernen, wie z. B. lineare Regression, logistische Regression, Entscheidungsbäume und andere, sind nützlich, um Vorhersagen aus beschrifteten Daten zu treffen, d. h. jede Eingabe umfasst Merkmalswerte, denen ein Beschriftungswert zugeordnet ist. So heißt es Überwachtes Lernen.
Allerdings müssen wir oft mit großen Datensätzen umgehen, denen keine Beschriftung zugeordnet ist. Stellen Sie sich ein Unternehmen vor, das die verschiedenen Kundengruppen anhand von Kaufverhalten, Demografie, Adresse und anderen Informationen verstehen muss, um bessere Dienstleistungen, Produkte und Werbeaktionen anbieten zu können.
Diese Artwork von Problemen kann mit der Verwendung von angegangen werden Unbeaufsichtigtes Lernen Techniken. Der Ok-Means-Algorithmus ist ein weit verbreiteter unbeaufsichtigter Lernalgorithmus im maschinellen Lernen. Sein einfacher und eleganter Ansatz ermöglicht es, einen Datensatz in eine gewünschte Anzahl von Ok unterschiedlichen Clustern zu unterteilen und so Muster aus unbeschrifteten Daten zu lernen.
Wie bereits erwähnt, versucht der Ok-Means-Algorithmus, Datenpunkte in eine bestimmte Anzahl von Clustern zu unterteilen. Die Punkte innerhalb jedes Clusters sind ähnlich, während Punkte in verschiedenen Clustern erhebliche Unterschiede aufweisen.
Vor diesem Hintergrund stellt sich die Frage: Wie definieren wir Ähnlichkeit oder Unterschied? Beim Ok-Means-Clustering ist der euklidische Abstand die gebräuchlichste Metrik zur Messung der Ähnlichkeit.
In der Abbildung unten können wir deutlich drei verschiedene Gruppen erkennen. Daher könnten wir die Mittelpunkte jeder Gruppe bestimmen und jeder Punkt würde dem nächstgelegenen Mittelpunkt zugeordnet.
Auf diese Weise besteht mathematisch gesehen die Idee darin, die zu minimieren Varianz innerhalb des Clustersdas Maß der Ähnlichkeit zwischen jedem Punkt und seinem nächstgelegenen Mittelpunkt.
Die Durchführung der Aufgabe im obigen Beispiel struggle unkompliziert, da die Daten zweidimensional waren und die Gruppen deutlich unterschiedlich waren. Da jedoch die Anzahl der Dimensionen zunimmt und unterschiedliche Werte von Ok berücksichtigt werden, benötigen wir einen Algorithmus, um die Komplexität zu bewältigen.
Schritt 1: Wählen Sie die anfänglichen Zentren aus (zufällig)
Wir müssen den Algorithmus mit anfänglichen Mittelvektoren ausstatten, die zufällig aus den Daten ausgewählt werden können, oder Zufallsvektoren mit den gleichen Abmessungen wie die Originaldaten generieren. Sehen Sie sich die weißen Diamanten im Bild unten an.
Schritt 2: Ermitteln Sie die Abstände jedes Punktes zu den Mittelpunkten
Jetzt berechnen wir den Abstand jedes Datenpunkts zu den Ok-Zentren. Dann verknüpfen wir jeden Punkt mit dem Mittelpunkt, der diesem Punkt am nächsten liegt.
Gegeben sei ein Datensatz mit N Einträge und M Merkmale, die Abstände zu den Zentren C kann durch die folgende Gleichung angegeben werden:
Wo:
okay variiert von 1 bis Ok;
D ist der Abstand eines Punktes n zum okay Heart;
X ist der Punktvektor;
C ist der Zentrumsvektor.
Daher für jeden Datenpunkt N Wir haben Ok Abstände, dann müssen wir den Vektor zum Mittelpunkt mit dem kleinsten Abstand beschriften:
Wo D ist ein Vektor mit Ok Entfernungen.
Schritt 3: Finden Sie die Ok Schwerpunkte und iterieren
Für jeden der Ok Cluster, berechnen Sie den Schwerpunkt neu. Der neue Schwerpunkt ist der Mittelwert aller diesem Cluster zugewiesenen Datenpunkte. Aktualisieren Sie dann die Positionen der Schwerpunkte auf die neu berechneten.
Überprüfen Sie, ob sich die Schwerpunkte gegenüber der vorherigen Iteration erheblich geändert haben. Dies kann durch einen Vergleich der Positionen der Schwerpunkte in der aktuellen Iteration mit denen in der letzten Iteration erfolgen.
Wenn sich die Schwerpunkte erheblich geändert haben, kehren Sie zu Schritt 2 zurück. Wenn nicht, ist der Algorithmus konvergiert und der Prozess stoppt. Siehe das Bild unten.
Nachdem wir nun die grundlegenden Konzepte des Ok-Means-Algorithmus kennen, ist es an der Zeit, eine Python-Klasse zu implementieren. Die verwendeten Pakete waren Numpy für mathematische Berechnungen, Matplotlib zur Visualisierung und das Make_blobs-Paket von Sklearn für simulierte Daten.
# import required packages
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
Die Klasse verfügt über die folgenden Methoden:
Eine Konstruktormethode zum Initialisieren der Grundparameter des Algorithmus: der Wert okay von Clustern, die maximale Anzahl von Iterationen max_iter, und die Toleranz Tol Wert, um die Optimierung zu unterbrechen, wenn keine signifikante Verbesserung eintritt.
Diese Methoden zielen darauf ab, den Optimierungsprozess während des Trainings zu unterstützen, z. B. die Berechnung des euklidischen Abstands, die zufällige Auswahl der anfänglichen Schwerpunkte, die Zuweisung des nächstgelegenen Schwerpunkts zu jedem Punkt, die Aktualisierung der Schwerpunktwerte und die Überprüfung, ob die Optimierung konvergiert.
Wie bereits erwähnt, handelt es sich beim Ok-Means-Algorithmus um eine unbeaufsichtigte Lerntechnik, was bedeutet, dass während des Trainingsprozesses keine gekennzeichneten Daten erforderlich sind. Auf diese Weise ist eine einzige Methode erforderlich, um die Daten anzupassen und vorherzusagen, zu welchem Cluster jeder Datenpunkt gehört.
Eine Methode zur Bewertung der Qualität der Optimierung durch Berechnung der Gesamtquadratfehler der Optimierung. Das wird im nächsten Abschnitt untersucht.
Hier ist der vollständige Code:
class Kmeans:# assemble technique for hyperparameter initialization
def __init__(self, okay=3, max_iter=100, tol=1e-06):
self.okay = okay
self.max_iter = max_iter
self.tol = tol
# randomly picks the preliminary centroids from the enter knowledge
def pick_centers(self, X):
centers_idxs = np.random.alternative(self.n_samples, self.okay)
return X(centers_idxs)
# finds the closest centroid for every knowledge level
def get_closest_centroid(self, x, centroids):
distances = (euclidean_distance(x, centroid) for centroid in centroids)
return np.argmin(distances)
# creates an inventory with lists containing the idxs of every cluster
def create_clusters(self, centroids, X):
clusters = (() for _ in vary(self.okay))
labels = np.empty(self.n_samples)
for i, x in enumerate(X):
centroid_idx = self.get_closest_centroid(x, centroids)
clusters(centroid_idx).append(i)
labels(i) = centroid_idx
return clusters, labels
# calculates the centroids for every cluster utilizing the imply worth
def compute_centroids(self, clusters, X):
centroids = np.empty((self.okay, self.n_features))
for i, cluster in enumerate(clusters):
centroids(i) = np.imply(X(cluster), axis=0)
return centroids
# helper operate to confirm if the centroids modified considerably
def is_converged(self, old_centroids, new_centroids):
distances = (euclidean_distance(old_centroids(i), new_centroids(i)) for i in vary(self.okay))
return (sum(distances) < self.tol)
# technique to coach the information, discover the optimized centroids and label every knowledge level in accordance with its cluster
def fit_predict(self, X):
self.n_samples, self.n_features = X.form
self.centroids = self.pick_centers(X)
for i in vary(self.max_iter):
self.clusters, self.labels = self.create_clusters(self.centroids, X)
new_centroids = self.compute_centroids(self.clusters, X)
if self.is_converged(self.centroids, new_centroids):
break
self.centroids = new_centroids
# technique for evaluating the intracluster variance of the optimization
def clustering_errors(self, X):
cluster_values = (X(cluster) for cluster in self.clusters)
squared_distances = ()
# calculation of whole squared Euclidean distance
for i, cluster_array in enumerate(cluster_values):
squared_distances.append(np.sum((cluster_array - self.centroids(i))**2))
total_error = np.sum(squared_distances)
return total_error
Jetzt verwenden wir die Ok-Means-Klasse, um das Clustering simulierter Daten durchzuführen. Dazu wird es verwendet Blobs erstellen Paket aus der Sklearn-Bibliothek. Die Daten bestehen aus 500 zweidimensionalen Punkten mit 4 festen Zentren.
# create simulated knowledge for examples
X, _ = make_blobs(n_samples=500, n_features=2, facilities=4,
shuffle=False, random_state=0)
Nachdem wir das Coaching mit vier Clustern durchgeführt haben, erzielen wir das folgende Ergebnis.
mannequin = Kmeans(okay=4)
mannequin.fit_predict(X)
labels = mannequin.labels
centroids =mannequin.centroids
plot_clusters(X, labels, centroids)
In diesem Fall struggle der Algorithmus in der Lage, die Cluster mit 18 Iterationen erfolgreich zu berechnen. Allerdings müssen wir bedenken, dass wir die optimale Anzahl an Clustern bereits aus den simulierten Daten kennen. In realen Anwendungen kennen wir diesen Wert oft nicht.
Wie bereits erwähnt, zielt der Ok-Means-Algorithmus darauf ab, Varianz innerhalb des Clusters so klein wie möglich. Die zur Berechnung dieser Varianz verwendete Metrik ist die gesamte quadrierte euklidische Distanz gegeben von:
Wo:
p ist die Anzahl der Datenpunkte in einem Cluster;
c_i ist der Schwerpunktvektor eines Clusters;
Ok ist die Anzahl der Cluster.
In Worten: Die obige Formel addiert die Abstände der Datenpunkte zum nächsten Schwerpunkt. Der Fehler nimmt mit zunehmender Zahl Ok ab.
Im Extremfall Ok = N haben Sie einen Cluster für jeden Datenpunkt und dieser Fehler ist Null.
Willmott, Paul (2019).
Wenn wir den Fehler gegen die Anzahl der Cluster auftragen und uns ansehen, wo sich die Grafik „biegt“, können wir die optimale Anzahl von Clustern ermitteln.
Wie wir sehen können, hat das Diagramm eine „Ellenbogenform“ und knickt bei Ok = 4 ab, was bedeutet, dass bei höheren Ok-Werten die Verringerung des Gesamtfehlers weniger signifikant ist.
In diesem Artikel haben wir die grundlegenden Konzepte des Ok-Means-Algorithmus, seine Verwendung und Anwendungen behandelt. Mithilfe dieser Konzepte konnten wir außerdem eine Python-Klasse von Grund auf implementieren, die das Clustering simulierter Daten durchführte und zeigte, wie mithilfe eines Scree-Plots der optimale Wert für Ok ermittelt werden konnte.
Da es sich jedoch um eine unbeaufsichtigte Technik handelt, gibt es noch einen zusätzlichen Schritt. Der Algorithmus kann den Clustern erfolgreich eine Bezeichnung zuweisen, aber die Bedeutung jeder Bezeichnung ist eine Aufgabe, die der Datenwissenschaftler oder Ingenieur für maschinelles Lernen durch die Analyse der Daten jedes Clusters erledigen muss.
Darüber hinaus möchte ich einige Punkte zur weiteren Erkundung hinterlassen:
- Unsere simulierten Daten verwendeten zweidimensionale Punkte. Versuchen Sie, den Algorithmus für andere Datensätze zu verwenden und die optimalen Werte für Ok zu finden.
- Es gibt andere weit verbreitete unbeaufsichtigte Lernalgorithmen, wie z Hierarchisches Clustering.
- Je nach Problembereich kann es erforderlich sein, andere Fehlermaße wie Manhattan-Distanz und Kosinus-Ähnlichkeit zu verwenden. Versuchen Sie, diese zu untersuchen.
Vollständiger Code verfügbar Hier: