Метод k ближайших соседей (KNN) классифицирует новую точку, глядя на k ближайших к ней обучающих точек и выбирая самую частую метку.
- Вычислите евклидово расстояние от
queryдо каждой точки. - Отсортируйте точки по расстоянию; если расстояния равны, раньше идёт точка с меньшим индексом.
- Возьмите первые k точек и посчитайте их метки.
- Верните метку с наибольшим числом голосов. При ничьей верните ту метку, чья ближайшая точка идёт раньше в отсортированном порядке.
Реализуйте knn_predict(points, labels, query, k).
Входные данные
points: обучающие точки, каждая — список координат.
labels: метка каждой точки.
query: точка, которую нужно классифицировать.
k: сколько соседей голосуют.
Выходные данные
Верните предсказанную метку.
Ограничения
1 ≤ k ≤ число точек ≤ 1000
1 ≤ размерность ≤ 20
-1000 ≤ каждая координата ≤ 1000
Примеры
Ввод:
k = 3
query = [3.0, 3.0]
labels = ["A", "A", "B", "B"]
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
Ожидаемый вывод:
expected = "A"Ввод:
long long k = 3;
std::vector<double> query = {3.0, 3.0};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
Ожидаемый вывод:
std::string expected = "A";Ввод:
long k = 3;
double[] query = new double[] {3.0, 3.0};
string[] labels = new string[] {"A", "A", "B", "B"};
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {2.0, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 9.0}
};
Ожидаемый вывод:
string expected = "A";Пояснение
Расстояния от (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Три ближайшие метки — A, A и B, поэтому ответ A.
Ввод:
k = 2
query = [1.0, 1.0]
labels = ["red", "blue", "blue", "red"]
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
Ожидаемый вывод:
expected = "red"Ввод:
long long k = 2;
std::vector<double> query = {1.0, 1.0};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
Ожидаемый вывод:
std::string expected = "red";Ввод:
long k = 2;
double[] query = new double[] {1.0, 1.0};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[][] points = new double[][] {
new double[] {0.0, 0.0},
new double[] {4.0, 0.0},
new double[] {0.0, 4.0},
new double[] {4.0, 4.0}
};
Ожидаемый вывод:
string expected = "red";Пояснение
Ближайшая точка — (0, 0) (red); следующие две, (4, 0) и (0, 4), находятся на одинаковом расстоянии, поэтому побеждает меньший индекс — (4, 0) (blue). У red и blue по одному голосу, и точка red шла первой, поэтому ответ red.
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.