26 lượt xem

K-nearest neighbors – Thuật toán K-lân cận gần nhất

Nếu người ta có câu “nước đến chân mới nhảy” thì trong Machine Learning cũng có một thuật toán tương tự.

Giới thiệu

Một câu chuyện thú vị:

Có một người bạn sắp thi cuối kỳ. Vì môn học đó được mở tài liệu trong kỳ thi nên anh ta không muốn bỏ công ôn tập và hiểu mối quan hệ giữa các bài học. Thay vào đó, anh ta thu thập tất cả các tài liệu từ lớp học, bao gồm ghi chú bài giảng, các slide và bài tập kèm lời giải. Để đảm bảo, anh ta còn mua tất cả các loại tài liệu quan trọng từ thư viện và các quán photocopy xung quanh trường (thật là tận tâm trong việc tìm kiếm tài liệu). Cuối cùng, anh bạn của chúng ta đã có một chồng tài liệu để mang vào phòng thi.

Vào ngày thi, anh ta tự tin mang chồng tài liệu vào phòng thi. Aha, ít nhất làm được 8 điểm. Câu 1 giống hệt bài giảng trên lớp. Câu 2 giống hệt đề thi năm trước trong tập tài liệu mua từ quán photocopy. Câu 3 gần giống với bài tập về nhà. Câu 4 là câu trắc nghiệm mà anh ta nhớ đúng ba tài liệu đều có đáp án. Câu cuối cùng, một câu khó nhưng anh ta đã từng thấy, chỉ là không nhớ chính xác ở đâu.

Kết quả cuối cùng, anh ta được 4 điểm, đủ để qua môn. Anh ta làm chính xác câu 1 vì tìm thấy trong ghi chú bài giảng. Câu 2 cũng tìm được đáp án, nhưng lời giải từ quán photocopy sai! Câu 3 gần giống bài tập về nhà, chỉ khác một chút, anh ta cho kết quả giống như vậy, nhưng không được điểm nào. Câu 4 tìm được cả 3 tài liệu, nhưng có hai trong đó cho đáp án A, cái còn lại cho đáp án B. Anh ta chọn A và được điểm. Câu 5 thì không làm được dù còn 20 phút, vì tìm mãi chẳng thấy đáp án – mệt quá!!

Xem thêm  Ôn tập hình học lớp 4: Tìm hiểu các góc và hình trong sách giáo khoa

Không phải ngẫu nhiên là tôi đã kể câu chuyện học tập của anh chàng này. Hôm nay, tôi xin trình bày về một thuật toán trong Machine Learning, gọi là K-nearest neighbors (hay KNN). Đây là một thuật toán rất giống cách học và thi của anh bạn kém may mắn kia.

K-nearest neighbors

K-nearest neighbors là một thuật toán supervised-learning đơn giản (nhưng hiệu quả trong một số trường hợp) trong Machine Learning. Khi training, thuật toán này không học gì từ dữ liệu training (đây cũng là lý do thuật toán này được gọi là lazy learning), mọi tính toán được thực hiện khi cần dự đoán kết quả của dữ liệu mới. K-nearest neighbors có thể áp dụng được vào cả hai loại bài toán Supervised learning là Classification và Regression. KNN còn được gọi là một thuật toán Instance-based hoặc Memory-based learning.

Có một số khái niệm tương ứng giữa người và máy như sau:

  • Ngôn ngữ người -> Ngôn ngữ Máy
  • Câu hỏi -> Điểm dữ liệu
  • Đáp án -> Đầu ra, nhãn
  • Ôn thi -> Huấn luyện
  • Tập tài liệu mang vào phòng thi -> Tập dữ liệu huấn luyện
  • Đề thi -> Tập dữ liệu kiểm thử
  • Câu hỏi trong đề thi -> Điểm dữ liệu kiểm thử
  • Câu hỏi có đáp án sai -> Nhiễu
  • Câu hỏi gần giống -> Điểm dữ liệu gần nhất

Với KNN, trong bài toán Classification, label của một điểm dữ liệu mới được suy ra trực tiếp từ K điểm dữ liệu gần nhất trong training set. Label của một test data có thể được quyết định bằng major voting (bầu chọn theo số phiếu) giữa các điểm gần nhất, hoặc nó có thể được suy ra bằng cách đánh trọng số khác nhau cho mỗi trong các điểm gần nhất đó rồi suy ra label. Chi tiết sẽ được nêu trong phần tiếp theo.

Xem thêm  Pure Tuber - Xem video mà không bị quảng cáo làm phiền

Trong bài toán Regression, đầu ra của một điểm dữ liệu sẽ bằng chính đầu ra của điểm dữ liệu đã biết gần nhất (trong trường hợp K=1), hoặc là trung bình có trọng số của đầu ra của những điểm gần nhất, hoặc bằng một mối quan hệ dựa trên khoảng cách tới các điểm gần nhất đó.

Một cách ngắn gọn, KNN là thuật toán tìm đầu ra của một điểm dữ liệu mới chỉ dựa trên thông tin của K điểm dữ liệu trong training set gần nó nhất (K-lân cận), không quan tâm có một vài điểm dữ liệu trong những điểm gần nhất này là nhiễu hay không.

Khoảng cách trong không gian vector

Trong không gian một chiều, khoảng cách giữa hai điểm được tính bằng hiệu giá trị tuyệt đối của hai điểm đó. Trong không gian nhiều chiều, khoảng cách giữa hai điểm có thể được định nghĩa bằng nhiều hàm số khác nhau, trong đó độ dài đường thẳng nối hai điểm chỉ là một trường hợp đặc biệt. Việc lựa chọn hàm khoảng cách phụ thuộc vào từng bài toán cụ thể.

Ưu điểm của KNN

  1. Độ phức tạp tính toán trong quá trình training là bằng 0.
  2. Việc dự đoán kết quả của dữ liệu mới rất đơn giản.
  3. Không cần giả định gì về phân phối của các class.

Nhược điểm của KNN

  1. KNN rất nhạy cảm với nhiễu khi K nhỏ.
  2. Tất cả tính toán đều nằm ở quá trình test, việc tính khoảng cách từ một điểm test data đến tất cả các điểm trong tập training set sẽ tốn rất nhiều thời gian, đặc biệt là với các tập dữ liệu lớn. Độ phức tạp càng tăng khi K càng lớn. Việc lưu toàn bộ dữ liệu trong bộ nhớ cũng ảnh hưởng tới hiệu năng của KNN.
Xem thêm  Guitar Tuna Pro Apk - Tải xuống miễn phí tại PRAIM

Tăng tốc cho KNN

Ngoài việc tính toán khoảng cách từ một điểm test data đến tất cả các điểm trong tập training set (Brute Force), còn có một số thuật toán khác để tăng tốc quá trình tìm kiếm này như K-D Tree và Ball Tree. Nhưng trên phạm vi bài viết này, chúng ta sẽ tập trung vào thuật toán KNN cơ bản.

Hãy thử áp dụng KNN cho bài toán của bạn và xem kết quả như thế nào. Đừng quên nhận xét và bình luận dưới phần Comment của bài viết này.

Trích nguồn: https://praim.edu.vn

Chào mừng bạn đến với PRAIM, - nền tảng thông tin, hướng dẫn và kiến thức toàn diện hàng đầu! Chúng tôi cam kết mang đến cho bạn một trải nghiệm sâu sắc và tuyệt vời về kiến thức và cuộc sống. Với Praim, bạn sẽ luôn được cập nhật với những xu hướng, tin tức và kiến thức mới nhất.