K-means находит группы в неразмеченных данных. Начиная с заданных центроидов, повторите iterations раз:
- Назначение: отнесите каждую точку к кластеру ближайшего центроида (евклидово расстояние). Если два центроида одинаково близки, выберите тот, у которого индекс меньше.
- Обновление: сдвиньте каждый центроид в среднее назначенных ему точек. Центроид без точек остаётся на месте.
Реализуйте k_means(points, centroids, iterations).
Входные данные
points: точки данных, каждая — список координат.
centroids: k начальных центроидов с тем же числом координат.
iterations: сколько раундов назначения и обновления выполнить.
Выходные данные
Верните итоговые центроиды в исходном порядке.
Ограничения
1 ≤ число точек ≤ 1000, 1 ≤ k ≤ 20, 1 ≤ размерность ≤ 10
0 ≤ iterations ≤ 100
-1000 ≤ каждая координата ≤ 1000
Примеры
Ввод:
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
Ожидаемый вывод:
expected = [
[1.25, 1.5],
[8.5, 8.25]
]Ввод:
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;
Ожидаемый вывод:
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};Ввод:
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;
Ожидаемый вывод:
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};Пояснение
Первые две точки ближе к (0, 0), а последние две — к (10, 10). Новые центроиды — это средние: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) и ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).
Ввод:
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
Ожидаемый вывод:
expected = [
[3.666667],
[100.0]
]Ввод:
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;
Ожидаемый вывод:
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};Ввод:
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;
Ожидаемый вывод:
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};Пояснение
Раунд 1: (100) далеко от всех точек, поэтому все три точки попадают к центроиду 1, который сдвигается в (0 + 1 + 10) / 3 ≈ 3.666667; центроид 2 не получает точек и остаётся в 100. Раунд 2 назначает так же, поэтому результат — [[3.666667], [100]].
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.