Thuật Toán KNN Là Gì? Giải Thích Cho Người Mới
KNN (k láng giềng gần nhất) là một thuật toán học có giám sát không tham số, không huấn luyện một mô hình riêng mà lưu lại dữ liệu đã gắn nhãn; khi có điểm mới, nó tìm k điểm giống nhất rồi để các điểm đó bỏ phiếu để chọn hạng mục hoặc lấy trung bình để dự đoán.
Trực giác đơn giản
KNN dựa trên ý rằng những dữ liệu giống nhau thường nằm gần nhau. Với một điểm cần dự đoán, thuật toán nhìn sang những điểm đã biết ở ngay bên cạnh, rồi để các điểm gần nhất quyết định kết quả, thay vì học một bộ quy tắc rút gọn.
Vì sao gọi là học thụ động
KNN không có giai đoạn huấn luyện rõ rệt; nó chỉ lưu các ví dụ và dồn mọi tính toán sang thời điểm dự đoán. Cách làm này thường được gọi là lazy learning (học thụ động). Chi phí huấn luyện gần như bằng không, nhưng chi phí tính toán tăng lên khi cần truy vấn.
Các bước KNN hoạt động
- Tính khoảng cách từ điểm cần dự đoán đến từng điểm đã lưu.
- Sắp xếp các điểm theo khoảng cách tăng dần.
- Chọn k điểm có khoảng cách nhỏ nhất.
- Với phân loại, bỏ phiếu đa số; với hồi quy, lấy trung bình giá trị của chúng.
Khoảng cách Euclid giữa hai điểm là lựa chọn phổ biến:
[ d(x, x_i) = \sqrt{\sum_{j=1}^{n}(x_j - x_{ij})^2} ]
Các phép đo khoảng cách
| Phép đo | Đặc điểm | Thường dùng khi |
|---|---|---|
| Euclid | Khoảng cách đường thẳng | Dữ liệu đã chuẩn hóa |
| Manhattan | Tổng độ lệch theo từng chiều | Đặc trưng rời rạc |
| Minkowski | Dạng tổng quát của hai phép trên | Cần điều chỉnh linh hoạt |
| Cosine | So sánh hướng vector | Dữ liệu embedding, văn bản |
Vai trò của chuẩn hóa đặc trưng
Mọi đặc trưng đều góp phần vào khoảng cách, nên đặc trưng có thang giá trị lớn dễ lấn át đặc trưng có thang nhỏ. Vì vậy pipeline KNN thường chuẩn hóa đặc trưng trước, ví dụ để tuổi và thu nhập đóng góp ở mức tương đương.
Chọn k như thế nào
Số láng giềng k ảnh hưởng đến kết quả. k nhỏ có thể nhạy với nhiễu, trong khi k lớn dễ làm mịn quá mức và bỏ qua chi tiết cục bộ. Một cách thường gặp là thử nhiều giá trị k và so sánh kết quả để chọn mức phù hợp với dữ liệu.
Ưu điểm và hạn chế
KNN dễ hiểu, dễ áp dụng và không giả định một dạng phân phối cố định. Mặt khác, nó cần lưu toàn bộ dữ liệu và chi phí truy vấn tăng khi tập dữ liệu lớn, nên việc chọn phép đo khoảng cách và chuẩn hóa đặc trưng cần được kiểm tra cẩn thận.
FAQ
KNN là phân loại hay hồi quy?
KNN dùng được cho cả hai: phân loại dựa trên bỏ phiếu đa số, hồi quy dựa trên trung bình giá trị của k láng giềng.
Vì sao KNN được gọi là học thụ động?
Vì nó không xây dựng mô hình ở giai đoạn huấn luyện, chỉ lưu dữ liệu và tính toán khi có truy vấn.
Có cần chuẩn hóa đặc trưng không?
Thường là có, vì đặc trưng thang lớn sẽ chi phối khoảng cách nếu không đưa về mức tương đương.
Chọn k nhỏ hay k lớn?
k nhỏ dễ nhạy với nhiễu, k lớn dễ làm mịn quá mức; nên thử nhiều giá trị và đối chiếu kết quả thực tế.
Điểm chính
- KNN tìm k điểm gần nhất và để chúng quyết định kết quả.
- Đây là phương pháp học thụ động, không tham số.
- Euclid là phép đo khoảng cách thường gặp.
- Chuẩn hóa đặc trưng và chọn k là hai bước cần kiểm tra.
Đọc tiếp machine learning là gì và học có giám sát là gì.
Sources
Learn by doing
Read a guide, then practice with bite-sized AI lessons you can take offline.
Start learning free