Problema
Il k-means trova gruppi in dati non etichettati. Partendo dai centroidi dati, ripeti iterations volte:
- Assegnazione: metti ogni punto nel cluster del centroide più vicino (distanza euclidea). Se due centroidi sono ugualmente vicini, scegli quello con l'indice minore.
- Aggiornamento: sposta ogni centroide sulla media dei punti assegnati. Un centroide senza punti resta dov'è.
Implementa k_means(points, centroids, iterations).
Input
points: I punti dei dati, ognuno una lista di coordinate.
centroids: I k centroidi iniziali, con lo stesso numero di coordinate.
iterations: Quanti cicli di assegnazione e aggiornamento eseguire.
Output
Restituisci i centroidi finali nel loro ordine originale.
Vincoli
1 ≤ numero di punti ≤ 1.000, 1 ≤ k ≤ 20, 1 ≤ dimensioni ≤ 10
0 ≤ iterations ≤ 100
-1.000 ≤ ogni coordinata ≤ 1.000
Esempi
Input:
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
Output atteso:
expected = [
[1.25, 1.5],
[8.5, 8.25]
]Input:
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;
Output atteso:
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};Input:
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;
Output atteso:
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};Spiegazione
I primi due punti sono più vicini a (0, 0) e gli ultimi due a (10, 10). I nuovi centroidi sono le medie: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) e ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).
Input:
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
Output atteso:
expected = [
[3.666667],
[100.0]
]Input:
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;
Output atteso:
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};Input:
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;
Output atteso:
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};Spiegazione
Ciclo 1: (100) è lontano da ogni punto, quindi tutti e tre i punti vanno al centroide 1, che si sposta a (0 + 1 + 10) / 3 ≈ 3.666667; il centroide 2 non riceve punti e resta a 100. Il ciclo 2 assegna allo stesso modo, quindi il risultato è [[3.666667], [100]].
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.