Tổng quan về thuật toán láng giềng gần k-NN

“Gần mực thì đen, gần đèn thì sáng” là một câu tục ngữ quen thuộc của người Việt, bạn có biết rằng trong Machine Learning cũng có một thuật toán mà bản chất nghĩa đen khá giống với nội dung của câu tục ngữ trên? Ở đây, tôi đang muốn nhắc đến thuật toán k-NN – một thuật toán phổ biến trong lớp thuật toán Lazy Learning.

Vậy k-NN là gì?

Cụ thể, k-NN là viết tắt của k nearest neighbours (k láng giềng gần nhất), đây là một thuật toán mà áp dụng được cho bài toán hồi quy dự đoán giá trị đầu ra liên tục và bài toán phân lớp dự đoán giá trị đầu ra rời rạc. Đúng theo tên của thuật toán, việc gán nhãn hay dự đoán kết quả của một ví dụ được dựa trên các ví dụ học gần nó nhất. Cụ thể hoạt động của thuật toán cũng như cách xác định tập láng giềng như thế nào thì chúng ta cùng tìm hiểu nhé!

Hoạt động của k-NN

Giai đoạn học: giai đoạn học của k-NN đơn thuần là lưu lại các ví dụ học mà thôi, không có sự tính toán hay ước lượng hàm mục tiêu gì ở đây cả. Thật đơn giản phải không?
Giai đoạn gán nhãn/dự đoán:
Với mỗi ví dụ z cần gãn nhán hoặc dự đoán giá trị đầu ra:
Xác định tập NB(z) bao gồm k ví dụ trong tập học có khoảng cách tới z là nhỏ nhất
Tiến hành gãn nhãn hoặc dự đoán giá trị của z dự trên nhãn lớp hoặc đầu ra của k ví dụ trong NB(z)
image

Xác định khoảng cách giữa 2 ví dụ

Một công việc quan trọng trong quá trình gãn nhãn lớp hoặc dự đoán cho ví dụ z là tính khoảng cách từ z tới từng ví dụ trong tập học. Vậy việc tính khoảng cách này như thế nào?
Đối với ví dụ có thuộc tính kiểu số thực, ví dụ như tọa độ chẳng hạn, thì chúng ta có thể dựa vào các công thức tính khoảng cách hình học như hàm Minkowski, Mahattan, Euclid để xác định khoảng cách. Cụ thể hơn nhé:
Hàm Minkowski:
image
Hàm Manhattan:
image
Hàm Euclid:
image
Còn với các ví dụ có thuộc tính kiểu rời rạc, kiểu định danh thì công việc xác định khoảng cách giữa các ví dụ khó hơn nhiều.
Đơn giản nhất ta có thể xác định khoảng cách giữa 2 ví dụ dựa trên số lượng thuộc tính có giá trị khác nhau. Ví dụ nhé
x: màu sắc = “Đỏ”, xuất xứ = “Trung Quốc”, hãng sản xuất = “A”
y: màu sắc = “Đỏ”, xuất xứ = “Thái Lan”, hãng sản xuất = “B”
Vậy thì khoảng cách giữa ví dụ x và y ở đây là 2 do có thuộc tính xuất xứ và hãng sản xuất mang giá trị khác nhau.
Tuy nhiên, trong một số trường hợp việc xác định khoảng cách dựa trên số lượng thuộc tính có giá trị khác nhau lại rất bất cập. Ví dụ nhé
x: địa điểm = “Hà Nội”
y: địa điểm = “Sài Gòn”
z: địa điểm = “Paris”
Rõ ràng khoảng cách giữa x và y bằng với khoảng cách giữa x và z (đều bằng 1), nhưng trên thực tế, rõ ràng khoảng cách giữa 2 địa điểm Việt Nam phải nhỏ hơn khoảng cách từ một điểm Việt Nam tới một điểm ở Pháp chứ. Vậy là việc áp dụng so sánh giá trị thuộc tính thô sơ rõ ràng không phải một giải pháp tối ưu, lúc này bạn phải tính đến các giải pháp ước lượng khoảng cách khác, có thể là số hóa, tùy thuộc vào đặc điểm của thuộc tính, và rất buồn là không có một công thức hay phương pháp tổng quát để giải quyết vấn đề này đâu nhé!
Một yếu tố khác nữa mà chúng ta có để xét tới là tầm ảnh hưởng của từng thuộc tính đến khoảng cách. Các thuộc tính khác nhau có thể có mức độ ảnh hưởng khác nhau tới việc xác định khoảng cách, tức là có thuộc tính mà sự chênh lệnh về giá trị dù nhỏ thôi nhưng chứng tỏ sự khác biệt giữa các ví dụ là lớn, tuy nhiên có thuộc tính thì chênh lệch xíu xíu thì có thể coi như không có sự khác biệt quá giữa chúng. Khi này ta có thể xét thêm trọng số cho các thuộc tính trong công thức xác định khoảng cách, cụ thể hơn ví dụ cho khoảng cách Euclid:
image
Trong đó wi là trọng số của thuộc tính thứ i.

Vấn đề chuẩn hóa miền giá trị thuộc tính

Cho một ví dụ đơn giản để bạn hiểu tại sao phải chuẩn hóa miền giá trị thuộc tính nhé:
Ví dụ x: tuổi = 23, lương = 23.000.000VND
Ví dụ y: tuổi = 54, lương = 24.000.000VND
Bạn thấy đấy nếu cứ áp dụng công thức tính khoảng cách đã trình bày ở trên mà không chuẩn hóa miền giá trị dữ liệu, thì gần như yếu tố lương sẽ quyết định khoảng cách giữa 2 ví dụ mà thuộc tính tuổi gần như không “đóng góp” vào mấy cả. Nguyên nhân là lương có miền giá trị quá lớn so với tuổi, vì thế nên chúng ta cần có một bước chuẩn hóa, có thể đơn giản như sau:
image

Gán nhãn lớp hoặc dự đoán kết quả đầu ra

Với việc gán nhãn lớp, thì sau khi xác định tập k láng giềng gần của z là NB(z) thì ta sẽ gán cho z nhãn lớp nào chiếm đa số các ví dụ trong NB(z).
Còn với việc dự đoán kết quả đầu ra rời rạc thì đầu ra của z đơn giản là trung bình cộng đầu ra của k ví dụ trong tập láng giềng NB(z):
image
Có thể thấy ở trong cách gán nhãn lớp hoặc dự đoán trên, ta đang đánh đồng vai trò của các ví dụ trong tập NB(z) trong việc gán nhãn hoặc dự đoán kết quả cho z. Tức là không xét tới yếu tố khoảng cách nữa, một ví dụ xa z hơn có vai trò như một ví dụ gần z hơn đối với xác định đầu ra của z, miễn là chúng đều nằm trong NB(z). Điều này với ai khắt khe, thì sẽ đặt câu hỏi: “Vô lý! Tôi gần hơn thì tôi phải có tầm ảnh hưởng nhiều hơn chứ”. Một giải pháp đưa ra là có thể xét thêm yếu tố khoảng cách trong công thức xác định đầu ra thông qua một tham số v sao cho v là nghịch đảo của d, cụ thể hơn thì:
image
Cho bài toán gãn nhãn, hoặc:
image
Cho bài toán dự đoán đầu ra liên tục.
Hàm v có thẻ xác định đơn giản như sau:
image
Đây chỉ là một trong rất nhiều cách chọn v thôi nhé!

Xác định giá trị k

Vậy giá trị k là bao nhiêu thì phù hợp? Bao nhiêu láng giềng gần thì sẽ cho hiệu quả phân loại hoặc dự đoán trị đầu ra tốt nhất? Lại rất tiếc, không có một công thức chuẩn nào cho việc xác định k. Chúng ta có thể sử dụng một tập tối ưu nhỏ nhỏ, thay đổi giá trị k để xem hiệu quả phân loại/dự đoán trên tập tối ưu này, và lựa chọn giá trị k tốt nhất.
Có một vài chú ý sau khi lựa chọn giá trị k như sau:
Không nên chọn k=1, tại sao thế? Hãy tưởng tượng chỉ có 1 ví dụ trong NB(z), và ví dụ này là ví dụ lỗi, bị gán nhãn sai, kéo theo việc gán nhãn cho z cũng sai luôn. Vậy thì chọn k=1 làm cho hệ thống rất nhạy cảm với nhiễu lỗi luôn nhé.
Với bài toán có 2 nhãn lớp cần dự đoán (nhãn dương và nhãn âm) thì nên chọn k lẻ để tránh trường hợp số ví dụ có nhãn dương và số ví dụ có nhãn âm trong tập NB(z) là bằng nhau, gân khó khăn cho việc gãn nhãn cho z.
Nếu sử dụng tất cả tập học để gán nhãn hoặc dự đoán cho ví dụ z, thì phải sử dụng thêm tham số thể hiện khoảng cách vào trong công thức xác định nhãn lớp hoặc kết quả đầu ra rời rạc nhé, không là tất cả ví dụ dự đoán bởi hệ thống sẽ chỉ thu được một đầu ra thôi. Ví dụ cụ thể hơn như tập học có 8 ví dụ nhãn dương và 4 ví dụ nhãn âm, nếu lấy cả tập để xác định nhãn lớp cho ví dụ z cần dự đoán mà không tính đến yếu tố khoảng cách, thì mọi ví dụ z đền chỉ có thể nhận nhãn dương (là nhãn chiếm nhiều hơn)

Ưu điểm

Đơn giản dễ hiểu
Làm việc được cho các bài toán có nhiều nhãn lớp mà không phải áp dụng one-vs-all
Quá trình train nhanh
Với k đủ lớn thì cho khả năng chịu nhiễu lỗi ở mức nhất định

Nhược điểm

Quá trình gán nhãn lớp, dự đoán đầu ra rất lâu
Vấn đề xử lý thuộc tính định danh để tính khoảng cách đôi lúc khá khó khăn
Không có công thức tổng quát cho xác định giá trị k phù hợp

Tài liệu tham khảo

Học dựa trên các láng giềng gần nhất- Nguyễn Nhật Quang
Link: https://users.soict.hust.edu.vn/quangnn/mldm/slides/L5-Phan_loai_va_Lang_gieng_gan_nhat.pdf

3 Likes

@nathan Ôi hay quá :smiley:
Cách em viết anh thấy thích ghê ấy, nên phải comment luôn @@@
Giờ anh ngồi đọc kỹ cái nhé, rồi hôm nào anh em mình đàm đạo nhở ^^^

Bài viết có hàm lượng nghiên cứu thuật toán kỹ càng. Đoạn mở đầu có thêm phần mô tả phạm vi ứng dụng thực tế của thuật toán thì sẽ giúp người đọc hiểu mục đích của nó trước khi xem chi tiết bên dưới.