Problème
K-means trouve des groupes dans des données non étiquetées. En partant des centroïdes donnés, répétez iterations fois :
- Assignation : placez chaque point dans le cluster de son centroïde le plus proche (distance euclidienne). Si deux centroïdes sont à égale distance, choisissez celui d'indice le plus petit.
- Mise à jour : déplacez chaque centroïde vers la moyenne des points qui lui sont assignés. Un centroïde sans point reste où il est.
Implémentez k_means(points, centroids, iterations).
Entrée
points : les points de données, chacun étant une liste de coordonnées.
centroids : les k centroïdes de départ, avec le même nombre de coordonnées.
iterations : le nombre de tours d'assignation et de mise à jour à effectuer.
Sortie
Renvoyez les centroïdes finaux dans leur ordre d'origine.
Contraintes
1 ≤ nombre de points ≤ 1 000, 1 ≤ k ≤ 20, 1 ≤ dimensions ≤ 10
0 ≤ iterations ≤ 100
-1 000 ≤ chaque coordonnée ≤ 1 000
Exemples
Entrée :
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
Sortie attendue :
expected = [
[1.25, 1.5],
[8.5, 8.25]
]Entrée :
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;
Sortie attendue :
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};Entrée :
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;
Sortie attendue :
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};Explication
Les deux premiers points sont plus proches de (0, 0) et les deux derniers de (10, 10). Les nouveaux centroïdes sont les moyennes : ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) et ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).
Entrée :
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
Sortie attendue :
expected = [
[3.666667],
[100.0]
]Entrée :
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;
Sortie attendue :
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};Entrée :
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;
Sortie attendue :
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};Explication
Tour 1 : (100) est loin de tous les points, donc les trois points rejoignent le centroïde 1, qui se déplace en (0 + 1 + 10) / 3 ≈ 3.666667 ; le centroïde 2 ne reçoit aucun point et reste à 100. Le tour 2 assigne de la même façon, donc le résultat est [[3.666667], [100]].
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.