Được sử dụng cho cả việc phân loại và hồi quy, tuy nhiên được sử dụng nhiều cho phân loại. Thuật toán KNN: tìm kiếm k hàng xóm gần nhất( gần nhất theo một khái niệm nào đó) so với vị trí đang xét.
Các hàm tính toán khoảng cách có thể là Euclidean, Manhattan, Minkowski và Hamming. Đầu tiên, 3 hàm ở đầu đều được sử dụng cho các hàm liên tục và hàm thứ 4 (Hamming) thì cho các biến phân loại.
kNN có thể dễ dàng liên tưởng tới thực tế, khi bạn muốn tìm hiểu một người nào đó – người mà bạn chưa hề có một thông tin gì, bạn sẽ tìm hiểu bằng cách tiếp cận bạn bè của người đó.
Một bài toán đơn giản, bạn bắt đầu với 2 tập user đã được phân loại sẵn như hình (tượng trưng bằng hình vuông đỏ và hình tròn xanh) – sau đó, bạn tạo một data point mới(hình vuông xám), bạn sẽ phân loại nó bằng cách nhìn vào các data point có sẵn.
Trong trường hợp này, nếu ta set k = 1, bạn có thể thấy ngay data point gần với hình vuông xám nhất là hình vuông đỏ, chính vì vậy data point mới này được phân loại là hình vuông đỏ.
Lưu ý rằng, đôi khi bạn set value cho k quá thấp, nó có thể là một đối tượng ngoại lai (outlier subject), nhưng nếu value của k quá cao, sẽ dẫn đến việc bị bỏ qua các class khi tập data mẫu (data sample) quá bé → vậy làm thế nào để set được value của k phù hợp nhất với data mà mình có ?
