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 neighborviết tắt  KNN. Đây là thuật toán sử dụng trong machine learning với phương pháp họ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  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  thuyết ở trên cùng đến với một  dụ cụ thể để hiểu hơn về thuật toán này nhé. 

 một cô gái T  developer cô gái xinh đẹp giỏi giang, lại  dân  thuật nên rất  tính  đượ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  theo đuổi mình. Với lợi thế  một developer, cô quyết định code một chương trình để   thể giúp cô đưa ra quyết định những anh chàng kia  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  hài hước (sự tương đồng trong giao tiếp  nói chuyện) 

Tuy nhiên nghe 3 khái niệm  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  hài hước

Chúng được đánh giá trên thang điểm từ 0 – 1  thể hiểu  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 đó 
1. những anh chàng hình mẫu  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  người yêu  

stt 

Ngoại hình 

Kinh tế  Học thức  Hài hước 

Ghi chú 

Kết quả 
1  0.9  0.8  0.6  0.6  chả  ý do   không chọn cả  có (lấy làm chồng) 
2  0.4  0.9  0.8  0.3    không 
3  0.9  0.3  0.3  0.4    không 
4  0.5  0.3  0.9  0.5    không  
5  0.3  0.5  0.3  0,3    không 
6  0.3  0.9  0.3  0.2  đã xuấu lại còn  duyên  không 
7  0.6  0.5  0.5  0.9     
8  0.6  0.7  0.7  0.7     
9  0.4  0.6  0.8  0.5     
10  0.9  0.4  0.7  0.6     

 

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

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  phù hợp hẹn  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  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  khoảng cách với các anh chàng trong tập dữ liệu mẫu như sau: 

d(H,1)  d(H,2)  d(H,3)  d(H,4)  d(H,5)  d(H,6)  d(H,7)  d(H,8)  d(H,9)  d(H,10) 
sqrt(0.18) 

 

sqrt(0.57) 

 

sqrt(0.18) 

 

sqrt(0.39) 

 

sqrt(0.33) 

 

sqrt(0.58) 

 

sqrt(0.06) 

 

sqrt(0.14) 

 

sqrt(0.30) 

 

sqrt(0.15) 

 

kết quả

  • Giả sử đặt k = 3 từ đó cô tìm ra 3 anh chàng  khoảng cách gần với anh H nhất  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  kết quả   => 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:

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

Add a Comment

Your email address will not be published.