Problema
O k-means encontra grupos em dados sem rótulo. Começando pelos centroides dados, repita iterations vezes:
- Atribuir: coloque cada ponto no cluster do centroide mais próximo (distância euclidiana). Se dois centroides estiverem à mesma distância, escolha o de menor índice.
- Atualizar: mova cada centroide para a média dos pontos atribuídos a ele. Um centroide sem pontos fica onde está.
Implemente k_means(points, centroids, iterations).
Entrada
points: Os pontos de dados, cada um uma lista de coordenadas.
centroids: Os k centroides iniciais, com o mesmo número de coordenadas.
iterations: Quantas rodadas de atribuir e atualizar executar.
Saída
Retorne os centroides finais na ordem original.
Restrições
1 ≤ número de pontos ≤ 1.000, 1 ≤ k ≤ 20, 1 ≤ dimensões ≤ 10
0 ≤ iterations ≤ 100
-1.000 ≤ cada coordenada ≤ 1.000
Exemplos
Entrada:
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
Saída esperada:
expected = [
[1.25, 1.5],
[8.5, 8.25]
]Entrada:
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;
Saída esperada:
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};Entrada:
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;
Saída esperada:
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};Explicação
Os dois primeiros pontos estão mais perto de (0, 0) e os dois últimos de (10, 10). Os novos centroides são as médias: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) e ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).
Entrada:
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
Saída esperada:
expected = [
[3.666667],
[100.0]
]Entrada:
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;
Saída esperada:
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};Entrada:
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;
Saída esperada:
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};Explicação
Rodada 1: (100) está longe de todos os pontos, então os três pontos vão para o centroide 1, que se move para (0 + 1 + 10) / 3 ≈ 3.666667; o centroide 2 não recebe pontos e continua em 100. A rodada 2 atribui do mesmo jeito, então o resultado é [[3.666667], [100]].
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.