Problem
K-Means findet Gruppen in unbeschrifteten Daten. Beginne mit den gegebenen Zentroiden und wiederhole iterations-mal:
- 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.
- 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
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).
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]].
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.