Ở bài trước [ML] Classification – Part 1 tôi đã giới thiệu về “Classification” trong Machine Learning. Tôi cũng đã có giới thiệu một vài ví dụ về việc áp dụng trong thực tế (ngân hàng, bệnh viện …) và chúng ta đã bắt đầu làm quen với “Iris Dataset”.

Quay trở về câu chuyện với hoa Iris, nên nhớ rằng chúng ta có danh sách các bông hoa, được mô tả bởi chiều dài và chiều rộng của đài hoa và cánh hoa (các thuộc tính). Ngoài ra chúng ta cũng biết được các loại hoa, ngoài trừ 1 bông hoa duy nhất (tạm gọi đó là bông hoa kỳ bí), và chúng ta muôn tìm được loại (Lớp) của bông hoa đó. Do vậy, từ giờ trở đi, tôi sẽ giải thích các thuật toán để xác minh và phân tích các thuộc tính, để làm rõ danh tính của bông hoa Iris kỳ bí này.

• Giải pháp 1: Tìm các đối tượng theo dõi giống nhau (same observation ). 

Giải pháp đầu tiên, đơn giản nhất được đưa ra là quan sát các bông hoa Iris khác, xem bông nào có cùng chiều dài và chiều rộng của đài hoa và cánh hoa, nếu chúng ta tìm thấy bông hoa giống đó, thì Loại hoa đó chính là loại của bông hoa Iris kỳ bí rồi 

Tuy nhiên thực tế là không có chuyện dễ như trở bàn tay như vậy, đây là 1 việc rất hiếm khi xảy ra, bởi luôn luôn có 1 sự sai lệch về kích thước của các bông hoa, do đó solution này cũng không có ý nghĩa lắm lắm, và mức độ chính xác cũng rất thấp.

• Solution 2: Giải pháp hàng xóm gần nhất  (1-nearest neighbors).
  

Thay vì việc tìm kiếm các đối tượng có các thuộc tính giống y hệt nhau, chúng ta nên chuyển hướng sang tìm kiếm các đối tượng có độ tương đồng cao nhất. Nếu 2 đối tượng có các thuộc tính chiều dài, chiều rộng giống nhau, rất có thể chúng cùng thuộc 1 loại.

Tuy nhiên có trường hợp 1 vài hoa Iris thuộc các loại khác nhau, nhưng lại trông giống giống với bông hoa kỳ bí, do đó lại tiếp tục phát sinh vấn đề. Do đó, thay vì việc tìm kiếm các bông hoa Iris giống nhau, chúng ta phải tìm 1 bông hoa Iris trông giống nhất. Điều đó có nghĩa là , chúng ta phải định nghĩa 1 cách rất chi tiết và chính xác về khái niệm giống nhau giữa các bông hoa Iris. Ngoài ra chúng ta cần làm rõ việc tại sao bông hoa này lại giống với bông hoa kỳ bí, mà không phải là bông hoa khác.

Giải pháp được sử dụng bởi các nhà khoa học là định nghĩa khoảng cách (distance) giữa 2 bông hoa. Nếu khoảng cách này lớn, nghĩa là chúng nó sự khác biệt. Còn ngược lại, nếu khoảng cách nhỏ, nghĩa là chúng giống nhau. Có rất nhiều cách để định nghĩa và tính toán khoảng cách này. Trong bài viết này, tôi sẽ giới thiệu 1 kỹ thuật mà các nhà khoa học máy tính thường xuyên sử dụng: Khoảng cách Euclidean. Khoảng cách này được tính bằng khoảng cách theo 1 đường thẳng giữa 2 vật (khoảng cách chim bay).

Tuy nhiên việc tính toán khoảng cách Euclidean giữa 2 điểm trên bản đồ là rất đơn giản, nhưng có thể việc tính toán khoảng cách Euclidean giữa 2 bông hoa Iris sẽ gây khó hiểu cho nhiều người.

Để tính toán khoảng cách này, chúng ta cần nhớ lại 1 vài công thức toán học về “Bình Phương” và “Căn bậc 2” của 1 số. Ví dụ: Bình thương của 2 là 4, của 3 là 9. Căn bậc 2 của 4 là 2, của 9 là 3.

Trở về với vấn đề khoảng cách hiện tại: để tính toán khoảng cách Euclidean, việc chúng ta cần làm và tính toán tổng của bình thường các sai lệch của giá trị thuộc tính, sau đó lấy căn bậc hai của tổng đó. Ví dụ cho việc tính toán khoảng cách giữa các bông hoa Iris mà có các thuộc tính như sau:

Khoảng cách của 2 bông hoa đầu tiên là:

Khoảng cách của bông hoa thứ nhất là thứ 3 là:

Kết quả của phép toán thứ 2 nhỏ hơn ( 3.70 < 3.90). Điều đó có nghĩa là bông hoa Iris đầu tiên giống với bông hoa Iris thứ 3 hơn là giống với bông hoa thứ 2.

Đến thời điểm hiện tại, chắc là bạn cũng đã hiểu phần nào về việc tìm bông hoa gần giống nhau nhất rồi đúng không? Đơn giản chỉ là việc tính toán khoảng cách giữa bông hoa kỳ bí và tất cả các bông hoa khác, sau đó lựa chon bông hoa có khoảng cách ngắn nhất là xong.

Giải pháp tưởng chừng quá đơn giản này hiện đang là 1 giải pháp thực sự mà nhiều nhà khoa học đang sử dụng. Tên gọi của giải pháp này là “1-nearest neighbors”.

• Solution 3: Giải pháp k – hàng xóm gần nhất  (k-nearest neighbors).

Hầu hết là giải pháp “1-nearest neighbors” hoạt động tốt, tuy nhiên trong vài trường hợp, nó có thể hoạt động kém hiệu quả do một vài lý do. Một trong những lý do đó có thể là việc đo lường, tính toán có sai số, dẫn đến việc không chính xác. Trong trường hợp này, khoảng cách đo được cũng không đảm bảo được độ chính xác, và thuật toán sẽ không có tác dụng trong việc tìm ra Class đúng nhất của bông hoa kỳ bí.

Cái khó ló cái khôn, các nhà khoa học đã tìm ra giải pháp khác để giải quyết vấn đề này: Thay vì tìm kiếm bông hoa Irsi giống nhất  (hoa có khoảng cách nhỏ nhất), họ tìm ra 5 bông hoa gần giống nhất. Hay nói 1 cách khác, họ tìm kiếm 5 bông hoa có khoảng cách nhỏ nhất với bông hoa kỳ bí. Nếu tất cả các bông hoa này có chung Loại, thì vấn đề trở nên đơn giản: Loại của bông hoa kỳ bí chính là loại của 5 bông hoa.

Tuy nhiên trong trường hợp xấu nhất, 5 bông hoa này lại có loại khác nhau, thì 1 việc khác lại cần được xử lý: Trong trường hợp này, các nhà khoa học cần đếm số lượng các bông hoa của từng Loại, là loại của Loại nào có số lượng bông hoa nhiều nhất, thì sẽ là Loại của bông hoa kỳ bí. Ví dụ: có 5 bông hoa gần giống nhau nhất: 1 là Setosa, 1 là Versicolour và 3 bông còn lại là Viginica. Do đó Loại của bông hoa kỳ bí chắc chắn là Viginica rồi.

Giải pháp này được gọi là “5-nearest neighbors”.

Bây giờ bạn sẽ thắc mắc là tại sao là 5, mà không phải là 2, 10 hoặc 50?

Đúng vậy, các thuật toán này được gọi là 2-nearest neighbors, 10-nearest neighbors và 50-nearest neighbors. Việc xác định thuật toán nào là tốt nhất, là câu trả lời rất khó, nó phụ thuộc vào rất nhiều vấn đề. Tôi sẽ không bàn luận nhiều về vấn đề đó tại đây, tuy nhiên bạn cần phải hiểu là trong thực tế, các nhà khoa học thường phải kiểm tra tất cả các giá trị và chọn ra giá trị tốt nhất.

Các nhà khoa học gọi chung thuật toán này là “k-nearest neighbors”.

Ở thời điểm đọc xong bài viết này, chắc hẳn bạn đã có thêm hiểu biết về thuật toán “k-nearest neighbors” . Trong bài viết sau, tôi sẽ giới thiệu thêm về thuật toán mới hơn, phức tạp và mạnh mẽ hơn, với tên gọi là “Random Forest”.