CÀI ĐẶT THUẬT TOÁN KNN BẰNG MATLAB

1. Thuật toán KNN

• Thuật toán KNN ( K Nearest Neighbor) là một trong những thuật toán dùng để phân lớp đối tượng phổ biến trong ML và Data Mining.
• KNN trong Machine Learning được gọi là 1 thuật toán lười “lazy learning” bởi trong quá trình train nó không học bất cứ điều gì từ dữ liệu train, mọi tính toán đều được nó thực hiện khi có một input cần dự đoán. KNN thuộc supervise Learning

* Ý Tưởng thuật toán

KNN là thuật toán tìm label của một input dựa vào K điểm dữ liệu lân cận gần nó nhất (tức là điểm input).

hình trên minh họa cho tập train của KNN, từ tập dữ liệu train ta xét điểm input với K điểm dữ liệu gần nhất với input để tìm label cho nó.

*Các bước thực hiện thuật toán

B1: chuẩn bị tập dữ liệu (tập dữ liệu đã có sẵn label), chia tập dữ liệu ra thành 2 tập: tập train và tập test. thường tập dữ liệu sẽ được chia là 8:2, có thể tùy vào người lập trình mà tỉ lệ có thể thay đổi.

-Tập train: là tập dữ liệu đã có sẵn label dùng để huấn luyện cho thuật toán.

-Tập test: là tập dữ liệu đã có sẵn label nhưng trong quá trình đưa vào thuật toán, label này coi như là không có, chỉ khi thuật toán chạy xong, chúng ta mới dùng label này để kiểm tra tính chính xác của thuật toán.

B2: Xác định giá trị tham số K

K là 1 số tự nhiên > 0, K phụ thuộc vào người lập trình, mỗi bài toán có K khác nhau, tùy vào số lượng dữ liệu trong tập train, chúng ta sẽ lựa chọn K thích hợp.

B3: Tính khoảng cách giữa các đối tượng input cần tìm label (tức là lớp của đối tượng) với tất cả các đối tượng trong tập train để tìm ra K đối tượng gần nhất với input.

B4: Lấy tất cả các label của K đối tượng gần nhất, tìm max của các label (xác định xem label nào có số lượng nhiều nhất ta sẽ lấy label đó làm label cho đối tượng input).

hình minh họa thuật toán KNN 

Trong hình trên tập dữ liệu train bao gồm các điểm đã có sẵn label, các điểm dữ liệu được chia làm 3 cluster (cụm). Xác định K = 5, sau khi tính khoảng cách giữa điểm Xj và tất cả các điểm trong tập train tìm ra được 5 điểm gần Xj nhất, xác định nhãn của 5 điểm, ta thấy: 4 điểm màu đỏ, 1 điểm màu xanh, vậy điểm Xj có label là đỏ.

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

• Phụ thuộc vào K do người dùng lựa chọn, nếu K quá nhỏ sẽ nhạy cảm với nhiễu, K quá lớn, vùng lân cận sẽ chứa các điểm của label khác (lớp khác).
• Cần lưu tất cả các mẫu để dự đoán, bởi vì KNN chỉ tính toán khi có input cần dự đoán.
• Tốn thời gian: mỗi lần có input mới, thì thuật toán sẽ tính toán lại từ đầu, tính toán khoảng cách và k điểm lân cận.

2. Cài đặt

Để hiểu kĩ thuật toán, chúng ta sẽ làm 1 ví dụ về KNN, cụ thể là bài toán face regconition (nhận dạng gương mặt, cho biết chính xác label của mặt, cụ thể là tên hoặc là mã số dùng để phân biệt khác nhau giữa các khuôn mặt).

a) Bộ dữ liệu: chúng ta sẽ sử dụng bộ dữ liệu ORL database

• Bộ dữ liệu nhỏ gồm ảnh khuôn mặt của 40 người, mỗi người có 10 ảnh, mỗi ảnh là 32×32 pixel.

Minh họa hình ảnh gương mặt của 1 người trong bộ dữ liệu, 10 gương mặt của cùng 1 người.

Bộ dữ liệu gồm :

• Tập fea: 400 X 1024 ( 400 nghĩa là 40 người, mỗi người 10 ảnh; 1024 = 32×32 đặc trưng cho mỗi hình).
• Tập gnd: 400×1 là tập label của mỗi hình, gồm 400 hình.

 

b) Cài đặt với MATLAB

B1: Tiền xử lý

Với ORL database, ta sẽ chia tập train và tập test theo tỉ lệ 8:2, tức là mỗi người lấy ra 8 tấm ảnh để train, 2 tấm còn lại để test (như hình minh họa dưới đây)

• load database và xử lí data

• Vì tập ảnh trong database sẽ xếp theo thứ tự từ 1 đến 400, cứ 10 ảnh là 1 người, t sẽ lấy mỗi người 8 ảnh để làm tập train, 2 ảnh để làm tập test. Biến row là biến chỉ số của ảnh. tập train_set là tập lưu giá trị của 8×40 ảnh train, tập test_set là tập lưu giá trị của 2×40 ảnh test. Tập idx_train và idx_test lưu chỉ số của ảnh.

• Sử dụng idx_train và idx_test để lấy ra label cho các ảnh trong tập train và test. Biến count để xác định kết quả đúng sau khi so sánh kết quả dự đoán với kết quả thực.

B2: Xây dựng thuật toán

Với bộ dữ liệu 40 người, ta sẽ chọn K = 15, tính khoảng cách từ điểm input đến tất cả các điểm, sau đó sắp xếp kết quả và lấy K kết quả gần nhất với input.

• Ở đây, sẽ có tìm số hình xuất hiện nhiều nhất, bởi trong KNN sau khi đã dự đoán các label, ta sẽ lấy label có tần số xuất hiện nhiều nhất (tức là input gần giống với điểm này nhất) để làm output (kết quả dự đoán).
• predict_label là label đã dự đoán được từ thuật toán.
• Như đã nói ở trên, biến count dùng để đếm số lượt dự đoán đúng của thuật toán, dùng để tính độ chính xác. Độ chính xác = số lần dự đoán đúng / tổng số lần dự đoán.