Giới thiệu về thuận toán K láng giềng (K nearest neighbor) trong machine learning

Giới thiệu sơ lược về thuật toán K láng giềng  

Thuật toán K láng giềng gần nhất (K nearest neighbor) viết tắt là KNN. Đây là thuật toán sử dụng trong machine learning với phương pháp học có giám sát để phục vụ cho việc đưa ra quyết định hoặc dự đoán tương lai.

KNN sử dụng công thức toán học để chọn ra K phần tử gần nhất từ tập dữ liệu data trainning để đưa ra quyết định. Thuật toán hoạt động trên nguyên lý hãy cho tôi biết những người xung quanh bạn tôi sẽ nói về bạn.

Bài toán ứng dụng thuật toán

Không dài dòng thêm nữa bỏ qua phần lý thuyết ở trên cùng đến với một ví dụ cụ thể để hiểu hơn về thuật toán này nhé. 

Có một cô gái T là developer cô gái xinh đẹp giỏi giang, lại là dân kĩ thuật nên rất cá tính và được rất nhiều người theo đuổi. Cô không biết phải chọn ai trong số nhưng anh chàng đang tán tỉnh và theo đuổi mình. Với lợi thế là một developer, cô quyết định code một chương trình để nó có thể giúp cô đưa ra quyết định những anh chàng kia có phù hợp để trở thành người bạn trai của cô không?  

Cô bắt đầu tự nghĩ ra những quy chuẩn để đánh giá những anh chàng đó :
Như bao cô gái khác cô đưa ra 3 yếu tố :
1. đẹp trai
2. nhà giàu
3. học giỏi và hài hước (sự tương đồng trong giao tiếp và nói chuyện) 

Tuy nhiên nghe 3 khái niệm có vể trừu tượng quá cô đổi chúng thành :
1. ngoại hình
2. kinh tế
3. học thức và hài hước

Chúng được đánh giá trên thang điểm từ 0 – 1 có thể hiểu là trên thang điểm 10 cũng được  

Cô bắt đầu nghĩ đến tập dữ liệu tranning của mình đó là
1. những anh chàng hình mẫu lý tưởng,
2. những anh chàng không thể nào yêu thương được
3. những anh chàng đã từng là người yêu  

Từ những hình mẫu lý tưởng và người cô đã từng yêu có tập trainning như trên 

Cô bắt đầu sử dụng đến thuật toán KNN để nhờ máy tính đưa ra quyết định anh chàng H đang tán tỉnh cô xem có phù hợp hẹn hò hoặc làm chồng không ? 

Anh H có các chỉ số như sau : ngoại hình 7đ, kinh tế 5đ, học thức 4đ, hài hước 7đ 

Giờ sẽ tính khoảng cách của anh H với 10 người ở trên với công thức sau euclidean : 

Ta có khoảng cách của anh H với anh chàng số 1 trong tập dữ liệu mẫu: 

d(H,1) = sqrt((0.7-0.9)2  + (0.5-0.8)2  + (0.4-0.6)2  + (0.7-0.6)2  ) = sqrt(0.18) 

tương tự ta có khoảng cách với các anh chàng trong tập dữ liệu mẫu như sau: 

kết quả

• Giả sử đặt k = 3 từ đó cô tìm ra 3 anh chàng có khoảng cách gần với anh H nhất là anh chàng số 7, 8, 10 
• Trong 3 anh chàng này sẽ lấy số lượng có kết quả nhiều nhất
•  3 anh chàng kia đều có kết quả là có => anh H phù hợp đề làm người yêu hoặc chồng  

K thường được chọn là số lẻ vì trong trường hợp anh chàng số 7, 8 , 10 và anh chàng số 7, 8 có kết quả là không nhưng chàng số 10 có kết quả là có thì kết luận anh chàng H là không phù hợp để làm chồng

Kết luận

•  Rõ ràng việc lựa chọn k có thể sẽ ảnh hưởng đến độ chính xác của thuật toán
• Với tập dữ liệu trainning đủ lớn và có thể đưa ra số k lớn và hợp lý độ chính xác sẽ tăng lên rất nhiều

Đây chỉ là một ví dụ vui để có thể hiểu về thuật toán, nếu bài viết này được nhiều sự quan tâm thì bài sau mình sẽ viết tiếp sử dụng matlab hoặc python để nhận diện chữ số với thuật toán KNN với tập dữ liệu trainning là khoảng 700 ảnh và input sẽ là 1 ảnh bất kì để sử dụng thuật toán nhận dạng
Input có thể là ảnh như sau :    thuật toán có thể nhận diện ra đây là số 1 hay số 7

Tài liệu tham khảo:

• https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
• http://bis.net.vn/forums/t/370.aspx

Cám ơn mọi người đã quan tâm