Thuật Toán KNN Là Gì? Giải Thích Cho Người Mới

Updated · By Viviai

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

  1. Tính khoảng cách từ điểm cần dự đoán đến từng điểm đã lưu.
  2. Sắp xếp các điểm theo khoảng cách tăng dần.
  3. Chọn k điểm có khoảng cách nhỏ nhất.
  4. 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

Đọc tiếp machine learning là gì và học có giám sát là gì.

Sources

  1. https://users.soict.hust.edu.vn/huonglt/AI/Chuong%206.%20Hoc%20may%20(1).pdf
  2. https://www.ultralytics.com/vi/glossary/k-nearest-neighbors-knn
  3. https://www.studocu.vn/vn/document/dai-hoc-kinh-te-quoc-dan/quan-ly-cong-nghe/cac-cong-nghe-hien-dai-dai-hoc-kinh-te-quoc-dan/78358601

Learn by doing

Read a guide, then practice with bite-sized AI lessons you can take offline.

Start learning free