Tất cả thử thách
Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Bộ phân loại K láng giềng gần nhất

Dự đoán nhãn bằng cách bỏ phiếu đa số trong k điểm huấn luyện gần nhất.

Bạn sẽ học được gì

  • Tìm các điểm huấn luyện gần nhất
  • Dự đoán bằng bỏ phiếu đa số
  • Xử lý hòa phiếu một cách xác định

Đề bài

Xem bản gốc (English)

K láng giềng gần nhất (KNN) phân loại một điểm mới bằng cách xét k điểm huấn luyện gần nó nhất và lấy nhãn phổ biến nhất.

  1. Tính khoảng cách Euclid từ query đến mọi điểm.
  2. Sắp xếp các điểm theo khoảng cách; nếu hai khoảng cách bằng nhau, điểm có chỉ số nhỏ hơn đứng trước.
  3. Lấy k điểm đầu tiên và đếm nhãn của chúng.
  4. Trả về nhãn có nhiều phiếu nhất. Nếu các nhãn hòa nhau, trả về nhãn có điểm gần nhất đứng trước trong thứ tự đã sắp xếp.

Hãy cài đặt knn_predict(points, labels, query, k).

Đầu vào

points: Các điểm huấn luyện, mỗi điểm là một danh sách tọa độ.

labels: Nhãn của từng điểm.

query: Điểm cần phân loại.

k: Số láng giềng được bỏ phiếu.

Đầu ra

Trả về nhãn dự đoán.

Ràng buộc

1 ≤ k ≤ số điểm ≤ 1.000

1 ≤ số chiều ≤ 20

-1.000 ≤ mỗi tọa độ ≤ 1.000

Ví dụ

Ví dụ 1
Đầu vào:
points = [
    [1.0, 1.0],
    [2.0, 2.0],
    [8.0, 8.0],
    [9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3

Kết quả mong đợi:
expected = "A"
Đầu vào:
std::vector<std::vector<double>> points = {
    {1.0, 1.0},
    {2.0, 2.0},
    {8.0, 8.0},
    {9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;

Kết quả mong đợi:
std::string expected = "A";
Đầu vào:
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[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;

Kết quả mong đợi:
string expected = "A";

Giải thích

Khoảng cách từ (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. 3 nhãn gần nhất là A, A và B, nên đáp án là A.

Ví dụ 2
Đầu vào:
points = [
    [0.0, 0.0],
    [4.0, 0.0],
    [0.0, 4.0],
    [4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2

Kết quả mong đợi:
expected = "red"
Đầu vào:
std::vector<std::vector<double>> points = {
    {0.0, 0.0},
    {4.0, 0.0},
    {0.0, 4.0},
    {4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;

Kết quả mong đợi:
std::string expected = "red";
Đầu vào:
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[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;

Kết quả mong đợi:
string expected = "red";

Giải thích

Điểm gần nhất là (0, 0) (red); hai điểm tiếp theo, (4, 0) và (0, 4), có cùng khoảng cách, nên điểm có chỉ số nhỏ hơn là (4, 0) (blue) được chọn. Red và blue mỗi bên một phiếu, và điểm của red đứng trước, nên đáp án là red.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Tính khoảng cách Euclid từ mỗi điểm đến query, rồi xếp hạng theo khoảng cách với chỉ số nhỏ hơn thắng khi hòa.

Gợi ý 2

Chỉ k điểm đầu sau khi sắp xếp mới bỏ phiếu, nên nhãn cuối cùng chỉ phụ thuộc vào một phần rất nhỏ của training set.

Gợi ý 3

Nếu số phiếu hòa nhau, chọn nhãn có điểm đóng góp gần nhất xuất hiện sớm hơn trong danh sách láng giềng đã sắp xếp.

Độ phức tạp mong đợi

thời gian O(n log n), bộ nhớ phụ O(n)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 930 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.