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)

nktung

Super Moderator
Thành viên BQT
08/10/2013
400
985 bài viết
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)
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 đó.

K-Nearest Neighbor.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
 
Chỉnh sửa lần cuối:
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
  • Thích
Reactions: palomadoan
xin chào, các bài viết này rất dễ hiễu nhưng tôi vẫn đang tìm kiếm tổng quan về một mô hình đầy đủ quy trình với các bước làm thực tế từ giai đoạn sàn lọc dữ liệu, tiền xử lý dữ liệu (ngoài các datasheet tại kaggle v.v.. thì lấy được từ những đâu? phân loại chúng như thế nào? đưa về dạng thuần text?) - dùng các mô hình để cho máy học (cách dùng chi tiết như thế nào?) - sau khi cho máy học, có kết quả đánh giá mô hình thì làm thế nào để trực quan hóa nó (cách nào để biểu diễn số liệu?). Mong bạn hướng dẫn thêm và cho thêm keywords hiệu quả để tôi nghiên cứu thêm. Hiện những việc phân lớp data như thế này sẽ làm được những công việc thực tế gì ? có cơ hội cho người mới không? cảm ơn bạn.
 
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
  • Thích
Reactions: nktung
Comment
xin chào, các bài viết này rất dễ hiễu nhưng tôi vẫn đang tìm kiếm tổng quan về một mô hình đầy đủ quy trình với các bước làm thực tế từ giai đoạn sàn lọc dữ liệu, tiền xử lý dữ liệu (ngoài các datasheet tại kaggle v.v.. thì lấy được từ những đâu? phân loại chúng như thế nào? đưa về dạng thuần text?) - dùng các mô hình để cho máy học (cách dùng chi tiết như thế nào?) - sau khi cho máy học, có kết quả đánh giá mô hình thì làm thế nào để trực quan hóa nó (cách nào để biểu diễn số liệu?). Mong bạn hướng dẫn thêm và cho thêm keywords hiệu quả để tôi nghiên cứu thêm. Hiện những việc phân lớp data như thế này sẽ làm được những công việc thực tế gì ? có cơ hội cho người mới không? cảm ơn bạn.
Hi bạn
Câu hỏi của bạn rất hay, đúng là cần phải như vậy. Tuy nhiên trong khuôn khổ của một bài viết trên diễn đàn, thì khó có thể truyền tải hết được những nội dung mà bạn cần. Thay vào đó, muốn mang đến cho người đọc những "từ khóa" để tiếp tục tìm hiểu chi tiết hơn.
Gửi bạn một số nguồn tài liệu hữu ích:
MachineLearningcoban.com
 
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
  • Thích
Reactions: palomadoan
Comment
Bên trên