Mittel 0 gelöst 0% Erfolgsquote

K-Means-Clustering

Teile Punkte in k Cluster ein, indem du sie wiederholt dem nächsten Zentroid zuordnest und die Zentroide verschiebst.

Das lernst du

  • Punkte dem nächsten Zentroid zuordnen
  • Zentroide zum Mittelwert des Clusters verschieben
  • Einen Algorithmus wiederholen, bis er sich stabilisiert

Problem

K-Means findet Gruppen in unbeschrifteten Daten. Beginne mit den gegebenen Zentroiden und wiederhole iterations-mal:

  1. Zuordnen: Ordne jeden Punkt dem Cluster seines nächsten Zentroids zu (euklidischer Abstand). Sind zwei Zentroide gleich nah, wähle den mit dem kleineren Index.
  2. Aktualisieren: Verschiebe jeden Zentroid zum Mittelwert der ihm zugeordneten Punkte. Ein Zentroid ohne Punkte bleibt, wo er ist.

Implementiere k_means(points, centroids, iterations).

Eingabe

points: Die Datenpunkte, jeweils eine Liste von Koordinaten.

centroids: Die k Start-Zentroide mit derselben Anzahl an Koordinaten.

iterations: Wie viele Runden aus Zuordnen und Aktualisieren ausgeführt werden.

Ausgabe

Gib die endgültigen Zentroide in ihrer ursprünglichen Reihenfolge zurück.

Einschränkungen

1 ≤ Anzahl der Punkte ≤ 1.000, 1 ≤ k ≤ 20, 1 ≤ Dimensionen ≤ 10

0 ≤ iterations ≤ 100

-1.000 ≤ jede Koordinate ≤ 1.000

Beispiele

Beispiel 1
Eingabe:
points = [
    [1.0, 1.0],
    [1.5, 2.0],
    [8.0, 8.0],
    [9.0, 8.5]
]
centroids = [
    [0.0, 0.0],
    [10.0, 10.0]
]
iterations = 1

Erwartete Ausgabe:
expected = [
    [1.25, 1.5],
    [8.5, 8.25]
]
Eingabe:
std::vector<std::vector<double>> points = {
    {1.0, 1.0},
    {1.5, 2.0},
    {8.0, 8.0},
    {9.0, 8.5}
};
std::vector<std::vector<double>> centroids = {
    {0.0, 0.0},
    {10.0, 10.0}
};
long long iterations = 1;

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {1.25, 1.5},
    {8.5, 8.25}
};
Eingabe:
double[][] points = new double[][] {
    new double[] {1.0, 1.0},
    new double[] {1.5, 2.0},
    new double[] {8.0, 8.0},
    new double[] {9.0, 8.5}
};
double[][] centroids = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {10.0, 10.0}
};
long iterations = 1;

Erwartete Ausgabe:
double[][] expected = new double[][] {
    new double[] {1.25, 1.5},
    new double[] {8.5, 8.25}
};

Erläuterung

Die ersten beiden Punkte liegen näher an (0, 0) und die letzten beiden näher an (10, 10). Die neuen Zentroide sind die Mittelwerte: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) und ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).

Beispiel 2
Eingabe:
points = [
    [0.0],
    [1.0],
    [10.0]
]
centroids = [
    [0.0],
    [100.0]
]
iterations = 2

Erwartete Ausgabe:
expected = [
    [3.666667],
    [100.0]
]
Eingabe:
std::vector<std::vector<double>> points = {
    {0.0},
    {1.0},
    {10.0}
};
std::vector<std::vector<double>> centroids = {
    {0.0},
    {100.0}
};
long long iterations = 2;

Erwartete Ausgabe:
std::vector<std::vector<double>> expected = {
    {3.666667},
    {100.0}
};
Eingabe:
double[][] points = new double[][] {
    new double[] {0.0},
    new double[] {1.0},
    new double[] {10.0}
};
double[][] centroids = new double[][] {
    new double[] {0.0},
    new double[] {100.0}
};
long iterations = 2;

Erwartete Ausgabe:
double[][] expected = new double[][] {
    new double[] {3.666667},
    new double[] {100.0}
};

Erläuterung

Runde 1: (100) ist von jedem Punkt weit entfernt, also kommen alle drei Punkte zu Zentroid 1, der sich zu (0 + 1 + 10) / 3 ≈ 3.666667 verschiebt; Zentroid 2 erhält keine Punkte und bleibt bei 100. Runde 2 ordnet genauso zu, also ist das Ergebnis [[3.666667], [100]].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Wechsle zwischen dem Zuweisen jedes Punkts zum nächsten Zentroiden und dem Neuberechnen jedes Zentroiden aus seinen zugewiesenen Punkten.

Hinweis 2

Bei gleichen Distanzen wähle den Zentroiden mit dem kleineren Index, und lass einen leeren Zentroiden unverändert.

Hinweis 3

Bilde für jede Koordinate separat den Durchschnitt und wiederhole den kompletten Zuweisungs-/Update-Zyklus genau die angegebene Anzahl an Malen.

Erwartete Komplexität

Zeit O(iterations × n × k × d), zusätzlicher Speicher O(n + k d)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.