Phân lớp dữ liệu bằng thuật toán những người láng giềng gần nhất (K-Nearest Neighbors)

Thảo luận trong 'AI' bắt đầu bởi nktung, 14/07/20, 11:07 PM.

  1. nktung

    nktung Super Moderator Thành viên BQT

    Tham gia: 08/10/13, 04:10 AM
    Bài viết: 869
    Đã được thích: 343
    Điểm thành tích:
    83
    Thuật toán KNN được sử dụng phổ biến trong việc phân lớp dữ liệu. Để phân lớp một mẫu dữ liệu mới gặp, ta sẽ xem mẫu dữ liệu đó giống với mẫu dữ liệu nào ở trong tập dữ liệu mà ta đang có. Tiếp theo ta chọn k mẫu dữ liệu giống với mẫu dữ liệu mới gặp, và xem trong k mẫu đó thì lớp nào chiếm đa số thì mẫu mới sẽ thuộc lớp đó.

    upload_2020-7-14_23-55-21.png
    Hình. Ví dụ về việc phân lớp với k​
    Như trên hình ta có 2 lớp dữ liệu: lớp màu tím và lớp màu vàng. Câu hỏi là nếu chấm một điểm hình sao ở vị trí như trong đồ thị, thì hình sao này thuộc lớp nào?

    - Nếu ta chọn k=3 thì hình sao gần với 3 điểm trong hình tròn. Trong 3 điểm này thì có 2 điểm màu tím và 1 điểm màu vàng. Vì vậy ngôi sao thuộc lớp màu tím

    - Nếu ta chọn k=6 thì ngôi sao gần với 4 điểm vàng và 2 điểm tím (trong vòng tròn to), do vậy ngôi sao thuộc lớp màu vàng.

    Như vậy có thể thấy thuật toán K-NN phụ thuộc vào k.

    Lưu ý: khi k lớn ta luôn có thể xác định được lớp của mẫu dữ liệu mới, còn khi k nhỏ thì có thể bị nhiễu.

    Thuật toán

    Input: Cho tập dữ liệu D có N mẫu và một điểm dữ liệu x; Cần kiểm tra xem thuộc lớp nào

    - Bước 1. Tính giá trị tất cả các khoảng cách Euclid từ x đến mọi điểm trong tập D.

    - Bước 2. Chọn k điểm trong tập D mà có khoảng cách đến x là nhỏ nhất; trong k điểm này, tính xem lớp nào có nhiều điểm nhất.

    Output: gán x thuộc lớp có nhiều điểm nhất.

    Ví dụ: Cho tập dữ liệu gồm 4 mẫu như bên dưới
    upload_2020-7-15_9-58-55.png
    Câu hỏi: nếu có mẫu (CO2, bụi mịn) là (3,2) thì môi trường là tốt hay xấu?

    B1. Tính khoảng cách từ mẫu cần đánh giá (3,2) tới các mẫu trong bảng
    upload_2020-7-15_9-59-44.png
    B2. Chọn ra k=3 mẫu có khoảng cách gần nhất (9, 13, 16), thấy có 2 mẫu tốt và 1 mẫu xấu. Vì vậy mẫu môi trường đó là Tốt







     

    Các file đính kèm:

    Chỉnh sửa cuối: 15/07/20, 09:07 AM
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan