K-Nearest Neighbors

K-NN không học tham số mô hình toàn cục. Nó dự đoán dựa trên nhãn của các điểm huấn luyện gần trong không gian đặc trưng.

Với điểm truy vấn x, chọn K mẫu gần nhất và tổng hợp nhãn bằng đa số (hoặc bỏ phiếu có trọng số).

$$\hat{y}(x)=\arg\max_c \sum_{i\in \mathcal{N}_K(x)} w_i\,\mathbf{1}(y_i=c)$$

• K nhỏ: ranh giới linh hoạt nhưng nhạy với nhiễu cục bộ.
• K lớn: ranh giới mượt hơn, phương sai thấp hơn, có thể tăng bias.
• Bỏ phiếu có trọng số (w=1/d) tăng ảnh hưởng của láng giềng rất gần.

Vì K-NN dựa trên khoảng cách, chuẩn hóa đặc trưng rất quan trọng. Chuẩn hóa thường tăng độ tin cậy.

Chi phí dự đoán tăng theo kích thước dữ liệu do phải tính khoảng cách với nhiều mẫu.

Dùng tập kiểm tra để chọn K và đánh giá độ bền với dữ liệu nhiễu hoặc chồng lấp.