Mittel 0 gelöst 0% Erfolgsquote

K-Means Clustering

Group points into k clusters by repeatedly assigning them to the nearest centroid and moving the centroids.

Das lernst du

  • Assign points to the nearest centroid
  • Move centroids to the cluster mean
  • Iterate an algorithm until it settles

Problem

Übersetzung anzeigen

K-means finds groups in unlabeled data. Starting from the given centroids, repeat iterations times:

  1. Assign: put each point in the cluster of its nearest centroid (Euclidean distance). If two centroids are equally close, choose the one with the smaller index.
  2. Update: move each centroid to the average of the points assigned to it. A centroid with no points stays where it is.

Implement k_means(points, centroids, iterations).

Input

points: The data points, each a list of coordinates.

centroids: The k starting centroids, with the same number of coordinates.

iterations: How many assign-and-update rounds to run.

Output

Return the final centroids in their original order.

Einschränkungen

1 ≤ number of points ≤ 1,000, 1 ≤ k ≤ 20, 1 ≤ dimensions ≤ 10

0 ≤ iterations ≤ 100

-1,000 ≤ each coordinate ≤ 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

The first two points are nearer to (0, 0) and the last two nearer to (10, 10). The new centroids are the averages: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) and ((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

Round 1: (100) is far from every point, so all three points join centroid 1, which moves to (0 + 1 + 10) / 3 ≈ 3.666667; centroid 2 gets no points and stays at 100. Round 2 assigns the same way, so the result is [[3.666667], [100]].

So gehst du vor

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

Hinweis 1

Alternate between assigning every point to its nearest centroid and recomputing each centroid from its assigned points.

Hinweis 2

When distances tie, choose the centroid with the smaller index, and keep an empty centroid unchanged.

Hinweis 3

Average each coordinate independently, and repeat the full assign-update cycle exactly the requested number of times.

Erwartete Komplexität

O(iterations × n × k × d) time, O(n + k d) extra space

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.