Giới thiệu về KNN

K-Nearest Neighbors (KNN) là một thuật toán học có giám sát (supervised learning), được dùng cho cả bài toán phân loại và hồi quy. Thuật toán này đơn giản nhưng mạnh mẽ, thường được dùng làm mô hình cơ sở để so sánh với các mô hình phức tạp hơn.

Thuật toán KNN tìm các đặc trưng tương đồng bằng cách dùng thước đo khoảng cách (distance metric) để xác định những điểm lân cận gần nhất với một điểm. Ví dụ, thuật toán có thể phân loại rượu vang bằng cách so sánh từng loại với những loại gần giống nhất, chẳng hạn nhóm các loại rượu có hương vị tương tự vào cùng một nhóm. Thuật toán giống như một người hướng dẫn giúp bạn tìm ra những loại rượu vang giống nhau dựa trên các đặc điểm chung nhất. 🍷
Ý tưởng đằng sau KNN khá đơn giản:

1. Tính khoảng cách: Với một điểm kiểm tra, thuật toán tính khoảng cách giữa điểm đó và mọi điểm khác trong tập dữ liệu huấn luyện. Có thể tính khoảng cách theo nhiều cách, chẳng hạn như khoảng cách Euclid hoặc khoảng cách Manhattan.
2. Tìm các điểm lân cận gần nhất: Sau đó, thuật toán chọn k điểm trong dữ liệu huấn luyện gần điểm kiểm tra nhất. Người dùng xác định hằng số k, và k có thể là bất kỳ số nguyên nào.
3. Đưa ra dự đoán: Với bài toán phân loại, thuật toán gán cho điểm kiểm tra nhãn lớp xuất hiện nhiều nhất trong số k điểm lân cận gần nhất. Với bài toán hồi quy, thuật toán gán giá trị trung bình của k điểm lân cận gần nhất.

KNN là thuật toán học lười (lazy learning), nghĩa là thuật toán không thực sự học một mô hình. Thay vào đó, thuật toán ghi nhớ các mẫu dữ liệu huấn luyện và dùng chúng để dự đoán. Bài học tiếp theo sẽ trình bày giai đoạn huấn luyện. Vì vậy, KNN đòi hỏi nhiều tài nguyên tính toán trong giai đoạn kiểm tra.

Dù đơn giản, KNN vẫn có thể đạt hiệu suất tốt ngoài mong đợi. Tuy nhiên, thuật toán nhạy với lựa chọn k và loại thước đo khoảng cách. Thuật toán cũng hoạt động không tốt với dữ liệu có nhiều chiều do lời nguyền số chiều.