So funktioniert das Clustering mit k-Means-Algorithmen

k-Means ist ein Algorithmus, der ein Modell schult, das ähnliche Objekte gruppiert. Der k-Means-Algorithmus erreicht dies, indem er jeder Beobachtung in der Eingabemenge einen Punkt im n-dimensionalen Raum zuweist (wobei n gleich der Anzahl der Attribute der Beobachtung ist). Beispiel: Angenommen, Ihr Datensatz enthält Beobachtungen über Temperatur und Luftfeuchtigkeit an einem bestimmten Standort, die auf Punkte (t, h) in einem zweidimensionalen Raum abgebildet sind.

Anmerkung

Clustering-Algorithmen sind unüberwacht. Bei unüberwachtem Lernen werden Kennzeichnungen, die den Objekten im Schulungsdatensatz zugeordnet werden, nicht verwendet. Weitere Informationen finden Sie unter Unüberwachtes Lernen.

Beim k-means-Clustering hat jedes Cluster ein Zentrum. Bei der Modellschulung verwendet der k-Means-Algorithmus den Abstand zwischen einer Beobachtung im Datensatz und dem Clusterzentrum als Grundlage für das Clustering. Sie wählen die Anzahl der zu erstellenden (k) Cluster.

Angenommen, Sie möchten ein Modell erstellen, das handschriftliche Zahlen erkennt und Sie wählen für die Schulung einen MNIST-Datensatz aus. Der Datensatz enthält Tausende von Bildern handschriftlicher Zahlen (0 bis 9). In diesem Beispiel können Sie beispielsweise 10 Cluster erstellen, einen für jede Ziffer (0, 1,..., 9). Im Rahmen der Modellschulung gruppiert der k-Means-Algorithmus die eingegebenen Bilder in 10 Cluster.

Jedes Bild im MNIST-Datensatz ist ein 28x28-Pixel-Bild mit insgesamt 784 Pixeln. Jedes Bild entspricht einem Punkt in einem 784-dimensionalen Raum, ähnlich einem Punkt in einem zweidimensionalen Raum (x, y). Um ein Cluster zu finden, dem der Punkt zugeordnet werden kann, sucht der k-Means-Algorithmus den Abstand dieses Punktes von allen Clusterzentren. Dann wählt der Algorithmus das Cluster mit dem nächsten Zentrum als Cluster aus, zu dem das Bild gehört.

Anmerkung

Amazon SageMaker verwendet eine angepasste Version des Algorithmus, bei der Sie, anstatt anzugeben, dass der Algorithmus k Cluster erstellen soll, die Modellgenauigkeit durch Angabe zusätzlicher Clusterzentren (K = k*x) verbessern können. Der Algorithmus reduziert diese jedoch letztendlich auf k Cluster.

In SageMaker legen Sie die Anzahl der Cluster beim Erstellen eines Trainingsauftrags fest. Weitere Informationen finden Sie unter CreateTrainingJob. Im Anforderungstext fügen Sie die HyperParameters String-Zuweisung hinzu, um die Strings k und extra_center_factor festzulegen.

Die folgende Übersicht zeigt, wie der k-Means-Algorithmus für die Modelltraining in SageMaker funktioniert:

1. Er bestimmt die anfänglichen K Clusterzentren.

   Anmerkung

   In den folgenden Themen beziehen sich K Cluster auf k * x, wobei Sie k und x beim Erstellen eines Modellschulungsauftrags festlegen.

2. Die eingegebenen Schulungsdaten werden abgearbeitet und die Cluster-Zentren neu berechnet.

3. Die sich daraus ergebenden Cluster werden auf k reduziert (wenn der Datenexperte in der Anforderung festgelegt hat, dass k*x Cluster erstellt werden).

In den folgenden Abschnitten werden einige der Parameter erläutert, die ein Datenexperte festlegen kann, um einen Modelltrainingssauftrag als Teil der String-Zuweisung HyperParameters zu konfigurieren.

Schritt 1: Festlegen der anfänglichen Clusterzentren

Bei der Verwendung von k-Means in SageMaker werden die anfänglichen Clusterzentren in kleinen, nach dem Zufallsprinzip zusammengestellten Batches aus den Beobachtungen ausgewählt. Wählen Sie eine der folgenden Strategien, um zu festzulegen, wie diese anfänglichen Clusterzentren ausgewählt werden:

• Der Zufallsansatz—Wählen Sie zufällig K-Beobachtungen in Ihrem Eingabedatensatz als Clusterzentren aus. Sie können beispielsweise ein Clusterzentrum auswählen, das auf den 784 dimensionalen Raum verweist, der 10 beliebigen Bildern im MNIST-Schulungsdatensatz entspricht.

• Der Ansatz k-Means++ funktioniert folgendermaßen:

  1. Sie beginnen mit einem Cluster und legen seine Zentren fest. Sie wählen zufällig eine Beobachtung aus Ihrem Schulungsdataset und verwenden den Punkt, welcher der Beobachtung entspricht, als Clusterzentrum. Wählen Sie z.B. im MNIST-Datensatz nach dem Zufallsprinzip ein handschriftliches Zahlenbild aus. Wählen Sie dann den Punkt im 784-dimensionalen Raum, der dem Bild als Ihrem Clusterzentrum entspricht. Dies ist das Clusterzentrum 1.

  2. Bestimmen Sie das Zentrum für Cluster 2. Von den verbleibenden Beobachtungen im Schulungsdatensatz suchen Sie nach dem Zufallsprinzip eine Beobachtung heraus. Wählen Sie eine, die sich von den zuvor ausgewählten unterscheidet. Diese Beobachtung entspricht einem Punkt, der von Clusterzentrum 1 weit entfernt ist. Führen Sie die folgenden Schritte aus, um den MNIST-Datensatz als Beispiel zu verwenden:

     • Finden Sie für jedes der restlichen Bilder den Abstand des entsprechenden Punktes von Clusterzentrum 1. Bilden Sie das Quadrat des Abstands und weisen Sie eine Wahrscheinlichkeit zu, die proportional zum Quadrat des Abstands ist. Auf diese Weise erhöht sich die Wahrscheinlichkeit, dass ein Bild als Clusterzentrum 2 ausgewählt wird, das sich von dem zuvor ausgewählten unterscheidet.

     • Wählen Sie eines der Bilder nach dem Zufallsprinzip, basierend auf den Wahrscheinlichkeiten, die im vorherigen Schritt zugewiesen wurden. Der Punkt, der dem angegebenen Bild entspricht, ist Clusterzentrum 2.

  3. Wiederholen Sie Schritt 2, um das Clusterzentrum 3 zu finden. Suchen Sie dieses Mal die Abstände der verbleibenden Bilder vom Clusterzentrum 2.

  4. Wiederholen Sie diesen Vorgang, bis Sie K Clusterzentren vorliegen haben.

Um ein Modell in SageMaker zu trainieren, erstellen Sie einen Trainingsauftrag. Stellen Sie in der Anforderung die Konfigurationsinformationen bereit, indem Sie folgende HyperParameters String-Zuweisung angeben:

• Um die Anzahl der zu erstellenden Cluster anzugeben, fügen Sie die k-Zeichenfolge hinzu.

• Um eine größere Genauigkeit zu erzielen, fügen Sie die optionale extra_center_factor-Zeichenfolge hinzu.

• Um die Strategie, die Sie zur Ermittlung der ersten Clusterzentren verwenden möchten, zu bestimmen, fügen Sie die Zeichenfolge init_method hinzu und setzen Sie ihren Wert auf random oder k-means++.

Weitere Informationen zum K-Means-Schätzer von SageMaker finden Sie unter K-Means in der Amazon SageMaker Python SDK-Dokumentation.

Sie verfügen jetzt über einen ersten Satz an Clusterzentren.

Schritt 2: Arbeiten Sie den Schulungsdatensatz ab und berechnen Sie die Clusterzentren

Die Clusterzentren, die Sie im vorhergehenden Schritt erstellt haben, sind meistens nach dem Zufallsprinzip unter Berücksichtigung des Schulungsdatensatzes entstanden. In diesem Schritt verwenden Sie den Schulungsdatensatz, um diese Zentren in die richtigen Clusterzentren zu verschieben. Der Algorithmus arbeitet das Schulungsdataset ab und berechnet die K- Clusterzentren neu.

1. Lesen Sie eine Mini-Stapel an Beobachtungen (eine kleine, nach dem Zufallsprinzip ausgewählte Teilmenge aller Datensätze) aus dem Schulungsdatensatz und führen Sie die folgenden Schritte aus.

   Anmerkung

   Beim Erstellen eines Modellschulungsauftrags geben Sie die Stapelgröße in der Zeichenfolge mini_batch_size in der Zeichenfolgenzuweisung HyperParameters an.

   1. Weisen Sie alle Beobachtungen im Mini-Stapel einem der Cluster mit dem nächstgelegenen Clusterzentrum zu.

   2. Berechnen Sie die Anzahl der Beobachtungen, die jedem Cluster zugewiesen werden. Anschließend berechnen Sie den Anteil der neuen Punkte, die jedem Cluster zugeordnet werden.

      Betrachten wir z. B. die folgenden Cluster:

      Cluster c1 = 100 zuvor zugewiesene Punkte. Sie haben in diesem Schritt 25 Punkte aus dem Mini-Stapel zugeordnet.

      Cluster c2 = 150 zuvor zugewiesene Punkte. Sie haben in diesem Schritt 40 Punkte aus dem Mini-Stapel zugeordnet.

      Cluster c3 = 450 zuvor zugewiesene Punkte. Sie haben in diesem Schritt 5 Punkte aus dem Mini-Stapel zugeordnet.

      Berechnen Sie den Anteil der neuen Punkte, die jedem Cluster zugewiesen wurden, wie folgt:

      p1 = proportion of points assigned to c1 = 25/(100+25)
      p2 = proportion of points assigned to c2 = 40/(150+40)
      p3 = proportion of points assigned to c3 = 5/(450+5)

   3. Berechnen Sie den Mittelpunkt der neuen Punkte, die jedem Cluster hinzugefügt wurden:

      d1 = center of the new points added to cluster 1
      d2 = center of the new points added to cluster 2
      d3 = center of the new points added to cluster 3

   4. Berechnen Sie den gewichteten Durchschnitt wie im Folgenden dargestellt, um die aktualisierten Clusterzentrem zu finden:

      Center of cluster 1 = ((1 - p1) * center of cluster 1) + (p1 * d1)
      Center of cluster 2 = ((1 - p2) * center of cluster 2) + (p2 * d2)
      Center of cluster 3 = ((1 - p3) * center of cluster 3) + (p3 * d3)

2. Lesen Sie den nächsten Mini-Stapel und wiederholen Sie Schritt 1, um die Clusterzentren neu zu berechnen.

3. Weitere Informationen zu k-Means-Mini-Batches finden Sie unter Web-Scale k-means Clustering.

Schritt 3: Reduzieren Sie die Cluster von K auf k

Wenn der Algorithmus K-Cluster erstellt hat– (K = k*x), wobei x größer als 1 ist– dann reduziert er K-Cluster auf k-Cluster. (Weitere Informationen finden Sie unter extra_center_factor der vorangegangenen Diskussion.) Dies geschieht durch Anwendung der Methode von Lloyd mit der kmeans++-Initialisierung auf die K Clusterzentren. Weitere Informationen zur Lloyd-Methode finden Sie unter k-means clustering.